Besondere Lernleistung: Evolutionäre Algorithmen und das Traveling-Salesman-Problem
Das offizielle Thema meiner besonderen Lernleistung lautet “Spieltheorie” mit Schwerpunkt auf “evolutionären Algorithmen”. Ich bringe die Lernleistung zusammen mit einem Freund als Ersatz für das 5. Prüfungsfach ins Abitur, das ich dieses Jahr mache, ein. Der Freund hat natürlich einen anderen thematischen Schwerpunkt, das Hauptthema (Spieltheorie) ist jedoch dasselbe. 
Für das sogenannte Traveling-Salesman-Problem soll ich außerdem im Rahmen dieser Lernleistung einen evolutionären Algorithmus schaffen.
Das Traveling-Salesman-Problem
Das Traveling-Salesman-Problem (TSP) ist einfach formuliert: Ein Handlungsreisender muss n Städte besuchen und am Ende zu seinem Ausgangsort zurückkehren. Gesucht ist die kürzeste Rundreise.
Viele schlaue und dumme Menschen haben sich auf der Suche nach einem effizienten Algorithmus jahrzehntelang den Kopf darüber zerbrochen. Einen Ansatz stellen die sogenannten evolutionären Algorithmen dar, die die Evolution als Vorbild haben.
Was ist ein evolutionärer Algorithmus?
Zitat Wikipedia:
“Ein Evolutionärer Algorithmus (EA) ist ein Optimierungsverfahren, das als Vorbild die biologische Evolution hat.”
Prinzipiell prozessiert ein evolutionärer Algorithmus eine Population mit n Individuen nach dem Vorbild der Evolution: “survival of the fittest”. Jedes Individuum stellt eine mögliche Lösung des jeweiligen Problems dar. Im Falle des TSP entspricht also jedes Individuum einer möglichen Rundreise.
Im Laufe des Algorithmus pflanzen sich außerdem je zwei Individuen fort und erzeugen ein Kind-Individuum nach Vorbild der Natur mittels Rekombination. Zusätzlich finden – ebenfalls nach Vorbild der Natur – mit einer bestimmten Wahrscheinlichkeit Mutationen statt, also z.B. (normalerweise) zufällige Veränderungen der Route.
Jeder Durchlauf eines evolutionären Algorithmus’ sieht also mehr oder weniger so aus:
- Entferne x Individuen aus der Population. (Zum Beispiel die beiden schlechtesten Routen.)
- Rekombiniere x-Mal zwei Individuen aus der Population. (Zum Beispiel die beiden besten Routen.)
- Wende mit einer bestimmten Wahrscheinlichkeit eine Mutation auf die Individuen an. (Zum Beispiel mit einer Wahrscheinlichkeit von 15%.)
- Wenn die maximale Anzahl von Durchläufen (Generationen) erreicht ist, beende den Vorgang, ansonsten starte einen neuen Durchlauf.
Die Güte bzw. Qualität eines evolutionären Algorithmus hängt vor allem von folgenden Faktoren ab:
- Populationsgröße
- Rekombinationsmethode
- Mutationsmethode
- Mutationswahrscheinlichkeit
- …
Ein evolutionärer Algorithmus für das Travelling-Salesman-Problem
Wie oben gesagt ist es meine Aufgabe für das TSP einen evolutionären Algorithmus zu programmieren. Als Programmiersprache habe ich mich für Python und als Entwicklungsumgebung für eclipse mit PyDev entschieden. (Damit lässt sich super arbeiten!)
Mit der Arbeit am evolutionären Algorithmus habe ich heute begonnen, und ich muss sagen: Ich bin bereits jetzt sehr zufrieden. Da die Güte des evolutionären Algorithmus – siehe oben – von vielen Faktoren abhängt, habe ich mich für eine Umsetzung entschieden, bei der ich all diese Faktoren leicht ändern kann.
Das ist mir ganz gut gelungen: Alle Parameter und Komponenten des evolutionären Algorithmus sind ganz einfach austauschbar. (Leider werde ich bis zum Erhalt meines Abiturs keine Quelltexte veröffentlichen. Der menschlichen Dummheit sind einfach keine Grenzen gesetzt und ich könnte mir vorstellen, dass man mir vorwirft, meine Arbeit aus dem Internet von einem “Robert Nitsch” kopiert zu haben.)
Nun folgt der schwierigste, aber wohl auch spannendste Teil meiner besonderen Lernleistung. Ich werde prüfen welche Parameter den besten evolutionären Algorithmus ausmachen und verschiedene Konfigurationen miteinander vergleichen. Natürlich wird auch eine Begründung nicht fehlen – also warum Konfiguration A besser ist als Konfiguration B.
Meine Arbeit und meine Ergebnisse muss ich abschließend in einem Skript dokumentieren und in einer Präsentation vorstellen. Meine Ergebnisse werde ich natürlich auch hier auf meiner Homepage festhalten, damit Schüler, die eine ähnliche Lernleistung erbringen, davon vielleicht profitieren können.
Für Tipps und Ratschläge bezüglich meiner besonderen Lernleistung bin ich natürlich jederzeit offen.
Geile Sache… hast meinen Respekt
Hätte da nur eine Frage: Wenn zwei Individuen untereinander gekreuzt werden, sich die Reisen aber unterscheiden (eine Route == mehrere Reisen), welche Reise wird dann gewählt und welche gelöscht?
Mfg
dispy
Kommentar by dispy — 09.01.2008 @ 19:29:35
Danke danke.
Bei deiner Frage habe ich folgendes Problem: “eine Route == mehrere Reisen” ist nicht korrekt. Eine Route entspricht einer Rundreise. Also “eine Route == eine Rundreise == eine Reise”.
Zur Rekombination:
Zwei Individuen (Rundreisen) erzeugen bei der Rekombination immer genau ein Kind-Individuum. In meinem bisherigen Algorithmus ist es meistens so, dass bei jedem Durchlauf zwei Rekombinationen stattfinden, es werden also zwei Kind-Individuen erzeugt.
Die Antwort auf deine Frage – falls ich die richtig verstanden habe – ist schließlich folgende:
Vor der Rekombination wird (momentan) immer die schlechteste Rundreise gelöscht. (Wenn die Rekombination zwei Mal abläuft, werden also auch die beiden schlechtesten Rundreisen gelöscht.)
Solltest du deine Frage allerdings äußerst ungeschickt formuliert und eigentlich gemeint haben: “Wie werden zwei Individuen gekreuzt?”, dann lautet die Antwort folgendermaßen:
http://www.acc.umu.se/~top/travel_information.html#TS ==> “Crossover”
Die Grafiken haben zwar einen kleinen Fehler, aber sie veranschaulichen das Prinzip der Rekombination sehr gut.
MfG, Robert Nitsch
Kommentar by Robert Nitsch — 09.01.2008 @ 22:16:03
Hallo Robert,
da hast du dir aber ein schönes Thema ausgesucht
Ich habe allerdings noch 2 Fragen dazu.
Du hast geschrieben:
—
Wenn die maximale Anzahl von Durchläufen (Generationen) erreicht ist, beende den Vorgang, ansonsten starte einen neuen Durchlauf.
—
Frage 1:
Warum legst du eine Maximalanzahl von Generationen fest, du möchtest doch die küzeste Route herausfinden?
Frage Nummer 2:
Wenn ich deine Antwort richtig verstanden habe, führst du pro 2 Individuen pro Generation 2 Rekombinationen durch.
Du löschst also die schlechtesten 2 Individuen und erzeugst dann ‘ne Menge neuer Kind-Individuen.
Das könnte man ja dann mit NewN=(n-2)+((n-2)/2*2) beschreiben, im Endeffekt also: NewN=(n-2)*2.
Was ich dabei nicht verstehe: das läuft auf unendlich, da ja bei jeder Generation mehr Kind-Individuen erzeugt werden als “schlechte” Individuen gelöscht werden.
Kommentar by Jens Scheider — 30.01.2008 @ 22:39:57
Hallo Jens!
Die kürzeste Route herauszufinden, würde mit einem EA schon bei leicht höheren Städtezahlen sehr lange dauern. (z.B. >40, da wirds schon aufwändig) Nicht zuletzt besteht auch das Risiko, dass sich ein EA “festfährt”, sozusagen bei einer bestimmten Lösung keine Verbesserung mehr findet – soetwas nennt man lokales Optimum.
Das wichtigste Argument ist aber, dass ich verschiedene Rekombinations- und Mutationsmechanismen miteinander vergleichen können möchte. Das ist nur dann möglich, wenn alle Rekombinations- und Mutationsmethoden gleich oft angewendet werden. Sonst wäre es ja “unfair”.
Naja, x-Mal passiert das. Also x-Mal werden die beiden schlechtesten gelöscht und zwei neue gezeugt:
Bei mir trifft x=1 meistens zu. Mittlerweile habe ich aber verschiedene andere Methoden entwickelt, die darüber entscheiden, wer sich fortpflanzen darf und wer nicht. Besonders erfolgreich ist diejenige, die die Individuen in Abhängigkeit von ihrer Fitness mit einer gewissen Chance fortpflanzen lässt.
Ich hoffe, ich konnte deine Fragen beantworten.
MfG, Robert Nitsch
Kommentar by Robert Nitsch — 31.01.2008 @ 08:41:10
[...] Robert Nitsch präsentierte uns ein paar Wochen später einen Teil seiner besonderen Lernleistung, die das TSP [...]
Pingback by TSP: Das Travelling Salesman Problem | Steffens Noteblog — 25.05.2008 @ 13:01:42
Die unter http://www.acc.umu.se/~top/travel_information.html#TS vorgestellten Crossover Methoden sind nicht gerade die Performantesten für den TSP.
Die ERX Methode versucht Rundreisen aus möglichst vielen Kanten der beiden Eltern zubilden. Der ERX erzeugt sogar bei gleichen Eltern Lösungen aber unterschiedlichen Rundreisen (Invertiert oder anderer Startpunkt) eine Lösung die gleichwertig mit denen der Eltern ist.
Leider muss der ERX bei <5% der Kanten zur Erzeugung einer gültigen Rundreise zu einen zufälligen oder nächsten freien Nachbar springen.
Kommentar by marian — 21.11.2008 @ 15:59:49
Das kann sein. Diese Methode habe ich gar nicht gefunden… jetzt beim Googlen mit “ERX” finde ich natürlich schon was. Sehr interessant…
Zum Glück wusste das mein Lehrer nicht, sonst wären’s vllt. nur 14 statt 15 Punkte gewesen.
Kommentar by Robert — 21.11.2008 @ 17:41:35
Ich habe hier noch eine weiter Methode die ich selber entwickelt habe. Ich nenne sie RNX (Random Neighbour)
Kopiere die Tour Parent1 ins Child. Vor und neben jeder Stadt fügst du die Nachbarn wie sie in Parent2 gegeben sind.
Der Vector enthällt nun jeden Ort dreimal.
Nun lösche zufällig Städte aus der Liste bis jede Stadt nur einmal vorhanden ist.
BSP:
P1 = 1,5,8,9,2,3,4,6,7,0
P2 = 0,1,9,2,6,4,5,7,3,8
tmpList = 0,1,9, 4,5,7, 3,8,0, 1,9,2, 9,2,6, 7,3,8, 6,4,5, 2,6,4, 5,7,3, 8,0,1
Mögliche Lösungen:
C1 : 0,1,9,4,5,8,7,3,0,2
C2 : 4,5,3,1,2,9,6,7,8,0
….
Du wirst feststellen das die Lösung viele Kanten aus einer der beiden Eltern enthällt oder aber Kanten zu Nachbarn von Nachbarn.
Gruss
Kommentar by marian — 25.11.2008 @ 17:44:53