Was ist ein genetischer Algorithmus?
Der genetische Algorithmus ist eine Methode zur Lösung von Optimierungsproblemen mit und ohne Nebenbedingungen, die auf der natürlichen Selektion basiert, dem Prozess, der die biologische Evolution antreibt. Der genetische Algorithmus modifiziert wiederholt eine Population individueller Lösungen. Bei jedem Schritt wählt der genetische Algorithmus Individuen aus der aktuellen Population als Eltern aus und nutzt diese, um die Kinder für die nächste Generation zu erzeugen. Über Generationen hinweg "entwickelt" sich die Population hin zu einer optimalen Lösung. Sie können den genetischen Algorithmus anwenden, um eine Vielzahl von Optimierungsproblemen zu lösen, die für Standardoptimierungsalgorithmen nicht gut geeignet sind, einschließlich Probleme, bei denen die Zielfunktion unstetig, nicht differenzierbar, stochastisch oder stark nichtlinear ist. Der genetische Algorithmus kann Probleme der gemischt-ganzzahligen Programmierung lösen, bei denen einige Komponenten auf ganzzahlige Werte beschränkt sind.
Dieses Flussdiagramm veranschaulicht die wichtigsten algorithmischen Schritte. Für Details siehe So funktioniert der genetische Algorithmus.
Der genetische Algorithmus verwendet in jedem Schritt drei Haupttypen von Regeln, um die nächste Generation aus der aktuellen Population zu erzeugen:
Selektionsregeln wählen die Individuen aus, die als Eltern bezeichnet werden und zur Population der nächsten Generation beitragen. Die Auswahl erfolgt im Allgemeinen stochastisch und kann von den individuellen Punktzahlen abhängen.
Kreuzungsregeln verbinden zwei Eltern, um Kinder für die nächste Generation zu erzeugen.
Mutationsregeln wenden zufällige Veränderungen an einzelnen Eltern an, um Nachkommen zu erzeugen.
Der genetische Algorithmus unterscheidet sich von einem klassischen, auf Ableitungen basierenden Optimierungsalgorithmus in zwei wesentlichen Punkten, die in der folgenden Tabelle zusammengefasst sind:
| Klassischer Algorithmus | Genetischer Algorithmus |
|---|---|
Erzeugt in jeder Iteration einen einzelnen Punkt. Die Folge der Punkte nähert sich einer optimalen Lösung an. | Erzeugt in jeder Iteration eine Population von Punkten. Der beste Punkt in der Population nähert sich einer optimalen Lösung an. |
Wählt den nächsten Punkt in der Sequenz durch eine deterministische Berechnung aus. | Wählt die nächste Population durch Berechnung mithilfe von Zufallszahlengeneratoren aus. |
Konvergiert typischerweise schnell zu einer lokalen Lösung. | Typischerweise sind viele Funktionsauswertungen erforderlich, um zu konvergieren. Kann gegen ein lokales oder globales Minimum konvergieren, muss aber nicht. |
