Lade Inhalt...

Simulated Annealing

Hausarbeit 2007 23 Seiten

BWL - Unternehmensforschung, Operations Research

Leseprobe

Inhaltsverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

1. Einleitung

2. Entwicklung
2.1. Heuristiken
2.2. Local Search
2.3. Der Metropolis-Algorithmus – Real Annealing
2.4. Der Simulated Annealing-Algorithmus
2.5. Parameter – Abkühlungstabelle:

3. Anwendungsbeispiele
3.1. Travelling Salesman Problem – Problem eines Touristen
3.2. Vehicle Routing Problem – Bochumer Privatbrauerei

4. Fazit

5. Literaturverzeichnis

6. Anhang

Aufgabe Travelling Salesman

Aufgabe Bochumer Privatbrauerei

Abildungsverzeichnis

2.1 Naturanaloge Verfahren im Überblick
2.2 Local Search Pseudo-Code
2.3 Vergleich zwischen Annealing und Quenching
2.4 Simulated Annealing Pseudo-Code

3.1-1 TSP – zufällig generierte Startlösung
3.1-2 TSP – Lösung nach dem ersten Tausch
3.1-3 TSP – Lösung nach dem zweiten Tausch
3.2-1 VRP – zufällig generierte Startlösung
3.2-2 VRP – Lösung nach dem ersten Tausch
3.2-3 VRP – Lösung nach dem zweiten Tausch

Tabellenverzeichnis

2.4 Analogie zw. Metropolis Algorithmus und Simulated Annealing
2.5 Generische und problemspezifische Parameter

3.1-1 TSP – Entfernungstabelle für die zufällig generierte Startlösung
3.1-2 TSP – Entfernungstabelle nach dem ersten Tausch
3,1-3 TSP – Entfernungstabelle nach dem zweiten Tausch
3.2-1 VRP – Entfernungstabelle für die zufällig generierte Startlösung
3.2-2 VRP – Entfernungstabelle nach dem ersten Tausch
3.2-3 VRP – Entfernungstabelle nach dem zweiten Tausch

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1. Einleitung

In dieser Seminararbeit wird Simulated Annealing (SA) vorgestellt und an- hand von zwei Anwendungsbeispielen erklärt.

2. Entwicklung

Simulated Annealing ist ein meta-heuristisches Optimierungsverfahren zum Lösen NP-harter kombinatorischer Optimierungsprobleme.1

Das Verfahren wurde von Kirkpatrick, Gelatt, Vecchi (1982; 1983) und unab- hängig davon von Cerny (1985) entwickelt.2

Der SA-Algorithmus ist eine Modifikation von Local Search. Der Vorteil gegenüber Local Search ist die Eigenschaft lokale Minima überwinden zu können, indem das Akzeptanzkriterium Verschlechterungen akzeptiert.3

SA ist ein naturanaloges Verfahren. Bei naturanalogen Verfahren ist das in- formationsauswertende bzw. steuernde Prinzip ist der Natur entlehnt. Das Auswahlkriterium von SA ist dem physikalischen Abkühlungsprozess von Feststoffen entlehnt.4

Naturanaloge Verfahren teilen sich in drei Klassen auf: Evolutionär, physi- kalisch und neuronal motivierte Verfahren. SA orientiert sich an den physi- kalischen Gesetzmäßigkeiten der Thermodynamik und gehört damit zu den physikalisch motivierten Verfahren.5

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.1 Naturanaloge Verfahren im Überblick (Quelle: In Anlehnung an Feldmann (1999), S. 72)

2.1 Heuristiken

Eine Heuristik ist ein problemspezifischer Algorithmus zur näherungsweisen Lösung von kombinatorischen Optimierungsproblemen. Bei einer exakten Lösung eines NP-harten Problems steigt der Rechenaufwand exponential mit der Größe des Problems. Der Vorteil von Heuristiken gegenüber exakten Verfahren ist, dass sie eine Lösung mit wesentlich weniger Rechenaufwand erreichen. Allerdings ist die dabei gefundene Näherungslösung nur selten auch die optimale Lösung, erreicht diese jedoch wesentlich effizienter als exakte Verfahren.6

Eine Meta-Heuristik ist ein iterativ ablaufender Prozeß, bei dem eine unter- geordnete Heuristik – in dieser Seminararbeit SA – durch ein übergeordnetes, allgemeines Prinzip der Informationsauswertung und Steuerung dirigiert wird.7

2.2 Local Search

Simulated Annealing ist eine Modifikation von Local Search, deshalb wird in diesem Kapitel kurz die funktionsweise von Local Search erläutert.8 Basiselemente des Algorithmus sind eine Startlösung, eine definierte Nach- barschaft, ein Selektionskriterium und ein Abbruchkriterium. Local Search beginnt mit einer zufälligen Startlösung i start des Problems und sucht den Lösungsraum S in einem iterativen Prozeß ab.

