Szimulált hűtés

A szimulált hűtés egy széles körben alkalmazott, és nagy múltra visszatekintő módszer. Az eddig ismertetett módszerek közül a csak a tabu keresésben volt lehetőség arra, hogy ne a kisebb irányába haladjon a keresés. Erre a szimulált hűtés is képes. Adott egy hőmérsékletnek nevezett érték, amely meghatározza, hogy milyen eséllyel haladhatunk a rossz irányba. Ha f és f' jelöli az aktuális és következőnek kijelölt állapotokhoz tartozó függvényértéket, ahol f < f', míg T a hőmérsékletet jelöli, akkor a következőnek kijelölt állapotot e(f-f')/T valószínűséggel választjuk. Ezek szerint ha a következőnek kijelölt állapothoz kisebb függvényérték tartozik, mint az aktuális állapothoz, akkor 1 valószínűséggel fogjuk választani. Az érdekes eset az, ha f' nagyobb (rosszabb) mint f. Ha T nagy, akkor nagy számmal osztunk, így a kitevő kicsi negatív szám lesz, azaz a valószínűség közel lesz 1-hez. Ha viszont T kicsi, akkor a kitevő nagy negatív szám lesz, azaz a valószínűség 0-hoz közeli. Mivel a módszer alapja a hőmérséklet folyamatos csökkentése, kezdetben a magas hőmérsékletnél viszonylag nagy valószínűséggel haladhatunk rossz irányba is; viszont ahogy a hőmérséklet egyre csökken, ez egyre ritkábban történik meg, míg végül a hegymászó módszert fogjuk követni.

Problémát jelenthet a kezdeti hőmérséklet meghatározása. Megszokott módszer erre a felfűtés: adott hőmérsékleten kezdve, folyamatosan mérjük, hogy a véletlenül kiválasztott kezdőpontból milyen eséllyel lépünk rosszabb irányba. Ha ez egy előre megadott valószínűséget meghalad, akkor indulhat a hűtés, egyébként tovább növeljük a hőmérsékletet.

Leggyakrabban alkalmazott hűtési stratégia a következő: a hőmérsékletet egy egyhez közeli konstanssal szorozzuk meg minden lépésben. Egy lépéshez bizonyos számú állapotváltás tartozik, ahogy a hőmérséklet csökken, az állapotváltások száma nő.

Amint látható a módszer igen finoman hangolható a paraméterek különféle megadásával. Éppen ezért a módszert úgy implementáltuk, hogy ezeket a paramétereket a felhasználó adhassa meg.

3.12. ábra - A szimulált hűtéshez kapcsolódó osztályok osztálydiagramja

A szimulált hűtéshez kapcsolódó osztályok osztálydiagramja

Szimulált hűtés implementációja

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Szimulált hűtés algoritmusa.
 * @author KOÓS Dániel, DUSZA Anikó, SZATMÁRI László, MORSIANI Renato
 */
public class SimulatedAnnealing extends SolvingMethod<State> {

A módszer futását igencsak befolyásoló tényező a kezdeti hőmérséklet. Megoldás lehet az is, hogy ezt paraméterként konkrétan megadjuk, ám mivel mi úgy gondoljuk, hogy ezen programrendszer igen sok fajta feladat megoldására szolgál, ahol ezek a kezdeti hőmérsékletek más és más értékeket jelentenek, így beépítünk egy felfűtési szakaszt az algoritmusba. Ez két paramétert jelent:

protected int SUGGESTED;
protected double ACCEPTED_RATIO;

Az első megadja, hogy hány kísérletet kell elvégezni egy-egy futam során, míg a második azt határozza meg, hogy a milyen arányban várjuk el az állapotváltozásokat a kísérletek során. Ha túl kicsi a hőmérséklet, akkor kevés az állapotváltozás, míg melegedés során az arány egyre nő.

A hűtés során a gyakorlatban leginkább alkalmazott exponenciális módszert használjuk mi is, az alábbi konstanssal szorozzuk meg minden esetben az aktuális hőmérsékletet:

protected double alpha;

A szimulált hűtés másik sarkalatos pontja, hogy mennyit tölt az algoritmus egy adott hőmérsékleten, hány állapotváltással próbálkozunk. Itt mi egy igen egyszerű módszert alkalmazunk: megadunk egy minimális lépésszámot, majd minden hőmérséklet változással ez az érték eggyel nő. Ha eléri a megadott maximális lépésszámot, akkor leáll az algoritmus. A minimális és maximális lépésszám a módszer paramétere, és az alábbi változók tárolják:

protected int minStep;      
protected int maxStep;

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

@Override
public void constants(String name, int numerator, int denominator) {
    if (name.equals("MIN_STEP")) {
        minStep = numerator;
    }
    if (name.equals("MAX_STEP")) {
        maxStep = numerator;
    }
    if (name.equals("ALPHA")) {
        alpha = (double) numerator / denominator;
    }
    if (name.equals("SUGGESTED")) {
        SUGGESTED = numerator;
    }
    if (name.equals("ACCEPTED_RATIO")) {
        ACCEPTED_RATIO = (double) numerator / denominator;
    }
}

Azt, hogy az aktuális hőmérsékleten hány lépésre van lehetősége az algoritmusnak, az alábbi változó tárolja:

protected int steps;

Míg a hegymászó algoritmus esetén akkor léphettünk egy szomszédra, ha az jobb volt, mint az aktuális, a szimulált hűtés módszerének az a lényege, hogy itt rosszabb szomszédokat is választhatunk. De hogy valóban kiválaszthatjuk-e abban a véletlennek is van szava.

Természetesen jó irányba bármikor mehetünk, az nincs korlátozva. A rossz irányt a hőmérséklettől függő véletlen érték befolyásolja. Ha a hőmérséklet magas, akkor az esély nagy, viszont ha a hőmérséklet kicsi, akkor ez az esély szinte 0:

/**
 * Elfogadjuk-e a megadott lépéslehetőséget?
 * @param x aktuális állapot
 * @param index szomszéd állapot
 * @param c aktuális hőmérséklet
 * @return igen, ha a lépés elfogadható.
 */
protected static boolean accept(State x, int index, double c) {
    Random r = new Random();
    int diff = x.diffNeighbour(index);

Ha az eltérés negatív (a szomszéd jobb), akkor válthatunk a szomszédra, egyébként az eltérés ellentettjét osztjuk a hőmérséklettel, majd ezt a negatív számot konvertáljuk 0 és 1 közé az exponenciális függvénnyel. Ha ennél kisebb véletlen számot generálunk, akkor válthatunk a szomszédra.

if (diff < 0) {
    return true;
} else {
    return (Math.exp((double) (-diff) / c) > r.nextDouble());
} }

Ezután lássuk a felfűtést, amely az előbbi metódusra épít, és a paramétereinknek már megfelelő hőmérsékletet adja vissza:

/**
 * Felfűtés fázisa
 * @param x aktuális állapot
 * @return legmagasabb hőmérséklet
 */
protected double heating(State x) {
    Random r = new Random();

Véletlen módon választunk szomszédokat, melyek azonosítóját az index tárolja. Nyilvántartjuk (accepted), hogy hányszor válthattunk volna a szomszédos állapotra Míg az aktuális hőmérsékletet a c változó tárolja:

int index;   
int accepted; 
double c = 1.0; 

Minden hőmérsékleten lefuttatjuk az előírt kísérletet, és megszámoljuk az elfogadott váltások számát. Ha elértük a kitűzött arányt, akkor a ciklus véget ért, egyébként magasabb hőmérsékleten újra kezdjük:

do {
    accepted = 0;
    c *= 2; 
    for (int j = 0; j < SUGGESTED; j++) {
        index = r.nextInt(x.numberOfNeighbours());
        if (accept(x, index, c)) {
            ++accepted;
        }
    }
} while (ACCEPTED_RATIO > ((double) accepted / SUGGESTED));
return c;
}

A hűtés folyamatának része egy véletlen séta. Itt a lépésszámot a steps változó értéke határozza meg. Ennyiszer próbálunk véletlen módon választott szomszédba átlépni. Végül az aktuális állapottal térünk vissza:

protected State randomWalk(State x, double c) {
    Random rand = new Random();
    for (int j = 0; j < steps; j++) {
        int i = rand.nextInt(x.numberOfNeighbours());
        if (accept(x, i, c)) {
            x.chooseNeighbour(i);
        }
    }
    return x;
}    

A hűtéshez az előző metódussal beállítjuk a kezdő hőmérsékletet, és a kezdeti lépészámot:

/**
 * Végrehajtja a szimulált hűtést.
 * @param x aktuális állapot
 */
protected void annealing(State x) {

    double c;
    c = heating(x); 
    steps = minStep; 

Majd kezdődik egy ciklus. Először az adott hőmérsékleten bolyongunk. Ezután egy alacsonyabb hőmérsékletet választunk, ám az itt használható lépések száma növekszik, amíg a lépések adta határt el nem értük, folytatódhat az algoritmus:

do {
    x=randomWalk(x, c);
    c = c * alpha;
    steps++; 
} while (steps < maxStep); }

Mivel a módszer lényege az előbbi metódusban szerepel, a megoldás keresése lényegében nem jelent mást, mint ennek meghívását.

@Override
public State solve(State x) {
    x.fillRandom();
    annealing(x);
    return x;
}}

Párhuzamos hűtés

A szimulált hűtés egy szálon halad. Ilyen szálakat lehet egymástól függetlenül versenyeztetni, de talán hatékonyabb, ha ezek kooperálnak egymással:

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Több szimulált hűtést futtat párhuzamosan, s időnként paramétereket cserél.
 * @author ASZALÓS László
 */
public class ParallelTempering extends SimulatedAnnealing {

Ez a módszer egy további paramétert használ, az egymással párhuzamos szimulált hűtések számát:

private int N;

Természetesen a többi paraméter mellett ezt is be kell olvasni:

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

Itt már nem egy hőmérséklet jellemző az egész algoritmusra, hanem a külön-külön hűtések saját hőmérsékletekkel rendelkeznek. Ezeket egy tömbben tároljuk:

private double[] c;

Minden szimulált hűtésnek megvan a saját aktuális állapota, ezeket szintén egy tömbben tároljuk:

private State[] xs;

A hűtés alapjában úgy történik, mint korábban, csak minden egyes hőmérsékleten megnézzük, hogy nem-e érdemes két hűtés paramétereit kicserélni:

/**
 * Lehűti a rendszert, párhuzamosan mindegyiket. 
 * @return legjobb csoportosítás indexe
 */
protected int annealAll() {
    Random rand = new Random();
    do {

A korábbi véletlen bolyongás helyett véletlen bolyongások sorozatára van szükség. Mivel felhasználjuk az aktuális állapotok értékét, így minden esetben kiszámítjuk a célfüggvény értékét, és természetesen az esetleg eltérő hőmérsékletek egyaránt csökkennek:

for (int i = 0; i < xs.length; i++) {
    xs[i]=randomWalk(xs[i], c[i]);
    xs[i].calculate();
    c[i] = c[i] * alpha;
}

Ezek után a szomszédos hűtésekre ellenőrizzük a Metropolis–Hastings kritériumot. Ha teljesül, akkor cseréljük ki a két hőmérsékletet:

for (int i = 1; i < xs.length; i++) {
    double r = Math.exp((xs[i - 1].getValue() - xs[i].getValue())
            * (1.0 / c[i - 1] - 1.0 / c[i]));
    if (rand.nextDouble() < r) {
        double temp = c[i - 1];
        c[i - 1] = c[i];
        c[i] = temp;
    }
}
steps++;
} while (steps < maxStep);

Ezután a megoldáshoz már csak a legjobb aktuális állapot kiválasztása marad hátra. Itt nem kell mást tenni, mint kiválasztani a legkisebb célfüggvényértékkel bíró állapotot:

int min = 0;
int minV = xs[0].getValue();
for (int i = 1; i < xs.length; i++) {
    if (xs[i].getValue() < minV) {
        min = i;
        minV = xs[i].getValue();
    }
}
return min;
}

A módszer elindítása kicsit körülményes. Míg korábban használhattuk az argumentumként megkapott állapotot, most azokról másolatot készítünk, és azokkal indítjuk a szimulált hűtésnél már megismert felfűtést.

@Override
public State solve(State x) {
    c = new double[N];
    xs = new State[N];
    for (int i = 0; i < xs.length; i++) {
        xs[i] = x.copy();
        xs[i].fillRandom();
        xs[i].calculate();
        c[i] = super.heating(xs[i]); 
    }

Ezek után beállítjuk a kezdeti lépésszámot, és alkalmazzuk a előbbi metódust.

steps = minStep;
int min = annealAll();
return xs[min];
}}