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)