Informatik: Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus
Released by matroid on Fr. 15. März 2019 12:05:24 [Statistics]
Written by Delastelle - 467 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\)
Im Artikel werden mehrere Näherungslösungen zu einem symmetrischen Rundreiseproblem (TSP)
durch 96 französische Städte ("Tour de France" oder TSP96) mittels eines Ameisenalgorithmus berechnet.
In meinem Notizbuch habe ich die entsprechenden Grafiken und Programme seit 2011 liegen.


Das symmetrische Rundreiseproblem(Travelling Salesman Problem) und der Ameisenalgorithmus


Bild
schwarz und orange: 2 Rundreisen.

Definition eines symmetrischen Rundreiseproblems:
Gegeben sind n Städte (bei mir n = 96).
Eine Rundreise ist ein geschlossener Weg durch alle Städte, bei dem jede Stadt genau 1x besucht wird.
Bei einem symmetrischen Rundreiseproblem gilt: d(a,b) = d(b,a) mit d als Abstand zwischen Stadt a und b.
Gesucht ist von allen Rundreisen die kürzeste.

Eigenschaften eines Rundreiseproblems:
- es gibt ca. n! Rundreisen (bei n = 96 sind das ca. 9.9*10^149)
- es ist NP-vollständig, also algorithmisch schwer lösbar (siehe Literatur)
- als Bezeichnung wird verwendet: Rundreiseproblem, Travelling-Salesman-Problem oder auch
Travelling-Salesperson-Problem (mein Rundreiseproblem kann man "TSP96" nennen)


eine globale Pheromonmatrix - ziemlich am Ende der Optimierung

Kurzbeschreibung eines Ameisenalgorithmus:
Ein Lauf des Ameisenalgorithmus besteht aus:
Es laufen nacheinander n Ameisen mit den n Städten als Startpunkt der Route Rundreisen.
Dabei wird die nächste Stadt in einer Route nach bestimmten Formeln bestimmt.
Die beste der n Rundreisen wird gemerkt.
Es werden eine globale Pheromonmatrix (ameise2 oder Tau) und eine temporäre Pheromonmatrix (ameise3 oder Delta-Tau) benutzt.
Während eines Laufes werden die Ameisen "versuche"-mal auf eine Rundreise geschickt.

Ein paar Formeln:
- in der Pheromonmatrix werden neue/gute Wege mit hohen Werten belegt und erhalten so eine höhere Chance(Wahrscheinlichkeit) ausgewählt zu werden
fed-Code einblenden
fed-Code einblenden
fed-Code einblenden
bzw.
ug(j+1) = ug(j) + ameise2 ^ alpha*( 1.0d0/dist(i,j) ) ^ beta
mit ug werden im Programm Intervallgrenzen bezeichnet. Aus den Intervallen wird dann
zufällig eines ausgewählt.

- in der temporären Pheromonmatrix (Matrix ameise3 oder fed-Code einblenden ) werden die Wege, die zum Rundenminimum gehören belohnt(mit fed-Code einblenden )
fed-Code einblenden
fed-Code einblenden

- die Pheromonmatrix "vergisst" mit der Zeit alte Wege (Bild oben Matrixeinträge in der
globalen Pheromonmatrix aus schwarz wird kontinuierlich grau wird weiß)
fed-Code einblenden
fed-Code einblenden

- Verhinderung eines zu großen Anwachsens der globalen Phermomonmatrix durch
leichtes Rücksetzen der temporären Pheromonmatrix Richtung 1
fed-Code einblenden
fed-Code einblenden

- mit der Wahrscheinlichkeit fed-Code einblenden wird das größte Intervall (in der ersten Formel) ausgewählt, sonst zufällig eines der Intervalle

Diese und noch mehr Formeln sind in dem Programm "TSP_81_96_Ameise.for" enthalten.
Das Programm kann in meinem Notizbuch gefunden werden.
Am Ende des Artikels habe ich ein paar Zahlenwerte für Parameter angegeben.

