wiki.neuro.tu-berlin.de

Genetische Algorithmen

Genetische Algorithmen gehören zu der Gruppe der evolutionären Algorithmen und stellen eine Metaheuristik zum Lösen von komplexen Optimierungsproblemen dar. Sie basieren dabei grundlegend auf der iterativen Optimierung über Selektion, Kreuzung und Mutation der stärksten Lösung.[1]

Hintergrund

Der genetische Algorithmus wurde vor allem durch das Buch Adaptation in Natural and Artificial Systems (1975) popularisiert und ist eine Abstraktion der biologischen Evolution auf der Grundlage der natürlichen Selektion.[2] Die Methode basiert somit grundlegend auf genetischen Konzepten. Sie wurde breites auf ein breites Spektrum von Optimierungsproblemen (bspw. Sudoku und Super Mario) angewandt.[3]

Bausteine

Operanden

Die fundamentalen Operanden eines genetischen Algorithmus sind die Population, Chromosome und Gene (siehe Abb. 1). Eine Population besteht aus mehreren Chromosomen. Dabei repräsentiert jedes Chromosom eine Lösung im Suchraum und ist als ein Vektor endlicher Länge von variablen Komponenten (bspw. 0 und 1), auch Gene genannt, kodiert.[4]

Operanden
Abb. 1 Operanden (eigene Darstellung)

Operatoren

Auf den oben genannten Operanden wird mit den Operatoren Selektion, Kreuzung und Mutation gearbeitet.[4:1]

Selektion

Bei der Selektion wird eine fitnessproportionale Auswahl der Chromosome (genehm einer Fitnessfunktion) getroffen, um gute Gene an nachfolgende Generationen (zukünftige Iterationen des Algorithmus) weiterzugeben.

Ein häufiger Ansatz ist hier die elitäre Auswahl, wobei die N Chromosome mit den niedrigsten Fitnessfunktionswerten ausgewählt werden. Die Anzahl N ist dabei frei zu wählen. Die Zielfunktion für die Evaluierung der oben genannten Fitness bzw. Fitnessfunktion soll die individuellen Kriterien der Lösung des vorliegenden Optimierungsproblems in mathematischer Form ausdrücken (siehe Sudoku und Super Mario). Die folgende Gleichung nach Bushra Alhijawi und Arafat Awajan definiert die Fitnessfunktion in der einfachsten Form:

F F_x=\frac{f_x}{\bar{f}}

es gilt

\lambda + \mu Strategie (Anteil von Jan Schäfer)

Die \lambda + \mu Evolutionsstrategie, bedient sich beim Elitismus.

In jeder Generation werden die \mu besten der Population als Elternteil für die nächste Generation festgelegt.
\lambda muss ein Vielfaches von \mu sein. So ergibt sich auch aus \frac{\lambda}{\mu} die Anzahl von Kindern pro Elternteil.[5]

Kreuzung

Bei der Kreuzung werden die Gene mehrerer Chromosomen an bestimmten Kreuzungsstellen ausgetauscht und neue Chromosomen (Nachfolger) entstehen. Für die Auswahl der Kreuzungsstellen selbst gibt es verschiedene Ansätze, darunter vor allem:

Mutation

Durch die Mutationen werden zufällige Gene der Nachfolger geändert, um eine Vielfalt in der Population zu erhalten.[4:2] Auch hier gibt es diverse Ansätze der eigentlichen Implementierung. Zwei häufige sind:

Algorithmus

Bei einem klassischen genetischen Algorithmus muss vorerst eigenständig die Fitnessfunktion definiert werden. Es wird dann mit der (häufig zufallsbasierten) Schaffung einer initialen Population von Chromosomen begonnen.

Für den eigentlichen Evolutionszyklus wird zuerst die Fitness aller Chromosome der aktuellen Population genehm der Fitnessfunktion bewertet. Es erfolgt (bei einer elitären Auswahl) die fitnessproportionale Selektion der N fittesten Chromosome mit den niedrigsten Fitnessfunktionswerten. Nun wird eine neue Population über die Kreuzung von ausgewählten Chromosomen und die darauffolgende Mutation geschaffen (siehe Abb. 2). Darauf folgt das Ersetzen der alten Population mit der neuen.

Operanden
Abb. 2 Operatoren eines vereinfachten genetischen Algorithmus (eigene Darstellung)

