Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

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

---

# Algorytmy ewolucyjne

- Przeszukiwanie lokalne, np. algorytm zachłanny, algorytm stromy, symulowane wyżarzanie, przeszukiwanie tabu mają za cel znalezienie lokalnego optimum
- Powoduje to, że do niektórych problemów te algorytmy nie są wystarczające
- W takich sytuacjach przydatne mogą być algorytmy ewolucyjne - inspirowane procesami ewolucyjnymi
- https://www.youtube.com/watch?v=plVk4NVIUh8

---
# Algorytmy ewolucyjne

- Algorytmy ewolucyjne różnią się od poprzednich, że dają w efekcie działania zbiór rozwiązań

- Rozwiązania mogą się krzyżować
--

- Algorytmy ewolucyjne mają też swoje wady, w tym np.:
    - większą złożoność niż algorytmy przeszukiwania lokalnego
    - są wolniejsze
    - mogą wymagać większych zasobów

---
class: inverse, left, bottom
# Typy algorytmów ewolucyjnych

---
# Typy algorytmów ewolucyjnych

- **Programowanie genetyczne** (ang. *genetic programming*)
- **Strategie ewolucyjne** (ang. *evolution strategies*) - wykorzytywane do optymalizacji numerycznej (osobnik jest wektorem liczb)
- **Algorytmy genetyczne** (ang. *genetic algorithms*) - opierają się o 0/1
- **Systemy klasifikujące** (ang. *classifier systems*)
- **Programowanie ewolucyjne** (ang. *evolutionary programming*)

---
class: inverse, left, bottom
# Terminy

---
# Terminy

- **Genotyp** - struktura danych - jak reprezentujemy rozwiązanie, np. w problemie komiwojażera jest to permutacja (wektor liczb)

--

- **Fenotyp** - znaczenie lub interpretacja tego rozwiązania - (w biologii: eskpresja cech zakodowanych w genach, np. wygląd), np. w problemie komiwojażera jest to cykliczna trasa

--

- **Populacja** - w optymalizacji - zbiór rozwiązań
--

- **Selekcja** - lepsze rozwiązania dostają wiecej kopii (przy stałej wielkości populacji lepsze rozwiązania zaczynają dominować)
--

- **Zmiana** - oparta o:
    - Mutację (ang. *mutation*)
    - Krzyżowanie (ang. *recombination*, *crossover*)

- **Dopasowanie** (ang. *fitness*) - funkcja celu - sprawdzenie jakości

---
# Genotyp a Fenotyp

**Genotyp**:
- reprezentacja struktury danych
- zmieniamy rozwiązanie - zmieniamy genotyp
 
**Fenotyp**:
- znaczenie lub interpretacja tego rozwiązania
- chcemy ocenić rozwiązanie - oceniamy fenotyp

---
class: inverse, left, bottom
# Działanie algorytmu ewolucyjnego

---
# Działanie algorytmu ewolucyjnego

Cykl:

1. **Selekcja** - rozmnożenie lepszych rozwiązań
2. **Zmiana** - stwórz nowe rozwiązania
3. **Dopasowanie** - oceń jakości rozwiązań (fenotyp)

---
# Operatory genetyczne

Rola:

- **Mutacja** (ang. *mutation*):
    - Utrzymuje różnorodność - dba o to, aby jakieś drobne (np. losowe) zmiany się pojawiały
    - Jest to odpowiednik sąsiedztwa
- **Krzyżowanie** (ang. *recombination*, *crossover*):
    - Konstruuje nowe rozwiązanie poprzez łączenie cech dwóch lub więcej rekombinowanych rozwiązań
    - Odziedziczenie wspólnej informacji - należy zidentyfikować wspólne elementy oby rodziców i przenieść je do dziecka, a reszta cech - swoboda (losowanie, inny wybór)
    - Trudniejsze do implementacji niż mutacja...

---
# Mutacja

- Mutacja odbywa się z pewnym prawdopodobieństwem - `\(P_m:[0.001..0.1]\)`
- Zazwyczaj jest to minimalna zmiana
- Np. dla reprezentacji binarnej

```
## Przed mutacją:  1 1 0 0 0
```

```
## Po mutacji:     1 1 0 1 0
```

---
# Krzyżowanie

- Postulat - wynik krzyżowania musi być nie dalej od żadnego z rodziców niż rodzice od siebie
- Krzyżowanie odbywa się z pewnym prawdopodobieństwem `\(P_c: [0.6..1.0]\)`
- Krzyżowanie jest wybierane losowo
- Różne metody krzyżowania:
    - średnia
    - liniowa
    - wielopunktowa

---
# Krzyżowanie

- Krzyżowanie jednopunktowe (ang. *one-point crossover*), np. dla reprezentacji binarnej

```
## Rodzic A: 1110|0    Dziecko 1: 1110 0
```

```
## Rodzic B: 1000|1    Dziecko 2: 1000 0
```

- Krzyżowanie dwupunktowe (ang. *two-point crossover*), np. dla reprezentacji binarnej

```
## Rodzic A: 11|01|1    Dziecko 1: 11 00 0
```

```
## Rodzic B: 10|00|1    Dziecko 2: 10 01 1
```

---
class: inverse, left, bottom
# Architektury algorytmów ewolucyjnych

---
# Architektury algorytmów ewolucyjnych

.pull-left[
- **Pokoleniowa** (ang. *generational*) - najbardziej popularne podejście - są tworzone nowe pokolenia.
Algorytm selekcji wybiera wiele razy, następuje mutacja/krzyżowanie, a potem ocena na wielu nowych osobnikach
]

.pull-right[
- **Inkrementacyjna** (stanu stałego) (ang. *incremental* (*steady-state*)) - nie tworzone są nowe pokolenia.
Algorytm selekcji jest używany raz, następuje mutacja/krzyżowanie, a potem ocena.
Następnie nowy osobnik wraca do populacji kosztem jakiegoś innego osobnika (selekcja negatywna)
]

---
class: inverse, left, bottom
# Algorytmy selekcji

---
# Algorytmy selekcji

Wiele różnych możliwych sposobów, wśród nich:
- **Selekcja ruletkowa** (ang. *roulette wheel selection*)
- **Selekcja turniejowa** (ang. *tournament selection*)
- **Model wyspowy** (ang. *island model*)

---
# Selekcja ruletkowa

- Dla każdego osobnika wyliczane jest jego dopasowanie
- Na podstawie dopasowania wyliczane jest prawdopodobieństwo selekcji
- Osobniki z lepszym dopasowaniem mają większą szansę na selekcję

---
# Selekcja turniejowa

- Potrzebujemy wielkość turnieju: najmniejsza wielkość to `\(k=2\)`, a największa to cała liczba osobników
- Wybieramy losowo uczestników turnieju
- Wybieramy lepsze rozwiązanie

---
# Model wyspowy

- Dzielimy populację na subpopulacje (wyspy)
- Wymieniamy część osobników pomiędzy wyspami (migracja)
- Algorytm, który łatwo zrównoleglić

---
class: inverse, left, bottom
# Cechy algorytmów ewolucyjnych

---
# Cechy algorytmów ewolucyjnych

Zalety:

- Bardziej uodpornione na wpadanie w lokalne optima
- Nie są zależne od punktu startowego
- Poszukiwanie zaczyna się od wielu punktów

Wady:

- Czas obliczeń
- Są niedokładne

---
class: inverse, left, bottom
# Przykłady

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

1) Generowanie początkowych rozwiązań:

- Losowe permutacje

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

2) Selekcja ruletkowa:

- Dla każdej trasy (osobnika) wyliczane jest jej dopasowanie (odwrotność odległości)
- Na podstawie dopasowania wyliczane jest prawdopodobieństwo selekcji
- Trasy z lepszym dopasowaniem mają większą szansę na selekcję

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

3) Krzyżowanie

```
//Classical Crossover Operator 
[0, 6, 2, 7, | 1, 4, 3, 5] //Parent 1
[2, 1, 7, 0, | 6, 5, 4, 3] //Parent 2

[0, 6, 2, 7, | 6, 5, 4, 3] //Offspring 1
[2, 1, 7, 0, | 1, 4, 3, 5] //Offspring 2

//Order 1 Crossover Operator
[0, 6, 1, 7, 2, 4, 3, 5] //Parent 1
[2, 1, 7, 0, 6, 5, 4, 3] //Parent 2

[, , 1, 7, 2, 4, , ] //Offspring 1
[, , 7, 0, 6, 5, , ] //Offspring 2

```

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

3) Krzyżowanie

```
//Classical Crossover Operator 
[0, 6, 2, 7, | 1, 4, 3, 5] //Parent 1
[2, 1, 7, 0, | 6, 5, 4, 3] //Parent 2

[0, 6, 2, 7, | 6, 5, 4, 3] //Offspring 1
[2, 1, 7, 0, | 1, 4, 3, 5] //Offspring 2

//Order 1 Crossover Operator
[0, 6, 1, 7, 2, 4, 3, 5] //Parent 1
[2, 1, 7, 0, 6, 5, 4, 3] //Parent 2

[0, 6, 1, 7, 2, 4, 5, 3] //Offspring 1
[1, 2, 7, 0, 6, 5, 4, 3] //Offspring 2

```

