Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

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

---

# Wyżarzanie

<br>

---
# Wyżarzanie

https://pl.wikipedia.org/wiki/Wy%C5%BCarzanie

> Wyżarzanie – jedna z operacji obróbki cieplnej metali polegająca na **nagrzaniu materiału do określonej temperatury, wytrzymaniu przy tej temperaturze oraz następnym powolnym studzeniu**.

> Celem obróbki jest przybliżenie stanu materiału do warunków równowagi.
Przeprowadzane jest w wyższej temperaturze niż starzenie.

- Przeciwieństwo hartowania

---
# Wyżarzanie

- Co to ma wspólnego z algorytmami?

---
# Symulowane wyżarzanie - inspiracja

- Algorytm Metropolisa-Hastingsa - algorytm statystycznego symulowania (Monte Carlo) zmian ciała stałego w gorącej kąpieli aż do stanu termicznej równowagi

Stan ciała stałego `$i$` i energia `$E_i$`:
1. Symulacje (losowe generowanie) kolejnego stanu ciała `$j$` i określenie jego energii `$E_j$`
2. Jeżeli `$E_j - E_i \le 0$` to `$j$` jest nowym stanem bieżącym, w przeciwnym razie stan `$j$` jest akceptowany z pewnym prawdopodobieństwem

`$$exp( \frac{E_i - E_j}{k_B T} )$$`

, gdzie `$k_B$` to stałą Boltzmanna, a `$T$` to temperatura kąpieli

---
# Symulowane wyżarzanie - inspiracja

- Przejście z problemu fizycznego na problem optymalizacyjny
- Symulowane wyżarzanie to zastosowanie algorytmu Metropolisa do optymalizacji

Stan ciała stałego `$i$` (**rozwiązanie**) i energia `$E_i$` (**koszt**):
1. Symulacje (losowe generowanie) kolejnego stanu ciała `$j$` (**nowe rozwiązanie**) i określenie jego energii `$E_j$` (**nowy koszt**)
2. Jeżeli `$E_j - E_i \le 0$` to `$j$` jest nowym stanem bieżącym, w przeciwnym razie stan `$j$` jest akceptowany z pewnym prawdopodobieństwem

`$$exp( \frac{E_i - E_j}{k_B T} )$$`

, gdzie `$k_B$` to stałą Boltzmanna, a `$T$` to temperatura kąpieli (**parametr kontrolny**)

---
# Symulowane wyżarzanie

- Algorytm heurystyczny służacy do określania przybliżonego optimum dla danego problemu

- Symulowanie wyżarzanie działa iteracyjnie, krok po kroku zbliżając się do optymalnego rozwiązania
- W tym algorytmie każdy kolejny krok (przybliżenie rozwiązania) może przyjmować dowolny element przestrzeni potencjalnych rozwiązań
- Wybór elementu z przestrzeni potencjalnych rozwiązań zależy od:
    1. Różnicy między starym rozwiązaniem a propozycją nowego rozwiązania
    2. Parametru (tzw. temperatury)

---
# Różnica

- Jeżeli propozycja nowego rozwiązania jest lepsza od starego to zostaje ona uznana jako nowe rozwiązanie
- Jeżli propozycja nowego rozwiązania jest gorsza od starego to może zostać ono uznane jako nowe rozwiązanie z pewnym prawdopodobieństwem
Prawdopodobiestwo wyboru gorszej propozycji jest tym mniejsze, im różnica między proponowanym a starym rozwiązaniem jest większa.
Celem tego jest ograniczenie odchodzenia od wcześniejszego lepszego rozwiązania

---
# Parametr

- Parametr (tzw. temperatura) steruje wyborem kolejnych przybliżeń, gdy propozycja nowego rozwiązania jest gorsza od starego
- Jeżeli wartość parametru jest wysoka to prawdopodobieństwo wyboru gorszego rozwiązania jest duże
- Jeżeli wartość parametru jest niska to prawdopodobieństwo wyboru gorszego rozwiązania jest małe
- W trakcie działania algorytmu, wartość parametru jest stale obniżana - w efekcie szansa wyboru gorszego rozwiązania maleje
- Ostatnim etapem jest stabilizacja rozwiązania, gdzie żadne zmiany nie są akceptowane

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

---
# Algorytm

1. Wybierz losowe rozwiązanie startowe i. 
Ustal paramter T = T_max
2. Wylicz f(i), czyli koszt rozwiązania i.
3. Wyznacz propozycję nowego rozwiązania j (np. losowy sąsiad).
4. Wylicz f(j), czyli koszt rozwiązania j.
5. Zaakceptuj nowe rozwiązanie, jeżeli obniża one całkowity koszt. Jeżeli jednak ta zmiana podwyższa całkowity koszt to nowe rozwiązanie może być przyjęte z pewnym prawdopodobieństwem.
6. Zmniejsz wartość parametru T.
7. Zakończ algorytm lub wróć do kroku 3.
    