Links:
de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
de.wikipedia.org/wiki/Ameisenalgorithmus
activevb.de/tutorials/tut_antalgo/tut_antalgo.html

ein Rundreiseproblem mit 96 französischen Städten ("Tour de France" oder TSP96)


Ich habe 2011 ein Rundreiseproblem durch die 96 europäischen (Festlands)-Départements Frankreichs aufgestellt ("Tour de France" oder TSP96).
Dabei habe ich als Knoten die Hauptstädte der 96 Départements genommen.
Ich erhielt eine Tabelle mit 96 Einträgen:
fed-Code einblenden


Da ich die Distanzen zwischen jeweils 2 Städten benötigte habe ich sie wie folgt berechnet
(die Formel habe ich in einem anderen Programm gefunden):
Fortran
          ort1(1) = lage(i,1)
          ort1(2) = lage(i,2)
          ort2(1) = lage(j,1)
          ort2(2) = lage(j,2)
          phi1 = ort1(1)*pi/180
          tht1 = ort1(2)*pi/180+pi/4
          phi2 = ort2(1)*pi/180
          tht2 = ort2(2)*pi/180+pi/4
          angularDistCos=sin(phi1)*sin(phi2)+cos(phi1)*cos(phi2)*cos(tht1-tht2)
          angularDist=acos(angularDistCos)*180.0d0/pi
          Erdradius=6350.0d0
          distanz=(angularDist*pi/180.0d0)*Erdradius
          dist(i,j) = floor(distanz+0.5);
          dist(j,i) = dist(i,j)


Die Distanzmatrix hat eine Dimension von 96 x 96.
Ich habe die Distanzen symmetrisch angesetzt.
Bei einer Rundreise mit einem Auto oder Flugzeug muss keine Symmetrie gelten.
Falls Ort A auf einem Berg und Ort B im Tal liegt und ich mit einem Auto fahre, kann dist(A,B) <> dist(B,A) sein. Falls dist z.B. den Benzinverbrauch angibt.
Bei einem Flugzeug kann eine Route mit dem Wind, die Gegenrichtung gegen den Wind sein.

3 Startheuristiken für symmetrische Rundreiseprobleme angewendet auf ein Problem mit 96 französischen Städten


Startheuristiken werden üblicherweise angewendet, wenn in kurzer Zeit(bei TSP96 in weniger als 1 Sekunde) eine recht gute Lösung gefunden werden soll.
Ich habe mit 3 Startheuristiken gearbeitet.
Dies sind "Nearest Insertion" (den am nächsten gelegenen Punkt einfügen), "Random Insertion" (einen Zufälligen Punkt einfügen) und
"Farthest Insertion" (einen möglichst weit weg von der Route liegenden Punkt einfügen).

Heuristik 1: "Nearest Insertion" liefert bei TSP96 ein ff = 7295. Dies liegt 8.1 % über dem von mir berechneten besten Funktionswert.
Die Grafik ist für den Bereich um Paris noch einmal vergrößert dargestellt, da dort viele Städte auf engem Raum sind.
Aus 96 Routen wird die Beste ausgewählt. Es wird eine Startstadt gewählt.
Dann wird jeweils die von der bisherigen Route am wenigsten entfernte Stadt eingefügt und zwar an der Stelle in der Route, die die geringste Verlängerung der Route ergibt.
Dies solange bis alle 96 Städte in der Rundreise liegen.


Heuristik 2 "Random Insertion" liefert bei TSP96 ein ff = 6955 (bei jedem Lauf ein anderer Wert). Dies liegt 3.1 % über dem von mir berechneten besten Funktionswert.
Dazu wird aus 96 Routen die Beste ausgewählt. Es wird eine Startstadt gewählt.
Dann wird jeweils die von der bisherigen Route eine zufällige Stadt eingefügt und zwar an der Stelle in der Route, die die geringste Verlängerung der Route ergibt.
Dies solange bis alle 96 Städte in der Rundreise liegen.


