Ein Handlungsreisender mit evolutionären Strategien

Im Laufe des Studiums bin ich über so manch eine Aufgabe gestolpert.
Dieses Mal geht es um das Problem des Handlungsreisenden (http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden).

Kurz gesagt:
Ein Reisender will eine Anzahl von Städten besuchen, und das auf dem dafür kürzesten Weg.



Wir habe über die Distanzen der Städte zueinander.
Wo es los geht, ist im Prinzip egal. Da wir alle gegebenen Städte besuchen wollen, können wir, nachdem wir die Algorithmen für uns gearbeitet haben lassen, die Reihenfolge im Kreis drehen, bis wir unseren geliebten Startpunkt wieder haben.

Als Algorithmus nehmen wir uns die evolutionären Strategien.
Auf dieser Seite im Abschnitt "The Travelling Salesman Problem" (TSP) ist eine gute Erklärung:
http://www.bionik.tu-berlin.de/user/giani/esdemos/evo.html


Für uns zählt (1+1)-ES → (1 Elternteil + 1 Kind) - evolutionäre Strategie.
Das heißt, dass aus einem Elternteil durch Mutation ein Kind entsteht und nur diese beiden verglichen werden.


Grob kann man sagen:

1. Bildung eines Elternteils
2. Bildung eines Kindes durch Mutation
3. Auswahl des Kindes, wenn
1. das Kind besser ist als sein Elternteil, oder
2. beide gleich gut sind und der Zufall das so will, oder
3. wenn das Elternteil besser ist, aber eine bestimmte kleiner werdende Variable kleiner ist, als ein Zufallswert
4. Verringerung des variablen Wertes
5. Erhöhung des Iterationszählers
6. Wenn der Iterationszähler das Maximum an Iterationen überschritten hat, ist Schluss, ansonst zurück zu Schritt 2

Schritt 1 ist einfach:
Man lege willkürlich eine Reihenfolge, eine Route, durch alle Städte fest.

Für Schritt 2 brauchen wir Mutationen. 4 sind auf der Webseite  oben zum TSP beschrieben. Das sind:

• Inversion (Invertierung eine Reihenfolge von Städten)
• Insertion (Entfernung einer Stadt und Platzierung an einer anderen Stelle)
• Displacement (Verschiebung einer Reihe von Städten)
• Reciprocal Exchange (Vertauschung zweier Städte)

Zuerst erstellen wir eine Kopie des Elternteils. Per uniformen Zufall wählen wir uns dann eines dieser Mutationen aus und wenden das auf das Kind an.

Innerhalb der Mutationsalgorithmen kommen Zufallszahlen zur Anwendung.

Für den Anfang nehmen wir dafür uniforme Zufallszahlen.

Im dritten Schritt schauen wir, ob wir das Kind akzeptieren und als neues Elternteil wählen.

Als erstes vergleichen wir die sogenannte Fitness der beiden Individuen. Als Fitness verstehen wir in diesem Problem die Gesamtlänge der Rundreise. Ist also die Gesamtlänge der Rundreise des Kindes kleiner als die des Elternteiles, so wird das Kind gewählt.

Sind beide Gesamtlängen gleich, so wählen wir per Zufall das Kind. Das geschieht ca. so:

if Gesamtlänge(Elternteil) equals Gesamtlänge(Kind) then

    if ZufallswertZwischen(true,false) gleich true then 

        wähle Kind

Als dritte Möglichkeit gibt es noch, dass das Elternteil besser ist. In diesem Fall schauen wir uns einen variablen Wert an und vergleichen den mit einem Zufallswert. Ist ersterer kleiner, so wählen wir wieder das Kind.
Dies erlaubt es uns aus möglichen lokalen Minima zu entkommen.
Die Suche nach der kürzesten Route gleicht grafisch gesehen einer welligen Kurve. In unserer Suche schmeißen wir einen Ball auf die Kurve. Der Ball fällt und roll und kann dabei in Einkärbungen (lokale Minima) stecken bleiben. Um dies zu vermeiden, "rütteln" wir. Wir erlauben "schlechtere" Kinder um aus dem Minima zu entkommen. Das Rütteln wird dabei von mal zu mal schwächer. Mit etwas Glück gelangen wir so in den Trichter des globalen Minimum, in den wir hinein wollen.
Als Funktion habe ich mir hier die "Gaussian Density" gewählt:

if gaussianDesnity (delta( Parent, Child), stdDev) > ZufallszahlZwischen(0,1) then …

 Die Funktion ist hier auf Seite 2 zu finden:
http://web.mst.edu/~tauritzd/courses/ec/fs2002/project/Koenig.pdf



Im Punkt 4 wird der variable Wert verringert. In diesem Fall ist es die "standard deviation" (stdDev). Sie wird innerhalb der gaussianDesnity und im weiteren im inneren der Mutationen verwendet. Je nach Anzahl der Iterationen und des Startwertes der "standard deviation" lässt sich eine Senkung mittels Multiplikation mit etwas weniger als 1 relativ gut verarbeiten.
(Zum Beispiel: Iteration von 100000, Multiplikator von 0.99)

Schritt 5 und 6 benötigen, glaube ich, keine weiteren Kommentare.

Soweit zur Theorie.
Auf zum Code.


Als Basis nehmen wir uns folgendes:
http://www.codeproject.com/Articles/26758/Simulated-Annealing-Solving-the-Travelling-Salesma

Hier finden wir das passende Problem mit Lösung in Form von "Simulated Annealing".
Die Herangehensweise ist ähnlich:
Ein Elternteil erzeugt eine Kopie und mutiert diese mittels "Reciprocal Exchange" (hier als "GetNextArrangement"). Für Punkt 3.3 kommt folgende Funktion anstelle von "gaussianDesnity" zum Einsatz:

Math.Exp(-deltaDistance / temperature)

Die Iterationen werden außen vor gelassen. Stattdessen wird die aktuelle Temperatur mit einem Minimum verglichen und ggf. abgebrochen.

Im Groben entspricht also der Code schon der evolutionären Strategie.
Bauen wir also ein paar Verbesserungen ein:

1.  Die Übernahme des Kindes: die Funktion für Punkt 3.3 wird ersetzt und ein zusätzliche Abfrage für 3.2 (gleiche Fitness) eingefügt.
2. Einbau der Abbruchbedingung über die maximale Anzahl an Iterationen.

Das dürfte ohne weitere Erklärung von alleine Funktionieren ;-)

Schwieriger ist das Hinzufügen der Mutationen, insbesondere derer, die von der Standardabweichung und der Normalverteilung abhängen.

Die integrierte Mutation verwendet Zufallswerte aus dem uniformen Raum. D.h., dass alle Werte gleichwahrscheinlich sind.

Für uns ist die Normalverteilung (auch gaussche Normalverteilung) besser geeignet. Diese Verteilung hat eine Glockenform. Werte um den "Mean" werden bevorzugt auftreten.

In C# muss dies selber programmiert werden (oder man kopiert sich etwas ;-)):

http://stackoverflow.com/questions/218060/random-gaussian-variables

Bei mir sieht das dann wie folgt aus:

double randomOfGaussianDistribution (double stdDev = 1){
    double mean = 0;
    double u1 = random.NextDouble (); //these are uniform(0,1)
    double u2 = random.NextDouble ();
    double randStdNormal = Math.Sqrt (-2.0 * Math.Log (u1)) * Math.Sin (2.0 * Math.PI * u2);
    double randNormal = mean + stdDev * randStdNormal; //random normal(mean,stdDev^2)
    return randNormal;
}
double randomOGD (double stdDev){
    return (randomOfGaussianDistribution (stdDev) + 1)/2;
}
int randomOGDMean (int mean, int start, int end, double stdDev){
    var rand = randomOfGaussianDistribution (stdDev);
    var newMean = mean + rand;
    var length = end - start;
    if (newMean < start) newMean = length - (-newMean) % length;
    if (newMean > end) newMean = (newMean % length);
    return (int)Math.Floor (newMean);
}
int randomOGDCount (int min, int max){
    var rand = Math.Min (1, Math.Max (-1, randomOfGaussianDistribution (1)));
    return min + (int)Math.Floor (rand * Math.Sign (rand)) * (max - min);
}

Die unteren Methoden sind speziell für die Mutationen. Zum einen wird ein Zufallswert um den "Mean" gesucht und bei dem anderen wird ein Zufallswert für eine bestimmte Anzahl gesucht.
Als Beispiel sei hier die "Inversion" angebracht:

void operatorInversionGauss (){
    var start = random.Next (0 + 1, nextOrder.Count - 2);
    var count = randomOGDCount (2, nextOrder.Count - start);
    nextOrder.Reverse (start, count);
}

Bei der "Inversion" wird eine Reihe von Elementen invertiert.
Der erste Wert wird aus der uniformen Verteilung gewählt und ist der Startwert. Die Anzahl ist dann vom ersten Wert abhängig und zählt nach "rechts".

 randomOGDMean ist gut am Beispiel von "Reciprocal Exchange" erklärbar:

void operatorReciprocalExchangeGauss (double stdDev){
    var first = random.Next (0 + 1, nextOrder.Count);
    var second = randomOGDMean (first, 0, nextOrder.Count, stdDev);
    var tmp = nextOrder [first];
    nextOrder [first] = nextOrder [second];
    nextOrder [second] = tmp;
}

Der erste Wert wird ganz uniform zufällig gewählt. Der zweite Wert hängt vom ersten ab. Zusätzlich spielt die Standardabweichung mit ein. Je kleiner diese ist, desto näher liegen die beiden zu vertauschenden Elemente.
Innerhalb der "randomOGDMean" wird der Überlauf der Grenzen beachtet.


Nur zur Erwähnung noch die letzten beiden Mutationen mit Gauss:

void operatorDisplacementGauss (double stdDev){
    var start = random.Next (0 + 1, nextOrder.Count - 1);
    var count = randomOGDCount (1, nextOrder.Count - start - 1);
    var place = randomOGDMean (start, 0, nextOrder.Count - count, stdDev);
    var sublist = new List<int> ();
    for (int i = 0; i < count; ++i) sublist.Add (nextOrder [start + i]);
    nextOrder.RemoveRange (start, count);
    nextOrder.InsertRange (place, sublist);
}

void operatorInsertionGauss (double stdDev){
    var start = random.Next (0 + 1, nextOrder.Count);
    var place = randomOGDMean (start, 0, nextOrder.Count, stdDev);
    var item = nextOrder [start];
    nextOrder.Remove (item);
    nextOrder.Insert (place,item);
}

Als sollte noch folgendes beachtet werden:
Dank der Verringerung von "stdDev" kann ab einem bestimmt kleinen Wert der entsprechende Mutationsoperator nicht mehr angewandt werden. Ist die "stdDev" kleiner als 1, so wird immer nur der "Mean" zurück gegeben. Das bringt nichts.
Aus diesem Grunde empfiehlt es sich die Mutationen ab dort wieder mit uniformen Zufallszahlen zu bestücken.



Hier noch ein Zitat von Dr. Jesús Emeterio Navarro Barrientos:

"the idea is to do the same as in the example code using simulated annealing to solve the TSP, but now with evolutionary strategies, i.e. use Gaussian random values instead of Uniform random values, and instead of cooling out the solution using a D=C(S')-C(S') e^D/T, reducing the temperature T every iteration, now for ES you decrease the standard deviation of the Gaussian random numbers every iteration. That would be roughly the main task, of course modifying the way to get new solutions S' would be also a plus." 

Kurz zerpflückt:

• use Gaussian random values instead of Uniform random values
• decrease the standard deviation  instead of cooling out

Heißt also, wie oben erwähnt:

• anstelle der uniformen Zufallszahlen sollen Gauss-Zufallszahlen genommen werden
• anstelle von Abkühlung (


• temperature *= coolingRate;
• Math.Exp(-deltaDistance / temperature) > random.NextDouble()
• soll die Anpassung der Standardabweichung und damit der Gauss-Zufallszahlen geschehen (Diese Anpassung ist wie bei der Abkühlung nur z.B. ein "stdDev *= 0.99;" pro Iteration.)

Zusätzlich wäre es fein, wenn neue Mutationsoperatoren eingebaut werden (zum Beispiel solche, wie oben ;-)).

Das sollte es eigentlich gewesen sein.
Fragen etc. einfach in die Kommentare.

PS:
Kompletter Code ist hier:
http://code.google.com/p/manuel-bellersen/downloads/detail?name=TSP_1.zip