Genetische Algorithmen

Zur selben Zeit in der Rechenberg seine Evolutionsstrategien entwickelte, beschäftigte sich John Holland ebenfalls mit der rechnergestützten Simulation der biologischen Evolution und begründete sein Modell der Genetischen Algorithmen (kurz GA). Die beiden Verfahren wurden dabei unter verschiedenen Gesichtspunkten und vollkommen unabhängig voneinander entwickelt. Dabei unterscheiden sich Genetische Algorithmen und Evolutionsstrategien nur in wenigen Einzelheiten, auf die im Artikel EA vs. GA eingegangen wird. Während Rechenberg primär die Lösung von Problemen mit realzahl-codierten Parametersätzen – die für ingenieurtechnische Problemstellungen meist sinnvollste und zugleich kompakteste Art der Codierung – im Auge hatte, interessierte sich Holland auch für die grundsätzliche Struktur, mit der in der natürlichen Evolution Informationen gespeichert und verarbeitet werden. Genetische Algorithmen gehen also genauer auf die natürlichen Gegebenheiten der natürlichen Evolution ein.

John Holland richtete sein Hauptaugenmerk auf die Frage, auf welche Art und Weise die Natur genetische Informationen speichert und wie die jeweiligen Prozesse auf diesen genetischen Daten operieren. Ihn faszinierte die Tatsache, dass sich das Leben in derart vielfältiger Form allein auf Grund des genetischen Codes und den damit verbundenen evolutionären Prozessen entwickeln konnte. Diese Form der Selbstorganisation und Adaption wollte er nachvollziehen und auf technischem Wege mit Hilfe von Computersimulationen nutzbar machen. Dabei widmete er sich nicht nur der Theorie, sondern er zeigte auch verschiedene praktische Anwendungsmöglichkeiten auf.

Beschreibung eines Genetischen Algorithmus

Da es, anders als bei den Evolutionsstrategien, für Genetische Algorithmen keine formale Notation gibt, wird das Grundgerüst eines Genetischen Algorithmus meist in Form eines Pseudocodes beschrieben. Auch bei den Genetischen Algorithmen wurden im Laufe der Zeit eine große Zahl von Varianten entwickelt, die sich primär in der Codierung und den verwendeten Verfahren (Heiratsschema, Rekombination, Mutation und Ersetzungsschema) unterscheiden. Der nachfolgend dargestellte Programmabschnitt beschreibt den üblichen Ablauf eines Genetischen Algorithmus in einem Pseudocode.

Wähle problemspezifische Individuencodierung
Initialisiere Individuen der Startpopulation zufällig
do {
  Bewerte Individuen mit Bewertungs-/Fitnessfunktion
  Selektiere Elterpaare nach Heiratsschema
  Erzeuge Nachkommen durch Rekombination
  Mutiere die erzeugten Nachkommen
  Ersetze Individuen der akt. Generation nach Ersetzungsschema
} while Abbruchbedingung trifft nicht zu

Problemspezifische Codierung bedeutet hier, dass der zu optimierende Parametersatz der Problemstellung in Form eines binären Parametervektors codiert wird. Die im Pseudocode angedeutete Initialisierung der Startpopulation erzeugt Individuen mit zufällig konfigurierten Chromosomen. Eine so generierte Generation 0 enthält also eine bestimmte Menge an möglichen Lösungen im Suchraum.

Nach der Initialisierung der Population setzt der Optimierungsprozess ein. Zunächst werden die Individuen bewertet und Elter-Individuen ausgewählt. Durch Rekombination dieser Elter-Individuen werden systematisch neue Lösungen erzeugt, die gegebenenfalls mutiert und danach ebenfalls bewertet werden. Zum Schluß werden die Individuen ausgewählt, die in die nächste Generation übernommen werden sollen.

Sehr vielfältig ist auch die Festlegung einer Abbruchbedingung. Eine Abbruchbedingung könnte durch die Angabe eines mindestens zu erreichenden Qualitätswertes festgelegt werden. Als Abbruchkriterium sind aber auch beispielsweise eine maximale Rechenzeit für die Simulation oder eine maximale Anzahl an Generationsschritten möglich, was aber dazu führen kann, dass das Finden einer optimalen Lösung durch frühzeitigen Abbruch verhindert wird. Denkbar wäre auch, dass die Verarbeitung beendet wird, wenn nach einer gewissen Anzahl von Generationsschritten keine weitere Verbesserung eingetreten ist.

