Skip to content

Latest commit

 

History

History
154 lines (105 loc) · 4.73 KB

ea1-intro.md

File metadata and controls

154 lines (105 loc) · 4.73 KB
Raw
archetype title linkTitle author readings tldr outcomes assignments youtube fhmedia
lecture-cg
Einführung Evolutionäre Algorithmen
Intro EA/GA
Carsten Gips (HSBI)
key comment
Russell2020
GA: Abschnitt 4.1.4
key comment
Schwefel1995
Originalarbeit zu Evolutionsstrategien
key
Michalewicz1996
key
Baeck1996
key
Nissen1997
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.
k2
Problematik der lokalen Minima bei Gradientenverfahren
k2
Überblick über die verschiedenen Strömungen
k2
Prinzipieller Ablauf von Genetischen Algorithmen
topic
sheet-ea
link name
VL Einführung Evolutionäre Algorithmen

Evolution sehr erfolgreich bei Anpassung

{width="60%"}

[Quelle: Photo by Johannes Plenio on Unsplash.com (Unsplash License)]{.origin}

\bigskip \bigskip

::: cbox [Wie funktioniert's?]{.alert} :::

[[kurze Diskussion]{.bsp}]{.slides}

EA -- Zutaten und Mechanismen

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

\bigskip

  • Mechanismen ("Operatoren"):
    • Selektion
    • Rekombination (Crossover)
    • Mutation

EA -- Allgemeiner Ablauf

{width="80%"}

EA -- Beispiel

{width="40%"}

::: notes 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). :::

[[Beispiel mit 4-Queens-Puzzle]{.bsp}]{.slides}

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

\smallskip

  1. 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$

\smallskip

  1. Evolutionäre Programmierung (EP)

::: notes 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!

\bigskip

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

::: slides

LICENSE

Unless otherwise noted, this work is licensed under CC BY-SA 4.0.

Exceptions