Rovarraj implementáció

A rovarraj optimalizációt alapvetően folytonos értékekkel leírható problémákra alkalmazzák. Minden egyes rovar ismeri a saját eddigi legjobb, valamint a raj eddigi legjobb pozícióját. A rovar kezdetben véletlen irányú sebességét e két pozícióba mutató irányú, aktuális távolsággal arányos, véletlen értékkel változtatjuk. Így lehetővé válik az aktuális pozíció környezetének felfedezése, valamint a jónak tekintett pontok megközelítése. Az adott feladathoz tartozó paraméterek megválasztása a kutatások jelenlegi tárgya.

A módszer alkalmazása során egyik állapotból egy másik irányába haladunk. Az erre szolgáló nearTo metódus csak StateRC típus esetén definiált, így itt ezt kell használnunk. Az átláthatóbb kód érdekében bevezetünk egy belső osztályt:

4.6. ábra - Rovarraj módszer osztálydiagramja

Rovarraj módszer osztálydiagramja

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Rovarraj optimalizációs módszer.
 * @author DUSZA Anikó, KOÓS Dániel, MORSIANI Renato, SZATMÁRI László
 */
public class ParticleSwarm extends SolvingMethod<StateRC> {

A rovarraj módszert is több paraméter határozza meg. Mint korábban, itt is fontos a populáció mérete:

private int N;

Hasonlóan a korábbiakhoz itt is adott egy lépésszám, amíg fut az algoritmus, esetünkben ez az eseménytelen lépések számát jelöli:

private int MAX_STEPS;
Végül egy-egy egyednek tekintett állapot három fajta mozgást tehet:
  • véletlen bolyong,

  • halad a saját legjobb pozíciója felé,

  • halad a raj legjobb pozíciója felé.

Az első két eset esélye R1 és R2-R1, míg a harmadiké 1-R2 lesz, ehhez szükséges a két paraméter:

private double R1;
private double R2;

Eme paramétereket a megszokott módon olvassuk be:

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

Belső osztály rovaroknak

Annak érdekében, hogy ne kelljen a részletekkel foglalkozni, az egyed részére megalkottunk egy belső osztályt:

/** * Belső osztály a rovarok tulajdonságainak */
private class Particle {

Az egyed/részecske két attribútummal rendelkezik, hol található most, illetve melyik pozíció volt számára a legjobb mindeddig?

private StateRC now;     
private StateRC best;

A részecske konstruktora megkapja a kezdeti adatszerkezetet, melyhez új állapotot generál, ehhez kiszámolja a függvényértéket, illetve elmenti, mint az eddigi legjobbat:

Particle(StateRC x) {
    now = (StateRC) x.copy();
    now.fillRandom();
    now.calculate();
    best = (StateRC) now.copy();
}

A részecskére vonatkozó érték nem más, mint aktuális pozíciójához tartozó érték:

/**
 * Mi a rovarhoz tartozó érték?
 * @return célfüggvény értéke
 */
int getValue() {
    return now.getValue();
}

A legjobb eddigi pozíciója pedig az eltárolt állapot:

/**
 * A legjobb pozíció
 * @return a teljes állapot
 */
StateRC getBest() {
    return best;
}

A részecske mozgását egy véletlen érték a következőképp határozza meg. Ha az kisebb, mint az első paraméter, akkor a részecske valamely szomszédos állapotba jut. Ha a két paraméter közé esik, akkor akkor saját korábbi legjobb állapota felé mozdul, egyébként pedig a raj legjobb értéke fele indul:

int move(double r) {
    if (r <= R1) {
        Random rr = new Random();
        int index = rr.nextInt(now.numberOfNeighbours());
        now.chooseNeighbour(index);
    } else if (r <= R2) {
        now.nearTo(best);
    } else {
        now.nearTo(xMin);
    }

Természetesen a mozgás megváltoztatta az aktuális pozíciót, és ezzel a célfüggvény értékét. Ezt újra kell számolni, és ha ez az érték jobb, mint az eddigi saját legjobb, akkor akként kell tárolni.

now.calculate();
if (now.getValue() < best.getValue()) {
    best = (StateRC) now.copy();
}

return now.getValue();
}    }

Rovar osztály alkalmazása

A belső osztály segítségével egyszerűen tudunk dolgozni a továbbiakban. Szükségünk lesz a részecskék tárolására:

private Particle[] swarm;

Valamint az eddig talált lejobb állapotra:

private StateRC xMin;

Az adatszerkezetek alaphelyzetbe állítása egyszerű feladat. Megfelelő számú részecskét tárolni képes vektort kell előállítani, és alkalmazni a belső osztály konstruktorát.

/**
 * Részecskék inicializálása.
 * @param x másolandó állapot
 */
private void psInitialize(StateRC x) {
    swarm = new Particle[N];
    for (int i = 0; i < swarm.length; i++) {
        swarm[i] = new Particle(x);
    }

Az előbb deklarált xMin változónak is értéket kell adnunk. Ezt egy egyszerű minimumkereséssel oldhatjuk meg:

int min = swarm[0].getValue();
int minIndex = 0;
for (int i = 1; i < N; i++) {
    if (swarm[i].getValue() < min) {
        min = swarm[i].getValue();
        minIndex = i;
    }
}
xMin = (StateRC) swarm[minIndex].getBest().copy();
        }

A megoldás keresése során kezdünk az adatszerkezet feltöltésével, majd indul egy ciklus, mely a előírt lépésszámnak megfelelően futna. A ciklusmag belsejében minden részecskét külön-külön megmozgatunk, és ha valamely olyan pozícióba jut, mely jobb az eddig talált legjobbnál, akkor ezt tároljuk tovább az xMin változóban. Sőt ekkor újrakezdjük a lépések számolását:

@Override
public StateRC solve(StateRC x) {
    Random r = new Random();
    psInitialize(x); 
    int value;
    for (int step = 0; step < MAX_STEPS; step++) {
        for (int i = 0; i < N; i++) {
            value = swarm[i].move(r.nextDouble());
            if (value < xMin.getValue()) {
                xMin = (StateRC) swarm[i].getBest().copy();
                step = 0;
            }
        }
    }
    return xMin;
}
}

Feladatok

  1. Implementálja a diszkrét raj módszert mint a folytonos módszer egy variánsát! Tipp: használja a

    A. Lazinica könyvének 397-422 illetve 451-460 oldalán található cikkeket!

  2. Amint a rovarok elmozdulnak újraszámoljuk a teljes célfüggvényt. Módosítsa/bővítse a nearTo metódust, hogy az vagy aktualizálja a célfüggvény értékét, vagy valamilyen módon adja vissza a célfüggvény értékek differenciáját.

  3. Módosítsa a módszert úgy, hogy egy rovar csak a számára kijelölt rovarokat figyeli, közülük a legjobb irányába mozdul el szükség esetén. Próbálkozzon a különféle kijelölések hatásával. (Tipp: próbálja ki a következő kapcsolódásokat: rovarbrigádok, hierarchikus rovarsereg, véletlen irányított és nem irányított kapcsolatok. Van-e annak hatása, ha rovarszigetek alakulnak ki, azaz a szomszédsági reláció lezártja nem a teljes reláció a rovarok között?)