Detail předmětu

Evoluční algoritmy

FEKT-FEALAk. rok: 2018/2019

Předmět je orientován na deterministické a stochastické metody optimalizace pro hledání globálních extrémů. Zaměřuje se zejména na evoluční algoritmy s populacemi, jako genetické algoritmy, řízené náhodné prohledávání, evoluční strategie, metodu rojení částic, metodu mjravenčích kolonií a další.

Jazyk výuky

čeština

Počet kreditů

5

Výsledky učení předmětu

Absolvent předmětu je schopen:
Realizovat jednoduché analytické optimalizační metody (metodu nejstrmějšího sestupu a Newtonovu metodu)
Realizovat simplexovou metodu pro hledání globálního extrému
Vysvětlit podstatu stochastických optimalizačních metod s populacemi
Vysvětlit podstatu binárních a spojitých genetických algoritmů a jejich základních operací

Prerekvizity

Jsou požadovány znalosti na úrovni bakalářského studia, předpokládáme znalosti ze základů numerické matematiky. V laboratorní výuce se předpokládá znalost programového prostředí Matlab.

Plánované vzdělávací činnosti a výukové metody

Metody vyučování zahrnují přednášky a cvičení na počítači. Předmět využívá e-learning. Student odevzdává jeden samostatný projekt.

Způsob a kritéria hodnocení

Podmínky pro úspěšné ukončení předmětu stanoví každoročně aktualizovaná vyhláška garanta předmětu.
- až 30 bodů za řešení zadaných úkolů v laboratorním cvičení (pro postup ke zkoušce je nutný zisk minimálně 15 bodů)
- až 70 bodů za písemnou zkoušku (z písemné zkoušky je nutné získat minimálně 35 bodů)
- 30 points can be obtained for activity in the laboratory exercises, consisting in solving tasks (for the procedure for the examination must be obtained at least 15 points)
- 70 points can be obtained for the written exam (the written examination is necessary to obtain at least 35 points)

Osnovy výuky

1. Úvod do matematické optimalizace - gradient, hessian
2. Metoda nejstrmějšího sestupu Newtonova metoda, Fibonacciho optimalizace
3. Simplexová metoda, horolezecký algoritmus, simulované žíhání (SA), řízené náhodné prohledávání (CRS)
4. DE (diferenciální evoluce), ES (evoluční strategie), soutěžní heuristiky
5. Úvod ke genetickým algoritmům (GA), GA s binárním vyjádřením hodnot
6. GA se spojitým vyjádřením hodnot, problém obchodního cestujícího (TSP) s GA
7. Genetické programování
8. Rojové algoritmy: mravenčí kolonie (AC), TSP s AC a SA, heuristické metody
9. Rojové algoritmy: rojení částic (PSO), SOMA
10. Algoritmy inspirované chováním světlušek, netopýrů, kukaček
11. Algoritmy inspirované chováním vlků, včel
12. Optimalizace v MATLABu, ověřování a porovnávání algoritmů – praktické ukázky

Učební cíle

Získání znalostí o deterministických a stochastických metodách optimalizace. Seznámení se s evolučními algoritmy s populacemi pro hledání globálních extrémů vícerozměrných funkcí. Seznámení se s úvodem do genetického programování.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu (viz Rozvrhové jednotky).
V zásadě:
- povinné počítačové cvičení (zmeškaná laboratorní cvičení musí být řádně omluvená a lze je nahradit po domluvě s vyučujícím)
- nepovinná přednáška

Základní literatura

Tvrdík, J.: Evoluční algoritmy. Skripta, Přírodovědecká fakulta Ostravské univerzity, 2004 (CS)

Doporučená literatura

Hynek, J.: Genetické algoritmy a genetické programování. Grada Publishing, 2008 (CS)

Zařazení předmětu ve studijních plánech

  • Program BTBIO-F magisterský navazující

    obor F-BTB , 2. ročník, zimní semestr, povinný

  • Program EEKR-CZV celoživotní vzdělávání (není studentem)

    obor ET-CZV , 1. ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Osnova

1. Úvod do matematické optimalizace - gradient, hessian
2. Metoda nejstrmějšího sestupu Newtonova metoda, Fibonacciho optimalizace
3. Simplexová metoda, horolezecký algoritmus, simulované žíhání (SA), řízené náhodné prohledávání (CRS)
4. DE (diferenciální evoluce), ES (evoluční strategie), soutěžní heuristiky
5. Úvod ke genetickým algoritmům (GA), GA s binárním vyjádřením hodnot
6. GA se spojitým vyjádřením hodnot, problém obchodního cestujícího (TSP) s GA
7. Genetické programování
8. Rojové algoritmy: mravenčí kolonie (AC), TSP s AC a SA, heuristické metody
9. Rojové algoritmy: rojení částic (PSO), SOMA
10. Algoritmy inspirované chováním světlušek, netopýrů, kukaček
11. Algoritmy inspirované chováním vlků, včel
12. Optimalizace v MATLABu, ověřování a porovnávání algoritmů – praktické ukázky

Cvičení na počítači

26 hod., povinná

Vyučující / Lektor

Osnova

1. Úvod do předmětu, náhodné a úplné prohledávání
2. Analytické řešení, metoda nejstrmějšího sestupu
3. Newtonova metoda
4. Simplexová metoda
5. Binární GA 1 - 1D
6. Binární GA 2 - 2D
7. Spojité GA
8. TSP - úvod, heuristiky, SA
9. TSP - permutační GA
10. TSP – ACO
11. Světlušky
12. Optimalizace Matlab
13. Samostatná práce, zápočtový test