Sztochasztikus hegymászó algoritmus

A sztochasztikus hegymászó algoritmus a hegymászó algoritmus egy újabb variánsa. A hagyományos hegymászó keresés mohó keresés, mindig a legjobb szomszéd irányába mozdul el a keresés. Ebben a részben egy olyan változatot ismertetünk, melyben a jó lépések közül azok jóságával arányosan választunk.

Ezt a következőképpen implementáljuk. Az alábbi ábra felső része mutatja, hogy az aktuális állapotban milyen lépéseket tehetünk (x tengely), és mekkora az ehhez a lépéshez tartozó célfüggvény-érték eltérése (y tengely) az aktuális állapot célfüggvény-értékétől. Jelöljék a vonal feletti részek, ahol a lépéssel javíthatunk a célfüggvény értékén, és a vonal alatti részek pedig azt, ahol ronthatunk rajta. Ehhez definiálunk egy függvényt, ami az ábra alsó felén szerepel. Mint látható, ez a függvény akkumulálja a jó irányba vivő lépéseket. Ha a felül szereplő függvény egy adott állapotban z pozitív értéket vesz fel, akkor az alul szereplő függvény értéke z-vel nő, egyébként az értéke nem változik.

3.9. ábra - Sztochasztikus keresés lépéseihez tartozó differenciák és az azok alapján generált függvény.

Sztochasztikus keresés lépéseihez tartozó differenciák és az azok alapján generált függvény.

Ezek után választunk egy egyenletes eloszlású véletlen értéket a függvény értékkészlete által meghatározott intervallumból, s megkeressük, hogy ez az érték mely lépéshez kapcsolható. Ahogy az az ábrán is látható, nagy lépéshez nagy valószínűség tartozik.

3.10. ábra - Véletlen r érték, és a hozzá tartozó y lépés kiválasztása

Véletlen r érték, és a hozzá tartozó y lépés kiválasztása

3.11. ábra - A sztochasztikus hegymászó kereséshez kapcsolódó osztályok osztálydiagramja

A sztochasztikus hegymászó kereséshez kapcsolódó osztályok osztálydiagramja

Akkumulált javítások

Az akkumulált javítások tárolását, visszakeresését egy külön osztály oldja meg:

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
/**
 * Változások akkumulálása.
 * @author Aszalós László
 */
public class DiffArrayTools {

Az adatainkat egy tömbben tároljuk:

private int[] diffArray;

Ha több egymást követő szomszéd sem jobb mint az aktuális állapot, akkor az előbbi tömb egymást követő pozícióin ugyanaz a szám szerepel. Ekkor természetesen nem azt a szomszédot kell kiválasztani mely csak ront a helyzeten, hanem azt, amely javít: tehát azt, amelyhez tartozó érték nem egyezik meg az őt megelőző értékkel. Persze az is előfordulhat, hogy a kiválasztott értéket a diffArray-ban tárolt függvény átugorja, ekkor az első nála nagyobb számhoz tartozó indexet/szomszédot kell választani.

Mivel a függvény monoton nemcsökkenő, a lineáris keresés helyett választhatjuk a bináris keresést, amely jelentős gyorsulást jelent, viszont óvatosan kell bánni a beépített függvény furcsaságaival:

/**
 * Megkeressük x első előfordulását.
 * @param x keresett érték
 * @return index, melyen először fordul elő <code>x</code>,
 * vagy nála nagyobb szám.
 */
int binarySearch(int x) {
    int j = Arrays.binarySearch(diffArray, x);
    if (j == diffArray.length) {
        return j - 1;
    }

A negatív szám azt jelenti, hogy az elem nem szerepel, ekkor annak az a kérdés, hogy ezt az elemet hova lehetne beszúrni:

if (j < 0) {
    j = -1 - j;
}

Ha egymást követő azonos elemek vannak, akkor közülük az elsőt keressük:

while (j > 0 && diffArray[j] == diffArray[j - 1]) {
    j--;
}
return j;
}

Az adatok lekérése egyszerűen a tömb megfelelő elemének visszaadását jelenti:

/**
 * Adatszerkezet <code>index</code>-edit eleme
 * @param index elem indexe
 * @return elem értéke
 */
int getX(int index) {
    return diffArray[index];
}

Elvileg lehetne konstruktor is, ám metódusként fogalmaztuk meg az adatszerkezet (azaz a tömb) inicializálását. Ez nem jelent mást, mint a méret megadását, és kezdeti értékkel feltöltését:

/**
 * Adatszerkezet előkészítése
 * @param size adatszerkezet mérete
 */
public void init(int size) {
    diffArray = new int[size];
    Arrays.fill(diffArray, 0);
}

Adott elem adott indexen történő rögzítése nem jelent mást, mint a tömbben a megfelelő helyre beírást:

/**
 * Adat rögzítése
 * @param index adat helye
 * @param value adat értéke
 */
void setX(int index, int value) {
    diffArray[index] = value;
}

Egyik egységtesztben szerepel az adatszerkezet mérete:

/** teszteléshez
 * @return vektor hossza
 */
int length() {
    return diffArray.length;
}}

