Lösung des Traveling-Salesman-Problems mittels Monte-Carlo-Simulation und Simulated Annealing auf einem HPC-Cluster

Gliederung

Abbildungsverzeichnis

Tabellenverzeichnis

1 Simulation und kombinatorische Optimierung
1.1 Wichtige Grundbegriffe der Simulation
1.2 Arten der Simulation
1.3 Modellierung dynamischer Systeme
1.4 Optimierungsprobleme und Lösungsmöglichkeiten
1.5 Heuristiken und Metaheuristiken
1.6 Das Traveling-Salesman-Problem als klassisches Beispiel eines kombinatorischen Optimierungsproblems

2 Der Zufall und die Physik - der Weg des Simulated Annealing
2.1 Monte-Carlo-Simulation: Numerik mit Zufall
2.2 Statistische Mechanik und der Metropolis-Algorithmus
2.3 Die Vielfalt des Simulated Annealing: der Algorithmus und seine Parameter
2.3.1 Der Simulated-Annealing-Algorithmus
2.3.2 Die Wahl der Parameter
2.3.3 Konvergenzgeschwindigkeit versus Genauigkeit
2.3.4 Problemfelder
2.4 Anwendung des Simulated Annealing auf das Problem des Handlungsreisenden

3 Parallelisierung als Ausweg?
3.1 Möglichkeiten der Parallelisierung von Metaheuristiken
3.2 Möglichkeiten der Parallelisierung von Simulated Annealing
3.2.1 Schwierigkeiten bei der Parallelisierung von Simulated Annealing
3.2.2 Synchrone und asynchrone Parallelisierung
3.2.3 Problemabhängige und problemunabhängige Parallelisierung
3.2.4 Parallelisierung mit seriellen oder parallelen Zustandsübergängen
3.3 Parallelisierung des Simulated Annealing mittels Speculative Computation
3.3.1 Die grundlegende Vorgehensweise
3.3.2 Die Wahl der Baumgestalt
3.3.3 Verringerung des Kommunikationsaufwands
3.3.4 Generalized Speculative Computation

4 Zusammenfassung und Ausblick

Anhang
Anlage 1 - Monte-Carlo-Flächenberechnung
Anlage 2 - Beispiel zum Traveling-Salesman-Problem
Anlage 3 - Herleitung des Ausdrucks zur Berechnung der Beschleunigung einer bestimmten Baumgestalt

Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Das System als zentrales Element der Simulation

Abbildung 2: eindimensionales Gitter

Abbildung 3: Vergleich der Zustände beim Abkühlen

Abbildung 4: Verlauf der Akzeptanzwahrscheinlichkeit

Abbildung 5: Metropolis-Algorithmus

Abbildung 6: Pseudocode Simulated-Annealing-Algorithmus

Abbildung 7: Beispiel eines Traveling-Salesman-Problems mit 100 Städten

Abbildung 8: optimale Route des 100-Städte-Beispiels aus Abbildung 7

Abbildung 9: Parallelisierungstechniken nach Greening (1999, S.295)

Abbildung 10: Decision Tree Decomposition

Abbildung 11: Farming

Abbildung 12: Master-Slave-Beziehung beim One-Chain-Algorithmus

Abbildung 13: Kommunikationsaufwand beim Clustering-Algorithmus

Abbildung 14: Binärbaum mit drei Prozessoren

Abbildung 15: Zeitdiagramm für drei Prozessoren

Abbildung 16: Binärbaum mit sieben Prozessoren

Abbildung 17: Zeitdiagramm für sieben Prozessoren

Abbildung 18: Unbalancierter Binärbaum mit sieben Prozessoren

Abbildung 19: Übertragung der Zustandsänderungen in einem unbalancierten Baum mit zehn Prozessoren

Abbildung 20: N-ärer spekulativer Baum mit drei Stufen

Abbildung 21: Graph der Funktion f(x) = x2

Abbildung 22: Startlösung

Abbildung 23: Lösungskandidat 1

Abbildung 24: Lösungskandidat 2

Abbildung 25: optimale Tour

Tabellenverzeichnis

Tabelle 1: Distanzmatrix in km

Tabelle 2: Entfernungstabelle für die Startlösung

Tabelle 3: Entfernungen für Lösungskandidat 1

Tabelle 4: Entfernungen für Lösungskandidat 2

1 Simulation und kombinatorische Optimierung

„Da steh‘ ich nun, ich armer Thor! Und bin so klug als wie zuvor;“ [Goethe, 1808, V. 358-359]. Wer kennt nicht die Klage des Gelehrten Faust, der in Goethes bekanntester Tragödie die Unergiebigkeit menschlicher Existenz anprangert? Faust steht am Ende seines Lebens und am Anfang eines großen Dilemmas: „Mit Eifer habe ich mich der Studien be-flissen; weiß ich viel, doch möcht ich alles wissen.“ [Goethe, 1808, V.600-601]. Das Stre-ben nach Erkenntnis treibt den Menschen an, bereits Johann Wolfgang von Goethe wusste das und widmete diesem Thema mit der Arbeit an seinem Werk „Faust. Eine Tragödie von Goethe“ große Zeit seines Lebens.

