Information Technology Reference
In-Depth Information
• Verwendung natürlicher Codierungen,
• Einsatz sinnvoller Operatoren,
• Vollständige Abbildung des Problem- und Lösungsraumes und
• Erreichbarkeit aller Punkte des Problem- und Lösungsraumes mit positiver Wahr-
scheinlichkeit.
9.4.1
Travelling Sales als Optimierungsproblem
Die Aufgabenstellung des Travelling-Salesman-Problems ist es, die kürzeste Route durch
eine vorgegebene Menge von Punkten zu ermitteln, z. B. die Städte, die ein Handlungsrei-
sender auf einer Reise besuchen muss. Dieses Problem repräsentiert eine Klasse von Pro-
blemen (genannt: NP-vollständig), die sich durch eine extrem große Anzahl von Kombi-
nationsmöglichkeiten auszeichnen. Praktische Beispiele reichen von Fahrplangestaltung
bis zum Bau von Mikrochips. Es ist beweisbar, dass ab einer bestimmten Datenmenge,
z. B. viele zu besuchende Städte, die vollständige Lösung solcher Probleme so aufwendig
ist, dass Digitalcomputer niemals leistungsfähig genug werden können, um in der Lage zu
sein, solche Problem in einem annehmbaren Zeitraum zu lösen. Näherungslösungen mit
zumindest akzeptablen Ergebnissen sind daher das Ziel intensiver Forschung.
Um das Problem zu verstehen, soll zunächst davon ausgegangen werden, dass es 3
Städte zu besuchen gilt. Um hier eine Startroute festzulegen, hat man zunächst 3 Städte
zur Auswahl. Nach Auswahl der ersten Stadt, stehen nunmehr noch zwei Städe zur wei-
teren Auswahl und nach Besuch der zweiten Stadt steht nur noch eine Stadt zur Anreise
an. Alles in allem beschert das Problem demnach 3 × 2 × 1 und damit 6 alternative Routen,
zwischen denen es auszwählen gilt. Die Anzahl der Routen berechnet sich also mit Hilfe
der Fakultät, was bedeutet, dass die Anzahl der alternativen Routen mit der Anzahl der
Städte nahezu explodiert. So beträgt die Fakultät von 10 bereits 3.628.800 und die Fakul-
tät von 20 immense 2.432.902.008.176.640.000. Bereits bei dieser Anzahl von Städten
wird deutlich, dass eine angenäherte Lösung nur mit Hilfe von Computern berechnet wer-
den kann (Abb.
9.20
).
Zur Lösung eines solchen Problems lassen sich unterschiedliche Techniken, wie bei-
spielsweise Nearest neighbor-Algorithmen oder Techniken aus der Schwarm-Intelligenz
verwenden. In diesem Abschnitt soll ein genetischer Algorithmus eingesetzt werden, um
eine „gute“ Lösung zu finden. Um eine Technik zu verwenden, muss zunächst das Prob-
lem entsprechend modelliert werden, dass die aus der Modellierung resultierende Prob-
lemrepräsentation mit Hilfe dieser Technik, hier dem genetischen Algorithmus, verarbeitet
werden kann. Beispielsweise gilt hier die Anforderung, dass eine Route alle Städte be-
rücksichtigen muss und zusätzlich jede Stadt nur einmal angereist werden darf. Das wie-
derum schließt den Einbezug zufälliger Städte und das Vorkommen von Dublikaten aus.
Ein Typ von Mutation, um solche unzulässigen Lösungen auszuschießen ist die sogenann-
te Tausch-Mutation. In dieser Mutationsvariante kommen die Städte als wohl definierte
Ansammlung von Objekten vor, wobei zwei dieser Städte per Zufall die Position innerhalb