Heuristik 3 "Farthest Insertion" liefert bei TSP96 ein ff = 6928. Dies liegt 2.7 % über dem von mir berechneten besten Funktionswert.
Dazu wird aus 96 Routen die Beste ausgewählt. Es wird eine Startstadt gewählt.
Dann wird jeweils die von der bisherigen Route am weitesten entfernte Stadt eingefügt und zwar an der Stelle in der Route, die die geringste Verlängerung der Route ergibt.
Dies solange bis alle 96 Städte in der Rundreise liegen.

Links:
de.wikipedia.org/wiki/Farthest-Insertion-Heuristik
de.wikipedia.org/wiki/Nearest-Insertion-Heuristik

meine beste mittels Ameisenalgorithmus gefundene Lösung mit ff = 6748



Meine beste mittels Ameisenalgorithmus gefundene Lösung mit ff=6748 für TSP96 ist in der Grafik dargestellt.
Dabei ist in der Grafik der Bereich um Paris noch einmal vergrößert dargestellt, da dort
viele Städte auf engem Raum sind. Die Lösung ff=6748 habe ich nur 1x gefunden, etwas schlechtere Lösungen ff=6750 und schlechter häufiger.
Die Lösung lautet:
x = [76 27 14 50 61 72 49 53 35 22 29 56 44 85 17 79 86 16 24 33 ...
40 64 65 32 47 46 82 81 31 9 11 66 34 30 84 13 83 20 96 6 ...
4 5 38 73 74 39 1 71 69 42 26 7 43 48 12 15 19 87 23 63 ...
3 58 18 36 37 41 45 28 78 92 95 93 75 94 91 77 89 10 52 21 ...
25 70 90 68 67 88 54 57 55 51 8 2 59 62 80 60];

gute Parameter (die Originalparameter des besten Laufs habe ich mir damals nicht gemerkt):
Programm: TSP_81_96_Ameise
ameise3 -> temporäre Pheromonmatrix
ameise2 -> globale Pheromonmatrix
c ug(j+1) = ug(j) + ameise2 ^ alpha*( 1.0d0/dist(i,j) ) ^ beta
c
c ameise3(xx(i),xx(i+1)) = ameise3(xx(i),xx(i+1)) + addi [=delta]
c
c ameise2(i,j) = max(gamma*ameise2(i,j)+ameise3(i,j),1)
c
c ameise2(xx(i),xx(i+1)) = (1-phi)*ameise2(xx(i),xx(i+1))+phi*1
alpha = 1 (aus Hauptgleichung)
beta = 5 (aus Hauptgleichung)
gamma = 0.99 (wieviel Prozent der Pheromonmatrix sollen nicht verdunsten am Ende einer Iteration? = Vergessensfaktor)
delta = 100 (Belohnung für Weg in bester Runde)
eps = 0.80 (größtes Intervall wird mit Wahrscheinlichkeit eps genommen)
phi = 0.2 (verhindert ein zu großes Anwachsen der Phermomonmatrix durch
leichtes Rücksetzen Richtung 1)
versuche = 2000 (Iterationen innerhalb des Ameisenalgorithmus)
bigsteps = 1000 (oder mehr -> äußere Schleife - Läufe des Verfahrens)




In den Grafiken sind 4 sehr gute Lösungen zu sehen. Rote Wege sind Abweichungen von Wegen von der besten Lösung.
Über den Grafiken sind auch die zahlenmäßigen Abweichungen (Anzahl der Wege) von der zweitbesten und drittbesten gefundenen Lösung aufgeführt.

