Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

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

---

# Optymalizacja

- Jak najlepiej wykorzystywać pewne zasoby?
- To sposób znalezienia dobrych, ale nie zawsze najlepszych rozwiązań
- Optymalizacja stosowana jest do trudnych problemów (NP-trudne)
- Uniwersalność - metody optymalizacyjne zazwyczaj nie wymagają bycia ekspertem w danej dziedzinie

---
# Problem optymalizacyjny

- Problemy optymalizacyjne są wszędzie
- Zazwyczaj dotyczą one podejmowania pewnych decyzji
- Celem rozwiązania problemu optymalizacyjnego jest znaczące polepszenie, czy to pewnego zasobu (czas, pieniądz) czy też poprawa jakości

---
# Optymalizacja a wspomaganie decyzji

- Optymalizacja - bardzo wiele możliwości
- Wspomaganie decyzji - mało możliwości, ale jak je oceniać, jakie są interakcje między kryteriami, etc.

---
# Zastosowania

.pull-left[
- Logistyka - układanie trasy przejazdu
- Energetyka - dbanie o zgodność zapotrzebowania i produkcji energii
- Zarządzanie kryzysowe - planowanie rozłożenia i działania służb naprawczych
- Sport - układanie harmonogramów gier
]

.pull-right[
- Ekonomia
- Biologia molekularna
- Robotyka
- Grafika komputerowa
- Medycyna
- Telekomunikacja
- Sieci komputerowe
- Bezpieczeństwo
- Wiele innych...
]

---
# Terminy

- Problem
- Instancja problemu - konkretne dane liczbowe opisujące problem
- Przestrzeń rozwiązań  - zbiór rozwiązań wraz z relacjami pomiędzy poszczególnymi rozwiązaniam. Niektóre rozwiązania są od siebie bliżej, inne dalej
- Kryterium oceny - sposób oceny jakości danego rozwiązania.
Możliwe jest posiadanie więcej niż jednego kryterium (problemy wielokryterialne)
- Funkcja celu - funkcja oceniająca rozwiązanie

---
# Terminy

- Problem - **np., problem komiwojażera**
- Instancja problemu - konkretne dane liczbowe opisujące problem - **np., odległości między miastami, itd.**
- Przestrzeń rozwiązań  - zbiór rozwiązań wraz z relacjami pomiędzy poszczególnymi rozwiązaniami.
Niektóre rozwiązania są od siebie bliżej, inne dalej - **np., rózne trasy**
- Kryterium oceny - sposób oceny jakości danego rozwiązania - **np., trasa ma być najkrótsza**. 
Możliwe jest posiadanie więcej niż jednego kryterium (problemy wielokryterialne)
- Funkcja celu - funkcja oceniająca rozwiązanie

---
# Co oznacza "trudny" problem?

1. **Problem jest bardzo złożony** - nie można zastosować prostego modelu

--
2. **Funkcja oceny jest obarczona dużą niepewnością** (np. objazdy, roboty drogowe, etc. w problemie komiwojażera)

--
3. **Znalezienia dopuszczalnego rozwiązania nie jest łatwe** (mocno ograniczona liczba rozwiązań, np. plan zajęć)

--
4. **Bardzo duża liczba możliwych rozwiązań** - przeszukanie całej przestrzeni rozwiązań jest bardzo czasochłonne lub nierealne (NP-trudność)

---
# 1. Problem jest bardzo złożony

Schemat działania:
1. Problem
2. Model
3. Rozwiązanie

---
# 1. Problem jest bardzo złożony

Schemat działania:
1. Problem
2. Model
3. Rozwiązanie

Często jednak problemy rzeczywiste nie są analogiczne do istniejących modeli.
Możliwe podejścia:

- Uproszczenie problemu, aby pasował do istniejącego modelu
- Wykorzystanie nietradycyjnego podejścia

---
# 2. Niepewność oceny

---
# 3. Mało dopuszczalnych rozwiązań

---
# 4. Duża liczba rozwiązań

- Czasem możliwa jest redukcja przestrzeni

Przykładowo:
- Problem ustalania kolejności składania samochodów na taśmie produkcyjnej 
- Możliwa liczba kombinacji `\(n!\)`, np., dla `\(n=5\)` mamy 120 kombinacji, a dla `\(n=50\)` jest już  30414093201713018969967457666435945132957882063457991132016803840 kombinacji
- Malowanie samochodów

---
class: inverse, left, bottom
# Dodatkowe źródła informacji

---
# Dodatkowe źródła informacji

Książki:

- Sean, L., 2013, Essentials of Metaheuristics, Lulu, second edition, https://cs.gmu.edu/~sean/book/metaheuristics/
- Talbi, E. G. 2009, Metaheuristics: from design to implementation, John Wiley & Sons.
- Michalewicz, Z., & Fogel, D. B., 2013, How to solve it: modern heuristics, Springer Science & Business Media.
- Michalewicz, Z., 2003, Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wydawnictwa Naukowo-Techniczne.
- Thomas, C., Charles, L., Ronald, R., & Clifford, S., 2012, Wprowadzenie do Algorytmów. Wydawnictwo Naukowe PWN.
- Cook, W. J., 2011, In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press.

Strona www:

- https://www.cs.put.poznan.pl/mkomosinski/site/?q=to

Kurs online:

- https://www.coursera.org/learn/discrete-optimization