class: center, middle, inverse, title-slide .title[ # Optymalizacja dyskretna
(w tym algorytmy heurystyczne) ] .subtitle[ ## Podstawy optymalizacji ] .author[ ### Jakub Nowosad
https://jakubnowosad.com/
] --- # Algorytmy optymalizacji 1. Dokładne 2. Heurystyczne - Specjalizowane - stworzone dla konkretnego problemu - Uniwersalne - tzw. metaheurystyki 3. Aproksymacyjne 4. [Inne](https://www.wired.com/2010/01/slime-mold-grows-network-just-like-tokyo-rail-system/) --- class: inverse, left, bottom # Algorytmy dokładne --- # Algorytmy dokładne - Przeszukiwanie wyczerpujące (ang. *exhaustive*, *brute force*) - Programowanie matematyczne - Podziel i ogranicz (ang. *branch and bound*) - Programowanie dynamiczne --- class: inverse, left, bottom # Algorytmy heurystyczne --- # Algorytmy heurystyczne Heurystyka: - To metoda służąca do znajdowania rozwiązań dla problemów dla których klasyczne metody są zbyt wolne (lub klasyczne metody nie są w stanie osiągnąć optymalnego wyniku) - Heurystyki nie gwarantują znalezienia rozwiązania optymalnego - Heurystyki są też używane do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. - Heurystyki są wykorzystywane, między innymi, w informatyce, optymalizacji matematycznej, sztucznej inteligencji <!-- --- --> <!-- # Heurystyka --> <!-- https://en.wikipedia.org/wiki/Heuristic_(computer_science) --> <!-- - Optymalność --> <!-- - Kompletność --> <!-- - Dokładność i precyzja --> <!-- - Czas wykonania --> --- # Algorytmy heurystyczne - Algortymy, które nie gwarantują znalezienia optymalnego rozwiązania - Ich celem jest za to znalezienie w rozsądnym czasie rozwiązania, które jest blisko optimum --- # Algorytmy heurystyczne Algorytmy specjalizowane: - Z reguły krótki czas obliczeń - Zwykle dobre wyniki - Wymagają znacznej wiedzy eksperckiej - Stworzone specjalnie dla konkretnego problemu --- # Algorytmy heurystyczne Metaheurystyki: - Wiele nich było inspirowanych naturalnymi procesami z fizyki, chemii czy biologii - https://en.wikipedia.org/wiki/List_of_metaphor-based_metaheuristics - Często umożliwiają uzyskanie wyników blisko optimum - Nie zawsze wymagają wiedzy eksperckiej --- # Algorytmy heurystyczne - Specjalizowane - stworzone dla konkretnego problemu - Uniwersalne - tzw. metaheurystyki * Przeszukiwanie losowe (ang. *random search*) * Przeszukiwanie lokalne, np. algorytm zachłanny, algorytm stromy, symulowane wyżarzanie, przeszukiwanie tabu * Przeszukiwanie populacyjne, np. algorytm grupy cząstek, algorytm ewolucyjny * Mrówkowe * Hybrydowe * Inne... --- class: inverse, left, bottom # Algorytmy aproksymacyjne --- # Algorytmy aproksymacyjne - Algorytmy aproksymacyjne służą do znajdowania przybliżonych rozwiązań - Różnią się one od algorytmów heurystycznych, że zwracają informację o koszcie określonego rozwiązania w stosunku do rozwiązania optymalnego --- class: inverse, left, bottom # Algorytmy optymalizacji --- # Algorytmy optymalizacji 1. Dokładne 2. Heurystyczne - Specjalizowane - stworzone dla konkretnego problemu - Uniwersalne - tzw. metaheurystyki: 3. Aproksymacyjne --- class: inverse, left, bottom # Formalizacja --- # Składowe problemu optymalizacyjnego Problem optymalizacyjny składa się z: 1. Kryterium oceny rozwiązania <!--i funkcji celu `\(z = f(x)\)`--> `\(z = f(x)\)` (funkcja oceniająca rozwiązanie) 2. Ograniczeń (ang. **constraints**) - niektóre rozwiązania nie są możliwe 3. Rozwiązania (reprezentacja rozwiązania): `\(x =[x_1, x_2, ..., x_n]\)` --- # Podstawowe pytania - Czym jest zbiór rozwiązań? - Jak duży jest zbiór rozwiązań? - Jak jest on ograniczony? - Jakie są kryteria oceny rozwiązań? - Jak takie kryteria policzyć automatycznie? --- # Formalizacja Problemy optymalizacyjne można formalizować jako model matematyczny albo problem programistyczny -- - Kryterium oceny rozwiązania może dotyczyć np. maksymalizacji lub minimalizacji danej wartości - Funkcja służąca do rozwiązania problemu jest określana często jako `\(f(x)\)` - Rozwiązanie problemu podlega pewnym ograniczeniom (np. `\(g(x) > 0\)`) - Rozwiązanie jest opisane często jako ciąg liczb <!-- --- --> <!-- # Przedstawienie problemu dla różnych algorytmów (API problemu optymalizacyjnego) --> --- # Reprezentacja rozwiązania - Permutacja (problem komiwojażera, QAP) - Macierz - Drzewo - Ciąg binarny<!--np. SAT--> - Reprezentacja zmiennoprzecinkowa (np. w programowaniu nieliniowym) - Inne... <!-- --- --> <!-- # ... --> <!-- - Reprezentacja rozwiązania --> <!-- - Metoda zmieniania rozwiązania lub generowania kolejnego --> <!-- - Funkcja oceniająca rozwiązanie --> --- # Krajobraz funkcji celu - Minimalizacja/maksymalizacja <img src="04-foundations_files/figure-html/unnamed-chunk-1-1.png" style="display: block; margin: auto;" /> <!-- https://cran.r-project.org/web/packages/plot3D/vignettes/plot3D.pdf --> --- # Krajobraz funkcji celu - Algorytm pełny <img src="04-foundations_files/figure-html/unnamed-chunk-2-1.png" style="display: block; margin: auto;" /> --- # Krajobraz funkcji celu - Algorytm losowy <img src="04-foundations_files/figure-html/unnamed-chunk-3-1.png" style="display: block; margin: auto;" /> --- # Krajobraz funkcji celu - Algorytm heurystyczny <img src="04-foundations_files/figure-html/unnamed-chunk-4-1.png" style="display: block; margin: auto;" />