Map Labeling mittels Simulated Annealing
und Genetischen Algorithmen
Seminar Label Placement
Leiter: Dr. A. Wolff
Referent: Tim Hoffmann
Trassenheide 16./17.Juni 2001
Fragestellung: Wie kann man eine solche Karte mit
Beschriftungen versehen?
Quelle:
Microsoft® Encarta
Weltatlas 2001
Gliederung
1. Labelplatzierung als Optimierungsproblems
2. Genetische Algorithmen
a) Grundlage und Ablauf der Algorithmen
b) Einige Varianten
3. Simulated Annealing
a) Grundlage und Ablauf des Algorithmus
b) Praktische Funktionsweise
4. Leistungsvergleiche der Algorithmen
1.
Labelplatzierung als
Optimierungsproblems
Das Allgemeine Optimierungsproblem:
Gegeben.: G , gG, c = c(g)
Gesucht: min (c(g))
1.
Labelplatzierung als
Optimierungsproblems
Das spezielle Optimierungsproblem
Grundmenge:
Mn über {0,..,8}
Zielfunktion:
Zahl der sich überschneidenden Label plus
2*Zahl der entfernten Label
minimieren
Quelle: Christensen et al. 1995
Quelle: Christensen et al. 1995
2.
Genetische Algorithmen
2.
Genetische Algorithmen
a) Grundlage und Ablauf der Algorithmen
2.
Genetische Algorithmen
b) Einige Varianten
 Lazy Hillclimber
 Lokal optimierter Genetischer Algorithmus (loGA)
 Rekombination der Elite (ERGA)
 Genetischer Algorithmus mit Fokussierung
 Genetischer Algorithmus mit speziellen
Crossover-Operatoren (Xover GA)
3.
Simulated Annealing
3. Simulated Annealing
a) Grundlage und Ablauf des Algorithmus
3. Simulated Annealing
b) Praktische Funktionsweise
4.
Leistungsvergleiche der Algorithmen
Quelle: van. Dijk et al. 1998
(verändert)

Das Allgemeine Optimierungsproblem