3. fejezet - Lokális keresések

Tartalom

Hegymászó algoritmus
HillClimbingTools segédosztály
Hagyományos algoritmus
Hagyományos algoritmus randomizált variánsa
Hagyományos algoritmus szűkített variánsa
Iterált hegymászó algoritmus
Absztrakt módszer iterált keresésre
Iterált módszer - teljes környezet
Iterált módszer - véletlen szomszédok
Iterált módszer - szűkített környezetek
Szétszórt keresés
Absztrak módszer szétszórt keresésre
Szétszórt keresés - teljes környezet
Szétszór keresés - véletlen szomszédok
Szétszórt keresés - szűkített környezetek
Tabu keresés
Tabu keresés - közös rutinok
Tabulista
Lépés kiválasztása
Lépések rövid távú memóriával
Absztrak módszer rövid távú memóriával
Tabu keresés - teljes környezet
Tabu módszer - véletlen szomszédok
Tabu keresés - szűkített környezetek
Tabu keresés középtávú memóriával
Középtávú memória használata
Absztrakt módszer középtávú memóriával
Középtávú memória - teljes környezet
Középtávú memória - véletlen szomszédok
Középtávú memória - szűkített környezetek
Feladatok
Sztochasztikus hegymászó algoritmus
Akkumulált javítások
Sztochasztikus keresés implementációja
Feladatok
Szimulált hűtés
Szimulált hűtés implementációja
Párhuzamos hűtés
Konfliktusok módszerei
Minimális konfliktusok
Max-min konfliktusok
Jó elem kiválasztása
Segédosztály konfliktusok kezelésére
Javított módszer
Jó elem megválasztása
Javított segédosztály
Feladatok

A lokális keresések esetén kiindulunk egy x kezdeti állapotból, és minden egyes lépésben N(x) környezetben levő állapotok egyikébe lépünk át. A lépés kiválasztásához a környezetét alkotó állapotok célfüggvényértékeit vesszük figyelembe. Wikipédia ismertető

Hegymászó algoritmus

A módszer közismert: minden egyes lépésben megvizsgáljuk, hogy az aktuális x pont N(x) környezetében van-e olyan y pont, melyre f(y)<f(x)? Ha nincs ilyen, akkor x egy lokális minimumhely, és a módszer megáll. Ha van ilyen, mondjuk az y; akkor y lesz az aktuális pont, és innen folytatjuk az algoritmust.

Mivel méretesebb feladatoknál az N(x) mérete igen nagy, és így sok időt elvesz a teljes környezet felderítése, ennek a módszernek több variánsa is létezik:

  • Minden egyes lépésben véletlenszerűen választunk egy Ri(x) szűkített környezetet, és az N(x) helyett csak Ri(x)-ben keresünk az aktuálisnál jobb állapotot.

  • Az N(x) környezetből véletlenszerűen választunk maximum n állapotot. Ha van köztük az aktuálisnál jobb, akkor az lesz az aktuális állapot, egyébként megáll az algoritmus.

3.1. ábra - Hegymászó keresés és variánsainak osztálydiagramja

Hegymászó keresés és variánsainak osztálydiagramja

HillClimbingTools segédosztály

Az egymáshoz igen hasonló variánsok sok ismétlődő kódot eredményeznének. Ezt elkerülendő ebbe az osztályba kigyűjtjük az ismétlődő részeket, és innen használjuk fel azokat.

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Hegymászó algoritmusok lépésválasztói és lépéssorozatai.
 * @author ASZALÓS László
 */
