class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne) ] .subtitle[ ## Przeszukiwanie losowe ] .author[ ### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a> ] --- # Przeszukiwanie losowe - Przeszukiwanie losowe (ang. *random search*) - rodzina metod optymalizacyjnych, która nie gwarantuje znalezienia optymalnego rozwiązania - Zamiast tego jej celem jest znalezienie dobrego rozwiązania w szybkim czasie --- # Algortym - Cel - minimalizacja kosztu 1. Rozpocznij od rozwiązania `\(x\)` znajdującego się w losowym miejscu przestrzeni rozwiązań 2. Wybierz nowe rozwiązanie aż do momentu aż nie zostanie osiągnięte pewne kryterium (np., liczba iteracji albo przekroczona wartość progowa) --- class: inverse, left, bottom # Przykłady --- # Problem komiwojażera <!-- http://www.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html --> Algorytm: ```r ustal liczbę kroków; nazwij ją K wybierz pierwszą trasę; nazwij ją T najlepsza_trasa <- T najlepsza_wartosc <- wartosc(T) while K > 0 stwórz nową permutację T if wartosc(T) < najlepsza wartosc najlepsza_trasa <- T najlepsza_wartosc <- wartosc(T) K <- K - 1 wyświetl najlepsza_trasa i najlepsza_wartosc ``` --- # Problem komiwojażera <img src="09-random-search_files/figure-html/unnamed-chunk-2-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 2 3 4 5 6 7 ## 1 0.0000000 0.2000000 0.3162278 0.4472136 0.5099020 0.7071068 0.3162278 ## 2 0.2000000 0.0000000 0.5099020 0.6324555 0.5099020 0.8602325 0.4242641 ## 3 0.3162278 0.5099020 0.0000000 0.3162278 0.5656854 0.6324555 0.4472136 ## 4 0.4472136 0.6324555 0.3162278 0.0000000 0.8602325 0.3162278 0.3162278 ## 5 0.5099020 0.5099020 0.5656854 0.8602325 0.0000000 1.1661904 0.8246211 ## 6 0.7071068 0.8602325 0.6324555 0.3162278 1.1661904 0.0000000 0.4472136 ## 7 0.3162278 0.4242641 0.4472136 0.3162278 0.8246211 0.4472136 0.0000000 ``` --- # Problem komiwojażera ``` ## [1] 360 ``` --- # Problem komiwojażera ``` ## [1] 2 3 4 5 6 7 ``` ``` ## [1] 2 5 3 4 7 6 ``` ``` ## [1] 3 4 2 7 6 5 ``` ``` ## [1] 3 6 4 2 7 5 ``` --- # Problem komiwojażera <!-- http://www.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html --> Algorytm: ```r ustal liczbę kroków; nazwij ją K wybierz pierwszą trasę; nazwij ją T najlepsza_trasa <- T najlepsza_wartosc <- wartosc(T) while K > 0 stwórz nową permutację T if wartosc(T) < najlepsza wartosc najlepsza_trasa <- T najlepsza_wartosc <- wartosc(T) K <- K - 1 wyświetl najlepsza_trasa i najlepsza_wartosc ``` <!-- http://www.micsymposium.org/mics_2005/papers/paper102.pdf -->