Simulated Annealing

[Termine] [Zusammenfassung] [Literatur]

Termine

Wann und wo donnerstags, 12-14 Uhr in der OH-14, Raum 304

erster Termin 18.10.2007

Vorbesprechung wird noch bekannt gegeben

Zusammenfassung

Simulated Annealing ist eine allgemeine randomisierte Suchheuristik, die häufig erfolgreich praktisch eingesetzt wird und theoretisch gut untersucht ist. Im Rahmen des Seminars werden verschiedene Aspekte von Simulated Annealing beleuchtet, dabei liegt der Schwerpunkt in der Analyse der Performanz bei der Anwendung im Optimierungskontext.

Ausgehend von ein oder zwei Arbeiten aus der unten stehenden Literaturliste sollen jeweils für alle Seminarteilnehmerinnen und Seminarteilnehmer nachvollziehbare Vorträge die verschiedenen Aspekte vorstellen und zur Diskussion stellen. Zu jedem Vortrag ist außerdem eine schriftliche Ausarbeitung zu erstellen, in der die benutzte Literatur prägnant und verständlich zusammengefasst ist.

Interessierte Studentinnen und Studenten können sich gerne jeder Zeit an mich wenden, entweder per e-mail oder persönlich in meinem Büro (OH-14, R 336).

Literatur

• S. Droste, T. Jansen, I. Wegener (2001): Dynamic parameter control in simple evolutionary algorithms. In W.N. Martin, W.M. Spears (Hrsg.): Foundation of Genetic Algorithms 6 (FOGA 2000). Morgan Kaufmann, 275--294.
• L. Ingber (1993): Simulated annealing: Practice versus theory. Mathematical and Computer Modelling 18(11):29--57.
• T. Jansen, I. Wegener (2007): A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation. Theoretical Computer Science. Erscheint.
• M. Jerrum, G.B. Sorkin (1998): The Metropolis algorithm for graph bisection. Discrete Applied Mathematics 82(1):155--175.
• S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi (1983): Optimization by simulated annealing. Science 220:671--680.
• K. Meer (2007): Simulated Annealing versus Metropolis for a TSP instance. Information Processing Letters. Erscheint.
• W. Michiels, E. Aarts, J. Korst (2007): Theoretical Aspects of Local Search. Springer. daraus: Kapitel 8: Asymptotic convergence of simulated annealing. 149--189.
• D. Mitra, F. Romeo, A. Sangiovanni-Vincentelli (1986): Convergence and finite-time behavior of simulated annealing. Advances in Applied Probability 18(3):747--771.
• A. Nolte, R. Schrader (2000): A note on the finite time behavior of simulated annealing. Mathematics of Operations Research 25(3):476--484.
• G.B. Sorkin (1991): Efficient simulated annealing on fractal energy landscapes. Algorithmica 6(1):367--418.
• K. Steinhöfel, A.A. Albrecht, C.K. Wong (1998): Various cooling schedules for simulated annealing applied to the job shop problem. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science. LNCS 1518, Springer, 260--279.
• I. Wegener (2005): Simulated annealing beats Metropolis in combinatorial optimization. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP). LNCS 3580, Springer, 589--601.