Einführung Evolutionäre Algorithmen

Evolution sehr erfolgreich bei Anpassung

Quelle: Photo by Johannes Plenio on Unsplash.com (Unsplash License)

EA -- Zutaten und Mechanismen

• Zutaten:

  • Individuen: Kodierung möglicher Lösungen
  • Population von Individuen
  • Fitnessfunktion: Bewertung der Angepasstheit

• Mechanismen ("Operatoren"):

  • Selektion
  • Rekombination (Crossover)
  • Mutation

EA -- Allgemeiner Ablauf

EA -- Beispiel

Jedes Individuum kodiert ein Spielfeld mit einer konkreten Anordnung aller Königinnen => Vollständige Zustandsbeschreibung.

Dabei korrespondiert der Index in das Array des Individuums mit der jeweiligen Spalte des Spielfelds. Die Zahl an einer Arrayposition gibt dann an, in welcher Zeile in dieser Spalte eine Königin ist.

Crossover: Die ausgewählten Individuen werden an der selben Stelle aufgetrennt und die Hälften verkreuzt zu zwei neuen Individuen zusammengesetzt. Es entstehen zwei neue Anordnungen der Königinnen (zwei neue Spielfelder).

EA -- Strömungen

1. Genetische Algorithmen (GA)

   • Holland und Goldberg (ab 1960)
   • Binäre Lösungsrepräsentation (Bitstring): $\mathbf{g} = (g_1, \dots, g_m)\in \{ 0,1\}^m$
   • Fitnessbasierte stochastische Selektion
   • $\mu$ Eltern erzeugen $\mu$ Kinder

2. Evolutionsstrategien (ES)

   • Rechenberg und Schwefel (ab 1960)
   • Kodierung reellwertiger Parameter: $\mathbf{g} = (\mathbf{x}, \mathbf{\sigma})$ mit $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n$
   • $\mu$ Eltern erzeugen $\lambda$ Kinder mit $\mu \le \lambda$

3. Evolutionäre Programmierung (EP)

Hinweis: Häufig finden sich Mischformen, beispielsweise GA mit reellwertigen Parametern

Hinweis: Im Folgenden werden Genetische Algorithmen (GA) betrachtet. Sie finden jeweils Hinweise auf die Gestaltung der Operatoren bei ES.

Anwendungsbeispiele für Evolutionäre Algorithmen

• Berechnung und Konstruktion komplexer Bauteile: beispielsweise Tragflächenprofile (Flugzeuge), Brücken oder Fahrzeugteile unter Berücksichtigung bestimmter Nebenbedingungen
• Scheduling-Probleme: Erstellung von Stunden- und Raumplänen oder Fahrplänen
• Berechnung verteilter Netzwerktopologien: Wasserversorgung, Stromversorgung, Mobilfunk
• Layout elektronischer Schaltkreise

Wrap-Up

Lokale Suchverfahren: Nur das Ergebnis zählt!

• Evolutionäre Algorithmen: Unterschied GA und ES (grober Überblick)

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 $\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 $\Phi$ ordnet jedem Individuum $\mathbf{g}_i$ eine reelle Zahl zu: $$\Phi(\mathbf{g}_i) = F(\Gamma(\mathbf{g}_i)) - w\cdot\sum_j(Z_j(\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{\Phi(\mathbf{g}_k)}{\sum_j \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)} = \left\{ \begin{array}{ll} \neg g_i^{(t)} & \mbox{ falls } \chi_i \le p_{mut}\\[5pt] \phantom{\neg} g_i^{(t)} & \mbox{ sonst } \end{array} \right. $$

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

Anmerkung: Die optimale Mutationsrate $p_{mut}^*$ ist von Länge $m$ des Bitstrings abhängig; annäherbar durch $p_{mut}^* \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 $$ \mbox{AES } = \frac{\sum\limits_{i \in \mbox{erfolgreiche Läufe}} \mbox{Generationen von Lauf } i}{\mbox{Anzahl der erfolgreichen Läufe}} $$

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

Lösungswahrscheinlichkeit: SR Success Rate $$ \mbox{SR } = \frac{\mbox{Anzahl der erfolgreichen Läufe}}{\mbox{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