Modellierung mit Genetischen Algorithmen

EA -- Allgemeiner Ablauf

Kodierung Individuen

• Binäre Lösungsrepräsentation (Bitstring): $\mathbf{g}=(g_1,\dots ,g_m)\in \{0,1{\}}^m$

  • String gliedert sich in $n$ Elemente (mit $n\le m$) => jedes Segment entspricht einer Problemvariablen
  • Dekodierungsfunktion $\mathrm{\Gamma }:\{0,1{\}}^m\to {\mathbb{R}}^n$

  Alle relevanten Aspekte des Problems müssen in die Codierung einfließen!

  Bei ES hat man einen Vektor mit reellen Zahlen, wobei jeder Eintrag einen Parameter des Problems darstellt. Eine Dekodierungsfunktion benötigt man entsprechend nicht.

  Bei der Erzeugung der Startpopulation werden die Individuen zufällig (mit zufälligen Werten) initialisiert.

• Fitnessfunktion $\mathrm{\Phi }$ ordnet jedem Individuum ${\mathbf{g}}_i$ eine reelle Zahl zu: $$\mathrm{\Phi }({\mathbf{g}}_i)=F(\mathrm{\Gamma }({\mathbf{g}}_i))-w\cdot \sum _j(Z_j(\mathrm{\Gamma }({\mathbf{g}}_i)){)}^2$$

  • Zielfunktion $F$: wie sehr genügt ein Individuum bereits dem Optimierungproblem
  • Strafterme $Z_j$: Anreicherung der Optimierung mit weiteren Informationen
  • Gewichte $w$: statisch oder dynamisch (Abkühlen)

  Die Wahl einer guten Fitnessfunktion ist oft eine Herausforderung, aber dennoch wichtig, da damit die Suche gesteuert wird!

Selektion: Erstelle Matingpool mit $\mu$ Individuen

• Fitnessproportionale Selektion (Roulette Wheel Selection): Auswahlwahrscheinlichkeit für Individuum ${\mathbf{g}}_k$: $$p_{sel}({\mathbf{g}}_k)=\frac{\mathrm{\Phi }({\mathbf{g}}_k)}{\sum _j\mathrm{\Phi }({\mathbf{g}}_j)}$$ => Voraussetzung: positive Fitnesswerte

• Turnier-Selektion (Tournament Selection):

  • Turniergröße $\xi$
  • Turnier: ziehe $\xi$ Individuen gleichverteilt (mit Zurücklegen!) und kopiere fittestes Individuum in den Matingpool
  • Führe $\mu$ Turniere durch

Hinweis: Es gibt noch viele weitere Selektionsmechanismen. Die vorgestellten sind in der Praxis am gebräuchlichsten.

Über die Selektion wird der sogenannte "Selektionsdruck" aufgebaut: Wie gut muss ein Individuum sein (im Vergleich zu den restlichen Individuen in der Population), damit es eine Chance zur Reproduktion erhält? Dürfen sich nur die "Guten" fortpflanzen, oder erhalten auch die "Schlechten" eine gewisse Chance?

Da jedes Individuum einen Punkt im Suchraum darstellt, beeinflusst die Wahl der Selektion die Geschwindigkeit der Suche, begünstigt u.U. aber auch ein eventuelles Festfahren in lokalen Minima. Dies kann beispielsweise geschehen, wenn immer nur die "Guten" selektiert werden, aber die "Guten" der Population sich in der Nähe eines lokalen Minimums befinden. Dann werden auch die Nachfolger sich wieder dort aufhalten.

Crossover: Erzeuge zwei Nachkommen aus zwei Eltern

Festlegung der Crossover-Wahrscheinlichkeit $p_{cross}$ (typisch: $p_{cross}\ge 0.6$)

1. Selektiere Eltern ${\mathbf{g}}_a$ und ${\mathbf{g}}_b$ gleichverteilt aus Matingpool

2. Zufallsexperiment:

   • mit $1-p_{cross}$: Kinder identisch zu Eltern (kein Crossover)

   • mit $p_{cross}$: Crossover mit ${\mathbf{g}}_a$ und ${\mathbf{g}}_b$

     • Ziehe $i$ gleichverteilt mit $1<i<m$
     • Kinder aus ${\mathbf{g}}_a$ und ${\mathbf{g}}_b$ zusammenbauen: $${\mathbf{g}}_c=(g_{a,1},\dots ,g_{a,i},g_{b,i+1},\dots ,g_{b,m})$$ und $${\mathbf{g}}_d=(g_{b,1},\dots ,g_{b,i},g_{a,i+1},\dots ,g_{a,m})$$

     => Trenne Eltern an gleicher Stelle auf, vertausche Bestandteile

