LS 2

Home

Teaching (German)

Winter 04/05

Sommer 04

Diplomarbeiten (pdf)

Frühere Semester

Service

Travel

Staff

Contact

Private

External Links

Universität Dortmund

Computer Science Faculty

Collab. Research Center 531

Collab. Research Center 475

Research Cluster 1126

Student Advisory

Wintersemester 2006/07

Vorlesung Randomisierte Lokale Suche

Dozent: Ingo Wegener

Termine:
Di. 10:15-11:45 Uhr
Raum 304, Otto-Hahn-Str. 14.

Folien zur Vorlesung (werden laufend ergänzt/überarbeitet!)

Worum geht es in der Vorlesung?

Bei der randomisierten lokalen Suche zur Optimierung von Funktionen f: S --> R wird ein aktueller Suchpunkt x mit seinem f-Wert verwaltet. Ein neuer Suchpunkt x' wird in einer Nachbarschaft N(x) von x zufällig gewählt. Abhängig von f(x) und f(x') wird, eventuell zufällig, entschieden, ob x aktuell bleibt oder x' aktuell wird. Somit fallen der (1+1)-EA, der Metropolis-Algorithmus und Simulated Annealing in dieses Szenario. Die Ausgestaltung und die Grenzen dieser Optimierungsstrategien werden ausgeleuchtet. Am Ende steht ein sehr allgemeines Konvergenzresultat für Simulated Annealing.

Literatur

Emile Aarts und Jan Karel Lenstra (Hrsg.): Local Search in Combinatorial Optimization, Princeton Univ. Press, 2003. (Original: Wiley 1997)
Bei Amazon

Wil Michiels, Emile Aarts und Jan Korst: Theoretical Aspects of Local Search, Buchmanuskript, 2005.
Bei Amazon