mas-challange

Vorraussetzung

Python 3.8

Visualisierung

Matplotlib 3.2.1

Basemap 1.2.1

Ausführung

Code z.B. als zip-Datei runterladen und entpacken.

Anschließend main.py ausführen.

Wenn Sie die Visualisierung aktivieren möchten. Muss matplotlib und basemap installiert sein. Anschließend kommentieren sie in simulatedannealing.py folgende Zeilen aus

4.  # import visualisierung

25. # visualisierung.createBasemap()

49. # visualisierung.path(currentArray, calc.berechneGesamtLaenge(currentArray), False)

53. # visualisierung.path(currentArray, calc.berechneGesamtLaenge(currentArray), False)

57. # visualisierung.path(currentArray, calc.berechneGesamtLaenge(currentArray), True)

62. # visualisierung.bestpath(currentArray, calc.berechneGesamtLaenge(currentArray))

Wenn Sie hingegen nur am Ende die Strecke Visualisieren möchten, müssen sie folgende Zeilen auskommentieren

4.  # import visualisierung

61. # visualisierung.createBasemap()

62. # visualisierung.bestpath(currentArray, calc.berechneGesamtLaenge(currentArray))

simulatedanneling.annealing(cityList, 100000, 0.00003)

Bei dieser Ausführung habe ich als beste Route 97627.179 km erhalten. Dabei wurde folgende Route gewählt:

Ismaning/München (Hauptsitz) -> Passau -> Stuttgart -> St. Georgen -> Ingolstadt -> Bretten -> Hamburg -> Köln/Hürth -> Essen -> Braunschweig -> Hannover -> Lingen (Ems) -> Münster -> Düsseldorf -> Chemnitz -> Nürnberg -> Schortens/Wilhelmshaven -> Berlin -> Görlitz -> Frankfurt -> Walldorf -> Ismaning/München (Hauptsitz) (Wieder zurück)

Ich habe den Code auf Windows 10 mit python 3.8 geteste.

Warum Simulated Annealing?

Dieses Verfahren erzeugt ein gutes Ergebnis in kurzer Zeit. Im Vergleich zum HillClimbing, welches bei einem Lokalen Maxima sein Ende erreicht hat. Simulated Annealing kann aus diesem Lokalen Maxima entkommen. Somit wird ein besseres Ergebnis erziehlt.

Funktionsweise

Bei Simulated Annealing wir eine Temperatur und eine Cooldown Rate übergeben. Je höher die Temperatur und je kleiner die Cooldown Rate, desto besser ist das Ergebnis, aber desto länger dauert die Berechnung. In diesem Beispiel ist als Temperatur 10000 und als Cooldown Rate 0.003 eine gute Option. Nachdem die Parameter übergeben wurden wird zuerst ein Start Route erzeugt. Anschließend werden zwei Zufällige Städte genommen und vertauscht. Dann wird geguckt, ob die Gesamtstrecke , welche auch als Energie angegeben wird. Wenn die kleiner geworden ist wird sie akzeptiert und es wird weiter gemacht. Falls die Stecke größer geworden ist wird

e^((gesamtStrecke - NeueStecke) / Temperatur)

berechnet. Anschließend wird entschieden, ob die Stecke doch akzeptiert werden soll. Am Anfang wird viel mehr akzeptiert. Dies sorgt dafür das man nicht im Lokalen Maxima stecken bleibt.

C = Start Route
E(C)
Next = Neue Stecke
E(N)
if(E(N) < E(C))
   akzeptiere
elif(e^(...) < Zufällige Zahl)
   akzepiere
Temperatur = Temperatur * Cooldown