Die Mathe-Redaktion - 16.07.2019 12:44 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 415 Gäste und 23 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Ergänzung zu meinem Artikel "Rundreiseproblem (TSP)" - noch mehr Grafiken
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Ergänzung zu meinem Artikel "Rundreiseproblem (TSP)" - noch mehr Grafiken
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-03-17


Hallo Leute!

Zu meinem aktuellen Artikel "Lösen eines Rundreiseproblems(TSP) durch 96 Städte mittels Ameisenalgorithmus" ( article.php?sid=1859 ) habe ich noch mehr Näherungslösungen, die etwas schlechter sind als 6748.
Im Artikel hatte ich 4 Lösungen vorgestellt.




Edit:
Hier nun 18 Lösungen.
Besonders interessant finde ich die Lösungen Nr. 4 (von links oben nach rechts unten) mit ff = 6753 und nur 5 Änderungen zur Lösung 6748.
Interssant auch die Lösungen Nr. 13 (6760) und Nr.17 (6764) mit jeweils 17 Änderungen zur besten von mir gefundenen Lösung.
Nr.13 und Nr.17 sind nur 12 bzw.16 Einheiten schlechter als die beste von mir gefundene Lösung, unterscheiden sich jedoch recht stark von ihr.
Zwischen 6758 B (Nr.10) und 6760 C (Nr.13) gibt es 19 Änderungen.

Die grünen Strecken sind Strecken die auch in der besten Lösung enthalten sind.
Rote Strecken unterscheiden sich von der besten Lösung.
Über den Diagrammen habe ich noch "rote Wege" berechnet.
Dies sind die Abweichungen von den bisherigen Lösungen.
Für Diagramm 18 sind es die Abweichungen von den anderen 17 Diagrammen(Lösungen).

Die Bilder haben leider etwas Überbreite.

Hier noch die 18 gezeichneten Rundreisen:
txt
% ff = 6748
x1 = [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];
 
% ff = 6750
x2 = [65 64 40 33 16 24 19 87 23 36 18 45 41 37 86 79 17 85 44 56 ...
      29 22 35 53 49 72 61 50 14 76 27 28 77 91 94 93 75 78 92 95 ...
      60 80 62 59  2  8 51 55 57 54 88 67 68 90 70 25 21 52 10 89 ...
      58  3 63 15 12 48 43  7 26 42 69 71  1 39 74 73 38  5  4  6 ...
      96 20 83 13 84 30 34 66 11  9 31 81 82 46 47 32];
 
% ff = 6752
x3 = [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 63  3 58 89 10 52 21 25 70 90 68 ...
      67 88 54 57 55 51  8  2 59 62 80 60 95 92 78 75 93 94 91 77 ...
      28 27 76 14 50 61 72 49 53 35 22 29 56 44 85 17 79 86 37 41 ...
      45 18 36 23 87 24 16 33 40 64 65 32 47 46 82 81];
 
% ff = 6753
x4 = [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 75 93 94 91 77 89 10 52 21 ...
  25 70 90 68 67 88 54 57 55 51  8  2 59 62 80 60 95 27 ...
  76 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];
 
% ff = 6754
x5 = [39  1 71 69 42 26  7 43 48 12 15 19 87 23 63  3 58 18 ...
  36 37 41 45 89 10 52 21 25 70 90 68 67 88 54 57 55 51 ...
   8  2 59 62 80 60 95 92 78 75 93 94 91 77 28 27 76 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];
 
% ff = 6754
x6 = [79 17 85 44 56 29 22 35 53 49 72 61 50 14 76 27 28 77 ...
  91 94 93 75 92 78 95 60 80 62 59  2  8 51 55 57 54 88 ...
  67 68 90 70 25 21 52 10 89 58  3 63 19 15 12 48 43  7 ...
  26 42 69 71  1 39 74 73 38  5  4  6 96 20 83 13 84 30 ...
  34 66 11  9 31 81 82 46 47 32 65 64 40 33 16 24 87 23 ...
  36 18 45 41 37 86];
 
% ff = 6755
x7 = [70 25 21 52 10 89 58  3 63 19 15 12 48 43  7 26 42 69 ...
  71  1 39 74 73 38  5  4  6 96 20 83 13 84 30 34 66 11 ...
   9 31 81 82 46 47 32 65 64 40 33 16 24 87 23 36 18 45 ...
  41 37 86 79 17 85 44 56 29 22 35 53 49 72 61 50 14 76 ...
  27 28 77 91 94 75 93 92 78 95 60 80 62 59  2  8 51 55 ...
  57 54 88 67 68 90];
 
% ff = 6756
x8 = [24 16 86 79 17 85 44 56 29 22 35 53 49 72 61 50 14 76 ...
  27 28 77 91 94 93 75 92 78 95 60 80 62 59  2  8 51 55 ...
  57 54 88 67 68 90 70 25 21 52 10 89 45 41 37 36 18 58 ...
   3 63 23 87 19 15 12 48 43  7 26 42 69 71  1 39 74 73 ...
  38  5  4  6 96 20 83 13 84 30 34 66 11  9 31 81 82 46 ...
  47 32 65 64 40 33];
 
