Genetic Algorithm: Ablauf und Anwendungen

Ein Genetic Algorithm – im Deutschen genetischer Algorithmus – ist ein Optimierungsverfahren, das die Mechanismen der natürlichen Selektion nachahmt und darauf abzielt, Populationen potenzieller Lösungen iterativ zu verbessern. Genetische Algorithmen kommen in einer Vielzahl von Anwendungsbereichen zum Einsatz, die von der Optimierung technischer Systeme bis zu maschinellem Lernen reichen.

Was ist unter genetischen Algorithmen zu verstehen?

Bei genetischen Algorithmen beziehungsweise Genetic Algorithms (kurz GAs) handelt es sich um eine globale Heuristik zur Lösung von Entscheidungsproblemen, die auf den Prinzipien der natürlichen Selektion und Genetik basiert. Genetische Algorithmen zählen zu den evolutionären Algorithmen und nutzen Mechanismen, die den Prozessen der natürlichen Auslese nachempfunden wurden, um Lösungen für komplexe Probleme schrittweise zu verbessern. Das bedeutet, es wird ein „Überleben der Stärkeren” simuliert, welches auf folgenden Prämissen beruht:

1. Individuen konkurrieren um Ressourcen und darum, sich zu paaren.
2. Die erfolgreichsten bzw. stärksten Individuen zeugen mehr Nachkommen als andere.
3. Die Gene der „fittesten” Elternteile werden über Generationen hinweg vererbt. Dadurch erzeugen diese des Öfteren Nachkommen, die über vorteilhaftere Gensequenzen verfügen als sie selbst.
4. Da langfristig die besten Gene weitergegeben werden, ist jede Generation besser an ihre Umgebung angepasst als die vorherige.

Genetic Algorithms erzeugen eine Population von Individuen, von denen jedes eine potenzielle Lösung für das gegebene Problem ist. Diejenigen Arten, denen es am besten gelingt, sich an ihre Umgebung anzupassen, überleben und pflanzen sich fort. Die verschiedenen Individuen werden durch sogenannte Chromosomen repräsentiert und in Form von Zeichenketten (Zeichen, Bits, Float oder Integer) dargestellt. Die einzelnen Chromosomen lassen sich wiederum in Gene zerlegen, die ein bestimmtes Merkmal wie die Haarfarbe angeben. Die Ausprägungen eines Gens – in diesem Fall beispielsweise blond, braun oder schwarz – werden als Allele bezeichnet.

Um der optimalen Lösung immer näherzukommen, starten genetische Algorithmen einen mehrstufigen Prozess aus Berechnung und Reproduktion. Die Chromosomen werden über mehrere Generationen beziehungsweise Iterationen durch verschiedene genetische Operatoren – Selektion, Kreuzung (Rekombination) sowie Mutation – verändert und kombiniert, um schrittweise bessere Lösungen zu finden. Das bedeutet, genetische Algorithmen nähern sich über die Kombination guter Teillösungen einer guten globalen Lösung an.

Wie funktionieren Genetic Algorithms?

Der Iterationsprozess unterteilt sich typischerweise in folgende Subroutinen:

1. Das Optimierungsproblem wird kodiert beziehungsweise auf ein binärkodiertes Chromosom abgebildet.
2. Der genetische Algorithmus erzeugt eine Population von Individuen und initialisiert diese zufällig. Die Ausgangspopulation wird auch als Generation 0 bezeichnet.
3. Jedem Individuum wird ein Fitnessscore in Form einer reellen Zahl zugeordnet.
4. Mithilfe einer vordefinierten Selektionsvariante wählt der Genetic Algorithm Eltern aus der Bevölkerung aus.
5. Auf Grundlage der genetischen Informationen beider Elternteile werden Nachkommen erzeugt.
6. Die genetischen Merkmale der Nachkommen (Allele) mutieren möglicherweise, was dazu führt, dass ihre Werte invertiert werden.
7. Die Population wächst um die neu erzeugten Nachkommen. Übersteigt die Populationsgröße das festgesetzte Limit, legt ein Ersetzungsschema fest, welche Individuen fortan nicht mehr Bestandteil der Lösungsmenge sind.
8. Solange kein Abbruchkriterium erfüllt wird, wiederholt der genetische Algorithmus die Schritte 3 bis 7, um sich der optimalen Lösung des Problems immer weiter anzunähern. Das Stoppkriterium lässt sich jedoch sehr unterschiedlich ausgestalten. Manche Algorithmen durchlaufen eine gewisse Anzahl an Generationen, während andere aktiv sind, bis es keine Verbesserung gegenüber der vorherigen Generation mehr gibt.

Fitnessscore

