link zum Programm

Ein Handlungsreisender (= "salesman") muß eine Rundreise durch eine gewisse Anzahl vorgegebene Städte machen. Um Zeit und Geld zu sparen, sucht er dazu nach demjenigen Weg, der unter allen denkbaren Routen die kürzeste Gesamtlänge aufweist.

kurze Anleitung:

linker Bereich:

Im linken, weißen Bereich können Reiseziele (durch Klicken) erstellt werden.
Der Algorithmus soll eine möglichst kurze Route finden, die alle Reiseziele erreicht und beim selben Ziel endet, an dem sie beginnt.

Die Reiseziele können (mit der Maus) verschoben werden, und (durch Rechtsklick & Menüauswahl) wieder gelöscht werden.
Zwischen je zwei Reisezielen können ihre Distanz und Verbindungslinien angezeigt werden (durch Rechtsklick auf die freie Fläche & Menüauswahl).

Während der Algorithmus aktiv ist wird in jedem Schritt das beste Zwischenergebnis durch eine rote Linie visualisiert.

rechter Bereich:

Rechts oben: Statistik über die aktuelle Konfiguration.

Rechts, in der Mitte, können die Einstellungen für den genetischen Algorithmus vorgenommen werden.
Größe der Population (Anzahl der Chromosomen), Anzahl der Durchgänge, Mutationsrate,...
Elitegröße bezeichnet die Anzahl der besten Chromosomen der Vorgänger-Generation, die automatisch in die nachfolgende Generation aufgenommen werden.
Elitekinder bezeichnet die Anzahl der Chromosomen, die durch CrossOver aus Elite-Mitgliedern erzeugt werden.
Kinder pro Paar legt die Anzahl der Chromosomen fest, die durch Crossover aus einem selektierten Elternpaar hervorgehen soll.
lokale Mutationsrate: legt die Wahrscheinlichkeit einer alternativen Art der Mutation fest, die jeweils die Reihenfolge zwei aufeinanderfolgender Ziele vertauscht.
Turnier: hier kann man die Art des Turnieres bestimmen, die verwendet wird, falls eine Turnier-Selektion gewählt wird: Nehme die (erste Zahl) besten von (zweite Zahl) zufällig ausgewählten Chromosomen zur Fortpflanzung.

lineare Selektion: nimm die bessere Hälfte der ursprünglichen Population für die Fortpflanzung.
Roulette Selektion: die Wahrscheinlichkeit für ein Individuum zur Fortpflanzung ist proportional zu seiner Fitness.
Turnier Selektion: Teile die Bevölkerung zufällig in Grüppchen und ziehe die fitteren Gruppenmitglieder zur Fortpflanzung heran.

CrossOver-Distanz-Heuristik: verbinde eher näher gelegene Ziele beim Crossover.
Mutation-Distanz-Heuristik: verbinde eher näher gelegene Ziele bei der Mutation.

Rechts unten:

Hier kann man Ziele benennen und die Distanz zwischen je zwei Zielen manuell festlegen.