Tabu keresés középtávú memóriával

Az előbb láttuk a rövidtávú memória szerepét a ciklusok elkerülésére. A tabu módszer megkülönböztet ezen felül középtávú és hosszútávú memóriát is. A középtávú memória szerepe, hogy ígéretes irányokba terelje az algoritmust, míg a hosszútávú memória szerepe az eddig még felderítetlen területek elérése. Komolyan el lehet filozofálni, hogy az általunk a most következő részben követett módszer melyik fajta memóriát is használja. Mi úgy véljük, hogy ez középtávúnak tekinthető, ezért is hivatkozunk rá ilyen névvel a későbbiekben.

A következőket csináljuk: felveszünk egy tömböt, mely megadja, hogy adott dimenzióban elmozdultunk-e már kiindulási ponthoz képest. Bizonyos időközönként kiválasztunk egy olyan irányt, amerre még nem jártunk, és ebbe az irányba lépünk egyet. Ha már ilyen irány nem létezik, akkor tetszőleges irányba teszünk meg egy lépést.

Középtávú memória használata

Lehetőség van rá, hogy korábbi lépéseinkről feljegyzéseket készítsünk, és ezt is figyelembe véve tegyük meg a lépést. Mivel a tárhely véges, nem a teljes lépést tudjuk lejegyezni és visszakeresni, csak bizonyos jellemzőit. Esetünkben ez nem lesz más, mint a lépés iránya.

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
import java.util.Random;
/**
 * Középtávú memória kezelése.
 * Nyomon követjük, hogy melyik irányba nem léptünk még.
 * @author Aszalós László
 */
public class TabuMoveIntermediateTools extends TabuMoveTools {

Ebben az osztályban viszonylag egyszerűen valósítjuk meg, hogy a programunk minden irányban keressen. Egy logikai tömbben tároljuk, hogy az adott irányt már felhasználtuk-e vagy sem:

private boolean[] notYet;

Ezek után ha megtesszünk egy lépést, akkor azt is fel kell jegyezni, hogy ebbe az irányba már haladtunk:

@Override
protected void chooseStepRestricted(StateR x, int direction, int step) {
    x.setRestrictedValue(direction, step);
    notYet[direction] = false; 
}

Természetesen ezt a memóriát is inicializálni kell. Ehhez be kell állítani a méretét, és fel kell tölteni:

/**
 * Középtávú memória inicializálása.
 * @param size memória mérete
 */
void init(int size) {
    notYet = new boolean[size];
    Arrays.fill(notYet, true);
}

Következzen eme memória használata! Keresünk egy nem használt irányt. Mivel a lépések megadásánál már elég szerepet kapott a véletlen talán nem hibázunk nagyot, ha most az első még nem használt irányt választjuk ki.

Persze egy idő után már nem lesz ilyen irány, ekkor véletlenszerűen választunk a lehetséges irányok közül. Ha viszont még van, és ebbe az irányba lépünk, akkor ezt is fel kell jegyezni:

/**
 * A keresési tér még nem vizsgált része fele mozdulunk.
 * @param x aktuális állapot
 * @return kiválasztott dimenzió
 */
int newDirection(StateR x) {
    Random random = new Random();
    int j = 0;
    while (j < notYet.length && !notYet[j]) { j++; }
    if (j == x.numberOfRestrictedNeighbours()) {
        j = random.nextInt(x.numberOfRestrictedNeighbours() - 1) + 1;
    } else {
        notYet[j] = false; 
    }
    return j;
}}

Absztrakt módszer középtávú memóriával

Az előző fejezetben csak a rövidtávú memóriára hagyatkoztunk. Ebben a fejezetben további információkat is felhasználunk a korábbi lépéseinkről:

package hu.unideb.inf.optimization.methods;
/**
 * Adott lépésszám után egy még eddig nem szereplő lépést tesz meg.
 * @author ASZALÓS László
 */
