Publikation

Heuristic Optimization Software Systems

Outline:

S. Wagner - Heuristic Optimization Software Systems - Phd Thesis, Johannes Kepler Universität Linz, Österreich, 2009, pp. 139

Abstract:

Viele Optimierungsprobleme können aufgrund ihrer Komplexität und der Größe des Lösungsraums nicht effizient mit klassischen mathematischen Optimierungsverfahren gelöst werden. Um dennoch Lösungen von möglichst hoher Qualität zu erzielen, werden daher oft heuristische Optimierungsverfahren eingesetzt. Diese Algorithmen haben nicht den Anspruch, global optimale Lösungen zu finden, sondern sind durch einen Kompromiss zwischen benötigter Laufzeit und erzielter Lösungsqualität für den Einsatz in der Praxis besonders gut geeignet. Die erfolgreiche Anwendung von heuristischen Optimierungsverfahren in unterschiedlichen Problemdomänen hat in den letzten Jahrzehnten zu einer Vielfalt von Optimierungsparadigmen geführt, die oftmals auch natürliche Prozesse zum Vorbild haben (z.B. evolutionäre Algorithmen, Simulated Annealing oder Ant Colony Optimization). Für die Entwicklung und den Einsatz von heuristischen Optimierungsverfahren im wissenschaftlichen und industriellen Umfeld werden ausgereifte und flexible Softwaresysteme benötigt, die zum einen Wissenschaftler bei der Entwicklung neuer Verfahren unterstützen und zum anderen Benutzern eine einfache Anwendung verschiedener Verfahren auf spezifische Optimierungsprobleme sowie eine homogene Integration in bestehende Softwaresysteme ermöglichen. Die Heterogenität der Anforderungen dieser beiden Benutzergruppen und die Vielzahl an verschiedenen Algorithmen und Optimierungsproblemen stellt Softwareentwickler dabei jedoch vor etliche Herausforderungen. Bestehende Systeme weisen in vielen Fällen gravierende Schwächen im Bezug auf Erweiterbarkeit, Flexibilität, Modularität und Benutzerfreundlichkeit auf. Spezifisch an bestimmte Optimierungsparadigmen angepasste Algorithmenmodelle verhindern die Erweiterung mit neuen Verfahren, unzureichende Modularisierung erschwert die Integration in bestehende Systeme und fehlende graphische Benutzerschnittstellen reduzieren die Benutzerfreundlichkeit und erhöhen den Lernaufwand. Die Überwindung dieser Mängel ist das zentrale Ziel dieser Arbeit. Basierend auf einer umfassenden Anforderungsanalyse sowie einer Gegenüberstellung bestehender Lösungen wird ein neues Design für Softwaresysteme zur heuristischen Optimierung entwickelt. Kernaspekte stellen dabei eine auf Plugins basierende Architektur, ein domänenunabhängiges Modell zur Beschreibung beliebiger Algorithmen, die Unterstützung von graphischen Benutzerschnittstellen, sowie die Integration paralleler Algorithmen dar. Diese Aspekte dienen als Grundlage für die Entwicklung neuer heuristischer Optimierungssysteme. Als Abschluss der Arbeit wird anhand einiger heuristischer Optimierungsalgorithmen exemplarisch gezeigt, wie diese Verfahren flexibel und wiederverwendbar umgesetzt werden können.

Downloads: