ISBN 978-3-8439-0118-5

978-3-8439-0118-5, Reihe Informatik

Marcel Kronfeld
Niching Methods in Heuristic Optimization

178 Seiten, Dissertation Eberhard-Karls-Universität Tübingen (2011), Softcover, A5

Zusammenfassung / Abstract

Die Arbeit beschäftigt sich mit dem Bereich der heuristischen Optimierung, welcher die numerische Lösung schwieriger Funktionen zum Ziel hat. Viele praktische Fragestellungen sind aus verschiedenen Gründen analytisch kaum zu lösen, etwa weil sie nichtlinear, nichtkonvex, nicht differenzierbar oder auch verrauscht und nicht stetig sind. Für solche Problemstellungen sind robuste Optimerungsverfahren gebräuchlich, die möglichst wenige Annahmen über die Zielfunktion benötigen und zur Suche nur auf direkte Funktionsauswertungen zurückgreifen. Da komplizierte Zielfunktionen häufig auch zeitaufwändig zu berechnen sind, muss zwischen der raumgreifenden Abtastung des Suchraums und der konzentrierten Suche in lokal vielversprechenden Bereichen abgewogen werden. Die Klasse der populationsbasierten heuristischen Suchverfahren stellt hierfür einen guten Mittelweg dar.

Während typische Suchheuristiken darauf ausgelegt sind, möglichst ein einzelnes, globales Optimum zu identifizieren, kann es in verschiedenen Anwendungen wertvoller sein, eine größere Anzahl guter Einzellösungen zu erhalten. Verfahren, die dies umsetzen, werden in Analogie zum Konzept der „ökologischen Nischen“ als „Niching-Verfahren“ oder „nischenerhaltende Suchverfahren“ bezeichnet.

Aktuell gebräuchliche Niching-Methoden werden häufig anhand niedrigdimensionaler Testfunktionen entwickelt, welche wenig praktische Relevanz aufweisen. Neben der Einführung in Grundlagen heuristischer Suche besteht deswegen ein Hauptteil dieser Arbeit im Vergleich bestehender Niching-Methoden und in deren Erweiterung zur realistischen Anwendbarkeit. Darüber hinaus werden theoretische Eigenschaften der Niching-Verfahren beleuchtet. Eine wichtige Eigenschaft ist dabei die Existenz von verschachtelten Bassins, die auf nicht-korrelierte, hochqualitative lokale Optima hinweisen. Hier muss ein Suchverfahren entscheiden, inwieweit die Suche auf ein erkanntes vielversprechendes Gebiet konzentriert oder aber auf noch unbekannte Gebiete ausgeweitet werden soll. Als prinzipielles Problem kann dies als „Dilemma des Suchenden“ bezeichnet werden. Es wird ein Ansatz vorgestellt, diese Abwägung zwischen explorierender und konzentrierender Suche im Rahmen von schwarmbasierten Niching-Methoden direkt zu beeinflussen. Die Vorgehensweise wird an Zielfunktionen zunehmender Schwierigkeit dargestellt und auf realistischen Anwendungen in höheren Dimensionen verifiziert.