Genetikus algoritmus

A genetikus algoritmus a fejezetben később ismertetett algoritmusokhoz képest nagyon réginek tűnik. Viszont az élet sok területén még mindig jól üzemel. Az elmúlt évek során igen sok különféle variánsa alakult ki az algoritmusnak, nem szándékunk bemutatni az összest, csupán kettőt választottunk ki.

4.2. ábra - Genetikus módszerek áttekintő osztálydiagramja

Genetikus módszerek áttekintő osztálydiagramja

Ám mielőtt ezekre rátérnék nézzük meg a közös részeket!

Absztrakt genetikus algoritmus

4.3. ábra - Genetikus algoritmusok közös része

Genetikus algoritmusok közös része

A genetikus algoritmus különböző variánsainak közös részét egy absztrakt osztályba foglaltuk össze:

/*FFIGURE Genetic*/
package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
import java.util.Random;
/**
 * Genetikus algoritmusok, közös rész
 * @author ASZALÓS László
 */
public abstract class Genetic extends SolvingMethod<StateRC> {

Maga a módszer igen sok paraméteren alapul. Első ezek közül a populáció mérete:

protected int POPSIZE;

A keresztezés mellett a mutációt is használnunk kell. Ehhez tartozó paraméter a mutáció foka:

protected float MUTATE;

További paraméter a generációk száma:

protected int MAX_STEPS;

A keresztezésekben rendszerint a jobb tulajdonságú elemek vesznek részt. Nem választhatjuk automatikusan csak a legjobba(ka)t, mert akkor a változatosság eltűnik a rendszerből. Éppen ezért egy véletlen módon kiválasztott halmaz legjobb elemét tekintjük. Ennek a halmaznak a méretét adja meg a következő paraméter:

protected int TOURNAMENT;

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

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

Szükségünk van pár attribútumra. Első ezek közül a populáció tárolására használt lista:

protected ArrayList<StateRC> p;

A módszer során talált legjobb elemet az alábbi változó tárolja:

protected StateRC xMin;

A keresztezés eredményeképp kapott két gyerek pedig ezekben a változókban tárolódik:

protected StateRC c1,c2;

Miután a módszer alapvető művelete a keresztezés, így az megjelenik a metódusok között. Egyelőre még csak jelöljük, a leszármazott osztályok fogják ezt konkretizálni:

/**
 * Keresztezzük a két szülőt.
 * @param x egyik szülő
 * @param y másik szülő
 */
protected abstract void crossover(StateRC x, StateRC y);

A popolációt kezdetben véletlen állapotokkal töltjük fel. Ezek közül a legjobbat már egyből el is tároljuk az xMin változóban. Hogy ne ugyanazon elemre hivatkozzon a populáció minden eleme, egy ugyanekkora vektort generálunk, melyből átmásoljuk a listába az egyes állapotokat:

/**
 * A <i>p</i> listát feltöltjük véletlen adatokkal
 * @param x másolandó elem
 * @param size lista mérete
 */
protected void fillList(StateRC x, int size) {
    // véletlen kezdőelemekkel feltölteni.
    StateRC c[] = new StateRC[size];
    xMin = (StateRC) x.copy();
    xMin.calculate();
    for (int i = 0; i < size; i++) {
        c[i] = (StateRC) x.copy();
        c[i].fillRandom();
        c[i].calculate();
        if (c[i].getValue() < xMin.getValue()) {
            xMin = (StateRC) c[i].copy();
        }
        p.add(c[i]);
    }
}

A keresztezéshez nem egy véletlen elemet és nem is a legjobbat választjuk ki. Hanem a paraméter által meghatározott méretű halmazból tekintjük a legjobbat. Ezt úgy valósítjuk meg, hogy egy véletlen elemet hasonlítunk össze megfelelő számú elemmel, és mindig a legjobbal dolgozunk tovább:

/**
* Megadott lépéshatárig keresünk egyre jobb és jobb elemet.
* @return kiválasztott elem indexe
*/
protected int tournamentSelect() {
    Random r = new Random();
    int best = r.nextInt(POPSIZE);
    int bestV = p.get(best).getValue();
    for (int i = 1; i < TOURNAMENT; i++) {
        int j = r.nextInt(POPSIZE);
        int jV = p.get(j).getValue();
        if (jV < bestV) {
            best = j;
            bestV = jV;
        }
    }
    return best;
}

A keresztezéshez első lépésben ki kell választani a két szülőt. Erre az előbb ismertetett metódus használandó. Majd keresztezzük a két elemet. Miután a keresztezés során az eredeti elemet felülírjuk, így a két szülőről elsőként másolatot készítünk, és valójában eme másolatokat keresztezzük. A keresztezés után kapott elemeket mutáljuk, hogy nagyobb legyen a változatosság, majd kiszámítjuk az egyes függvényértékeket:

/**
 * Kiválasztunk két viszonylag jó szülőt, és a keresztezett majd mutált
 * leszármazottak a <i>c1</i> és a <i>c2</i> változókban találhatóak. */
protected void selectParents() {
    int a,b;
    // két szülő
    a = tournamentSelect();
    b = tournamentSelect();
    c1 = (StateRC) p.get(a).copy();
    c2 = (StateRC) p.get(b).copy();
    crossover(c1,c2);
    c1.mutate(MUTATE);
    c1.calculate();
    c2.mutate(MUTATE);
    c2.calculate();
}}

