Méhek algoritmusa

Háttér

A méhek algoritmusa 2004-től eredeztethető. Az algoritmus próbálja a méhek társadalmát utánozni. Ehhez két típusú méhet különböztetünk meg: a kereső méheket, és a mézhordókat. A kereső méhek felderítik a környezetet, majd tánc formájában beszámolnak eredményeikről a kaptárnak. Ennek megfelelő mennyiségű mézhordó indul el, és takarítja be a termést.

Esetünkben a keresőméheket szétszórjuk a keresési térben, és csak a legjobb függvényértékkel rendelkezőkhöz (elit) rendelünk mézhordókat, arányosan a függvényértékkel. A többi kereső tovább bolyong a keresési térben, és dinamikusan változik, hogy melyek tartoznak az elithez, és melyiket mennyi méh követi. A mézhordók a számukra kirendelt keresőméh körül mozognak, és ha jobb függvényértéket találnak, akkor a keresőméh ide lép.

4.8. ábra - Bees osztály

Bees osztály

4.9. ábra - Bee2 osztály

Bee2 osztály

Méhek algoritmusának implementációja

package hu.unideb.inf.optimization.methods;
import java.util.Random;
import java.util.Arrays;
/**
 * A Bees algoritmus a méhek nektárgyűjtését követi.
 * @author BÓNIS Balázs
 */
public class Bees extends SolvingMethod<State> {

Az előzőekhez hasonlóan itt is van pár ismert paraméter:

protected int MAX_STEPS;
protected int N;

Az N a keresőméhek számát jelöli, melyből párat külön kezelünk, ezek számát adja meg a következő paraméter:

protected int ELITE;

A paraméterek betöltése a megszokott:

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

A módszerben felhasznált adatszerkezet egyrészt tárolja a keresőméhek helyzetét:

protected State[] bees;

Továbbá azt,hogy egy elit-méhet hány mézhordó követ, pontosabban az elit környezetében hány kísérletet teszünk meg egy lépésben:

protected int followers[];

Az alaphelyzetbe állításnál az átadott állapotot kell átmásolni. A véletlen kezdőpozíció beállítása most máshol történik.:

/**
 * Adatszerkezet inicializálása
 */
protected void beesInitialize(State x) {
    bees = new State[N];
    for (int i = 0; i < bees.length; i++) {
        bees[i] = x.copy();
    }
}

Az i-ik elit-méh környezetében a followers tömbben szereplő számnak megfelelő kísérletet végzünk el. Ennyi szomszédos állapotot vizsgálunk meg, és a legjobbat feljegyezzük. Ha ez a legjobb szomszéd jobb mint az aktuális állapot, akkor a méh átlép oda, és kiszámolandó az új függvényérték.

/**
 * Az <code>i</code>-dik méhet legjobb szomszédjába mozdítja el.
 * @param i a méh indexe
 */
protected void findNeighbour(int i) {
    Random rand = new Random();
    int index, value, diff;
    int bestIndex = -1;
    int bestDiff = 0;
    for (int j = 0; j < followers[i]; j++) {
        index = rand.nextInt(bees[0].numberOfNeighbours());
        diff = bees[i].diffNeighbour(index);
        if (bestDiff > diff) {
            bestIndex = index;
            bestDiff = diff;
        }
    }
    if (bestDiff < 0) { 
        bees[i].chooseNeighbour(bestIndex);
        bees[i].calculate();
    }
}

A diákjaim az előbbi a függvényt találták. Ebben az esetben az összes követő méh számát az ELITE és N értékek meghatározzák. Figyelni kell a paraméter megadásánál, hogy ne kapjunk negatív értékeket:

/**
 * Követők méretének beállítása
 */
protected void generateFollowerSizes() {
    followers = new int[ELITE];
    for (int i = 0; i < followers.length; i++) {
        followers[i] = N - (i + 1) * (i + 1) / 3;
    }
}

A nem elit keresőméhek minden lépésben véletlenszerűen helyet változtatnak. Az első lépésben ez igaz mindegyik méhre, ezért is van ez a kezdeti index, mint függvény-paraméter:

/**
 * Méh-populáció véletlen feltöltése az adott indextől kezdve
 * @param index kezdeti index
 */
protected void randomBees(int index) {
    for (int i = index; i < N; i++) {
        bees[i].clean();
        bees[i].fillRandom();
        bees[i].calculate();
    }
}

A megoldási módszerünk itt is egy kezdeti feltöltéssel és randomizálással kezdődik. Majd meghatározzuk a követő rajok méreteit. Ezután indul az előírt lépésszámú ciklus.

Ebben először rendezzük a méheket, hogy kiderüljön, hogy ebben a fordulóban melyek tartoznak az elithez. Ezekhez elvégezzük a kísérleteket, míg a többit véletlen pozícióba helyezzük.

Ha már a ciklusnak vége, még egyszer utoljára rendezzük a méheket, és a legjobbat visszaadjuk:

@Override
public State solve(State x) {
    beesInitialize(x);
    randomBees(0); 
    generateFollowerSizes();
    for (int iter = 0; iter < MAX_STEPS; iter++) {
        Arrays.sort(bees); 
        for (int i = 0; i < ELITE; i++) { 
            findNeighbour(i);
        }
        randomBees(ELITE); 
    }
    Arrays.sort(bees); 
    return bees[0];
}}

