4. fejezet - Sokaságokon alapuló algoritmusok

Tartalom

Evolúciós stratégia
Evolúció - absztrakt módszer
Segédosztály evolúcióhoz
(μ,λ) változat
(μ+λ) változat
Speciális evolúció változat
Feladatok
Genetikus algoritmus
Absztrakt genetikus algoritmus
Elitista megközelítés
Konkrét megvalósítások
Stabil megközelítés
Üresedés
Konkrét megvalósítások
Feladatok
Rovarraj implementáció
Belső osztály rovaroknak
Rovar osztály alkalmazása
Feladatok
Szentjánosbogár algoritmus
Háttér
Szentjánosbogár algoritmus megvalósítása
Feladatok
Méhek algoritmusa
Háttér
Méhek algoritmusának implementációja
Apróbb változtatás a követő méheknél
Méhek változó környezet variánsa
Feladatok
Harmónia keresés
Háttér
Harmónia keresés implementációja
Feladatok
Kereszt-entrópia
Kereszt-entrópia implementációja
Feladatok

Már korábban is ismertettünk olyan módszert, ahol egyszerre több szálon is fut a keresés. Ám miután az a hegymászó algoritmusnak volt egy speciális változata, így jobbnak láttuk az előző fejezetben ott ismertetni.

Az evolúciós és genetikus algoritmustól eltekintve az itt bemutatásra kerülő algoritmusok viszonylag frissek, és többnyire a természetből származó ötleteket használ fel.

Evolúciós stratégia

Két evolúciós algoritmus mutatunk be: az egyik a (μ,λ), míg a másik a (μ+λ) néven ismert. Mindkét esetben a szülők halmaza μ elemből áll, és λ leszármazottjuk lesz. Első esetben a gyerekek közül a μ legjobb elfoglalja a szülők helyét, míg második esetben a szülők és gyerekek versenyeznek a legjobb μ pozíciójáért.

4.1. ábra - Evolúciós algoritmus osztálydiagramja

Evolúciós algoritmus osztálydiagramja

Mivel mindig a legjobb elemeket kell keresni, egy olyan adattárolási szerkezetet érdemes használni, melyben a rendezés egyszerűen, kis költséggel megvalósítható, mint például a PriorityQueue. Nekünk sajnos ezt nem sikerült működésre bírni, így a kicsit lassabban használható ArrayList adatszerkezetet használjuk ebben a fejezetben.

Egy aprócska segédosztályban meg is fogalmaztunk két metódust. A fillFirst metódus egy mintának megadott állapotot (c) másol le size-szor, véletlen módon feltölti, és az x listában helyezi el azokat. Természetesen az ArrayList nem rendezetten tárolja az állapotokat, így nekünk kell azt a feltöltés végén rendezni.

A generateChildren metódus a c szülőnek n darab gyerekét generálja, majd azokat a megadott mértékben (r) megváltoztatja és végül az y listában helyezi el. Mivel a Java hajlamos az objektumok esetén csak a hivatkozásokat eltárolni, így nem érdemes a c változót többször, különböző tartalmakkal elhelyezni a listában, mert a lista ugyanarra az elemre fog többszörös hivatkozást tartalmazni. Ehelyett a c-nek megfelelő számú másolatát készítjük el a cc tömbben, és mindegyik másolatot külön-külön kezelve tároljuk.

Evolúció - absztrakt módszer

package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
import java.util.Collections;
/**
 * (MU,LAMBDA) evolúciós algoritmus
 * @author ASZALÓS László
 */