Das Zeitalter immer leistungsfähigerer Computer liefert mit der Technik der Simulation ein weiteres Werkzeug, um zu erkennen, „was die Welt im Innersten zusammenhält“ [Goe-the, 1808, V.382-383]. Neben reiner Theorie und praktischen Experimenten ist diese als dritter großer Bereich in Wissenschaft und Forschung weitreichend akzeptiert. Die digitale Simulation stellt Methoden zur Verfügung, mit denen dynamische Systeme nachgebildet werden können, um Ergebnisse und Erkenntnisse zu gewinnen, die auf die Realität über-tragbar sind und sowohl kostengünstiger und schneller als auch in der Durchführung weni-ger gefährlich sind als reale Experimente. Zum Verständnis des in dieser Arbeit fokussier-ten Algorithmus müssen zunächst einige Grundlagen der Simulationstheorie erklärt wer-den. Im Folgenden soll deshalb auf wichtige Grundbegriffe sowie eine mögliche Untertei-lung der verschiedenen Arten der Simulation eingegangen werden, bevor ein Einblick in das Gebiet der kombinatorischen Optimierung gewährt wird, um kurz das Anwendungsge-biet der betrachteten Prozedur vorzustellen. Ein besonderes Augenmerk soll auf das Feld der Heuristiken und Metaheuristiken gerichtet werden, zu denen auch Simulated Annealing gehört, ein Algorithmus aus der Familie der Monte-Carlo-Simulation und Gegenstand die-ser Arbeit.

1.1 Wichtige Grundbegriffe der Simulation

Zunächst sollen einige wesentliche Begriffe erklärt werden, um eine Grundlage für das Verständnis des Bereiches der Simulation zu schaffen.

Das zentrale Element ist das System, welches ein Objekt der realen Umwelt darstellt, wenn es folgende Eigenschaften erfüllt:

− Systemzweck: Es liegt eine zu erfüllende Funktion vor.
− Systemstruktur: Die Funktion wird bestimmt durch eine spezifische Kombination von Teilelementen des Systems und deren Relationen untereinander.
− Unteilbarkeit: Der Systemzweck kann nicht erfüllt werden, wenn Teilelemente ent-fernt oder deren Verknüpfungen zerstört werden.

Wie in Abbildung 1 dargestellt, ist ein System demnach ein Objekt der Realität, welches durch einen bestimmten Zweck und seine nicht teilbare Struktur aus Elementen und deren

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Das System als zentrales Element der Simulation

Beziehungen zueinander definiert ist. Jedes dieser Systemelemente ist weiterhin durch At­tribute gekennzeichnet, die gewisse Merkmalsausprägungen annehmen können und die Relationen innerhalb des Objekts entstehen durch die Beschränkung, dass diese Ausprä-gungen nicht in jeder theoretisch denkbaren Kombination auftreten dürfen. Die Modifika-tion der Attributwerte erfolgt durch die gegenseitige Beeinflussung der Systemelemente mittels Kommunikation. Um chaotisches Systemverhalten zu simulieren, kann ein Zufalls-zahlengenerator eingesetzt werden, der zufällige Änderungen der Eigenschaften vornimmt. Die jeweilige Konfiguration der Attributwerte bestimmt dann den Systemzustand, der sich sowohl kontinuierlich als auch diskret, das heißt zu bestimmten Zeitpunkten, ändern kann. An dieser Stelle soll nur die diskrete Zustandsänderung von Bedeutung sein, die auch als Ereignis bezeichnet wird. Es gibt verschiedene Einflussfaktoren, die ein Ereignis auslösen können: Zum einen kann die äußere Umwelt auf das System wirken, zum anderen können aber auch Prozesse innerhalb des Objekts, bedingt durch die Relationen zwischen den Teilelementen, die Beschaffenheit des Systems beeinflussen. Zur vollständigen Beschrei- bung des Zustands eines Systems werden Zustandsgrößen verwendet, die voneinander unabhängig sind.

Die Zielsetzung der Simulation besteht darin, dynamische Systeme, die zeitlichen Verän-derungen unterliegen, zu analysieren und durch die Abbildung in einem Modell beschreib-bar und vor allem prognostizierbar zu machen. Durch wiederholte Durchführung von Si-mulationen und der Interpretation der Ergebnisse bezüglich Zustand und Verhalten des Systems kann das Modell als Abbild der Realität weiter verbessert werden, um bessere Lösungen und Vorhersagen für ein bestimmtes Problem finden zu können.

1.2 Arten der Simulation

