Aktuální číslo:

2017/12

Téma měsíce:

Kontakty

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

 |  17. 1. 2005
 |  Vesmír 84, 44, 2005/1

Hraje počítač DeepBlue, který dokáže porazit nejlepšího šachistu světa Kasparova, kreativně? Nebo je to jen hrubá síla pramenící z toho, že dnešní počítače dokážou vykonat miliardy instrukcí za sekundu? Informatika redukuje hru v šachy na problém vyhledávání ve stavovém prostoru. Tento stavový prostor dokážeme pro šachy zkonstruovat a efektivně v něm vyhledávat strategie, které ani Kasparov neobjeví. Rychle, přesně, se zkušenostmi generací šachistů před námi a bez emocí.

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 1) 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ě“!

Literatura

Bentley P., Corne D. W. (editoři): Creative Evolutionary Systems, Morgan Kaufmann, San Francisco 2002
Koza J. R. et al.: Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann, San Francisco 1999

Poznámky

1) Komisi tvořili D. Goldberg z Illinoiské univerzity (asi nejznámější propagátor genetických algoritmů), J. Koza ze Stanfordovy univerzity (průkopník genetického programování; tajemník komise, nehlasoval), R. Poli z Univerzity v Essexu ve Velké Británii, E. Goodman z Michiganské státní univerzity a W. Banzhaf z kanadské Memorial University na Novém Foundlandu.

CO JE TO EVOLUČNÍ NÁVRH?

Evoluční návrh vychází z evoluční optimalizace využívající evolučních algoritmů pro nalezení hodnot vektoru parametrů, které se nedají rozumným způsobem vypočítat. Tyto parametry jsou určeny zkušeným návrhářem a optimalizací jejich hodnot obvykle něco vylepšíme (např. výkonnost systému apod.). V případě evolučního návrhu nejčastěji pracujeme s množinou vhodných komponent, nikoliv pouze s parametry. Necháme evoluci, ať sestaví tyto komponenty tak, aby výsledný systém dělal to, co potřebujeme. Je to výrazně obtížnější úloha než hledání hodnot parametrů, ale výsledek často bývá překvapivý a nečekaný – proto může dojít k novému (patentovatelnému) objevu.

Co tedy musíme udělat:

Zakódovat problém jako datovou strukturu. Musíme zvolit vhodnou množinu komponent (např. rezistor, kondenzátor a cívku, pokud chceme navrhnout pasivní elektronický obvod), způsob zakódování a propojení těchto komponent v počítači (např. v podobě grafu).

Navrhnout účelovou funkci. Účelová funkce určuje, jak dobře řeší dané kandidátní řešení zadaný problém. V případě návrhu obvodů např. měříme odchylku frekvenční charakteristiky kandidátního obvodu od požadované frekvenční charakteristiky. Výstupem účelové funkce je hodnota, např. 0–10 %, reprezentující kvalitu daného kandidátního řešení.

Navrhnout genetické operátory. Nová kandidátní řešení vznikají nejčastěji pomocí operátorů inspirovaných biologií – mutace (např. se náhodně změní hodnota vybrané položky v datové struktuře) a křížení (prohodí se hodnoty položek dvou vybraných datových struktur).

Vlastní evoluční algoritmus (zjednodušeně) pracuje následovně:

  • Náhodně vytvoř množinu (populaci) kandidátních řešení problému.

  • Ohodnoť každý prvek pomocí účelové funkce.

  • Opakuj, dokud není splněna ukončující podmínka.

  • — Vytvoř novou populaci s využitím operátorů inspirovaných biologií.

    — Ohodnoť každý prvek pomocí účelové funkce.


PŘÍKLADY EVOLUČNÍHO DESIGNU

Evoluční design byl úspěšně použit pro návrh v řadě inženýrských oborů. Příklady zahrnují: číslicové a analogové obvody, regulátory, antény, programy, klasifikátory, kvantové algoritmy, neuronové sítě, konstrukce robotů, sítě chemických reakcí, molekuly, molekulární elektroniku, struktury organizace, kolektivní chování, mechanické konstrukce, umělé „živé“ organizmy (o evolučním návrhu obvodů viz Vesmír 81, 393, 2002/7).

