Durch eine Projekt in meinem Fernstudium habe ich mich sehr intensive mit dem Thema Genetische Algorithmen befasst. Meine Erkenntnisse will ich nun unter anderem in ein paar Blogartikeln festhalten.
Inhaltsverzeichnis
Was sind Genetische Algorithmen
Genetische Algorithmen werden generell dem Bereich der Evolutionäre Algorithmen zugeordnet. Dabei handelt es sich um Optimierungsverfahren die nach dem gleichen System funktionieren wie die Evolution in der Biologie.
Der Bereich der Evolutionären Algorithmen lässt sich grundsätzlich in vier verschiedene Teilbereiche unterteilen:
- Genetischer Algorithmus
- Genetische Programmierung
- Evolutionäre Strategie
- Evolutionäre Programmierung
Genetische Algorithmen wurden erstmals in den frühen 1960er Jahren von John Holland und seinen Kollegen an der University of Michigan eingeführt.
Motivation für Genetische Algorithmen
Im wesentlichen lassen sich drei Gründe für die Verwendung von Genetischen Algorithmen finden:
- Lösung schwieriger Probleme (NP-Schwer)
- Versagen von gradientenbasierten Verfahren
- Schnell eine gute Lösung finden
Grundbegriffe aus der Genetik
Da Genetische Algorithmen an der Natur orientiert sind, ist es nicht weiter verwunderlich das in diesem Zusammenhang gewisse Wörter aus dem Bereich der Genetic stammen.
- Individuen / Chromosom
- Gen
- Allel
- Genotyp
- Phänotyp
- Population / Bevölkerung
Diese Wörter will ich hier kurz etwas erklären.
Individuen / Chromosom:
Ein Individuum wird in der Biologie als ein lebender Organismus beschrieben, dessen Erbinformation in einem Satz von Chromosomen gespeichert ist.Individuum und Chromosom werden im Zusammenhang mit genetischen Algorithmen gleichgesetzt.
Gen:
Als Gen wird eine Stelle oder Sequenz eines Chromosoms bezeichnet.
Allel:
Unter Allele versteht man die mögliche Ausprägung eines Gens, dass sich innerhalb eines Chromosoms an einer bestimmten Stelle befindet.
Genotyp:
Der Genotyp ist der kodierte Vektor der Entscheidungsvariablen.
Phänotyp:
Der Phänotyp hingegen ist der dekodierte Vektor der Entscheidungsvariablen.
Population / Bevölkerung:
Eine Reihe von strukturell ähnlichen Individuen einer bestimmten Gattung wird als Population bezeichnet. Wenn neue Lebewesen dieser Gattung geboren werden oder andere sterben werden, ändern sich zwangsläufig auch die Größenverhältnisse der Bevölkerung. Betrachtet man die Populationen einer Gattung über mehrere Zeiträume hinweg, spricht man von Generationen.
Struktur von genetischen Algorithmen
Wie ein genetischer Algorithmus funktioniert, kann man dem folgenden Workflow Diagramm entnehmen.
Der Ablauf des Algorithmus lässt sich in die folgenden acht Punkte unterteilen.
- Das zu optimierende Problem ist kodiert, d.h. es wird auf ein binär codiertes Chromosom geschrieben.
- Eine Population von Individuen wird erzeugt und zufällig initialisiert. Man spricht hier von der Ausgangspopulation oder Generation 0.
- Jedes Individuum wird mit einer Fitnessfunktion bewertet, die jedem einzelnen Chromosom eine reelle Zahl zuordnet.
- Mittels eines Selektionsverfahren werden zwei Elternteile ausgewählt.
- Aus der genetischen Information der Eltern werden die Nachkommen mit Hilfe eines Kreuzungsverfahrens erzeugt.
- Die Allele der Nachkommen können mutieren, d.h. ihre Werte werden umgekehrt.
- Die neue Generation wird mit den entstandenen Nachkommen ergänzt. Dafür wird ein Ersetzungsverfahren verwendet um die Maximalgröße der Generation nicht zu überschreiten.
- Ab Schritt 3 wiederholen bis ein Abbruchkriterium erfüllt ist.
Wie geht es weiter
Ich habe mir genetische Algorithmen im Kontext eines Projektes für die Spieleentwicklung angeschaut. Dabei habe einige der Verfahren in C# implementiert und eine Sammlung davon auf GitHub gestellt. Dazu ist geplant, noch Artikel zu den folgenden Themen auf diesem Blog zu veröffentlichen:
- Selektionsverfahren
- Rekombinationsverfahren
- Ersetzungsverfahren
- Beispielimplementierung im Kontext der Computerspieleentwicklung
- Wofür können genetische Algorithmen im Kontext der Computerspieleenwicklung verwendet werden
Schreibe einen Kommentar