public class HillClimbingTools {

A könnyebb olvashatóságért bevezetünk egy konstanst, mely azt jelöli, hogy még egyik irányt/szomszédot sem választottuk ki.

private static final int NONE = -1;

A hagyományos hegymászó algoritmus esetén megvizsgáljuk az aktuális állapot összes szomszédját. (A mi jelölésünkben a teljes N(x)-t át kell vizsgálni, és sorra kiszámolni a f(y)-f(x) értékeket.)

A rutin egy egyszerű minimumszámítás. Ha az aktuális állapothoz tartozik a minimális célfüggvény érték, akkor a legjobb és aktuális állapothoz tartozó függvényértékeket különbsége 0 (=f(x)-f(x)), ezért helyes, hogy a min kezdőértéke 0. Ha van nála jobb, azaz kisebb függvényértékű állapot, akkor a különbség negatív lesz, tehát a kezdeti 0-t tudjuk majd csökkenteni. Az eddig talált legjobb szomszéd indexét feljegyezzük, ést ezt adjuk vissza. (Vagy NONE-t, ha nincs jobb az aktuálisnál.)

/**
 * Adott állapotnak megvizsgálja az összes szomszédját.
 * @param x aktuális állapot
 * @return legjobb szomszéd azonosítója
 */
int bestStepAll(State x) {
    int bestIndex = NONE;
    int min = 0;
    for (int index = 0; index < x.numberOfNeighbours(); index++) {
        if (x.diffNeighbour(index) < min) {
            bestIndex = index;
            min = x.diffNeighbour(index);
        }
    }
    return bestIndex;
}

A hagyományos hegymászó algoritmus egyik variánsa a véletlent hívja segítségül. Véletlenül választ egy y elemet az N(x) környezetből, melynek azonosítója az index. Megvizsgálja, hogy y jobb-e, mint x, ha igen, akkor az y lesz az aktuális elem, és a számlálót (i) is alaphelyzetbe állítjuk. Ha y nem jobb, akkor a számlálót növeljük. Ha a számláló elérhete a paraméterként megadott határt, akkor kilépünk a rutinból.

/** Véletlen hegymászás.
 * @param x aktuális állapot 
 * @param limit próbálkozások száma
 */
void firstBetter(State x, int limit) {
    Random r = new Random();
    int index, diff, i = 0;
    do { 
        index = r.nextInt(x.numberOfNeighbours());
        diff = x.diffNeighbour(index);
        if (diff < 0) {
            x.chooseNeighbour(index);
            i = 0;
        } 
        else {
            i++;
        }
    } while (i < limit);
}

Az előbbi keresést a teljes környezet helyett valamely szűkített környezeten is végrehajthatjuk. A szűkített környezethez már a StateR osztály tartozik, ahol az f(x) teljes kiszámítása helyett csak a szűkített környezetből származó részt kell figyelembe venni. Ezt most jelölje f', így f'(y)-f'(x) értékek minimumát kell kiszámítani. Az f'(x)-t a conflicts, míg f'(y)-t a possibleConflicts segítségével számíthajuk ki. A best változó hivatkozik a szűkített környezetben eddig talált legjobb szomszédra. A változó kiinduló értéke x, és ha jobbat találunk nála, akkor lecseréljük.

/**
 * Végigmegyünk az szűkített környezeten.
 * @param direction szűkített környezet azonosítója
 * @param x aktuális állapot
 * @return legjobb lépés
 */
int bestStepOne(int direction, StateR x) {
    int best = x.getRestrictedValue(direction); 
    int bestConflict = x.conflicts(direction);  
    int temp;
    for (int neighbour = 0; neighbour < x.sizeOfRestrictedNeighbours(direction);
            neighbour++) {
        temp = x.possibleConflicts(direction, neighbour);
        if (temp < bestConflict) {
            bestConflict = temp;
            best = neighbour;
        }
    }
    return best; 
}

A teljes, valamint a szűkített környezet átvizsgálásakor csak a legjobb szomszédot találtuk meg. A véletlen keresés már szomszédok egy sorozatát határozta meg, és tért vissza közülük a legjobbal. A következő rutin lényegében megvalósítja a hagyományos hegymászó keresést, egyre jobb és jobb szomszédokat határoz meg, míg egy lokális minimumban elakad. (Ha nem talál jobb szomszédot, akkor a rutin a véget ér.)

/**
 * Lokális minimum meghatározása teljes környezetek segítségével.
 * @param x aktuális állapot
 */
void sequenceAll(State x) {
    int bestIndex;
    do {
        bestIndex = bestStepAll(x);
        if (bestIndex > NONE) {
            x.chooseNeighbour(bestIndex);
        }
    } while (NONE < bestIndex);
}

Ugyanezt megvalósíthatjuk szűkített környezetek esetén is. Viszont figyelni kell arra, hogy az egyik irányban minimális állapot más irányban nem feltétlenül minimális. (Gondoljon a nyeregfelületre!) Így érdemes több irányt is kipróbálni, mielőtt úgy döntenénk, hogy lokális minimumba jutottunk.

Az előbbi metódushoz hasonlóan itt is egy ciklus adja a metódus törzsét, melyből csak akkor léphetünk ki, ha nem sikerült jobb szomszédot találni, és már megvizsgáltuk az előírt számú irányt.

A ciklus belsejében választunk egy véletlen szűkített környezetet (index), és a korábban ismertetett rutinnal meghatározzuk a legjobb elemét (value). Ha f'(x)>f'(index,value), akkor át kell lépni ebbe a szomszédba, és újraindul a számolás (counter). Ha pedig nincs jobb szomszéd a szűkített környezetben, akkor a számláló növekszik:

/**
  * Szűkített környezetek alapján lokális minimumot határoz meg.
  * @param x aktuális állapot
  * @param directions hány irányt vizsgálunk meg a megállás előtt?  
  */
 void sequenceOne(StateR x, int directions) {
     Random random = new Random();
     int diff;
     int counter=0;
     do {
         int index = random.nextInt(x.numberOfRestrictedNeighbours());
         int value = bestStepOne(index, x);
         diff = x.diffRestrictedNeighbour(index, value);
         if (diff < 0) {
             x.setRestrictedValue(index, value);
             counter=0;
         } else {
             counter++;
         }
     } while (diff < 0 || counter<directions);
 }

A hegymászó keresés és variánsai egy véletlen kezdőállapotból indulnak, így az átadott adatszerkezetet randomizálni kell.

/** Kezdeti beállítások 
 * @param x átadott állapot
 */
void init(State x) {
    x.fillRandom();
}}

