Authors: Jansen, Thomas
Title: Theoretische Analyse evolutionärer Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumen
Language (ISO): de
Abstract: Evolutionäre Algorithmen sind allgemeine, randomisierte Suchverfahren, die in verschiedenen Bereichen erfolgreich eingesetzt werden. Ein wichtiges und typisches Anwendungsgebiet ist die Optimierung. In dieser Arbeit werden evolutionäre Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumen, konkret bei der Maximierung pseudo-boolescher Funktionen, theoretisch analysiert. Dabei werden vor allem einfache evolutionäre Algorithmen auf konkreten, typischen Zielfunktionen oder Klassen von Zielfunktionen bezüglich ihrer Effizienz untersucht. Als Maße der Effizienz dienen dabei die erwartete Laufzeit und die Wahrscheinlichkeit pt, mit der nach t Zielfunktionsauswertungen ein globales Maximum erreicht wird. Die Analyse beginnt nach einer allgemeinen Einführung, in der Grenzen und Möglichkeiten evolutionärer Algorithmen sehr grundsätzlich diskutiert werden, mit dem vielleicht einfachsten evolutionären Algorithmus, dem (1+1) EA. Wesentliche Ergebnisse sind vor allem die asymptotisch exakte Bestimmung der erwarteten Laufzeit für die Klasse der linearen Funktionen und eine exponentielle untere Schranke für eine unimodale Funktion. Ausgehend von diesem sehr einfachen Algorithmus wird das weite Feld evolutionärer Algorithmen erschlossen mittels Analyse von Variationen des (1+1) EA. Variationen der Mutation führen zur Diskussion der Wahl des Mutationswahrscheinlichkeit und motivieren den Entwurf eines einfachen evolutionären Algorithmus mit dynamischer Parametersteuerung, für den die erwartete Laufzeit auf einer Reihe von Funktionen bestimmt wird. Variationen der Selektion führen unter anderem zur Analyse des Metropolis-Algorithmus von Simulated Annealing. Schließlich wird die Analyse ausgedehnt auf "richtige" evolutionäre Algorithmen: für einen speziellen Steady State GA wird auf einer bestimmten Funktionenfamilie nachgewiesen, dass er mutationsbasierte Algorithmen bei weitem schlägt. Neben den konkreten Ergebnissen ist besonders die Bereitstellung verschiedener Methoden, mit denen sowohl obere als auch untere Schranken für die erwartete Laufzeit eines evolutionären Algorithmus bestimmt werden können, wichtig.
Subject Headings: (1+1) EA
Evolutionäre Algorithmen
Fitnesslandschaften
Mutation
Optimierung
Rekombination
Simulation
URI: http://hdl.handle.net/2003/2537
http://dx.doi.org/10.17877/DE290R-1190
Issue Date: 2000-10-16
Publisher: Universität Dortmund
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
diss.ps1.84 MBPostscriptView/Open
jansen.pdfDNB1.25 MBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.