Verfahren der Simulation können unter anderem in Bezug auf die verfügbaren Daten und Entscheidungsregeln differenziert werden. Auf der einen Seite existiert dann die determi-nistische Simulation, bei der alle Daten und Regeln bekannt und eindeutig sind. Das resul-tierende Modell bildet konstante Systemelemente und Relationen ab, es unterliegt keinerlei stochastischen Schwankungen von Parameterkonfigurationen. Der Zustand eines solchen Modells ist bei bekannten Startwerten jederzeit eindeutig vorhersehbar, was vor allem bei komplexen Systemen offensichtlich nicht der Fall sein kann, da möglicherweise auftreten-de zufallsbedingte Störgrößen und bestimmte Wechselwirkungen der Teilelemente für ge-wöhnlich nicht exakt identifiziert werden können. Im Gegensatz dazu sind die Systemei-genschaften und -relationen bei der stochastischen Simulation von zufälliger Natur. Exemplarisch sei hier das Warteschlangenproblem genannt, bei dem die Ankunftszeiten und somit die Bedienungszeiten willkürlich sind. Daher müssen vor Beginn einer solchen Simulation die Wahrscheinlichkeitsverteilungen der Eingabedaten empirisch bestimmt werden. Aus diesem Umstand ergibt sich weiterhin, dass der Zustand des Modellsystems nicht zu jedem beliebigen Zeitpunkt bestimmt werden kann. Vielmehr muss auch hierfür eine angemessene Reihe von Simulationen mit verschiedenen Eingabewerten durchgeführt werden, aus denen sich eine Wahrscheinlichkeitsverteilung der Systemzustände ergibt. Wichtige Voraussetzung ist ein passender Zufallszahlengenerator, der die Daten entspre-chend ihrer Verteilung erzeugt.

Im folgenden Abschnitt soll kurz dargestellt werden, wie dynamische Systeme mittels Mo-dellen beschrieben werden können und wie die Umsetzung im Computer erfolgt, um Simu-lationen zum Zweck der Optimierung durchzuführen.

1.3 Modellierung dynamischer Systeme

Ein System wird als dynamisch bezeichnet, wenn es, wie bereits erwähnt, zeitlichen Ver-änderungen unterliegt. Zur Beschreibung solcher Systeme werden Modelle benutzt, deren wesentliche Zielsetzung in der vereinfachten Abbildung eines Ausschnitts aus der Realität besteht. Allerdings ist diese Abstrahierung meist eine sehr komplexe Aufgabenstellung, da ein geeigneter Kompromiss bezüglich Umfang und Detaillierungsgrad der benötigten Da-ten gefunden werden muss, sodass das Modell auf der einen Seite die Realität korrekt wi-derspiegelt, aber auf der anderen Seite nicht zu umfangreich wird. Der wesentliche Schritt bei der Modellierung komplexer Systeme ist demnach das Herausfiltern der relevanten Informationen und deren Abbildung. Weiterhin ist zu beachten, dass ein in der Realität dynamisches System auch im Modell zeitabhängigen Veränderungen unterliegen muss und nicht nur Informationen über Systemzustände umfasst.

Eine Untersuchung auf der Basis der Simulation kann mittels Modellen auf zwei Arten stattfinden:

1. Black-Box-Ansatz: Lediglich das Verhalten des Systems wird mit dem Modell re- konstruiert, das heißt das Modellsystem hat der Anforderung zu genügen, dass es die Verhaltensweise des Vorbilds aus der Realität zeigt. Jegliche Merkmale der in-neren Beschaffenheit und Zusammensetzung sind nicht von Interesse, es wird aus-schließlich ein Abbild des Systemverhaltens geschaffen. Dieser Ansatz wird auch als beschreibendes Modell bezeichnet.

2. Glass-Box-Ansatz: Hierbei geht es um die Konstruktion der inneren Wirkungsstruk- tur des Objekts aus der Realität, das heißt das System selbst und nicht nur dessen Verhalten wird abgebildet. Voraussetzung für ein solches Modell ist eine umfang-reiche Untersuchung des nachzubildenden Objekts und Erkennung der wichtigen Elemente und Relationen, damit die anschließende Simulation bestenfalls Verhal-tensweisen erzeugt, die dem des Originals entsprechen. Diese Herangehensweise wird auch erklärendes Modell genannt.

Simulationen, die mit Hilfe von Computern durchgeführt werden, folgen immer dem Glass-Box-Ansatz, wobei die Mathematik genutzt wird, um ein formales Modell zu erstel-len, welches dann verarbeitet wird. Neben der Notwendigkeit der Modellerstellung ist es weiterhin erforderlich, dass bestimmte Beurteilungsgrößen, wie Beschränkungen, Gütema-ße und Wichtungen, für alle wichtigen Systemgrößen existieren, damit die Ergebnisse be-wertet werden können.

1.4 Optimierungsprobleme und Lösungsmöglichkeiten

Es wurde bereits einführend dargestellt, wie Objekte und Prozesse der Realität nachgebil-det werden können und welche Schwierigkeiten diese Aufgabe nach sich ziehen kann. Im Folgenden soll gezeigt werden, wie die auf Modellen komplexer Systeme basierende Si­mulation dazu genutzt werden kann, Optimierungsprobleme zu lösen. Ein Optimierungs-problem umfasst, kurz gesagt, das Finden der besten Lösung aus allen möglichen Lösun-gen.