Elitista megközelítés

A genetikus algoritmusnak több megközelítése van. Az elsőben nagy számú leszármazottat generálunk, amelyek az evolúciós módszerhez hasonlóan versenyeznek az előző generációval a továbbélésért:

package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
/**
 * A gyerekek és az öregek versenyeznek egymással.
 * @author Aszalós László
 */
public abstract class GeneticElitism extends Genetic {

Új paraméter a továbbélő szülők száma:

protected int N;

Amit a megszokott módon kell beolvasni:

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

A populáció (a régi generáció) mellett az új generációt is tárolni kell:

protected ArrayList<StateRC>  q;

Az előző és az új generáció is azonos méretű lesz. Az ezeket tároló listák méretét az alábbi metódus állítja be, és ez gondoskodik a kezdeti populáció generálásáról is:

/**
 * Beállítjuk a listák méreteit
 * @param x mintának szánt adat.
 */
protected void setupLists(StateRC x) {
    p = new ArrayList<StateRC>(POPSIZE);
    q = new ArrayList<StateRC>(POPSIZE);
    fillList(x, POPSIZE);
}

A megoldás keresése során elsőként az adatszerkezeteket kell beállítani, majd ezt követően indul egy ciklus, ahol a ciklusmag egy új generációt állít elő:

@Override
public StateRC solve(StateRC x) {
    Random r = new Random();
    setupLists(x);
    for (int i = 0; i < MAX_STEPS; i++) {

Az előző generációból csak az N legjobbat mentjük át:

Collections.sort(p); //TODO: kupac használata
for (int j = 0; j < N; j++) {
    StateRC c = p.get(j);
    q.add(c);
}

A megmaradt helyeket a régi generáció alapján keresztezett új elemekkel töltjük fel:

for (int j = N; j < POPSIZE; j+=2) {
    selectParents();
    q.add(c1);
    q.add(c2);
}

Miután az új generáció elkészült, már ez tekinthető a réginek:

p.clear(); //TODO: munkatakarékos megvalósítás
p = (ArrayList)q.clone();
q.clear();
}

Az utolsó generáció elkészültekor kiválasztjuk a legjobb elemét:

Collections.sort(p);
return p.get(0);
}}

Konkrét megvalósítások

4.4. ábra - Elitista genetikus algoritmusok osztálydiagramja

Elitista genetikus algoritmusok osztálydiagramja

Elitista genetikus - egypontos keresztezés

package hu.unideb.inf.optimization.methods;
/**
 * Egypontos keresztezés
 * @author ASZALÓS László
 */
public class GEOne extends GeneticElitism {

    @Override
    protected void crossover(StateRC x, StateRC y) {
        x.crossoverOnePoint(y);
    }
}

Elitista genetikus - kétpontos keresztezés

package hu.unideb.inf.optimization.methods;
/**
 * Kétpontos keresztezés
 * @author ASZALÓS László
 */
public class GETwo extends GeneticElitism {

    @Override
    protected void crossover(StateRC x, StateRC y) {
        x.crossoverTwoPoint(y);
    }
}

Elitista genetikus - uniform keresztezés

package hu.unideb.inf.optimization.methods;
/**
 * Uniform keresztezés
 * @author ASZALÓS László
 */
public class GEUni extends GeneticElitism {

    @Override
    protected void crossover(StateRC x, StateRC y) {
        x.crossoverUniform(y, MUTATE);
    }
}

Stabil megközelítés

A genetikus algoritmus másik megközelítése szerint a populáció egy lépésben alig változik, a gyerekek a populációból kiesettek helyét foglalják el.

package hu.unideb.inf.optimization.methods;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
/**
 * Az új egyedek egyből elfoglalják az öregek helyét.
 * @author Aszalós László
 */
public abstract class GeneticSteady extends Genetic {

Az új egyedek számára helyet kell biztosítani, tehát kell egy módszer, hogyan lehet kiválasztani a halálra ítélteket. Itt most erről nincs konkrét döntés, az majd a leszármazott osztályra hárul.

/**
 * Valamilyen úton-módon kinyírunk két öreget.
 */
protected abstract void deleteOlds();

Mivel csak egy populációnk van, ezt kell alapállapotba hozni:

/**
  * Beállítjuk a lista méretét
  * @param x mintának szánt adat.
  */
 protected void setupLists(StateRC x) {
     p = new ArrayList<StateRC>(POPSIZE);
     fillList(x, POPSIZE);
 }

Az elitista megközelítéshez hasonlóan a kezdeti beállítások után egy ciklusban megkonstruáljuk az összes generációt. Viszont a ciklusmag már jóval egyszerűbb, mint volt korábban. Elegendő kiválasztani a két szülőt és elvégezni a kereszteződést, majd helyet csinálni a két új elemnek, és azokat elhelyezni:

@Override
public StateRC solve(StateRC d) {
    Random r = new Random();
    setupLists(d);
    for (int i = 0; i < MAX_STEPS; i++) {
        selectParents();
        deleteOlds();
        p.add(c1);
        p.add(c2);
    }

A legjobb elemet hasonlóan kaphatjuk meg, mint korábban:

Collections.sort(p);
return p.get(0);
}}