(ENDE)
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Traveling Salesman :: Informatik :: Diskrete Optimierung :: NP-Vollständigkeit :
Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus [von Delas  
Im Artikel werden mehrere Näherungslösungen zu einem symmetrischen Rundreiseproblem (TSP) durch 96 französische Städte ("Tour de France" oder TSP96) mittels eines Ameisenalgorithmus berechnet. In meinem Notizbuch habe ich die entsprechenden Grafiken und Programme seit 2011 liegen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 467
 
Aufrufstatistik des Artikels
Insgesamt 75 externe Seitenaufrufe zwischen 2020.05 und 2021.07 [Anzeigen]
DomainAnzahlProz
https://google.com2533.3%33.3 %
https://google.de3648%48 %
https://www.bing.com79.3%9.3 %
https://webinar.pmplattform.com45.3%5.3 %
https://duckduckgo.com11.3%1.3 %
https://www.ecosia.org11.3%1.3 %
https://www.startpage.com11.3%1.3 %

Häufige Aufrufer in früheren Monaten
Insgesamt 64 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (27x)https://google.de/
202006-12 (24x)https://google.com/
202101-03 (9x)https://google.de
2020-2021 (4x)https://www.bing.com/

[Top of page]

"Informatik: Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus" | 5 Comments
The authors of the comments are responsible for the content.

Re: Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus
von: trunx am: Sa. 16. März 2019 15:09:08
\(\begingroup\)
Hallo Delastelle,

vielen Dank für den Artikel. Ich habe mich vor vielen Jahren ebenfalls mal mit dem TSP uz. im Rahmen meiner Diplomarbeit beschäftigt. Daher war es interessant, mal wieder etwas dazu zu lesen.

bye trunx\(\endgroup\)
 

Re: Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus
von: Delastelle am: Mo. 18. März 2019 00:36:16
\(\begingroup\)
Hallo,

ich habe jetzt noch etwas ergänzendes zum Artikel geschrieben.
Und zwar Grafiken und Werte von 18 guten Lösungen.

LinkErgänzung zu meinem Artikel "Rundreiseproblem (TSP)" - noch mehr Grafiken

Die Grafiken sind sehr breit - auch deshalb wollte ich sie nicht in den Artikel einfügen.

Viele Grüße
Ronald\(\endgroup\)
 

[Kein Betreff]
von: haribo am: Fr. 22. März 2019 14:50:40
\(\begingroup\)
\(\endgroup\)
 

Re: Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus
von: haribo am: Fr. 22. März 2019 15:36:16
\(\begingroup\)
habs in den anderen treat verschoben\(\endgroup\)
 

Re: Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus
von: Friedel am: Mo. 29. April 2019 19:44:40
\(\begingroup\)
Falls jemand das ganze weniger von der mathematischen Seite und mehr für die praktische Anwendung interessiert, kann er bestimmt www.theprojectspot.com/tutorial-post/solving-traveling-salesman-problem-using-google-maps-and-genetic-algorithms/9 gut gebrauchen. Das ist ein Script, das solche Rundreisen in Google Maps berechnet.Da werden also tatsächlich existierende Verkehrswege benutzt. Das ganze kann man auch für eigene Zwecke anpassen, wenn man es von github.com/leejacobson/googlemaps-tsp-ga downloadet.

Ich habe eine frühere Version des Scriptes erfolgreich verwendet, als ich 2010 die 99 Kindergärten in Landau (Pfalz) und in den Landkreisen Südliche Weinstraße und Germersheim im Rahmen der Aktion Kinder wollen singen besucht habe um die Liederbücher zu verteilen. Damals hat sich auch gezeigt, wo die Grenzen des Ameisenalgorithmus
 in der Praxis sind. Das Ergebnis war nämlich eine Route, die mehr als 50 Stunden gedauert hat. Entsprechend musste ich die „Rundreise“ 4 mal unterbrechen und zum Schlafen nach Hause fahren. Wahrscheinlich war die gefahrene Route sehr weit vom Optimum entfernt, weil ich teilweise relativ weite Heimfahrten hatte. Die neue Route mit den verbleibenden Zielen habe ich täglich neu berechnet.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]