Moodle FEL ČVUT
Evoluční optimalizační algoritmy
B191 - Zimní 19/20
Tento předmět se nenachází v Moodle. Na jeho domovskou stránku se můžete dostat pomocí tlačítka "Stránka kurzu (mimo Moodle)" vpravo (pokud existuje).
Evoluční optimalizační algoritmy - A0M33EOA
| Kredity | 6 |
| Semestry | zimní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+2C |
Anotace
Evoluční algoritmy jsou stochastické optimalizační techniky využívající analogií s přírodní evolucí. Cílem předmětu je seznámit studenty s touto třídou algoritmů, s problémy, na něž mohou narazit při jejich aplikaci, a s metodami jejich řešení. Na přednáškách budou představeny různé varianty evolučních algoritmů a budou ukázány vhodné oblasti pro jejich nasazení. Na cvičeních si studenti vyzkouší implementaci evolučního algoritmu pro řešení složitějších optimalizačních problémů.
Cíle studia
Cílem předmětu je detailně seznámit studenty s několika variantami evolučních optimalizačních algoritmů a ukázat vhodné oblasti pro jejich praktické nasazení. Důraz je kladen na identifikaci překážek, na které narážíme v aplikacích evolučních algoritmů, a na metody, kterými se řeší.
Osnovy přednášek
1. Standardní evoluční algoritmy. Vztah klasických opt. technik a EA. Memetické algoritmy.
2. No Free Lunch. Hodnocení výkonosti a porovnání EA.
3. Práce s omezeními. Speciální reprezentace, penalizace a dekodéry, opravné algoritmy, multikriteriální přístup.
4. Parametry EA. Ladění, adaptace.
5. Statistická závislost mezi komponentami řešení. Perturbační metody. Optimalizace učením modelu.
6. Algoritmy EDA. Optimalizace odhadem modelu rozdělení pravděpodobnosti.
7. Evoluční strategie s adaptací kovarianční matice (CMA-ES).
8. Paralelní evoluční algoritmy.
9. Genetické programování (GP). Reprezentace,
inicializace, operátory, typované GP, ADF.
10. Gramatická evoluce. Gene expression programming.
11. Lineární GP. Grafové GP.
12. Problémy v GP. "Bloat", udržení diverzity.
13. Koevoluce.
14. Rezerva
2. No Free Lunch. Hodnocení výkonosti a porovnání EA.
3. Práce s omezeními. Speciální reprezentace, penalizace a dekodéry, opravné algoritmy, multikriteriální přístup.
4. Parametry EA. Ladění, adaptace.
5. Statistická závislost mezi komponentami řešení. Perturbační metody. Optimalizace učením modelu.
6. Algoritmy EDA. Optimalizace odhadem modelu rozdělení pravděpodobnosti.
7. Evoluční strategie s adaptací kovarianční matice (CMA-ES).
8. Paralelní evoluční algoritmy.
9. Genetické programování (GP). Reprezentace,
inicializace, operátory, typované GP, ADF.
10. Gramatická evoluce. Gene expression programming.
11. Lineární GP. Grafové GP.
12. Problémy v GP. "Bloat", udržení diverzity.
13. Koevoluce.
14. Rezerva
Osnovy cvičení
1. Realizace jednoduchého genetického algoritmu (SGA). Ukázky vlivu jednotlivých parametrů SGA na jeho výpočet.
2. Rozbor témat na semestrální úlohu. Zadání úloh.
3. Řešení semestrální úlohy I - implementace lokálního optimalizačního algoritmu.
4. Odevzdání semestrální úlohy I.
5. Řešení semestrální úlohy II - implementace jednoduchého EA.
6. Řešení semestrální úlohy II - implementace jednoduchého EA.
7. Odevzdání semestrální úlohy II.
8. Řešení semestrální úlohy III - implementace specializovaného EA.
9. Úspěšné aplikace evolučních algoritmů.
10. Řešení semestrální úlohy III - implementace specializovaného EA.
11. Odevzdání semestrální úlohy III. Prezentace referátů.
12. Prezentace referátů.
13. Prezentace referátů.
14. Rezerva
2. Rozbor témat na semestrální úlohu. Zadání úloh.
3. Řešení semestrální úlohy I - implementace lokálního optimalizačního algoritmu.
4. Odevzdání semestrální úlohy I.
5. Řešení semestrální úlohy II - implementace jednoduchého EA.
6. Řešení semestrální úlohy II - implementace jednoduchého EA.
7. Odevzdání semestrální úlohy II.
8. Řešení semestrální úlohy III - implementace specializovaného EA.
9. Úspěšné aplikace evolučních algoritmů.
10. Řešení semestrální úlohy III - implementace specializovaného EA.
11. Odevzdání semestrální úlohy III. Prezentace referátů.
12. Prezentace referátů.
13. Prezentace referátů.
14. Rezerva
Literatura
- Luke, S.: Essentials of Metaheuristics, 2009
http://cs.gmu.edu/~sean/book/metaheuristics/
- Poli, R., Langdon, W., McPhee, N.F.: A Field Guide to Genetic Programming, 2008
http://www.gp-field-guide.org.uk/
http://cs.gmu.edu/~sean/book/metaheuristics/
- Poli, R., Langdon, W., McPhee, N.F.: A Field Guide to Genetic Programming, 2008
http://www.gp-field-guide.org.uk/
Požadavky
Základní povědomí o optimalizaci a optimalizačních metodách.
Více o předmětu na:
https://cw.fel.cvut.cz/wiki/courses/a0m33eoa/start
Více o předmětu na:
https://cw.fel.cvut.cz/wiki/courses/a0m33eoa/start