% ff = 6758
x9 = [69 42 26  7 43 48 12 15 19 63  3 58 89 10 52 21 39 25 ...
  70 90 68 67 88 54 57 55 51  8  2 59 62 80 60 95 92 78 ...
  75 93 94 91 77 28 27 76 14 50 61 72 49 53 35 22 29 56 ...
  44 85 17 79 86 37 41 45 18 36 23 87 24 16 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  1 71];
 
% ff = 6758
x10 = [12 15 63  3 58 18 89 10 52 21 25 70 90 68 67 88 54 57 ...
  55 51  8  2 59 62 80 60 76 27 95 92 78 75 93 94 91 77 ...
  28 45 41 37 72 61 14 50 22 29 56 35 53 49 44 85 17 79 ...
  86 36 23 87 19 24 16 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];
 
% ff = 6760
x11 = [ 7 43 48 12 15 63  3 58 89 10 52 21 25 70 90 68 67 88 ...
  54 57 55 51  8  2 59 62 80 60 95 93 94 77 91 75 92 78 ...
  28 27 76 14 50 61 72 49 53 35 22 29 56 44 85 17 79 86 ...
  37 41 45 18 36 23 87 19 24 16 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];
 
% ff = 6760
x12 = [42 69 71  1 74 73 38  5  4  6 96 20 83 13 84 30 34 66 ...
  11  9 31 81 82 46 47 32 65 64 40 33 24 16 86 79 17 85 ...
  44 56 29 22 35 53 49 72 61 50 14 76 27 28 77 91 94 93 ...
  75 78 92 95 60 80 62 59  2  8 51 55 57 54 88 67 68 90 ...
  70 25 39 21 52 10 89 45 41 37 36 18 58  3 63 23 87 19 ...
  15 12 48 43  7 26];
 
% ff = 6760
x13 = [47 32 65 64 40 33 16 24 87 23 36 18 45 41 37 86 79 17 ...
  85 44 56 29 22 35 53 49 72 61 50 14 76 27 28 77 91 94 ...
  93 75 92 78 95 60 80 62 59  2  8 51 55 57 54 88 67 68 ...
  90 70 25 39 21 52 10 89 58  3 63 19 15 12 48 43  7 26 ...
  42 69 71  1 74 73 38  5  4  6 96 20 83 13 84 30 34 66 ...
  11  9 31 81 82 46];
 
% ff = 6761
x14 = [55 51  8  2 59 62 80 60 95 92 78 75 93 94 91 77 28 27 ...
  76 14 50 61 72 49 53 35 22 29 56 44 85 17 79 86 37 41 ...
  45 18 36 23 87 24 16 33 40 64 65 32 47 82 46 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 63  3 58 89 10 52 21 25 70 ...
  90 68 67 88 54 57];
 
 % ff = 6762
x15 = [82 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 63  3 58 89 10 52 21 ...
  25 70 90 68 67 88 54 57 55 51  8  2 59 62 80 60 95 92 ...
  78 75 93 94 91 77 28 27 76 14 50 61 72 49 53 35 22 29 ...
  56 44 85 17 79 86 37 41 45 18 36 23 87 19 24 16 33 40 ...
  64 65 32 47 46 81];  
 
% ff = 6764
x16 = [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 63  3 58 89 10 52 21 25 ...
  70 90 68 67 88 54 57 55 51  8  2 59 62 80 60 95 92 78 ...
  75 93 94 91 77 28 27 76 14 50 61 72 49 53 35 22 29 56 ...
  44 85 17 79 86 37 41 45 18 36 23 87 24 16 33 40 64 65 ...
  32 47 46 81 82 31];
 
% ff = 6764 
x17 = [47 32 65 64 40 33 16 24 87 23 36 18 45 41 37 86 79 17 ...
  85 44 56 29 22 35 53 49 72 61 50 14 76 27 28 77 91 94 ...
  93 75 78 92 95 60 80 62 59  2  8 51 55 57 54 88 67 68 ...
  90 70 25 21 52 10 89 58  3 63 43 48  7 26 42 69 71  1 ...
  39 74 73 38  5  4  6 96 20 83 13 84 30 34 66 11  9 31 ...
  81 12 15 19 46 82];
 
% ff = 6765
x18 = [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 75 93 94 91 77 89 10 52 21 25 70 90 68 ...
  67 88 54 57 55 51  8  2 59 62 80 60 95 27 76 14 50 61 ...
  72 49 53 35 22 29 56 44 85 17 79 86 16 24 33 40 64 65 ...
  32 47 46 81 82 31];

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-03-22




es gibt zwar keine schnelle strasse zwischen 78 yvelynes und 95 val-d'oise insofern könnte das länger dauern...

aber ausgehend von deiner Lösung mit ff=6748
komme ich händisch mit dem gelben weg im zentralen bereich nahe paris auf ~6 weniger also ~6742

