PhiLIOsoph

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.