Codierung

Die Chromosomen von Individuen werden bei Genetischen Algorithmen in Form von binären Vektoren gespeichert. Jede einzelne Variable wird dabei durch einen Teilbereich im Individuenvektor abgebildet und eine Population ist demnach eine Menge dieser Individuenvektoren.

Beispiele:
           x = <1, 0, 1, 1, 1, 0, 0, 1>
           x ist ein Individuum mit acht Variablen

           x = <<1,0,1,1>, <1,0,0>, 1>
           x ist ein Individuum mit drei Variablen

In der praktischen Anwendung bedeutet dies, dass die zu codierenden Variablen zunächst in geeigneter Form binär codiert werden müssen. Hierbei ist unbedingt darauf zu achten, dass die Codierung der Individuen mit den genetischen Operationen, die später auf diesen Individuen durchgeführt werden sollen, optimal abgestimmt sind. Sind Codierung und die darauf operierenden genetischen Operationen unpassend gewählt, so wird ein Genetischer Algorithmus nicht erfolgreich arbeiten.

Ein grosser Vorteil der binären Codierung ist die Tatsache, dass binäre Informationen in digitalen Datenverarbeitungsanlagen schnell verarbeitet werden können. Je nach Art der zu speichernden Variablen ist die binäre Speicherung wesentlich kompakter als eine Speicherung in Form von reellen oder natürlichen Zahlen. Große Populationen können aufgrund der kompakten Speicherung also mit relativ wenig Speicher auskommen, was auch die Verarbeitung beschleunigt.

Die binäre Codierung birgt aber auch einige Nachteile. Einer dieser Nachteile ist die Positionsabhängigkeit bei der Codierung von natürlichen Zahlen, den man versucht mit einschrittigen Binärcodes wie dem Gray-Code zu entschärfen. Auch die Wertigkeit der Binärstellen stellt ein Problem dar. Bei einer Mutation beispielsweise sollten stets kleine Änderungen bevorzugt werden. Aus diesem Grunde wird ein Genetischer Algorithmus im Falle einer Mutationen höherwertige Vektorpositionen mit einer geringeren Wahrscheinlichkeit mutieren als niederwertigere.

Bewertung und Fitness

Ebenso problemabhängig wie die Codierung selbst ist auch die Bewertung der Individuen einer Population. Die Bewertungsfunktion ist eine Funktion, mit deren Hilfe Individuen aufgrund ihrer Parameterkonfiguration – der Einstellung ihrer Chromosomen – bewertet werden können. Sie stellt gewissermaßen das Optimierungskriterium dar. Ein Genetischer Algorithmus versucht stets für die Bewertungsfunktion einer Problemstellung einen optimalen Parametersatz zu erzeugen. Ob die Bewertungsfunktion dazu minimiert oder maximiert werden muss, hängt von der Problemstellung ab. Man könnte also sagen, dass die Bewertungsfunktion die Qualität einer möglichen Lösung – eines Individuums – misst bzw. wie weit ein Individuum von dem gesuchten Optimum entfernt ist.

Die ebenfalls problemspezifische Fitness eines Individuums legt die Wahrscheinlichkeit fest, mit der ein Individuum beim nächsten Generationsschritt an einer Rekombination teilnimmt. Während die Bewertung also aussagt wie gut ein Individuum an das Optimum angenähert ist, errechnet die Fitness aufgrund der Bewertung die individuelle Rekombinationswahrscheinlichkeit. Bei vielen Problemen unterscheidet sich die Fitness und die Bewertung nicht voneinander, das heißt in diesem Fall ist die Fitnessfunktion gleich der Bewertungsfunktion.

Evolutionsstrategen unterscheiden nicht zwischen der Bewertungsfunktion und der Fitnessfunktion, sondern kennen nur die Qualitätsfunktion, die quasi der Bewertungsfunktion entspricht. Im Gegensatz dazu werden diese Funktionen bei den Genetischen Algorithmen sehr wohl unterschieden. Bei den Genetischen Algorithmen entscheidet nämlich die Fitness des Individuums, ob ein Individuum zur Rekombination herangezogen wird oder nicht. Dagegen nimmt bei den Evolutionsstrategien jedes Individuum mit derselben Wahrscheinlichkeit an einer Rekombination bzw. am Fortpflanzungsprozess Teil. In vielen Fällen ist die Fitnessfunktion aber auch eine Transformation der Bewertung.

Heirats-Schema

Mit dem Heirats-Schema werden die Individuen einer Population ausgewählt, die an einer Rekombination teilnehmen sollen. Im Allgemeinen werden Rekombinationen mit je zwei Elter-Individuen durchgeführt, die zur Erzeugung von jeweils zwei Nachkommen führen. Dies ist allerdings kein Zwang, da – wie bei den Evolutionsstrategien – auch aus einem Elter-Individuum – durch klonen – ein oder mehrere Nachkommen erzeugt werden können. Prinzipiell ist auch die Rekombination von mehr als zwei Elter-Individuen denkbar.

Das bei den Genetischen Algorithmen am häufigsten verwendete Heirats-Schema ist das Roulette-Wheel-Schema. Es wählt die Elter-Individuen mit einer Wahrscheinlichkeit aus, die proportional zu ihrer Bewertung ist. Dies führt dazu, dass hoch bewertete Individuen ihre Erbinformationen mit größerer Wahrscheinlichkeit verbreiten können als durchschnittlich oder gar schlecht bewertete Individuen. Aber auch schlecht bewertete Individuen haben eine – wenn auch recht geringe – Chance sich fortzupflanzen. Dies soll dazu führen, dass sich mit zunehmenden Generationsschritten die Güte der Population fortwährend steigert. Beim Roulette-Wheel-Schema wird die Fitness der Einfachheit halber mit der Bewertung gleich gesetzt.

Rekombination

Bei den Genetischen Algorithmen spielt die Rekombination von Individuen eine wesentliche Rolle. Sie sind für die Optimierung nach dem Prinzip der Genetischen Algorithmen das, was die Mutationen für die Evolutionsstrategien sind. Bei der Entwicklung von Genetischen Algorithmen widmet man sich deshalb intensiv der Entwicklung geeigneter Rekombinationsmechanismen. Das Rekombinationsverfahren, auch Crossover-Verfahren genannt, dient dazu den Suchraum schneller und zielgerichteter zu durchschreiten, als dies durch zufälliges Suchen möglich wäre. Dabei wird das individuell verwendete Verfahren auf das jeweilige Optimierungsproblem angepasst. Es wird dabei problemabhängiges Wissen über den Suchraum in die Rekombination eingearbeitet – das Rekombinationsverfahren wird also mit einer gewissen Orientierungsfähigkeit ausgestattet.

Es existiert eine Fülle von Crossover-Verfahren, von denen das einfachste das one-point-crossover ist. Hier wird an einer zufälligen Position – ermittelt durch eine gleichverteilte Pseudo-Zufallszahl zwischen 1 und der um eins verminderten Anzahl der im Individuenvektor enthaltenen Bitwerte – im Binärvektor eine Bruchstelle ausgewählt, an der die Chromosomen der beiden Individuen gekreuzt werden. Das two-point-crossover erweitert das one-point-crossover um eine weitere Bruchstelle. Dieses Verfahren lässt sich zu einem n-point-crossover erweitern, indem weitere Zufallszahlen für zusätzliche Bruchstellen erzeugt werden.

Beispiel:
       Bei einem one-point-crossover mit den Eltern p₁ und p₂
       und der zufällig gewählten Bruchstelle q = 4
       werden aus den Eltern
           p₁ = <1, 0, 1, 1, 1, 0, 0, 1>
           p₂ = <1, 1, 0, 0, 1, 0, 1, 1>
       die Kinder
           p_Kind1 = <1, 1, 0, 0, 1, 0, 0, 1>
           p_Kind2 = <1, 0, 1, 1, 1, 0, 1, 1>

