WItam, jestem nowy na forum i mam do rozwiązania problem komiwojażera wykorzystując algorytm symulowanego wyżarzania. Na wejściu mam tablicę dwuwymiarową z policzonymi odległościami pomiędzy poszczególnymi miastami (wykorzystałem formułę Haversine). Punkt początkowy trasy komiwojażera jest również punktem końcowym. Proszę o pomoc, ponieważ po zrobieniu research'u w internecie nadal nie bardzo rozumiem jak działa ten algorytm symulowanego wyżarzania.
0
0
Obawiam się, że nikt Ci tutaj tego nie wytłumaczy.Musisz pooglądać filmy, przeanalizować przykłady i samemu zaskoczyć.
Algorytm nie jest strasznie trudny ale jeśli piszesz "nadal nie bardzo rozumiem jak działa ten algorytm" to naprawdę nie wiadomo na jakim poziomie utknąłeś.
3
Sam algorytm symulowanego wyżarzania działa bardzo prosto - to taka analogia do wyżarzania jako procesu fizycznego, gdzie w wysokiej temperaturze szybciej zachodzą zmiany w strukturze materiału, niż w niższej.
Wykonujesz w iteracjach jakąś optymalizację (ja pierwszy raz trafiłem na to pojęcie przy algorytmach genetycznych - ale możemy sobie uogólnić że chodzi o dowolny problem optymalizacyjny), na przykład minimalizującą długość ścieżki w problemie komiwojażera. Optymalizacja ma "jakiś" dodatkowy parametr (coś jak temperaturę), który steruje tym jak duże zmiany będą wprowadzane przez algorytm - co do zasady w początkowych iteracjach ten parametr ma wysoką wartość, więc możliwe są bardziej radykalne zmiany - w Twoim przypadku to może być np. wybór jakiejś totalnie innej permutacji miast. Z każdą iteracją parametr maleje, aż w końcu dopuszcza tylko niewielkie zmiany - np. zamianę miejscami dwóch miast.
3
Ok, a skąd wiadomo że dana iteracja jest ostatnia?
Każdy algorytm optymalizacyjny musi mieć warunek, który określa kiedy go zatrzymać. To może być chociażby
- osiągnięcie maksymalnej liczby iteracji
- jakaś progowa wartość zmiany funkcji celu, poniżej której uznajemy że algorytm stoi w miejscu i już nic nie zyskamy na dalszych iteracjach
- dowolne inne kryterium na podstawie którego stwierdzasz, że należy zakończyć
- kombinacja powyższych
Muszę założyć jakąś minimalną "temperaturę" którą chcę osiągnąć?
To trochę bez sensu, bo zwykle "temperatura" zależy od iteracji - na dobrą sprawę wedle uznania jak, dopóki efekt końcowy będzie taki że w iteracji N + 1tej algorytm będzie chciał robić mniejsze zmiany, niż w Ntej i tyle :P
Przy stałej liczbie iteracji możesz policzyć ze swojego wzoru, jaka będzie ta minimalna temperatura - na początek możesz spróbować jakiegoś const_1 * exp(- iteracja * const_2) i się pobawić tymi const_1, const_2. Przy innym kryterium temperatura może sobie maleć tak długo, jak długo algorytm będzie uzyskiwał poprawę coraz mniejszymi zmianami i nie będzie żadnej stałej minimalnej temperatury.
1
Najlepiej szukaj po angielsku, zaoszczędzisz sobie czasu.
Hasło: "travelling salesman simulated annealing java"
Pierwszy wynik: https://www.baeldung.com/java-simulated-annealing-for-traveling-salesman