taramath
Problem des Handlungsreisenden
unter Verwendung eines genetischen Algorithmus
Beschreibung
Gegeben seien feste Orte in der Ebene. Das Problem des Handlungsreisenden oder das Traveling Salesman Problem besteht darin, alle Orte genau einmal zu besuchen und anschließend wieder zum Ausgangspunkt zurückzukehren. Dabei soll die gesamte Route möglichst kurz sein.
Das Problem des Handlungsreisenden lässt sich als ganzzahliges Programm formulieren und (theoretisch) exakt lösen. Aufgrund der Komplexität ist dies praktisch jedoch in keiner vertretbaren Rechenzeit möglich. Wir bestimmen daher eine gute Lösung des Problems unter Verwendung eines genetischen Algorithmus (GA).
Beispiel 1
Im folgenden Beispiel bestimmen wir eine Lösung das Problem des Handlungsreisenden mit Orten unter Verwendung eines genetischen Algorithmus. Anschließend wird das Ergebnis graphisch dargestellt.
Tipp: Aktualisiere die Vorschau (mehrfach) und beobachte den Zielfunktionswert der bestimmten Lösung. Verändere dabei auch die Anzahl der Iterationen des genetischen Verfahrens. Vorschau aktualisieren