public abstract class Evolution extends SolvingMethod<StateR> {

A két bemutatott módszer mindegyikében MU szülőnek mutáció segítségével LAMBDA gyereket lesz.

protected int MU;
protected int LAMBDA;

A mutáció mértékét (mennyire különbözik a gyerek a szülőtől) mi adjuk meg:

protected float MUTATE;

Mi döntünk arról is, hogy hány lépés után ér véget a módszer:

protected int MAX_STEPS;

Ezeket a paramétereket a szokott módon olvassuk be:

@Override
public void constants(String name, int numerator, int denominator) {
    if (name.equals("MU")) {
        MU = numerator;
    }
    if (name.equals("MAX_STEPS")) {
        MAX_STEPS = numerator;
    }
    if (name.equals("LAMBDA")) {
        LAMBDA = numerator;
    }
    if (name.equals("MUTATE")) {
        MUTATE = (float) numerator / denominator;
    }
}

A programban tárolni kell a szülőket és a gyerekeket. A korábban alkalmazott tömbök helyett most erre listákat fogunk használni:

protected ArrayList<StateR> xs, ys;

Eme listák kezelésének metódusait külön osztályba szerveztük:

protected EvolutionaryTools e;

Két kérdést hagyunk nyitva (és bízzuk a leszármazott osztályokra), egyrészt a szülők jövőjét, másrészt mekkora listákkal dolgozzunk?

/**
 * Mi legyen a szülőkkel miután elkészült az összes leszármazott?
 * @param ys leszármazottak listája
 * @param xs szülő
 */
protected abstract void handleParent(ArrayList<StateR> ys, StateR x);

/**
 * Beállítjuk a listák méreteit
 * @param xs mintának szánt adat.
 */
protected abstract void setupQueues();

A megoldásban az átadott aktuális állapot alapján feltöltjük a listákat, majd az első szülők a gyerekek listájában kapnak helyet. A fillFirst metódus rendezett listával tér vissza:

protected void evolve(StateR x) {
    StateR p;
    setupQueues();
    e.fillFirst(ys, LAMBDA, x);

Ezután elindul egy előírt lépésszámú ciklus, melyben először az előző korszak legjobb gyerekeit helyet kapnak a következő korszak legjobb felnőttjei között. A többi gyerekre ezután nem lesz szükség:

for (int i = 0; i < MAX_STEPS; i++) {
    //átmásoljuk a MU legjobbat
    for (int j = 0; j < MU; j++) {
        xs.add(ys.get(0));
        ys.remove(0);
    }
    ys.clear();

Majd minden egyes szülő esetén elkészítjük a gyerekeit, ezzel együtt a szülő kikerül a szülői listából. Az kérdés, hogy bekerül-e a következő generációba, vagy sem. Végül az új generációt rendezzük:

for (int j = 0; j < MU; j++) {
    p = xs.get(0);
    xs.remove(0); 
    e.generateChildren(p, ys, LAMBDA / MU, MUTATE);
    handleParent(ys, p); 
}
Collections.sort(ys); 
} }

Az előző metódus szinte mindent megcsinált. Egy dolgunk van csak, hogy az utolsó generáció legjobb elemét visszaadjuk:

@Override
public StateR solve(StateR x) {
    evolve(x);
    return ys.get(0);
}}

Segédosztály evolúcióhoz

package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
import java.util.Collections;

/**
 * Segédosztály az evolúciós módszerekhez.
 * @author ASZALÓS László
 */
public class EvolutionaryTools {

Kezdetben a szülők listája is üres, ezt valahogy fel kell tölteni. A paraméterként átadott x lesz a minta, erről készítünk másolatokat, hogy az abban szereplő mellékelt adatszerkezeteket átvegyük, majd következik a kezdeti aktuális állapot véletlen megválasztása, amit a célfüggvényérték meghatározása követ. Végül ezen értékek alapján rendezzük a listát.

/**
 * Létrehozzuk az első generációt tartalmazó listát.
 * @param xs szülők listája
 * @param size szülőlista mérete
 * @param x aktuális állapot
 */
void fillFirst(ArrayList<StateR> xs, int size, StateR x){
    StateR h[] = new StateR[size];
    for (int j = 0; j < size; j++) {
        h[j]= (StateR) x.copy();
        h[j].fillRandom();
        h[j].calculate();
        xs.add(h[j]);
    }
    Collections.sort(xs);
}

A szülő gyerekeinek elkészítése viszonylag egyszerű. Kell venni a szülő másolatát, azt az adott mértékig mutálni, és érdemes ennek az új egyednek kiszámítani a függvényértékét. Ezután már nincs más teendő, mint az így elkészült állapotot a gyerekek közé felvenni:

/**
 * Generáljuk a kiválasztott szülő gyerekeit.
 * és a megadott listában tároljuk.
 * @param p a szülő, melynek gyerekeit generáljuk
 * @param n gyerekek száma
 * @param ys gyerekek listája
 */
void generateChildren(StateR p, ArrayList<StateR> ys,
  int n, float r){
    StateR h[] = new StateR[n];
            //TODO: a lista régi elemeit újrafelhasználni
    for (int i = 0; i < n; i++) {
      h[i] = (StateR) p.copy();
      h[i].mutate(r);
      h[i].calculate();
      ys.add(h[i]);
    }
}}