Die Fitness ist ein Synonym für die Anpassungsfähigkeit der einzelnen Individuen. Der Fitnessscore eines Individuums gibt demnach dessen Konkurrenzfähigkeit an. Das Ziel des genetischen Algorithmus besteht darin, die Person mit der idealen (oder fast idealen) Fitness ausfindig zu machen. Die Individuen mit besseren Scores werden mit höherer Wahrscheinlichkeit ausgewählt, um Nachwuchs zu zeugen. Dies führt dazu, dass neue Generationen im Durchschnitt bessere Teillösungen haben als frühere.

Welche Operatoren nutzen Genetic Algorithms?

Genetische Algorithmen greifen auf verschiedene Operatoren zurück, um die Ausgangspopulation weiterzuentwickeln. Zu den grundlegenden Mechanismen, welche die Evolution überhaupt erst ermöglichen, zählen Selektion, Rekombination und Mutation. Nachfolgend werden die einzelnen GA-Operatoren genauer vorgestellt.

Selektion (Selection-Operator)

Selektion bestimmt, welchen Individuen es erlaubt wird, Nachwuchs zu zeugen und wie viele Nachkommen ihnen gestattet werden. Die Auswahl der Elternteile basiert auf dem Fitnessscore, wobei der Genetic Algorithm Personen mit guten Werten bevorzugt.

Rekombination (Crossover-Operator)

Neue Individuen werden durch Rekombination erzeugt. Die Kreuzungsstellen wählt der genetische Algorithmus per Zufall aus. An den entsprechenden Stellen werden daraufhin die Gene ausgetauscht, wodurch Nachkommen mit neuen Eigenschaften entstehen. Die nachfolgende Übersicht zeigt ein Beispiel für Rekombinationen auf:

• Gene von Elternteil 1: A|B|C|D|E|F
• Gene von Elternteil 2: G|H|I|J|K|L
• Gene des Nachwuchses: A|B|I|J|K|F

Mutation (Mutation-Operator)

Die Grundidee von Mutationen besteht darin, zufällige Gene in die Nachkommen einzufügen – also die potenzielle Lösung eines Entscheidungsproblems abzuändern. Das hält die Vielfalt innerhalb der Population aufrecht und verhindert ein vorzeitiges Konvergieren. Hier ein Beispiel für eine Mutation:

• Gene vor Mutation: A|B|C|D|E|F
• Gene nach Mutation: A|B|L|D|T|F

In welchen Bereichen werden Genetic Algorithms eingesetzt?

Genetische Algorithmen finden vor allem in Anwendungsbereichen Verwendung, wo traditionelle analytische Methoden an ihre Grenzen stoßen. Dies gilt hauptsächlich für Probleme mit einem großen und komplexen Lösungsraum. Ein zentrales Einsatzgebiet stellt Deep Learning dar, wo Genetic Algorithms zur Optimierung der Gewichte von Neural Networks eingesetzt werden.

Darüber hinaus werden genetische Algorithmen oftmals in der Produktionsplanung verwendet. Dort helfen sie, optimale Zeitpläne und Ressourcenzuweisungen zu finden. In der Wirtschaft und im Finanzwesen kommen die Algorithmen sowohl im Zuge der Portfoliooptimierung als auch bei der Entwicklung komplexer Handelsstrategien zum Einsatz. Ein weiteres Anwendungsgebiet ist das Hyperparametertuning von Modellen aus dem Bereich Machine Learning. Obwohl sie nicht immer die effizienteste Methode sind, gelten GAs aufgrund ihrer Flexibilität als sehr vielseitige Optimierungstechnik.

Praktisches Anwendungsbeispiel für genetische Algorithmen

Angenommen, die Aufgabe eines genetischen Algorithmus besteht darin, eine Zielzeichenkette – beispielsweise „The fittest survive” – zu erzeugen, die ausgehend von einer zufälligen Zeichenkette gleicher Länge gebildet wird. Die einzelnen Zeichen (A bis Z, a bis z, 0 bis 9 und Sonderzeichen) stellen in diesem Beispiel die Gene dar. Die Zeichenkette lässt sich hingegen als Chromosom beziehungsweise Lösung betrachten. Der Fitnessscore bildet die Anzahl der Zeichen ab, die von der Zielzeichenkette abweichen. Demzufolge werden Individuen mit einem niedrigen Score bevorzugt. Die nachfolgende Tabelle zeigt auf, wie der Output in diesem Fall aussehen könnte:

Allerdings sei an dieser Stelle angemerkt, dass der Output möglicherweise variiert. Dieser Umstand lässt sich darauf zurückführen, dass der Genetic Algorithm mit zufälligen Zeichenfolgen startet.