Iterált hegymászó algoritmus

Miután egy hegymászó keresés csak egy lokális minimumhelyet képes megadni, egyáltalán nem biztos, hogy a kapott állapot globális minimumhely, vagy akár közel optimális állapot. Ezért a hegymászó algoritmusnak több javítása is létezik. Az iterált hegymászó algoritmusnál a lokális minimumból úgy lépünk el, hogy az állapotot véletlenszerűen megváltoztatjuk, és innen indítjuk újra a hegymászó keresést.

Maga az ötlet jónak tűnik, de vigyázni kell a változtatás mértékére. Ha az túl kicsi, akkor a korábbi lokális minimumhelyre jutunk vissza. Ha pedig nagy, akkor az előző megoldástól teljesen független megoldást kapunk. Tehát elveszítjük a korábbi megoldás során nyert lépéseinket, részeredményeinket.

3.2. ábra - Iterált hegymászó keresés és variánsainak osztálydiagramja

Iterált hegymászó keresés és variánsainak osztálydiagramja

Absztrakt módszer iterált keresésre

Mivel ennek a módszernek a lényege abban áll, hogy a lokális minimum elérése után egy közeli véletlen pontban folytatjuk a keresést, így minden variánsnál használni kell a korábban bevezetett mutációt. Ennek eredményeképpen elkészíthető ez a segédosztály:

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * A hegymászó módszer továbbfejlesztése, 
 * többször próbálkozik csúcstámadással.
 * @author ASZALÓS László
 */
abstract public class IteratedHC extends SolvingMethod<StateR> {

Az egyes lépéssorozatok meghatározásához a korábban ismertetett segédosztályt használjuk:

HillClimbingTools hc = new HillClimbingTools();

Szükséges megadni, hogy hányszor van lehetőség a keresés újraindítására egy közeli állapotból:

protected int LIMIT;

Illetve mennyire változtathatjuk meg a kapott lokális minimumot:

protected float MUTATE;

A keresések során kapott legjobb állapotot érdemes nyilvántartani:

StateR xMin;

A korábbiak alapján két paramétert kell figyelembe vennünk, ahol a LIMIT egy egész szám, míg a MUTATE 0 és 1 közti valós szám:

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

Most lehetőségünk adódott egy általános megoldó algoritmus megírására. Ehhez kisorsolunk egy véletlen kezdőállapotot (hc.init), és eltároljuk ezt, mint az eddigi legjobb állapotot. Majd az előírt lépésszámnak megfelelően generálunk egy lépéssorozatot, és az annak végén megkapott lokális minimumhoz tartozó állapotot összehasonlítjuk az eltárolttal. Ha jobbat találunk, akkor ezt a jobbat tároljuk tovább. Végül véletlen irányban ellépünk a minimumból.

@Override
public StateR solve(StateR x) {
    hc.init(x);
    Random r = new Random();
    x.calculate(); 
    xMin = (StateR) x.copy();
    for (int limit = 0; limit < LIMIT; limit++) {
        hillClimbingSequence(x);
        x.calculate();
        if (x.getValue() < xMin.getValue()) {
            xMin = (StateR) x.copy();
        }
        x.mutate(MUTATE); 
    }
    return xMin;
}

Használtuk a lépéssorozat fogalmát, de most nem fogjuk konkrétan megadni, arra következő alfejezetekben kerül sor:

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

Iterált módszer - teljes környezet

A három variáns közül az egyik minden szomszédot figyelembe vesz:

package hu.unideb.inf.optimization.methods;
/**
 * A lépéssorozatnál minden szomszédot figyelembe veszünk.
 * @author ASZALÓS László
 */
public class IHCAll extends IteratedHC {

Nincs más dolgunk, csak a függőben hagyott lépéssorozatot konkretizálni, amely egy másik segédosztályban található.

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

Iterált módszer - véletlen szomszédok

A korábban alkalmazott módon lehetőség van rá, hogy ne minden szomszédot, hanem a szomszédok közül adott számú, véletlen módon kiválasztottat tekintsünk, és ez alapján döntsünk arról, hogy elértük-e a lokális minimumot, vagy sem:

package hu.unideb.inf.optimization.methods;
/**
 * Iterált hegymászó módszer, FB variáns
 * @author ASZALÓS László
 */
public class IHCFirstBetter extends IteratedHC {

Természetesen a korábban definiált, megfelelő lépéssorozatot kell használni.

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

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

Iterált módszer - szűkített környezetek

A harmadik variáns csak néhány szűkített környzetet vizsgál át:

package hu.unideb.inf.optimization.methods;
/**
 * Csak néhány szűkített környezet vizsgálata.
 * @author ASZALÓS László
 */
public class IHCOne extends IteratedHC {

Ismét felhasználhatjuk a segédosztály megfelelő módszerét.

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

Ez a módszer is használ paramétert:

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