Detail předmětu

Aplikované evoluční algoritmy

FIT-EVOAk. rok: 2018/2019

Přehled principů stochastického prohledávání stavového prostoru - metody Monte Carlo, evoluční algoritmy. Podrobné seznámení s vybranými technikami: Metropolisův algoritmus, simulované žíhání, úlohy statistické fyziky. Přehled principů základních variant evolučních algoritmů (EA): evoluční programování (EP), evoluční strategie (ES), genetické algoritmy (GA), genetické programování (GP), diferenciální evoluce (DE). Pokročilé evoluční techniky: EA s pravděpodobnostními modely, multikriteriální optimalizace, paralelní a distribuované EA. Metody optimalizace založené na společenstvích: částicové roje, mravenčí kolonie. Aplikace EA v inženýrských úlohách a umělé inteligenci.

Garant předmětu

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

Schopnost formulovat řešený problém tak, aby mohl být řešen prostředky evolučních algoritmů. Znalost postupů analýzy a návrhu základních typů evolučních algoritmů.

Prerekvizity

Nejsou žádné prerekvizity.

Doporučená nebo povinná literatura

  • Luke, S.: Essentials of Metaheuristics. Lulu, 2015, ISBN 978-1-300-54962-8
  • Jansen, T.: Analyzing Evolutionary Algorithms. Springer-Verlag, Berlin Heidelberg, 2013, ISBN 978-3-642-17338-7
  • Kvasnička, V., Pospíchal, J., Tiňo, P.: Evolučné algoritmy. Vydavatelství STU Bratislava, Bratislava, 2000, ISBN 80-227-1377-5
  • Oplatková, Z., Ošmera, P., Šeda, M., Včelař, F., Zelinka, I.: Evoluční výpočetní techniky - principy a aplikace. BEN - technická literatura, Praha, 2008, ISBN 80-7300-218-3

  • Brabazon, A., O'Neill, M., McGarraghy, S.: Natural Computing Algorithms. Springer-Verlag Berlin Heidelberg, 2015, ISBN 978-3-662-43630-1
  • Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing, 2nd ed. Springer-Verlag Berlin Heidelberg, 2015, ISBN 978-3-662-44873-1
  • Jansen, T.: Analyzing Evolutionary Algorithms. Springer-Verlag, Berlin Heidelberg, 2013, ISBN 978-3-642-17338-7
  • Talbi, E.-G.: Metaheuristics: From Design to Implementation. Wiley, Hoboken, New Jersey, 2009, ISBN 978-0-470-27858-1
  • Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford, 1996, ISBN 978-0195099713

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Zápočet není ustanoven.

Jazyk výuky

čeština

Osnovy výuky

    Osnova přednášek:
    1. Úvod, základní pojmy, principy stochastického prohledávání prostoru.
    2. Metoda Monte Carlo a její varianty (Metropolisův algoritmus, simulované žíhání).
    3. Základní evoluční techniky (evoluční programování, evoluční strategie).
    4. Genetické algoritmy (řídicí parametry, genetické operátory).
    5. Genetické programování a symbolická regrese.
    6. Případová studie z oblasti návrhu algoritmů a elektronických obvodů.
    7. Diferenciální evoluce (optimalizace v reálné doméně, aplikace z inženýrské praxe).
    8. Evoluční algoritmy s pravděpodobnostními modely.
    9. Algoritmy vícekriteriální optimalizace (základní techniky, aplikace z inženýrské praxe).
    10. Pokročilé techniky vícekriteriální optimalizace.
    11. Paralelní evoluční techniky a koevoluční algoritmy.
    12. Evoluční vývin a gramatická evoluce (základní modely, aplikace v umělé inteligenci).
    13. Algoritmy založené na společenstvích (částicové systémy, mravenčí algoritmy).

    Osnova laboratorních cvičení:
    • Základní koncepty evolučního počítání, typické problémy, řešení technické úlohy pomocí varianty Metropolisova algoritmu.
    • Evoluční algoritmy v inženýrské praxi, optimalizace elektronických obvodů pomocí genetického algoritmu.
    • Evoluční návrh pomocí genetického programování.
    • Diferenciální evoluce, algoritmy s pravděpodobnostními modely.
    • Optimalizace pomocí algoritmů založených na společenstvích.
    • Řešení vybrané úlohy z oblasti statistické mechaniky.

    Osnova ostatní - projekty, práce:
    Zpracování tématu dle vlastní volby formou:
    • implementace aplikace z oblasti evolučních výpočtů nebo
    • studia vybraného odborného článku, prezentace hlavních myšlenek.
    Po dohodě lze projekty, řešené současně v jiných kurzech (např. BIN), uznat též pro kurz EVO, pokud tématicky zapadají do oblasti evolučních technik.

Cíl

Získat přehled o moderních optimalizačních technikách a evolučních algoritmech pro řešení složitých, vesměs NP úplných problémů. Naučit se řešit vybrané složité úlohy z inženýrské praxe pomocí evolučních technik.

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

Hodnocená počítačová cvičení, individuální projekt.

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

  • Program IT-MGR-2 magisterský navazující

    obor MBS , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MBI , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
    obor MIS , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MIN , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MMI , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MMM , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MGM , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MPV , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
    obor MSK , libovolný ročník, letní semestr, 5 kreditů, volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Osnova

  1. Úvod, základní pojmy, principy stochastického prohledávání prostoru.
  2. Metoda Monte Carlo a její varianty (Metropolisův algoritmus, simulované žíhání).
  3. Základní evoluční techniky (evoluční programování, evoluční strategie).
  4. Genetické algoritmy (řídicí parametry, genetické operátory).
  5. Genetické programování a symbolická regrese.
  6. Případová studie z oblasti návrhu algoritmů a elektronických obvodů.
  7. Diferenciální evoluce (optimalizace v reálné doméně, aplikace z inženýrské praxe).
  8. Evoluční algoritmy s pravděpodobnostními modely.
  9. Algoritmy vícekriteriální optimalizace (základní techniky, aplikace z inženýrské praxe).
  10. Pokročilé techniky vícekriteriální optimalizace.
  11. Paralelní evoluční techniky a koevoluční algoritmy.
  12. Evoluční vývin a gramatická evoluce (základní modely, aplikace v umělé inteligenci).
  13. Algoritmy založené na společenstvích (částicové systémy, mravenčí algoritmy).

Cvičení na poč.

12 hod., nepovinná

Vyučující / Lektor

Projekty

18 hod., nepovinná

Vyučující / Lektor