Evolutionäre oder Genetische Algorithmen funktionieren beeindruckend gut in der Praxis. Wenn man sich verschiedene meta-heuristische Suchalgorithmen im Vergleich anschaut, wird schnell deutlich, dass natürliche Evolution als Suchalgorithmus die jeweils besten Aspekte verschiedener Ansätze vereint und diesen damit deutlich überlegen ist. Die hier dargestellten Grundlagen basieren im wesentlichen auf dem Buch von Russell and Norvig—"Artificial Intelligence: A Modern Approach". Die Authoren haben auf großartige Weise die verschiedenen Algorithmen klassifiziert, strukturiert und in eine logische Ordnung gebracht.

Im folgenden geht es darum, eine Lösung für ein beliebiges Optimierungsproblem (z.B. Arbeitsplan, Schaltflächenlayout, ...) zu finden. Der Suchraum eines Problems ist der Lösungsraum, wie er durch die Menge aller möglichen Lösungskandidaten definiert wird. Wenn der Suchraum zu groß ist um systematisch untersucht zu werden (z.B. wenn er unendlich/kontinuierlich ist) können Lokale Suchalgorithmen eingesetzt werden, um in angemessener Zeit Lösungen zu finden die "gut genug" sind. Diese Algorithmen arbeiten mit einem aktuellen Zustand (statt z.B. einem Suchpfad), und belegen damit eine konstante Menge an Speicher — ungeachtet der Größe des Suchraumes. Im allgemeinen bewegen sich lokale Suchalgorithmen nur vom aktuellen Zustand zu einem direkten Nachbarzustand — daher die Bezeichnung "lokale" Algorithmen.

Die Form des Suchraumes (genannt Landschaft, eng. landscape) wird durch eine Zielfunktion definiert. Ein Beispiel einer solchen Landschaft wird oben im Bild dargestellt. Jeder Zustand dieser Landschaft hat eine Position und eine "Höhe" bzw. einen Zielwert (definiert durch den Wert des Zustandes entsprechend der Zielfunktion). Abhängig davon, ob das Problem als Minimierungs- oder Maximierungsproblem dargestellt ist, besteht das Ziel darin, das tiefste Tal (genannt globales Minimum) oder den höchsten Gipfel (genannt globales Maximum) zu finden. Da diese beiden Probleme einfach ineinander überführt werden können, wird im Folgenden nur noch das Maximierungsproblem betrachtet. Oft gibt es in solchen Landschaften auch lokale Maxima — also ein Gipfel der höher ist als die benachbarten Zustände, aber trotzdem noch niedriger als das globale Maximum. Außerdem gibt es möglicherweise Plateaus (in der Darstellung als Schulter bezeichnet), also Gebiete in denen alle Zustände den gleichen Zielwert haben. In den meisten Optimierungsproblemen gibt viele Optimierungsparameter, sodass die Landschaft dann multi-dimensional ist. Zur vereinfachten Darstellung wurde im Beispiel eine Landschaft mit nur einem Optimierungsparameter gewählt.

Ein Bergsteigeralgorithmus ist einfach eine Schleife, in der zu benachbarten Zuständen in Richtung steigendem Zielwert gewechselt wird (also "bergauf") und die beendet wird wenn ein Gipfel erreicht ist. Dieser einfache gierige Algorithmus (eng. greedy) macht oft initial schnelle Fortschritte, bleibt aber in lokalen Maxima stecken (statt globale Maxima zu erreichen) oder endet auf Plateaus, wo die Orientierung verloren geht, und der Algorithmus nicht weiß, in welche Richtung er sich weiter bewegen soll. Um dieses Problem zu umgehen wählt der stochastische Bergsteigeralgorithmus von mehreren Möglichkeiten sich aufwärts zu bewegen aus zufällig eine aus (besonders sinnvoll wenn die Landschaft multi-dimensional ist). Im Falle von vielen (z.B. vielen Tausend) Nachbar- oder Folgezuständen kann ein stochastischer Bergsteigeralgorithmus als erste-Wahl (eng. first choice) Bergsteigeralgorithmus implementiert werden, indem Nachfolgezustände so lange zufällig generiert werden, bis ein Zustand dabei ist, der besser ist als der aktuelle. Wenn dabei auch (mit einer gewissen Wahrscheinlichkeit) ein Folgezustand gewählt werden kann, der schlechter ist als der aktuelle, handelt es sich dabei um eine Zufallsbewegung (eng. random walk). Eine reine Zufallsbewegung ist hoch ineffizient, hat aber bessere Chancen nicht in einem lokalen Maximum stecken zu bleiben. Simulierte Abkühlung (eng. simulated annealing) (benannt nach dem Abkühlungsprozess in der Metallverarbeitung) akzeptiert auch einen schlechteren Nachfolgezustand, wobei die Wahrscheinlichkeit hier mit der Zeit abnimmt (was eben die Abkühlung simuliert). Ein Zufalls-Neustart (eng. random-restart) Bergsteigeralgorithmus führt eine Serie von Bergsteigersuchen durch, wobei jedes Mal von einem anderen zufälligen Initalzustand gestartet wird.

