Programmierungs-Frameworks für Metaheuristiken

Inhaltsverzeichnis

Abstract

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

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.

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.

Vorliegende Arbeit soll einen Überblick über derartige, im Internet verfügbare, Programmierungs-Frameworks für Metaheuristiken geben. Eine Auswahl von Frameworks wird hinsichtlich selbst definierter Kriterien klassifiziert und verglichen. Zuvor sollen die wichtigsten Metaheuristiken und darauf aufbauende Designprinzipien für Frameworks vorgestellt werden.

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 in dieser Leseprobe nicht enthalten

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:

- Einfache lokale Suchalgorithmen
- Lagrange-Heuristiken
- GRASP (Greedy Randomized Adaptive Search Procedure)
- Simulated Annealing und verwandte Methoden
- Variation der Nachbarschaft und deren Bewertung (z.B. Ruin-and-Recreate)
- Tabu Search
- Genetische und Evolutionäre Algorithmen
- Ameisenalgorithmen
- Neuronale Netze

Die wichtigsten Metaheuristiken werden nun detaillierter beschrieben.

2.1 Einfache lokale Suchverfahren

Einfache lokale Suchverfahren manipulieren eine gegebene zulässige Lösung durch elementare Operationen in eine andere zulässige Lösung, welche nach einer Zielfunktion bewertet wird. Durch die zulässigen Elementaroperationen ist eine Nachbarschaft definiert. Abstrakt gesehen wird als Nachbarschaft Abbildung in dieser Leseprobe nicht enthalteneiner Lösung Abbildung in dieser Leseprobe nicht enthaltendie Menge aller möglichen Lösungen bezeichnet welche von dieser aus durch die zulässigen Elementaroperationen (z.B. Vertauschen zweier Knoten eines Netzgraphen, bzw. Basistausch) erreichbar sind.

Wird eine bezüglich der Zielfunktion bessere Lösung gefunden, wird von der besseren Lösung aus wieder mit den zulässigen Elementaroperationen manipuliert.

Bei der einfachen lokalen Suche handelt es sich um ein Verbesserungsverfahren, welches eine bezüglich der gewählten Nachbarschaft optimale Lösung liefert (vgl. [1]).

2.2 Lagrange-Heuristiken

Lagrange-Heuristiken basieren auf der Lösung des Lagrange-dualen Problems. Hierbei werden ständig neue Lagrange-Multiplikatoren p bestimmt, und für diese das Lagrange-relaxierte Problem gelöst. Die primal unzulässige Lösung des Lagrange-relaxierten Problems soll nun in eine zulässige Lösung für das zugrunde liegende Optimierungsproblem umgewandelt werden, wofür so genannte „Repair-Algorithmen“ entwickelt wurden.

Lagrange-Heuristiken werden in der Literatur meist nicht als Metaheuristiken bezeichnen, erfüllen jedoch die definitionsgemäßen Eigenschaften (vgl. [1]).

2.3 GRASP

Bei der „Greedy Randomized Adaptive Search Procedure“ handelt es sich um eine Kombination aus einem Greedy-Algorithmus mit einem local-search-Algorithmus (vgl. [10]). Hiermit wird in jeder Iteration mit einem stochastisch gesteuerten Greedy-Algorithmus eine zulässige Lösung erzeugt, welche danach mit Hilfe der lokalen Suche weiter verbessert wird. Ist die Lösung besser als die beste bisher gefundene Lösung wird diese fixiert und von vorne begonnen. Der dritte Bestandteil des GRASP-Algorithmus ist die so genannte Stop-Regel. Hier wird meist die Anzahl der Iterationen oder eine Konvergenzfunktion verwendet. Ein derartiges Abbruchkriterium ist jedoch auch bei den meisten anderen Metaheuristiken notwendig. Im Gegensatz zur klassischen Greedy-Heuristik welche eine zulässige Eröffnungslösung generiert, ist zu erwähnen dass bei GRASP die Auswahl der nächsten zu fixierenden Variablen zufällig auf Basis einer Kandidatenliste erfolgt.

2.4 Simulated Annealing

Eine häufig verwendete Metaheuristik, welche fast jedes Framework bietet, ist Simulated Annealing. Der Name bedeutet „simuliertes Ausglühen“ und geht darauf zurück dass der zugrunde liegende Algorithmus von Metropolis et al. im Jahre 1953 ursprünglich zur Simulation der Kristallstruktur des Glüh- und Abkühlprozesses von Metallen vorgeschlagen wurde [1].

Der Algorithmus kann verallgemeinert und umgedeutet jedoch als Metaheuristik zur Lösung jedes Minimierungsproblems genutzt werden.

Das wesentliche Prinzip des Simulated Annealing besteht darin, dass bei jeder Iteration aus der Nachbarschaft der aktuellen Lösung x eine potentielle neue Lösung x’ ausgewählt und akzeptiert wird, sofern die implizite Zielfunktionswertänderung nicht negativ ist. Ist die Zielfunktionswertänderung negativ kann der Zug gegebenenfalls nicht-deterministisch abgelehnt werden. Jedoch kann der Zug abhängig vom Ergebnis eines stochastischen Akzeptanzkriteriums dennoch akzeptiert werden. Hierbei wird das Akzeptanzkriterium normalerweise derart definiert, dass eine Ablehnung mit steigendem Absolutbetrag der Verschlechterung wahrscheinlicher wird. Zudem wird um den Suchprozess zu steuern die so genannte Temperatur T eingeführt, welche mit zunehmendem Verlauf der Suche abgesenkt wird. Die Temperatur T ist ein zweiter wichtiger Parameter des Akzeptanzkriteriums, welcher dazu verwendet wird die Wahrscheinlichkeit des Akzeptierens verschlechternder Züge im Suchablauf durch Absenken der Temperatur T herabzusetzen (vgl. [11]).

[...]