Mike Preuss  •  Algorithm Engineering  •  TU Dortmund
	Solving Map Labeling Problems by Means of Evolution Strategies

Solving Map Labeling Problems by Means of Evolution Strategies

Was soviel bedeutet wie der Versuch, mithilfe eines 'universalen' Optimierungsverfahrens ein Problem zu lösen, dass sich nur recht schwer quantifizieren lässt. In der einfachsten Variante geht es darum, die Beschriftungen auf einer Karte so anzuordnen, dass sich keine Überschneidungen mit den 'features', d.h. den Objekten der Karte ergeben. Diese Zielsetzung lässt sich beliebig verkomplizieren, wenn man zusätzlich sicherstellen möchte, dass:

• sowohl die Objekte als auch ihre Beschriftungen nahezu beliebige Grösse und Form haben können,
• durch die Positionierung eine eindeutige Zuordnung zwischen bezeichnetem Objekt und seiner Beschriftung möglich ist,
• eine möglichst gleichmässige Verteilung der Bezeichner erzeugt wird, um 'Cluster' zu vermeiden, welche die Lesbarkeit erschweren,
• neben der theoretischen Realisierbarkeit auch optische bzw. gestalterische Grundsätze aus der Kartographie berücksichtigt werden.

Ich habe das Problem etwas eingeschränkt: es werden nur 'point features', d.h. Objekte ohne Flächenausdehnung berücksichtigt. Diese lassen sich durch einen Kreis darstellen, dessen Radius die 'Wichtigkeit' des Objektes reflektiert. Die Beschriftungen haben zwar verschiedene Größen, werden aber immer durch umschriebene Rechtecke dargestellt. Die eindeutige Zuordnbarkeit soll durch eine angegebene Minimal-/Maximalentfernung zwischen Objekt und Beschriftung sichergestellt werden.

Eine gleichmässige Verteilung wird in der Zielfunktion nicht berücksichtigt, lediglich einige statistische Maße dazu werden online zur Verfügung gestellt. Bei der Bewertung der relativen Position von Objekt und Beschriftung habe ich versucht, die Regeln von Eduard Imhof in eine mathematische Form zu bringen.

Die Diplomarbeit hatte nicht zum Ziel, ein fertiges Software-Produkt zu erstellen, sondern sollte eher als eine Machbarkeitsstudie angesehen werden, inwiefern sich Evolutionäre Algorithmen für die Bearbeitung des Map Labeling Problems eignen. Als Fazit aus der Arbeit kann diese Frage wohl positiv beantwortet werden, obgleich es bis zur praktischen Einsetzbarkeit noch ein weiter Weg sein kann...

Hier kann man:
	Die Diplomarbeit downloaden (1481 kByte)