3. Gehe zu Schritt 1, bis insg. $\mu$ Nachkommen

Anmerkung: Die Eltern werden jeweils in die Ausgangsmenge zurückgelegt.

Mit einer kleinen Wahrscheinlichkeit sind die Kinder also identisch zu den Eltern. Dies ist im Sinne der lokalen Suche wichtig, um bereits erreichte gute Positionen im Suchraum nicht zu verlieren: Es könnte sein, dass die Nachfolger alle schlechter sind ...

Varianten: $N$-Punkt-Crossover, Shuffle-Crossover

Bei ES wird parameterweise gekreuzt. Dabei gibt es verschiedene Möglichkeiten: Übernahme eines Parameters von einem Elternteil, Verrechnen (beispielsweise Mitteln) der Werte beider Eltern, ... Bei ES heißt "Crossover" deshalb oft "Rekombination".

Mutation

• Mutationswahrscheinlichkeit $p_{mut}$ (typische Werte: $p_{mut}=0.01$ oder $p_{mut}=0.001$)

• Für alle Individuen:

  • Mutiere jedes Gen eines Individuums mit $p_{mut}$:

    $$g_i^{(t+1)}=\{\begin{array}{ll}\mathrm{\neg }{g}_i^{(t)}& \text{ falls }{\chi }_i\le p_{mut}\\ \phantom{\mathrm{\neg }}{g}_i^{(t)}& \text{ sonst }\end{array}$$

    =>${\chi }_i$ gleichverteilte Zufallsvariable (Intervall $[0,1]$), für jedes Bit $g_i$ neu bestimmen

Anmerkung: Die optimale Mutationsrate $p_{mut}^{\ast }$ ist von Länge $m$ des Bitstrings abhängig; annäherbar durch $p_{mut}^{\ast }\approx 1/m$.

Die beim Crossover erstellten Nachfolger liegen im Suchraum in der Nähe der Eltern. Durch die Mutationsrate bestimmt man, ob und wie weit sich ein Kind entfernen kann. Dies entspricht dem Bild des "Schüttelns" der Zustandslandschaft.

Bei ES unterscheidet man Mutationswahrscheinlichkeit und Mutationsrate. Es wird parameterweise mutiert.

Bewertungskriterien

Vorsicht: Es handelt sich um Zufallsexperimente. Wenn man nicht nur direkt nach einer Lösung sucht, sondern beispielsweise Parametereinstellungen oder die Wahl der Fitnessfunktion für ein Problem vergleichen will, muss man jeweils mehrere Experimente mit der selben Einstellung machen und Kenngrößen berechnen.

Geschwindigkeit: AES Average Evaluations to a Solution $$\text{AES }=\frac{\sum _{i\in \text{erfolgreiche Läufe}}\text{Generationen von Lauf }i}{\text{Anzahl der erfolgreichen Läufe}}$$

Die AES liegt im Intervall $[0,maxGen]$.

Lösungswahrscheinlichkeit: SR Success Rate $$\text{SR }=\frac{\text{Anzahl der erfolgreichen Läufe}}{\text{Anzahl aller Läufe}}$$

Die SR liegt im Intervall $[0,1]$.

Typische Läufe

• Populationsgröße $\mu =15$
• Anzahl Nachfahren $\lambda =100$
• Abbruch nach $maxGen=200$ Generationen

Stochastischer Algorithmus! Ausreichend Wiederholungen durchführen und mitteln!

Hinweis: Die Parameter müssen problemabhängig gewählt werden. Zu hohe Werte für $\mu$ und $\lambda$ führen dazu, dass man bei kleinen Problemen mit hoher Wahrscheinlichkeit bereits am Anfang eine Lösung "würfelt", also gar kein GA nutzt. Wenn dies allerdings nicht passiert, sorgt eine hohe Populationsgröße dafür, dass jeder Schritt sehr lange dauert. Die Abbruchgrenze ist ebenfalls mit Augenmaß zu wählen: Ein zu kleiner Wert sorgt für zu frühen Abbruch (keine Lösung!), ein zu hoher Wert sorgt beim Festfressen des Algorithmus für eine unnötige weitere "Suche" ...

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Evolutionäre Algorithmen:
  • Begriffe: Individuum, Population, Kodierung
  • Operationen: Selektion, Rekombination, Mutation
  • Bewertung mit Fitnessfunktion