Hagyományos algoritmus

Az előző osztály minden szükséges eszközt megadott, már csak pár technikai apróság van hátra:

package hu.unideb.inf.optimization.methods;
/**
 * Hagyományos hegymászó algoritmus.
 * @author ASZALÓS László
 */
public class HCAll extends  SolvingMethod<State> {

A módszerünk az absztrakt SolvingMethod kiterjesztése, így az ott felsorolt metódusokat implementálnunk kell. Mivel a módszer nem használ paramétert, így az üres függvény is megteszi:

@Override
    public void constants(String name, int numerator, int denominator) {}

Az előbbi metódusban definiált módszerekhez hozzá kell férnünk, így bevezetünk egy változót.

HillClimbingTools hc= new HillClimbingTools();

Ezek után már nem kell mást tenni, mint véletlen kezdőállapotot generálni, és elindítani a keresést. A keresés végén kapott aktuális állapotot pedig visszaadni.

/**
 * Az aktuális állapot összes szomszédját figyelembe veszi.
 * Ha talál jobbat, akkor a legjobb irányába megy tovább.
 * Ha ilyen nincs, akkor leáll.
 */
@Override
public State solve(State x) {
    hc.init(x);
    hc.sequenceAll(x);
    return x;
}}

Hagyományos algoritmus randomizált variánsa

A hagyományos hegymászó algoritmus hátránya, hogy méretesebb N(x) esetén igen sokáig tart, míg a teljes környezetet átvizsgálja a program. A randomizált variánsban a környezet néhány eleme alapján döntünk a továbblépésről, illetve a megállásról.

A randomizált variáns is a közös absztrakt módszer utóda.

package hu.unideb.inf.optimization.methods;
/**
 * Véletlen irányba véletlen lépések sorozata.
 * @author ASZALÓS László
 */
public class HCFirstBetter extends SolvingMethod<State> {

Ennek megfelelően itt is meg kell adni a konstansok feldolgozásának metódusát. Viszont ennek a módszernek már van egy paramétere, mely megszabja, hogy hány próbálkozást tehetünk egy lépés során.

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

Természetesen ehhez be kell vezetni egy lokális változót, mely az így beolvasott értéket tárolja.

private int MAX_STEPS;

Másrészt szükség van a korábban definiált módszerekre is.

HillClimbingTools hc= new HillClimbingTools();

A megoldás meghatározása hasonlóképp megy mint az előbb, csak más metódusra támaszkodunk a keresés során.

@Override
public State solve(State x) {
    hc.init(x);
    hc.firstBetter(x, MAX_STEPS);
    return x;
}}

Hagyományos algoritmus szűkített variánsa

Ha az N(x) környezet elemszáma nagy, akkor meg lehet próbálkozni néhány szűkített környezet alapján megkeresni az optimális megoldást.

package hu.unideb.inf.optimization.methods;
/**
 * Egy véletlen választott irányba próbálja meg a hegymászást.
 * @author ASZALÓS László
 */
public class HCOne extends SolvingMethod<StateR> {

Mivel az esetlegesen több száz szűkített környezetből csak egynek az átvizsgálása a kísérleteink szerint nem vezet eredményre, a módszernek van egy paramétere, mely megmondja, hogy hány szűkített környezet átvizsgálása után kell döntenünk a megállásról illetve a folytatásról:

private int DIRECTIONS;

Ezt a paramétert az ismert módon olvashatjuk be.

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

A keresés során az előbbiekben ismertetett segédosztályt használjuk,

HillClimbingTools hc= new HillClimbingTools();

valamint az ott definiált metódust a korábban ismertetett módon.

/**
 * Szűkített környezeteken keresi az optimális megoldást.
 */
@Override
public StateR solve(StateR x) {
    hc.init(x);
    hc.sequenceOne(x, DIRECTIONS);
    return x;
}}