Viele solcher Probleme sind sowohl theoretisch als auch praktisch von großer Wichtigkeit und beruhen auf der Suche nach der optimalen Konfiguration einer Menge von Variablen. Es werden zwei wesentliche Kategorien unterschieden: die Lösungen können entweder durch reellwertige oder durch diskrete Variablen kodiert sein. Letztere beinhalten die Klas-se der kombinatorischen Optimierungsprobleme, die an dieser Stelle betrachtet werden soll. Im Mittelpunkt dieser Art der Optimierung steht die Suche nach einem Objekt aus einer endlichen, oder abzählbar unendlichen, Menge, welches idealerweise die optimale Lösung darstellt. Dieses Objekt kann eine ganze Zahl, eine Teilmenge, eine Permutation oder auch eine Graphenstruktur sein. Nach Blum / Roli (2003, S.269) kann ein kombinato-risches Optimierungsproblem P = (S, f) definiert werden durch:

- eine Menge von Variablen X = {x1, x2, ... , xn} und deren Definitionsbereiche D1, D2, ... , Dn;
- Beschränkungen beziehungsweise Nebenbedingungen zwischen den Variablen und
- eine zu minimierende Zielfunktion¹ Abbildung in dieser Leseprobe nicht enthalten. S bezeichnet den Such- oder Lösungsraum:

Abbildung in dieser Leseprobe nicht enthalten

Jedes Element dieser Menge kann als Lösungskandidat betrachtet werden. Ziel ist das Fin-den einer Lösung s* E S mit minimalem Wert der Funktion f, das heißt

Abbildung in dieser Leseprobe nicht enthalten

wobei s* das globale Optimum von (S, f) und S* g S die Menge aller globalen optimalen Lösungen bezeichnet.

Ein naiver Ansatz zur Lösung eines solchen Optimierungsproblems besteht darin, alle möglichen zulässigen Kombinationen zu konstruieren und sie anhand der Zielfunktion zu bewerten. Da dies offensichtlich bei steigender Problemgröße zu hohem Aufwand führen würde, bietet es sich an, Simulation und Optimierung zu verbinden. Das verwendete Simu-lationsmodell stellt den für die Optimierung notwendigen Zusammenhang zwischen den Input- und den Outputvariablen her, indem mit Hilfe der Resultate der Simulation die zu minimierende Zielfunktion berechnet wird und anhand dieser Ergebnisse die Entschei-dungsvariablen wieder neu belegt und der Simulation übergeben werden. Dieser Kreislauf wird solange fortgesetzt, bis ein geeignetes Abbruchkriterium erfüllt ist, was nicht zwin-gend bedeutet, dass die optimale Lösung gefunden ist. Das in dieser Arbeit an späterer Stelle vorgestellte Simulated Annealing ist ein Vertreter der stochastischen Simulation, welcher exakt diese grundlegende Vorgehensweise umsetzt.

Aufgrund der praktischen Bedeutung kombinatorischer Optimierungsprobleme, zu denen beispielsweise das Rucksackproblem oder das Problem des Handlungsreisenden gehört, wurden in der Literatur viele verschiedene Algorithmen vorgeschlagen, die diese entweder vollständig oder näherungsweise zu lösen versuchen. Vollständig meint hier, dass garan-tiert für jede Instanz endlicher Größe in begrenzter Zeit ein Optimum gefunden wird. Wer-den jedoch Aufgabenstellungen betrachtet, die der Klasse der NP-vollständigen² Probleme angehören, so existiert bis heute kein deterministischer Algorithmus, der diese in polyno-mialer Zeit lösen kann. Solche Rechenmethoden benötigen meist exponentielle Rechenzeit, wobei der Exponent proportional zur Größe des Problems wächst, was für praktische Zwe-cke viel zu hoch ist. Aus diesem Grund rückte die Nutzung approximierender Verfahren immer mehr in den Vordergrund, die zwar die Garantie des Findens einer optimalen Lö-sung aufgeben, dafür aber gute Resultate in signifikant reduziertem Zeitumfang erzielen können. Solche Algorithmen, die der Simulation zur Lösung kombinatorischer Optimie-rungsprobleme dienen, werden Heuristiken genannt.

1.5 Heuristiken und Metaheuristiken

Der Begriff Heuristik bezeichnet die Kunst, mit wenig Wissen und eingeschränktem Zeit-budget zu guten Lösungen zu kommen. Diese Art der Problemlösung hat bereits eine lange und bedeutende Erfolgsgeschichte in der kombinatorischen Optimierung hinter sich ge-bracht und stellt häufig die einzige praktische Alternative im Umgang mit Probleminstan-zen realistischer Dimensionen und Eigenschaften dar. Als Gründe seien vor allem die leichte und schnelle Implementierbarkeit sowie die hohe Robustheit genannt, weshalb sie kostengünstig entwickelt und auf eine breite Klasse von Problemen angewendet werden können.

