|
Das Java-Applet illustriert die Funktionsweise eines genetischen Algorithmus (GA). Zuerst wird eine fraktale Landschaft gebaut. Das muss mit dem Button Landschaft gestartet werden. Ziel des GA ist es, den höchsten Punkt in der Landschaft zu finden und dazu möglichst wenig Punkte "auszuprobieren", das heisst, an möglichst wenigen Stellen die Höhe der Landschaft zu ermitteln. Dazu wird zuerst eine Population von z.B. 100 Käfern (=Individuen) zufällig über die Landschaft verteilt (Button Population). Der Ort, wo der Käfer liegt, ist sein genetischer Code (die Käfer sind unbeweglich); die Höhe der Landschaft an dieser Stelle ist seine Fitness.
Danach laufen die beiden Schritte des GA, die Rekombination und die Selektion, im Wechseltakt ab: Beim Rekombinationsschritt werden zwei Käfer zufällig ausgewählt, wobei solche mit hoher Fitness bevorzugt werden. Die beiden Käfer spannen zwischen sich ein Rechteck auf; irgendwo in diesem Rechteck wird zufällig der Nachkomme geboren, der zur Population hinzugefügt wird. Beim Selektionsschritt wird ein Käfer mit einer niedrigen Fitness ausgewählt und aus der Population entfernt; die Population hat damit wieder die ursprüngliche Anzahl Individuen.
Diese Evolution kann entweder im Einzelschritt oder automatisch laufen gelassen werden: Mit dem Button Rekombination/Selektion (er wechselt seine Beschriftung je nach anstehendem Schritt) wird jeweils der nächste Schritt ausgeführt und illustriert. Mit dem Button Go wird der automatische Ablauf gestartet. Hier werden jeweils neue Nachkommen kurz hervorgehoben. Mit dem Button Abbrechen kann der automatische Ablauf unterbrochen werden.
Wenn alle Käfer dieselbe Höhe erreicht haben, ist der Algorithmus abgeschlossen. Sein Resultat ist die maximale erreichte Höhe; die kann mit dem absoluten Maximum der Landschaft verglichen werden. Die dafür gebrauchte Anzahl Messungen (Käfer, die je geboren wurden) muss in Relation zur Anzahl Punkte in der Landschaft, also 120'000, gesehen werden.
| Landschaft | Baut eine neue Landschaft. Die allfällig vorhandene Population wird gelöscht. Das funktioniert nur, wenn nicht gerade der Bau einer Landschaft im Gang ist (vlg. Abbrechen) |
| Abbrechen | Bricht den Bau einer Landschaft ab, oder den automatischen Lauf des Algorithmus |
| Population | Legt eine neue Population mit der links vom Button angegebenen Anzahl Individuen an. Sinnvolle Grössen sind zwischen 20 und etwa 200 Individuen. Bei grösseren Populationen wird der Rechenaufwand zu gross und der Ablauf langsam. |
| Rekombination / Selektion | Der Button wechselt seine Beschriftung je nach anstehendem Schritt. Durch Druck auf den Button wird ein Schritt ausgeführt und illustriert. |
| Go | startet den automatischen Ablauf des Algorithmus. Mit dem Schieberegler kann die Geschwindigkeit eingestellt werden. |
| Statusfeld links | Zeigt Informationen über die Landschaft: x,y sind die Koordinaten des Mauszeigers, h ist die Höhe an diesem Punkt, und max ist die Höhe des höchsten Punktes der Landschaft |
| Statusfeld mitte | Zeigt Informationen über die Population: N ist die Anzahl Individuen, max die Höhe des höchsten Individuums, Gen (Generationen) die Anzahl insgesamt berechneter Individuen. Das sind alle Individuen der Startpopulation plus alle Nachkommen. |
| Statusfeld rechts | Gibt Auskunft über den Zustand des Applets und die vorgeschlagenen Aktionen. |
Über Kommentar freue ich mich. Fragen werden gerne beantwortet: mailto: glauser.breitenegg@spectraweb.ch
© Pascal Glauser 13.02.1999
Genetische Algorithmen (GA) sind eine mathematische Methode, deren Grundidee mit der Evolutionstheorie aus der Natur stammt. Es geht darum, Lösungen zu Problemen zu finden, die nicht einfach so berechnet werden können, sondern durch Ausprobieren gesucht werden müssen.
Beispielsweise gibt es für die Multiplikation einen effizenten Algorithmus (=Berechnungsanleitung); niemand wird hingehen und alle Zahlen zwischen 1 und 10000 testen, um das Resultat von 13 multipliziert mit 85 zu finden. Wenn man aber auf der anderen Seite einen Weg durch ein Labyrinth sucht, kann man (bei einem gut gebauten Labyrinth) nichts anderes machen, als einen Weg nach dem anderen und eine Verzweigung nach der anderen auszuprobieren, und Irrwege als solche zu markieren. Man muss die Lösungskandidaten also einer nach dem anderen ausprobieren. Natürlich gibt es schlechtere und bessere Techniken (man kann jedesmal wieder am Anfang beginnen, oder bei einem Irrweg nur zur letzten Verzweigung zurückkehren und mit einem Weg weiterfahren, der noch nicht als Irrweg markiert ist). Analog dazu sind die GA eine Technik, die durch den Computer zugänglich geworden ist, gegenwärtig intensiv erforscht wird und die für bestimmte Problemstellungen vielversprechender sein könnte als bisher bekannte Techniken.
Dummerweise spielen sich die meisten GA in einem Raum mit mehr als drei (meist mit sehr vielen) Dimensionen ab. Damit kann sich niemand das Funktionieren eines sochen GA's vorstellen. Es gibt aber eine zweidimensionale Art der GA, die am Computer illustriert werden können. Hier wird ein Java-Applet bereitgestellt, das so einen GA laufen lässt. Gefunden habe ich die Idee zu einem GA in zwei Dimensionen bei Jeffery Horn, 1995.
Die hier vorliegende fraktale Landschaft wird nach einer Idee von Benoît Mandelbrot in Die fraktale Geometrie der Natur, Birkhäuser 1987 konstruiert: auf eine Ebene werden an zufällige Orte laufend immer kleinere Pyramiden in immer höherer Zahl gesetzt, deren Höhen sich für die Oberfläche addieren. Wenn also die erste Pyramide mit der Spitzenhöhe 100m gesetzt wird, wird ein Punkt P im unteren Teil der Flanke auf beispielsweise 30m angehoben. Wenn später eine weitere Pyramide mit Spitzenhöhe 15m zufälligerweise in die Nähe von P gesetzt wird, erhält P von dieser zweiten Pyramide nochmals z.B. 7.5m Höhe (wenn er in der Mitte der Flanke sitzt), insgesamt also 37.5 m. Aus den Höhen aller Punkte ergibt sich die Oberfläche unserer Landschaft. Sie zeichnet sich dadurch aus, dass sie aus der Ferne betrachtet (die Details verschwinden, nur die groben Züge sind zu sehen) gleich aussieht wie aus der Nähe (nur ein kleiner Ausschnitt ist sichtbar; die grossen Züge sind im kleinen Ausschnitt nicht erkennbar, aber die Details sind jetzt sichtbar). Der Mathematiker nennt diese Eigenschaft "selbstähnlich".
Im Programm wird die Höhe eines Punktes durch seine Farbe
dargestellt: beginnend bei Schwarz über Blau und Grün zu weiss,
je höher, desto heller.
Um zu interessanten Landschaften zu kommen, wird auf einer
Fläche von 400 x 300 Punkten mit zwei Pyramiden mit der Höhe
von 128 Einheiten begonnen. Für die weiteren Schritte wird die
Zahl der Pyramiden jeweils, die Höhe jeweils halbiert
vervierfacht (im zweiten Schritt also 8 Pyramiden mit der Höhe
64). Das wird solange fortgesetzt, bis die Pyramiden im letzten
Schritt eine Höhe von 1 haben. Nach jedem Schritt wird die
Landschaft neu gezeichnet und erhält dadurch laufend mehr
Details.
Falls die Landschaft etwa einem natürlichen, zerklüfteten Gebirge entspricht, ist die Aufgabe gar nicht so einfach (d.h, es gibt keinen einfachen Algoryhtmus). Es reicht z.B. nicht, von einem beliebigen Punkt aus immer nur bergauf zu gehen, um dann auf dem Gipfel festzustellen, dass es einen noch höheren Gipfel gibt, den man aber nur erreicht, indem man zuerst wieder bergab wandert. Um den höchsten Punkt sicher zu finden, bleibt nichts anderes übrig, als jeden Punkt zu messen und den höchsten herauszusuchen. Bei sehr vielen Punkten (bei richtigen GA's mit vielen Dimensionen) würden dazu u.U. sogar leistungsfähige Computer Jahre brauchen.
Im vorliegenden Fall können ohne nennenswerten Aufwand alle 120'000 Punkte durchsucht werden. Das Ergebnis wird angezeigt und dient als Vergleichswert für den Erfolg des GA. Im wirklichen Leben kommen aber manchmal Probleme vor, bei denen die Höhe des höchsten Punkts nicht bekannt ist.
Diese Art GA geht auf Whitley (1988, 1989) zurück und heisst Genitor. Sie passt sehr gut zu fraktalen Landschaften: Die Nachkommen liegen jeweils zwischen Eltern mit hoher Fitness (d.h. solche, die an hohen Stellen in der Landschaft liegen), womit die Bereiche zwischen fitten Käfern besonders intensiv erforscht (durch Käfer besiedelt) werden. Das geschieht zuerst über die ganze Landschaft; mit der Zeit konzentriert sich die Population und damit die Suche nach dem höchsten Punkt langsam auf die schon gefundenen Hügel, wo sie auf einem kleineren Gebiet, dafür aber mit höherer Intensität, weitergeht. Zuerst werden also die interessanten Gebiete ausgewählt, dann werden nur noch diese genauer unter die Lupe genommen. Spannend ist es, wenn es zwei Teilpopulationen auf etwa gleich hohen Hochplateaus gibt: Welcher wird es gelingen, sich durchzusetzen ? (Das ist übrigens der Grund, warum die Landschaft ausgehend von zwei Pyramiden gebaut wird.).
Daneben gibt es noch viele andere Arten von GA, die z.B. bei jeder Generation soviele Nachkommen erzeugen, wie es Eltern hat und dann die Eltern sterben lassen. Der Genitor lässt sich aber relativ einfach programmieren.
Die Verwandschaft mit der Evolution wird mit folgendem Modell augenfällig: Der Ort, wo sich ein Käfer befindet, entspricht seinem genetischen Code. Er besteht in diesem Fall aus zwei Koordinaten (zwei Gene), die zwischen 1 und 300 bzw. 1 und 400 liegen. Der genetische Code des Nachkommens ist eine zufällige Kombination desjenigen seiner Eltern; seine beiden Koordinaten liegen irgendwo zwischen denjenigen seiner Eltern. Die ganze Evolution des GA basiert also im vorliegenden Fall auf der Rekombination der vorhandenen, mit der zufälligen Anfangspopulation erzeugten Merkmale. Eine Mutation, die völlig neue Merkmale erzeugen würde, ist nicht eingebaut. Es ist aber möglich, GA's zu bauen, die Mutationen zufällig einbauen.
Beim Rekombinationsschritt werden alle Käfer in einer Liste nach steigenden Höhen sortiert. Für die Auswahl zur Rekombination wird dann die Rangzahl in der Liste betrachtet und nicht die ursprüngliche Fitness. Damit wird erreicht, dass auch dann noch, wenn sich die Population auf eine Gebirgskuppe zurückgezogen hat und sich die Höhen der einzelnen Käfer viel weniger unterscheiden als wenn sie über die ganze Landschaft verteilt sind, möglichst Käfer mit einer grossen Höhe bevorzugt werden.
Der Nachkomme entsteht gleichverteilt über das aufgespannte Rechteck: Die Wahrscheinlichkeit, in einem beliebigen Feld mit einer Fläche von einem Hunderstel vom Rechteck zu entstehen, ist immer genau 1/100; egal wo das Feld im Rechteck liegt.
Beim Selektionsschritt ist die Wahrscheinlichkeit, aus der Population entfernt zu werden, umgekehrt proportional zur Fitness. Hier wird also nicht eine Rangfolge berücksichtigt, sondern direkt die Fitness.
Es gibt keine Garantie, dass beim Ende des Algorithmus auch die beste mögliche Lösung gefunden wurde. Das hier gewählte Abbruchkriterium (alle Käfer haben dieselbe Höhe) entspringt eher dem Bedürfnis nach einer effizienten Programmierung als einer theoretischen Überlegung. Tatsächlich könnten die Käfer alle auf derselben Höhe liegen, aber es könnte zwischen ihnen einen noch höheren, unbesiedelten Punkt geben, der auch noch gefunden würde, wenn der GA weiterliefe. Deshalb ist das gängigste Abbruchkrierium, wenn alle Individuen denselben genetischen Code haben (alle Käfer würden an derselben Stelle liegen). Dann ist auch ein Weiterlaufen des GA nicht mehr interessant, denn es kann nichts neues mehr entstehen, jedenfalls nicht ohne Mutation. Ein anderes mögliches Abbruchkrierium ist, einfach die Anzahl Schritte vorzugeben.
Um die Funktion eines GA zu erklären wird meist das Schema Theorem, das Holland 1975 veröffentlicht hat, herangezogen. Eine Analogie zwischen dem vorgestellten GA und dem Schema Theorem ist aber nicht offensichtlich.
Die viel einfachere Beobachtung, dass bei jedem GA die Distanz vom Nachkommen zu je einem Elter kleiner oder gleich der Distanz zwischen den Eltern untereinander ist, trifft allerdings auch für den vorliegenden GA zu. Man kann vermuten, dass ein solches Vorgehen für selbstähnliche Landschaften erfolgreich ist, was mit ein paar Experimenten mit dem vorliegenden Programm auch bestätigt wird. Das stimmt überein mit der Beobachtung von Terry Jones, wonach die Fitness-Distanz-Korrelation ein Mass sein kann für die Schwierigkeit eines Problems für einen GA.
Mit der Distanzierung vom Schema Theorem kann auch darauf verzichtet werden, Schemas zu erhalten, was als starkes Argument für das Ein- oder Zweipunkt-Crossover gilt. In vielen Fällen ist die Reihenfolge der Bits im Genotyp eher willkürlich, so dass konsequenterweise ein "uniform crossover" gewählt werden sollte. Das Analogon zum uniform crossover, wo kein Zusammenhang zwischen den einzelnen Genen bezüglich ihrer Ererbung vom einen oder anderen Elter besteht, ist mit der Auswahl des Nachfahren aus dem Rechteck zwischen den Eltern gegeben. Dabei sind die Anteile des einen wie des anderen Elter in beiden Koordinaten, die im vorliegenden Fall als Gene betrachtet werden, unabhängig voneinander. Andere Möglichkeiten wäre etwa die Wahl des Nachfahren auf der Diagonalen zwischen den Eltern (Korrelation des Elternanteils auf beiden Genen) oder auf dem Mittelpunkt der Diagonalen. Es wäre interessant, den Einfluss dieser Anpassung auf die Leistung des GA zu untersuchen.
Whitley, D., and Kauth, J. (1988) GENITOR: a Different Genetic Algorithm. Proceedings of the Rocky Mountain Conference on Artificial Intelligence, Denver, CO. pp 118-130 zitiert in Whitley D, A Genetic Algorythm Tutorial, Colorado State University
Geoffrey Horn, Genetic Algorythms, Problem Difficulty, and the Modality of Fitness Landscapes, Illigal Report No 95004, 1995
Jones, T., and Forrest, S., Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms; Sixth international conference on genetic Algorithms
Im Internet bieten viele Universitäten Literaturlisten, die z.T. heruntergeladen werden können. Zwei Beispiele:
Daneben führt das private Santa-Fe-Institute ein Projekt Evolving Cellular Automata ( www.santafe.edu/projects/evca ) durch.
Folgende Stichworte können z.B. in Altavista verwendet werden: genetic algorithms, evolutionary computation.
zurück zur Homepage: Ursula und Pascal Glauser's Homepage