Evolutionre Algorithmen (EA)


(Contents)(Previous)(Next)

Evolutionäre Algorithmen (EA)

Vorbild bei der PSO war das Suchverhalten eines Schwarms, bei dem sowohl Physik als auch Biologie eine Rolle spielen. Evolution wird von vielen Forschern als das Optimierungsproblem der Biologie par excellence betrachtet und ist zunehmend zum Vorbild für Optimierungsprogramme geworden. Dabei ist allerdings nicht sehr klar, wie die Evolution "funktioniert". Seit Darwin wurden unterschiedlichste Vorstellungen (Selektion, Überleben des Fittesten, Mutation, Reproduktion, geschlechtliche Fortpflanzung, usw.) entwickelt, welche aber nie mathematisch präzisiert wurden. Recht grobe Analogien führten zu unterschiedlichsten evolutionären Optimierungsverfahren, welchen gemein ist, dass mit Populationen gearbeitet wird. Wir verwenden für derartige Verfahren den Oberbegriff evolutionäre Algorithmen.

Im folgenden betrachten wir die berühmtesten Varianten, Evolutions Strategien (Evolution Strategy - ES), evolutionäre Programme (Evolutionary Programming EP), genetische Algorithmen (Genetic Algorithms GA) und genetische Programme (Genetic Programming GP). N.B. auch PSO kann zu den evolutionären Algorithmen gezählt werden, obwohl hier im biologischen Sinne keine Evolution stattfindet.

Eine wichtige Frage ist, ob Evolution sich auf der Ebene der Individuen oder auf der Ebene der Spezies abspielt. Konkurrieren beispielsweise Hunde untereinander oder Hunde mit Katzen? Je nach Auffassung ergeben sich natürlich unterschiedlich ausgeprägte EA.

Eine zweite Frage ist, welches mathematische Objekt als Individuum aufgefasst werden soll. Auch hier gibt es unterschiedlichste Möglichkeiten.

Leider wurden verschiedene Begriffe eingeführt und miteinander vermischt, so dass die Namengebung eher verwirrend ausgefallen ist und die Begriffe nicht einheitlich verwendet werden. So versteht man beispielsweise unter Algorithmus bei GA meist einen Bitstring, welcher als Algorithmus aufgefasst werden kann, bei EA hingegen ein Optimierungsverfahren. Bei EP wird unter Programm eine Zustandsmaschine, bei GP hingegen eine Funktion oder eine Subroutine verstanden. Statt EA wird auch Evolutionsprogramme als Oberbegriff benutzt.

Allen Verfahren gemein ist das Arbeiten mit einer Population von Individuen, wobei jedes Individuum einem Lebewesen oder aber einer Art, Gattung oder Spezie entsprechen kann. Es wird angenommen, dass die Individuen miteinander konkurrieren und dass es ein Mass für die Qualität jedes Individuums gebe. Diese Mass wird Fitness genannt. In der Natur ist oft unklar, welche Faktoren zur Fitness eines Individuums beitragen, bei der Züchtung hingegen bestimmt der Züchter die Fitness. Bei der Züchtung hat man deshalb eine ausgeprägt zielgerichtete Form der Evolution. Hier ist nicht nur die Fitness recht klar definiert, sondern auch der Prozess der Auswahl (Selektion) und Reproduktion. Fitness spielt damit einerseits für das Überleben der Individuen und andererseits bei der Auswahl der Eltern eine Rolle, wobei für beide Formen der Selektion unterschiedliche Merkmale zum Tragen kommen. Die heute bekannten EA Varianten arbeiten jedoch mit einer einzigen Fitness Definition. Wichtig ist, dass eine streng zielgerichtete Selektion zu einer relativ raschen Evolution führt, welche jedoch nach kurzer Zeit stagniert, weil sich die gesamte Population rasch auf ein lokales Optimum hin bewegt und sich davon nicht mehr lösen kann. Mathematisch wird die Selektion durch einen Selektionsoperator beschrieben. Dabei muss dem Zufall ausreichend Platz eingeräumt werden um eine zu rasche Verengung der Population zu verhindern.

