Detail předmětu

Evoluční algoritmy

FEKT-MEALAk. rok: 2016/2017

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

Garant předmětu

doc. Ing. Jiří Kozumplík, CSc.

Zajišťuje ústav

Ústav biomedicínského inženýrství (UBMI)

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 programovací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 upřesňuje 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ů)

Osnovy výuky

1. Optimalizace vycházející z matematické analýzy, podmínky optimality, gradient, hessián
2. Metoda nejstrmějšího sestupu, Newtonova metoda
3. Jednoduché metody: horolezecký algoritmus, zakázané prohledávání, simulované žíhání
4. Stochastické algoritmy pro hledání globálního minima, simplexová metoda
5. Evoluční algoritmy s populacemi. Binární genetické algoritmy.
6. Spojité genetické algoritmy.
7. Řízené náhodné prohledávání, evoluční strategie, diferenciální evoluce.
8. Rojové algoritmy: SOMA, rojení částic, mravenčí kolonie,
9. Algoritmy inspirované světluškami a včelami,
10. Algoritmy inspirované netopýry a vlčí smečkou.
11. Soutěžící heuristiky,testovací funkce pro ověřování optimalizačních algoritmů
12. Experimentální porovnávání evolučních algoritmů
12. Úvod do genetického programování

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 EEKR-M1 magisterský navazující

    obor M1-BEI , 2 ročník, zimní semestr, volitelný oborový

  • Program EEKR-M magisterský navazující

    obor M-BEI , 2 ročník, zimní semestr, volitelný oborový

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

    obor ET-CZV , 1 ročník, zimní semestr, volitelný oborový

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

doc. Ing. Jiří Kozumplík, CSc.
Ing. Martin Mézl, Ph.D.

Osnova

1. Optimalizace vycházející z matematické analýzy, podmínky optimality, gradient, hessián
2. Metoda nejstrmějšího sestupu, Newtonova metoda
3. Stochastické algoritmy pro hledání globálního minima, simplexová metoda
4. Evoluční algoritmy s populacemi. Binární genetické algoritmy.
5. Spojité genetické algoritmy.
6. Řízené náhodné prohledávání, evoluční strategie, rojení částic
7. Diferenciální evoluce, SOMA, mravenčí kolonie
8. Soutěžící heuristiky
9. Testovací funkce pro ověřování optimalizačních algoritmů
10. Jednoduché metody: horolezecký algoritmus, zakázané prohledávání, simulované žíhání
11. Experimentální porovnávání evolučních algoritmů
12. Úvod do genetického programování

Cvičení na počítači

13 hod., povinná

Vyučující / Lektor

Ing. Martin Mézl, Ph.D.

Osnova

1. Deterministické metody matematické optimalizace. Metoda nejstrmějšího sestupu.
2. Newtonova metoda
3. Simplexová metoda (Nelderův-Meadův algoritmus)
4. Úvod do heuristických a metaheuristických algoritmů. Binární genetický algoritmus (GA)
5. GA pro nalezení minima v 2D
6. Spojité GA. Rozdíly mezi binárními a spojitými GA
7. Aplikace GA pro registraci obrazů
8. Problém obchodního cestujícího, základní heuristické algoritmy
9. Permutační GA pro řešení problému obchodního cestujícího (TSP)
10. Metoda rojení částic (PSO), metoda mravenčích kolonií pro řešení TSP
11. Řešení projektu - „problém batohu“
12. PSO pro nalezení minima 2D funkce