Randomisierte Suchheuristiken auf Plateaus, Fachbücher von Bastian Krol

In dieser Arbeit wird das Verhalten randomisierter Suchheuristiken und evolutionärer Algorithmen (insbesondere RLS und (1 + 1)EA) auf pseudobooleschen Fitnessfunktionen, die zusammenhängenden Gebiete mit konstanter Fitness (Plateaus) enthalten, untersucht. Einige ausgewählte beispielhafte Funktionen mit Plateaus werden untersucht und untere und obere Schranken gezeigt. Die Untersuchung erfolgt mit einer bisher im Kontext evolutionärer Algorithmen neuen Methode, der Widerstandsmethode. Mit Hilfe dieser Methode werden allgemeine Schranken für eine bestimmte Klasse von Plateau-Funktionen (Ein-Ziel-Plateaus) bewiesen. Es wird gezeigt, dass diese Schranken asymptotisch genau sind. Im weiteren Verlauf werden noch einige andere Klassen von Plateau-Funktionen (Mehr-Ziel-Plateaus) untersucht und miteinander verglichen.