Es existieren zwei grundlegende Strategien: Divide-and-Conquer und iterative Verbesse-rung. Erstere Vorgehensweise zerlegt das Problem in Teilprobleme, die idealerweise dis-junkt sind, und löst diese unabhängig voneinander. Anschließend müssen die partiellen Ergebnisse zusammengeführt werden, um eine Lösung für das Gesamtproblem zu finden. Der zweite Ansatz beginnt mit einer bekannten Startkonfiguration und wendet dann eine standardisierte Operation zur Umordnung der Systemelemente an, bis eine Konfiguration entdeckt wird, welche die zugrunde liegende Kostenfunktion verbessert. Dieser Vorgang wird solange wiederholt, bis keine weiteren Verbesserungen gefunden werden können. Allerdings besteht bei diesen Methoden ein wesentlicher Nachteil darin, dass sie nach dem ersten gefundenen lokalen Optimum nicht fortfahren können, das heißt die Wahrschein-lichkeit sehr hoch ist, dass das globale Optimum nicht gefunden wird. Des Weiteren ist weder eine Abschätzung der Abweichung vom tatsächlichen Optimum noch eine dynami-sche Anpassung an spezielle Probleminstanzen möglich. Folglich entwickelten sich soge-nannte moderne Heuristiken, auch bekannt als Metaheuristiken, die versuchen diese Män-gel zu beseitigen. Im Prinzip ist diese Art eines approximierenden Algorithmus ein iterati-ver Prozess, welcher die Operationen untergeordneter problemspezifischer Heuristiken steuert und modifiziert, indem verschiedene Konzepte für die Untersuchung und Aus-schöpfung des Suchraums kombiniert werden, um effizient hochqualifizierte Lösungen zu finden.

Verwendung finden derartige Problemlösungsmethoden in zahlreichen Disziplinen, wie Mathematik, Operations Research, künstliche Intelligenz, und in vielfältigen Anwen-dungsgebieten, wie Design, Planung und Betrieb komplexer Systeme in Bereichen wie Transport oder Telekommunikation; Verwaltung und Allokation knapper Ressourcen; Sprach- und Bilderkennung und einiges mehr. Als Beispiele für Metaheuristiken seien die Tabu-Suche, Ameisensysteme, neuronale Netze, genetische Algorithmen und Simulated Annealing genannt. Es ist leicht zu erkennen, dass viele dieser Methoden von der Natur inspiriert sind, weshalb sie auch als naturanaloge Verfahren bezeichnet werden. Wesentli-cher Vorteil von Metaheuristiken ist, dass sie auf dem Weg zur optimalen Lösung Ver-schlechterungen des Zielfunktionswertes zulassen, um so eventuell lokale Optima zu ver-lassen und die Wahrscheinlichkeit des Findens des globalen Optimums zu erhöhen. Am Beispiel des Simulated Annealing soll später noch genauer gezeigt werden, wie dies umge-setzt wird und wie leistungsfähig ein solcher Lösungsweg ist. Es ist wichtig, dass stets ein Gleichgewicht zwischen Diversifikation und Intensivierung angestrebt wird, um einerseits schnell Regionen des Suchraums mit hochqualitativen Lösungen zu identifizieren und an-dererseits nicht zu viel Zeit in Bereichen zu verschwenden, die bereits untersucht sind oder keine guten Lösungen liefern. Aus diesem Grund kombiniert und erweitert der Simulated-Annealing-Algorithmus die beiden grundlegenden heuristischen Strategien: Die Einfüh-rung eines Temperaturparameters ermöglicht es, Probleme verschiedener Größe abzutren-nen, was eine angepasste Form des Divide-and-Conquer-Ansatzes darstellt. Weiterhin wird das Verfahren der iterativen Verbesserung angewendet, wobei jedoch temporäre Erhöhun-gen der Zielfunktionswerte erlaubt werden, wodurch lokale Minima zugunsten des globa-len Optimums verlassen werden können.

Allerdings bleibt zu beachten, dass trotz des Aufgebens der Lösungsgenauigkeit zu Guns-ten der Zeit, diese Herangehensweise bei größeren Problemdimensionen schnell viel Re-chenzeit in Anspruch nimmt. Um diesem Nachteil entgegen zu wirken, wurden zahlreiche Ansätze zur Parallelisierung von Metaheuristiken entwickelt, die im Zusammenhang mit Simulated Annealing noch vorgestellt werden sollen und einen effizienten Weg bieten, um die Laufzeit signifikant zu verkürzen.

Im folgenden Abschnitt erfolgt eine kurze Erklärung des Traveling-Salesman-Problems, bevor das Prinzip der Monte-Carlo-Simulation und der Simulated-Annealing-Algorithmus vorgestellt und auf dieses Problem angewendet werden sollen. Da, wie bereits erwähnt, sequentielle Methoden meist nicht ausreichen, um praktisch relevante Problemgrößen zu bearbeiten, sollen im Anschluss Möglichkeiten und Schwierigkeiten der Parallelisierung von Simulated Annealing gezeigt werden, wobei das Hauptaugenmerk auf den Ansatz des Speculative Computation gerichtet sein soll, welches einen effizienten Weg zur Verkür-zung der Rechenzeit darstellt ohne die Vorteile der seriellen Implementierung aufzugeben.

1.6 Das Traveling-Salesman-Problem als klassisches Beispiel eines kom-binatorischen Optimierungsproblems

