Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

.title[
# Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne)
]
.subtitle[
## Local Search (LS)
]
.author[
### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a>
]

---

# Pojęcia

- `$S$` - wszystkie możliwe rozwiązania (przestrzeń rozwiązań)
- `$x$` - jedno potencjalne rozwiązanie
- `$N(x)$` - to jest zbiór rozwiązań sąsiednich `$x$` 
<br>
--
<br>
- `$x \in S$`
- Każde rozwiązanie `$y \in N(x)$` jest nazywane rozwiązaniem sąsiednim (albo sąsiadem `$x$`)

---
# Cechy sąsiedztwa

1. Sąsiedztwo musi być ograniczone:
    - Dla każdego `$x$` istnieje co najmniej jedno rozwiązanie `$y$` różne od `$x$`
    - Sąsiedztwo nie może obejmować całej przestrzeni rozwiązań dopuszczalnych
2. Sąsiedztwo musi być homogeniczne (podobne do siebie):
    - `$y$` niewiele się różni od `$x$`
3. Każde sąsiedztwo ma równe szanse
    - Niezależnie od wyboru rozwiązania początkowego każde rozwiązanie należące do `$S$` powinno być osiągalne
 
---
class: inverse, left, bottom
# Przykłady sąsiedztw

---
# Przykłady sąsiedztw - permutacja

- k-zamiana (ang. *k-swap*, *k-opt*)
- Np. 2-zamiana z zachowaniem pozycji (*2-opt*)

```
## 1 2 3 4 5 6 7 8 9
```

```
## 1 2 8 4 5 6 7 3 9
```

`$$|N_{2P}(x)| = \frac{n(n-1)}{2}$$`

- 3-zamiana z zachowaniem pozycji (*3-opt*)
- 4-zamiana z zachowaniem pozycji (*4-opt*)
- Itd...

---
# Sąsiedztwo w TSP

- Oparte o macierz odległości
- Ocena permutacji to suma odegłości wszystkich odcinków
- Możliwe, np.:
    - Zamiana miast
    - Zamiana łuku

---
# Sąsiedztwo w TSP

.pull-left[
- 2-zamiana z zachowaniem pozycji (*2-opt*) - Zamiana miast

```
## 1 2 3 4 5 6 7 8 9
```

```
## 1 2 8 4 5 6 7 3 9
```

- 2-zamiana z zachowaniem pozycji (*2-opt*) - Zamiana (odwrócenie) łuku

```
## 1 2 3 4 5 6 7 8 9
```

```
## 1 2 8 7 6 5 4 3 9
```
]

.pull-right[
<img src="10-local-search_files/figure-html/unnamed-chunk-4-1.png" style="display: block; margin: auto;" />

]

---
# Eksploracja sąsiedztwa rozwiązania `$x$`

1. Wybierz jakieś rozwiązanie w `$S$` i je oceń - rozwiązanie bieżące
2. Wygeneruj nowe rozwiązanie i je oceń:
    - Jeżeli nowe rozwiązanie jest lepsze, uznaj je jako rozwiąznie
    bieżące
    - Jeżeli nowe rozwiązanie jest gorsze, odrzuć je
3. Powtarzaj kroki 2 i 3 dopóki można uzyskać poprawę

---
# Lokalne optimum

---
class: inverse, left, bottom
# Typy optymalizacji lokalnej

---
# Typy optymalizacji lokalnej

- **Algorytm zachłanny** (ang. *greedy*) - rozgląda się po całym sąsiedztwie i wybieria rozwiązanie, które daje jakiekolwiek polepszenie 
- **Algorytm stromy** (ang. *steepest*) - rozgląda się po całym sąsiedztwie i wybiera rozwiązanie, które daje największe polepszenie

---
class: inverse, left, bottom
# Algorytm zachłanny

---
# Algorytm zachłanny

- Algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego wyboru rozwiązania częściowego
- Zachłanny wybór oznacza taki, który rokuje najlepiej w danym momencie
- Oznacza to też, że zachłanny wybór nie musi dawać poprawnego (i optymalnego) wyniku

