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

Gliederung

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

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

Anhang

Literaturverzeichnis

Abstract

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 GAFramework 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

Abbildungsverzeichnis

Abbildung 1:Taxonomie der Optimierungsmethoden

Abbildung 2:kreuzende Kanten bei metrischem TSP

Abbildung 3:Merkmale von DNS und RNA

Abbildung 4: Reduplikation von Erbinformationen

Abbildung 5:Terminologie der evolutionären Algorithmen

Abbildung 6: Ablauf eines evolutionären Algorithmus

Abbildung 7: Eigenschaften der deterministischen Turnier Selektion

Abbildung 8:Eigenschaften der linearen Rangauswahl

Abbildung 9: Diversitätsverlust bei linearem ranking und Turnier Auswahl

Abbildung 10: ein Punkt Crossover

Abbildung 11:Partially Matched Crossover (PMX)

Abbildung 12: Programm als Binärbaum

Abbildung 13:cache kohärente nonuniform memory Architektur

Abbildung 14: Hyperwürfel in verschiedenen Dimensionen

Abbildung 15: Übersicht paralleler genetischer Algorithmen

Abbildung 16: Beispielhafte Konfiguration von MetaTsp

Abbildung 17:Auswirkungen der HC Mutation in einer Ring Topologie

Abbildung 18:MetaTsp Hauptkomponenten

Abbildung 19: MetaTsp Hauptprogramm

Abbildung 20: MetaTspIsland

Abbildung 21:Framework Performance: 52 Städte

Abbildung 22:Framework Performance: 101 Städte

Abbildung 23: Framework Performance: 2392 Städte

Tabellenverzeichnis

Tabelle 1: Typische Wachstumsklassen von Algorithmen

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einführung

Das Problem des Handlungsreisenden, eine möglichst kurze Reiseroute zwischen verschiedenen Kundenstandorten zu finden, welche wieder zum Ausgangspunkt der Reise zurückführt, übt aufgrund seiner scheinbar einfachen Problemstellung, aber überaus schwierigen Lösung, eine stetige Faszination auf die Menschen aus.

Die vorliegende Arbeit wird zeigen warum es so schwer ist dieses und ähnliche Probleme zu lösen und verschiedene Lösungsansätze vorstellen. Im Folgenden soll der Gang der Untersuchung skizziert werden:

In den ersten Kapiteln wird kurz der Begriffsapparat der Optimierung in Erinnerung gerufen und das Problem des Handlungsreisenden im Kontext der verschiedenen Optimierungsprobleme positioniert.

Ein Überblick der Komplexitätstheorie soll die Grundlage für das Verständnis schaffen, warum einige Probleme der mathematischen Optimierung schwieriger zu lösen sind als andere, scheinbar ähnliche Probleme: Das im 18. Jahrhundert diskutierte Problem, einen Rundweg über die sieben Brücken Königsbergs zu finden und wieder zum Startpunkt zurückzukehren, ist auf den ersten Blick dem Problem des Handlungsreisenden nicht unähnlich. Es kann aber im Gegensatz zu diesem schnell und effizient gelöst werden, wie in Kapitel 3.3 gezeigt werden wird.

Als Teilproblem in vielen wichtigen Anwendungen der Logistik und Produktion, wurde das Problem des Handlungsreisenden bereits mit vielen Ansätzen zu lösen versucht. Das Kapitel 2.4 gibt einen Überblick über diese Verfahren und stellt ihren Platz innerhalb einer Taxonomie der Optimierungsverfahren heraus.

Das Problem des Handlungsreisenden wird anschließend kurz formalisiert und die Eignung einiger in Kapitel 2.4 vorgestellter Verfahren bewertet.

In den darauf folgenden Abschnitten wird der, von der natürlichen Evolution inspirierte Ansatz der evolutionären Algorithmen vorgestellt. Einer der wichtigsten Schritte im Ablauf eines evolutionären Algorithmus ist die Selektion. Sie steuert die künstliche Evolution indem sie die zur Fortpflanzung bestimmten Individuen festlegt und die Zusammensetzung der folgenden Generation bestimmt. Verschiedene Ansätze zur Realisierung der Selektion werden detaillierter beleuchtet und bezüglich verschiedener Parameter untereinander verglichen.

Anschließend wird die, in den letzten Jahren zunehmend kostengünstig verfügbare, parallele Rechentechnik bezüglich ihrer Architektur klassifiziert. Es werden verschiedene Ansätze aufgezeigt, wie diese zur Parallelisierung genetischer Algorithmen genutzt werden kann.

Nach einem Überblick über die verschiedenen Hauptvarianten paralleler und koevolutionärer genetischer Algorithmen werden zwei Frameworks zur Entwicklung genetischer Algorithmen anhand der an sie gestellten Anforderungen miteinander verglichen. Darauf folgt eine kurze Vorstellung von MetaTsp ± einem parallelen genetischen Algorithmus, welcher auf einem HPC-Cluster auch Reiserouten für größere Instanzen des Problems des Handlungsreisenden zu finden vermag.

Eine abschließende Betrachtung wird mögliche zukünftige Trends im Bereich des Soft Computing vorstellen und Ansätze für weitere Forschungen aufzeigen. Der eben dargestellte, grobe Ablauf soll nun im Folgenden umgesetzt werden: Es folgt eine kurze Beschreibung der Motivation und eine Vorstellung der wichtigsten Begriffe der Optimierung, welche für das Verständnis der weiteren Kapitel wichtig sind.

2 Optimierung

Viele Anwendungen aus Natur-, Wirtschafts- und Ingenieurwissenschaften erfordern die geeignete Wahl eines oder mehrerer Parameter um eine gegebene Zielfunktion zu maximieren oder zu minimieren: Sei es die Minimierung von Kosten, Zeiten und Risiken, oder die Maximierung von Profit, Effizienz und Qualität im Unternehmen ± Optimierungsprobleme sind oft komplex, aber das Finden einer geeigneten Lösung ist umso kritischer.

Die Lösung solcher Extremwertaufgaben ist die Domäne der mathematischen Optimierung. Diese ist ein Teilgebiet der Angewandten Mathematik und beschäftigt sich mit der Entwicklung und Analyse konstruktiver Verfahren zur konkreten Lösung mathematisch modellierter Optimierungsmodelle.

2.1 Wichtige Begriffe

Ein Optimierungsproblem ist ein 4-Tupel ( I, L, f, opt) aus einer Menge zulässiger und möglicher Lösungen L, sowie einer Zielfunktion IؿEingaben I /ĺԹ, welche L einen Wert bezüglich der Eignung zur Problemlösungאjeder möglichen Lösung l {min, max}אzuweist und die es zu optimieren gilt (vgl. [Talbi, 2009, S.3]). Dabei gibt opt an, ob es sich um ein Minimierungs- oder Maximierungsproblem handelt. Die Interpretation von f kann sich je nach Problem-Domäne unterscheiden: Kosten- oder Gewinnfunktion in der Betriebswirtschaftslehre, Nutzen-, oder Wohlfahrtsfunktion in der Volkswirtschaftslehre ± die Bezeichnungen sind so vielfältig wie die Problemstellungen für welche ein Optimum gefunden werden soll.

Ein globales Optimum ist eine Lösung L, für die für alle möglichen Lösungen l imאl* Suchraum gilt: f(l*) - f(l).

In diesem Fall spricht man von einem globalen Maximum. Für ein globales Minimum gilt entsprechend: f(l*) - f(l).

Lokale Optima gelten analog nur in einer offenen ࣅ-Umgebung des Suchraumes, wobei ࣅ eine positive, aber beliebig kleine reelle Zahl darstellt.

Da die vorerst allerwichtigsten Begriffe in Erinnerung gerufen wurden, folgt nun eine kurze Zusammenfassung der Grundlagen der Komplexitätstheorie. Diese werden zum Verständnis benötigt, warum schon kleinere Instanzen des Problems des Handlungsreisenden nicht mehr handhabbar sind, wogegen aber das bereits auf Seite 1 vorgestellte Brückenproblem auch für sehr große Probleminstanzen keine Herausforderung darstellt.

2.2 Komplexitätsbetrachtungen

Um von einzelnen Rechnerarchitekturen abstrahieren zu können, wird für Komplexitätsbetrachtungen oft ein idealisierter von Neumann-Rechner in Form einer Registermaschine (RAM) bemüht. Eine Registermaschine besteht aus einer unendlichen Zahl von Registern, einem Akkumulator, einem Befehlszähler und einem nur-lesbaren Programmspeicher.

Algorithmische Komplexität lässt sich auf drei Ebenen untersuchen:

- Die Zeitkomplexität bezeichnet die Anzahl der Programmschritte, welche eine Registermaschine für die Ausführung einer Eingabe benötigt.
- Der zur Berechnung eines RAM-Algorithmus benötigte Speicherplatzbedarf bestimmt die Platzkomplexität des Algorithmus.
- Die Beschreibungskomplexität beschreibt die Programmlänge als Anzahl der Instruktionen, aus dem das Registermaschinen-Programm besteht. Oft sind aber Implementierungen mit geringer Beschreibungskomplexität schwerer verständlich, wodurch die Beschreibungskomplexität eine eher untergeordnete Rolle bei der Komplexitätsbetrachtung eines Algorithmus spielt.

2.2.1 Landausche Symbole

Da genaue Abschätzungen der Zeit- und Platzkomplexität eines Algorithmus nur unter großem Aufwand möglich sind, gibt man sich oft mit asymptotischen Abschätzungen zufrieden. Mittels der Landauschen Symbolik lassen sich die asymptotischen Resultate verschiedener Algorithmen untereinander vergleichen.

