Travelling Salesman Problem (TSP)
Bearbeiter
- Michael Gebhardt
- Lukas Kalinowski
Beschreibung
Im Rahmen der Übung aus der Vorlesung Machine Learning wurde das Optimierungsproblem TSP mit genetischen Algorithmen gelöst. Dabei existiert eine Anzahl an Städten, die bereist werden sollen. Es wird bei einer Stadt begonnen und eine Tour durch alle Städte durchgeführt, bis der Ausgangspunkt wieder erreicht wird. Dabei soll die Gesamtlänge der Tour minimal sein. Die Entwicklung erfolgte in der Programmiersprache java.
Vorgehen
- Eine geeignete Repräsentation des Problems wählen:
Eine Klasse “City” (Gen), bestehend aus einer x- und y-Position und Berechnung der Distanz zwischen zwei Städten.
Eine “Tour” Klasse (Individuum), zum Wählen welche Städte wann durchlaufen werden. - Eine Population mit k Individuen erstellen, deren Parametersätze zufällig generiert werden:
Eine “Tour” Klasse, die eine Liste an Städten (Gene) erhält und zunächst zufällig über alle zu durchlaufenden Städte generiert wird. Es werden k Touren entwickelt (Population) - Anhand der individuellen Fitness werden je zwei Individuen zur Reproduktion ausgewählt:
Die Fitness einer Tour berechnet sich aus der Gesamtdistanz beim Durchlaufen aller Städte. Es wurden drei Verfahren zur Selektion einer Tour (Population) entwickelt: Roulettewheel-, Rank- und Tournament-Selektion. - Für jedes Elternpaar werden die folgenden Schritte durchgeführt:
- Es wird ein Nachkommen durch Rekombination der Gene generiert.
- Es werden zufällige Mutationen beim Nachkommen durchgeführt.
Für die Rekombination wurden drei Verfahren implementiert: Single-Point, Two-Point und Uniform
Wobei bei der Entwicklung der Verfahren stets gewährleistet werden musste, dass bei einem Nachkommen keine Stadt zweimal durch die Tour besucht wird. - Entspricht das fitteste Individuum als Hypothese der Problemstellung nicht hinreichend genau, gehe zu Schritt 3:
Als Problemstellung wird die Gesamtlänge der Tour sowie die Anzahl an Kreuzungen beim Rundlauf der Städte aufgefasst. Es kann mehrere optimale Lösungen geben, daher kann in der Anwendung die Anzahl an Generationen (Iterationen von Schritt 5 zu 3), die durchlaufen werden sollen über einen Parameter festgelegt werden.