Genetische Algorithmen (GA)

Schon wieder bei der Natur abgeschaut! ;-)

Naja, wo auch sonst? Die Lebewesen in unserer Natur müssen sich anpassen. Ohne Anpassung wäre kein Leben möglich. Tiere und Pflanzen sind ein erstaunliches Vorbild.
Die Evolution, die es Lebewesen ermöglicht hat zu überdauern, lässt sich im Computer vereinfacht und beschleunigt simulieren.
Was wissen wir von der Natur?

• Die Schwachen sterben vor den Starken
• Es vermehren sich mehr starke als schwache Lebewesen
• Eltern geben Kindern Erbgut weiter
• Es treten Mutationen auf
• Gute Mutationen führen zu erhöhter Lebensdauer
• Schlechte Mutationen verkürzen das Leben

Und genau dieses Wissen lässt sich übertragen! Fangen wir mit 'Information' an. Erbgut enthält Information. Ein Computerprogramm hat auch Information. Gene liegen in Ketten vor.

Daher ordnen wir die Informationen des Programms auch als Kette an.
In unserem Beispiel geht es um eine Ameise. Diese Ameise ist nicht sehr schlau. Sie folgt einem Pfad, der in ihren Genen festgeschrieben ist und dreht nur um, wenn sie einen Ort betritt, an dem sie schon war.
Der Pfad ist so abgespeichert:
LRLRLRLLRLLLRLRLRLLRLLLRRRLRL
Immer ein Stück nach Links oder nach Rechts! Wenn die Befehlskette 'abgearbeitet' ist, geht es wieder von vorne los.
Da es nur 2 Zustände gibt, lässt sich die Kette binär darstellen:
01010100100010101001000111010

Eine Ameise kann sich nicht fortpflanzen und in der Evolution voranschreiten. Daher braucht man viele Ameisen. Da der GA eine Vereinfachung ist, reichen z.B. 50 Ameisen aus. Diese 50 Ameisen haben alle unterschiedliche Gene. Diese werden per Zufall am Anfang des Computerprogramms bestimmt.

Nun muss man die Umgebung der Ameisen festlegen. Man muss sagen, wo die Ameisen langlaufen können und festlegen, was gut für eine Ameise ist. In unserem Beispiel ist die Welt nur 300x300 Ameisenschritte groß, und die Ameisen sind reiselustig und wollen möglichst viel von der Welt sehen! Das heisst: Möglichst viel von der Welt erkunden und wenig Orte doppelt sehen. Die Lebensdauer der Ameise legen wir auch fest (Ist natürlich unrealistisch, aber hier geht es ja um den Weg und nicht um die Reisedauer). Ein Ameisenleben dauert 10000 Ameisenschritte. Auf schnellen Prozessoren ist das ein kurzes Leben und auf alten Prozessoren ein langes Leben.

Algorithmus:

Der nächste Schritt besteht also darin, alle Ameisen nacheinander in der Mitte der Welt auszusetzen und sie 10000 Schritte machen zu lassen. Es wird für jede Ameise notiert, wieviele Orte sie auf ihrer Reise gesehen hat.

Von unseren Ameisen werden sich die Stubenhocker nicht fortpflanzen dürfen. Sie sterben aus. An ihre Stelle rücken die teilweise mutierten Nachkommen der Cityhopper-Ameisen. ;-)


In der Tabelle kann man sehen, welche Gene vom Vater und welche von der Mutter kommen. Die Mutationen sind mit Fettschrift markiert.
Die Population wird also mit Kindern wieder aufgefüllt. Nicht selten passiert es, dass ein Kind sich durch die Neukombination der Gene oder durch Mutation noch besser verhält als seine Eltern.

Der Algorithmus wird ab hier wieder von vorn begonnen.

Anhalten kann man den Algorithmus dann, wenn man meint, dass sich keine besseren Gene mehr ergeben. Oder einfach nach einer festgelegten Zeit.

In meinem Beispielprogramm habe ich den Weg der Ameise als blauen Pfad angezeigt. Orte, die mehrmals besucht werden, werden langsam gelb. Hier das Endergebnis:
Das Optimum wäre natürlich eine Gleichverteilung von blauen Linien, ohne dass man schwarze oder gelbe Bereiche erhält.


Nochmal in 'Bewegung' und zum Verlinken mit Youtube:


So, das wär dann die Einführung. Vielleich vertiefe ich dieses Thema noch, denn es gibt auch noch die genetischen Programme. Dort wird etwas abstrakter gearbeitet. Gene gibt es da nur noch selten...