Czytam teraz o algorytmie wyżarzania (zainteresowała mnie jego nazwa) czy to prawda że algorytm ten podczas procesu optymalizacji może wykonać ruch tylko do rozwiązania gorszego od bieżącego ? jesli tak to jest to strasznie dziwne i powolne ( w sensie długa droga)
0
0
Cisi204 napisał(a):
Czytam teraz o algorytmie wyżarzania (zainteresowała mnie jego nazwa) czy to prawda że algorytm ten podczas procesu optymalizacji może wykonać ruch tylko do rozwiązania gorszego od bieżącego ? jesli tak to jest to strasznie dziwne i powolne ( w sensie długa droga)
Nie.
Symulowane wyżarzanie polega w ogólności na tym, że z biegiem czasu (kolejnymi iteracjami algorytmu wykorzystującego symulowane wyżarzanie) algorytm będzie, w zależności od wariantu:
- coraz mniej skory do zaakceptowania zmiany stanu na nowy
- będzie dokonywał coraz mniejszych zmian
W przypadku rozwiązywania problemu komiwojażera trochę ciężko byłoby rozpatrywać zmiany w kategoriach "dużych" i "małych", więc bierzemy wariant pierwszy.
Algorytm wyżarzania może zaakceptować zmianę na gorsze, ale wyłącznie z pewnym prawdopodobieństwem - tym mniejszym, im bardziej ta zmiana pogorszy wynik oraz im więcej czasu upłynęło.
Możesz przyjąć np. takie prawdopodobieństwo:
k to jakaś dowolna, dodatnia stała, którą możesz sobie ustalić na początku. T to "temperatura" która również powinna być dodatnia, a ponadto maleć z czasem.
Zauważ, że jeśli zmiana będzie korzystna lub neutralna (/\S <= 0) prawdopodobieństwo zawsze wyniesie 1, bo wykładnik potęgi będzie nieujemny. Jeśli zmiana pogorszy wynik, prawdopodobieństwo będzie w przedziale (0, 1) - dla bardzo złych wyników będzie dużo mniejsze, niż dla tylko troszkę gorszych. Podobnie, prawdopodobieństwo zaakceptowania niekorzystnej zmiany będzie wyższe na początku działania algorytmu, gdy temperatura jest wysoka np. T=100 niż prawdopodobieństwo zaakceptowania tej samej zmiany, gdy temperatura spadnie do np. T=20.
0
czyli algorytm ten podczas procesu optymalizacji może wykonać ruch do rozwiązania gorszego niż bieżące z pewnym prawdopodobieństwem, a do rozwiązania lepszego zawsze ? tak ?Czytałem o tym że im "temperatura" zejdzie tym on będzie dokonywał coraz rozsądniejszych , korzystniejszych wyborów
0
Cisi204 napisał(a):
czyli algorytm ten podczas procesu optymalizacji może wykonać ruch do rozwiązania gorszego niż bieżące z pewnym prawdopodobieństwem, a do rozwiązania lepszego zawsze ? tak ?Czytałem o tym że im "temperatura" zejdzie tym on będzie dokonywał coraz rozsądniejszych , korzystniejszych wyborów
Tak, algorytmy symulowanego wyżarzania w założeniu mają na początku dokonywać "odważniejszych" zmian w celu "przeszukania" przestrzeni rozwiązań, ale z biegiem czasu stają się coraz bardziej "ostrożne" by mogły zbiec do lokalnego optimum.
Tylko w przypadku grafów i żonglowania permutacjami z tym zbieganiem może być trochę ciężej - bardziej chodzi o to, by punkt startowy nie ograniczył możliwości przeszukiwania. Zauważ, że w algorytmie zachłannym początkowe wybory algorytmu bardzo ograniczają możliwe dalsze kroki - może być tak, że pierwszy krok będzie super-korzystny i zostanie wybrany, ale w rzeczywistości wybranie innej krawędzi w danym kroku mogłoby się okazać korzystniejsze w przyszłości, "odblokowując" inne, jeszcze korzystniejsze połączenie :)
0
Patrząc takim amatorskim okiem i chcąc porównać działanie algorytmów ze względu na jakość i efektywność. Można przypuszczać że najbardziej stabilnym algorytmem jest algorytm Symulowanego wyżarzania który bez względu na wielkość n zawsze daje stabilną ilość tras i czas obliczeń. Dla algorytmu dokładnego czas obliczeń zwiększa sie horrendalnie już przy n=15 a dla algorytmu zachłannego ilość tras zależy tylko od wierzchołka na początku.
0
Cisi204 napisał(a):
Patrząc takim amatorskim okiem i chcąc porównać działanie algorytmów ze względu na jakość i efektywność. Można przypuszczać że najbardziej stabilnym algorytmem jest algorytm Symulowanego wyrażania który bez względu na wielkość n zawsze daje stabilną ilość tras i czas obliczeń. Dla algorytmu dokładnego czas obliczeń zwiększa sie horrendalnie już przy n=15.
Bo algorytm dokładny ma złożoność rzędu (n-1)!
Zauważ, że w przypadku grafu pełnego w pierwszym kroku rozpatrujesz n-1 krawędzi do przejścia, w następnym n-2... i tak dalej, zasadniczo wszystkie możliwe permutacje.
Algorytm wyżarzania działa według określonych reguł i ma pewne kryterium stopu - jesteś w stanie tym samym kontrolować, ile kroków zostanie wykonanych przed zakończeniem algorytmu. Przy czym skracając czas obliczeń (np. przyspieszając spadek temperatury) sprawiasz, że algorytm będzie mógł przeszukać mniejszy podzbiór rozwiązań, tym samym zmniejszasz szanse, że znajdzie jakieś wystarczająco dobre rozwiązanie ;)