Apróbb változtatás a követő méheknél

package hu.unideb.inf.optimization.methods;
/** A <code>Bees</code> osztály továbbfejlesztése: a követő méhek száma paraméter.
 * @author Aszalós László
 */
public class BeesV extends Bees {

A korábbihoz képest egy új paraméterünk van, hány méh követi az elit méheket:

private int FOLLOW;

Ennek a paraméternek a 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("FOLLOW")) {
         FOLLOW = numerator;
     }
 }

A négyzetes csökkenés ebben ez esetben is teljesül, viszont most a followers tömbben szereplő értékek összege az előírt paramétert közelíti:

@Override
protected void generateFollowerSizes() {
    /* Az értékek négyzetesen csökkennek,
     * összegük a megadott FOLLOW konstans.*/
    int sum = (2 * ELITE * ELITE * ELITE + 3 * ELITE * ELITE + ELITE) / 6;
    followers = new int[ELITE];
    for (int i = 0; i < followers.length; i++) {
        followers[i] = Math.round((ELITE - i) * (ELITE - i) * FOLLOW / sum);
    }
}}

Méhek változó környezet variánsa

Ebben az általunk megalkotott variánsban a környezet idővel nő:

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
import java.util.Random;
/**
 * Méhek módszerének variánsa, ahol a követő méhek idővel
 * egyre nagyobb körben keresnek.
 * @author ASZALÓS László
 */
