Jan Wolters

Seminararbeit, Ruhr-Universität Bochum

INHALTSVERZEICHNIS I

  Inhaltsverzeichnis  

  Abbildungsverzeichnis  II

  Abkürzungsverzeichnis  III

1.  Einleitung  1

2.  Entwicklung  1

2.1.  Heuristiken  2

2.2.  Local Search  2

2.3.  Der Metropolis-Algorithmus Real Annealing  4

2.4.  Der Simulated Annealing-Algorithmus  6

2.5.  Parameter Abkühlungstabelle:  7

3.  Anwendungsbeispiele  9

3.1.  Travelling Salesman Problem Problem eines Touristen  9

3.2.  Vehicle Routing Problem Bochumer Privatbrauerei  12

4.  Fazit  14

5.  Literaturverzeichnis  15

6.  Anhang  

  Aufgabe Travelling Salesman A1  

  Aufgabe Bochumer Privatbrauerei A2  

ABBILDUNGSVERZEICHNIS II

  Abildungsverzeichnis  

2.1  Naturanaloge Verfahren im Überblick  2

2.2  Local Search Pseudo-Code  3

2.3  Vergleich zwischen Annealing und Quenching  5

2.4  Simulated Annealing Pseudo-Code  6

3.1-1  TSP zufällig generierte Startlösung  10

3.1-2  TSP Lösung nach dem ersten Tausch  10

3.1-3  TSP Lösung nach dem zweiten Tausch  11

3.2-1  VRP zufällig generierte Startlösung  12

3.2-2  VRP Lösung nach dem ersten Tausch  13

3.2-3  VRP Lösung nach dem zweiten Tausch  14

  Tabellenverzeichnis  

2.4  Analogie zw Metropolis Algorithmus und Simulated Annealing  6

2.5  Generische und problemspezifische Parameter  7

3.1-1  TSP Entfernungstabelle für die zufällig generierte Startlösung  10

3.1-2  TSP Entfernungstabelle nach dem ersten Tausch  10

3,1-3  TSP Entfernungstabelle nach dem zweiten Tausch  11

3.2-1  VRP Entfernungstabelle für die zufällig generierte Startlösung  12

3.2-2  VRP Entfernungstabelle nach dem ersten Tausch  13

3.2-3  VRP Entfernungstabelle nach dem zweiten Tausch  14

  ABKÜRZUNGSVERZEICHNIS III  

  Abkürzungsverzeichnis  

  α Kühlrate  

  c k Kontrollparameter  

  E i aktueller Energiezustand des Feststoffs  

  E j nachfolgender Energiezustand des Feststoffs  

  ∆E ij = E j - E i Energiedifferenz  

  f Kostenfunktion  

  i Lösung i  

  i start Startlösung  

  k B Boltzmannkonstante  

  L Anzahl der Durchläufe pro Temperatur  

  S Lösungsraum  

  S i Nachbarschaft von i  

  SA Simulated Annealing  

  T Temperatur  

  TSP Traveling Salesman Problem  

  VRP Vehicle Routing Problem  

1

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

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

1

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

2

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

3

Vgl. Feldmann (1999), S. 31.

4