Optimierung mit evolutionären Algorithmen: das Traveling-Salesman-Problem

Autor: Nils Becker

Das Traveling-Salesman-Problem – oder „Problem des Handelsreisenden“ – ist ein in der Informatik bekanntes Optimierungsproblem. Bildlich gesprochen: Der „Handelsreisende“ hat eine Palette von Produkten, die er verkaufen möchte. Deswegen reist er von Stadt zu Stadt und bietet seine Waren an. Um Geld zu sparen, möchte er die Strecke, die er zurücklegen muss, minimieren. Je nachdem in welcher Reihenfolge er die Städte besucht können hohe Fahrtkosten entstehen.

Das Problem scheint trivial zu sein, ist es aber nicht. Bei drei Städten sind die möglichen Reihenfolgen noch sehr eingeschränkt. Es gibt sechs verschiedene Möglichkeiten die Zielorte nacheinander zu besuchen. Bei zehn Städten sind es schon mehr als 3,6 Millionen Kombinationen! Alle Möglichkeiten zu prüfen, funktioniert nicht mehr. Daher werden anderweitige Lösungsmethoden benötigt.

Biologie als Vorbild: Evolutionärer Algorithmus

Hierzu kann ein evolutionärer Algorithmus eingesetzt werden. Evolutionäre Algorithmen sind ein von der Biologie inspiriertes Optimierungsverfahren. Dabei gibt es eine Anfangspopulation, aus der in jeder Iteration „Nachkommen“ generiert werden. Diese werden anschließend anhand einer Fitnessfunktion bewertet und selektiert, ganz nach dem Motto „Survival of the fittest“. Aus den besten „Individuen“ wird eine neue Generation erzeugt. Dabei werden die Genome der „Elternteile“ miteinander kombiniert. Die neue Generation unterläuft anschließend einen Mutationsprozess, wodurch ein Teil des Genoms zufällig geändert wird.

So viel zur Theorie, doch wie sieht das in der Praxis aus? Um das Problem des Handelsreisenden zu lösen, müssen erstmal die Städte ausgewählt werden, die besucht werden sollen. Hier bieten sich die Hauptstädte Deutschlands an. Neben den Städtenamen wird deren geographische Lage benötigt. Der Datensatz sieht wie folgt aus:

stadt,breitengrad,laengengrad
Berlin,52.5170365,13.3888599
Düsseldorf,51.2254018,6.7763137
Kiel,54.3227085,10.135555
Potsdam,52.4009309,13.0591397
Magdeburg,52.1315889,11.6399609
Dresden,51.0493286,13.7381437
München,48.1371079,11.5753822
Stuttgart,48.7784485,9.1800132
Saarbrücken,49.234362,6.996379
Mainz,50.0012314,8.2762513
Wiesbaden,50.0820384,8.2416556
Erfurt,50.9777974,11.0287364
Hannover,52.3744779,9.7385532
Schwerin,53.6288297,11.4148038
Hamburg,53.550341,10.000654
Bremen,53.0758196,8.8071646

Um den Datensatz einzulesen kann die Pandas-Bibliothek verwendet werden. Nebenbei können weitere hilfreiche Bibliotheken importiert werden, wie die Geopy-Bibliothek, welche für die Berechnung der Distanz zwischen zwei geographischen Koordinaten genutzt wird.

Da nun das zu optimierende Problem und die Daten bekannt sind, kann eine entsprechende Codierung des Genoms implementiert werden. Weil die Reihenfolge der zu besuchenden Städte optimiert werden soll, besteht das Genom jedes Individuums aus einer Permutation der Städtenamen, welche in einer Liste gehalten werden.

Die Initialisierung der Anfangspopulation geschieht mit folgendem Code:

Der Code generiert 100 Permutationen auf der Menge der Städtenamen. Der nächste Schritt ist die Beurteilung der Individuen anhand einer Fitnessfunktion. Als solche bietet sich die Distanz der Reise an. Da es sich hierbei um geographische Koordinaten handelt, kann nicht die euklidische Distanz verwendet werden, da sonst die Erdkrümmung außer Acht gelassen würde. Die Geopy-Bibliothek bietet eine entsprechende Funktion zur Abstandsbestimmung an.

