To tylko jedna z 8 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
1. Wstęp.
Celem eksperymentu było zbadanie skuteczności algorytmu symulowanego
wyŜarzania zastosowanego do rozwiązywania problemu n-komiwojaŜerów – naleŜało nkomiwojaŜerom przydzielić takie cykle, aby maksymalna z n dróg była najmniejsza.
2. Opis algorytmu.
•
•
•
•
•
Badany algorytm był oparty na losowym ruchu typu insert:
Losujemy wierzchołek grafu, oraz miejsce w uporządkowanym zbiorze wierzchołków
tworzących drogi.
Obliczamy jakie zmiany w długości dróg wprowadzi wylosowany ruch
JeŜeli nowe rozwiązanie jest lepsze to wykonaj ten ruch
W przeciwnym wypadku przyjmujemy wylosowane rozwiązanie z
prawdopodobieństwem określonym przez funkcję f(numer iteracji).
Kończymy algorytm po określonej ilości iteracji.
W moim eksperymencie sprawdziłem działanie programu dla następujących funkcji
wyznaczających prawdopodobieństwo przyjęcie gorszego rozwiązania:
• funkcja ekspotencjalnie malejąca (parametrem jest współczynnik w wykładniku)
• funkcja liniowo malejąca (parametrem jest współczynnik kierunkowy prostej)
• funkcja do pewnego momentu stała, następnie gwałtownie opadająca (parametrem jest
przy której iteracji funkcja zaczyna opadać)
Wykres 1: Stosowane podczas symulacji funkcje prawdopodobieństwa (przykładowe parametry).
KaŜda z funkcji przyjmowała wartości poprawnie określające prawdopodobieństwo,
czyli przedział [0,1]. Losowanie z prawdopodobieństwem zaimplementowałem losując liczbę
z przedziału [0,1] i sprawdzając czy jest ona większa od wartości funkcji f dla aktualnego
numeru iteracji.
3. Badanie kształtowania się rozwiązania w zaleŜności od ilości iteracji dla róŜnych
parametrów funkcji prawdopodobieństwa.
Wylosowałem po 3 róŜne instancje dla kaŜdej z funkcji określającej
prawdopodobieństwo oraz uruchomiłem 500 razy dla metodę insert() rejestrując wartość
kryterium, co 50 iteracji. Wyniki zostały zobrazowane na wykresach.
Wykresy 2,3,4: Wartość kryterium w funkcji numeru iteracji dla ekspotencjalnej funkcji
prawdopodobieństwa.
Wykresy 5,6,7: Wartość kryterium w funkcji numeru iteracji dla liniowej funkcji
prawdopodobieństwa.
Wykresy 8,9,10: Wartość kryterium w funkcji numeru iteracji dla nieliniowo opadającej
funkcji prawdopodobieństwa.
4. Badanie kształtowania się rozwiązania w zaleŜności od zastosowanej funkcji określającej
prawdopodobieństwo.
Następnie przeprowadziłem podobne badania lecz dla róŜnych funkcji
prawdopodobieństwa w których przyjąłem stałe parametry (0,1 dla eksponenty i f. liniowej
oraz 50 dla funkcji opadającej). Wyniki równieŜ zostały zobrazowane na poniŜszych
wykresach.
Wykresy 11, 12, 13: Kształtowanie się rozwiązania dla róŜnych funkcji prawdopodobieństwa
(porównanie skuteczności).
5. Porównanie algorytmu z optymalnym algorytmem rozwiązywania problemu
komiwojaŜera.
Do porównania skuteczności algorytmów zastosowałem metodę analizy
eksperymentalnej. Liczyłem średnie błędy względne 100 instancji dla ilości miast w zakresie
od 4 do 14. ZaleŜności przedstawione zostały na wykresie.
Wykres 14: ZaleŜność względnych
... zobacz całą notatkę
Komentarze użytkowników (0)