Evolutionäre Algorithmen:
Chancen für die praxisorientierte Optimierung
Prof. Dr. J. Willms

Angewandte Informatik und Mathematik
Fachhochschule Südwestfalen
Meschede

Simulation des Evolutionsprozesses

Nachdem die Bewertungsfunktion festgelegt ist, kann der eigentliche Evolutionäre Algorithmus ablaufen. Viele Optimierungsstrategien gehen von einer geschätzten oder zufällig ausgewählten Anfangslösung aus und versuchen, die Lösung sukzessiv zu verbessern. Hat man nur einen zweidimensionalen Lösungsraum, dann kann man sich das Problem als eine dreidimensionale künstliche Landschaft vorstellen. Die Höhe an einer Stelle entspricht hierbei der Bewertung dieser Stelle.

Beim Maximierungsproblem wird die höchste Erhebung in dieser Landschaft gesucht, beim Minimierungsproblem hingegen die tiefste Stelle. Eine Strategie beim Maximierungsproblem könnte nun sein, an jeder Stelle dem steilsten Anstieg zu folgen. Da die Lösung in jedem Schritt verbessert wird, führt dies zwangsläufig auf einen Gipfel und das Verfahren endet. Jedoch ist in der Regel dies nicht der höchste Gipfel. Ist die Bewertungsfunktion so beschaffen, dass es viele Gipfel unterschiedlicher Höhe gibt, dann ist das beschriebene Verfahren nicht brauchbar, da es nur ein lokales Maximum findet, aber keine Aussage über das globale Maximum machen kann, an dem man eigentlich interessiert ist. Analoges gilt für das Minimierungsproblem.

Man kann das obige Verfahren modifizieren, um sicher zu stellen, dass man nicht sofort im nächsten lokalen Maximum gefangen wird. Simulated Annealing oder Tabu Search sind Beispiele von Modifikationen solcher reinen Verbesserungsverfahren.

Evolutionäre Algorithmen benutzen eine andere heuristische Strategie. Statt einer Lösung werden hier zu jedem Zeitpunkt jeweils eine Menge von Lösungen - man spricht auch von einer Population oder einer Generation von Lösungen - betrachtet. Zu Beginn wird die erste Generation von Lösungen erzeugt. Dies kann zum Beispiel durch eine zufällige Wahl dieser Initialpopulation geschehen. In jedem weiterem Entwicklungsschritt passiert nun zweierlei (siehe Grafik). Wie wir weiter unten erklären werden, werden durch Mutation und / oder Kreuzung aus der bestehenden Lösungspopulation weitere Lösungen gewonnen. Danach findet eine Selektion statt; die besten Lösungen werden (entsprechend der Bewertungsfunktion) für die nächste Generation ausgewählt. Dabei gibt es unterschiedliche Selektionsmechanismen. Neben der deterministischen Auswahl der besten Lösungen werden in der Regel stochastische Selektionsverfahren benutzt, die die Wahrscheinlichkeit einer Auswahl einer Lösung an deren Bewertung koppeln.

Die ständige Wiederholung dieser beiden Schritte entspricht dem in der Evolutionstheorie bekanntem Prinzip "Survival of the fittest". Die Bewertungsfunktion wird daher oft auch als Maß der Fitness angesehen.

Durch eine Mutation wird eine einzelne Lösung verändert. In der Regel ist dies eine geringfügige Änderung und tritt wie in der biologischen Evolutionstheorie zufällig auf. Durch Kreuzung (Crossover) hingegen entsteht eine neue Lösung aus bereits zwei vorhandenen Lösungen. Die durch Kreuzung hervorgegangene Lösung übernimmt Teile der beiden Elternlösungen. Sie entspricht biologisch somit der Vererbung.

Oft wird in der Literatur zwischen Genetischen Algorithmen und Evolutionsstrategien unterschieden. Beide Verfahren sind sehr ähnlich, sie unterscheiden sich im wesentlichen in ihrer Implementierung.

Genetische Algorithmen arbeiten häufig direkt mit einer binären Repräsentation (Binärvektoren) der einzelnen Lösungen (analog der Repräsentation der genetischen Information eines lebenden Organismus als Sequenz von vier Basen der DNA), während Evolutionsstrategien eine Repräsentation in allgemeineren, auch nichtdiskreten Datentypen zulassen. Ferner stehen bei Evolutionsalgorithmen Mutationsmechanismen und deren Steuerung (wie zum Beispiel adaptive Schrittweitenregelung der Mutationsrate) im Vordergrund, während bei Genetischen Algorithmen der binäre Kreuzungsmechanismus als genetische Rekombination eine entscheidende Rolle spielt. Richtungsweisend für die Genetischen Algorithmen war unter anderem die Arbeit von J. H. Holland [4]; die anfänglich hauptsächlich in Deutschland untersuchten Evolutionsstrategien wurden hingegen stark von I. Rechenberg [5] und H.-P.Schwefel [6] beeinflusst.

Allerdings gibt es bei vielen praktischen Anwendungen eine Überschneidung beider Konzepte und die ursprünglich strikte Trennung scheint sich auch in der Theorie mehr und mehr aufzulösen ( z. B. [7]). Im folgenden soll daher - wie mittlerweile üblich - für beide Methoden der Begriff Evolutionäre Algorithmen benutzt werden. Es gibt mittlerweile eine Vielzahl von Veröffentlichungen über Evolutionäre Algorithmen. Aktuelle Zusammenfassungen über Evolutionäre Algorithmen finden sich zum Beispiel in [7], [8] oder im Internet [9]. Das "No free lunch theorem" [10] zeigt allerdings, dass es keinen allgemeinen Evolutionären Algorithmus geben kann, der alle Optimierungsprobleme gleich gut löst. Evolutionäre Algorithmen müssen in der Regel auf das jeweilige Anwendungsfeld zugeschnitten und angepasst werden.

Neben der bereits erwähnten Datenrepräsentation müssen beim Entwurf eines Evolutionären Algorithmus aber noch weitere Fragen geklärt werden. Wie groß soll z.B. eine Population einer Generation gewählt werden und wie viel Nachkommen sollen pro Generation erzeugt werden? Welcher Selektionsmechanismus soll verwandt werden? Welches Abbruchkriterium wird benutzt? Für all diese Fragen gibt die Theorie Evolutionärer Algorithmen keine endgültigen Antworten.


weiter

nach oben

Impressum     Datenschutz
nach oben

29.7.2003