Map Labeling mittels Map Labeling mittels Simulated AnnealingSimulated Annealing und und Genetischen AlgorithmenGenetischen Algorithmen

Seminar Label PlacementLeiter: Dr. A. Wolff

Referent: Tim HoffmannTrassenheide 16./17.Juni 2001

Fragestellung: Wie kann man eine solche Karte mit Fragestellung: Wie kann man eine solche Karte mit Beschriftungen versehen?Beschriftungen versehen?

Quelle:Quelle:

MicrosoftMicrosoft®® Encarta Encarta Weltatlas 2001Weltatlas 2001

GliederungGliederung

1.1. Labelplatzierung als OptimierungsproblemsLabelplatzierung als Optimierungsproblems

2.2. Genetische Algorithmen Genetische Algorithmen

a)a) Grundlage und Ablauf der AlgorithmenGrundlage und Ablauf der Algorithmen

b)b) Einige VariantenEinige Varianten

3.3. Simulated AnnealingSimulated Annealing

a)a) Grundlage und Ablauf des AlgorithmusGrundlage und Ablauf des Algorithmus

b)b) Praktische FunktionsweisePraktische Funktionsweise

4.4. Leistungsvergleiche der AlgorithmenLeistungsvergleiche der Algorithmen

1.1. Labelplatzierung alsLabelplatzierung als OptimierungsproblemsOptimierungsproblems

Das Allgemeine Optimierungsproblem: Das Allgemeine Optimierungsproblem: Gegeben.: G , gGegeben.: G , gG, c = c(g)G, c = c(g)

Gesucht: min (c(g))Gesucht: min (c(g))

1.1. Labelplatzierung als Labelplatzierung als OOptimierungsproblemsptimierungsproblems

Das spezielle OptimierungsproblemDas spezielle OptimierungsproblemGrundmenge: Grundmenge: MMnn über {0,..,8} über {0,..,8}

Zielfunktion:Zielfunktion: Zahl der sich über-Zahl der sich über-schneidenden Label plus schneidenden Label plus 2*Zahl der entfernten Label 2*Zahl der entfernten Label minimierenminimieren

Quelle: Christensen et al. 1995

Quelle: Christensen et al. 1995

2.2. Genetische AlgorithmenGenetische Algorithmen

2.2. Genetische Algorithmen Genetische Algorithmen a) Grundlage und Ablauf der a) Grundlage und Ablauf der

AlgorithmenAlgorithmen

2. 2. Genetische Algorithmen Genetische Algorithmen b) Einige Variantenb) Einige Varianten

Lazy HillclimberLokal optimierter Genetischer Algorithmus (loGA)Rekombination der Elite (ERGA)Genetischer Algorithmus mit Fokussierung Genetischer Algorithmus mit speziellen

Crossover-Operatoren (Xover GA)

3.3. Simulated Annealing Simulated Annealing

3.3. Simulated AnnealingSimulated Annealinga) Grundlage und Ablauf des Algorithmusa) Grundlage und Ablauf des Algorithmus

3.3. Simulated AnnealingSimulated Annealingb) Praktische Funktionsweiseb) Praktische Funktionsweise

4.4. Leistungsvergleiche der AlgorithmenLeistungsvergleiche der Algorithmen

Quelle: van. Dijk et al. 1998 Quelle: van. Dijk et al. 1998 (verändert)(verändert)