Zu Analyse und Entwurf evolutionärer Algorithmen

Abstract

Evolutionäre Algorithmen sind randomisierte Suchheuristiken, die Prinzipien der natürlichen Evolution verwenden, um Optimierungsprobleme zu lösen. Sie sind auch ohne genaueres Wissen über die Struktur der zu lösenden Probleme schnell einsetzbar, doch sind die Mechanismen, die evolutionäre Algorithmen funktionieren oder scheitern lassen, kaum verstanden. In dieser Arbeit werden evolutionäre Algorithmen zuerst in einem allgemeinen Kontext als Vertreter allgemeiner Suchverfahren untersucht. Hier zeigt sich, dass allgemeine Suchverfahren nur auf relativ kleinen Klassen von Optimierungsproblemen sinnvoll untersucht oder entworfen werden können. Dies motiviert die folgende theoretisch genaue Untersuchung auf klar definierten Funktionsklassen. Da theoretische Grundlagen für evolutionäre Algorithmen recht spärlich gesät sind, wird ein einfacher, aber wichtige Prinzipien verkörpernder evolutionärer Algorithmus, der sogenannte (1+1) EA bezüglich seiner Laufzeit, der Anzahl der Schritte bis zum Erreichen eines Optimums, untersucht. In diesem Hauptteil der Arbeit werden manche Vermutungen bestätigt (für lineare zu optimierende Funktionen) bzw. widerlegt (für unimodale Funktionen). Dabei können auch manche Methoden verallgemeinert werden, um zu untersuchen, wie eine Veränderlichkeit der Akzeptanzwahrscheinlichkeit von Verschlechterungen den Suchprozess beeinflusst oder eine dem bekannten MAXSAT-Problem entspringende Funktion für alle mutationsbasierten evolutionären Algorithmen schwierig ist. Wegen der mangelnden theoretischen Grundlagen gibt es für den Entwurf evolutionärer Algorithmen nur wenige empirisch belegte Daumenregeln. Für den Entwurf problemspezifischer evolutionärer Algorithmen stellen wir Richtlinien vor, in die das Problemwissen in Form einer Metrik auf dem Suchraum eingeht. Die so definierten Metrik-basierten evolutionären Algorithmen sind somit auf die Zielfunktion abgestimmt, ohne dass die Anschaulichkeit der evolutionären Operatoren verloren geht. Empirische Resultate anhand eines Systems der genetischen Programmierung zeigen, dass die Richtlinien zumindest für das betrachtete Benchmark-Problem eine deutliche Leistungsverbesserung bedeuten. Zuletzt wird mittels der Übertragung eines Resultats der Lerntheorie, dem so genannten Occam's Razor Theorem gezeigt, wie für das Lernen nur teilweise bekannter Funktionen mittels genetischer Programmierung nicht-triviale Fehlergarantien gezeigt werden können.