Üresedés

Hogyan lehet eldönteni, hogy melyik elemek hagyják el a populációt? A legegyszerűbb módszer választottuk: döntsön a véletlen!

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Legegyszerűbben két véletlen választott elem tűnik el. 
 * @author Aszalós László
 */
public abstract class GeneticSR extends GeneticSteady{
    @Override
    protected void deleteOlds() {
        Random r = new Random();
        p.remove(r.nextInt(p.size()));
        p.remove(r.nextInt(p.size()));
    }
}

Konkrét megvalósítások

4.5. ábra - Stabil genetikus algoritmusok osztálydiagramja

Stabil genetikus algoritmusok osztálydiagramja

Stabil genetikus - egypontos keresztezés

package hu.unideb.inf.optimization.methods;
/**
 * Egypontos keresztezés
 * @author Aszalós László
 */
public class GSOneR extends GeneticSR {
    @Override
    protected void crossover(StateRC x, StateRC y) {
        x.crossoverOnePoint(y);
    }
}

Stabil genetikus - kétpontos keresztezés

package hu.unideb.inf.optimization.methods;
/**
 * Kétpontos keresztezés
 * @author ASZALÓS László
 */
public class GSTwoR extends GeneticSR {
    @Override
    protected void crossover(StateRC x, StateRC y) {
        x.crossoverTwoPoint(y);
    }
}

Stabil genetikus - uniform keresztezés

package hu.unideb.inf.optimization.methods;
/**
 * Uniform keresztezés
 * @author Aszalós László
 */
public class GSUniR extends GeneticSR {
    @Override
    protected void crossover(StateRC x, StateRC y) {
        x.crossoverUniform(y, MUTATE);
    }
}

Stabil genetikus - javítás

Az előzőekben bemutattuk, hogyan javítható az evolúciós módszer. Most ugyanezt a módszert alkalmazzuk a genetikus algoritmus esetén is, ezért a program nagy rész már ismerős lesz:

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
/**
 * Keresztezés javítása
 * @author ASZALÓS László
 */
public class GeneticSRP extends GeneticSR {

A javításnak van egy paramétere, amely azt adja meg, hogy hányszor kívánjuk közelíteni egymáshoz a populáció elemeit:

private int NI;

Ezt a paramétert is a szokott módon olvassuk be:

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

A három különböző keresztezésből a kétpontost választottuk a kísérleteink alapján:

@Override
protected void crossover(StateRC x, StateRC y) {
    x.crossoverTwoPoint(y);
}

A megoldás metódusa úgy kezdődik mint korábban:

@Override
public StateRC solve(StateRC x) {
    setupLists(x);
    for (int i = 0; i < MAX_STEPS; i++) {
            selectParents();
            deleteOlds();
            p.add(c1);
            p.add(c2);
    }

Itt kezdődik a korábbi javításhoz kísértetiesen hasonló változtatás:

StateRC[] a = p.toArray(new StateRC[p.size()]);
for (int i = 0; i < NI; i++) {
    for (int j = 1; j < a.length; j++) {
        a[j].nearTo(a[j/2]);
    }
    Arrays.sort(a);
}
return a[0];
}}

Feladatok

  1. Implementáljon más szülő kiválasztási módszert! Tipp: használja a [Deepa07] illetve [Sean09] könyvben leírt módszereket!

  2. Implementáljon további keresztezési módszereket!

  3. Az elitista módszert implementálja rendezés nélkül! (Tipp: használjon kupacokat!)

  4. Az elitista módszernél két listát is használunk, egyet a régi, egyet az új generáció tárolására. Aztán az új generációt áthelyezzük a régibe. Implementálja úgy a módszert, hogy a két lista által betöltött szerepek cserélődjenek fel minden lépésben!

  5. A stabil állapotok esetén adjon meg és implementáljon további módszereket az elemek törlésére!

  6. Hasonlítsa össze az előbbi feladat elkészítése során nyert program hatékonyságát az itt ismertetettel!

  7. Használjok a listák helyett egyszerű vektorokat, és a a költséges new helyett hasznosítsa újra a törlendő elemeket!

  8. Implementálja mutációra a [Sean09] 26. algoritmusát, és tesztelje a program hatékonyságát!

  9. Stabil generikus algoritmusnál a halál ne véletlen módon jöjjön, hanem minden lépésben a legrosszabbak pusztuljanak el! Tesztelje ennek a programnak hatékonyságát az eredetihez képest!