Abbildung in dieser Leseprobe nicht enthalten

Durch sukzessive geringfügiges Veränderungen wird versucht eine Verbesse- rung zu erreichen. Die Menge aller in einem Zug erreichbaren Lösungen S i sind die Nachbarschaft von i.

Abbildung in dieser Leseprobe nicht enthalten

Der Transformationsvorgang wird wiederholt, bis von der errreichten Lösung ausgehend keine Verbesserung in der Nachbarschaft der Lösung gefunden werden kann.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2. 2 Local Search Pseudo-Code

(Quelle: In Anlehnung an Aarts/Korst (1997), S. 9)

Der Erfolg von Local Search hängt stark von der Startposition ab. Da Local Search keinen Mechanismus zum Überwinden lokaler Minima besitzt. Bei großen Lösungsräumen mit vielen lokalen Minima sinkt die Wahrscheinlich- keit eine optimale Lösung zu finden.9

2.3 Der Metropolis Algorithmus - Real Annealing

Der Metropolis-Algorithmus beschreibt den Abkühlungsmechanismus von Feststoffen und wurde von Metropolis et al. (1953) entwickelt.

In der Hüttentechnik und der Werkstoffkunde bezeichnet das Anlassen (engl. Annealing) die Hitzebehandlung von Feststoffen und ist ein Bestandteil des Härten.

Zwei Verfahren werden beim Härten unterschieden, das Anlassen und das Abschrecken. Beim Anlassen wird das Metall stark erhitzt, mit steigender Temperatur nimmt es Energie auf und geht in einen Zustand über in dem die Moleküle frei beweglich sind (viskoser Zustand). Durch langsames Abküh- lung bilden die Moleküle regelmäßige Strukturen und eine energieminimale molekulare Anordnung wird erreicht.

Beim Abschrecken (Quenching) wird die Temperatur nach dem Erhitzen sehr schnell verringert und die energieminimale Anordnung wird nicht erreicht. Das Metall ist dann in einem meta-stabilen Zustand.

Das Erwärmen des Metalls entspricht einer temporären Verschlechterung. Über diese temporäre Verschlechterung kann ein ernergieärmerer Zustand erreicht werden. Die Eigenschaften des Metalls werden durch die Ge- schwindigkeit der Abkühlung bestimmt. Der Kotrollparameter dabei ist die Temperatur.

Metropolis et al. (1953) entwickelten den folgenden Algorithmus um diesen Zusammenhang zu beschreiben.10

Abbildung in dieser Leseprobe nicht enthalten

Die Menge aller in einem Zug erreichbaren Lösungen S sind die Nachbar- schaft von i. Aus dieser Menge wird zufällig ein Nachbar j gezogen.

Ist die Energiedifferenz kleiner gleich Null wird j als aktuelles Energieniveau übernommen.

Ist die Energiedifferenz größer Null wird die Annahme von j durch das Me tropoliskriterium gesteuert.

Metropoliskriterium:

Dabei wird j nur dann als aktueller Zustand akzeptiert, wenn eine generierte Zufallszahl zwischen 0 und 1 kleiner ist als als das Metropolis Kriterium.11

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2. 3 Vergleich zwischen Annealing und Quenching (Quelle: In Anlehnung an Dréo et al (2006), S. 6)

[...]


1Vgl. Floudas/Pardalos (2001), S.217.

2Vgl. Laarhoven/Aarts (1992), S.1.

3Vgl. Aarts/Korst (1997), S. 13; Schneider/Kirkpatrick (2006) S. 80.

4Vgl. Feldmann (1999), S. 31.

5 Vgl. Feldmann (1999), S. 71f.

6 Vgl. Grünert/Irnich (2005), S.213; Floudas/Pardalos (2001), S.217f.

7 Vgl. Feldmann (1999), S.31; Voss (2001), S. 552 - 554.

8 Vgl. Michalewicz/Fogel (2000), S. 64

9 Vgl. Aarts/Korst (1997), S.7ff.

10Vgl. Schneider/Kirkpatrick (2006), S. 69ff; Arts/Korst (1997), S. 13f.

11 Vgl. Grünert/Irnich (2005), S.211ff; Arts/Korst (1997), S. 15.

Details

Seiten
23
Jahr
2007
ISBN (eBook)
9783640298761
ISBN (Buch)
9783640303830
Dateigröße
1.2 MB
Sprache
Deutsch
Katalognummer
v124773
Institution / Hochschule
Ruhr-Universität Bochum
Note
1,7
Schlagworte
heuristische Optimierungsverfahren Metaheuristik Global optimization Travelling Sales Person TSP

Autor

Zurück

Titel: Simulated Annealing