Sztochasztikus keresés implementációja

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Hegymászó keresés variánsa, minden lépést kiszámol,
 * és az adott lépés jóságától függően véletlenszerűen választja azt.
 * @author BÓNIS Balázs, SZOKOL Péter
 */
public class StochasticHC extends SolvingMethod<State> {

Mivel több variánst is megadunk, a közös segédfüggvényeket külön osztályba szerveztük:

DiffArrayTools diffArr = new DiffArrayTools();

Megvizsgáljuk az aktuális állapot összes szomszédját. Ha valamelyiknél a függvény értéke kisebb, akkor érdemes lehet arra menni. Éppen ezért a sumDiff értékét ezzel az aktuális és szomszéd függvényértékeinek különbségével (abszolút érték!) növeljük, és eltároljuk. Ha a szomszéd értéke nem jobb, akkor a sumDiff korábbi értékét tároljuk a szóbanforgó szomszédnál.

Ennek eredményeképpen a javítások akkumulált értékeiből álló függvényt tárolja a segédosztály:

/**
 * Meghatározzuk, hogy mely lépéssel mennyit nyerhetünk.
 * @param x aktuális állapot
 */
public void calculateDiffs(State x) {
    int sumDiff = 0;
    int difference;
    for (int i = 0; i < x.numberOfNeighbours(); i++) {
        difference = x.diffNeighbour(i);
        if (difference < 0) {
            sumDiff -= difference; 
        }
        diffArr.setX(i, sumDiff);
    }
}

Az algoritmus nem paraméterfüggő:

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

A módszer egy véletlen pontból indul. Megfelelő méretű tárolót biztosítunk az előbbi metódussal számolt függvény számára:

@Override
public State solve(State x) {
    int stochastic; 
    int max;
    x.fillRandom();
    diffArr.init(x.numberOfNeighbours());

Majd egy ciklust kezdünk. Ebben kiszámítjuk az említett függvényt, majd ennek a monoton nemcsökkenő függvénynek maximális értékét vesszük, és ha van javulás, azaz legalább az egyik szomszédja jobb mint az aktuális állapot, akkor sorsolunk egy függvényértéket, és megkeressük, hogy ezt hol éri el, vagy hol lépi át. Ezt a szomszédot választjuk ki, mint következő aktuális állapot:

do {
    Random random = new Random();
    calculateDiffs(x);
    max = diffArr.getX(x.numberOfNeighbours() - 1);
    if (max > 1) {
        // TODO a sorsolás, a lépés kiválasztása történjen a DiffArrayTools.ban!
        stochastic = random.nextInt(max - 1) + 1;
        int step = diffArr.binarySearch(stochastic);
        x.chooseNeighbour(step);
    }
} while (max > 1);
return x;
}}

Feladatok

  1. Készítse fel a sztochasztikus keresés programját arra, hogy nem konstanst az aktuális állapot szomszédjainak a száma! Ilyen feladat például a korábban említett huszártúra. (Tipp: paraméterként kérje be a maximális szomszédszámot, és ennek megfelelően foglaljon helyet. A program ügyeljen arra, hogy esetleg mégis több szomszéd lesz!)

  2. Készítse el a korábban alkalmazott három különféle környezetfelderítési módszernek megfelelő variánsait az itt közölt programnak! Hasonlítsa össze az eredményeket és a futási időket!