16,99 €
Mehr erfahren.
- Herausgeber: GRIN Verlag
- Sprache: Deutsch
Studienarbeit aus dem Jahr 2007 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,0, Friedrich-Alexander-Universität Erlangen-Nürnberg (Lehrstuhl für Betriebswirtschaftslehre, insbesondere Logistik), Veranstaltung: Hauptseminar "Aktuelle Forschungsfragen der Logistik und des Operations Research", Sprache: Deutsch, Abstract: 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.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Veröffentlichungsjahr: 2008
Ähnliche
Impressum:
Copyright (c) 2013 GRIN Verlag GmbH, alle Inhalte urheberrechtlich geschützt. Kopieren und verbreiten nur mit Genehmigung des Verlags.
Bei GRIN macht sich Ihr Wissen bezahlt! Wir veröffentlichen kostenlos Ihre Haus-, Bachelor- und Masterarbeiten.
Jetzt beiwww.grin.com
Abstract
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.
0 Inhaltsverzeichnis
Abstract
0 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
6 Literaturverzeichnis
7 Verzeichnis der Abbildungen und Tabellen
8 Anhang – Internetseiten der Frameworkprojekte
1 Zielsetzung der Studie
In der Praxis treten eine Vielzahl diskreter (kombinatorischer) planerischer und analytischer Aufgaben in Anwendungsbereichen wie Verkehr, Logistik, Produktionsplanung, Bioinformatik, Life Sciences, chemische Technologie auf, bei welchen eine Optimierung im Sinne verschiedener Zielvorgaben unter Berücksichtigung festgelegter Schranken vorzunehmen ist.
Derartige Probleme sind oft dadurch gekennzeichnet, dass sie im Sinne der Komplexitätstheorie zur Klasse der NP-schweren Probleme gehören (siehe [1]). Zudem sind bei den meisten realen Problemen die Instanzen sehr groß. Diese Eigenschaften führen zu einem hohen Bedarf an Rechenzeit. Um derartige Probleme lösen zu können, werden heuristische Suchverfahren eingesetzt, welche jedoch in der Regel problembasiert sind. Metaheuristiken hingegen sind übergeordnete Algorithmen, welche die Lösungssuche eines oder mehrerer abhängiger Algorithmen steuern, und damit generische Schemata zur Entwicklung heuristischer Methoden (vgl. [2]) darstellen. Mit Hilfe von Metaheuristiken lassen sich praktische Problemstellungen unterschiedlichster Gebiete effizient lösen. Da Metaheuristiken unabhängig von der Problemstellung und den untergeordneten Algorithmen sind, macht es Sinn allgemein verwendbare Programmierumgebungen, so genannte Frameworks, anzulegen.
2 Metaheuristiken
An dieser Stelle soll der Begriff der Metaheuristik kurz diskutiert und eingegrenzt werden. Darauf folgt eine Systematisierung und Vorstellung der wichtigsten Metaheuristiken.
Metaheuristiken werden in der Literatur als generische Schemata zur Entwicklung heuristischer Methoden verstanden (vgl. [1,2]). Als wichtiges Merkmal wird hierbei angesehen, dass eine Metaheuristik eine einfache Heuristik „leitet“. Damit zeichnen sich Metaheuristiken im Vergleich zu einfachen lokalen Suchverfahren dadurch aus, dass Lokale Optima überwunden werden können. Dies ist in Abbildung 1 (S.5.) illustriert.
Abbildung 1: Verhalten einer Suche mit Metaheuristiken in eindimensionaler Nachbarschaft
Einfache lokale Suchverfahren haben die Eigenschaft in lokalen Optima hängen zu bleiben (s. [4,5,6,7]). So würde eine einfache lokale Suche im ersten lokalen Minimum (bei x=10) hängen bleiben und damit das globale Optimum verfehlen. Um dieses globale Optimum zu treffen, muss jedoch zuvor ein lokales Maximum übersprungen werden. Dies leistet eine im einfachsten Fall rein deterministische Abfrage ob ein Suchwert bei Bewegung in eine Richtung kleiner als der vorherige Wert ist nicht. Hierzu werden Metaheuristiken, welche die lokale Suche steuern, notwendig. Diese müssen um die lokalen Optima verlassen zu können, zusätzliche deterministische oder stochastische Ansätze zur Steuerung der untergelagerten Heuristik aufweisen. Ein möglicher Suchverlauf mit einer die lokale Suche steuernden Metaheuristik, einer sog. „stochastic local search“-Methode ist in Abbildung 1 aufgetragen (vgl. [3]).
Aufgrund obiger Problematik ist die Verwendung des Begriffs Metaheuristik in der Literatur nicht konsequent. Teilweise werden einfache lokale Suchverfahren nicht zu den Meta-heuristiken gezählt. Andere Autoren (Glover und Laguna, S.17 [8]) bezeichnen lokale Suchverfahren als „low-level-Metaheuristiken“. Als moderne Metaheuristiken werden heuristische Suchmethoden bezeichnet, welche sich durch die Überwindung lokaler Optima auszeichnen [9]. Neben den klassischen Suchalgorithmen sollen noch neuronale Netzwerke erwähnt werden, welche in weiterem Sinne auch als Metaheuristiken angesehen werden können. Diese werden jedoch im Folgenden nicht weiter betrachtet.
Gebräuchliche Metaheuristiken sind:
