ail025 - evolutionary computation

abstract

outlines

• modely evoluce - základní přístupy a pojmy. populace, rekombinace. ohodnocení úspěšnosti individua.
• genetické algoritmy. zakódování řešené problému do chromozómu. základní genetické operace, křížení, mutace.
• selekce - simulace přirozeného výběru. Účelová funkce. dynamická vs. statická selekce, mechanismus rulety, turnaje, elitářství.
• reprezentační schemata, vlastnosti, věta o schematech.
• evoluční programování. alternativní reprezentace problému. evoluce konečných automatů. "meta-evoluce" - adaptace evolučních pravidel.
• evoluční strategie, kooperace individuí, (1+1) es, (m+1) es, rychlost konvergence.
• klasifikační systémy. učení pravidel "if-then", makléřský algoritmus, q-učení, produkční systémy.
• ea, strojové učení a datokopectví. evoluce expertních systémů, vnitřní reprezentace, michiganský vs. pittsburgský přístup.
• adaptivní chování, animati, artificial life. emergence, simulace stádního chování, simulace prostředí a interakcí (tierra, broučci, ...).
• celulární automaty, l-systémy, třídy složitosti, výpočetní síla.
• genetické programování. evoluce počítačových programů. vnitřní stromová reprezentace, genetické operátory.
• ea a numerická optimalizace. binární vs. float reprezentace, multiúčelová optimalizace, zahrnutí explicitních podmínek a omezení.
• ea a kombinatorické problémy. Řešení np-úplných úloh, problém obchodního cestujícího, problém batohu.
• genetické učení neuronových sítí. vnitřní reprezentace, evoluce topologií. funkční ekvivalence sítí.

references

• russel, s.j. and norvig p.: artificial intelligence: a modern approach. prentice-hall, 1995.  
  obsáhlá moderní učebnice shrnující oblast umělé inteligence. jednotné pojetí výkladu pomocí adaptivních agentů. algoritmy k dispozici on-line.
• mitchell, m.: introduction to genetic algorithms. mit press, 1996. 
  Úvodní text o genetických algoritmech. nejde příliš do hloubky, ale obsahuje novější informace než [3], včetně genetického programování, genetického učení neuronových sítí, atd.
  
• goldberg, : genetic algorithms in search optimization and machine learning, addison-wesley, 1989. 
  klasický učebnicový text o genetických algoritmech, jejich principech, teorii (hlavně dle [4]) a aplikacích.
  
• holland, j.: adaptation in natural and artificial systems, mit press, 1992 (2nd ed).  
  první monografie (1. vyd. z roku 1975) o genetických algoritmech. podrobně jsou prezentovány klasické teoretické výsledky o ga. něco je už překonané.
  
• holland, j.: hidden order, addison-wesley, 1995. 
  nová kniha klasika genetických algoritmů o cas (complex adaptive systems) rozvíjí koncept klasifikačních systémů. napsáno lehce a s nadhledem bez teoretických pasáží (text vznikl na základě hollandových čestných ulam lectures).
  
• michalewicz, : genetic algorithms + data structures = evolutionary programs. springer verlag, 1994. 
  kniha popisující moderní trendy v ga pracující se složitějšími datovými strukturami. důraz na aplikace a experimenty.
  
• koza, j.: genetic programming i, ii. mit press, 1992, 1994. 
  dvě velmi rozsáhlé knihy o genetické evoluci programů v lispu. patnáct set stran, mnoho příkladů.
  
• hitch-hiker's guide to evolutionary computation. 
  zábavný úvod do hlavních pojmů ec (jako nadmnožiny ga). formou slovníku se spoustou odkazů na on-line zdroje i na douglase adamse. text je v několika verzích k dispozici on-line na encore (viz links).
  
• chambers, l. (ed.): practical handbook of genetic algorithms i, ii, crc press 1995 
  
• dawkins, r.: sobecky gen, mf praha 1998. 
  

on-line resources

charles university lecture info