V oblasti umění generuje evoluční systém kandidátní návrhy a uživatel na základě svého estetického cítění (které nahrazuje účelovou funkci) vybírá ty artefakty, které se mu líbí. Existují programy pro evoluční návrh obrazů, hudby nebo architektury. Dva jednoduché interaktivní systémy pro evoluční návrh obrázků, vytvořené studenty FIT VUT v Brně, jsou k vyzkoušení na stránce www.fit.vutbr.cz/~sekanina/ehw/studentp.htm.... >

Nabízí se otázka, zda evoluční design v dohledné době nahradí kreativce v reklamních agenturách, kteří vymýšlejí reklamní slogany. Evoluční návrh vtipů už snad i někdo řeší.

KDY JE VÝSLEDEK EVOLUČNÍHO ALGORITMU UZNÁN ZA SCHOPNÝ KONKUROVAT ČLOVĚKU?

Musí splňovat alespoň jeden z následujících požadavků. Na stránkách www.genetic-programming.com/humancompetitiv... je uvedeno prozatím 36 výtvorů, které byly vyprodukovány genetickým programováním a které jsou konkurenceschopné lidským výtvorům týchž kritérií:

  • Výsledek byl patentován jako vynález v minulosti, je vylepšením patentovaného vynálezu nebo by dnes mohl být kvalifikován jako patentovatelný vynález.

  • Výsledek je stejně dobrý nebo lepší než jiné řešení, které bylo akceptováno jako nový vědecký výsledek v době, kdy bylo publikováno v recenzovaném vědeckém časopisu.

  • Výsledek je stejně dobrý nebo lepší než jiný výsledek, který byl vložen do databáze nebo archivu výsledků udržovaných mezinárodně uznávanou skupinou vědců.

  • Výsledek je publikovatelný ve své podstatě jako nový vědecký výsledek nezávisle na tom, že byl mechanicky vytvořen.

  • Výsledek je stejně dobrý nebo lepší než nejaktuálnější člověkem vytvořené řešení dlouho známého problému, pro který vznikala řada neustále lepších výsledků navržených člověkem.

  • Výsledek je stejně dobrý nebo lepší než to řešení, které bylo považováno za pokrokové ve svém oboru, když bylo objeveno.

  • Výsledek řeší problém, který má pro daný obor nepopiratelnou obtížnost.

  • Výsledek zvítězil v soutěži s řešeními vytvořenými člověkem (buď ve hře proti člověku, nebo proti programu, který byl napsán člověkem).

Ke stažení

OBORY A KLÍČOVÁ SLOVA: Evoluční biologie

O autorovi

Lukáš Sekanina

Ing. Lukáš Sekanina, Ph.D., (*1976) vystudoval Fakultu elektrotechniky a informatiky VUT v Brně. Nyní je asistentem na Fakultě informačních technologií VUT a zabývá se využitím biologických principů pro návrh hardwaru. Je autorem monografie Evolvable Components (Springer Verlag, 2003). http://www.fit.vutbr.cz/~sekanina

Doporučujeme

Přemýšlej, než začneš kreslit

Přemýšlej, než začneš kreslit

Ondřej Vrtiška  |  4. 12. 2017
Nástup počítačů, geografických informačních systémů a velkých dat proměnil tvorbu map k nepoznání. Přesto stále platí, že bez znalosti základů...
Tajemná „Boží země“ Punt

Tajemná „Boží země“ Punt uzamčeno

Břetislav Vachala  |  4. 12. 2017
Mnoho vzácného zboží starověkého Egypta pocházelo z tajemného Puntu, kam Egypťané pořádali časté obchodní výpravy. Odkud jejich expedice...
Hmyz jako dokonalý létací stroj

Hmyz jako dokonalý létací stroj

Rudolf Dvořák  |  4. 12. 2017
Hmyz patří k nejdokonalejším a nejstarším letcům naší planety. Jeho letové schopnosti se vyvíjely přes 300 milionů let a předčí dovednosti všech...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné