Routenoptimierung / Genetische Verfahren / Problem des Handlungsreisenden

Zurück zum Inhaltsverzeichnis

Problem des Handlungsreisenden

Ein Handlungsreisender soll Kunden in einer Reihe von Städten besuchen. Da er möglichst wenig unterwegs sein möchte sucht er die kürzeste mögliche Route für seine Tour. Bei einer kleinen Anzahl von Städten N läßt sich das Problem noch mit Hilfe der blinden Suche lösen. Die Anzahl der möglichen Wege läßt sich nach der Formel (N – 1) ! bestimmen. Für 5 Städte ergibt sich ein zu durchsuchender Suchraum von 24 Möglichkeiten, für 10 Städte bereits 362880 Möglichkeiten und für hundert Städte die unvorstellbare Anzahl von 9.33 * 10¹⁵⁵ Möglichkeiten.

Zum Beginn der Suche wird eine Anfangspopulation von zufällig generierten Routen erzeugt (Abb. oben, links). Für jedes Individuum wird die Länge seiner Route ermittelt. Diejenigen Lösungen, deren Route relativ kurz ist, reproduzieren sich. Während des Reproduktionsvorgangs wird die Route zufällig leicht verändert. Diejenigen Individuen, die relativ schlechte, also lange Routen tragen, sterben aus. Nur die erfolgreichen setzen sich durch. Nach dem Durchlaufen mehrerer Generationen wird eine Route gefunden, die sich gegenüber ihren Konkurrenten durchgesetzt hat und kürzer ist, als alle anderen bisher gefundenen Routen (Abbildung oben, rechts). Ob diese Route optimal ist, läßt sich aufgrund der oben geschilderten Problematik nicht klären. Sind die Städte kreisförmig angeordnet, findet das Verfahren garantiert die optimale Route (Siehe Abbildung unten). Ob dies jedoch als Beweis gewertet werden kann, daß auch bei einer zufälligen Anordnung der Städte immer die kürzeste Route gefunden wird, bleibt unklar. Trotzdem stellt die gefundene Route eine gute, wenn vielleicht auch nur suboptimale Lösung des Problems dar.

Technische Details

Zu Anfang wird eine Anzahl X von Städten zufällig über die Fläche verteilt. Beim Start des Programms werden den turtles der Startpopulation Listen zugewiesen. Jede Liste enthält die Ordnungsnummer der vorhandenen Städte in zufälliger Reihenfolge. Mittels der distance-Stammfunktion wird die Länge der Route für jede turtle berechnet. Die Reproduktion der Lösungskandidaten wird durch die hatch-Stammfunktion ermöglicht. hatch erlaubt das Klonen einer turtle. Sämtliche turtle-own-Variablen, also auch die Liste mit der Reihenfolge der Städte, werden an die geklonte turtle übergeben. Anschließend erfolgt die Mutation der Route. Dazu wird mit einem Konstrukt aus listenverarbeitenden Funktionen zufällig eine Stadt aus der Liste ausgewählt und verschoben. Aus der Liste

[stadt5 stadt2 stadt3 stadt1 stadt4 stadt5]

wird beispielsweise:

[stadt5 stadt3 stadt1 stadt4 stadt2 stadt5]

Nach der folgenden Berechnung der Routenlänge wird überprüft, ob die neue Route kürzer ist, als die vorhergehende. Ist dies der Fall, wird die Mutter-turtle verworfen. Da bei bestimmten Konstellationen die Route erst länger werden muß, um später in einem weiteren Schritt kürzer werden zu können wurde eine Variable selektionslaenge eingeführt. Sie erlaubt das Überleben von Lösungskandidaten, die nicht länger sind als selektionslaenge * bisher gefundene kürzeste Route. Bei einem Wert von 1,5 für selektionslaenge haben auch turtles eine Überlebenschance, deren Route nicht mehr als eineinhalb mal so lang ist, wie die bisher gefundene kürzeste Route. Ist die Längendifferenz größer, wird die geklonte und mutierte turtle verworfen.

Um lokale Minima weitgehend auszuschließen, finden Mutation und Selektion in mehreren (10 – 100) voneinander getrennten Populationen statt, deren Individuen nicht miteinander in Konkurrenz stehen.