Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

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

---

# 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

---
# 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  `\(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

---
# Reprezentacja rozwiązania

- Permutacja (problem komiwojażera, QAP)
- Macierz
- Drzewo
- Ciąg binarny
- Reprezentacja zmiennoprzecinkowa (np. w programowaniu nieliniowym)
- Inne...

---
# Krajobraz funkcji celu

- Minimalizacja/maksymalizacja

---
# Krajobraz funkcji celu

- Algorytm pełny

---
# Krajobraz funkcji celu

- Algorytm losowy

---
# Krajobraz funkcji celu

- Algorytm heurystyczny