Nature-Inspired Algorithms

Celem wykładu jest zapoznanie studentów z problematyką optymalizacji kombinatorycznej oraz przedstawienie algorytmów inspirowanych mechanizmami Natury umożliwiających rozwiązywanie tych problemów. Szczególna uwaga będzie poświęcona algorytmom ewolucyjnym, w tym algorytmom genetycznym. Studenci poznają również metodologię automatów komórkowych jak też inne współczesne metaheurystyki, w szczególności takie jak symulowane wyżarzanie, algorytmy mrówkowe, roje cząsteczek, uogólniona ekstremalna optymalizacja oraz sztuczne sieci immunologiczne.

1. Wprowadzenie: motywacje, problemy optymalizacji funkcji i optymalizacji

kombinatorycznej. Algorytmy dokładne, aproksymacyjne,metaheurystyki.

2. Klasyczny algorytm genetyczny (AG): kodowanie i operatory genetyczne.

Zastosowanie AG do optymalizacji funkcji.

3. Współpraca i wspołzawodnictwo w Dylemacie Więźnia: gra 2-osobowa i n-

osobowa. Zastosowanie AG do ewolucji strategii gry.

4. Automaty komórkowe (AK) i automaty uczące się (AU).

5. Strategie ewolucyjne, algorytmy mrówkowe.

6. Teorie ewolucji: Lamarcka, Darwina, Baldwina, teoria punktowych

równowag. Gatunki, nisze, koewolucja.

7. Kolokwium 1 (max. ocena: 30p./100p.). Zastosowania AK i AU: w

kryptografii, klasyfikacji danych, rekonstrukcji obrazów.

8. AG – dlaczego one działają. Twierdzenie o schematach, twierdzenie „no

free lunch”. Inne modele teoretyczne.

9. Algorytmy zachłanne, symulowane wyżarzanie, metoda tabu search.

Wybrane zastosowania.

10. Warianty sekwencyjnych AG, równoległe AG. Zastosowania AG do

optymalizacji kombinatorycznej.

11. Programowanie ewolucyjne, programowanie genetyczne, uczące się

systemy klasyfikujące.

12. Algorytmy koewolucyjne: koewolucyjny algorytm Paredisa, algorytmy

CCGA oraz LCGA.

13. Sztuczne systemy immunologiczne. Zastosowanie do detekcji anomalii i

intruzów w sieciach komputerowych.

14. Algorytm roju cząsteczek i GEO, hyperheurystyki, optymalizacja

wielokryterialna.

15. Prezentacje przez grupy studenckie artykułów poświęconych algorytmom

inspirowanym naturą (max. ocena: 10p./100p.).

Literatura podstawowa

1 Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT1996.

2 El-Ghazali Talbi, Metaheuristics: From Design to Implementation, Wiley 2009.

Literatura uzupełniająca

1 Materiały z konferencji GECCO, CEC, PPSN, ACRI

2 D.Corne, M.Dorigo, F.Glover, New Ideas in Optimization, McGraw Hill, 1999.

3 L.Nunes de Castro, F.J. von Zuben, Recent Developments in Biologically Inspired Computing, Idea Group, 2005.

- zna i rozumie teoretyczne podstawy informatyki oraz biologiczne paradygmaty

będące inspiracją algorytmów inspirowanych naturą,

- zna i rozumie modele matematyczne opisu zjawisk, w tym zjawisk o charakterze

probabilistycznym będących podstawą algorytmów inspirowanych naturą,

- zna i rozumie podstawowe algorytmy inspirowane naturą,

- zna i rozumie metody obliczeniowe wykorzystujące algorytmy inspirowane naturą

służące do rozwiązywania współczesnych problemów nauki i technologii.

Szacunkowy nakład pracy

- uczestnictwo w zajęciach: 30

- przygotowanie do zajęć: 12

- przygotowanie do weryfikacji: 12

- konsultacje z prowadzącym: 1

Dla wszystkich efektów przyjmuje się następujące kryteria oceny we wszystkich formach weryfikacji:

- osiągnięty w pełni (bez uchwytnych niedociągnięć): 5

- osiągnięty niemal w pełni i nie są spełnione kryteria przyznania wyższej

oceny: 4,5

- osiągnięty w znacznym stopniu i nie są spełnione kryteria przyznania wyższej

oceny: 4

- osiągnięty w znacznym stopniu – z wyraźną przewagą pozytywów – i nie są

spełnione kryteria przyznania wyższej oceny: 3,5

- osiągnięty dla większości przypadków objętych weryfikacją i nie są spełnione

kryteria przyznania wyższej oceny: 3

- nie został osiągnięty dla większości przypadków objętych weryfikacją: 2

Ocena końcowa x jest wyznaczana na podstawie wartości

st(w)= 5, jeśli 4,5 < w; st(w)= 4,5, jeśli 4,25 < w <= 4,5; st(w)= 4, jeśli 3,75 < w <= 4,25; st(w)= 3,5, jeśli 3,25 < w <= 3,75; st(w)= 3, jeśli 2,75 < w <= 3,25; st(w)= 2, jeśli w <= 2,75

oraz na bazie podanej niżej reguły:

- jeśli każda z ocen końcowych za zajęcia powiązane jest pozytywna i ich średnia wynosi y, to x wyznacza się ze wzoru x=st(z), gdzie z jest średnią ważoną ocen z przeprowadzonych weryfikacji, w których wagi ocen z egzaminów wynoszą 2, a wagi ocen z innych form weryfikacji są równe 1