Evolutionäre Algorithmen – Die Evolution als Vorbild zur Problemlösung – Teil 3

Was evolutionäre Algorithmen überhaupt sind und wie sie funktionieren, haben wir in den letzten beiden Artikeln besprochen. Das Problem mit der bisherigen Erklärung von evolutionären Algorithmen ist jedoch, dass sie sehr problemgebunden sind; für jedes zu lösende Problem muss ein neues Programm geschrieben werden, da insbesondere die Mutation und Rekombination von den jeweiligen Eigenschaften der Individuen – der Lösungskandidaten – abhängen. Dass dies eleganter zu lösen ist, habe ich ja schon das letzte Mal angedeutet. Heute möchte ich nun auch darlegen, wie sich das bewerkstelligen lässt.

Rekapitulieren wir noch einmal das Problem. Um die Eigenschaften eines Individuums zu mutieren, muss natürlich jede einzelne Eigenschaft bekannt und zudem vorgegeben sein, wie und vor allem in welchem Rahmen sie geändert werden darf. Auch für die Rekombination – die Verschmelzung der Eigenschaften zweier Individuen zu einem Kind – müssen natürlich sämtliche Eigenschaften der Individuen bekannt sein. Prinzipiell ist das natürlich kein Problem, führt jedoch dazu, dass ein einmal geschriebenes Programm nur zur Lösung exakt des Problems geeignet ist, für welches es entworfen wurde. Hinzu kommt, dass die Rekombination einzelner Eigenschaften zu einer insgesamt geringeren Variabilität zwischen den einzelnen Generationen von Individuen führt. Denken wir etwa an das Beispiel aus dem letzten Artikel: ein Individuum bestand bestand dort aus jeweils 2 Eigenschaften – der vertikalen und der horizontalen Position -, deren Rekombination nur zu ganz bestimmten Kindern führen konnte, wobei pro Elternpaar jeweils nur 2 verschiedene Kinder überhaupt möglich waren. Mit steigender Anzahl von Eigenschaften würde übrigens auch der Programmieraufwand immer weiter ansteigen, da die Funktionen zum Mutieren und Rekombinieren immer mehr Eigenschaften beachten müssten. Ein Ansatz, der sowohl allgemeingültig (und damit problemunabhängig) ist und auch problemlos auf “größere” Individuen angewandt werden kann, wäre also von Vorteil.

Zur Lösung der genannten Problematik(en) haben sich schlaue Informatiker einmal mehr in der Natur umgeschaut und von dort ein “Verfahren” übernommen, welches auch passenderweise bereits die Grundlage für die Evolution liefert: die Genetik. Wie wir alle wissen, werden die Erbinformationen eines jeden Lebewesens durch die DNA gespeichert. Die DNA ist – vereinfacht gesagt – eine Kette, bestehend aus den Nukleinbasen Adenin, Thymin, Cytosin und Guanin, in welcher durch die sequentielle Anordnung der vier Basen Informationen codiert werden (siehe Bild rechts, via Wikipedia). Diese Informationen bestimmen zu einem großen Teil, wie das Lebewesen später aussieht und sich verhält; die DNA bildet somit den Genotyp – die Gesamtheit der Gene – eines Lebewesens und codiert seinen Phänotyp, sein Erscheinungsbild. Denkt man aber einmal genauer darüber nach, so stellt die DNA nichts anderes als eine Kette von Werten dar, wobei jeweils 4 Werte für jede Position in der Kette zur Verfügung stehen. Die DNA ähnelt damit einer einfachen Bitkette, nur dass bei letzterer eben für jede Position nur 2 Werte – 0 und 1 – möglich sind. Und genau hier setzen die evolutionären Algorithmen an.

