Die vorliegende Arbeit positioniert die genetischen Algorithmen innerhalb einer Taxonomie verschiedener Optimierungsverfahren und skizziert den generischen Ablauf eines evolutionären Algorithmus.
Verschiedene Ansätze zur Parallelisierung genetischer Algorithmen werden vorgestellt und die Hauptvarianten paralleler und koevolutionärer genetischer Algorithmen umrissen.
Ferner werden Anforderungen an Frameworks zur Entwicklung genetischer Algorithmen formuliert, anhand welcher das ParadisEO-Framework mit dem proprietären GA-Framework aus der IMSL-Bibliothek von Visual Numerics verglichen wird.
Abschließend wird eine hybride low-level Teamwork Metaheuristik vorgestellt, die den Bergsteiger-Algorithmus zur lokalen Suche innerhalb eines grob-granularen parallelen genetischen Algorithmus einsetzt. Sie zeigt die Eignung paralleler genetischer Algorithmen zur Lösung des Problems des Handlungsreisenden.
Schlüsselwörter:
Evolutionary Computation, Metaheuristik, Traveling Salesman Problem, High Performance Computing, parallele genetische Algorithmen, koevolutionäre Algorithmen
Gliederung
1 Einführung
2 Optimierung
2.1 Wichtige Begriffe
2.2 Komplexitätsbetrachtungen
2.2.1 Landausche Symbole
2.2.2 Entscheidungsprobleme
2.2.3 Komplexitätsklassen
2.3 Arten von Optimierungsproblemen
2.3.1 Lineare Optimierung
2.3.2 Nichtlineare Optimierung
2.3.3 Multikriterielle Optimierung
2.3.4 Diskrete Optimierung
2.4 Optimierungsverfahren
2.4.1 Exakte Optimierungsmethoden
2.4.2 Approximative Optimierungsmethoden
3 Das Traveling Salesman Problem
3.1 Historischer Überblick
3.2 Mathematische Modellierung als Problem der Graphentheorie
3.3 Komplexität des TSP
3.4 Algorithmen zur Lösung des TSP
4 Evolutionäre Algorithmen
4.1 Biologische Hintergründe
4.1.1 Speicherung der genetischen Informationen
4.1.2 Mutation
4.1.3 Rekombination
4.2 Eine Algorithmenfamilie zur Lösung einer Vielzahl von Problemen
4.3 Terminologie
4.4 Ablauf eines Evolutionären Algorithmus
4.4.1 Initialisierung der Anfangspopulation
4.4.2 Evaluation
4.4.3 Abbruchstrategie
4.4.4 Zuchtwahl
4.4.5 Variationsoperatoren
4.4.6 Ersetzungsstrategien
4.5 Hauptvarianten evolutionärer Algorithmen
4.5.1 Genetische Algorithmen
4.5.2 Evolutionsstrategien
4.5.3 Evolutionäre Programmierung
4.5.4 Genetische Programmierung
5 Parallele Genetische Algorithmen
5.1 Parallele Computerarchitekturen
5.2 Parallele genetische Algorithmen
5.2.1 Parallelisierung auf Ebene des Algorithmus
5.2.2 Parallelisierungsmodelle auf Generationen-Ebene
5.2.3 Parallelisierungsmodelle für einzelne Individuen
5.3 Arten paralleler genetischer Algorithmen
5.3.1 Globale parallele genetische Algorithmen
5.3.2 Verteilte parallele genetische Algorithmen
5.3.3 Zellulare parallele genetische Algorithmen
5.3.4 Hierarchische parallele genetische Algorithmen
5.4 Koevolutionäre genetische Algorithmen
5.4.1 Koevolution
5.4.2 Arten koevolutionärer genetischer Algorithmen
6 MetaTSP: Eine parallele Metaheuristik für das TSP
6.1 Frameworks für Metaheuristiken
6.2 Anforderungen an Frameworks
6.3 MetaTsp – Ein Überblick
6.3.1 HC in Verbindung mit Swap-Mutation
6.3.2 HC als Antrieb der Evolution innerhalb eines CGPGA
6.4 Implementierung
6.4.1 MetaTsp Hauptprogramm
6.4.2 Implementierung der Inseln
6.5 Verbesserungsmöglichkeiten an MetaTsp
7 Abschließende Betrachtungen
Zielsetzung und Themen der Arbeit
Die Arbeit untersucht die Eignung paralleler genetischer Algorithmen zur Lösung des Traveling-Salesman-Problems (TSP) auf HPC-Clustern. Ziel ist die Entwicklung einer hybriden Metaheuristik, die verschiedene Optimierungsansätze kombiniert, um sowohl die explorativen Vorteile evolutionärer Algorithmen als auch die lokale Suchstärke klassischer Verfahren zu nutzen.
- Grundlagen der mathematischen Optimierung und Komplexitätstheorie
- Methodik des Traveling-Salesman-Problems (TSP)
- Konzept und biologische Basis evolutionärer Algorithmen
- Architektur und Parallelisierung genetischer Algorithmen auf HPC-Clustern
- Implementierung und Leistungsvergleich von Metaheuristik-Frameworks (VnGa vs. ParadisEO)
Auszug aus dem Buch
3.1 Historischer Überblick
Schon im 19. Jahrhundert wurden von Sir William Rowan Hamilton und Thomas Kirkman mit dem Problem des Handlungsreisenden (TSP) verbundene mathematische Probleme diskutiert.
Die wohl erste mathematische Formulierung einer Variation des Problems geht auf Karl Menger (siehe [Menger, 1998, S. 130] für einen Nachdruck des 9. Kolloquiums vom 5.2.1930) zurück, welcher recht anschaulich formuliert:
„[...] Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlichviele [sic!] Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. [...]“
In den 1950er Jahren beschäftigte sich dann eine Gruppe von Wissenschaftlern um George Dantzig systematisch mit der Formulierung, Analyse und Lösung des TSP (siehe dazu [Dantzig et al., 1954]).
In dieser Problemformulierung gilt es die kürzeste Tour von einer gegebenen Stadt aus zu finden, welche alle gegeben Städte besucht und zum Ausgangspunkt zurück führt. Seitdem wurde das Traveling Salesman Problem in einer unüberschaubaren Anzahl von Veröffentlichungen analysiert und als Benchmark-Problem für verschiedenste Optimierungsverfahren herangezogen, wodurch es aktuell wohl zu einem der am besten erforschtesten kombinatorischen Optimierungsprobleme zu zählen ist.
Zusammenfassung der Kapitel
1 Einführung: Die Einleitung positioniert das TSP als ein zentrales, historisch faszinierendes sowie komplexes Optimierungsproblem und skizziert den Gang der Untersuchung.
2 Optimierung: Dieses Kapitel erläutert grundlegende Begriffe der mathematischen Optimierung, führt in die Komplexitätstheorie ein und klassifiziert verschiedene Arten von Optimierungsproblemen.
3 Das Traveling Salesman Problem: Das TSP wird als kombinatorisches Problem formalisiert, seine Komplexität analysiert und verschiedene exakte sowie approximative Lösungsansätze werden gegenübergestellt.
4 Evolutionäre Algorithmen: Ausgehend von biologischen Prinzipien der Genetik werden Ablauf, Komponenten und die vier Hauptvarianten evolutionärer Algorithmen detailliert dargestellt.
5 Parallele Genetische Algorithmen: Hier werden parallele Rechnerarchitekturen beschrieben und Strategien zur Parallelisierung genetischer Algorithmen auf verschiedenen Granularitätsebenen untersucht.
6 MetaTSP: Eine parallele Metaheuristik für das TSP: Dieser Abschnitt beschreibt die Implementierung der hybriden Metaheuristik MetaTsp unter Verwendung des ParadisEO-Frameworks auf einem HPC-Cluster.
7 Abschließende Betrachtungen: Das Fazit fasst die Ergebnisse der Arbeit zusammen und gibt einen Ausblick auf zukünftige Entwicklungen im Bereich der naturinspirierten Optimierung.
Schlüsselwörter
Evolutionary Computation, Metaheuristik, Traveling Salesman Problem, High Performance Computing, parallele genetische Algorithmen, Optimierung, Fitnesslandschaft, Evolutionäre Algorithmen, HPC-Cluster, ParadisEO, Selektion, Mutation, Rekombination, Komplexitätstheorie, hybride Metaheuristik.
Häufig gestellte Fragen
Worum geht es in dieser Bachelorarbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Lösung des Traveling-Salesman-Problems unter Verwendung eines genetischen Algorithmus, der auf Hochleistungsrechnern (HPC-Clustern) parallel ausgeführt wird.
Was sind die zentralen Themenfelder?
Zentrale Themen sind die mathematische Optimierung, die Komplexitätstheorie, die Funktionsweise evolutionärer Algorithmen sowie Methoden der Parallelisierung von Berechnungen.
Was ist die Forschungsfrage oder das primäre Ziel?
Das Ziel ist die Implementierung einer hybriden Metaheuristik, die eine effiziente Rundreiseplanung für TSP-Instanzen ermöglicht, indem sie globale evolutionäre Ansätze mit lokaler Suchoptimierung kombiniert.
Welche wissenschaftlichen Methoden kommen zum Einsatz?
Es werden Literaturanalysen zur Theorie der Optimierung und Komplexität sowie praktische Implementierungen und Performance-Vergleiche zwischen Frameworks wie VnGa und ParadisEO durchgeführt.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretischen Grundlagen (Optimierung, TSP, evolutionäre Algorithmen), die Parallelisierungsansätze und die konkrete Vorstellung und Implementierung von "MetaTsp".
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind insbesondere das Traveling Salesman Problem (TSP), High Performance Computing (HPC), evolutionäre Algorithmen, Metaheuristiken und parallele genetische Algorithmen.
Warum wurde das ParadisEO-Framework ausgewählt?
ParadisEO bot im direkten Vergleich eine bessere Performance und höhere Flexibilität als VnGa, was die Portierung auf die Windows HPC Server 2008 Umgebung rechtfertigte.
Welche Rolle spielt der Bergsteiger-Algorithmus (HC) in MetaTsp?
Er dient als lokale Suchstrategie, um die Konvergenz zu lokalen Optima innerhalb einer Insel zu beschleunigen, wird jedoch zur Bewahrung der genetischen Vielfalt nur begrenzt eingesetzt.
Was besagt die Punktualismus-Theorie im Kontext der Arbeit?
Sie wird genutzt, um das Evolutionsverhalten der Populationen nach Migrationen zu erklären, bei denen es zu Sprüngen in der Lösungsqualität kommt.
- Quote paper
- Kevin Kraßnitzer (Author), 2009, Lösung des Traveling-Salesman-Problems mittels eines Genetischen Algorithmus auf einem HPC-Cluster, Munich, GRIN Verlag, https://www.grin.com/document/140098