public class Bee2 extends SolvingMethod<State> {

A módszer paraméterei majdnem megegyeznek az előző változat paramétereivel:

private int MAX_STEPS;
private int N;
private int ELITE;
private int FOLLOW;

Egy új paraméterünk van csak, mely azt adja meg, hogy hány iteráció után növekedhet a környezet sugara

private int STEP;

A paraméterek beolvasása is szinte ugyanaz:

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

A keresőméhekhez most hozzárendelünk egy hosszt, a keresési környezet sugarát:

private class MyBee implements Comparable {
    private State bee;
    private int radius;

A konstruktor csak abban különbözik a korábbitól, hogy a keresési környezet sugarát is be kell állítani:

MyBee(State x){
    bee = x.copy();
    bee.fillRandom();
    bee.calculate();
    radius = 1;
}

Miután ezeket a méheket is rendezni kívánjuk, definiálni kell köztük a rendezés alapját:

public int compareTo(Object o) {
    State ob = ((MyBee)o).bee;
    return bee.compareTo(ob);
}   }

Az adatszerkezeteink lényegében megegyeznek az előző változatéval, ahogy az inicializálásuk is:

private MyBee[] bees;
private int followers[];

protected void beesInitialize(State x) {
    bees = new MyBee[N];
    for (int i = 0; i < bees.length; i++) {
        bees[i] = new MyBee(x);
    }
}

A keresés során az elit-méhet a környezetében talált legjobb irányba fogjuk elmozdítani.

/**
 * Az <code>i</code>-dik méhet elmozdítja a legjobb irányba. 
 * @param i a méh indexe
 */
protected void findNeighbour(int i) {
    Random rand = new Random();
    State follower;
    int index, diff;
    int bestDiff = 0;
    State best=null;

Technikai okokból ha a kör sugara 3, akkor nem csak a méhtől 3 távolságra levő állapotokat vizsgáljuk, hanem ugyanannyi 1 távolságút mint 2 távolságút és 3 távolságút. Éppen ezért az alábbi ciklus nem a követők számáig tart. Készítünk egy másolat az elitről és a kör sugarának megfelelő számú lépésben azt egyre távolabb visszük a keresőméhtől. Nyomon követjük, hogy mennyit változott a célfüggvény értéke, és ha jobb pozíciót találunk, mint amilyen az elité, akkor azt feljegyezzük:

for (int j = 0; j < followers[i]/bees[i].radius; j++) {
    follower = bees[i].bee.copy();
    diff=0;
    for (int k = 0; k < bees[i].radius; k++) {
        index = rand.nextInt(follower.numberOfNeighbours());
        diff += follower.diffNeighbour(index);
        follower.chooseNeighbour(index); // megtesszük a lépést
        if (bestDiff > diff) {// ha van jobb lépés
            bestDiff = diff;
            best=follower.copy();
        }
    }
}

Végül ha sikerült az eliténél jobb eredményt elérni, akkor azt a feljegyzett pozícióba mozgatjuk. Mivel új helyre kerül, a keresési környezetet újra kicsire állítjuk:

if (bestDiff < 0) {
    bees[i] = new MyBee(best);
    bees[i].bee.calculate();
    bees[i].radius=1;
}   }

Az alábbi két metódus betűről betűre megegyezik a korábban megadottal:

protected void generateFollowerSizes() {
     int sum = (2 * ELITE * ELITE * ELITE + 3 * ELITE * ELITE + ELITE) / 6;
    followers = new int[ELITE];
    for (int i = 0; i < followers.length; i++) {
        followers[i] = Math.round((ELITE - i) * (ELITE - i) * FOLLOW / sum);
    }
}

/**
 * Méh-populáció véletlen feltöltése az adott indextől kezdve
 * @param index kezdeti index
 */
protected void randomBees(int index, State x) {
    for (int i = index; i < N; i++) {
        bees[i] = new MyBee(x);
        bees[i].radius=1;
    }
}

A megoldást kereső módszer nagyon hasonlít a korábban megadotthoz. Annyi az eltérés, hogy itt felhasználjuk a STEP paramétert. Ha a lépésszám ennek többszöröse, akkor az elithez tartozó méhek környezete nő.

Így ha egy méh régóta az elit tagja, akkor mivel a szűk környezetét a program alaposan átvizsgálta, érdemes a keresést kiterjeszteni. Az elitbe frissen bekerült méhek környezete viszont kicsi, így közvetlen környezetüket alaposan meg fogja vizsgálni a módszer:

@Override
public State solve(State x) {
    beesInitialize(x);
    randomBees(0,x); 
    generateFollowerSizes();
    for (int iter = 0; iter < MAX_STEPS; iter++) {
        Arrays.sort(bees); 
        for (int i = 0; i < ELITE; i++) { 
            if (0 == iter % STEP) {bees[i].radius++;} 
            findNeighbour(i);
        }
        randomBees(ELITE,x); 
    }
    Arrays.sort(bees); 
    return bees[0].bee;
}}

Feladatok

  1. Adjon meg további módszert a követők meghatározására, és hasonlítsa össze az eredményeket!

  2. Hasonlítsa össze a módszer eredményeit különböző STEP értékekre!