Darwinova teorie pomáhá informatikům

Zatímco matematika a informatika většinou svými výsledky obohacují ostatní vědní obory, při evolučních algoritmech je tomu přesně naopak. Aplikováním biologické Darwinovy teorie o vývoji druhů získali informatici možnost řešit problémy, na které zatím matematický aparát nestačil. Teorie o vývoji druhů rozšířila informatiku o vývoj evolučních výpočetních technik, které se využívají k vývoji umělé inteligence. Jednou z odnoží evolučních algoritmů jsou genetické algoritmy. Genetický algoritmus (GA) je postup, který se snaží aplikací principů evoluční biologie nalézt řešení složitých problémů, pro které neexistuje použitelný exaktní algoritmus. GA, resp. všechny postupy patřící mezi evoluční algoritmy, používají techniky napodobující evoluční procesy známé z biologie – dědičnost, mutace, přirozený výběr a křížení – pro „šlechtění“ řešení zadané úlohy. Princip práce GA je postupná tvorba generací různých řešení problému. Při řešení se uchovává tzv. populace, jejíž každý jedinec představuje jedno řešení problému. Přitom to, jak si tyto organismy vedou, tj. jejich schopnost přežít a schopnost reprodukce, odpovídá tomu, o jak „dobrá“ řešení se jedná. Jak populace probíhá evolucí, řešení se zlepšují. Algoritmus je obvykle ukončen při dosažení postačující kvality řešení. Jedná se tedy v podstatě o aplikaci principů, které příroda úspěšně používá již po tisíciletí. Tým informatiků z Ústavu počítačových systémů Fakulty informačních technologií VUT v Brně se biologií inspirovanou aplikací evolučních algoritmů a z ní vyplývajícího i nového přístupu k vývoji inteligentního hardwaru zabývá již několik let. Jejich cílem je navrhnout a implementovat zařízení umožňující automaticky generovat potřebná inovativní řešení. Takové zařízení bude zhotoveno jako relativně malá vestavěná součást cílového přístroje-systému a bude schopno generovat inteligentní řešení těch problémů, které dynamicky vznikají v reálných aplikacích, např. v mobilních systémech, adaptivních dopravních kontrolérech, robotech apod. „Lze si to dobře představit např. na vyslání kosmické sondy. Místo toho, aby se obvody potřebné např. pro zajištění spojení vyrobily a instalovaly podle předpokládaných parametrů již na Zemi, lepší bude vyvinout je pomocí metody genetických algoritmů podle konkrétních podmínek v kosmu přímo na palubě sondy,“ vysvětluje Lukáš Sekanina z brněnského týmu informatiků. Takové postupy se již ostatně nyní využívají. NASA např. pomocí genetických algoritmů vyvinula anténu speciálních vlastností pro umístění na satelitech určených pro měření magnetosféry Země. Její tvar navržený metodou genetického programování byl sice hodně překvapivý, ale z hlediska funkčnosti naprosto vyhovující. Brněnský tým informatiků patří v aplikacích evolučních algoritmů ke světové špičce. Svědčí o tom i jejich úspěch v letošním ročníku soutěže Human competitive awards in genetic and evolutionary computation, která se konala v rámci konference Genetic and Evolutionary Computation COnference (GECCO) v americké Atlantě. Tomáš Pečenka, Lukáš Sekanina a Zdeněk Kotásek v soutěži obsadili skvělé druhé místo. GECCO je nejvýznamnější světovou akcí v oblasti genetických algoritmů a programování, které se každoročně účastní více než 500 vědců z celého světa. Informatici z VUT v Brně soutěžili v Atlantě s evolučně navrženou sadou testovacích obvodů pro diagnostické CAD systémy, která má lepší parametry než stávající sady. Navržené obvody nejenže vykazují požadované diagnostické vlastnosti, ale se složitostí až 1,2 milionu hradel jsou i největšími obvody doposud navrženými evolučním algoritmem. V soutěži je třeba představit výsledek, který byl získán pomocí technik evolučního návrhu – tedy automaticky vygenerován počítačem simulujícím evoluční proces. Je možné přihlásit jen takovou práci, která byla publikována v roce, jenž předcházel termínu konání soutěže. Komise složená z odborníků pak posuzuje, zda je takto vytvořený výsledek schopen měřit se s lidskou invencí – je „human-competitive“. Tým z Brna jen těsně skončil za prací z Hampshirské akademie v massachusettském Amherstu o použití genetického programování pro charakterizaci konečných algeber. Igor Maukš