Bei der Züchtung wird vor allem auf die geschlechtliche Fortpflanzung mit Kreuzung (crossover) und Mutation abgestellt, wobei die Mutation eine bescheidene Rolle spielt. Da die entsprechenden Mechanismen auf der Ebene der Gene einigermassen verständlich sind, implementieren die "genetischen" Varianten von EA die zu optimierenden mathematischen Objekte als Genom. Wichtig ist dabei die Unterscheidung von Genotyp und Phänotyp. Letzterer ist die Ausprägung des Individuums in seiner Umwelt. Bei den Varianten von EA mit dem Attribut "evolutionär" wird auf diese Unterscheidung meist verzichtet.

In der Natur beobachtet man prinzipiell ungeschlechtliche Fortpflanzung und geschlechtliche Fortpflanzung mit zwei Eltern. Diese Einschränkung kann bei der Entwicklung von EA aufgehoben werden, d.h., man kann Algorithmen schreiben, bei denen jedes Kind ein, zwei, oder mehrere Eltern hat. Prinzipiell vermischt sich dabei die Information der Eltern (sofern nicht nur ein Elter existiert). Mathematisch lässt sich diese Fortpflanzung durch einen Rekombinationsoperator beschreiben.

Insbesondere bei der ungeschlechtlichen Fortpflanzung (mit einem Elter) ergibt sich keinerlei Evolution, da die Kinder mit den Eltern identisch sind. Im Falle der Züchtung ergäbe sich hier lediglich eine sofortige Ausrottung der weniger fitten Individuen. Damit eine Evolution stattfinden kann ist zumindest eine minime Veränderung von Generation zu Generation erforderlich. Dies ist die Mutation. Man weiss, dass grosse Mutationen eine kleine Chance haben, ein fitteres Individuum hervorzubringen. Je kleiner die Mutation, um so ähnlicher sind Kind und Elter. Offensichtlich ist dies eine Form der Nachbarschaftssuche mit dem Motto: "Der Apfel fällt nicht weit vom Stamm". Auch die Mutationen können mathematisch mit einem Mutationsoperator beschrieben werden.

Betrachtet man den Stammbaum eines Individuums, so unterscheidet man verschiedene Generationen. In der Natur sind die Generationen allerdings nicht sauber getrennt. Bei den meisten EA Varianten werden die Generationen strikt getrennt und alle Individuen leben damit genau eine Generation lang. Ausserdem wird meist mit einer festen Populationsgrösse gearbeitet. Dies vereinfacht die Struktur der Algorithmen und insbesondere die Speicherverwaltung, hat aber neben der ungenauen Abbildung des natürlichen Vorbilds auch Nachteile. So kann beispielsweise die Fitness des besten Individuums von einer Generation zur nächsten abnehmen.

Da die erste Population üblicherweise rein zufällig erzeugt wird, ist klar, dass EA welche mit grossen Populationen und wenige Generationen arbeiten nahe bei der Zufallssuche liegen, und somit eine relativ gute Chance haben, bei komplizierten Fitnesslandschaften auf brauchbare Lösungen zu stossen. Gleichzeitig sind solche EA bei einfacheren Fitnesslandschaften zu wenig zielstrebig und damit ineffizient. Schliesslich ist zu beachten, dass die Fitnessberechnung bei vielen praktischen Problemen sehr rechenintensiv ist, so dass sehr grosse Populationen gar nicht in Frag kommen.

Neben der Initialisierung spielt der Zufall bei allen EA auch bei Selektion, Rekombination und Mutation eine grosse Rolle. Das richtige Mass an Zufälligkeit ist problemabhängig und hat einen starken Einfluss auf die Effizienz.

Im folgenden skizzieren wir einige Ausprägungen von EA und werden dann auch die verschiedenen Probleme verdeutlichen.


(Contents)(Previous)(Next)