Uni-Kiel Wiso-Fakultät |
KontaktStudenten Forum Kiel
Das Studentenforum für Kiel und Umgebung.
(Werbeeinträge sind nicht erlaubt)
Simulated Annealing
| Autor | Nachricht |
|---|---|
|
Verfasst am: 19. 02. 2006 [00:14]
|
|
|
Satan
Themenersteller
Dabei seit: 23.08.2005
Beiträge: 405
|
Hi! In Torbens letztem Tut wurde ja noch simulated annealing behandelt. dabei habe ich folgendes Problem: Die Startlösung war die Rundereise: 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 2 dann wurde die Kanten 2->1 und 3->5 entfernt (also i j = 1 3) und geprüft ob die Rundereise: 2->3->1->5->6->4->2 besser ist. sie war zwar schlechter, wurde aber wegen exp(-2/6) = 0,72 > 0,25 = gamma trotzdem angenommen. dann wurde erneut bei i j 1 3 gestartet. Wenn man nun aber wieder von Position 1 zu Position 3 geht und die Kante von Postion 1 zu Position 2 weglässt und außerdem von Position 2 zu Position 4 geht, wofür dann die Kante von Position 3 zu Position 4 weggelassen wird, erhält man wieder die Ausgangslösung, nämlich die Startrundreise 2->1->3->5->6->4->2 würde man dann wieder i j 1 3 wählen, würde man ja "kreisen". wie muss ich also die "i" und "j" ändern um dies zu vermeiden? Hätte man ausgehend von der neuen Rundreise mit i j 1 4 weitermachen müssen und versteht überhaupt einer was ich meine??? mfg Satan http://www.pokerstrategy.com/u36VAF
Lerne Poker spielen mit Strategie ohne eigene Kosten und hole dir deinen 150$ Bonus von PokerStrategy! PokerStrategy ist kostenlos! |
|
Verfasst am: 19. 02. 2006 [13:39]
|
|
|
impi
Dabei seit: 23.09.2005
Beiträge: 60
|
also ich habs so aufgeschrieben : i=1 ---> n-2 ( n =Anzahl der Knoten ) j=i+2 ---> n 1. Iteration i=1 , daraus folgt das j =3 ist. C1,5 + C3,6 -C1,3-C5,6 = 8+6-6-4 =4 > 0 also weitersuchen..... also ich hab das so verstanden, dass man im prinzip nur die kanten austauschen und dann nachprüfen muss, ob die neue Rundreise Kostengünstiger ist als die alte !!?? oder übersehe ich da was ? |
|
Verfasst am: 19. 02. 2006 [15:24]
|
|
|
Uzif
Dabei seit: 25.08.2005
Beiträge: 92
|
ich habe zu dem thema mal eine frage zum buch auf seite 146. und zwar auf die abb. 6.8: 2-opt: es soll j=i+2 sein, nun ist aber hier i=2 und j=5 ... da ich zu diesem thema sowieso nicht recht den draht habe, wäre ich dankbar für ein paar erläuterungen. |
 |
|
|
Verfasst am: 19. 02. 2006 [22:18]
|
|
|
Henrik
Dabei seit: 13.02.2006
Beiträge: 11
|
Das Thema macht mir auch Schwierigkeiten... Ist es nicht so, dass für ein gegebenes i im Algorithmus zunächst alle Möglichkeiten mit j gebildet werden? Da werden ja zwei Schleifen initialisiert... Meine Frage diesbezüglich ist (vielleicht weiß ein Tutor bescheid?): Nachdem man im TSP per Suche nach dem besten Nachfolger eine zulässige Lösung gefunden hat: Sortiert man dann die nach aufsteigender Reihenfolge neu? Oder beziehen sich i und j noch auf die von Anfang an gegebenen Knoten? Vielen Dank schon einmal für die Hilfe! |
|
Verfasst am: 20. 02. 2006 [00:08]
|
|
|
Satan
Themenersteller
Dabei seit: 23.08.2005
Beiträge: 405
|
impi schrieb: also ich hab das so verstanden, dass man im prinzip nur die kanten austauschen und dann nachprüfen muss, ob die neue Rundreise Kostengünstiger ist als die alte !!?? oder übersehe ich da was ? Bei simulated annealing werden ja auch Verschlechterungen zugelassen. Man nimmt nicht nur bessere Rundreisen. Das Problem liegt bei darin, dass nachdem die neue Rundreise übernommen wurden, i und j so gewählt wurden, dass gleich im nächsten Schritt wieder die Ausgangsrundreise enstanden wäre. Ist man dann fertig, oder wie? Oder muss man nicht doch erst einmal j laufen lassen, selbst wenn zwischendurch eine Neue Rundreise übernommen wurde? http://www.pokerstrategy.com/u36VAF
Lerne Poker spielen mit Strategie ohne eigene Kosten und hole dir deinen 150$ Bonus von PokerStrategy! PokerStrategy ist kostenlos! |
|
Verfasst am: 20. 02. 2006 [12:33]
|
|
|
LuckyLuke
Dabei seit: 15.10.2004
Beiträge: 224
|
Ich denke mal in der Klausur wirst Du nicht die Zeit haben, das dann noch weiter zu rechnen. In einer alten Klausur wurde es ja auch so formuliert, das man es nur bis zur ersten Verbesserung durchführen braucht, oder bei 2-opt ohne SA halt eine vorgegebene Anzahl an Schritten. |
