Tabu keresés

A hegymászó keresés minden lépésben megpróbál egy jobb állapotot találni, így egy idő után lokális minimumba jut, ahonnan nem tud elszabadulni. A tabu keresés megpróbálja elkerülni a már meglátogatott állapotokat, és minden lépésben egy új állapotot fedez fel, így akár a minimum *állapotgödréből* is kimászik.

Ehhez az x pont N(x) környezetének csak N'(x) részét használhatja fel. Az N'(x) meghatározása több módon is történhet. Rövid távú memória az utolsó n állapotot, vagy annak bizonyos jellemzőit tárolja. Tiltott (tabu) olyan lépés megtétele, mely a rövid távú memóriában szerepel. Egy kivétel van ez alól, ha a lépéssel kapott célfüggvény érték jobb az eddig tárolt legjobbnál. Ez ugyanis azt jelenti, hogy ebben az állapotban még nem voltunk, különben tároltuk volna ezt a kedvező értéket. Természetesen ebben az esetben a lépés megtehető.

A tabu módszernél is használható az előbb látott három megközelítés: a környezet különféle átvizsgálása. Az alap algoritmus mellett bemutatunk egy variánst, mely középtávú memóriát is felhasznál. A konkrét módszerek bemutatását megelőzően az absztrakt osztály bemutatásával kezdjük.

3.4. ábra - Tabu keresés, azok variánsaink és segédosztályainak áttekintő ábrája

Tabu keresés, azok variánsaink és segédosztályainak áttekintő ábrája

Tabu keresés - közös rutinok

3.5. ábra - Általános tabu keresés absztrakt osztálya

Általános tabu keresés absztrakt osztálya

package hu.unideb.inf.optimization.methods;
/**
 * Tabu módszer: a már megtett lépést egy bizonyos ideig nem ismétli.
 * @author BÓNIZS Balázs
 */
abstract public class TabuCommon extends SolvingMethod<StateR> {

Mivel a lokális minimum nem természetes határ mint korábban, így valahogy meg kell adni, hogy az algoritmus hány lépést tehet meg:

protected int LIMIT;

A tabu módszer alapvető eszköze a tabu-memória, mely a lépések jellemzőit tárolja. Ez rövid távú memóriaként viselkedik, egy idő múlva elfelejti a tárolt információt. Az, hogy mennyi információt (hány lépés jellemzőjét) képes tárolni, az a módszerünk paramétere lesz:

protected int SIZE;

A két paraméter értékét a megszokott módon olvassuk be:

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

A tabu-memória minden variánsnál előkerül, így a hozzá kapcsolódó eljárásokat külön osztályba szerveztük:

protected TabuListTools tabu;

A hegymászó módszer változatainál látható módon a legjobb meglátogatott állapotot feljegyezzük, hogy majd azt adjuk vissza eredményül:

protected StateR xMin;

Az egyes lépéseket teljes egészében nem érdemes tárolni, a többlet tárhely-igény lényegében elhanyagolható, viszont rendszerint a feladat teszi feleslegessé azt, hogy egy szűkített környezetben egymást követő változások történjenek. Például a bűvös kocka forgatásnál ha egy lapot elforgattunk 90 fokkal, akkor felesleges a következő lépésben újra elforgatni újabb 90 fokkal, mert már eleve kezdhettük egy 180 fokos forgatással. Ilyenkor elegendő a szűkített környezet azonosítóját tárolni.

Ebből következik, hogy ha a tabu-memória az átmenetileg tiltott szűkített környezeteket tárolja, akkor a tabu-memória mérete nem érheti el a szűkített környezetek számát. Erre figyelni kell, mert különben könnyen kizárhatunk minden irányt.

Ha ez rendben van, akkor generálhatunk egy véletlen kezdőállapotot, amit egyből el is tárolunk, mint az eddigi legjobb. Majd a tabu-memóriát a paraméterként megadott hosszra beállítjuk.

protected void init(StateR x) {
    if (x.numberOfRestrictedNeighbours() < SIZE) {
        System.err.println("The tabu list is to long for this problem!");
        System.exit(1);
    }
    x.fillRandom(); // aktuális állapot
    x.calculate();
    xMin = (StateR) x.copy();// eddig ez a legjobb
    tabu = new TabuListTools();
    tabu.init(SIZE, x.numberOfRestrictedNeighbours());
}}

Tabulista

Miután a tabu módszer a tabunak tekintett lépések elkerülésén alapul, a tabuk tárolására és kezelésére létrehozunk egy külön osztályt:

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
/**
 * Tabu(lista) tárolása és kezelése
 * @author ASZALÓS László
 */
public class TabuListTools {

Miután minden egyes lépést (pontosabban annak az irányát) egész számokkal azonosítottunk, így nem is kell mást tárolnunk:

private int[] tabu;

Az egyszer tiltott irány egy idő múlva lehetségessé válik, így a tabunak tekintett irányokat valójában sorként kell kezelnünk: az aktuális irány bekerül a sor végére, és a sor elején szereplő irány felszabadul a tiltás alól. Egy általános sor két index-szel írható le. Ám mi egyszerre írunk és törlünk is, így elég lesz egy index is:

private int counter;

Természetesen kezdetben a sor üres, így a vektort speciális elemekkel töltjük fel:

final static int EMPTY = -1;

Gondoljunk bele, hogyan dönthetjük el egy adott lépésről, hogy az engedélyezett-e vagy sem? Végig kell menni a tabulistán, és ha szerepel benne az adott elem, akkor nem engedélyezett, míg ha nem szerepel, akkor engedélyezett. Ez azt jelenti, hogy minden egyes lépésnél a teljes listát végigolvassuk (lineáris bonyolultság). Hosszabb listánál ez elég sok időt elvehet. Ezért vezessünk be egy másik vektort, amely azt jelzi, hogy az adott irány tiltott-e vagy sem. Az alapötlet alapján nyilvánvaló, hogy erre egy boolean vektor is elég lesz. Van viszont egy kivétel a tabu alól. Ha az adott lépés eredményeképp a célfüggvény az eddigi legjobb értéknél is jobbat ad, akkor a tiltott irányú lépést is megtehetjük. Így egy irány akár duplán/triplán is lehet tiltott. Éppen ezért a logikai értékek helyett egészeket használunk, és a 0 érték jelöli, hogy az adott irány szabad:

private int[] numbers;

Feladatról feladatra változhat, hogy egyszerre hány irányt akarunk tiltani. Így ezt paraméterként kezeljük, és ilyen hosszú tabulistát készítünk. A módszer másik paramétere a lehetséges irányok száma. Ezen paraméterek alapján inicializáljuk az adatszerkezeteket, és állítjuk alapállapotba:

/**
 * A tabulista alaphelyzetbe állítása.
 * @param size tabulista mérete
 * @param maxValue tabulistában szereplő értékek maximuma
 */
public void init(int size, int maxValue) {
    numbers = new int[maxValue];
    tabu = new int[size];   // megadott méretű lista
    Arrays.fill(tabu, EMPTY);       // még semmi sem tabu
    counter = 0;                    // mutatót előre
}

Ezek után annak vizsgálata, hogy adott irány tabu-e vagy sem, a numbers segédtömb megfelelő értékén múlik. Ha pozitív ez a szám, akkor az irány jelenleg tiltott, egyébként nem:

/**
 * Az adott lépés tabunak számít-e?
 * @param index megváltoztatandó elem
 * @return tabu?
 */
public boolean isTabu(int index) {
    return (numbers[index] > 0);
}

Az aktuális lépés (irány) tárolásához kapcsolódó műveletek a save metódusban találhatóak. A következőket kell tennünk. Ha irány szabadul fel, akkor a hozzá tartozó számlálót csökkenteni kell, majd pedig az új irány számlálóját növelni. Ezután már tárolhatjuk az irány azonosítóját a sorban, és léptethetjük a számlálót. Persze vigyázni kell, ha ez a számláló kilép a vektorból, az elején kell folytatni:

/**
  * Tároljuk a lépés indexét a tabu között.
  * @param index megváltoztatott elem
  */
 public void save(int index) {
     if (tabu[counter] != EMPTY) {numbers[tabu[counter]]--;}
     numbers[index]++;
     tabu[counter] = index;  // tároljuk
     counter++;              // következő pozíció
     if (counter == tabu.length) {
         counter = 0;
     }
 }}

Lépés kiválasztása

Az aktuális állapot környezetét kétféle állapotok alkotják: a tiltott és az engedélyezett állapotok.

  • Ha a korábban említett speciális eset előfordul, azaz valamelyik tiltott szomszéd annyira jó, hogy eddig nem találkoztunk még ilyen jóval, akkor mindenképpen ezt kell választanunk. (A tiltott állapotoknak az a haszna, hogy így a már megismert állapotokat elkerülve a keresési tér egy eddig meg nem ismert részét fedezzük fel. A célfüggvény alapján a tiltott állapotot még nem látogattuk meg korábban, így a tiltást most felülbíráljuk.)

  • A nem tiltott szomszédok közül a legjobbat kell kiválasztani. Arra viszont vigyázni kell, hogy ne az aktuális állapotot válasszuk, még akkor sem, ha az lokális minimumhely.

A lépés kiválasztására vonatkozó metódusokat külön absztrakt osztályban fogalmaztuk meg, melynek két leszármazottja a tabu keresés két változatára jellemzőket foglalja össze.

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

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

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Tabu módszer lokális keresései.
 * @author ASZALÓS László
 */
public abstract class TabuMoveTools {

Legjobb tiltott és tűrt lépések tárolása

Az eddig talált legjobb megengedett szomszédot annak irányával, és e szűkített környezeten belüli lépéssel ábrázoljuk:

protected int permittedDirection;
protected int permittedStep;

Az aktuális és eddigi legjobb szomszéd célfüggvényértékének különbségét külön tároljuk, hogy ne kelljen újra és újra kiszámolni:

protected int permittedDiff;

Az eddig talált legjobb tiltott lépést, és a célfüggvényértékek különbségét is hasonlóképpen tároljuk:

protected int tabuDirection;
protected int tabuStep;
protected int tabuDiff;

Azt, hogy még nem választottunk ki egyetlen egy irányt sem, egy konstanssal jelöljük

protected final static int EMPTY = -1;

Az alaphelyzetbe állítást több rutinnál is fel kell használnunk. Ezért külön metódust alkottunk ebből a pár utasításból.

private void initDirections(){
    permittedDirection    = EMPTY;
    permittedStep         = EMPTY;
    tabuDirection         = EMPTY;
    tabuStep              = EMPTY;
    tabuDiff             = 0;
}

Lépés vizsgálata és megtétele

Az iránnyal és azon belüli azonosítóval megadott szomszéd jobb mint az eddigi tiltott szomszédok bármelyike? Ha igen, akkor elmentjük a szomszédot:

/** Ez az eddigi legjobb tiltott elem?
 * @param diff szomszéd és aktuális elem célfüggvényértékének eltérése
 * @param direction szomszéd iránya
 * @param step szomszéd azonosítója a szűkített környezeten belül
 */
protected void checkBetterTabu(int diff, int direction, int step) {
    if (diff < tabuDiff) {
        tabuDirection     = direction;
        tabuStep          = step;
        tabuDiff         = diff;
    }
}

Az iránnyal és azon belüli azonosítóval megadott szomszéd jobb mint az eddigi engedélyezett szomszédok bármelyike? Ha igen, akkor elmentjük a szomszédot:

/** A megadott engedélyezett szomszéd eddig a legjobb-e?
 * @param diff a szomszéd és az aktuális elem célfüggvényértékének eltérése
 * @param direction szomszéd iránya
 * @param step szomszéd azonosítója a szűkített környezeten belül
 */
protected void checkBetterPermitted(int diff,int direction, int step) {
    if (EMPTY == permittedStep || diff < permittedDiff) {
        permittedDirection        = direction;
        permittedStep             = step;
        permittedDiff            = diff;
    }
}

Az előbbi két rutint együtt szoktuk használni, ezért az alkalmazásukat külön metódusba foglaltuk. Fontos, hogy csak valódi szomszédot vizsgálunk meg! (Ezt az első feltétel ellenőrzi.):

/** A kiválasztott szomszéd vizsgálata. 
 * @param x aktuális állapot
 * @param direction szomszéd iránya
 * @param step szomszéd azonosítója 
 * @param tl tabulista
 */
private void checkStep(StateR x, int direction, int step, TabuListTools tl){
    if (step != x.getRestrictedValue(direction)) {
        if (tl.isTabu(direction)) {
            checkBetterTabu(x.diffRestrictedNeighbour(direction, step),direction,step);
        } else {
            checkBetterPermitted( x.diffRestrictedNeighbour(direction,step),direction,step); 
        }
    }
} 

Miután átvizsgáltuk az x környezetét (vagy csak egy részét) dönteni kell, hogy a kiválasztott tiltott, vagy engedélyezett lépést tesszük-e meg. A tiltott lépést csak akkor választhatjuk, ha a paraméterként átadott minimális értéknél jobbat érünk el vele. A lépés megtétele után a lépés irányát tabuként kezeljük:

/** Döntés a megteendő lépésről.
 * @param x aktuális állapot
 * @param minValue eddig talált legjobb célfüggvényérték
 * @return sikerült megjavítani az eddigi rekordot?
 */  
private boolean makeStep(StateR x, int minValue,TabuListTools tl){
    if (tabuDirection != EMPTY && x.getValue() + tabuDiff < minValue) {
        chooseStepRestricted(x, tabuDirection, tabuStep);
        tl.save(tabuDirection);
        return true;
    }
    if (permittedDirection != EMPTY) {
        chooseStepRestricted(x, permittedDirection, permittedStep);
        tl.save(permittedDirection);
    }
    return false;
}

Környezetek vizsgálata

Az alábbi módszerek már ismertek a hegymászó algoritmusból. Itt is a már jól ismert három variánst valósítjuk meg.

Az első módszernél átvizsgáljuk az x teljes N(x) környezetét. Az alaphelyzetbe állítás után végigmegyünk a környezet minden elemén, meghatározzuk a hozzá tartozó irányt és azon belüli azonosítót. Megvizsgáljuk, hogy ez a lépés jobb-e mint a tárolt lépések. Végül az összes közül a kiválasztottat meglépjük.

/** Megvizsgálja az aktuális állapot összes szomszédját,
 * és a minimális értékűbe lép.
 * @param x aktuális állapot
 * @param minValue eddig talált legjobb érték
 * @param tl tabulista
 * @return sikerült megjavítani a rekordot?
 */
boolean isNBetter(StateR x, int minValue, TabuListTools tl) {
    initDirections();
    for (int index = 0; index < x.numberOfNeighbours(); index++) {
        int direction = x.getRestrictedNeighbour(index);
        int step      = x.getRestrictedNeighbourValue(index); 
        checkStep(x,direction,step,tl);
    }
    return makeStep(x,minValue,tl);
}

A második variánsnál a környezetből véletlen módon kiválasztunk pár elemet. Mindegyikhez meghatározzuk az irányt és azonosítót, és megvizsgáljuk a lépés jóságát. Végül a legjobb lépést megtesszük.

/**
 * Az N(d)-ben maxSteps véletlen szomszéd között keres minimálist.
 * @param x aktuális állapot
 * @param minValue eddig talált legjobb érték
 * @param maxSteps próbálkozások száma
 * @param tl tabulista
 * @return sikerült megjavítani az eddigi rekordot?
 */
boolean isFBetter(StateR x, int minValue, int maxSteps, TabuListTools tl) {
    Random random = new Random();
    initDirections();
    for (int s = 0; s < maxSteps; s++) {
        int direction = random.nextInt(x.numberOfRestrictedNeighbours());
        int step      = random.nextInt(x.sizeOfRestrictedNeighbours(direction));
        checkStep(x,direction,step,tl);
    }
    return makeStep(x, minValue,tl);
}

A harmadik módszernél a szűkített környezetek közül fogunk párat teljesen átvizsgálni. Hogy melyiket, azt a véletlen dönti el.

/**
 * Egy véletlen módon választott szűkített környezetben megkeresi a
 * legjobb szomszédokat, és annak irányába mozdul el.
 * @param x aktuális állapot
 * @param minValue eddig talált legjobb érték
 * @param index szűkített környezet azonosítója
 * @param tl tabulista
 * @return sikerült megjavítani az eddigi rekordot?
 */
boolean isRBetter(StateR x, int directions, int minValue, TabuListTools tl) {
    Random random=new Random();
    initDirections(); 
    for (int i=0;i<directions;i++){ // hányszor ismétlünk?
        int direction =  random.nextInt(x.numberOfRestrictedNeighbours());
        for (int step = 0; step < x.sizeOfRestrictedNeighbours(direction); step++) {
            checkStep(x,direction,step,tl);
        }
    }
    return makeStep(x,minValue,tl);
}

Adósak maradtunk azzal, hogyan is kell megtenni a lépést. Ezt majd a leszármazott osztályokban pontosítjuk.

/**
 * Átlép a megjelölt állapotba.
 * @param x aktuális állapot
 * @param index következő állapotot tartalmazó szűkített környezet
 * @param step következő állapot azonosítója a szűkített környezetben
 */
protected abstract void chooseStepRestricted(StateR x, int index, int step);
}

