Szétszórt keresés

A szétszórt (scatter) keresés esetén egyszerre párhuzamosan több keresést is futtatunk. Amint ezek mindegyike egy-egy lokális minimumban véget ér, a minimumhelyeket kombinálva új állapotokat kapunk. Innen indítjuk újra a kereséseket. Természetesen itt is hegymászó keresésre alapozunk.

3.3. ábra - Szétszórt keresés és variánsainak osztálydiagramja

Szétszórt keresés és variánsainak osztálydiagramja

Absztrak módszer szétszórt keresésre

Az előző fejezethez hasonlóan itt is egységes módon kezelhetjük a három variánst, így elkészíthettük ezt a segédosztályt:

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Lokális minimumok adatait kombináljuk.
 * @author Renato MORSIANI, KOÓS Dániel
 */
abstract public class ScatterSearch extends SolvingMethod<StateRC> {

Továbbra is lépéssorozatokkal dolgozunk, melyhez felhasználjuk a bemutatott segédosztályt:

HillClimbingTools hc = new HillClimbingTools();

Meg kell adnunk paraméterként, hogy hányszor keverjük össze az egyes lokális minimumokat:

protected int LIMIT;

Továbbá hány a lokális minimumot keresünk párhuzamosan?

protected int SIZE;

Paraméter továbbá a lokális minimumok összekeverésének foka, azaz mennyire alakítjuk át egy másik minimum adatainak felhasználásával:

protected float MUTATE;

Talált legjobb eredményt külön tároljuk:

StateRC xMin;

Ezeket a paramétereket a már jól ismert módon be kell olvasni:

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

Korábban elég volt egy állapotot eltárolni, most SIZE darab állapotunk van. A legegyszerűbb és legkényelmesebb ezeket egy tömbben tárolni:

StateRC[] xs;

A rendszer alaphelyzetbe állításához az előbbi tömböt megfelelő méretben létre kell hozni, és véletlen kezdeti értékkel ellátni. Annak érdekében, hogy az xMin-nek is legyen valamilyen értéke, az első kezdeti állapot másolatát tároljuk benne:

protected void hcInit(StateRC x) {
    xs = new StateRC[SIZE];
    for (int i=0; i<xs.length; i++) {
        xs[i] = (StateRC) x.copy();
        xs[i].fillRandom();
    }
    xMin = (StateRC) xs[0].copy();
    xMin.calculate();
}

Ezek után a módszer maga elég egyszerű. Először felhasználjuk az előbb bemutatott metódust az inicializálásra, majd a LIMIT paraméterben adott számban végrehajtjuk a következőket:

@Override
public final StateRC solve(StateRC x) {
    hcInit(x);
    Random r = new Random();
    for (int limit = 0; limit < LIMIT; limit++) {

Minden egyes tárolt állapotból egy lépéssorozattal eljutunk egy lokális minimumba, ott kiszámoljuk a célfüggvény értékét, és az állapot ábrázolását normalizáljuk. Ennek eredményeképp a hasonló állapotok leírása is hasonló lesz. Ezután már csak azt ellenőrizzük, hogy nem kaptunk-e jobb állapotot az eddig talált legjobbnál? Ha igen, akkor ezt az új állapotot tároljuk tovább.

for (int i=0;i<xs.length;i++) {
    hillClimbingSequence(xs[i]);
    xs[i].calculate();
    xs[i].normalize();

    if (xs[i].getValue() < xMin.getValue()) {
        xMin = (StateRC) xs[i].copy();
        xMin.normalize();
    }
}

Ezután következik az állapotok összekeverése. Minden állapotot az utána következővel kombinálunk, illetve az utolsót az elsővel:

//TODO kevesebb kavarás, csak páronkénti csere
for (int j = 1; j < SIZE; j++) {
    xs[j].crossoverUniform(xs[j-1], MUTATE);
}
xs[SIZE-1].crossoverUniform(xs[0], MUTATE);
}
return xMin;
}

Az előző fejezethez hasonlóan most sem konkretizáltuk a lépéssorozatot. Ezek most is az elkövetkező alfejezetekben következnek.

/**
 * Lépéssorozat
 * @param x kiinduló állapot
 */
protected abstract void hillClimbingSequence(StateRC x);
}  

Szétszórt keresés - teljes környezet

Az első variáns itt is minden szomszédot figyel egy-egy lépésnél:

package hu.unideb.inf.optimization.methods;
/**
 * Minden szomszédos állapot figyelése.
 * @author ASZALÓS László
 */
public class SSAll extends ScatterSearch {

A korábban definiált segédosztály rutinjait használjuk.

@Override
protected void hillClimbingSequence(StateRC x) {
    hc.sequenceAll(x);
}}

Szétszór keresés - véletlen szomszédok

Csak pár véletlen módon kiválasztott szomszédot veszünk figyelembe:

package hu.unideb.inf.optimization.methods;
/**
 * Véletlen szomszédok.
 * @author ASZALÓS László
 */
public class SSFirstBetter extends ScatterSearch {

A korábban ismertetett segédosztály metódusát használjuk:

@Override
protected void hillClimbingSequence(StateRC x) {
    hc.firstBetter(x, MAX_STEPS);
}

A módszer használ egy paramétert:

private int MAX_STEPS;

A paraméter beolvasása a szokott módon történik:

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

Szétszórt keresés - szűkített környezetek

A harmadik variáns szűkített környezeteket vizsgál meg:

package hu.unideb.inf.optimization.methods;

/**
 * Szűkített környezetek vizsgálata lépésenként.
 * @author ASZALÓS László
 */
public class SSOne extends ScatterSearch {

Korábban ismertetett segédosztály metódusát használjuk fel:

@Override
protected void hillClimbingSequence(StateRC x) {
    hc.sequenceOne(x,DIRECTIONS);
}

A módszernek van egy paramétere:

private int DIRECTIONS;

A paraméter beolvasása a szokott módon történik:

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