Der Evolutionszyklus wird bis zum Erreichen einer ebenfalls eigenständig definierten Abbruchbedingung (bspw. Anzahl Zyklen) wiederholt. Ist diese Bedingung erreicht, wird das fitteste Chromosom der aktuellen Population zurückgegeben.[4:3][3:1]

Pseudocode

create initial population of chromosomes
while not end condition do
	for each chromosome in population
		evaluate fitness 
  select chromosomes with max fitness
  perform crossover
  perform mutation with propability y
  replace old population with new population
select chromosome with max fitness
return chromosome

Bewertung

Herausforderungen

Nachteile sind vor allem die eigenständige Formulierung der Fitnessfunktion, Festlegen der Populationsgröße, sowie die Wahl wichtiger Parameter wie die Mutationswahrscheinlichkeit. Das Festlegen dieser Parameter fällt grundsätzlich unter das Problem der Hyperparameteroptimierung. Dabei ist vor allem die Berechnungszeit und Qualität der Lösung abzuwägen. Im Allgemeinen führen komplexere Strukturen (bspw. eine größere Population) zu einer längeren Berechnungszeit. Diese können zugleich aber auch eine potenziell bessere Lösung hervorbringen, da bei einer größeren Population zum Beispiel auch eine größere Vielfalt innerhalb der Population herrscht und der Suchraum somit breiter erkundet wird.[6]

Möglichkeiten

Ein markanter Vorteil ist die Fähigkeit, mit komplexen Problemen umzugehen. Nach Xin-She Yang basiert dies auf der in hohem Maße anpassbaren Fitnessfunktion, welche das Regelwerk des zugrundeliegenden Optimierungsproblems darstellen soll. Diese kann stationär, nichtstationär, linear, nichtlinear, kontinuierlich oder diskontinuierlich sein.[3:2]

Eine hohe Parallelisierbarkeit ist in vielen Fällen ebenfalls realisierbar. Die verschiedenen Ansätze (bspw. Populationen oder Chromosomen) können sich wie unabhängige Agenten verhalten und den Suchraum der potenziellen Lösungen des jeweiligen Optimierungsproblems in vielen Richtungen gleichzeitig erkunden, so Yang.[3:3]

Möglicherweise stellen evolutionäre Algorithmen im Allgemeinen sogar eine skalierbare Alternative zu Reinforcement Learning dar. Insbesondere sind diese im Vergleich einfacher zu implementieren (u.A. wird keine Backpropagation benötigt), sowie leichter zu skalieren und weisen, aus den oben genannten Gründen, eine höhere Parallelisierbarkeit auf. Dazu gehen evolutionäre Algorithmen besser mit spärlichen Belohnungen (Hinweise auf eine gute Lösung) um.[7]

Referenzen

  1. B. Alhijawi and A. Awajan, “Genetic algorithms: theory, genetic operators, solutions, and applications,” Evolutionary Intelligence, Feb. 2023, doi: https://doi.org/10.1007/s12065-023-00822-6. ↩︎ ↩︎ ↩︎ ↩︎

  2. H. H John, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press, 1975. Accessed: Jan. 31, 2024. Online. Available: https://openlibrary.org/books/OL5070129M/Adaptation_in_natural_and_artificial_systems. ↩︎

  3. X.-S. Yang, “Chapter 6 - Genetic Algorithms,” ScienceDirect, Jan. 01, 2021. https://www.sciencedirect.com/science/article/pii/B9780128219867000135. ↩︎ ↩︎ ↩︎ ↩︎

  4. M. Mitchell, “An introduction to genetic algorithms,” Choice Reviews Online, vol. 34, no. 01, pp. 34-035134-0351, Sep. 1996, doi: https://doi.org/10.5860/choice.34-0351. ↩︎ ↩︎ ↩︎ ↩︎

  5. S. Bojarski and C. B. Congdon, “REALM: A rule-based evolutionary computation agent that learns to play Mario | IEEE Conference Publication | IEEE Xplore,” ieeexplore.ieee.org. https://ieeexplore.ieee.org/abstract/document/5593367. ↩︎

  6. S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimedia Tools and Applications, vol. 80, no. 5, Oct. 2020, doi: https://doi.org/10.1007/s11042-020-10139-6. ↩︎

  7. T. Salimans, J. Ho, X. Chen, S. Sidor, and I. Sutskever, “Evolution Strategies as a Scalable Alternative to Reinforcement Learning,” arXiv:1703.03864 cs, stat, Sep. 2017, Available: https://arxiv.org/abs/1703.03864. ↩︎