# Algorytmy heurystyczne - dokumentacja końcowa
## Skład zespołu
* Rafał Kulus (300249)
* Kamil Przybyła (300254)
## Treść zadania `#2`
Jesteś kapitanem statku *USS Voyager* i próbujesz powrócić na Ziemię z *Kwadrantu Delta*, ale przed wyruszeniem w drogę z planety `P` musisz zgromadzić odpowiednią ilość deuteru. Możesz odwiedzić $n$ stacji kosmicznych przy czym odwiedzając stację kosmiczną $s_i$ zyskujesz $d_i$ jednostek deuteru. Podróż między stacjami kosmicznymi $s_i$ i $s_k$ kosztuje Cię $k_{ij} > 0$ jednostek deuteru.
Zaprojektuj eksperyment, w którym wykorzystasz algorytmy heurystyczne w celu znalezienia trasy cyklicznej między planetą `P`, a stacjami kosmicznymi, która zapewni Ci maksymalny stosunek zysków do strat.
## Założenia
* Istnieje połączenie między planetą `P` a każdą stacją kosmiczną.
* Deuter znajdujący się na planecie `P` jest pozyskiwany tylko raz -- przed wylotem i stanowi początkowe paliwo, którego jest zawsze na tyle dużo, że można dostać się na dowolną stację kosmiczną.
* Istnieją pary stacji, między którymi nie istnieje droga.
* Statek nie może wyruszyć w drogę, jeśli miałoby mu zabraknąć po drodze paliwa.
* Statek musi powrócić na planetę `P` -- nie może zakończyć swojej podróży na stacji kosmicznej.
* Koszty podróży między stacjami lub między stacją a planetą są symetryczne, tj. $k_{ij} = k_{ji}$.
## Technologie realizacji projektu
Projekt zrealizowano w języku *Python 3.8* z wykorzystaniem biblioteki *matplotlib* do przygotowania wykresów.
## Założenia implementacyjne
* **BF** - Brute force (DFS)
* **SA** - Simulated annealing
* **HC** - Hill climbing
* **TS** - Tabu search
Wszystkie obliczenia wykonano z seedem `ALHE`. Można go zmienić poprzez modyfikację zawartości pliku `./seed.txt`.
Wszystkie problemy zostały wygenerowane z następującymi parametrami generatora (które zostały wytłumaczone w dalszej części dokumentacji), chyba że zaznaczono inaczej:
* `DIM = 3`
* `DEUTER_STD_DEV = 0.5`
* `CONN_COEF = 0.7`
Stanami w przestrzeni przeszukiwań każdego z algorytmów są sekwencje podzbioru liczb, oznaczających odwiedzane stacje kosmiczne, np. "143" oznacza, że z planety P w pierwszej kolejności powinna zostać odwiedzona stacja 1., następnie 4., a na koniec 3., po czym należy powrócić na planetę P.
Dopuszczamy, aby w czasie działania wszystkich algorytmów (za wyjątkiem algorytmu wspinaczkowego) stan aktywny był stanem niedopuszczalnym, to znaczy możliwe jest, aby w czasie swojego działania algorytm wykorzystał stan, który reprezentuje ścieżkę niemożliwą do zrealizowania ze względu na niewystarczającą ilość deuteru. Innymi słowy, nie gwarantujemy, że procedura generująca stany sąsiadujące zwróci tylko stany dopuszczalne. Gwarantowane jest jedynie, że wszystkie krawędzie występujące na ścieżce będą istnieć. Mimo to, w wyniku swojego działania, algorytm zawsze zwróci wartość prawidłową. Zdecydowaliśmy się na takie rozwiązanie, ponieważ sprawdzenie czy dany stan jest dopuszczalny jest tak samo wymagające obliczeniowo co wyznaczenie wartości funkcji celu, a zwykle zakłada się, że liczba ewaluacji tej funkcji powinna być jak najmniejsza.
Generowanie losowego sąsiada zaimplementowano naiwnie: budowana jest pełna lista sąsiadów, a z niej losowany jest jeden stan. Nie udało nam się wymyślić procedury losowania sąsiadów, która umożliwiałaby wybranie każdego z możliwych do wygenerowania sąsiadów z równym prawdopodobieństwem.
Funkcja ewaluacji stanu zwraca $-1$ dla stanów reprezentujących ścieżki, w których pojawiają się nieistniejące w rzeczywistości krawędzie. Stany niedopuszczalne ze względu na niewystarczającą ilość deuteru do przeprowadzenia lotu są oceniane tak samo, jak stany prawidłowe. Zakładaliśmy, że dla takich stanów stosunek zdobytego deuteru do zużytego będzie mniejszy niż $1$. Zaletą przypisywania stanom niedopuszczalnym różnych wartości funkcji celu jest to, że algorytmy są w stanie stwierdzić, który stan jest "mniej niedopuszczalny" i łatwiejsze może być opuszczenie obszaru przestrzeni przeszukiwań, zawierającego takie stany.
## Główne składowe projektu
### Generator
```
usage: python ./generator.py problem_size [connection_coef] [deuter_std_dev]
```
Generator dostaje na wejściu parametr `problem_size` oznaczający liczbę stacji kosmicznych. Następnie dla każdej z nich generuje losową ilość deuteru opisaną rozkładem `distance(coords) * max(0.0, random.gauss(1, deuter_std_dev))` i losowe położenie w przestrzeni `DIM`-wymiarowej, której środkiem jest planeta `P`, a jej wymiary zależą od wielkości problemu. Dzięki przyjętemu rozkładowi, im dalej stacje są położone od planety `P`, tym mają średnio więcej deuteru. Zapobiega to sytuacjom, w których statek leci tylko do jednej pobliskiej stacji z dużą ilością deuteru i od razu wraca na planetę. Na koniec zostają wyznaczone połączenia między stacjami. Ilość połączeń zależy od `connection_coef`, gdzie:
* 0 = każda stacja jest połączona tylko z planetą
* 1 = każda stacja jest połączona z planetą i każdą inną stacją
Koszty podróży nie są generowane, ponieważ są wprost proporcjonalne do odległości. Dane są zapisywane do katalogu `./problems`.
### Solver
```
Usage: python ./solver.py dir_with_data MAX_CPUS MODE
MODE:
0 - brute
1 - heuristics
2 - heuristics + brute
```
Skrypt rozwiązuje wszystkie problemy, które znajdują się w `dir_with_data`, a następnie (w zależności od trybu) generuje stosowne wykresy (które zapisuje w `./plots`). W trybie `1` zostają porównane ze sobą wszystkie 3 algorytmy heurystyczne opisane w dalszej części dokumentacji, zaś tryb `2` pozwala na porównanie wyników osiąganych przez algorytmy heurystyczne z wynikiem, będącym globalnym maksimum.
### Metoda brute force
```
Usage: python ./alg_brute_force.py path_to_data
```
Wykorzystuje DFS w celu znalezienia najlepszego rozwiązania danego problemu.
### Algorytm wspinaczkowy
```
Usage: python ./alg_hill_climbing.py path_to_data MAX_ITERS
```
Algorytm zaczyna działanie w wylosowanym, dopuszczalnym stanie. W każdej iteracji działania rozpatrywane są stany sąsiadujące, to znaczy stany różniące się od obecnego jedną transpozycją stacji w sekwencji, albo dodaniem lub usunięciem stacji z dowolnego miejsca w sekwencji (o ile jest to możliwe). Dla każdego stanu wyznaczona zostaje wartość funkcji celu, czyli stosunek zysku paliwa do strat, po czym następuje przejście do stanu maksymalizującego tą wartość. Jeśli stan jest niedopuszczalny (ilość deuteru jest niewystarczająca do wykonania lotu), wartość funkcji celu zostaje ustawiona na inaczej nieosiągalnie niską wartość. Algorytm kończy działanie w momencie, w którym żaden z sąsiadujących stanów nie gwarantuje wyższej ewaluacji funkcji celu lub został osiągnięty limit iteracji.
### Symulowane wyżarzanie
```
Usage: python ./alg_simulated_annealing.py path_to_data MAX_ITERS [START_TEMP] [TEMP_DECAY]
```
Podobnie jak w przypadku algorytmu wspinaczkowego, algorytm zaczyna działanie od wylosowanego stanu początkowego oraz w każdej iteracji rozpatrywany jest losowy stan z jego otoczenia. Dodatkowo, śledzona jest wartość zwana temperaturą, malejąca z każdą iteracją algorytmu, która ma wpływ na prawdopodobieństwo akceptacji rozwiązania gorszego niż obecne. W początkowych iteracjach algorytmu -- kiedy temperatura jest duża -- algorytm chętniej eksploruje przestrzeń przeszukiwań, a w późniejszych etapach preferuje pozostanie w stanie gwarantującym wyższą wartość funkcji celu.
### Przeszukiwanie tabu
```
Usage: python ./alg_tabu_search.py path_to_data MAX_ITERS [TABU_SIZE]
```
Cechą wyróżniającą ten algorytm jest fakt utrzymywania listy stanów tabu, do których algorytm nie może przejść. Dopuszczalne jest zatem przejście do stanu pogarszającego jakość rozwiązania. Zapobiega to wpadnięciu algorytmu w optimum lokalne. Poza tym faktem jego działanie jest podobne do algorytmów wspomnianych wcześniej, zatem nie będziemy go szerzej opisywać.
## Wykonane eksperymenty numeryczne
### Małe problemy
Problemy o rozmiarach od 8 do 16 znajdujące się w `./problems/small` z następującymi parametrami (wymagają ustawienia w `./solver.py` w funkcjach `run_xx`).
```
HC:
MAX_ITERS = 100
SA:
MAX_ITERS = 1000
TEMP = 100
DECAY = 0.95
TS:
MAX_ITERS = 50
TABU_SIZE = 35
```
Jak widać, czas potrzebny do rozwiązania problemu metodą przeszukiwania wyczerpującego rośnie wykładniczo. Można to uzasadniać faktem, iż liczba możliwych ścieżek jest proporcjonalna do liczby permutacji, którą można przybliżać za pomocą $\sqrt{2\pi n}(\frac{n}{e})^n$.
Dla dużej liczby przypadków algorytm *tabu search* był w stanie znaleźć maksimum globalne, podczas gdy algorytm wspinaczkowy czasem zatrzymywał się w optimum lokalnym. Tymczasem algorytm symulowanego wyżarzania kompletnie sobie nie radził.
### Zachowanie algorytmu SA dla n = 50 i różnych wartości stygnięcia
Jak widać po dużych wariacjach funkcji celu, algorytm eksplorował przestrzeń przeszukiwań bardziej, kiedy temperatura była wysoka. Na ostatnich dwóch wykresach można zauważyć, że wartość stygnięcia była na tyle wysoka, że temperatura nie zdążyła odpowiednio szybko zmaleć, co poskutkowało tym, że algorytm nie zdążył się ustabilizować.
### Większe problemy
Problemy o rozmiarach od 20 do 75 (co 5) znajdujące się w `./problems/to_solve` z następującymi parametrami (wymagają ustawienia w `./solver.py` w funkcjach `run_xx`).
```
HC:
MAX_ITERS = 100
SA:
MAX_ITERS = 10000
TEMP = 100
DECAY = 0.998
TS:
MAX_ITERS = 100
TABU_SIZE = 35
```
Na powyższych wykresach można dostrzec pewne podobieństwo do wykresów dla małych problemów.
## Wnioski
1. Algorytm symulowanego wyżarzania działa zwykle najgorzej ze wszystkich badanych algorytmów. Podejrzewamy, iż jest tak dlatego, że rozwiązania dopuszczalne są na tyle rzadkie w przestrzeni przeszukiwań, że algorytm ma trudność odnaleźć takie rozwiązanie spośród generowanych sąsiadów stanu niedopuszczalnego, zaakceptowanego na etapie eksploracyjnym - kiedy temperatura jest duża. Dodatkowo, algorytm ten działa bardzo wolno, co jest zapewne wynikiem niewydajnej procedury generowania losowego stanu sąsiadującego.
2. Wyszukiwanie z tabu wydaje się być najlepszą metodą spośród badanych. Dla małych problemów udawało jej się odnajdywać optima globalne, a dla dużych skutecznie wychodziła z optimów lokalnych, często osiągając dużo lepszą wartość funkcji celu niż algorytm wspinaczkowy.
3. Metoda wyszukiwania zupełnego przestaje być opłacalna już dla problemów o rozmiarze 16.
Sign in with Wallet
Connect another wallet