abstract public class TabuIM extends TabuCommon {

A korábbiakhoz hasonlóan most is három módszerrel derítjük majd fel az aktuális pont környezetét:

3.8. ábra - Segédosztályok a lépés kiválasztására

Segédosztályok a lépés kiválasztására

A variánsokban használt közös metódusokat itt is kiszerveztük egy külön osztályba:

TabuMoveIntermediateTools tmi = new TabuMoveIntermediateTools();

Újdonság a korábbi osztályhoz képest, hogy egy új paramétert kell bevezetnünk, amely jelzi, hogy hány lépés után kell új irányt keresnünk:

protected int STEPS;

Ezt a paramétert is a megszokott módon olvassuk be:

@Override
public void constants(String name, int numerator, int denominator) {
    super.constants(name, numerator, denominator);
    if (name.equals("STEPS")) {
        STEPS = numerator;
    }
}

Ezek után ha nem a paraméter többszöröse az aktuális lépésszám, akkor az előző osztályban leírt módon lépünk tovább. Ha viszont az, akkor a kiválasztott irányban megkeressük a legjobb lépést, és megtesszük:

@Override
public StateR solve(StateR x) {
    init(x);
    tmi.init(x.numberOfRestrictedNeighbours());
    for (int step = 0; step < LIMIT; step++) {
        if (0 == step % STEPS) {
            HillClimbingTools hc = new HillClimbingTools();
            int direction = tmi.newDirection(x);
            tmi.chooseStepRestricted(x,direction,hc.bestStepOne(direction,x));
            x.calculate();
            if (x.getValue()<xMin.getValue()){
                xMin = (StateR) x.copy();
            }
        } else {
            if (tabuStep(x, xMin.getValue(),tmi)) {
                x.calculate();
                xMin = (StateR) x.copy();
            }
        }
    }
    return xMin;
}

Ahogy az előbb, most sem konkretizáljuk az egyes lépéseket:

abstract protected boolean tabuStep(StateR d, int value,
        TabuMoveIntermediateTools tm);
}

Középtávú memória - teljes környezet

Az első esetben átvizsgáljuk a teljes környezetet:

package hu.unideb.inf.optimization.methods;
/**
 * Az összes szomszédot figyelembe vesszük. 
 * @author Aszalós László
 */
public class TabuIMAll extends TabuIM {

Ehhez az a metódust kell meghívni, amely a teljes környezetet átvizsgálja:

@Override
protected boolean tabuStep(StateR x, int minValue, TabuMoveIntermediateTools tm) {
    return tm.isNBetter(x, minValue, tabu);
}}

Középtávú memória - véletlen szomszédok

A második módszer véletlen módon válogat a szomszédokból:

package hu.unideb.inf.optimization.methods;
/**
 * Véletlen elemek vizsgálata.
 * @author Aszalós László
 */
public class TabuIMFirstBetter extends TabuIM {
    @Override
    protected boolean tabuStep(StateR x, int minValue, 
                    TabuMoveIntermediateTools tm) {
        return tm.isFBetter(x, minValue, MAX_STEPS, tabu);
    }

Ez a lépéssorozat használ egy paramétert:

private int MAX_STEPS;

A paraméter értékét a szokott módon állítjuk be:

@Override
public void constants(String name, int numerator, int denominator) {
    super.constants(name, numerator, denominator);
    if (name.equals("MAX_STEPS")) {
        MAX_STEPS = numerator;
    }
}}

Középtávú memória - szűkített környezetek

A harmadik variáns pár irányt vizsgál át:

package hu.unideb.inf.optimization.methods;
/**
 * Csak néhány szűkített tartományban keresünk.
 * @author ASZALÓS László
 */
public class TabuIMOne extends TabuIM {

Ebben az esetben is a megfelelő metódust kell meghívni:

@Override
protected boolean tabuStep(StateR x, int minValue, TabuMoveIntermediateTools tm) {
    return tm.isRBetter(x, DIRECTIONS, minValue, tabu);
}

A módszer a korábbiakhoz hasonlóan használ egy paramétert:

private int DIRECTIONS;

A paraméter értékét a szokott módon állítjuk be:

@Override
public void constants(String name, int numerator, int denominator) {
    super.constants(name, numerator, denominator);
    if (name.equals("DIRECTIONS")) {
        DIRECTIONS = numerator;
    }
}}

Feladatok

  1. Készítse el a newDirection metódus olyan variánsát, melyben a rutin számolja, hogy a program mely irányba hány lépést tett, és olyan irányba javasoljon lépést, amely fele a legritkábban haladt.

  2. Építse be a hosszú távú memóriát a programba!