Evoluční design poráží řešení vytvořená kreativním návrhářem

Podobná situace existuje i v oblasti inženýrského nebo uměleckého designu. Každý výtvor (design) nebo postup vedoucí k dosažení tohoto výtvoru může být zakódován bitovým řetězcem a představovat jeden bod v prostoru možných designů. Otázkou je, zda jsme schopni toto kódování navrhnout tak, aby potenciální algoritmus, který bude prohledávat stavový prostor možných designů, našel požadované řešení v rozumném čase a aby toto řešení bylo zajímavé.

V posledních letech můžeme pozorovat řadu nových výsledků týkajících se základů a teorie evolučních algoritmů. Evoluční algoritmy jsou však také stále více využívány v průmyslu pro řešení obtížných reálných problémů, které vyžadují kreativní přístup. Jedním z důsledků tohoto jevu je nárůst produktů vytvořených evolucí běžící v počítači, jejichž kvalita je srovnatelná nebo i lepší v porovnání s konvenčně navrženými produkty, které vytvořili kreativní lidé. Tomuto novému odvětví se říká evoluční design (viz rámeček 1 ) a pomocí evoluce bylo již navrženo nebo objeveno mnoho nového v řadě oborů (viz rámeček 2 ).

Výsledky vygenerované evolučním algoritmem

V neděli 27. 6. 2004 se v rámci Genetic and Evolutionary Computation COnference (GECCO), konané v Seattlu, uskutečnil první ročník soutěže Human competitive results in genetic and evolutionary computation. Této konference se každoročně zúčastní více než 500 vědců z celého světa, a je tudíž z těch, které se věnují problematice evolučních algoritmů, největší. Představuje vynikající půdu pro prezentaci toho nejlepšího, co se podařilo pomocí evolučních algoritmů objevit. Do soutěže bylo přihlášeno 11 prací, tj. 11 výsledků, které byly automaticky vygenerovány nějakým evolučním algoritmem v uplynulém roce a které byly publikovány v obecně přístupné literatuře. Komise ¹⁾ posuzovala podle stanovených kritérií (viz rámeček 3 ), zda jde o výsledek konkurenceschopný produktům vytvořeným člověkem, a dále vzájemně porovnávala přihlášené výsledky. Poznamenejme, že uvedená kritéria jsou poměrně přísná a rozhodně jim nevyhovují problémy běžně prezentované v učebnicích umělé inteligence. Pokud byl výsledek shledán konkurenceschopným, byla autorům vyplacena určitá peněžitá odměna. Letos se dělilo celkem 5500 amerických dolarů. Autoři v krátké prezentaci, ve které zejména zdůraznili, jak jejich práce splňuje určená kritéria, seznámili komisi se svými výsledky. Nejlepším produktům, které navrhla evoluce, byly uděleny ceny (podrobněji viz www.genetic-programming.org/gecco2004hc.htm...).

1. cena

• Anténa (tým Amesova výzkumného centra NASA, vedený J. Lohnem). Návrh antén je částečně magie a vyžaduje zkušenosti expertů a měsíce experimentování. Pomocí genetického programování byla poměrně rychle navržena anténa unikátního tvaru pro vysílání na frekvenci 8470 MHz a příjem na 7209.125 MHz, která předčila antény navržené experty v řadě parametrů. Zvítězila ve výběrovém řízení (pořádaném NASA) na realizaci antény pro nastávající vesmírnou misi ST5. Bude to pravděpodobně první produkt navržený evolucí, který bude použit ve vesmíru.
• Kvantové algoritmy (L. Spector z Hampshirské akademie v massachusettském Amherstu). Návrh kvantových algoritmů je výrazně náročnější než návrh algoritmů pro konvenční počítače, protože kvantové počítání se řídí zákony kvantové mechaniky, která není intuitivní (blíže viz Vesmír 76, 250, 1997/5). L. Spector použil genetické programování pro návrh nových kvantových algoritmů sloužících k řešení typických problémů, které je výhodné řešit na kvantovém počítači. V projektu byl využit simulátor jednoduchého kvantového počítače, jenž běžel na konvenčním počítači
.

2. cena

• Heuristiky řešící SAT problém (Alex Fukunaga z Kalifornské univerzity v Los Angeles).

  SAT je zkratka slova satisfiability (splnitelný). Zmíněný problém je znám z teoretické informatiky a logiky – vzniká, když máme zjistit, zda je daná množina logických formulí splnitelná. Nedá se řešit jinak, než že vyzkoušíme všechny možné vstupní kombinace, což ovšem je z časového hlediska na dnešních počítačích nezvládnutelné. Existují ale různé heuristiky, které mohou za jistých předpokladů hledání urychlit. Pomocí genetického programování se již podařilo několik velmi zajímavých heuristik objevit – a jsou lepší než nejlepší z dosud známých.

• Dvoudimenzionální kinematická konstrukce umožňující kreslit rovnou čáru (H. Lipson z Cornellovy univerzity). Jak pomocí mechanického zařízení nakreslit rovnou čáru, jestliže není k dispozici jiná rovná čára? Není to tak snadné jako nakreslit kružnici. Tento problém řešily nejlepší mozky již od 18. století, např. James Watt si nechal svoje řešení patentovat v roce 1782. Lipsonův evoluční algoritmus nalezl princip mechanické konstrukce, která rovnou čáru kreslí.
• Optimalizace návrhu organizace s využitím genetického programování (B. Khosraviani, R. Levitt a J. Koza ze Stanfordovy univerzity). Genetické programování bylo použito místo manažera k nalezení (téměř) optimálního návrhu pro jeho projektovou organizaci. Pomocí genetického programování se hledá způsob rozhodování, velikost týmu, přiřazení aktivit, navrhují se změny apod. S využitím simulátoru „virtuálního týmu návrhářů“ se hodnotí kvalita a průběh řešení projektu. Genetické programování ve spojení s tímto simulátorem umožnilo vytvořit lepší způsoby vedení projektu, než kdyby s tímtéž simulátorem pracoval člověk.

3. cena

• Realizace analogového obvodu (tým z Laboratoře tryskových pohonů NASA v Pasadeně, vedený A. Stoicou). Pomocí evolučního algoritmu, simulátoru obvodů a řady dalších technik byl objeven zvláštní, a přitom velmi elegantní obvod, který umí měnit svoji logickou funkci podle hodnoty napájecího napětí. Pokud by takový obvod byl použit pro konstrukci počítače, umožnil by například měnit pouhou změnou napájení způsob provádění výpočtu.

Čestná uznání

Ačkoliv zbývajících pět prací nebylo ohodnoceno jako „human-competitive result“ podle dohodnutých kritérií, bylo jim (resp. jejich autorům) uděleno čestné uznání a vyplacena finanční odměna, protože představují vynikající inženýrská díla.

Budou ještě potřeba návrháři?

Výhodou evolučního designu je, že občas najde vynikající řešení, která jsou mimo možnost konvenčních technik. Kreativní evoluční design také pracuje automaticky, bez asistence člověka. Můžeme spekulovat o tom, zda budeme muset propustit řadu kreativních návrhářů, podobně jako byla propuštěna řada dělníků v důsledku průmyslové revoluce. Jsou zde však také nějaká minus. Za největší nevýhodu je pokládán fakt, že se doposud nepodařilo evolvovat řešení pro opravdu složité problémy, které nás většinou zajímají. A k tomu propouštění. Evoluční design sice pracuje automaticky, ale někdo musí vytvořit vhodný evoluční algoritmus. To ale bývá často složitější než navrhnout něco zajímavého „ručně“!