Theoretische Analyse evolutionärer Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumen

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.