Idea:

- Wybieramy losowy fragement od jednego rodzica
- Brakujące elementy dodajemy używając odpowiednich pozostających lokalizacji od drugiego rodzica (w kolejności)

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

4) Mutacja

```
[0, 6, 2, 7, 1, 4, 3, 5] --> [0, 4, 2, 7, 1, 6, 3, 5]
```

---
# Problem komiwojażera I

- https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1

.lc[
Porównanie architektur:

- Steady-State Approach with Roulette Wheel Selection (SS-RW)
- Steady-State Approach with Tournament Selection (SS-T)
- Generational Approach with Roulette Wheel Selection (G-RW)
- Generational Approach with Tournament Selection (G-T)
]

.rc[
<img src="images/ga-tsp2.png" width="100%" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera II

- Implementacja w Pythonie - https://towardsdatascience.com/evolution-of-a-salesman-a-complete-genetic-algorithm-tutorial-for-python-6fe5d2b3ca35

---
# Problem plecakowy

.pull-left[
1. Start - generowanie początkowego zbioru rozwiązań
2. Ocena każdego rozwiązania
3. Stworzenie nowej populacji (kroki 4-6)
4. Selekcja - wybranie pary najlepszych "rodziców"
5. Krzyżowanie - krzyżowanie "rodziców" do stworzenia "dziecka"
6. Mutacja - mutowanie z pewnym prawdopodobieństwem
7. Akceptacja - umieszczenie nowych "dzieci" w populacji (zbiorze rozwiązań)
8. Zamień - użyj nowej populacji do kolejnego uruchomienia algorytmu
9. Sprawdź - czy warunek jakości jest spełniony, wtedy przerwij
10. Jeżeli nie - wróć do kroku 2
]

.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\)`
]

---
# Problem plecakowy

.pull-left[
1) Start - generowanie początkowego zbioru rozwiązań

a. 0101010

b. 1100100

c. 0100011

]

.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\)`
]

---
# Problem plecakowy

.pull-left[
2) Ocena każdego rozwiązania

a. 0101010: wartość 19. waga 24

b. 1100100: wartość 20, waga 19

c. 0100011: wartość 21, waga 18

]

.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\)`
]

---
# Problem plecakowy

.pull-left[
4) Selekcja - wybranie pary najlepszych "rodziców"

~~a. 0101010: wartość 19. waga 24~~

**b. 1100100: wartość 20, waga 19**

**c. 0100011: wartość 21, waga 18**

]

.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\)`
]

---
# Problem plecakowy

.pull-left[
5) Krzyżowanie - krzyżowanie "rodziców" do stworzenia "dziecka"

Rodzice:

- Rodzic  A: 110|0100
- Rodzic  B: 010|0011

Dzieci:

- Dziecko A: 1100011
- Dziecko B: 0100100

]

.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\)`
]

---
# Problem plecakowy

.pull-left[
6) Mutacja - mutowanie z pewnym prawdopodobieństwem

Przed mutowaniem:

- Dziecko A: 1100011
- Dziecko B: 0100100

Po mutowaniu:

- Dziecko A: 1100011
- Dziecko B: 010010**1**

]

.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\)`
]

---
# Problem plecakowy

.pull-left[
7) Akceptacja - umieszczenie nowych "dzieci" w populacji (zbiorze rozwiązań)

8) Zamień - użyj nowej populacji do kolejnego uruchomienia algorytmu

9) Sprawdź - czy warunek jakości jest spełniony (np. próg jakości, albo number populacji), wtedy przerwij

10) Jeżeli nie - wróć do kroku 2
]

.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
# Dodatkowe informacje

---
# Dodatkowe informacje

- https://www.youtube.com/watch?v=N3tRFayqVtk
- https://blog.floydhub.com/introduction-to-genetic-algorithms/
- https://ysosirius.github.io/windfarmGA/
- https://www.youtube.com/watch?v=qv6UVOQ0F44&feature=emb_logo
- https://blog.datascienceheroes.com/feature-selection-using-genetic-algorithms-in-r/
- http://gradientdescending.com/evolve-new-colour-palettes-in-r-with-evopalette
- https://github.com/anopara/genetic-drawing
- https://www.rforecology.com/post/intro-to-evolutionary-algorithms-with-r-for-beginners-from-scratch-part-1/
- https://blog.ephorie.de/evolution-works
- http://csc.ucdavis.edu/~evca/Papers/evca-review.pdf (https://www.youtube.com/watch?v=KhmdGoHN1u8&list=PLF0b3ThojznRyDQlitfUTzXEXwLNNE-mI&index=92)