Vorlesungsinhalt
Evolutionäre Algorithmen basieren auf einer allgemeinen Idee,
Optimierungsprobleme zu bearbeiten. Dabei wird eine Menge (Population)
von aktuellen Suchpunkten oder Lösungsmöglichkeiten mit Ihrer
Bewertung (Fitness) verwaltet. Beim TSP stellt ein Suchpunkt eine Tour
dar, die mit Ihren Kosten bewertet wird. An Hand dieser Information
werden neue Suchpunkte zufallsgesteuert erzeugt. Mit lokalen
Suchoperatoren (Mutationen) werden aus einzelnen Suchpunkten neue
Suchpunkte erzeugt, die bevorzugt in der Nähe des alten
Suchpunktes liegen. Mit Rekombinationsoperatoren (Crossover) werden
aus Suchpunkten neue Suchpunkte erzeugt, die von jedem der Suchpunkte
(Eltern) Informationen übernehmen. Der neue Suchpunkt (Kind) liegt
also "zwischen den Eltern". Welche Suchpunkte zur Erzeugung neuer
Suchpunkte herangezogen werden und welche der alten und neuen
Suchpunkte erhalten bleiben (die nächste Generation bilden), wird
in Abhängigkeit der Bewertungen deterministisch oder randomisiert
entschieden (Selektion).
Evolutionäre Algorithmen bilden eine
Alternative zu problemspezifischen Algorithmen,
wenn (wie so oft) Zeit, Geld oder Kenntnisse
fehlen, um einen guten speziellen Algorithmus zu
entwerfen oder nicht alle Problemparameter
bekannt sind und Bewertungen nur durch
Experimente oder Simulationen zu erhalten
sind. Sie haben sich in Anwendungen vielfach
bewährt.
Die Vorlesung befasst sich mit der Optimierung
auf endlichen Suchräumen. In einem ersten
Teil (für den ein Skript bereitsteht)
werden allgemeine Entwurfsprinzipien für
evolutionäre Algorithmen vorgestellt und
die Klasse evolutionärer Algorithmen wird
mit anderen randomisierten Suchverfahren (wie
z. B. Simulated Annealing) verglichen. Dazu
werden ältere Theorieansätze
diskutiert. Danach werden evolutionäre
Algorithmen auf verschiedenen Problemen
analysiert. Aus der Abschätzung der zu
erwartenden Optimierungszeit ergeben sich
Hinweise, wie die Parameter in den jeweiligen
Situationen möglichst eingestellt werden
sollten. Eine derartige Analyse stellt einen
neuen und hochaktuellen Zweig bei der
Betrachtung evolutionärer Algorithmen dar
und schließt die Lücke zwischen dem klassischen
Gebiet "Effiziente Algorithmen" und der Theorie
randomisierter Suchheuristiken. In diesem Teil
der Vorlesung werden vornehmlich Ergebnisse
unserer Arbeitsgruppe behandelt, sodass die
Vorlesung auch als ideale Vorbereitung auf eine
von mir betreute Diplomarbeit dienen kann.
Home
Winter 04/05
Universität Dortmund