Beim Rekombinationsverfahren mit dem Namen Zufalls-Schablone wird eine zufällige Bitmaske der gleichen Länge eines Individuenvektors erzeugt. Die rekombinierten Vektoren p_Kind1 und p_Kind2 entstehen dann unter Verwendung des Zufallsvektors z durch folgendes Schema:

       p_Kind1(i) := p₁(i) für z_i = 1 und
       p_Kind1(i) := p₂(i) für z_i = 0 und
       p_Kind2 := 1-p_Kind1(i)

Mutation

Anders als bei den Evolutionsstrategien spielen Mutationen bei den Genetischen Algorithmen in der Theorie eine untergeordnete Rolle. Sie dienen hier fast ausschließlich der Verhinderung frühzeitiger Konvergenz einer durch Selektionsdruck im Laufe der Generationen zunehmend homogener werdenden Population. Damit sind sie, anders als bei den Evolutionsstrategien, nicht als Suchoperatoren oder Effizienzbeschleuniger gedacht und machen zudem keinen Gebrauch von Adaptionsmechanismen.

Dagegen wird die Mutation in der Praxis oft als zusätzliche Suchoperation eingesetzt, um den Suchvorgang zu beschleunigen. Man ist hier für jedes Mittel, welches eine Beschleunigung oder Verbesserung des Suchvorgangs zur Folge hat, dankbar. Richtig eingesetzt können Mutationen zufällig und doch zielgerichtet eine Veränderung bewirken. Da speziell angepasste Mutationen ebenso wie bei den Rekombinationen aufgrund ihrer Problemabhängigkeit effektivere Suchstrategien ermöglichen, sollten derartige Operationen auch genutzt werden.

Ersetzungsschema

Bei den Genetischen Algorithmen existieren verschiedene Selektionsverfahren, die hier als Ersetzungsschemata bezeichnet werden. Das Ersetzungsschema ist eine Vorgehensweise nach der entschieden wird, welche Individuen aus der Menge der Individuen der Elter-Generation und aus der Menge der Individuen, die als Nachkommen erzeugt wurden, als Individuen der Folgegeneration übernommen werden.

Werden einfache Ersetzungsschemata – beispielsweise Generational Replacement, was einer vollständigen Ersetzung der Elter-Individuen durch die besten Kinder und damit der ','-Variante der Evolutionsstrategien entspricht, oder Elitismus (survival of the fittest) – genutzt, so kommt es, insbesondere bei fortgeschrittener Generationenzahl, immer häufiger zur Ersetzung von einer hohen Anzahl von Individuen, die gerade erst als Nachkommen erzeugt wurden (was daran liegt, dass die Individuen der Elter-Generation meist besser bewertet wurden, als die Nachkommen). Dies führt dazu, dass Individuen nicht einmal eine Generation lang überleben. In der Natur kommt es eher selten – beispielsweise in Katastrophenfällen – vor, dass nahezu der gesamte Nachwuchs einer Population direkt nach seiner Geburt stirbt.

Eine bessere Abbildung von sozialen Strukturen bei höher entwickelten Lebewesen stellt auch die Einführung eines Kindergartens dar. In der Natur werden neu geborene Individuen oft von den Eltern, größeren Geschwistern oder von anderen Artgenossen betreut und auch beschützt, so dass sie nicht direkt nach der Geburt am Selektionsprozess teilnehmen. Erst nachdem die Individuen alles zum Überleben nötige gelernt haben, sind sie auf sich allein gestellt und können sich – sofern sie die Geschlechtsreife erreicht haben – fortpflanzen.

Abgesehen davon überleben Individuen in der Natur meist nicht nur eine Generation sondern haben eine gewisse genetisch vorgegebene Lebenszeit zur Verfügung, die sie selbst dann erreichen können, wenn sie nicht zu den Besten ihrer Art gehören. Das Modell eines Altersheims und der damit verbundenen Alterung von Individuen hat den Sinn Individuen, die noch keinen passenden Partner finden und somit nur schlechtere Individuen hervorbringen können, trotzdem noch eine gewisse Zeit an der Erzeugung von Nachkommen teilnehmen zu lassen, in der Hoffnung, dass sich mit der Zeit Individuen mit ähnlicher Qualität finden, mit denen eine Rekombination bessere Ergebnisse hervorbringen kann. Es ist eventuell auch sinnvoll, Individuen nach Erreichen eines Höchstalters zu löschen.