Lépések rövid távú memóriával

A két variáns közül az első egyszerűen végrehajtja a lépést:

package hu.unideb.inf.optimization.methods;
/**
 * Tabu keresésnél a rövid távú memóriára alapozva megteszi az előírt lépéseket.
 * @author ASZALÓS László
 */
public class TabuMoveShortTools extends TabuMoveTools {

A paramétereket egy az egyben felhasználva meghívjuk a megfelelő metódust.

/**
 * Átlép az értékpárossal megadott állapotba.
 * @param d aktuális állapot
 * @param direction következő állapotot tartalmazó szűkített környezet
 * @param step következő állapot azonosítója a szűkített környezetben
 */
@Override
protected void chooseStepRestricted(StateR x, int direction, int step){
        x.setRestrictedValue(direction, step);
}}

Absztrak módszer rövid távú memóriával

A tabu módszer irodalmában szerepel a rövid-, közép és hosszútávú memória is. Az első módszernél csak a rövidtávú memóriára hagyatkozunk:

package hu.unideb.inf.optimization.methods;
/**
 * A már megtett lépést egy bizonyos ideig nem ismétli.
 * @author BÓNIZS Balázs
 */
abstract public class TabuShort extends TabuCommon {

A korábbiakhoz hasonlóan a környezet átvizsgálásánál a már megismert három módszer mindegyikét használni fogjuk.

3.7. ábra - Rövidtávú memóriát felhasználó keresések osztályai

Rövidtávú memóriát felhasználó keresések osztályai

Így itt is kiszervezzük egy új osztályba a lépéseknél alkalmazni kívánt közös metódusokat:

TabuMoveShortTools tm = new TabuMoveShortTools();

Ezek után a tabu keresés külső váza igen egyszerűen írható le. Az előírt számú lépést (LIMIT) kell végrehajtani, minden egyes lépés után kiszámoljuk, hogy a mennyire volt az eredményes. Ha sikerült az eddigi legjobbnál jobb állapotot találni, akkor a legjobb állapotot frissítjük. Végül ha az összes lépést megtettük, visszaadjuk az eddig talált legjobb állapotot.

@Override
public StateR solve(StateR x) {
    init(x);
    for (int step = 0; step < LIMIT; step++) {
        if (tabuStep(x, xMin.getValue())) {
            x.calculate();
            if (x.getValue() < xMin.getValue()){
                xMin = (StateR) x.copy();
            }
        }
    }
    return xMin;
}

Adósak maradtunk azzal, hogy mit is jelent esetünkben egy lépés. Ezt majd az alfejezetben áruljuk el.

/**
 * Az adott módszer feltételei szerint megteszünk egy lépést az adott
 * állapotból egy szomszédos állapotba.
 * @param x aktuális állapot
 * @param value eddig talált legjobb függvényérték
 * @return Sikerült megdönteni a rekordot?
 */
abstract protected boolean tabuStep(StateR x, int value);
}

Tabu keresés - 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 TabuShortAll extends TabuShort {

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

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

Tabu módszer - 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 TabuShortFirstBetter extends TabuShort {

Ebben az esetben is megfelelő metódust kell alkalmazni:

@Override
protected boolean tabuStep(StateR d, int value) {
    return tm.isFBetter(d, value, MAX_STEPS, tabu);
}

Ez a lépéssorozat használ egy paramétert, az átvizsgálandó szomszédok számát:

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;
    }
}}

Tabu keresés - szűkített környezetek

A második 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 TabuShortOne extends TabuShort {

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

@Override
protected boolean tabuStep(StateR x, int minValue) {
    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;
    }
}}