Szentjánosbogár algoritmus

Háttér

A szentjánosbogár algoritmus rövid múltra tekint vissza, 2008-ban jelent meg az első publikáció. Az előbb ismertetett rovarraj optimalizációtól eltérően itt nincs szükség, hogy az egyes rovarok emlékezzenek a legjobb állapotaikra, hanem minden egyes szentjánosbogár fényessége az állapotához tartozó célfüggvényértékkel arányos. A szentjánosbogarak minden egyes lépésben a legfényesebb társuk felé haladnak. Ez így első hallásra a rovarraj módszer variánsának tűnik. Viszont nem szabad figyelmen kívül hagyni az abszorpció jelenségét. Ebből számunkra az Id=I0e-γd képlet az érdekes. Az I0 kezdeti intenzitás Id-re csökken, mialatt a sugárzás γ elnyelési együtthatójú, d vastagságú rétegen halad át. Ezt kombinálhatjuk az fényre vonatkozó inverz négyzetes szabállyal, így az előbbi képletben d helyére d2 kerül A számolást egyszerűsítendő ezt a képletet a következővel közelíthetjük: Id=I0/(1+γd2). Viszont míg az eredeti szentjánosbogár algoritmusban a maximumot, optimalizációs feladatunkban a minimumot keressük. Bár számolhatnánk az eredeti képlet ellentettjével vagy reciprokával, mi osztás helyett szorozni fogunk, és a legkisebb értéket választjuk az összes közül.

A Firefly osztály igen egyszerű:

4.7. ábra - Firefly osztály

Firefly osztály

Szentjánosbogár algoritmus megvalósítása

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Rovarraj algoritmus variánsa.
 * @author DUSZA Anikó
 */
public class Firefly extends SolvingMethod<StateRC> {

Pár paraméter ugyanazt a szerepet tölti be most is, mint az előbb is:

private int N;
private int MAX_STEPS;

Viszont van egy másik paraméter, mely a fényelnyelést jelöli:

private double GAMMA;

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

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

A bogarainkat egy vektorban tároljuk:

private StateRC firefly[];

A fényelnyelés képletében exponenciális függvény szerepel. Ez közelíthető az eredeti érték per távolság négyzete plusz egy kifejezéssel. Mivel eredetileg a legfényesebb szomszédot keresik, míg mi pedig a minimálist (leghalványabbat), osztás helyett szorozni fogunk. Annak érdekében, hogy ne kelljen ugyanannál a feladattípusnál más és más méret esetén újabb GAMMA értékeket használni, a feladatot normalizáljuk azáltal, hogy a szűkített környezetek számával osztjuk a távolságokat:

/**
 * Kiszámolja az abszorciós értéket.
 * @param x aktuális állapot
 * @param y távoli állapot
 * @return a fv értéke
 */
private double calculateValue(StateRC x, StateRC y) {
    double product = GAMMA * Math.pow(x.distance(y)
            /x.numberOfRestrictedNeighbours(), 2);
    return (y.getValue() * (product + 1));
}

Az előző módszerhez hasonlóan a megfelelő méretű vektort feltöltjük a megadott állapot másolataival, majd új kezdőpontokat generálunk, és kiszámítjuk a függvényértékeket:

/** A bogarak kezdeti populációjának inicializálása
 * @param x kezdeti állapot
 */
private void ffInitialization(StateRC x) {
    firefly = new StateRC[N];

    for (int i = 0; i < firefly.length; i++) {
        firefly[i] = (StateRC) x.copy();
        firefly[i].fillRandom();
        firefly[i].calculate();
    }
}

A rovarraj algoritmusban abszolút értékeket használunk, míg itt relatívakat. Minden egyes bogár a legfényesebb bogár irányába indulna el, ezért minden egyes bogár esetén meg kell keresni a legfényesebb szomszédját

/**
 * Megkeresi a legfényesebb szomszédot.
 * @param index aktuális bogár indexe
 * @return a legfényesebb szomszéd indexe
 */
private int findBrightest(int index) {
    int minIndex = 0;
    double minValue = calculateValue(firefly[index], firefly[0]);
    for (int i = 1; i < firefly.length; i++) {
        double temp = calculateValue(firefly[index], firefly[i]);
        if (temp < minValue) {
            minValue = temp;
            minIndex = i;
        }
    }
    return minIndex;
}

Kívülről a megoldási módszer hasonló mint korábban: adott lépésszámig kell menni, és minden lépésben megmozgatunk minden egyes bogarat.

@Override
public StateRC solve(StateRC d) {
    Random r = new Random(); 
    int bestIndex; 
    int bestValue;  
    ffInitialization(d);
    for (int t = 0; t < MAX_STEPS; t++) { 
        for (int i = 0; i < N; i++) {

A bogár esetén meg kell nézni, hogy melyik a legfényesebb szomszédja. Ha az derül ki, hogy saját maga, akkor véletlen bolyongáshoz kezdhet. Ha nem ő, akkor a megfelelő szomszédja fele kell elmozdulnia. Mindkét esetben elmozdult, újra kell számolni a célfüggvény értékét:

int j = findBrightest(i); 
if (j == i) { 
    firefly[i].chooseNeighbour(
            r.nextInt(firefly[i].numberOfNeighbours()));
} else { 
    firefly[i].nearTo(firefly[j]);
}
firefly[i].calculate(); 
}   }

Ha túl vagyunk az összes lépésen, akkor egyszerű minimumszámítással meg kell keresnünk a legjobb bogarat, melyet eredményként visszaadunk:

bestIndex = 0;
bestValue = firefly[0].getValue();
for (int i = 1; i < N; i++) {
    int temp = firefly[i].getValue();
    if (temp < bestValue) {
        bestIndex = i;
        bestValue = temp;
    }
}
return firefly[bestIndex];
}   }

Feladatok

  1. Alakítsa át a módszert úgy, hogy tárolja az egyes rovarok távolságát úgy, hogy egy elmozdulás után könnyen meghatározható legyen a távolság változása!

  2. Építse be a módszerbe az xMin változót a megszokott szerepben!