Eine Vielzahl planerischer Optimierungsprobleme aus unterschiedlichsten Anwendungsbereichen wie Logistik, Produktion, Bioinformatik, Elektrotechnik, Netzwerkdesign, etc. lassen sich effizient mit heuristischen Methoden und Metaheuristiken lösen. Eine Metaheuristik ist hierbei ein übergeordneter Algorithmus, welcher eine oder mehrere abhängige Algorithmen bzw. Heuristiken bei der Lösungssuche steuert.
Da sich viele der praktischen Problemstellungen auf eine gemeinsame abstrakte Struktur zurückführen lassen, wurden zur effizienten, zeitsparenden Implementierung von problemangepassten Metaheuristiken Programmierframeworks entwickelt.
Vorliegende Arbeit gibt einen Überblick über frei im Internet verfügbare und kommerzielle Frameworks. Nach der Darstellung wichtiger Grundlagen wurden diese hinsichtlich für die Softwareentwicklung relevanter Kriterien, wie Anzahl und Art der in den Frameworks enthaltenen Algorithmen, verwendete Programmiersprache, Ausführlichkeit und schnelle Verständlichkeit der Dokumentation bewertet.
Es wurde ein grafisches Eigenschaftsprofil abgeleitet, welches die Stärken und Schwächen der ausgewählten Frameworks zeigt und zusammen mit in der Arbeit erstellten Eigenschaftstabellen bei der Auswahl eines geeigneten Frameworks für eine konkrete Entwicklungsaufgabe, oder der Weiterentwicklung der Frameworks selbst, helfen kann.
Inhaltsverzeichnis
1 Zielsetzung der Studie
2 Metaheuristiken
2.1 Einfache lokale Suchverfahren
2.2 Lagrange-Heuristiken
2.3 GRASP
2.4 Simulated Annealing
2.5 Tabu Search
2.6 Genetische und evolutionäre Algorithmen
2.7 Ameisenalgorithmen
3 Frameworks für Metaheuristiken – allgemeine Konzepte
4 Vergleich ausgewählter Frameworks
4.1 Kriterien zum Vergleich der Frameworks
4.2 Vergleich der Frameworks nach der Art der mitgelieferten Algorithmen
4.3 Vergleich der Frameworks nach weiteren Kriterien
4.4 Gesamtbewertung der Frameworks
5 Zusammenfassung und Ausblick
Zielsetzung & Themen der Arbeit
Die vorliegende Seminararbeit verfolgt das Ziel, einen strukturierten Überblick über frei verfügbare sowie kommerzielle Programmier-Frameworks zur Implementierung von Metaheuristiken zu geben. Dabei wird untersucht, wie diese Werkzeuge Entwickler bei der Lösung komplexer, NP-schwerer Optimierungsprobleme unterstützen können, indem sie generische Softwarearchitekturen zur Verfügung stellen.
- Grundlagen der wichtigsten Metaheuristiken (z.B. Simulated Annealing, Tabu Search, Genetische Algorithmen).
- Konzeptionelle Anforderungen an Software-Frameworks für die Metaheuristik-Entwicklung.
- Kriterienbasierte Klassifizierung und Vergleich verschiedener existierender Frameworks (z.B. HotFrame, EasyLocal++, HeuristicLab).
- Bewertung der Frameworks hinsichtlich ihrer Anwendungsreife, Dokumentationsqualität und Algorithmenvielfalt.
Auszug aus dem Buch
2.5 Tabu Search
Tabu Search ist eine auf der lokalen Suche aufbauende Metaheuristik. Hierbei verhindert man ein Zurückkehren in ein lokales Optimum durch inverse Züge (nach wenigen Zügen weg von diesem) indem man einen Mechanismus zur Steuerung der lokalen Suche einführt. Im Gegensatz zu Simulated Annealing, welches zum Vermeiden dieser so genannten „Zyklen in der Suche“ den Faktor „Zufall“ verwendet, kommt in Tabu Search ein Gedächtnisspeicher zum Einsatz. Hierbei findet ein sog. attributiver Speicher Anwendung. In diesem Speicher werden Eigenschaften (Attribute) von Lösungen und Zügen abgelegt. Vor Ausführung eines Zuges wird nachgesehen ob eine Kombination aus Attributen darauf hinweist, dass eben dieser Zug schon einmal ausgeführt wurde. In diesem Fall ist der Zug als „tabu“ deklariert und wird nicht ausgeführt, da die zu Grunde liegende Lösung wahrscheinlich schon untersucht wurde. Der Speicherbedarf lässt sich im Gegensatz zu einer vollständigen Speicherung aller Lösungen auf dem Weg der Suche durch einen attributiven Speicher klein halten.
Nachteilig ist allerdings, dass verschiedene Übergänge oder Lösungen ähnliche Attribute aufweisen können, so dass auch eine bisher nicht untersuchte Lösung als „tabu“ erklärt werden kann (vgl. [8]). In gewissem Maße kann dies jedoch durch die „Tabu-Restriktionen“ gesteuert werden, welche mehr oder weniger restriktiv gewählt werden können. Tabu-Search-Implementierungen unterscheiden sich unter anderem auch durch den verwendeten attributiven Speicher.
Zusammenfassung der Kapitel
1 Zielsetzung der Studie: Einleitung in die Problematik NP-schwerer Optimierungsaufgaben und Darstellung des Nutzens von Metaheuristik-Frameworks.
2 Metaheuristiken: Systematisierung und theoretische Einführung in klassische Verfahren wie Simulated Annealing, Tabu Search und Genetische Algorithmen.
3 Frameworks für Metaheuristiken – allgemeine Konzepte: Erläuterung der zugrunde liegenden Domain-Engineering-Konzepte und der Architektur von Metaheuristik-Software.
4 Vergleich ausgewählter Frameworks: Detaillierte Evaluation und Gegenüberstellung verschiedener Tools anhand von Kriterien wie Dokumentation, Programmiersprache und enthaltenen Algorithmen.
5 Zusammenfassung und Ausblick: Resümee der Arbeit sowie kritische Einschätzung zur Auswahl geeigneter Frameworks für die Praxis.
Schlüsselwörter
Metaheuristiken, Programmier-Frameworks, Optimierungsprobleme, Simulated Annealing, Tabu Search, Genetische Algorithmen, Softwarearchitektur, Domänenanalyse, Lokale Suche, Algorithmik, Informatik, HotFrame, HeuristicLab, Komplexitätstheorie.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Unterstützung von Softwareentwicklern bei der Lösung schwieriger Optimierungsprobleme durch den Einsatz spezialisierter Programmier-Frameworks für Metaheuristiken.
Was sind die zentralen Themenfelder?
Die zentralen Felder sind die Theorie der Metaheuristiken, das Software-Framework-Design für Optimierungsaufgaben und der systematische Vergleich existierender Softwarelösungen.
Was ist das primäre Ziel der Studie?
Das Ziel ist es, einen Überblick über den Markt der verfügbaren Frameworks zu geben und Entscheidungshilfen für die Auswahl geeigneter Werkzeuge für spezifische Entwicklungsaufgaben zu liefern.
Welche wissenschaftliche Methode wird verwendet?
Es wird ein systematischer Vergleichsansatz angewandt, bei dem Frameworks anhand definierter Qualitätskriterien wie Dokumentation, algorithmische Unterstützung und Flexibilität bewertet und grafisch aufbereitet werden.
Was wird im Hauptteil behandelt?
Im Hauptteil werden zunächst die theoretischen Grundlagen der Metaheuristiken erläutert, gefolgt von der Diskussion allgemeiner Framework-Konzepte und einem detaillierten Vergleich von acht ausgewählten Software-Frameworks.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wesentliche Begriffe sind Metaheuristiken, Frameworks, Optimierungsprobleme, Algorithmik und Software-Wiederverwendung.
Warum spielt die Unterscheidung zwischen Suchverfahren und genetischen Algorithmen eine Rolle?
Diese Unterscheidung ist relevant, da Frameworks häufig spezialisiert sind; einige eignen sich besser für lokale Suchverfahren, während andere ihren Schwerpunkt auf evolutionäre Ansätze legen.
Welchen Stellenwert nimmt die Dokumentation bei der Bewertung ein?
Die Dokumentationsqualität ist ein kritisches Kriterium, da sie maßgeblich darüber entscheidet, wie schnell sich ein Entwickler in die Programmstruktur einarbeiten kann.
Welche Bedeutung hat das grafische Eigenschaftsprofil im Fazit?
Das Netzdiagramm dient als visuelle Entscheidungshilfe, um die Stärken und Schwächen der verschiedenen Frameworks auf einen Blick vergleichbar zu machen.
- Quote paper
- Cand. Wirtsch.-Ing. Christian Luschmann (Author), 2007, Programmierungs-Frameworks für Metaheuristiken, Munich, GRIN Verlag, https://www.grin.com/document/89097