Die Idee ist relativ einfach: anstatt ein Individuum durch seine konkreten Eigenschaften – seinen Phänotyp – zu beschreiben, werden diese Eigenschaften in Form einer Bitkette codiert. Im Kontext unseres Beispiels aus dem letzten Artikel (wer sich nicht erinnert, möge noch einmal nachlesen) würde das bedeuten, dass die beiden Positionen (die vertikale und die horizontale) einfach durch Bitketten repräsentiert und aneinandergereiht werden. Nehmen wir an, ein Individuum hat die Position (12,7) und die möglichen Positionen befinden sich im Intervall (0,0) bis (15,15); es reichen also 4 Bit aus, um eine Komponente der Position zu beschreiben (wir erinnern uns). Dual codiert erhalten wir damit die Position (1100,0111); in einer einzigen Bitkette zusammengefasst können wir also durch die Kette 11000111 das Individuum beschreiben, welches an Position (12,7) liegt. Diese codierte Bitkette wollen wir – analog zur Genetik – als Genom bezeichnen.

Auf die gleiche Art und Weise kann nun jedes beliebige Individuum codiert werden. Es ist dabei übrigens nicht notwendig, dass die Eigenschaften eines Individuums zwingend aus einzelnen Zahlen bestehen, die dual codiert und dann aneinandergereiht werden. Die Codierung in eine Bitkette kann beliebig aussehen; es muss lediglich möglich sein, aus dieser Bitkette – dem Genotyp – das eigentliche Individuum – den Phänotyp – wiederherstellen zu können. Für diese Wiederherstellung wird eine Funktion g definiert, welche eine Bitkette auf das zugehörige Individuum abbildet. Für obiges Beispiel würde das etwa bedeuten, dass

g(11000111) = (12,7)

ist. Wie die Abbildung genau funktioniert, liegt dabei allein im Ermessen des Programmierers und kann praktisch beliebig umgesetzt werden. Zudem muss natürlich festgelegt werden, ob die Bitkette eine feste Länge haben soll (wie in unserem Beispiel mit 8 Bit) oder ob sie variabel sein kann; das hängt aber wie immer vom konkreten Problem ab. Übrigens muss man sich natürlich nicht auf Bitketten beschränken – jedes beliebige Wertesystem kann die Grundlage für die Informationskette bilden. Häufig verwendete Systeme sind eben das duale System, das Dezimalsystem mit nur natürlichen oder ganzen Zahlen oder auch das Dezimalsystem mit reellen Zahlen.

Wo liegt nun aber der eigentliche Vorteil darin, ein Individuum als Wertkette zu codieren und nicht den Phänotyp direkt für Mutation und Rekombination zu benutzen? Genau wie in der Natur alle Lebewesen auf der DNA basieren und Mutation sowie Rekombination den gleichen Prinzipien folgen – sei es ein Fisch, ein Insekt, eine Pflanze, ein Mensch oder ein anderes Tier -, können die gleichen Techniken bei der Mutation und Rekombination von Wertketten in einem evolutionären Algorithmus angewendet werden, unabhängig davon, wie das codierte Individuum aussieht. Man sagt, dass die Mutation und Rekombination auf dem Genotyp der Individuen stattfinden.

Die möglichen Mutationen hängen nun nicht mehr von den Eigenschaften des Individuums ab, sondern nur noch von den Operationen, die auf Wertketten – dem Genom – stattfinden können. Die einfachste Operation ist hier sicherlich auf Bitketten möglich: die Invertierung einer einzelnen, zufällig gewählten Position im Genom – aus einer 0 wird eine 1 oder umgekehrt – bewirkt die kleinstmögliche Änderung an einem derart codierten Individuum. Etwas umfangreichere Mutationen können mehrere Stellen im Genom oder ganze Abschnitte invertieren, bis hin zur gesamten Bitkette (wobei über die Sinnhaftigkeit einer solchen Makro-Mutation natürlich gestritten werden kann). Besteht das Genom nicht aus binären, sondern etwa aus natürlichen, ganzen oder reellen Zahlen, so können die einzelnen Positionen zwar nicht invertiert, so doch aber auf verschiedene andere Arten modifiziert werden. Denkbar ist hier alles, was man einer Zahl so antun kann; man kann Werte hinzuaddieren oder abziehen, man kann sie mit einem Faktor multiplizieren oder man kann dividieren, man kann sie auf einen Höchst- oder Mindestwert setzen und so weiter. Unabhängig von der dem Genom zugrundeliegenden Zahlenbasis kann man auch Abschnitte des Genoms austauschen oder – bei variabler Genomlänge – Abschnitte löschen oder zufällige neue Abschnitte hinzufügen. Ein kleines Beispiel hierzu; nehmen wir dazu unser obiges Beispielindividuum 11000111, welches die Position (12,7) codiert. Wenden wir verschiedene Mutationen darauf an, so können sich etwa die folgenden Individuen ergeben:

Auch bei der Rekombination kann die einheitliche Darstellung des Genoms ausgenutzt werden. Ein typischer Rekombinationsvorgang eines evolutionären Algorithmus sieht so aus, dass die Genome zweier (oder mehrerer) Elternindividuen hergenommen, geteilt und zu (meist zwei) neuen Individuen zusammengesetzt werden. Die Teilung kann nach verschiedenen Verfahren erfolgen. Häufige Verwendung findet hier der 1-Punkt-Crossover, bei welchem die beiden Genome der Eltern an der gleichen Stelle geteilt und die beiden Teile jeweils untereinander vertauscht werden. Analog kann natürlich auch ein 2-Punkt-Crossover mit 2 Teilungspunkten oder ein beliebiger n-Punkt-Crossover verwendet werden. Darf die Länge des Genoms variieren, können die Teilungspunkte für den Crossover auch an unterschiedlichen Stellen innerhalb der Genome der Eltern liegen, so dass die Genomlänge der Kinder von der der Eltern abweicht. Da die Teilungspunkte in den Genomen natürlich nicht zwingend an den Stellen liegen müssen, welche bestimmte Eigenschaften des Individuums codieren (sofern überhaupt eine direkte Abbildung von Genomabschnitten auf Eigenschaften vorhanden ist), können bereits bei der Rekombination neue Eigenschaften entstehen, wodurch die Variabilität der Individuen in der Nachfolgegeneration erhöht wird (ein oft begrüßenswerter Umstand bei der Anwendung evolutionärer Algorithmen; warum, sehen wir im nächsten Artikel). Zur Demonstration noch 3 kleine Bilder (übernommen aus der Wikipedia); die beiden Farben repräsentieren jeweils die Genom(abschnitt)e der beiden Elternteile:

1-Punkt-Crossover:

2-Punkt-Crossover:

1-Punkt-Crossover mit variabler Genomlänge:

Mit dem hier beschriebenen Verfahren ist es also möglich, einen einmal programmierten evolutionären Algorithmus auf jedes beliebige Problem anwenden zu können. Anstatt immer den gesamten Algorithmus neu programmieren zu müssen, reicht es zur Problemlösung also, 3 problemabhängige Informationen vorzugeben: die Art des Genoms der Individuen (die Basis der Wertkette, ob es fester oder variabler Länge sein kann und ob Restriktionen etwa in Bezug auf die größtmögliche Zahl in einem Genom mit Dezimalzahlen bestehen); die Abbildungsfunktion g, welche den Genotyp eines Individuums auf seinen Phänotyp abbildet; und natürich die Fitnessfunktion f, die den Phänotyp (alternativ natürlich auch direkt den Genotyp) eines Individuums bewertet. Mit Hilfe dieser 3 Angaben kann ein einmal programmierter Algorithmus prinzipiell auf jedes beliebige, [update]durch evolutionäre Algorithmen zu lösende[/update] Problem angewendet werden. Eine, wie ich finde, überaus elegante Lösung, welche das Vorbild der Natur aufgreift und zur Lösung von Problemen einsetzt.