..28 78 95 92 75 93 94 91..
haribo





  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-03-24


Hallo Haribo!

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 95 92 75 93 94 91 77 89 10 52 21 ...
      25 70 90 68 67 88 54 57 55 51  8  2 59 62 80 60];
Deine Route kommt leider nur auf 6750 Einheiten Länge.
% 28 78 95 92 75 93 94 91 -> 61,26,12,19,9,15,17 Summe = 159 (6750)
% 28 78 92 95 93 75 94 91 -> 61,10,19,30,9,11,17 Summe = 157 (6748)

2019-03-22 15:39 - haribo in Beitrag No. 1 schreibt:
es gibt zwar keine schnelle strasse zwischen 78 yvelynes und 95 val-d'oise insofern könnte das länger dauern...
Ergänzend gibt es auch keine guten Straßen vom Festlandsfrankreich
nach Korsika (Städte 20 und 96). :-)
Also eher eine Rundreise mit einem Hubschrauber. Der findet immer einen Landeplatz an den angegebenen Koordinaten.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-03-24




hm, ich hatte mir einige mühe gegeben die department-orte aus deiner skizze zu ermitteln und dann direkt in der skizze gemessen..., es besteht für mich also derzeit irgendwie eine diskrepanz zwischen deiner berechnung und deiner skizze???

insbesondere die beiden strecken:
"78-95" messe ich mit 20,0 und du gibst 26 an
"92-75" messe ich mit 12,7 und du gibst 19 an
???



generell kann ich deine skizze bisher auf keine landkarte projezieren, die landkarte müsste ~20% nord_süd gestaucht werden

möglicherweise könnte man mal deine strecken-längen-formel zwischen zwei in koordinaten (länge/breite) angegebenen orten überdenken?

spontan hätte ich folgenden ansatz mit spährischen dreiecken benutzt, bei welchem grosskreisabschnitte berechnet werden:
"kürzeste Distanz d wird über das Kugeldreieck Nordpol-P1-P2 mit dem Kosinussatz ermittelt. Sei P1 = (n1,o1), P2 = (n2,o2), dann gilt:
d = arccos[sin(n1) · sin(n2) + cos(n1) · cos(n2) · cos(o1-o2)]"

ok, durch frankreich verläuft der nullmeridian, darauf muss man also nochmal achten, also evtl westliche längen als negative zahl eingeben?

aber selbst fals deine streckenberechnung nen fehler hätte, ändert das nichts an deinem geschickten ameisenansatz...
haribo



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-03-24



eine andere frage beschäftigt mich schon länger:

die runde kann ich ja an einem beliebigen ort starten, also auch an einem aussenliegenden und dort in uhrzeigersinn, hier z.B. quimper/finisterre, wenn ich dann mehr oder weniger erstmal ein gummiband (pink) um den ganzen bereich lege und abfahre, würde ich die anderen aussenliegenden orte A;B;C...I in genau dieser reihenfolge besuchen

ist die aussage richtig: dass auch im absolut gesamt kürzesten wege mit gleichem start diese orte immer in der gleichen reihenfolge auftauchen? also alle anderen inneren zwischen orte als einzel-ausflüge ins landesinnere von der gummibandrunde definiert werden könnten?

die aussage trifft jedenfals für deine beste lösung zu... und auch für meine IMO jetzt nochmals 0,4% bessere(!) route, hier gelb dargestellte, bei der hier lediglich der von dir gefundene "innere wegekreis" an einer anderen stelle an den "aussenring" angeschlossen wurde (nebst geringen änderungen an den anschlüssen), also beispielsweise paris zwischen START und A besucht wird und nicht mehr zwischen D und E... aber ABCDEFG trotzdem in dieser reihenfolge in der besuchsliste stehen würden

haribo



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-03-24


in deiner distanc formel steht:
tht1 = ort1(2)*pi/180+pi/4 (tht1 steht wohl für länge ort 1?)

bei mir an gleicher stelle nur länge=o1 (östliche länge von ort 1)

pi/180 ist ne umrechnung von RAD zu DEG, also plausibel, aber wofür steht das +pi/4 ???

bis auf das pi/4 sind die formel gleich

haribo



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-03-25


Hallo Haribo!

Die Distanzformel stammt auch einem Matlab-Programm einem Demo zu Matlab 4 - "worldtravel.m" oder so ähnlich.
Darin wurden Flüge um die Welt gezeichnet und die Entfernungen berechnet.
Die Orte von "worldtravel.m" sind:
Matlab
% west
latLongData1=[-34 18.3; 14.5 -17.5; 51.5 0; 25.7 -80; 55.7 37.5; ...
  1.3 36.8; 42.3 -71.4; 28.5 77.1; 24.5 46.6; -23.5 -46.5];
% east
latLongData2=[61.2 -150; 40 116.4; 13.5 144.8; 21.3 -157.9; ...
  32.6 -117.2; 1.3 103.9; -33.9 151.2; 35.6 139.7; -41.3 174.8];
...
    phi1=city1(1)*pi/180;
    tht1=(city1(2)+135)*pi/180+pi/4; 
 
    phi2=city2(1)*pi/180;
    tht2=(city2(2)+135)*pi/180+pi/4; 
...
    % Following calculation uses Napier's Spherical 
    % Trigonometry Cosine Rule for Sides
    % Ref: VNR Encyclopedia of Mathematics
    angularDistCos=sin(phi1)*sin(phi2)+cos(phi1)*cos(phi2)*cos(tht1-tht2);
    angularDist=acos(angularDistCos)*180/pi;
    % Earth radius in miles: 3963
    earthRadius=3963;
    distance=(angularDist*pi/180)*earthRadius;
    erg(i,j) = distance;
Die Formeln habe ich direkt übernommen. Statt mit Meilen rechne ich mit Kilometern.
Bei meinem Frankreich-Problem (TSP96) musste ich so nur 96 mal 2 Koordinaten angeben - die Distanzmatrix von 96x96 wird mir dann berechnet.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-03-25


Beim matlap vorbild City2 war im Original noch ein +135° .... evtl. hatten sie damit den Sprung über den nullmeridian gemeistert???

entweder solltest du in deiner distanc formel auch die +135 schreiben (woimmerfür sie ist) oder die pi/4 weglassen

tht1 = (ort1(2)+135)*pi/180+pi/4
oder
tht1 = ort1(2)*pi/180

ich tendiere zu letzterem, das entspricht allen anderen mir bekannten entfernungsformeln und auch der Ref: VNR Encyclopedia of Mathematics...

mit der art und weise wie du die latLong koordinaten eingibst hat das  jedenfals weniger zu tun



das meilenrechnen kommt aus der seefahrt und ist praktisch weil eine sm(seemeile) sowiso über den winkel an der erdoberfläche definiert ist,
1 winkelminute = 1sm

die luft-fahrt hat es übernommen die engländer/amerikaner mit ihren statut-mile´s nicht, denen war 1593 der fuss näher als die erde unter den füssen

haribo



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-03-26


Hallo Haribo!

Es kann auch sein, dass die +135 nur in bestimmten Fällen verwendet wurde -
ich habe gerade nicht mehr den vollständigen Quelltext vorliegen.
Mit dem +pi/4 wollte ich wohl erreichen, dass die Städte alle bei
östlicher Länge liegen. Die Distanzen müßten gleich bleiben.
(Die +pi/4 werden bei Start und Ziel addiert.)

Zu Beitrag 4: gewisse Städte werden sicher immer in der gleichen
Reihenfolge in die Gesamtroute eingefügt. Das ändet aber nichts
daran, dass die Komplexität des Rundreiseproblems sehr hoch bleibt.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-03-26


Nun an irgendwas muss es schon liegen wenn Städte-Graphen nicht auf Landkarten projezierbar sind... und distanzen unterschiedlich ermittelt werden... aber sei’s drum kann ja an mir liegen

Nochmal zur Gummiband Umrandung: für die aussenliegenden Orte dürfte es doch einfach sein zu zeigen dass die konvexe Hülle der absolut kürzeste Weg ist

Alls Beispiel alle 12 zahlen einer analogen Uhr haben dann nicht 12! Varianten sondern nur 1

Kommt ein weiterer innerer Ort hinzu gäbe es nur 12 also n Möglichkeiten ihn in den rundweg einzubauen, und ich nehme doch an dass es immer noch eindeutig der kürzeste Weg ist dann genau einmal einen binnenausflug zu machen???

Ab wann (und wiso überhaupt) wird es denn dann so komplex?
haribo



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-03-27


Hallo Haribo!

Wenn man Pech hat ist eine Lösung für 95 Städte stark unterschiedlich zu einer Lösung mit 96 Städten.
Wir hatten dazu mal eine Diskussion:
LinkTSP und Induktion

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-03-29


vielen dank für den link Delastelle,

dich beschäftigt TSP schon seit vielen jahren

#2 wiso nicht so? das wären dann nur zwei rote zusatz teilstrecken und der neue TSP wäre zugleich einiges kürzer??


beim weiterlesen:
da steht ja tatsächlich mit jahreszahl 2009 also seit 10 jahren schon alles drin was ich mir letzte woche erarbeitet zu haben meinte... hätte ich mal im MP gesucht...

insb. xylon weist darauf hin das es nicht n! versuche benötigt, er unterscheidet  in #11+#18 zwischen punkten auf der konvexen hülle [k](das gummiband) und inneren punkten [n]

auch sonst sind dort gute ideen angeführt

und in #45 sind fünf jahre später deine vergleiche mit zusätzlichen punkten,
du schriebst damals "Die gefundenen Lösungen (5, 10, 15 Städte) wurden mittels Branch&Bound verifiziert. Die Lösungen zu 20, 25 Städte wurden mit lokaler Suche überprüft und dürften zu 99,9% richtig sein."

(also da solltest du die ausgangs TSP´s doch heute nochmal´s überprüfen...

ich hab jedenfals ad hoc bei 5 städten 8%; bei 10 städten 12% und bei den 15 städten sogar 25% kürzere TSP´s gefunden, das reduziert die von dir angegebenen zusätzlichen änderungsstrecken, ähnlich dem bild oben, ziemlich dolle) in klammern wegen: siehe nachtrag

du fügst meist einen aussenliegenden punkt [k] hinzu, mich würde etwas mehr interessieren wann ein zusätzlicher innerer punkt [n] die inneren ausflüge stark verformt... also beispielsweise wenn man in obiges bild innen ein D einfügt wo genau wird der dann angeschlossen und wann beeinflusst es den anschluss von C... das wäre doch ein sehr lokales problem

haribo

nachtrag: jetzt hab ichs an obigem bild erkannt... hat ein bischen gedauert, das linke bild müsste ein 2/2 quadrat sein ist aber ein rechteck, deine skizzen sind einfach nicht maßstäblich in x/y richtung, daran liegt also wohl auch die diskrepanz in frankreich...
dann dürften wohl deine anderen berechnungen auch richtig sein... sorry ich hatte es immer nur graphisch betrachtet unter der (fehl-)annahme der masstäblichkeit






  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-04-01


Hallo,

@Haribo
Beitrag 2 (TSP und Induktion): falls alle Strecken zugelassen sind, sieht deine Lösung sehr kurz aus.

@all
Zum Ameisenalgorithmus:
(im Artikel waren)
      alpha = 1.0d0
      beta = 5.00d0
      gamma = 0.99d0
      delta = 100
      eps = 0.90d0    
      phi = 0.20d0
      versuche = 2000  
      bigsteps = 1000

 Staedte           96
 Mittelwert(der gefundenen Lösungen) 6928.72920000    
 Standardabweichung           108.946730210

etwas bessere Parameter für das Problem der 96 Städte sind:
 alpha =           1.04000000000    
 beta =           4.71000000000    
 delta =           94
 eps =          0.954000000000    
 phi =          0.192000000000    
 
 gamma =          0.990000000000    
 versuche =         2000
 
 Staedte           96
 bigsteps         1000
 Mittelwert           6898.58800000    
 Standardabweichung           114.603596105  

Dazu muss im Programm "TSP_81_96_Ameise.for" nur ein alpha größer
als 1 erlaubt werden:
Fortran
subroutine ameise ...
...
double precision amatrix(300,300)
...
do 1000 kkk = 1,versuche
        do 1005 i = 1,n
          do 1010 j = i+1,n
            ameise3(i,j) = 0
            amatrix(i,j) = ameise2(i,j)**alpha
            amatrix(j,i) = amatrix(i,j)
1010      continue            
1005    continue
...
do 1600 j = 1,si
            if (x(nr) < aktx(j)) then
              ug(j+1) = ug(j) + amatrix(x(nr),aktx(j))*
     c                          bmatrix(x(nr),aktx(j))
            else
              ug(j+1) = ug(j) + amatrix(aktx(j),x(nr))*
     c                          bmatrix(aktx(j),x(nr))
            endif
Es muss also nur die globale Pheromonmatrix mit alpha potenziert werden.

Viele Grüße
Ronald

Edit:
im Unterprogramm permutation ist noch ein Fehler gewesen -
die Routine wird vom Progamm aber gar nicht verwendet.
Korrekt lautet die Routine so:
Fortran
c *****************************************
c bilden einer Zufallspermutation
c Herrmann: Algorithmen-Arbeisbuch
c *****************************************
      subroutine permutation(perm,elemente) 
      implicit none
      integer elemente
      integer perm(elemente)
      integer i,merk,r
      double precision zwi
c bilde Permutationsvektor
      do 1000 i = 1,elemente
        perm(i) = i
1000  continue
      do 1100 i = elemente,2,-1        
        call random_number(zwi)
        r = floor(zwi*i)+1
        merk = perm(i)
        perm(i) = perm(r) 
        perm(r) = merk 
1100  continue
      end




  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-04-01




es ist selbst bei unter 10 punkten gar nicht so einfach eine systematik zu erkennen, wenn ein zusätzlicher innerer punkt dazu kommt

der neunte punkt I wird eindeutig von der strecke d-e aus eingebunden sofern er im hellgrauen bereich liegt,

ein weiterer punkt würde wohl auch wieder von der nächstliegenden linie aus eingefangen werden, liegt er in diesem fall jedoch ~in dem rotausgemalten bereich dann wird er von c-d aus eingebunden und verändert gleichzeitig die anbindung von I, dann springt also die innere lösung in einen anderen zustand und wird gar nicht mehr von d-e aus eingebunden

den roten bereich hab ich nur abgeschätzt, man könnte ihn mal versuchen noch exakter zu konstruieren

(fortran verstehe ich kaum...)

haribo



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1325
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2019-04-02


Hi,

Mit einem genetischen Algorithmus (sorted match crossover) habe ich folgende Tour berechnet:

x = [29 22 35 50 14 53 49 72 61 76 27 28 78 91 77 94 93 75 92 95 60 80 62 59 2
8 51 10 89 58 3 63 48 43 7 26 42 69 71 1 39 21 52 55 57 54 88 67 68 90 70 25 74
73 38 5 4 6 96 20 83 13 84 30 34 66 11 9 31 81 12 15 19 46 82 47 32 65 64 40 33
16 24 87 23 36 18 45 41 37 86 79 17 85 44 56]



Ich habe allerdings (ohne Umrechnung) direkt die Breiten-/Längenkoordinaten verwendet. Die zugehörige Länge ist etwa 73.546. Mich würde jetzt der Vergleich zur 6748er Tour interessieren, allerdings ist mir nicht ganz klar, ob man auch direkt die Längen umrechnen kann.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2019-04-02


Hallo Kay_S!

Deine Lösung für das modifizierte Problem hat 23 Änderungen zu meiner besten Lösung. (Und auch 73 Übereinstimmungen.)

Die Lösung hat bei mir einen Funktionswert von 6938.
Mir ist nicht klar, wie gut Dein Algorithmus ist oder ob die Modellierung für die Unterschiede sorgt! Hast Du den Euklidischen Abstand benutzt?

Ich habe mit meinem Ameisenalgorithmus in Fortran das Problem,
dass ich zu lange (einige Stunden) zu guten Lösungen für das Frankreichproblem brauche. Und die 6748 erreiche ich schwer, 6750 und 6752 oder schlechtere Funktionswerte häufiger.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-04-03


@kay

du verwendest eine quadratische plattkarten abbildung, man kann aber die gemessenen weglängen nicht miteinander vergleichen bei verschiedenen abbildungsvorschriften...

hier ne mercartorprojektion... im vergleicch mit deiner quadratischen plattkarte


delastelle bildet auch irgendwie verzerrt ab, ihn interessieren scheints nur die gerechneten abstände

einiges besser als die quadratische plattkarte wäre ne rechteckige plattkarte, also z.B die längengrade multipliziert mit cos 46°(breite auf halber bildhöhe) dann sähe deine strecke so aus, bzw du kämst wohl dann zu nem anderen ergebnis...


also um im bild gemessene ergebnisse vergleichen zu können, das erdkugel-TSP problem also auf 2D zu reduzieren (macht IMO sinn), müssten wir uns erst mal definitiv auf eine abbildungsvorschrift einigen
haribo




  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1325
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-04-03


Ich hatte einfach die Längen-/Breitenangaben als x/y-Koordinate in der euklidischen Ebene genommen (das ist freilich eine Verzerrung).
Mittlerweile habe ich die Metrik basierend auf der Umrechnung aus dem Artikel verwendet und bekomme ganz andere Ergebnisse. U.a. habe ich zwei Touren berechnet, bei der die eine bzgl. der ersten Metrik kürzer ist und bzgl. der zweiten länger.




  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-04-03


ja, verschiedene verzerrungen ergeben verschiedene lösungen

da es ansich fürs TSProblem grundsätzlich egal ist, braucht man nur ne abbildungsvereinbarung wenn man ergebnisse sowohl geometrisch also auch rechnerisch bearbeiten/vergleichen möchte, mich interessiert halt immer der geometrische ansatz... drum hätte ich gerne eine 2D ausgangslage

X=cos(46°)*L ;Y=B
wäre dafür recht einfach und erträglich gering verzerrt
haribo



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1325
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-04-03


2019-04-02 23:27 - Delastelle in Beitrag No. 15 schreibt:
Mir ist nicht klar, wie gut Dein Algorithmus ist oder ob die Modellierung für die Unterschiede sorgt! Hast Du den Euklidischen Abstand benutzt?

Ich habe mit meinem Ameisenalgorithmus in Fortran das Problem,
dass ich zu lange (einige Stunden) zu guten Lösungen für das Frankreichproblem brauche. Und die 6748 erreiche ich schwer, 6750 und 6752 oder schlechtere Funktionswerte häufiger.

Interessant, dass das recht lange dauert. Da stellt sich die Frage, wie sich der Ameisenalgorithmus im Vergleich zu anderen Verfahren schlägt. Ich habe die Hintereinanderausführung zweier Verbesserungsheuristiken ausprobiert:

  1. Erzeuge Zufallstour (zufällige Permutation der Knoten)
  2. 2-Opt-Heuristik (ersetze solange Kantenpaare (u0,v0),(u1,v1) durch (u0,u1),(v0,v1), wie sich dadurch eine Verkürzung ergibt)
  3. Knotenverschiebungen (verschiebe x aus dem Teilstück (u0,x,v0) in die Kante (u1,v1), falls sich eine Verkürzung ergibt -> es entsteht (u0,v0) und (u1,x,v1))

Bei 2-Opt werden sich überkreuzende Kanten ersetzt, sodass immer eine kreuzungsfreie Tour entsteht (zumindet beim euklidischen TSP). Bei Schritt 3 wird ein Knoten, falls er sehr nah bei einer anderen Kante liegt, in diese integriert.

Einige tausend Durchgänge (jeweils Schritt 1 bis 3) scheinen zu genügen, um eine Tour der Güte < 6760.0 zu finden, eine Tour mit 6748.0 wird meist in weniger als einer Minute gefunden. Das allerdings mit Java anstelle Fortran.



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2019-04-03


zeigst du mal eine < 6760iger?

ansich gibts nahezu nie eine verbindung zu einem weiter als der fünft-nächste liegende punkt, damit müsste man die zufallstour (schritt 1) doch schon verbessern können???
haribo



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1325
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-04-03


Die Zufallstour ist nur der Ausgangspunkt für die beiden Verbesserungsheuristiken in Schritt 2 und 3 (man kann natürlich auch andere aus einer Konstruktion hervorgegangene Touren verwenden).
Hier sind einige gefundene Lösungen:


len = 6760.0
t = [74 73 38 5 4 6 96 20 83 13 84 30 34 66 11 9 31 81 82 46 47 32 65 64 40 33
16 24 19 87 23 36 18 45 41 37 86 79 17 85 44 56 29 22 35 53 49 72 61 50 14 76 27
 28 78 92 75 91 77 94 93 95 60 80 62 59 2 8 51 55 57 54 88 67 68 90 70 25 21 52
10 89 58 3 63 15 12 48 43 7 26 42 69 71 1 39]

len = 6757.0
t = [18 58 3 63 42 26 7 43 48 34 30 84 13 83 20 96 6 4 5 38 73 74 69 71 1 39 21
 25 70 90 68 67 88 54 57 55 52 89 10 51 8 2 59 62 80 60 76 27 28 78 92 95 93 75
94 91 77 45 41 37 72 61 14 50 22 29 56 35 53 49 44 85 17 79 86 16 24 33 40 64 65
 32 47 46 82 31 9 66 11 81 12 15 19 87 23 36]

len = 6754.0
t = [82 46 47 32 65 64 40 33 24 16 86 79 17 85 44 56 29 22 35 53 49 72 61 50 14
 76 27 28 77 91 94 93 75 78 92 95 60 80 62 59 2 8 51 55 57 54 88 67 68 90 70 25
21 52 10 89 45 41 37 36 18 58 3 63 23 87 19 15 12 48 43 7 26 42 69 71 1 39 74 73
 38 5 4 6 96 20 83 13 84 30 34 66 11 9 31 81]

len = 6753.0
t = [93 94 91 77 89 10 52 21 25 70 90 68 67 88 54 57 55 51 8 2 59 62 80 60 95 2
7 76 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 75]

len = 6750.0
t = [23 36 18 45 41 37 86 79 17 85 44 56 29 22 35 53 49 72 61 50 14 76 27 28 77
 91 94 93 75 78 92 95 60 80 62 59 2 8 51 55 57 54 88 67 68 90 70 25 21 52 10 89
58 3 63 15 12 48 43 7 26 42 69 71 1 39 74 73 38 5 4 6 96 20 83 13 84 30 34 66 11
 9 31 81 82 46 47 32 65 64 40 33 16 24 19 87]

len = 6748.0
t = [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 8
7 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 6
7 88 54 57 55 51 8 2 59 62 80 60 76 27 14 50]



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2741
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2019-04-04


hallo,
ich hatte mich vor ca. 30 Jahren auch mal mit dem TSP beschäftigt, der zugrunde liegende Algorithmus orientierte sich dabei zunächst an einer sogenannten Evolutionsstrategie. Diese sah zunächst wie folgt aus:

1. wähle eine beliebige Route (z.B. einfach [1,...,n]),
2. Mutation: wähle 1<k<n Städte aus und permutiere sie (bei großen k zufällig)
3. Selektion: vergleiche die neuen Distanzen mit der alten, gibt es eine bessere (beste), nimm diese als neue Route, falls nicht, lasse auch schlechtere mit einer gewissen Wahrscheinlichkeit zu.

Solange die Änderungen sich noch oberhalb eines bestimmten Abbruchkriteriums befinden, mache mit der neuen (eventuell auch schlechteren) oder halt der alten Route bei 2. weiter.

Sowohl bei Mutation als auch bei Selektion gibt es Optimierungsmöglichkeiten, es ist z.B. klar, dass bei sehr kleinen Mutationsraten k, die Änderungen möglicherweise zu lange dauern oder erst gar nicht geschafft werden. Bei zu großen Mutationsraten k dagegen können sich gute Teilstrecken nicht etablieren. Analog sieht es mit den Selektionsraten aus.

m gute Lösungen wurden auf diese Weise als sogenannte Population gesammelt, mithilfe eines genetischen Algorithmus' (sog. Rekombination) wurden daraus, ebenfalls mittels Mutation und Selektion, neue Routen erzeugt.  Dabei wurden Teilstrecken, die sich nicht mehr geändert, also bewährt haben, fixiert und nur noch die Zwischenbereiche geändert.

Wie auch immer, ich würde gern mitmachen, habt ihr euch auf eine Distanzmatrix geeinigt und könntet ihr sie mir zur Verfügung stellen (matlab habe ich nicht)?

vielen Dank
bye trunx


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, vom Themenstarter, eingetragen 2019-04-04


Hallo trunx!

Die im Artikel verwendete Distanzmatrix für das 96 Städte Problem
liegt bei mir im Notizbuch unter:
> Distanzmatrix zu einem TSP durch 96 Städte Frankreichs "Tour-de-France" <

Matlab ist nicht notwendig, ich habe die letzten Grafiken mittels des kostenlosen Octave hergestellt.

@Kay_S: die 6757er Tour kannte ich noch nicht!

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2019-04-04


die tour ist im norden zu breit, im süden zu schmal
aber so ungefähr kann man die departments ablesen.




  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2741
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2019-04-09


2019-04-03 22:37 - Kay_S in Beitrag No. 19 schreibt:
Interessant, dass das recht lange dauert. Da stellt sich die Frage, wie sich der Ameisenalgorithmus im Vergleich zu anderen Verfahren schlägt.

...

Einige tausend Durchgänge (jeweils Schritt 1 bis 3) scheinen zu genügen, um eine Tour der Güte < 6760.0 zu finden, eine Tour mit 6748.0 wird meist in weniger als einer Minute gefunden. Das allerdings mit Java anstelle Fortran.

ich habe nun meinen Evolutionsalgorithmus das ganze Wochenende laufen lassen und dümple noch bei 8000 herum (mein bestes Ergebnis ist bisher 7799) - es ist wirklich beeindruckend, wie schnell eure Verfahren sind!


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1319
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, vom Themenstarter, eingetragen 2019-04-09


Hallo trunx!

2019-04-09 00:51 - trunx in Beitrag No. 25 schreibt:
ich habe nun meinen Evolutionsalgorithmus das ganze Wochenende laufen lassen und dümple noch bei 8000 herum (mein bestes Ergebnis ist bisher 7799) - es ist wirklich beeindruckend, wie schnell eure Verfahren sind!

Ich hoffe, Du verwendest keinen Computer von 1990 - z.B. einen 286er mit 16 MHz Taktfrequenz ;-) .

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2741
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2019-04-09


:D
ja, das könnte man fast glauben. Tatsächlich hatte ich seinerzeit wirklich einen solchen Rechner und der lief einige Wochen in meiner Kammer; ich hatte gehofft, dass es diesmal schneller ginge.

Das Problem ist wohl heute etwas anders gelagert, ich programmiere in php (früher Turbo Pascal) und lasse das Programm in Windows Eingabeaufforderung laufen. Aber diese Windows-PC's sind ja ständig mit anderen Dingen beschäftigt, ständig wird nach Updates gesucht oder installiert oder schnell mal ein Virenscan gemacht usw. usf.

Naja und eben nicht zu vergessen, es gibt eben auch langsame Algorithmen ;)

meint trunx (dessen bester Wert nun bei 7643 liegt)


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1325
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2019-04-10


Im Netz gibt es ja einige Informationen zur Güte verschiedener Algorithmen z.B. hier.
Demnach kommt man bei mittelgroßen Instanzen (50<n<3000) mit einer Konstruktionsheuristik wie Farthest Insertion bereits auf ca. 10% an das Optimum heran, in Kombination mit einer Nachoptimierung (z.B. 2-Opt-Heuristik) etwa 7-8%.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2014
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2019-04-12


ich weiss nun nicht was "farthest insertion" bedeutet, aber es scheint einige verfahren zu geben die schnell ungefähr in den bereich +10% ans optimum kommen...

zb dieses: von jedem ort eine linie zu den zwei nächstliegenden orten,
ergibt einen graphen (erstaunlicherweise ohne überschneidungen) und in diesem fall sogar ohne inseln

drumrum eine hüllkurve (weiss) gelegt, dabei keinen ort doppelt ansteuern
ergibt hier eine route die hier schon 84 orte geschickt erreicht, geschickt weil sie ja nahezu immer nur auf den kürzest und zweitkürzesten wegen fährt

die fehlenden 12 orte ziemlich freihändig eingefangen (blau) und an die weisse route angeschlossen (gelb) ergibt eine geschlossenen route mit ~108% weglänge gegenüber der bisher von euch optimalsten gefundenen

haribo



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1325
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2019-05-11


Auf meiner Webseite kann ein allgemeines Javascript-Löseprogramm ausprobiert werden :-) Allerdings nur für das Euklidische TSP, dafür jedoch mit grafischer Ausgabe. Es benutzt eine Iterierte Lokale Suche zur Lösung, die bereits ziemlich gute Lösungen produziert.
Zum Testen kann man z.B. die Probleme aus der TSPLIB verwenden, da hier alle Optimallösungen bekannt sind, so dass man die Ergebnisse vergleichen kann. Man kann die Problemdaten unverändert in das Eingabefeld kopieren.



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]