Einführung Evolutionäre Algorithmen

TL;DR

Lokale Suchverfahren: Nur das Ergebnis zählt!

Evolutionäre Algorithmen sind lokale Suchverfahren, wobei gleichzeitig an mehreren Stellen im Problemraum gesucht wird. Sie bedienen sich Mechanismen aus der Evolution: Es gibt eine Population von Individuen, die jedes das Problem kodieren ("vollständige Zustandsbeschreibung") und damit im Laufe der Suche zu einer möglichen Lösung werden können.

Videos (HSBI-Medienportal)
Lernziele
  • (K2) Problematik der lokalen Minima bei Gradientenverfahren
  • (K2) Überblick über die verschiedenen Strömungen
  • (K2) Prinzipieller Ablauf von Genetischen Algorithmen

Evolution sehr erfolgreich bei Anpassung

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

Wie funktioniert's?

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)
Übungsblätter/Aufgaben
Quellen
  • [Baeck1996] Evolutionary Algorithms in Theory and Praxis
    Bäck, T., Oxford University Press, 1996. ISBN 978-0-1950-9971-3.
  • [Michalewicz1996] Genetic Algorithms + Data Structures = Evolution Programs
    Michalewicz, Z., Springer, 1996. ISBN 978-3-5406-0676-5.
  • [Nissen1997] Einführung in Evolutionäre Algorithmen
    Nissen, V., Vieweg+Teubner Verlag, 1997. ISBN 978-3-5280-5499-1.
  • [Russell2020] Artificial Intelligence: A Modern Approach
    Russell, S. und Norvig, P., Pearson, 2020. ISBN 978-0134610993.
    GA: Abschnitt 4.1.4
  • [Schwefel1995] Evolution and Optimum Seeking
    Schwefel, H. P., Wiley, 1995. ISBN 978-0-4715-7148-3.
    Originalarbeit zu Evolutionsstrategien