Statt eines einzigen aktuellen Zustandes verwaltet ein lokaler Balkensuchalgorithmus (eng. local beam search) eine Menge von k aktuellen Zuständen. Bei jedem Schritt werden alle Nachfolger aller k Zustände erzeugt, aber es werden nur die k besten Nachfolger behalten. Obwohl dies auf den ersten Blick wie k parallele Zufälls-Neustart Bergsteigersuchen wirkt, liegt der Unterschied darin, dass ergebnislose Suchen relativ schnell verworfen werden, und so die Ressourcen dort konzentriert werden, wo der größte Fortschritt erzielt wird. Im Gegenzug dazu, kann lokale Balkensuche unter der Reduktion der Diversität unter den k Zuständen leiden: Wenn z.B. ein einzelner Zustand mehr als k Nachfolgezustände hat, die jeweils alle allen anderen Nachfolgezuständen überlegen sind, konzentriert sich der Algorithmus auf eine kleine Region des Suchraumes und degradiert somit zu nicht viel mehr als einer teuren Version des Bergsteigeralgorithmus. Die stochastische Balkensuche (analog zur stochastischen Bergsteigersuche) versucht dieses Problem zu umgehen, indem die k Nachfolgezustände mit einer bestimmten Wahrscheinlichkeit gewählt werden, in Abhängigkeit vom jeweiligen Zielwert.

Wenn man einen Folgezustand als Nachkomme (eng. offspring) bezeichnet und die Zielfunktion als Fitness, dann gleicht stochastische Balkensuche einem evolutionären Prozess mit asexueller Reproduktion und natürlicher Selektion. Ein Genetischer Algorithmus oder GA macht daraus eine sexuelle Reproduktion, indem zwei Elternzustände oder Individuen kombiniert werden anstatt einen einzelnen Zustand zu modifizieren. Diese Kombination wird Rekombination (eng. crossover) genannt und die konkrete Ausprägung hängt stark vom Einsatzgebiet ab. Wenn die Individuen z.B. Sequenzen von etwas sind, kann eine Rekombination bedeuten, dass zwei solcher Sequenzen an einem zufälligen Rekombinationspunkt getrennt und mit der jeweiligen Hälfte der anderen Sequenz wieder vereint werden. Abhängig von der Diversität der Eltern kann eine Rekombination Individuen erzeugen, die sehr unterschiedlich zu beiden Elternteilen sind. Die Diversität einer Popultion ist oft zu Beginn der Suche größer, sodass Rekombination dazu führt, dass der Algorithmus am Anfang des Prozesses größere Schritte macht, und kleinere Schritte gegen Ende der Suche, wenn sich die Individuen stärker ähneln. Darin ähnelt der Algorithmus der simulierten Abkühlung. Rekombination birgt außerdem den Vorteil, dass verschiedene Teile von Individuen, die sich unabhängig entwickelt haben um sinnvolle Funktionen zu erfüllen, kombiniert werden und dabei die Granulariät mit der die Suche operiert erhöht wird. Zustätzlich werden, wie in der stoachstischen Balkensuche, alle Individuen mit einer gewissen Wahrscheinlichkeit mutiert. Die Folgegeneration der Population wird dann aus den neuen Zuständen gewählt, entsprechend der Zielfunktion bzw. Fitnessfunktion. Wie oben erläutert, definiert die Fitnessfunktion die Form der Landschaft des Suchraumes und ist damit überaus wichtig für die Effektiviät der Suche.

Natürlich sind genetische Algorithmen eine plumpe Vereinfachung der komplexen evolutionären Prozesse, wie sie in der Natur ablaufen. Von den vielen Unterschieden ist der wichtigste vermutlich der, dass die Gene selbst sowohl Teile der Mechanismen des biologischen Prozesses (wie Partnerwahl, Rekombinations- und Mutationswahrscheinlichkeiten) als auch den Mechanismus mit dem die Gene wiederrum in einen funktionierenden Organismus übersetzt werden codieren. Dass heißt in der Natur werden sowohl die Individuen als auch der Suchalgorithmus selbst verbessert.

Quellen:

Tagged in : Programmierung, Genetische Algorithmen,

Dr. Jeremias Rößler
Dr. Jeremias Rößler

ist Software Ingenieur – spezialisiert auf das Erstellen und die Pflege von großen, komplexen Softwaresystemen, die unter akzeptablen Kosten stabil und zuverlässig funktionieren. Er besitzt über sechs Jahre Berufserfahrung in der Entwicklung von Individualsoftware. 2013 hat er am Lehrstuhl für Softwaretechnik an der Universität des Saarlandes promoviert. Seine Forschung beschäftigt sich mit dem Auffinden und der Analyse von Fehlern, indem Software-Systeme mittels generierter Tests systematisch ausgeführt und dabei Fehler aufgedeckt und analysiert werden. Er ist Gründer von ReTest, einem IT-Dienstleistungsunternehmen, das Software programmunterstützt testet.