Do przypomnienia i przygotowania samodzielnie przed zajęciami:
- Python: idea tworzenia klas i obiektów oraz korzystania z metod; for, while, if; tablice jedno- i dwuwymiarowe (dostęp do elementów tablicy, sprawdzanie ile elementów ma tablica).
- jako ćwiczenie: napisz i uruchom prosty programik, np. taki, który dla podanej listy liczb wpisuje je do tablicy, a następnie zamienia w tej tablicy dwa przypadkowe elementy ze sobą i wyświetla tablicę. Przykładowe wywołanie Zamieniacz.py:
python Zamieniacz.py 5 3 1 -5 100 -4e-2
- możesz też napisać samodzielnie kilka podobnych, bardzo prostych programików, żeby przećwiczyć i przypomnieć sobie Pythona.
Zagadnienia (pomocnicze)
- Optymalizacja kombinatoryczna (ogólnie na czym polega, bez wzorów).
- Algorytmy przeszukujące (zasada działania, pojęcia optimum globalnego i lokalnego):
- ogólna idea + różnica między algorytmami przeszukującymi, a heurystycznymi,
- algorytm przeszukiwania dokładnego (exhaustive search),
- algorytmy przeszukiwania lokalnego — poczytaj więcej o:
- lokalnym zachłannym (greedy local search), w każdym kroku wybiera pierwszego lepszego sąsiada
- lokalnym stromego spadku/wzrostu (steepest local search), wybiera najlepszego z sąsiadów
- sąsiedztwie 2-opt (szczególnym przypadku sąsiedztw k-opt) — sąsiedztwo stanowią wszystkie permutacje różniące się od bieżącej zamianą dwóch elementów.
- Problem komiwojażera a praktyka i rzeczywistość: własne eksperymenty z różnymi wartościami parametrów w OptiFacility dla małych instancji (do 10 lokalizacji+kurierów). W jednym z własnych eksperymentów ustaw parametry tak, żeby ogólniejszy problem optymalizacji, jaki rozwiązuje OptiFacility (wiele tras "dniowych", powroty do bazy) sprowadzić do klasycznego TSP (jedna cykliczna trasa obejmująca wszystkie lokalizacje).
- Porównanie: jak ludzie, a jak algorytmy rozwiązują TSP?
Materiały
- piątkowe wykłady
- Python: wszelakie kursy w internecie; Python Programming, Intro to Python for Data Science
- Wykład MetaheuristicsSummary.pdf — do "Problems with Local Search"
- Wykład LS.pdf — wzory i rozważanie konkretnych przypadków dla chętnych.
Do pobrania:
Notebook
Notebook eksperyment
Dlaczego komiwojażera ?
Komiwojażer ma do odwiedzenia pewna liczbę miast. Chciałby dotrzeć do każdego z nich i wrócić do miasta, z którego wyruszył. Znamy odległości między tymi miastami. Problemem, który chcemy rozwiązać jest sposób w jaki komiwojażer powinien zaplanować trasę podróży, aby w sumie przebył możliwie najkrótszą drogę.
Przez odległość miedzy miastami będziemy rozumieć odległość w kilometrach (choć mógłby to być np. czas trwania podróży miedzy tymi miastami, jej koszt — na przykład cena biletu lotniczego, albo ilość zużytego paliwa).
Korzystając z efektów własnej pracy na zajęciach drugich proszę wykonać następujące zadania:
Zadanie 1
- Implementacja algorytmu greedy local search
- Proszę utworzyć program, w którym:
-
-
-
- generowana jest losowa trasa (rozwiązanie) i oceniana jest jej długość
- przeszukiwane jest sąsiedztwo dla danego rozwiązania, tzn. sprawdzane są wszystkie trasy różniące się od trasy wyjściowej kolejnością odwiedzenia dwóch miast
- w przypadku, gdy pierwszy "napotkany sąsiad" jest trasą krótszą, staje się on rozwiązaniem wyjściowym (dla którego zaczynamy przeszukiwać sąsiedztwo)
- w przypadku, gdy żaden sąsiad nie jest trasą krótszą, program kończy pracę i zwraca najkrótszą znalezioną do tej pory trasę (oraz jej długość)
-
-
-
Pseudokod algorytmu:
1: kandydat $\leftarrow$ losowa trasa
.
2: dla sąsiad w Sąsiedztwo-2-opt(kandydat):
3: ….jeżeli długość(sąsiad) < długość(kandydat):
4: ……..kandydat $\leftarrow$ sąsiad
.
5: zwróć kandydat, długość(kandydat)
Zadanie 2
- Implementacja algorytmu steepest local search
- Analogicznie jak w zadaniu pierwszym, z tą różnicą, że rozwiązaniem wyjściowym staje się najkrótsza trasa z całego sąsiedztwa
Pseudokod algorytmu:
1: kandydat $\leftarrow$ losowa trasa
2: tymczasowy $\leftarrow$ kandydat
3: postęp $\leftarrow$ TRUE
.
4: dopóki postęp:
5: ….postęp $\leftarrow$ FALSE
6: ….dla sąsiad w Sąsiedztwo-2-opt(kandydat):
7: ……..jeżeli długość(sąsiad) < długość(tymczasowy):
8: …………tymczasowy $\leftarrow$ sąsiad
9: …………postęp $\leftarrow$ TRUE
10: …kandydat $\leftarrow$ tymczasowy
.
11: zwróć kandydat, długość(kandydat)
Zadanie 3
- Implementacja algorytmu exhaustive search
- Proszę utworzyć program, w którym sprawdzane są wszystkie trasy i zwracana jest trasa najkrótsza (oraz jej długość)
Pseudokod algorytmu:
1: najkrótsza $\leftarrow$ losowa trasa
.
2: dla kandydat w Zbiór-wszystkich-rozwiązań:
3: ….jeżeli długość(kandydat) < długość(najkrótsza):
4: ……..najkrótsza $\leftarrow$ kandydat
.
5: zwróć najkrótsza, długość(najkrótsza)
Przykłady systemów obrazujących algorytmy optymalizacji
- Proszę przeprowadzić proces poszukiwania optymalnego rozwiązania i zapoznać się z różnymi algorytmami optymalizacji przy pomocy programu OptiVis. Proszę obejrzeć różne, dostępne w katalogu programu, gotowe funkcje.
- Jak można modyfikować działanie algorytmów przy pomocy parametrów? Proszę znaleźć odpowiedź na pytanie: na co wpływają owe parametry?
- Proszę zapoznać się z przykładowymi algorytmami rozwiązującymi problem komiwojażera — TSP (Travelling Salesman Problem — opis w treści zajęć)
Eksperymenty z algorytmami zachłannym i stromym
Poniżej znajdują się wyniki eksperymentów z algorytmami zachłannym i stromym w trybie multi random start (kod w notebooku). Eksperymenty zostały przeprowadzone na 5 instancjach problemu TSP.