(μ,λ) változat

Két kérdés nyitva maradt. Az egyik válasz az lehet, hogy nincs szükség a vénekre:

package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
/**
 * A szülő eltűnik, jönnön az új korosztály
 * @author Aszalós László
 */
public class EvolutionC extends Evolution {

Ekkor a szülőről egy az egyben elfelejtkezünk:

protected void handleParent(ArrayList<StateR> ys, StateR p) {
}

Ennek megfelelően a méretek a következőek lesznek: MU szülőknek és LAMBDA a gyerekeknek.

protected void setupQueues() {
    xs = new ArrayList<StateR>(MU);
    ys = new ArrayList<StateR>(LAMBDA);
    e = new EvolutionaryTools();
}}

(μ+λ) változat

A másik fajta válasz jóval liberálisabb: győzzön a jobbik:

package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
/**
 * A szülő is bekerül a gyerekek közé, a jobb marad életben.
 * @author ASZALÓS László
 */
public class EvolutionP extends Evolution {

Ebben az esetben a szülő is bekerül a gyerekek listájába:

protected void handleParent(ArrayList<StateR> ys, StateR p) {
    ys.add(p);
}

Mivel többen vannak a gyerekek listájában, így azt nagyobbra is kell méretezni:

protected void setupQueues() {
    xs = new ArrayList<StateR>(MU);
    ys = new ArrayList<StateR>(LAMBDA+MU);
    e = new EvolutionaryTools();
}}

Speciális evolúció változat

Az első változatnál a második jobban teljesített a kísérletek alapján, tehát jó az öreg a háznál! Viszont az evolúciós módszer nem veszi figyelembe azt, ha egymástól függetlenül két jó tulajdonság is kifejlődik. Ezek kombinálására vállalkozunk ezzel az új módszerrel:

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
/**
 * Evolúciós módszerrel kapott eredmények kombinálása
 * @author ASZALÓS László
 */
public class EvolutionPP extends EvolutionP {

Paraméterként tekintünk egy számot, mely megadja, hogy hányszor próbáljuk egymáshoz közelíteni az egyes egyedeket:

private int N; 

Ennek beolvasása a szokott módon megy:

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

A megoldás keresésének első fázisa az, amit eddig is használtunk. Utána viszont következik egy másik fázis. Ebben az egyedeket kezdjük egymáshoz közelíteni.

Ehhez a listát vektorrá alakítjuk. Majd egy dupla ciklusban a rosszabban teljesítő egyedeket a jobbak irányába mozdítjuk el. Ha ennek eredményeképp megjavul valamely egyed, akkor annak azonnal lesz hatása, mert ezt a vektort rendezzük.

Végül e vektor első, azaz legjobb elemét adjuk vissza:

@Override
public StateR solve(StateR x) {
    evolve(x);
    StateRC[] a = ys.toArray(new StateRC[ys.size()]);
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < a.length; j++) {
            a[j].nearTo(a[j/2]);
        }
        Arrays.sort(a); 
    }
    return a[0];        
}}

Feladatok

  1. Implementálja az evolúciós algoritmust kupacok segítségével!

    Tipp: A szülők listájának kialakításakor hajtsa végre a kupacrendezés kezdő lépéseit! A gyerekek generálásakor kezelje a kupacot egy egyszerű tömbként, és csak a teljes adatszerkezet elkészültekor alakítsa kupaccá! Törekedjen a hatékony implementációra, igyekezzen újrahasznosítani a változók számára lefoglalt területeket!

  2. Implementálja az evolúciós algoritmust úgy, hogy ne kelljen az állapotokat rendezni!

  3. Implementálja az evolúciós algoritmust úgy, hogy a kiinduló generációban helyet kapjon az átadott elem! (Így egy korábbi keresési algoritmus végeredményét lehet tovább finomítani evolúció segítségével.)

  4. A javításban használt tömböt is kezelje kupacként! Hasonlítsa össze a futási időket!