Die drei wichtigsten Landauschen Symbole beschreiben die asymptotischen Schranken einer Funktion g, wenn [Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

Wenn [Abbildung in dieser Leseprobe nicht enthalten]gilt, sagt man: g wächst höchstens so schnell wie f.

Abbildung in dieser Leseprobe nicht enthalten

Wenn [Abbildung in dieser Leseprobe nicht enthalten]sagt man analog: g wächst mindestens so schnell wie f.

Abbildung in dieser Leseprobe nicht enthalten

Man sagt zu [Abbildung in dieser Leseprobe nicht enthalten]g ist asymptotisch nach oben und unten durch f beschränkt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Typische Wachstumsklassen von Algorithmen (in Anlehnung an [Brill, 2001, S.277])

2.2.2 Entscheidungsprobleme

wird, ist es zunächst nötig Entscheidungsprobleme - und den damit verbundenen Begriff der Berechenbarkeit ± kurz zu definieren:

Eine Teilmenge D der Ganzen Zahlen Ժ heißt entscheidbar, wenn ihre Indikatorfunktion Ժ ĺԺ eine RegistermaschineكI{D} berechenbar ist, d.h. wenn es zu einer Funktion f: D D die Ausgabe von M ist, oder andernfalls M auf x nichtאM gibt, so dass f(x) für alle x hält (vgl. [Heun, 2003, S.307]).

Ein Entscheidungsproblem ist nun eine Funktion, welche zu einer Eingabe ein bool´sches true oder false liefert (formal: [Abbildung in dieser Leseprobe nicht enthalten] Etwas anschaulicher lässt sich ein

Entscheidungsproblem also als Frage formulieren, ob ein bestimmtes Objekt eine gewisse Eigenschaft besitzt, oder nicht.

2.2.3 Komplexitätsklassen

Zur besseren Vergleichbarkeit verschiedener Probleme werden diese in Komplexitätsklassen eingeteilt, welche für alle, in einer bestimmten Klasse enthaltenen Probleme, die benötigten Rechenressourcen wie z.B. Speicherplatz oder den Zeitaufwand zur Berechnung beschreibt.

Die Klasse P enthält Entscheidungsprobleme, welche mittels einer polynomiell zeitbeschränkten Registermaschine gelöst werden können. Diese Probleme sind relativ einfach handhabbar, da es deterministische Algorithmen gibt, welche das Problem (mehr oder weniger) effizient lösen.

Schwierig nennt man Probleme, welche in polynomieller Zeitkomplexität von nichtdeterministischen Verfahren, also Verfahren, für welche es mehr als genau einen Berechnungsweg gibt, gelöst werden können. Anders ausgedrückt: Wenn eine gegebene Lösung (Zertifikat) von einer polynomiell zeitbeschränkten Registermaschine verifiziert werden kann.

Da Komplexitätsklassen nur eine Informationen zum asymptotischen Verhalten liefern, ist es noch immer nicht möglich zu sagen, ob nun ein Entscheidungsproblem P schwieriger ist als ein Entscheidungsproblem P´. Wenn nun P mit weniger Aufwand auf P´ zurückgeführt werden könnte, als zur Berechnung von P nötig ist, so wäre P´ schwieriger als P. P gilt,אMan nennt eine solche Abbildung ȡ von P auf P´ eine Reduktion, wenn für alle x P´ (vgl. [Heun, 2003, S. 321] oder [Karp, 1972, S. 86]).אdass ȡ [

Man kann also ein Entscheidungsproblem lösen, indem man es auf ein anderes reduziert und dann dieses löst.

Die schwierigsten Entscheidungsprobleme sind NP-vollständige Probleme, welche sich dadurch auszeichnen, dass sie in der Klasse NP liegen und sich jedes andere, auch in NP liegende Problem, in polynomieller Zeit auf dieses reduzieren lässt (NP-Härte). Man kann zeigen (wie geschehen in [Heun, 2003, S. 324]), dass ein, in polynomieller Zeit beschränkter, Algorithmus, welcher ein einziges NP-hartes Problem löst, ausreicht zu beweisen, dass die Komplexitätsklassen P und NP gleich sind ± eines der vom Clay Mathematics Institute formulierten, ungelösten Millennium-Probleme (vgl. [CMI, 2000]). Mit dem Beweis der Existenz eines solchen Algorithmus, wäre auch gezeigt, dass alle anderen Probleme in NP effizient gelöst werden könnten (siehe dazu [Cook, 1971]). Es wird aber vermutet, dass es einen solchen Algorithmus nicht gibt.

Der Begriff der NP-Vollständigkeit kann auch noch etwas weiter aufgefasst werden, indem man ihn auch auf Optimierungs- und Suchprobleme ausweitet:

Ein Optimierungsproblem P = (I, L, f, opt) gehört zur Klasse NPO, falls die Menge der Instanzen in polynomieller Zeit erkannt werden und die Größe jeder Lösung polynomiell in der Eingabegröße beschränkt ist und die Zielfunktion f ebenfalls mit polynomiellem Aufwand berechnet werden kann. In diesem Fall ist das P zugrunde liegende Entscheidungsproblem in NP, da einfach eine mögliche Lösung geraten werden kann, für welche in poylnomieller Zeit entschieden werden kann, ob sie auch tatsächlich in L ist.

Wenn das P zugrunde liegende Entscheidungsproblem NP-vollständig ist und P in NPO liegt, so nennt man P NP-äquivalent.

Zusammenfassend lässt sich festhalten, dass also nicht die mittlere zu erwartende Laufzeit eines konkreten Problems auf einer bestimmten Hardware betrachtet wird, sondern das asymptotische Verhalten unter Abstrahierung spezifischer Eigenschaften der Rechentechnik und der Implementierung. Probleme mit ähnlichem Verhalten werden in Komplexitätsklassen zusammengefasst. Probleme, für welche eine Lösung in polynomieller Laufzeit möglich ist nennt man einfache Probleme.

Im Folgenden werden nun verschiedene Arten von Optimierungsproblemen vorgestellt, für welche sich unterschiedliche Lösungsverfahren anbieten.

2.3 Arten von Optimierungsproblemen

Mathematische Optimierungsprobleme lassen sich in vier Hauptvarianten einteilen, welche hier kurz skizziert werden sollen. Abschnitt 3 beleuchtet das Travelling Salesman Problem (TSP) als bekanntes kombinatorisches Optimierungsproblem etwas genauer.

2.3.1 Lineare Optimierung

Lineare Optimierungsprobleme, wie z.B. Mischungs- und Produktionsprobleme, bei welchen in der Regel mehrere Alternativen unter Berücksichtigung verschiedener Nebenbedingungen optimal zu kombinieren sind, zeichnet aus, dass die Zielfunktion als lineare Funktion der Entscheidungsvariablen und die Nebenbedingungen als Menge linearer Gleichungen oder Ungleichungen formuliert werden können. Probleme dieser Art können mit dem Innere-Punkte-Verfahren oder dem 1947 von George Dantzig vorgestellten Simplex-Verfahren für die meisten Probleminstanzen in polynomieller Zeitkomplexität gelöst werden, d.h. sie liegen in der Komplexitätsklasse P.

2.3.2 Nichtlineare Optimierung

Wenn die zu optimierende Zielfunktion oder Nebenbedingungen nicht linear sind, spricht man von nichtlinearer Optimierung. Sucht man ein Optimum in einem abgegrenzten Bereich des Suchraumes, so stehen je nach Beschaffenheit der Funktion verschiedene, unterschiedlich aufwändige Verfahren zur Verfügung.

Nichtlineare Optimierungsprobleme können in unrestringierte und restringierte Probleme eingeteilt werden. Bei den restringierten Optimierungsproblemen wird ein mittels Gleichungen und Ungleichungen beschriebener Teilbereich aus Թ betrachtet. Bei unrestringierten Problemen ist ganz Թ zulässig.

Mögliche Strategien, welche ohne Ableitungen auskommen, sind das Sekantenverfahren oder die rekursive Teilung der Suchintervalle z.B. nach dem goldenen Schnitt oder in gleich große Teilintervalle, so dass die Intervalllänge gegen Null konvergiert. Bekannte Verfahren, welche die Berechnung von Ableitungen in Kauf nehmen, sind z.B. das Verfahren des steilsten Abstiegs oder das Newton-Verfahren.

Alle diese Verfahren eignen sich nur zum Finden lokaler Optima ± ist das globale Optimum einer Zielfunktion gesucht, so werden in der Regel stochastische Metaheuristiken, wie z.B. die in Abschnitt 4 vorgestellten Evolutionären Algorithmen Գ ) auch nur potentielleאgenutzt, welche aber in vertretbarer Zeit (also in ȅ Qk ) mit k Optima liefern können.

2.3.3 Multikriterielle Optimierung

Sollen Optima nicht nur für eine, sondern simultan für viele, oft konfliktionäre Zielfunktionen gefunden werden, spricht man von Multiple Criteria Decision Making (MCDM). Beispiele für Anwendungen finden sich oft in den Wirtschaftswissenschaften: In der Portfoliotheorie von Harry Markowitz (siehe [Markowitz, 1952]) soll ein Anlagen- Portefeuille gefunden werden, welches verschiedene Kriterien wie z.B. Rendite und Risiko optimiert.

Da auch hier ein globales Optimum in polynomieller Zeit oft nicht zweifelsfrei festgestellt werden kann, kommen auch bei der multikriteriellen Optimierung verbreitet Metaheuristiken zum Einsatz.

2.3.4 Diskrete Optimierung

In vielen Anwendungen von praktischer Relevanz sind die zu optimierenden Variablen nicht beliebig teilbar, sondern müssen als ganzzahliges Programm modelliert werden. Das Ziel der diskreten Optimierung ist es nun, aus einer endlichen, aber in der Regel sehr großen, Menge von Objekten das ± bezüglich der Zielfunktion ± optimale zu finden (vgl. [Zimmermann, 1998, S.59]).

Viele wichtige Zuordnungs-, Reihenfolge, Auswahl- und Gruppierungsprobleme wie z.B. Tourenplanungsprobleme oder Zeitplanungs-Probleme, bei denen es um die optimale Zuordnung von Ressourcen unter Berücksichtigung verschiedener Nebenbedingungen geht, gehören zur Familie der ± oft in NP liegenden ± kombinatorischen Optimierungsprobleme. [Morlock/Neumann, 1993, S. 380 f.] definieren ein kombinatorisches Optimierungsproblem formal:

[Abbildung in dieser Leseprobe nicht enthalten] @Gegeben seien eine endliche Menge E (Grundmenge [Hervorhebung im Original]), eine Teilmenge I der Potenzmenge[Abbildung in dieser Leseprobe nicht enthalten] von E (die Elemente heißen zulässige Mengen oder zulässige Lösungen [Hervorhebungen im Original]) und

eine Funktion [Abbildung in dieser Leseprobe nicht enthalten]E d efinieren wir ihre n W ert durchكEoK. Für jede Menge F

[Abbildung in dieser Leseprobe nicht enthalten]der klein) wie [Abbildung in dieser Leseprobe nicht enthalten]chאund wir suchen eine Menge [Abbildung in dieser Leseprobe nicht enthalten]

Im folgenden Abschnitt werden verschiedene Lösungsverfahren in einen Zusammenhang gebracht, welche sich insbesondere für diskrete Optimierungsprobleme eignen, zu denen auch das Problem des Handlungsreisenden gehört.

2.4 Optimierungsverfahren

Zur Lösung von Optimierungsproblemen haben sich eine Vielzahl von systematischen Vorgehensweisen und Verfahren¹ durchgesetzt, welche in exakte und approximative Methoden unterschieden werden können. Abbildung 1 zeigt eine Taxonomie verschiedener Ansätze.

Exakte Methoden finden garantiert optimale Lösungen, da aber viele Optimierungsprobleme in der Komplexitätsklasse NP liegen, ist der Aufwand zur Lösung von in der Praxis gängigen Problemgrößen meist zu hoch. Daher gibt man sich oft mit suboptimalen, aber Ähinreichend guten³ Lösungen² zufrieden, welche nach ± verglichen mit vielen exakten Methoden ± kurzer Berechnungszeit verfügbar sind.

2.4.1 Exakte Optimierungsmethoden

Bei den Verzeigung und X ± im englischen auch branch and X ± Meta-Verfahren wird der Suchraum rekursiv unterteilt und nur vielversprechende Lösungskandidaten an den Blättern des entstehenden Entscheidungsbaums werden enumerativ untersucht.

Die Dynamische Programmierung verwaltet die, bei der rekursiven Bearbeitung des Problems entstandenen, Zwischenlösungen in einer Tabelle und ermöglicht damit die Weiterverwendung bereits gelöster Teilprobleme.

Die ÄConstraintprogrammierung³ ist ein exaktes Such-Paradigma, welches aus der KIForschung stammende Techniken zur Erfüllung von Lösungsbedingungen auf kombinatorische Optimierungsprobleme anwendet.

Ähnlich zu greedy-Verfahren bearbeiten die, zu der Familie der informierten Suchverfahren gehörenden, A*- und IDA*- Algorithmen zuerst die vielversprechendsten Lösungskandidaten, beachten dabei aber die bereits angefallenen Suchaufwendungen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1:Taxonomie der Optimierungsmethoden (in Anlehnung an [Talbi, 2009, S.18])

2.4.2 Approximative Optimierungsmethoden

Die Approximativen Optimierungsmethoden lassen sich in Approximierungsalgorithmen, welche in polynomieller Laufzeit für ein spezifisches Problem garantiert eine Lösung finden, welche maximal um den Faktor H vom Optimum abweicht, und in heuristische Methoden einteilen.

Heuristische Verfahren, für die kein Konvergenzbeweis geführt werden kann, zeichnen sich dadurch aus, dass sie durch nichtwillkürliche Entscheidungsoperatoren die Suche steuern, bzw. diejenigen potentiellen Lösungen identifizieren, welche vom Suchprozess ausgeschlossen werden sollen (vgl. [Streim, 1975, S.151 f.]).

Anders als bei Approximierungsalgorithmen kann bei heuristischen Methoden nicht garantiert werden, dass das Optimum ± oder auch nur eine Lösung innerhalb einer H - Umgebung um das Optimum ± gefunden wird.

Trotzdem erreichen insbesondere problemspezifische Heuristiken sehr gute zulässige Lösungen mit nur vergleichsweise geringem Rechenaufwand.

Metaheuristiken sind Verfahren, welche nicht nur auf ein bestimmtes, sondern auf eine Vielzahl von Problemen angewendet werden können. Sie erfreuen sich einer großen Beliebtheit, da sie prinzipiell mit wenig Anpassungsaufwand auf viele spezifische Probleme ± auch auf große Probleminstanzen ± anwendbar sind. Wolpert und Macready zeigten aber, dass a priori kein Verfahren besser ist als ein anderes (vgl. [Wolpert/Macready, 1997, S.69] und Beweis ebenda S. 77 ff.): So eignen sich beispielsweise Evolutionäre Algorithmen³ -Probleme (vgl. [Moreland / Truemper, 2009]) zu lösen, bei welchen wenige, sich stark von der Umgebung im Suchraum abhebende, Extremwerte zu finden sind.

Metaheuristiken lassen sich nach einer Vielzahl von, in [Talbi, 2009, S. 25] skizzierten, Kriterien klassifizieren: Exemplarisch zeigt Abbildung 1 verbreitete Metaheuristiken, welche anhand der Kardinalität der Lösungskandidaten unterteilt wurden: Einzellösungsbasierte Algorithmen steuern anschaulich formuliert nur einen Lösungskandidaten in der Fitnesslandschaft des Suchraumes und eignen sich somit tendenziell besser, die nähere Umgebung des Suchpunktes intensiv nach Optima zu durchsuchen, wogegen populations-basierte Verfahren eine Vielzahl von Lösungskandidaten gleichzeitig manipulieren und so einen größeren Teil des Suchraumes abdecken.

In diesem Kapitel über die mathematische Optimierung wurden die wichtigsten Begriffe und Arten von Optimierungsproblemen vorgestellt. Es stellte sich heraus, dass es relativ einfach ist ein Optimum in einem begrenzten Gebiet des Suchraumes zu finden. Als problematisch erweist sich jedoch oft die Suche nach einem globalen Optimum, weshalb Optimierungsverfahren entwickelt wurden, welche einen Kompromiss zwischen der Lösungsqualität und dem dafür benötigten Aufwand eingehen. Mit den vorgestellten Grundlagen der Komplexitätstheorie ist es möglich diesen Aufwand zu beurteilen und 3UREOHPH EH] JOLFK LKUHU Ä6FKZLHULJNHLW³ ]X NODVVLIL]LHUHQ