---
# Algorytm zachłanny - zalety

- Łatwy do zaprojektowania i zaimplementowania
- Potrafi być bardzo szybki

---
# Algorytm zachłanny - wady

- Nie istnieje ogólna metoda dowodzenia czy dla danego problemu rozwiązanie zachłanne odnajduje poprawny (i optymalny) wynik
- Może dawać wyniki o różnej jakości

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

---
# Algorytm stromy

- Algorytm, który w celu wyznaczenia rozwiązania sprawdza rozwiązania w najbliższym sąsiedztwie, a następnie wybiera to, które rokuje najlepiej 
- Oznacza to też, że stromy wybór nie musi dawać poprawnego (i optymalnego) wyniku

---
# Algorytm stromy - zalety

- Łatwy do zaprojektowania i zaimplementowania
- Potrafi być bardzo szybki

---
# Algorytm stromy - wady

- Nie istnieje ogólna metoda dowodzenia czy dla danego problemu rozwiązanie strone odnajduje poprawny (i optymalny) wynik
- Może dawać wyniki o różnej jakości

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

---
# Przykład

---
# Przykład

.lc[
Wybierz jakieś rozwiązanie (np. B2)
- Jak zadziała algorytm zachłanny i stromy?
- Jaki wpływ ma sąsiedztwo 4 lub 8?
- Jaki wpływ ma warunek `$\lt$` lub `$\le$`?
]

.rc[
<img src="10-local-search_files/figure-html/unnamed-chunk-10-1.png" style="display: block; margin: auto;" />
]

---
# Przykład

.lc[
Wybierz jakieś rozwiązanie (np. D4)
- Jak zadziała algorytm zachłanny i stromy?
- Jaki wpływ ma sąsiedztwo 4 lub 8?
- Jaki wpływ ma warunek `$\lt$` lub `$\le$`?
]

.rc[
<img src="10-local-search_files/figure-html/unnamed-chunk-11-1.png" style="display: block; margin: auto;" />
]

---
# Przykład

.lc[
Wybierz jakieś rozwiązanie (np. E2)
- Jak zadziała algorytm zachłanny i stromy?
- Jaki wpływ ma sąsiedztwo 4 lub 8?
- Jaki wpływ ma warunek `$\lt$` lub `$\le$`?
]

