Zur Zeit beschäftige ich mich intensiv mit einer äußerst spannenden Klasse von Optimierungsverfahren, den sog. Genetischen Algorithmen.
Genetische Algorithmen (kurz: GA) sind Optimierungsverfahren, die durch die Theorien von Charles Darwin und die Prinzipien der Evolution inspiriert sind. Dabei werden die Prozesse der natürlichen Selektion und Reproduktion von Individuen in Populationen im Computer simuliert, um optimale oder zumindest sehr gute Lösungen für Such- und Optimierungsprobleme zu finden. Genetische Algorithmen werden auch naturanaloge Optimierungsverfahren bezeichnet, da ihre grundsätzliche Funktionsweise von biologischen Vorbildern inspiriert sind. Die wesentlichen Konzepte Genetischer Algorithmen werde ich nachfolgend kurz dargelegt.
- Chromosom (chromosome):
Jedes Individuum bzw. jeder potentielle Lösungskandidat wird durch eine Sammlung von Genen (Chromosom), wie beispielsweise eine Folge von Bits (1011) oder nummerischen Werten, repräsentiert. Durch die Kreuzung zweier Individuen werden diese Gene gemischt und an die Nachkommen weitergegeben.
- Population (population):
Im Rahmen des Optimierungsprozesses gibt es zu jedem Zeitpunkt eine Population von Individuen, welche die aktuelle Generation darstellen. So kann beispielsweise eine Sammlung von Individuen, die jeweils durch eine Folge von Bits dargestellt werden, eine Generation zum Zeitpunkt t repräsentieren (1111, 0100, 0011, … , 1011). Durch Evolution wird diese Generation dann durch eine neue Generation ersetzt.
- Fitnessfunktion (fitness function):
Jedes Individuum in der aktuellen Generation wird im Rahmen des Optimierungsprozesses mit Hilfe der sog. Fitnessfunktion bewertet. Sie ist die Zielfunktion, die es gilt zu optimieren und dessen Wert darüber Auskunft gibt, wie gut ein Individuum die Lösung für das zu lösende Problem darstellt. Die Fitnessfunktion beschreibt somit den Kern des Optimierungsproblems. Individuen, die einen höheren Fitnesswert aufweisen und somit bessere Lösungskandidaten darstellen, besitzen eine höhere Wahrscheinlichkeit für die Auswahl zur Fortpflanzung und die Repräsentation in der nachfolgenden Generation.
- Selektion (selection):
Nach Ermittlung der Fitnesswerte aller Individuen einer Generation findet der Selektionsprozess statt, in dem die jeweiligen Individuen für die Fortpflanzung ausgewählt werden. Hierzu gibt es eine ganze Reihe unterschiedlicher Methoden. Allen ist jedoch gemein, dass Individuen mit einem höheren Fitnesswert auch eine höhere Wahrscheinlichkeit aufweisen, für die Fortpflanzung ausgewählt zu werden und ihre Eigenschaften an die nächste Generation weiterzugeben.
- Kreuzung (crossover):
Um zwei neue Individuen für die nachfolgende Generation zu erzeugen, werden Teile der Chromosome zweier im Rahmen der Selektion ausgewählter Individuen ausgetauscht bzw. gemischt. Dieser Prozess wird Kreuzung (crossover) oder Rekombination (recombination) genannt. Auch hierfür gibt es eine ganze Reihe von Methoden, die je nach Modell und Problemstellung angewendet werden können.
- Mutation (mutation):
Wie im natürlichen Evolutionsprozess auch, besteht im Rahmen von Genetischen Algorithmen die Möglichkeit zufälliger Mutationen, wie z.B. durch das zufällige Flippen eines Bits in den Chromosomen (1011→1010). Ziel dabei ist, eine neue Generation zufällig mit neuen Mustern in den Chromosomen zu bereichern, um somit die Diversität zu steigern und unbekannte Bereiche im Lösungsraum finden zu können. Mutationen sind wahrscheinlichkeitsbasiert und werden üblicherweise mit einer geringen Wahrscheinlichkeit versehen, um den Optimierungsprozess nicht in eine Zufallssuche zu verwandeln.
Durch die wiederholte Anwendung von Selektion, Kreuzung, Mutation und der Bildung neuer Generationen im Rahmen des evolutionären Prozesses, nähert sich der Algorithmus Generation für Generation sukzessiv einer optimalen Lösung. Das Ergebnis am Ende der Optimierung stellt das Individuum, repräsentiert durch sein Chromosom, mit dem höchsten Fitnesswert dar.
Gegenüber traditionellen Optimierungsverfahren besitzen Genetische Algorithmen eine Reihe von Vorteilen. So besteht bei vielen traditionellen Optimierungsverfahren, insbesondere bei gradienten-basierten Verfahren, das Risiko, lediglich lokale Minima oder Maxima zu finden.
Genetische Algorithmen sind diesbezüglich weniger anfällig, da sie eine Population von Lösungskandidaten verwenden, welche durch Kreuzung und Mutation eine gewisse Distanz und Diversität aufweisen, so dass die Wahrscheinlichkeit für das Finden des globale Optimums steigt.
Für die Optimierung benötigen Genetische Algorithmen lediglich den Wert der Fitnessfunktion eines jeden Individuums; weitere Aspekte der Fitnessfunktion sind hierbei nicht relevant. So eigenen sich Genetische Algorithmen für Probleme mit komplexen mathematischen Repräsentationen oder Funktionen, die nicht oder nur sehr schwer differenziert werden können.
Jedoch auch für Probleme, die generell einen Mangel an mathematischer Repräsentation aufweisen, sind Genetische Algorithmen geeignet. Dies kann beispielsweise der Fall sein, wenn der Fitnesswert eines Individuums auf Meinungen oder Beurteilungen basiert, wie bei der Optimierung von Farbkombinationen für eine Website. Für die Anwendung Genetischer Algorithmen muss es lediglich möglich sein, mittels des Ergebnis der Fitnessfunktion zwei Individuen miteinander vergleichen und somit eine Rangfolge bilden zu können.
Genetische Algorithmen eigenen sich aufgrund ihrer Eigenschaften sehr gut für parallele und verteilte Verarbeitung. So können die Fitnesswerte für jedes Individuum unabhängig voneinander und somit gleichzeitig berechnet werden. Auch die Selektions-, Kreuzungs- und Mutations-Operationen können gleichzeitig und unabhängig auf Individuen bzw. Paaren von Individuen angewendet werden. Somit sind Genetische Algorithmen perfekte Kandidaten für die parallele, verteilte und cloud-basierte Verarbeitung.
Neben den genannten Vorteilen, besitzen Genetische Algorithmen auch Eigenschaften, die bei der Optimierung und Modellierung berücksichtigt werden müssen. So ist es für die Anwendung Genetischer Algorithmen erforderlich, eine geeignete Repräsentation des Problems zu erstellen. Dies beinhaltet insbesondere die Definition der Fitnessfunktion, der Struktur der Chromosome sowie der Selektions-, Kreuzungs- und Mutations-Operationen. Dies kann, je nach Problemstellung durchaus recht anspruchsvoll sein.
Ähnlich wie bei der Nutzung von Machine Learning sind auch bei der Anwendung von Genetischen Algorithmen Hyperparameter festzulegen, wie beispielsweise die Populationsgröße oder die Mutations-Rate, für deren Bestimmung es keine festen und exakten Regeln gibt.
Da für jedes Individuum in der Population der Fitnesswert bestimmt werden muss, kann dieser Prozessschritt bei großen Populationen zeit- und rechenintensiv sein. Durch die angesprochene Möglichkeit der verteilten und parallelen Verarbeitung lässt sich diese Eigenschaft jedoch recht gut handhaben. Wie bei fast allen nicht analytischen Optimierungsverfahren kann auch bei Genetischen Algorithmen nicht garantiert werden, dass immer das globale Optimum gefunden wird.
Genetische Algorithmen sind ein spannendes Feld und bieten eine interessante Alternative zu den traditionellen (häufig gradienten-basierten) Optimierungsverfahren.