---
# Prawdopodobieństwo

- Kryterium akceptacji

$$
P_T\\{akceptacja\,j\\} = 
`\begin{cases}
1  & \text{jeżeli f(j)} \le \text{f(i)}\\ 
exp(\frac{f(i) - f(j)}{T}) & \text{jeżeli f(j)} \gt \text{f(i)}
\end{cases}`
$$

- Gdzie:
    - i to stare rozwiązanie
    - j to proponowane rozwiązanie
    - f(i) i f(j) to koszty
    - T to parametr (tzw. temperatura)

---
# Wpływ parametru T

- Kryterium akceptacji

$$
P_T\\{akceptacja\,j\\} = 
`\begin{cases}
1  & \text{jeżeli f(j)} \le \text{f(i)}\\ 
exp(\frac{f(i) - f(j)}{T}) & \text{jeżeli f(j)} \gt \text{f(i)}
\end{cases}`
$$

```r
delta = 5
parametr_t = seq(100, 0, by = -2)
exp(-delta/parametr_t)
```

```
##  [1] 0.9512294 0.9502593 0.9492498 0.9481984 0.9471026 0.9459595 0.9447658
##  [8] 0.9435183 0.9422131 0.9408462 0.9394131 0.9379088 0.9363280 0.9346646
## [15] 0.9329120 0.9310628 0.9291088 0.9270409 0.9248488 0.9225210 0.9200444
## [22] 0.9174044 0.9145842 0.9115648 0.9083243 0.9048374 0.9010751 0.8970034
## [29] 0.8925825 0.8877655 0.8824969 0.8767101 0.8703247 0.8632432 0.8553453
## [36] 0.8464817 0.8364643 0.8250530 0.8119363 0.7967035 0.7788008 0.7574651
## [43] 0.7316156 0.6996725 0.6592406 0.6065307 0.5352614 0.4345982 0.2865048
## [50] 0.0820850 0.0000000
```

---
# Parametr T

- Dla parametru T należy określić skończoną sekwencję jego wartości, czyli podać:
    - Początkową wartość parametru T
    - Funkcję zmniejszania się wartości parametru T
    - Końcową wartość parametru T

---
# Parametr T

- Wartość początkowa parametru T powinna być wystarczająco wysoka by zapewnić akceptację niemal wszyskich przejść
- Czyli początkowe prawdopodobieństwo akceptacji powinno być bliskie 1

- Wartość początkowa parametru T zależy od postawionego problemu
- Można np. przyjąć jakiś wstępną wartość prawdopodobieństwa P (np. 0,98) a dla losowej próby wyliczyć średnią różnicę pomiędzy `$f(i) - f(j)$` ( `$\Delta f$` )

$$
T_o = - \frac{\Delta f}{ln(P)}
$$

---
# Parametr T

- Schodkowy schemat chłodzenia
- W praktyce schodek jest ustalany proporcjonalnie do średniego rozmiaru sąsiedztwa

---
# Parametr T

- Algorytm kończy działanie, gdy bieżące rozwiązanie nie zmienia się dla kilku kolejnych kroków

---
# Symulowane wyżarzanie

- Nie gwarantuje tego, że zostanie przy najlepszym rozwiązaniu

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

---
# Problem komiwojażera I

1) Wybierz dowolną permutację `n` punktów

2) Wykonaj permutację par

- Zaakceptuj permutację, jeżeli ta zmiana obniża całkowitą długość trasy do przebycia
- Jeżeli jednak ta zmiana wydłuża całkowitą długość trasy do przebycia to permutacja może zostać uznana jako nowe rozwiązanie z pewnym prawdopodobieństwem

$$
P_T\\{akceptacja\,j\\} = exp(\frac{f(i) - f(j)}{T})
$$

3) Zmniejsz wartość parametru T

4) Zakończ algorytm lub wróć do kroku 2

---
# Problem komiwojażera II

https://toddwschneider.com/posts/traveling-salesman-with-simulated-annealing-r-and-shiny/

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

---
# Dodatkowe informacje

- https://en.wikipedia.org/wiki/Simulated_annealing
- http://faculty.washington.edu/aragon/pubs/annealing-pt1.pdf
- https://pdfs.semanticscholar.org/22ea/d55c99d537754ee377c284319d1f0ce4cdd1.pdf
- http://iswiki.if.uj.edu.pl/iswiki/images/2/20/AiSD_22._Symulowane_wy%C5%BCarzanie_(problem_komiwoja%C5%BCera).pdf
- https://www.youtube.com/watch?v=gX-X85dCib0
- https://codereview.stackexchange.com/a/84718/193387
- https://jameshfisher.com/2019/05/28/what-is-simulated-annealing/
- https://stackoverflow.com/questions/12934213/how-to-find-out-geometric-median
- http://blog.schochastics.net/post/rdew-valley-optimizing-farming-with-r/
- https://edepot.wur.nl/333538