Lösung des Traveling-Salesman-Problems mittels eines Genetischen Algorithmus auf einem HPC-Cluster

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

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.