Evolutionäre Strategien und multitome Optimierung

by Rosé, Helge

Für die erfolgreiche Lösung eines Optimierungsproblems ist die Wahl der verwendeten Suchstrategie von entscheidender Bedeutung. Die vorliegende Arbeit untersucht die Kriterien dieser Wahl. Dabei stellen sich drei grundlegende Fragen: Welche Strategien der Optimierung eines gegebenen Problems existieren überhaupt, und was für Eigenschaften besitzen sie? Wodurch wird der Charakter eines Optimierungsproblems bestimmt, und gibt es Klassen ähnlicher Probleme? Besteht eine Verbindung zwischen den Eigenschaften der Strategien und den Klassen der Probleme, die es ermöglicht, für jede Problemklasse eine geeignete Optimierungsstrategie anzugeben? Dazu wird zuerst die Klasse der Evolutionären Algorithmen naher betrachtet, deren generelles Verhalten die Boltzmannstrategie, Darwinstrategie oder Boltzmann-Darwin-Strategie beschreiben. Als weiteres Beispiel wird die Multitome Strategie untersucht. In ihr wird das Problem unter verschiedenen Gesichtspunkten betrachtet und in Einzelanforderungen zerlegt, die abwechselnd optimiert werden. Für den speziellen Fall der Dichotomen Strategie wird die allgemeine zeitabhängige Lösung mit Hilfe der Methode der Charakteristiken bestimmt. Zur Beantwortung der zweiten Frage wird die Zustandsdichte als klassifizierende Größe des Optimierungsproblems eingeführt. Sie kann unter Verwendung der Boltzmannstrategie während des Optimierungslaufes durch zwei allgemeine Approximationsmethoden: die Methode der stationären Verteilungen und die Eigenvektormethode bestimmt werden. Aus der Zustandsdichte erhält man den Wirkungsgrad der Zufallssuche. Er charakterisiert den Ordnungsgrad des Problems und stellt damit ein wichtiges Maß der Problemschwierigkeit dar. Die entscheidende dritte Frage wird für Probleme der Optimierung frustrierter Sequenzen, der Netzwerkoptimierung und für das Faltungsproblem der RNA behandelt. Mit der Einführung der Klassen gerichteter und ungerichteter Strategien, die für Optimierungsprobleme mit niedrigem bzw. hohem Wirkungsgrad der Zufallssuche effektiv sind, kann eine Verbindung zwischen dem Strategieverhalten und dem Problemcharakter hergestellt werden, die es ermöglicht, für eine konkrete Optimierungsaufgabe die Klasse der geeigneten Strategien zu wählen.