2.3 Evolutionsstrategien

Previous PageTable Of ContentsNext Page

Die Entwicklung der Evolutionsstrategien begann in den 60er Jahren an der Technischen Universität Berlin durch Bienert, Rechenberg und Schwefel. Sie bearbeiteten verschiedene Probleme experimentell, die sich nicht analytisch beschreiben ließen und auf die keine traditionellen Methoden angewendet werden konnten. Deshalb entwickelten sie einen einfachen Algorithmus, mit dem die experimentellen Bedingungen verändert wurden. Der Algorithmus basierte auf zufälligen Veränderungen, wobei kleinere Veränderungen wahrscheinlicher waren als große Veränderungen. Wenn die neuen experimentellen Bedingungen eine Verbesserung erbrachten, wurden sie als Ausgangspunkt für die Einstellung neuer Bedingungen genutzt. Ansonsten dienten die vorhergehenden Bedingungen als Ausgangspunkt für weitere Experimente. Mit diesem einfachen Verfahren wurden verschiedene Probleme gelöst, u.a. Widerstandsminimierung einer Gelenkplatte im Windkanal 1964 [Rec73], Optimierung eines Rohrkrümmers [Rec73] und Strukturoptimierung einer Zweiphasen-Überschalldüse [Sch68]. Mit der Verfügbarkeit eines ersten Rechners simulierte Schwefel verschiedene Versionen der Evolutionsstrategie genannten Experimentiermethode auf einem Computer. Andere wendeten nachfolgend die Evolutionsstrategie zur Lösung numerischer Optimierungsprobleme an.

Die ersten Arbeiten mit Evolutionsstrategien verwendeten ein Individuum, das einen Nachkommen produzierte. Ein Nachkomme entstand durch Mutation aus dem Elter. Das in den ersten Experimenten verwendete diskrete Mutationsschema wurde wenig später durch ein kontinuierliches Mutationsschema unter Verwendung normal verteilter Mutationen ersetzt. Das bessere Individuum von Elter und Nachkomme wurde als Elter des nächsten Nachkommen verwendet. Diese einfache Evolutionsstrategie mit zwei Individuen bildete die Grundlage für die weiteren Entwicklungen der Evolutionsstrategie.

Eine Theorie der Evolutionsstrategien sowie ein Überblick über einige der frühen Anwendungen der Evolutionsstrategie wurde von Rechenberg 1973 in [Rec73] veröffentlicht.

Die Verwendung einer vollständigen Population für Evolutionsstrategien wurde von Schwefel entwickelt und u.a. in [Sch75] und [Sch81] vorgestellt. Neben der Verwendung einer Population von Individuen und Rekombination zur Produktion von Nachkommen bezogen diese Evolutionsstrategien außerdem die wichtigsten Parameter des Suchverfahrens (Standardabweichung und Korrelationskoeffizienten der normalverteilten Mutation) in den Optimierungsprozeß mit ein. Dadurch wurden nicht nur die Parameter des Problems optimiert, sondern auch die Parameter der Suchstrategie den aktuellen Gegebenheiten des Optimierungsproblems angepaßt (Selbstadaption der Strategieparameter).

Nachdem es seit dem Ende der 70er Jahre etwas ruhiger um die Evolutionsstrategien geworden war, kam es ab Ende der 80er Jahre zu einem deutlichen Aufschwung des Interesses. Die Weiterentwicklung der Evolutionsstrategien wird auch heute hauptsächlich in Deutschland vorangetrieben. Die Zentren der Aktivitäten liegen an der TU Berlin (Prof. Rechenberg) und an der TU Dortmund (Prof. Schwefel).

In den letzten Jahren wurden viele Arbeiten zu Evolutionsstrategien veröffentlicht. Sehr gut zu lesen ist das Buch von Rechenberg "Evolutionsstrategie 94" [Rec94], in dem er die Weiterentwicklung der Evolutionsstrategien seit [Rec73] darstellt und sich mit anderen Evolutionären Algorithmen auseinandersetzt. Bäck gab in [Bäc96] einen hervorragenden Überblick über Evolutionäre Algorithmen, der Evolutionsstrategien ausführlich behandelt. Schwefel stellt in [Sch95] viele ableitungsfreie Optimierungsverfahren vor, einschließlich einer ausführlichen Darstellung verschiedener Evolutionsstrategien und verglich diese untereinander. Von Ostermeier, Hansen und Gawelzyk wurden in mehreren Arbeiten ([OGH93], [OGH94], [HOG95] und [HO96]) neue Methoden für die Adaption der Strategieparameter einer Evolutionsstrategie (Schrittweitenanpassung der Mutation) vorgestellt.

Die Evolutionsstrategien haben heute einen festen Platz unter den Evolutionären Algorithmen. Dazu haben nicht nur die langjährige Entwicklung und der erfolgreiche Einsatz beigetragen, sondern auch die Ergebnisse zur Theorie der Evolutionsstrategien, u.a. Aussagen zur Fortschrittsgeschwindigkeit ([Rec94], [Bey95]) und der Konvergenz zum globalen Optimum.


Previous PageTable Of ContentsList Of FiguresList Of TablesNext Page

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).