class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna
(w tym algorytmy heurystyczne) ] .subtitle[ ## Local Search (LS) ] .author[ ### Jakub Nowosad
https://jakubnowosad.com/
] --- <!-- nie wiem czy to dokładnie to --> <!-- https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL --> # 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 <!-- ok 10 min https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL --> - Oparte o macierz odległości - Ocena permutacji to suma odegłości wszystkich odcinków - Możliwe, np.: - Zamiana miast - Zamiana łuku <!-- Termin "konstrukcja sąsiedztwa" --> --- # 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ę <!-- algorytm --> <!-- min 29 --> <!-- https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL --> --- # Lokalne optimum <img src="10-local-search_files/figure-html/unnamed-chunk-5-1.png" style="display: block; margin: auto;" /> --- 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 <!--https://pl.wikipedia.org/wiki/Algorytm_zach%C5%82anny--> - **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 <!-- https://www.geeksforgeeks.org/greedy-algorithms/ --> --- # 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 <!-- - Problem feasibility needs to be "easy" --> --- 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 <!-- dodaj wartości!! --> <img src="10-local-search_files/figure-html/unnamed-chunk-9-1.png" style="display: block; margin: auto;" /> --- # Przykład <!--min40 https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL--> .lc[ Wybierz jakieś rozwiązanie (np. B2) - Jak zadziała algorytm zachłanny i stromy?<!--co jest filozoficznie lepsze; niespecjalnie. Czy któryś jest szybszy? (zatrzymują się naturalnie)jakość i czas jest podobny--> - Jaki wpływ ma sąsiedztwo 4 lub 8? - Jaki wpływ ma warunek `\(\lt\)` lub `\(\le\)`?<!--pierwszy lub ostatni; nie losowy bo nie musimy zapamiętać--> ] .rc[ <img src="10-local-search_files/figure-html/unnamed-chunk-10-1.png" style="display: block; margin: auto;" /> ] --- # Przykład <!--min40 https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL--> .lc[ Wybierz jakieś rozwiązanie (np. D4) - Jak zadziała algorytm zachłanny i stromy?<!--co jest filozoficznie lepsze; niespecjalnie. Czy któryś jest szybszy? (zatrzymują się naturalnie)jakość i czas jest podobny--> - Jaki wpływ ma sąsiedztwo 4 lub 8? - Jaki wpływ ma warunek `\(\lt\)` lub `\(\le\)`?<!--pierwszy lub ostatni; nie losowy bo nie musimy zapamiętać--> ] .rc[ <img src="10-local-search_files/figure-html/unnamed-chunk-11-1.png" style="display: block; margin: auto;" /> ] --- # Przykład <!--min40 https://www.youtube.com/watch?v=oe94AHDQap0&index=6&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL--> .lc[ Wybierz jakieś rozwiązanie (np. E2) - Jak zadziała algorytm zachłanny i stromy?<!--co jest filozoficznie lepsze; niespecjalnie. Czy któryś jest szybszy? (zatrzymują się naturalnie)jakość i czas jest podobny--> - Jaki wpływ ma sąsiedztwo 4 lub 8?<!--dużo sąsiedztwo - zabiera więcej czasu;średnio większe sąsiedztwo prowadzi do lepszych wyników--> - Jaki wpływ ma warunek `\(\lt\)` lub `\(\le\)`?<!--pierwszy lub ostatni; nie losowy bo nie musimy zapamiętać--> ] .rc[ <img src="10-local-search_files/figure-html/unnamed-chunk-12-1.png" style="display: block; margin: auto;" /> ] <!-- Przykład I --> <!-- https://pl.wikipedia.org/wiki/Problem_wydawania_reszty --> <!-- Przykład II --> <!-- https://www.youtube.com/watch?v=psN4jCs3J9c&list=PLl33p3GENNQGGW-H5pJ5afLMTVR18simL&index=10&t=0s --> <!-- TSP vs QAP --> <!-- od startu, najbliższy punkt --> --- # Problem komiwojażera <!-- https://www.researchgate.net/publication/307856959_Implementation_of_Greedy_Algorithm_in_Travel_Salesman_Problem --> 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 <img src="10-local-search_files/figure-html/unnamed-chunk-13-1.png" style="display: block; margin: auto;" /> <!-- https://stackoverflow.com/questions/27363653/find-shortest-path-from-x-y-coordinates-with-start-%E2%89%A0-end --> --- # Problem komiwojażera ``` ## [1] 360 ``` --- # Problem komiwojażera 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 ``` ## 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) <!-- https://github.com/akilahmd/Knapsackpackage/blob/master/R/brute_force_knapsack.R.R --> --- # Problem plecakowy Algorytm zachłanny nie musi dawać optymalnego wyniku dla problemy plecakowego (0-1 problem plecakowy) --- # Problem plecakowy .pull-left[ 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) ] .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 we mgle --> 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<!--wyznacznie pomocniczej struktury dodaje czas, a później 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