.rc[
<img src="10-local-search_files/figure-html/unnamed-chunk-12-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

Algorytm:

1. Wprowadź macierz odległości
2. Losowo wybierz miasto początkowe (miasto X), usuń kolumnę z tym miastem z macierzy odległości
3. Znajdź w wierszu X najbliższe miasto do miasta X (miasto Y)(przy takiej samej odległości roztrzygnij to losowo)
4. Usuń kolumnę Y z macierzy odległości
5. Sprawdź czy macierz odległości jest pusta, jeżeli tak to idź do kroku 7, jeżeli nie to do kroku 6
6. Ustal X = Y i powtórz krok 3
7. Dodaj miasto początkowe jako miasto końcowe
8. Wypisz miasta w kolejności oraz uzyskaną sumę odległości

---
# Problem komiwojażera

---
# Problem komiwojażera

```
## [1] 360
```

---
# Problem komiwojażera

```
##           A         B         C         D         E         F         G
## A 0.0000000 0.2000000 0.3162278 0.4472136 0.5099020 0.7071068 0.3162278
## B 0.2000000 0.0000000 0.5099020 0.6324555 0.5099020 0.8602325 0.4242641
## C 0.3162278 0.5099020 0.0000000 0.3162278 0.5656854 0.6324555 0.4472136
## D 0.4472136 0.6324555 0.3162278 0.0000000 0.8602325 0.3162278 0.3162278
## E 0.5099020 0.5099020 0.5656854 0.8602325 0.0000000 1.1661904 0.8246211
## F 0.7071068 0.8602325 0.6324555 0.3162278 1.1661904 0.0000000 0.4472136
## G 0.3162278 0.4242641 0.4472136 0.3162278 0.8246211 0.4472136 0.0000000
```

---
# Problem plecakowy

Założenie:

- Wybieramy przedmioty jeden po jednym

Pomysły:

1. Lepiej mieć więcej przedmiotów - sortujemy je według wagi i wybieramy najpierw najlżejsze
2. Lepiej mieć najcenniejsze przedmioty - sortujemy je według wartości i wybieramy najpierw najcenniejsze
3. Lepiej mieć przedmioty o najlepszej proporcji wartości do wagi - sortujemy je według gęstości (wartość/waga)

---
# Problem plecakowy

Algorytm zachłanny nie musi dawać optymalnego wyniku dla problemy plecakowego (0-1 problem plecakowy)

---
# Problem plecakowy

.pull-left[
Pomysły:

.pull-right[
Liczba elementów:
- `$I = 7$`

Ograniczenie (ang. *constraint*):
- `$W = 22$`

Wagi:
- `$w_1 = 7$`, `$w_2 = 8$`, `$w_3 = 4$`, `$w_4 = 10$`, `$w_5 = 4$`, `$w_6 = 6$`, `$w_7 = 4$`

Wartości:
- `$c_1 = 5$`, `$c_2 = 8$`, `$c_3 = 4$`, `$c_4 = 10$`, `$c_5 = 4$`, `$c_6 = 6$`, `$c_7 = 4$`
]

---
class: inverse, left, bottom
# Analogia turysty w górach

---
# Analogia turysty w górach

Turysta wyszedł na spacer w górach w mglisty porannek:

1. Algorytm zachłanny - turysta widzi, że teren obok się podnosi - od razu ją wybiera
2. Algorytm stromy - turysta najpierw obraca się dookoła, następnie wybiera kierunek w którym teren obok się podnosi najbardziej

- To ile metrów widzi turysta odpowiada rozmiarowi sąsiedztwa

---
class: inverse, left, bottom
# Przeliczanie kosztu

---
# Przeliczanie kosztu

Problem komiwojażera - zamiana jednej pary punktów. 
Możliwe jest:
1. Policzenie całego kosztu jeszcze raz.
2. Odjęcie od znanego kosztu zabranych odcinków oraz dodanie nowych odcinków.

Wpływ tych rozwiązań:
1. Czas liniowy - im więcej punktów, tym dłuższy jest czas wyliczania nowego kosztu.
2. Czas stały - czas wyliczania nowego kosztu jest stały, bez względu na liczbę punktów

---
# Przeliczanie kosztu

Problem przydziału kwadratowego. 
Możliwe jest:
1. Policzenie całego kosztu jeszcze raz.
2. Wyliczenie tylko kosztu zmiany rozwiązania i dodanie/odjęcie go od poprzedniego kosztu (zmiana dwóch wierszy i dwóch kolumn)
3. Stworzenie tzw. tablicy delt

Wpływ tych rozwiązań:
1. Czas kwaratowy - im większa macierz, tym kwadratowo dłuższy jest czas wyliczania nowego kosztu.
2. Czas liniowy - im większa macierz, tym dłuższy jest czas wyliczania nowego kosztu.
3. Czas prawie-stały - czas wyliczania nowego kosztu jest stały, bez względu na wielkość macierzy

---
class: inverse, left, bottom
# Zalety i wady

---
# Zalety optymalizacji lokalnej

- Są proste
- Są szybkie
- Są elastyczne
- Można je stosować dla każdego problemu optymalizacji kombinatorycznej

---
# Wady optymalizacji lokalnej

- Kończą działanie w optimum lokalnym
- Jakość rozwiązania końcowego zależy od wyboru rozwiązania startowego - zazwyczaj nie jest możliwe wcześniejsze określenie miejsca startowego o najlepszych parametrach

---
# Minimalizacja wad

- Wykonywanie algorytmu dla dużej liczby różnych rozwiązań startowych (*multi-random start*, *guided local search*)
- Wprowadzenie bardziej złożonej definicji sąsiedztwa
- Zmienianie sąsiedztwa w trakcie działania
- Ograniczone akceptowanie pogorszeń funkcji celu
- Wiele innych...

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

---
# Dodatkowe informacje

https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL