class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna
(w tym algorytmy heurystyczne) ] .subtitle[ ## Symulowane wyżarzanie ] .author[ ### Jakub Nowosad
https://jakubnowosad.com/
] --- <!-- https://en.wikipedia.org/wiki/Simulated_annealing --> # Wyżarzanie <br> <img src="images/steel_annealing.jpg" width="1253" style="display: block; margin: auto;" /> --- # 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**. <!----> <!--chaotyczny rozkład cząsteczek --> > Celem obróbki jest przybliżenie stanu materiału do warunków równowagi. Przeprowadzane jest w wyższej temperaturze niż starzenie. <!-- efekt oznacza się symetrycznością --> <!-- nadaje elastyczność --> <!-- Wyżarzanie przeprowadza się w różnych celach, w zależności od temperatury w jakiej jest prowadzone (poprawia np. własności mechaniczne i plastyczne) --> - Przeciwieństwo hartowania --- # Wyżarzanie - Co to ma wspólnego z algorytmami? <img src="images/steel_annealing.jpg" width="1253" style="display: block; margin: auto;" /> --- # 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 <!-- - 3m https://www.youtube.com/watch?v=gX-X85dCib0 --> 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 <!-- może gdzieś wspomnieć o szybkim schładzaniu --> 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 <!-- when used --> - 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) <!--wyjaśnij parametr--> --- # 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 <!-- wyjaśnij dlaczego --> <!-- min 14 https://www.youtube.com/watch?v=gX-X85dCib0 --> <!-- kilka opcji krajobrazów rozwiązań --> - 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)} $$ <!-- https://www.phy.ornl.gov/csep/mo/node32.html --> <!-- https://www.mathworks.com/matlabcentral/answers/uploaded_files/14677/B:COAP.0000044187.23143.bd.pdf --> <!-- wyliczanie rozkładu różnić rozwiązań --> <!-- http://faculty.washington.edu/aragon/pubs/annealing-pt1.pdf --> --- # 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 <!-- https://www.geeksforgeeks.org/simulated-annealing/ --> <!-- # https://codereview.stackexchange.com/a/84718/193387 --> <!-- # Initialize --> <!-- ## s stands for state --> <!-- ## f stands for function value --> <!-- ## b stands for best --> <!-- ## c stands for current --> <!-- ## n stands for neighbor --> --- class: inverse, left, bottom # Przykłady --- # Problem komiwojażera I 1) Wybierz dowolną permutację `n` punktów 2) Wykonaj permutację par <!--(jednej pary czy wszystkich?)--> - 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