Die Fitnessfunktion sieht dann wie folgt aus:

Damit die Fitnessfunktion funktioniert, wird noch eine weitere Funktion benötigt, die die Koordinaten anhand des Städtenamens zurückgibt.

Der nächste Schritt führt schon in die Optimierungsschleife, daher wird ein passendes Abbruchkriterium benötigt. In diesem Fall wird die Suche abgebrochen, sobald nach 1.000 Iterationen keine Verbesserung der Fitness beim besten Individuum erzielt wurde. Die Beurteilung der Fitness der Individuen findet direkt zu Beginn der Optimierungsschleife statt.

Danach findet die Selektion statt. Hier gibt es viele verschiedene Möglichkeiten die Individuen auszuwählen. Eine einfache und effektive Variante ist, die besten Individuen der Population zu verwenden.

Damit eine höhere Diversität bei der Generierung der Nachkommen gewährleistet ist, werden die ausgewählten Individuen gemischt. Für jedes Elternpaar werden nun zwei Nachkommen mittels Rekombination generiert. Es gibt verschiedene Arten wie die Rekombination stattfinden kann. Die ausgewählte Methode hängt vom Anwendungsfall ab. In diesem Fall liegt eine Besonderheit vor, da jede Stadt nur einmal im Lösungskandidaten vorhanden sein darf. Es muss sichergestellt sein, dass bei der Rekombination keine ungültigen Individuen generiert werden. Dies wäre bei einem gewöhnlichen Crossover zum Beispiel der Fall. Daher wird das sogenannte PMX-Crossover mit zwei Crossoverpunkten verwendet.

Die Crossoverpunkte werden dabei zufällig gewählt. Es werden für jedes Elternpaar zwei Nachkommen generiert. Anschließend findet eine Mutation der Nachkommen statt, indem zwei Städte die Position tauschen. Die zu tauschenden Positionen werden zufällig ausgewählt. Die Eltern werden nicht verändert, sodass gewährleistet ist, dass die besten Individuen in der nächsten Generation erhalten bleiben. Die neue Generation besteht dann aus den Eltern und den generierten Nachkommen.

Das ist auch schon die komplette Optimierungsschleife. Zu beachten ist, dass die Lösung nur eine Approximation ist. Es ist nicht garantiert, dass die abschließende Lösung tatsächlich die beste ist. Als Letztes muss noch das beste Individuum beziehungsweise die Lösung ausgegeben und dargestellt werden. Hierfür kann die Plotly-Bibliothek verwendet werden. Dabei wird als Erstes ein Pandas-Datenframe mit den Städten entsprechend der gefundenen Reihenfolge aufgebaut. Die erste Stadt in der Lösung wird am Ende nochmal angehängt, schließlich soll es eine komplette Runde sein. Die Methode line_geo plottet anschließend die im Datenframe befindlichen Koordinaten und Linien zwischen den einzelnen Datenpunkten auf eine Karte.

Man kann die verschiedenen Parameter weiter anpassen und das Verfahren mehrmals laufen lassen, um bessere Ergebnisse zu erzielen. So kann man zum Beispiel die Größe der Elternpopulation verringern, dadurch wird die Berechnung beschleunigt. Allerdings kann die Qualität des Ergebnisses darunter leiden. Es empfiehlt sich verschiedene Parameterkombinationen auszuprobieren, um das optimale Ergebnis zu erreichen. Das Genom der unten abgebildeten Route sieht wie folgt aus: [‚Kiel‘, ‚Hamburg‘, ‚Bremen‘, ‚Hannover‘, ‚Düsseldorf‘, ‚Wiesbaden‘, ‚Mainz‘, ‚Saarbrücken‘, ‚Stuttgart‘, ‚München‘, ‚Erfurt‘, ‚Dresden‘, ‚Berlin‘, ‚Potsdam‘, ‚Magdeburg‘, ‚Schwerin‘]. Die Route ist 2263 Kilometer lang.

Abbildung 1: Eine optimierte Route mit 2263 Kilometer Länge.