Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

# Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne)
## Przeszukiwanie tabu
### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a>

---

# Przeszukiwanie lokalne

Problem:

- Akceptacja ruchów niepolepszających 
- Może to skutkować powstawaniem cykli
--

- **Pomysł - lista "tabu"** - powoduje to czasem stworzenie za wielu zakazanych ruchów
--

- **Pomysł 2 - algorytm przeszukiwania "tabu"** - akceptowanie atrakcyjnych ruchów zakazanych (poziom aspiracji)

---
# Przeszukiwanie lokalne

- Przeszukiwanie "tabu" jest bliżej koncepcyjnie do algorytmu stromego
- Symulowane wyżarzanie jest bliżej koncepcyjnie do algorytmu zachłannego

---
class: inverse, left, bottom
# Lista "tabu"

---
# Tworzenie listy "tabu"

- Główna idea - wykorzystanie pamięci
- Nie wykonuje ruchu w miejsce, w którym już się było
--

- Problem - lista wpisów będzie rosła z każdym krokiem - co powoduje liniowe spowalnianie algorytmu

--
- Obejście - pamiętanie tylko n-liczby ostatnich miejsc

- Dwie możliwości:
    1. zapamiętywanie rozwiązań
    2. zapamiętywanie ruchów (zmian)

---
# Tworzenie listy "tabu"

- Musimy zapamiętywać najlepsze rozwiązanie
- Warto sprawdzić ile będzie wynosiła funkcja celu (sprawdzamy czy zakazany ruch jest wyższy niż najlepsze rozwiązanie)
- "Algorytm niestrudzonego turysty" - sam nie kończy swojego działania

---
class: inverse, left, bottom
# Kryteria aspiracji

---
# Kryteria aspiracji

Określenie kiedy restrykcje "tabu" można pominąć:

1. Usunięcie restrykcji "tabu", gdy ruch "tabu" da rozwiązanie lepsze od znalezionego do tej pory
2. Aspiracja domniemana - jeżeli wszystkie ruchy są "tabu" to wybierany jest ruch najmniej "tabu"
3. Aspiracja według kryterium: 
    - forma globalna - ruch "tabu" jest akceptowany jeżeli `\(c(x') \lt bestcost\)`
    - forma regionalna - przestrzeń jest dzielona na regiony `\(R\)` - ruch "tabu" jest akceptowany jeżeli `\(c(x') \lt bestcost(R)\)`

---
class: inverse, left, bottom
# Algorytm

---
# Algorytm

(Sean, 2013)

```r
 1: l <- oczekiwana maksymalna długość listy tabu
 2: n <- liczba innych rozwiązań do sprawdzenia
 3: S <- wstępne rozwiązanie
 4: Best <- S
 5: L <- {} lista tabu o maksymalnej długości l
 6: Dodaj S do L
 7: repeat
 8:     if Długość(L) > l wtedy
 9:         Usuń najstarszy element z L
10:     R <- Modyfikuj(S)
11:     for n - 1 razy zrób
12:         W <- Modyfikuj(S)
13:         if W nie należy do L i (Jakość(W) > Jakość(R) lub R należy do L) wtedy
14:             R <- W
15:     if R nie należy do L wtedy
16:         S <- R
17:         Dodaj R into L
18:     if Jakość(S) > Jakość(Best) wtedy
19:         Best <- S
20: until Best jest najlepszym rozwiązaniem lub do pewnego czasu
21: return Best
```

---
class: inverse, left, bottom
# Dodatkowa idea

---
# Dodatkowa idea - zbiór `\(V\)`

- Założenie - dobry (nie najlepszy) ruch, który nie został wykonany w bieżącej iteracji będzie ciągle dobry w kilku następnych
- Idea - tworzenie "listy" kandydatów - zbioru `\(V\)`
- Zaleta - nie jest konieczne przeglądanie całego sąsiedztwa w każdej iteracji (najbardziej wymagający proces)
- Wybór kandydatów?

---
# Wybór kandydatów - strategia I

- Przeszukiwanie sąsiedztwa aż do znalezienia sąsiada lepszego o pewną wartość progową ("poziom aspiracji")
- Liczba kandydatów rośnie aż do osiągnięcia wartości progowej
- Zakres liczby sąsiadów - Min `\(\le\)` liczba sprawdzonych sąsiadów `\(\le\)` Max
- Poziom aspiracji może być zmienny w trakcie poszukiwania (zależeć od historii poszukiwania)
- Ta strategia zwraca jednego lub więcej najlepszych znalezionych sąsiadów
- Ma ona aż trzy parametry - Min, Max, Aspiracja

---
# Wybór kandydatów - strategia II

- Tworzenie tzw. "master list"
- Polega to na sprawdzeniu wszystkich (lub większości) ruchów a następnie wyboru `\(k\)` najlepszych (gdzie `\(k\)` jest parametrem do ustalenia)
- W kolejnych iteracjach wybierany jest najlepszy ruch ze zbioru `\(k\)` ruchów, aż do momentu gdy jakość ruchu spadnie poniżej danego progu (lub zostanie osiągnięta pewna liczba iteracji)
- Dwa parametry - `\(k\)` i Próg

---
class: inverse, left, bottom
# Przykłady

---
# Problem komiwojażera I

1. **Reprezentacja rozwiązania:** ABCDEFA
2. **Wstępne rozwiązanie:** np. najbliższy sąsiad
3. **Sąsiedztwo:** zamiana miast
4. **Kryteria aspiracji:** wybór rozwiązania z listy "tabu"
5. **Dywersyfikacja:** nie chcemy wpaść w lokalne optimum

---
# Problem komiwojażera II

Sha’ban, R. Z., & Alkallak, I. N. (2008). Tabu Search Method for Solving the Traveling salesman Problem. AL-Rafidain Journal of Computer Sciences and Mathematics, 5(2), 141-153.

---
class: inverse, left, bottom
# Unifikacja algorytmów optymalizacji

---
# Unifikacja algorytmów optymalizacji

- Intensyfikacja (ang. *exploitation*) - skupiamy się na lokalnym otoczeniu
- Dywersyfikacja (ang. *exploration*) - szukamy dalekich rozwiązań (*"the grass is always greener on the other side"*)

---
# Unifikacja algorytmów optymalizacji

Intensyfikacja:

- Przeszukiwanie lokalne, np. algorytm zachłanny, algorytm stromy

Dywersyfikacja:

- Przeszukiwanie losowe

Pomiędzy:

- Symulowane wyżarzanie (zależy od temperatury)
- "Tabu" (trochę bliżej intensyfikacji) - zależy od długości listy kandydatów - im dłuższa lista tym bliżej intensyfikacji

---
class: inverse, left, bottom
# Dodatkowe informacje

---
# Dodatkowe informacje

- http://www.cleveralgorithms.com/nature-inspired/stochastic/tabu_search.html
- Sean, L., 2013, Essentials of Metaheuristics, Lulu, second edition, https://cs.gmu.edu/~sean/book/metaheuristics/