Das Traveling-Salesman-Problem ist eines der bekanntesten und am besten untersuchtesten kombinatorischen Optimierungsprobleme, da es sehr einfach erklärt werden kann. Grund-sätzlich geht es um einen Handlungsreisenden, der in einer Rundreise n vorgegebene Städ-te besuchen soll, wobei er jede Stadt genau einmal passiert und letztendlich wieder am Startpunkt angelangt. Diese Route muss so geplant werden, dass die Gesamtlänge mini-miert wird, wobei anstelle von Entfernungen in diesem Zusammenhang natürlich auch Rei-sezeiten oder -kosten betrachtet werden können. Diese Aufgabe, welche zur Klasse der NP-vollständigen Probleme gehört, tritt in der Praxis sehr häufig auf, zum Beispiel in der Verkehrsplanung, Logistik oder beim Entwurf integrierter Schaltungen. Die Anzahl der Möglichkeiten für die Gestaltung der Rundreise wächst exponentiell mit der Anzahl der Städte und lässt sich unter Verwendung der symmetrischen Form des Traveling-Salesman-Problems wie folgt ausdrücken:

Abbildung in dieser Leseprobe nicht enthalten

Beispielhaft bedeutet dies bei 10 Städten: 181440 mögliche Kombinationen; bei 15 Städten steigt die Zahl der Möglichkeiten bereits auf 6,54 x 1011. Es ist leicht zu sehen, dass die naive Methode des Durchprobierens aller erdenklicher Lösungen einen riesigen Rechen-aufwand und demnach enorm viel Zeit in Anspruch nehmen würde. Hier können Metaheu-ristiken effizient Abhilfe schaffen, wobei zu beachten ist, dass die kürzeste Route trotzdem nicht mit Sicherheit gefunden werden kann, da diese Methoden nur eine Annäherung an das Optimum versprechen. Eine formale Definition sowie die Anwendung des Simulated Annealing zur Lösung des Problems des Handlungsreisenden finden sich im Kapitel 2.4 dieser Arbeit.

2 Der Zufall und die Physik - der Weg des Simulated Annealing

In diesem Abschnitt soll gezeigt werden, wie sich die Methode des Simulated Annealing basierend auf zwei wichtigen Faktoren entwickelt hat: dem Zufall und der Physik. Ersteres bezieht sich auf die Monte-Carlo-Simulation, welche eine wichtige Grundlage zur Durch-führung einer Simulation mittels Simulated Annealing bildet. Aus der Physik, insbesondere dem Gebiet der Thermodynamik, entsprang der Grundgedanke dieses Verfahrens, der ers-tmalig von Nicholas Metropolis 1953 aufgegriffen und mit Hilfe des Metropolis-Algorithmus formalisiert wurde. Im weiteren Verlauf der Forschung entwickelte sich auf Basis dieser Prozedur das Simulated Annealing, welches eine vielversprechende Methode zur Lösung kombinatorischer Optimierungsprobleme darstellt, die aus der Natur inspiriert wurde.

2.1 Monte-Carlo-Simulation: Numerik mit Zufall

Monte Carlo, bekannt durch das berühmte Casino an der Côte d’Azur, ist Sinnbild für das Glücksspiel mit über 1600 einarmigen Banditen und zahlreichen Spieltischen. Daher scheint es nicht verwunderlich, dass dieser Ort als Namenspate für eine Simulationstechnik fungiert, die auf der Nutzung von Zufallszahlen basiert. Bei diesem Verfahren werden ma-thematische oder physikalische Prozesse durch Zufallsexperimente nachgebildet. Die Idee, Berechnungsmodelle auf Basis von Zufallszahlen zu entwickeln, ist nicht neu - Ansätze für eine solche Vorgehensweise gab es bereits im 18. Jahrhundert. Allerdings begann erst in den 40er Jahren des vorigen Jahrhunderts die systematische Erforschung der theoretischen Grundlagen solcher Verfahren. Zu dieser Zeit nutzten beispielsweise Stanislaw Ulam, Ni­cholas Metropolis und John von Neumann, die in Los Alamos an der Entwicklung der Atombombe beteiligt waren, die Monte-Carlo-Methode zur Berechnung komplizierter In-tegrale. Ein einfaches und nachvollziehbares Beispiel zur Anwendung dieses Prinzips ist im Anhang (Anlage 1) beschrieben.

Berechnungen, die auf dem Zufall basieren, benötigen möglichst viel Zahlenmaterial, um verlässlich zu sein. Mit der steigenden Leistungsfähigkeit der Computer in den letzten Jah-ren wuchs daher die Bedeutung der Monte-Carlo-Simulation für praktische Anwendungen, da die effiziente Erzeugung einer großen Menge von Zufallszahlen viel Rechenleistung beansprucht. Besonders wichtig ist die Vernetzung von mehreren Rechnern zu sogenann-ten Computerclustern, die das Ziel verfolgt, die Rechenkapazität und Verfügbarkeit der einzelnen Computer zu steigern. Damit können heutzutage Rechenleistungen erreicht wer-den, die vor ein paar Jahren kaum vorstellbar waren.

Doch wie kann die Verwendung des Zufalls bei der Simulation dynamischer Modelle so-wie der Lösung kombinatorischer Optimierungsprobleme helfen? Obwohl die Einbezie-hung von Zufall auf den ersten Blick kontraproduktiv erscheint, kann festgestellt werden, dass unter bestimmten Bedingungen vorteilhafte Effekte erzielt werden können. Eine der Rollen des Zufalls in Verfahren der stochastischen Suche ist das Erlauben spontaner Be-wegungen in noch nicht erforschte Gebiete des Such- oder Lösungsraums, welche mögli-cherweise einen unerwartet guten Wert für den aktuell zu betrachtenden Lösungskandida-ten liefern. Damit kann der Zufall den notwendigen Anstoß liefern, um zum Beispiel auf der Suche nach dem globalen Optimum aus einem lokalen zu entkommen. Wie in 1.5 er-klärt wurde, ist das Verharren in lokalen Optima ein häufiges und nur schwer lösbares Problem heuristischer Methoden, weshalb die Verbindung von Heuristiken und Monte-Carlo-Verfahren einen möglichen Ausweg darstellt. Dass diese Kombination zu funktio-nieren scheint, zeigt der Erfolg des Simulated Annealing.

Im folgenden Abschnitt soll nun dargestellt werden, wie der zweite wichtige Faktor die Entwicklung des Simulated Annealing beeinflusst(e) - die Physik.

2.2 Statistische Mechanik und der Metropolis-Algorithmus

Simulated Annealing wird üblicherweise nachgesagt, es sei die älteste unter den Metaheu-ristiken und einer der ersten Algorithmen, die über eine explizite Strategie verfügten, um aus einem lokalen Optimum zu entkommen. Die Ursprünge dieses Verfahrens liegen in der statistischen Mechanik, welche die theoretische und experimentelle Analyse zahlreicher, fundamentaler Eigenschaften von Systemen vieler Teilchen beschreibt und heutzutage oft mit der statistischen Thermodynamik gleichgesetzt wird. Ausgangspunkt ist die prinzipiel-le Überlegung, dass ein makroskopisches System aus sehr vielen einzelnen Teilchen be-steht, deren Zustand zum einen unbekannt und zum anderen zeitlich variabel ist.

In Anlehnung an Černý (1985) und Kirkpatrick et al. (1983) sollen die grundlegenden Prinzipien im Folgenden anhand eines Beispiels beschrieben werden. Zunächst wird ein eindimensionales Gitter betrachtet, wobei sich an jedem Punkt dieses Gitters ein kleiner Pfeil befindet, der in genau zwei Zuständen existieren kann: nach oben oder nach unten zeigend (siehe Abbildung 2).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: eindimensionales Gitter [Černý, 1985, S.43]

Der Zufall und die Physik - der Weg des Simulated Annealing 12

Wenn das Gitter N Punkte hat, dann gibt es 2N Möglichkeiten für die Anordnung der Orientierung der Pfeile, also gibt es 2N mögliche Konfigurationen des Systems. Weiterhin soll angenommen werden, dass das System in jedem Zustand eine definierte Energie be-sitzt, die für unterschiedliche Konfigurationen nicht notwendigerweise verschieden sein muss. Es gilt zum Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

wenn n.(n_) die Anzahl der Pfeile ist, die nach oben (unten) zeigen, und B eine Konstan-te. Die physikalische Praxis hat gezeigt, dass große Systeme dieser Art sich spontan dem Gleichgewichtszustand nähern, häufig ungeachtet der Ausgangskonfiguration. Allerdings ist dieses thermische Gleichgewicht keinesfalls eine statische Situation. Vielmehr verän-dert das System zufällig seinen Zustand, meist aufgrund von Interaktionen mit der Umge-bung, von einer möglichen Konfiguration in eine andere so, dass die Wahrscheinlichkeit P5 das System in einem bestimmten Zustand s zu finden, gegeben ist durch die Boltzmann-Gibbs-Verteilung:

Abbildung in dieser Leseprobe nicht enthalten

Der Gewichtungsfaktor, der die Wahrscheinlichkeit bestimmt, dass sich ein System im thermodynamischen Gleichgewicht bei Temperatur T im Zustand s befindet, ist der soge-nannte Boltzmann-Faktor:

Abbildung in dieser Leseprobe nicht enthalten

wobei kB die Boltzmann-Konstante bezeichnet und E(s) die Energie des Zustandes s. Der Boltzmann-Faktor an sich stellt noch keine Wahrscheinlichkeit dar, da er noch nicht nor- malisiert ist. Daher wird der Normalisierungsfaktor ,1 > 0 hinzugefügt, wobei Z die soge- nannte Zustandssumme bezeichnet, das heißt die Summe aller Boltzmann-Faktoren für alle Zustände des Systems. Nun kann unter Verwendung eines Computers das Verhalten des Systems modelliert werden, indem mit Hilfe eines geeigneten Monte-Carlo-Algorithmus die zufällige Änderung des Zustands von einer Konfiguration in eine andere simuliert wird. Wenn diese Simulation mit einer willkürlichen Konfiguration gestartet wird, kann der Gleichgewichtszustand nach einer vernünftigen Anzahl von Monte-Carlo-Durchläufen erreicht werden. Erkennbar wird dies, wenn die Energie der generierten Konfigurationen beginnt um einen bestimmten Wert zu schwanken.

