2.2 Evolutionäre Programmierung

Von Fogel, Owens und Walsh ([FOW66]) wurde 1966 die Entwicklung und Anwendung der Evolutionären Programmierung (Evolutionary Programming) berichtet. Sie wendeten diese Methode auf ein relativ kompliziertes Problem an, die Vorhersage einer Kette von Symbolen (sequential symbol prediction).

Die Individuen stellten einfache finite Automaten (finite-state machines) dar. Neue Individuen wurden durch zufällige Änderungen im transition table erstellt. Ein Nachkomme wurde bewertet, indem ein Vergleich der durch das Individuum erzeugten Sequenz von Symbolen mit einer gegebenen Sequenz durchgeführt wurde. Der Prozentsatz der Übereinstimmungen ergab die Güte. Der Nachkomme und sein Elter wurden miteinander verglichen und nur der bessere überlebte. Das schlechtere Individuum wurde verworfen.

Fogel, Owens und Walsh war bekannt, daß so ein Algorithmus in lokalen Minima hängen bleiben kann. Deshalb arbeiteten sie mit einer Population von Individuen. Es wurden genauso viele Nachkommen erstellt, wie Individuen in der Population waren. Durch Selektion wurde die jeweils bessere Hälfte der Eltern und Nachkommen ausgewählt und bildete die neue Population.

Obwohl Mutation als der hauptsächliche Operator angesehen wurde, erwähnten Fogel, Owens und Walsh die Möglichkeit der Verwendung einer Rekombination, die sogar zwischen mehr als zwei Eltern stattfinden könne.

Die Arbeiten von Fogel, Owens und Walsh können als erste erfolgreiche Anwendung Evolutionärer Algorithmen angesehen werden. Sie wurden aber für viele Jahre nicht beachtet bzw. abgelehnt.

Erst in den 80er Jahren kam es wieder zu einer Belebung des Evolutionary Programming. Dies ist insbesondere ein Verdienst von David Fogel, der die über lange Zeit ignorierten Arbeiten seines Vaters wieder aufnahm bzw. fortführte.

In [Fdb92] und [Fdb95] werden ein Überblick sowie eine ausführliche Erläuterung des Ablaufs und der Operatoren des Evolutionary Programming gegeben. Dort werden auch Erweiterungen des Standard-EP, wie z.B. Meta-EP, RMeta-EP und Continous-EP, vorgestellt.

Das Gebiet des Evolutionary Programming ist auch heute noch gut überschaubar, da im Vergleich zu den anderen Schulen Evolutionärer Algorithmen nur wenige Leute auf diesem Gebiet arbeiten. Aber nicht zuletzt durch die seit 1992 jährlich stattfindende internationale Konferenz zu Evolutionary Programming (z.B. [EP96]) und die Evolutionary Programming Society ist das Interesse in den letzten Jahren stetig angestiegen.

Diese Dokument ist Teil der Dissertation von Hartmut Pohlheim "Entwicklung und systemtechnische Anwendung Evolutionärer Algorithmen". This document is part of the .
The is not free.
© Hartmut Pohlheim, All Rights Reserved, (hartmut@pohlheim.com).