Das Problem des Handlungsreisenden ist ein schwieriges Problem der diskreten Optimierung und wird nun detaillierter betrachtet werden.

3 Das Traveling Salesman Problem

Eines der prominentesten und am besten erforschten kombinatorischen Optimierungsprobleme ist das des Handlungsreisenden, welches als Grundproblem für viele praktische Anwendungen, wie die Routenplanung für öffentliche Verkehrsmittel, Ä(VVHQ DXI 5lGHUQ³ oder optimale Inspektionsreihenfolgen für Sicherheits-Dienstleister, aber auch beim Bohren von Leiterplatten oder bei der Gen-Sequenzierung, gelöst werden muss.

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:

Postboten,übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlichviele [sic!] Punkte, deren paarweise Abstände bekannt sind, den

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.

3.2 Mathematische Modellierung als Problem der Graphentheorie

Zum Erarbeiten einer Lösung eines Optimierungsproblems wird in der Regel ein mehrstufiger Prozess angewandt: Zuerst muss das Problem in geeigneter Weise mathematisch modelliert werden, danach wird die Komplexität des Problems untersucht um darauf aufbauend einen geeigneten Algorithmus zu formulieren.

Bevor das TSP mathematisch modelliert wird, sollen zuerst noch einmal die wichtigsten Begriffe der Graphentheorie in Erinnerung gerufen werden:

Ein ungerichteter Graph G ist ein Paar (V, E), bestehend aus der Knotenmenge V (G) und V}. Man nennt zwei Knoten u und v adjazent,א{{u , v}| u , v كder Kantenmenge E(G) wenn es eine Kante zwischen ihnen gibt. Die Menge der Nachbarn eines Knotens u sei NG(u). Der Grad deg(u) ist die Anzahl seiner Nachbarn |NG(u)|. Zwei Kannten welche einen gemeinsamen Knoten besitzen, nennt man ebenfalls adjazent.

Bei einem gerichteten Graphen ist die Richtung der Kanten relevant, da die Menge

[Abbildung in dieser Leseprobe nicht enthalten]aus geordneten Knotenpaaren besteht. Eine Kante e und[Abbildung in dieser Leseprobe nicht enthalten] ein Knoten u des Graphen G nennt man inzident, wenn u ein Element von e ist. Eine Schleife ist eine ein-elementige Kantenmenge im Falle eines ungerichteten Graphen oder eine Kante mit identischem Anfangs- und Endknoten bei einem gerichteten Graphen. Eine Kantenfolge p = (e0 « Hn) mit der Länge n, nennt man einen Weg, wenn jede Kante aus p einen Endknoten mit ei-1 und ei+1 teilt. Ein Weg heißt einfach, wenn jeder Knoten des Pfades nur einmal auftaucht. Sind der Anfangsknoten und der Endknoten eines Weges identisch, so nennt man diesen Weg einen Kreis. Ein einfacher Kreis ist ein Weg mit einer Mindestlänge drei, bei welchem außer dem identischen Start- und Endknoten jeder Knoten nur einmal auftaucht.

Ein Graph ist vollständig, wenn alle in ihm enthaltenen Knoten miteinander verbunden sind.

Erweitert man einen gerichteten Graphen G = (V, E), dessen Knoten als zu besuchende Städte und dessen Kanten als Verbindungen zwischen Städten zu verstehen sind, mit Kantengewichten, welche als Kantenlängen interpretiert werden sollen, für alle Kanten aus E(G) entsprechend einer Gewichtsfunktion Ȗ (ĺԹ, so kann man das Traveling Salesman Problem folgendermaßen formulieren:

Gesucht ist ein einfacher Kreis über alle Knoten von G, dessen Summe der Kantengewichte minimal ist.

Dies ist äquivalent zur Suche eines Hamiltonkreises mit minimaler Länge.

Ein Hamiltonkreis kann auch als Permutation, also als Anordnung der Elemente einer Menge, aufgefasst werden. In diesem Fall ist also diejenige Permutation ʌ gesucht, welche folgende Summe minimiert:

Man unterscheidet zwei grundsätzliche Variationen des TSP: Bei dem symmetrischen TSP sind die Hin-und Rückrichtungen auf einer Kante mit gleichen Kantengewichten versehen, wogegen bei asymmetrischen TSP-Instanzen diese Einschränkung nicht besteht.

3.3 Komplexität des TSP

Für eine Abschätzung der Komplexität einer TSP-Instanz mit n Städten wird die Anzahl aller Reisemöglichkeiten mit |[Abbildung in dieser Leseprobe nicht enthalten]abgeschätzt. Im schlechtesten Fall hat das TSP als/[Abbildung in dieser Leseprobe nicht enthalten] wobei p ein Polynom darstellen soll. Diesesאld(n) [Abbildung in dieser Leseprobe nicht enthalten]exponentielle Laufzeitverhalten lässt vermuten, dass das Problem des Handlungsreisenden ein Problem aus der Komplexitätsklasse NP ist.

Indem man das TSP auf das Entscheidungsproblem zurückführt, ob es zu einem gegebenen Graphen einen Hamilton-Kreis gibt oder nicht (also dem von Richard Karp formulierten Problem DIRECTED HAMILTON CIRCUIT (DHC)), lässt sich beweisen, dass das TSP NP-vollständig bzw. NP-äquivalent ist: In [Karp, 1972] wurde dazu das DHC über verschiedene Reduktionen auf das Erfüllbarkeitsproblem der Aussagenlogik (SAT) zurück geführt, für welches in [Cook, 1971] bereits der Beweis der NP-Vollständigkeit erbracht wurde.

Die Anzahl, der Lösungsmöglichkeiten lässt sich aber oft beträchtlich einschränken: So kann man in der Regel den Startpunkt der Tour frei wählen, so dass die Anzahl der Rundreisen auf (n-1)! sinkt. Noch mehr Knoten können bei der Untersuchung eingespart werden, wenn man ein symmetrisches TSP zu Grunde legt, dann fällt die Hälfte der möglichen Hamilton-Touren weg. Das symmetrische TSP liegt also in ȅ[1] /2(n - 1)!). Ferner kann der Suchraum weiter eingeschränkt werden, indem man die Lage der Knoten zueinander betrachtet: Wie Abbildung 2 zeigt, haben sich überkreuzende Kanten unter Verwendung einer Metrik, z.B. dem euklidischen Distanzmaß eine größere Länge, als wenn die gegenüberliegenden Verbindungen getauscht werden würden. Für praktische Anwendung ist die Gültigkeit der Dreiecksungleichungen zwar oft eine sinnvolle Einschränkung, dennoch muss nicht für alle Problemstellungen zwingend der direkte Weg auch der kürzere sein.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2:kreuzende Kanten bei metrischem TSP

Man nennt ein solches Problem, bei dem die Dreiecksungleichung erfüllt ist, ein ǻ-TSP.

Mittels der Grundlagen der Komplexitäts- und Graphentheorie ist es nun möglich, das in Kapitel 1 formulierte Königsberger Brückenproblem zu formalisieren und abzuschätzen. Der entscheidende Unterschied bei dem Brückenproblem ist, dass nicht ± wie im Falle des TSP ± jeder Knoten (bis auf den Anfangspunkt der Rundreise) genau einmal besucht werden muss, sondern jede Kante:

Sei G = (V, E) ein zusammenhängender Graph, bei dem Mehrfachkanten explizit zugelassen sind. Eine Knotenfolge (v0, v1,« vm) ist ein Euler-Kreis in G, wenn gilt: (vi-1, vi) mit 1 - i - m sind Kanten, vm = v0, d.h. Start-und Endknoten sind identisch und wenn unter diesen m Kanten jede Kante in E(G) genau einmal vorkommt. Ein Graph welcher einen Euler-Kreis enthält, wird Euler-Graph genannt. Das zugrunde liegende Entscheidungsproblem, ob ein Graph G ein Euler-Graph ist, lässt sich im Gegensatz zu DHC leicht beantworten: Wenn der Grad deg(v) eines jeden Knotens in E(G) gerade ist, handelt es sich bei G um einen Euler-Graphen, da der Euler-Kreis jeden .QRWHQ JHQDX VR RIW ÄEHWUHWHQ³ PXVV, wie er ihn verlässt.

Die Komplexität dieses Entscheidungsproblems ist offensichtlich in O( |E(G)| ), wodurch es als einfach bezeichnet werden kann.

Einige der im folgenden Abschnitt vorgestellten Verfahren basieren darauf, dass man in polynomieller Zeit einen Hamiltonkreis mit geringerer Pfadlänge aus einem Euler-Kreis extrahieren kann, indem die mehrfach vorkommenden Knoten in dem Euler-Kreis streicht. Mittels einem minimal aufspannenden Baum, welcher in O( |E(G)| log |V(G|) gefunden werden kann, lässt sich so eine Approximation für das ǻ-TSP aufstellen.

3.4 Algorithmen zur Lösung des TSP

Aufgrund der Beliebtheit, welches das TSP als NP-äquivalentes Benchmark-Problem für Optimierungsverfahren genießt, wurde es bereits mit den meisten, der auf Abbildung 1 dargestellten, Methoden zu Lösen versucht. Einige Lösungsansätze haben sich dabei aber als besonders ausgezeichnet:

Unter den exakten Methoden haben sich insbesondere auf Verzweigung und Schranke - Verfahren (Branch and Bound) beruhende Ansätze als leistungsfähig erwiesen, da durch die Held-Karp-Relaxation ([Held / Karp, 1970]) ± eine auf minimal aufspannenden Bäumen beruhende Methode zur Bestimmung einer scharfen unteren Schranke für das

TSP ± große Teilbäume bei der Suche ignoriert werden konnten.

Auch Schnittebenen-Verfahren als Weiterentwicklungen der polyedrischen Kombinatorik, welche aus den Ideen von [Dantzig et al., 1954] entstanden, wurden von Martin Grötschel und Manfred Padberg in diversen Publikationen erfolgreich auf das TSP appliziert.

Als aktuell erfolgreichste exakte Verfahren für das TSP gelten Verzweigung und Schnitt- Verfahren (Branch and Cut), welche Schnittebenen-Verfahren zur Ableitung unterer Schranken für Verzweigung und Schranke-Ansätze (Branch and Bound) anwenden. Bei den heuristischen Verfahren werden oft die, auf Karl Menger (vgl. [Menger, 1998, S. 130]) zurückgehenden, nächste-Nachbarn-Heuristiken genutzt, welche als ÄJLHULJH³ Verfahren zwar recht schnell sind, deren Lösungsqualität aber oft zu wünschen lässt. Andere Heuristiken versuchen durch Transformation der effizient berechenbaren minimalen Spannbäume des TSP-Graphen oder durch Einfügen von Städten in bestehende Teilgraphen Lösungen zu generieren.

Andere verbreitete Heuristiken verbessern bereits bestehende Lösungen durch den Austausch von Kanten, so dies zu einer Verbesserung führt (z.B. k-opt-Verfahren). Darauf baut auch die bisher leistungsfähigste Heuristik für das Problem des Handlungsreisenden auf: So hält eine Weiterentwicklung der Lin-Kernighan-Heuristik (mehr dazu in [Lin / Kernighan, 1973]) den zum 12.12. 2008 vorläufigen Rekord der Lösung einer 47.608 Städte TSP-Instanz (vgl. [Uni Halle, 2009])⁴.

Es ist anzumerken, dass nahezu alle der Optimierungsverfahren für das TSP ein symmetrisches und metrisches (meist euklidisches) Problem betrachten, dessen Komplexität zwar noch immer NP-vollständig ist, aber durch die in Abschnitt 3.3 genannten Einschränkungen ± insbesondere die der euklidischen Metrik, welche die Berechnung einer konvexen Hülle über die beteiligten Knoten ermöglicht ± wesentlich besser handhabbar ist. Soll ein allgemeines TSP gelöst werden, so dass die Lage der Knoten zueinander nicht einbezogen werden kann, eignen vor allem Metaheuristiken, da diese wenig problemspezifisches Wissen voraussetzen.

Dieses Kapitel hat kurz die Historie des TSP umrissen und in die Grundlagen der Graphentheorie eingeführt. Damit konnte das TSP formal als die Suche nach einem Hamilton-Kreis minimaler Länge formuliert werden, welche nicht in polynomieller Zeit möglich ist. Es wurden aber Möglichkeiten aufgezeigt, wie der Suchaufwand etwas entschärft werden kann.

[...]

---

¹ Methoden und Verfahren werden in diesem Kontext weitgehend synonym im Sinne einer Handlungsvorschrift zur Lösung eines Problems verwendet

² Für weitere Betrachtungen zur Approximationsqualität siehe Kapitel 6.

³ Siehe Kapitel 4

⁴ Mit dem TSP-Solver Concorde, welcher auf dem Branch and Cut ±Verfahren aufbaut, wurde 2006 schon eine 85900 Städte bzw. Bohrlöcher TSP-Instanz gelöst (vgl. [Applegate et al., 2006, S.522]). Aufgrund der benötigten 136 CPU-Jahre auf einem gemischten 64 x 2,4GHz Opteron und 192 x 2,66 GHz Xeon Cluster, kann dieser Aufwand aber wohl nicht als praktisch vertretbar bezeichnet werden.