Zusammenfassend lässt sich sagen, dass sich große Systeme bei gegebener Temperatur spontan dem Gleichgewichtszustand annähern, welcher charakterisiert ist durch einen be-stimmten Mittelwert der Energie, der von der Temperatur abhängt. Durch die Simulation des Übergangs zum Gleichgewicht und die Verringerung der Temperatur können immer kleinere Werte der mittleren Energie des Systems gefunden werden. Dies ist auch die grundlegende Vorgehensweise des Simulated Annealing, um zum Beispiel für das Trave­ling-Salesman-Problem näherungsweise Lösungen zu finden. Die mittlere Energie ent-spricht der Länge der Rundreise, die minimiert werden soll. Die Verwirklichung der ma-thematischen Analogie zwischen Optimierungsproblemen, insbesondere dem Traveling-Salesman-Problem, und thermodynamischen Systemen soll später noch genauer aufgezeigt werden.

Zu Beginn dieses Kapitels wurde erwähnt, dass das Simulated Annealing von der Natur inspiriert wurde. Der physikalische Prozess, der diesem Algorithmus zugrunde liegt, ist das Verhalten von abkühlenden Substanzen. Allerdings gibt es kein deutsches Wort, das dem englischen ‚annealing‘ exakt entspricht. Der Begriff könnte in etwa mit „Erhitzen und dann langsam Abkühlen“ erfasst werden. Dies wird zum Beispiel am Ausglühungsprozess von Metallen deutlich, bei dem die Metalle zunächst in einem Wärmebad erhitzt und zum Schmelzen gebracht und dann wieder langsam abgekühlt werden. Zu Beginn sind die Atome des Metalls in einem festen Gitter eingebunden. Bei steigender Temperatur wäh-rend des Erhitzens wird diese ursprüngliche Struktur zerstört, denn die Atome beginnen sich aus ihren Bindungen zu lösen und zu bewegen. Im flüssigen Zustand, also im ge-schmolzenen Metall, haben die Atome dann willkürliche Positionen und verfügen über eine hohe Mobilität, das heißt sie können sich nahezu frei bewegen. Wird die Substanz anschließend langsam abgekühlt, suchen sich die Teilchen neue Bindungen, wobei sie sich oft regelmäßiger verteilen als vorher, sodass eine Art kristallförmiger Aufbau entsteht. Diese ausgerichtete Struktur entspricht dann dem minimalen Energiezustand des Systems. Der entscheidende Punkt in diesem Prozess ist das langsame Abkühlen des Metalls, denn ein zu schnelles Senken der Temperatur würde einem extremen „Abschrecken“ von hohen Temperaturen auf 0 entsprechen, was als „Quenching“ bezeichnet wird. In diesem Fall wird die Abkühlung schneller durchgeführt als die Atome ein thermisches Gleichgewicht bei jeder Temperaturstufe erreichen können. Daher ist es wichtig, dass zwischenzeitlich auch Erhöhungen der Energie akzeptiert werden. Dies kann anschaulich an einem kleinen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Vergleich der Zustände beim Abkühlen [Wolters, 2007, S.5]

Versuch erklärt werden: Werden einige Kugeln willkürlich in ein Gefäß geworfen, so lie-gen sie zu Beginn wahrscheinlich sehr unordentlich verteilt. Um sie zu ordnen, könnte das Gefäß geschüttelt werden. Dies würde die Unordnung zunächst erhöhen, denn die Kugeln fliegen konfus durcheinander. Wenn der Vorgang stetig verlangsamt wird, dann ordnen sie sich ganz von selbst. Wird das Schütteln jedoch allzu plötzlich abgebrochen, werden sie noch relativ chaotisch und nicht ganz dicht beieinander liegen bleiben. Abbildung 3 ver-deutlicht die verschiedenen Zustandsveränderungen, wenn die Abkühlung langsam (An­nealing) oder sehr schnell (Quenching) erfolgt.

Das grundlegende Prinzip hinter dem Simulated Annealing ist das langsame Abkühlen von Substanzen, um in einem thermischen Gleichgewicht den minimalen Energiezustand zu erreichen. Nun muss dieser Grundgedanke auf die Optimierung übertragen werden. Dies geschieht im Wesentlichen dadurch, dass der Energiezustand sinnbildlich auf eine zu mi-nimierende Zielfunktion abgebildet wird. Damit kann analog dem Verfahren in der Natur zur Minimierung der mittleren Energie eines Systems im thermischen Gleichgewicht folg-lich der Zielfunktionswert eines kombinatorischen Optimierungsproblems minimiert wer-den. Wie im physikalischen Abkühlungsprozess, der während der Anordnung der Atome temporäre Zustände höherer Energie erlaubt, akzeptiert auch Simulated Annealing tempo-räre Erhöhungen der Werte der Zielfunktion, da dies helfen kann, lokale Minima zu verlas-sen und so das globale Optimum zu erreichen. Die kritische Komponente des Algorithmus ist die mathematische Analogie zur Abkühlungsgeschwindigkeit physikalischer Prozesse, denn die Wahl dieses implementierungs- und problemspezifischen Abkühlungsschemas hat starke Auswirkungen auf Erfolg oder Misserfolg der Simulation.

[...]

---

¹ Die Maximierung einer Funktion f entspricht der Minimierung von -f.

² Die Abkürzung NP steht für nichtdeterministisch polynomial.