Genetische Algorithmen

Optimierung nach dem Ansatz der natürlichen Selektion.

Genetische Algorithmen sind Methoden zur Optimierung von Funktionen, die sich durch ihren evolutionären Ansatz an der Fortpflanzung von natürlichen Lebewesen orientieren. Sie können für eine Vielzahl von Optimierungsproblemen eingesetzt werden, wie beispielsweise der Planung von Produktionen oder sogar für das Hyperparametertuning von MachineLearning-Modellen. Zwar gibt es für die einzelnen Probleme besser zugeschnittene Lösungen, der evolutionäre Ansatz macht diese Form von Algorithmen jedoch sehr spannend. Sie bieten sich besonders dann an, wenn keine passende analytische Lösung vorhanden ist und man durch einen großen Parameterraum eine hohe Anzahl an Kombinationsmöglichkeiten berechnen muss.  Ein beliebtes Beispiel, um den genetischen Algorithmus zu behandeln, ist das „Traveling Salesperson Problem“, bei dem eine möglichst kurze Route zwischen einer Anzahl an Punkten berechnet werden soll. Die klassische Anwendung für dieses Problem ist die Berechnung der optimalen Route eines Paketauslieferers.

Auf dieser Website kannst du den Genetischen Algorithmus gleich selbst ausprobieren:

Genetischer Algorithmus

Das Traveling Salesperson Problem

Beim „Traveling Salesperson Problem“ wird eine Person skizziert, welche mehrere Orte auf der Welt besuchen soll. Ziel ist es, am Ende die kürzeste Route zu wählen. Die Herausforderung liegt nun darin, mit möglichst wenig Rechenaufwand eine möglichst kurze Route zu ermitteln – also ohne jede Eventualität einzeln durchzurechnen.

Bruteforce Ansatz

Um das „Traveling Salesperson Problem“ zu lösen, könnten alle Kombinationen aus Punkten errechnet und die kürzeste Strecke ausgewählt werden. Bei einer geringen Anzahl an Punkten funktioniert das noch sehr gut, das Ergebnis ist dann die tatsächlich kürzeste Route. Erhöht man jedoch die Anzahl der Punkte, steigt die Anzahl der Kombinationen sehr stark an – jede Möglichkeit einzeln durchzurechnen ist dann nicht mehr möglich.

Die Anzahl der möglichen Routen, die ausprobiert werden können, folgt der Fakultät der Anzahl der Stopps. Bei 3 Punkte ergibt das lediglich 6 mögliche Routen. 10 Punkte, hingegen, ergeben bereits über 3,5 Millionen mögliche Routen. Um 20 Orte einmal zu besuchen, muss die Person bereits über 2 Trillionen mögliche Routen evaluieren.

Berechnung des Genetischen Algorithmus

Aufbau

Um sich einer optimalen Lösung annähern zu können, durchläuft der Genetische Algorithmus mehrere Iterationen aus Berechnung und Reproduktion. Diese Iterationen können durch die evolutionäre Perspektive als Generationen bezeichnet werden. Jede Generation hält eine Population von Lösungsansätzen, deren Aufbau im folgenden Bild zu sehen ist. Um die Lösungsansätze dieser Generation zu verbessern, werden die besten Lösungen kombiniert und somit neue Generation gebildet. Um nach dem Motto „Survival of the fittest“ die besten Routen identifizieren zu können, errechnet man für jede Lösung einen Fitness-Score, welcher sich in unserem Fall sehr einfach über die Distanz der Route berechnen lässt. Somit werden die Routen mit der kürzesten Distanz ausgewählt und dürfen die nächste Generation formen.

Generation Zero

Zu Beginn wird eine Anfangsgeneration gebildet. Dafür wird eine Population mit komplett zufällig erstellten Lösungsmöglichkeiten befüllt. Jedes Mitglied erhält somit eine Route, deren Punkte in einer beliebigen Reihenfolge vorkommen können.

Elite

Der Elite-Parameter ist eine der Stellschrauben zur Steuerung eines Genetischen Algorithmus. Die Höhe dieses Parameters bestimmt die Größe des Mitglieder-Pools mit der größten Fitness, also in unserem Beispiel die Routen mit der kürzesten Distanz. Aus diesem festgelegten Pool wird die neue Generation zusammengestellt. Dieser Schritt simuliert also die Selektion einer realen Generation von Lebewesen, die durch ihre hohe Anpassungsfähigkeit in einer Umgebung überleben und damit auch die Möglichkeit haben, sich fortzupflanzen (und damit ihre positiven Eigenschaften an ihre Kinder weiterzuvererben).

Crossover

Für jedes Mitglied der neuen Generation werden zwei Elternteile aus dem Elite-Pool ausgewählt, welche jeweils einen Teil ihrer Lösung an ihr Kind vererben. Hierbei wird von einem Elternteil eine zufällige Anzahl an Punkten ausgewählt und an das Kind an der gleichen Position weitergegeben. Das zweite Elternteil füllt die fehlenden Punkte möglichst mit der ebenfalls gleichen Position auf. Ist diese allerdings bereits besetzt, wird eine komplett freie Position genutzt, welche durch keinen anderen Punkt besetzt ist. Ist die Population wieder aufgefüllt, wird der Kreislauf aus Fitnessberechnung und Reproduktion über mehrere Generationen wiederholt, bis man eine zufriedenstellende Lösung erhält.

Mutation

Mit jeder neuen Generation verbessert sich die Distanz der aktuell kürzesten Route. Irgendwann wird der Fortschritt jedoch stagnieren, da aus der zufällig erstellten Anfangsgeneration das bestmögliche herausgeholt wurde. Alle Kinder einer neuen Generation werden also fast den gleichen Lösungsansatz enthalten. Um dies zu verhindern, kann eine prozentuale Chance gesetzt werden, zu welcher ein Kind eine Mutation erhält. Trifft dies zu, werden zwei Punkte innerhalb der Route getauscht. Dadurch entsteht eine neue Route, die möglicherweise nicht in der vorherigen Generation auftritt, jedoch auch nicht zu stark von den besten Routen abweicht.

Eine weitere Möglichkeit, die Vielfalt einer neuen Generation zu fördern, ist einen Anteil der neuen Population nicht zu reproduzieren, sondern zufällig zusammenzustellen.

Fazit

Der Genetische Algorithmus kann schneller eine gute Lösung errechnen, als es durch das Ausprobieren aller möglichen Kombinationen möglich wäre. Hierbei besteht jedoch keine Garantie, dass die Lösung, die man nach jeder Generation erhält, auch die bestmögliche ist, ohne alle Kombinationen vorher ausprobiert zu haben. Da jedoch das Erfassen aller Möglichkeiten aus Gründen, wie z.B. benötigter Rechenleistung, nicht immer möglich ist, bietet der Genetische Algorithmus einen sehr guten Kompromiss und bietet durch den biologischen Ansatz eine Inspiration für neue Lösungsansätze.