Univerzita Hradec Králové Fakulta informatiky a managementu Katedra informatiky a kvantitativních metod
Swarm Intelligence Modelování algoritm a za ízení ešících problémy inspirované kolektivními návyky len kolonií hmyzu a ostatních zví at, žijících ve spole enství Bakalá ská práce
Autor: Martin Šlajchrt Aplikovaná informatika
Vedoucí práce: Doc. RNDr. Josef Hynek, MBA, Ph.D.
Hradec Králové
b ezen 2004
-I-
Prohlášení Prohlašuji, že jsem bakalá skou práci zpracoval samostatn a s použitím uvedené literatury.
Jméno a p íjmení :
V Hradci Králové dne :
- II -
Pod kování Na tomto míst bych cht l velice pod kovat panu Doc. RNDr. Josefu Hynkovi, MBA, Ph.D. Obzvlášt za prop j ení nedostupné literatury, pr b žnou korekturu této práce, vst ícný p ístup a mnoho konstruktivních a perspektivních poznámek.
- III -
Anotace práce Tato práce je koncipována jako úvodní studie do problematiky swarm intelligence. Mojí snahou bylo podat p ípadným zájemc m o toto téma srozumitelný úvod do této v dní disciplíny. Práce je rozd lena do n kolika hlavních ástí. V první popisuji r zné pohledy na principy života a inteligence a snahy o jejich simulaci v po íta ových programech. Druhá ást je úvodem do problematiky optimalizace. Jsou zde popsány základní principy optimalizace metodou pokusu a omylu. Ve t etí
ásti se zabývám spole enským chováním živo ich . Zde jsou uvedeny
p íklady , jak zástupci živo išné íše eší složité problémy za pomocí jednoduchých postup . V poslední ásti nasti uji formou úvodu základní charakteristiky a principy evolu ních výpo t . Do této oblasti spadají genetické algoritmy, genetické programování, evolu ní programování a evolu ní strategie.
Synopsis This work is ment to be an introductory study on the porblematics of swarm intelligence. My effort is to offer to potencialy interested people on this topic comprehensible introduction into this science. My work is divided into four parts. In the first part are described diferent views on the life and intelligence princile‘s field and aspirations of their simulations in computer programs. Second section is an introduction of optimalization’s field. There are described basic principles of optimalization by trial and error. The third part describes the social behaviors of organisms. Some examples how animals solve komplex problems by using simple methods are mentioned there. The last chapter is written as an introduction of basic characteristics and principles of evolutionary computations. To this field belongs genethic algorithms, genetic programming, evolution programming and evolution strategies.
- IV -
Obsah 1 ÚVOD ................................................................................................................................................................... 1 2 MODELY A NÁVRHY ŽIVOTA A INTELIGENCE ..................................................................................... 2 2.1 CO JE ŽIVÉ A CO NE? ....................................................................................................................................... 2 2.2 STOCHASTICKÉ P IZP SOBOVÁNÍ ................................................................................................................... 3 2.3 DVA OBROVSKÉ STOCHASTICKÉ SYSTÉMY ...................................................................................................... 5 2.4 HRA NA ŽIVOT ................................................................................................................................................ 6 2.5 CELULÁRNÍ AUTOMATY .................................................................................................................................. 8 2.6 UM LÝ ŽIVOT V PO ÍTA OVÝCH PROGRAMECH ........................................................................................... 11 2.6.1 Slepý hodiná ....................................................................................................................................... 12 2.6.2 Sv t Karla Simse .................................................................................................................................. 13 2.7 INTELIGENCE V P ÍSTROJÍCH – TURING V TEST ........................................................................................... 16 3 OPTIMALIZACE METODOU POKUSU A OMYLU.................................................................................. 20 3.1 JEDNODUCHÝ OPTIMALIZA NÍ PROBLÉM ...................................................................................................... 20 3.2 DIMENZE OPTIMALIZACE .............................................................................................................................. 21 3.3 ZNÁZORN NÍ OHODNOCENÍ .......................................................................................................................... 22 3.4 VÍCEROZM RNÝ ROZPOZNÁVACÍ PROSTOR ................................................................................................... 23 3.5 NK KRAJINY ................................................................................................................................................. 26 3.6 KOMBINATORICKÁ OPTIMALIZACE ............................................................................................................... 27 3.7 BINÁRNÍ OPTIMALIZACE ............................................................................................................................... 29 3.7.1 Náhodné a hladové prohledávání ........................................................................................................ 32 3.7.2 Horolezecký algoritmus (Hill Climbing).............................................................................................. 33 3.7.3 Simulované žíhání (Simulated Annealing) ........................................................................................... 34 3.7.4 Binární a Grayovo kódování................................................................................................................ 34 4 SOCIÁLNÍ ORGANISMY ............................................................................................................................... 36 4.1 POHLEDY NA EVOLUCI .................................................................................................................................. 36 4.1.1 Hypotéza Gaia ..................................................................................................................................... 36 4.1.2 Sv t sedmikrásek .................................................................................................................................. 37 4.1.3 Diferenciální selekce............................................................................................................................ 38 4.1.4 Teorie vnit ního symbiontu .................................................................................................................. 40 4.2 SOCIÁLNÍ CHOVÁNÍ JAKO OPTIMALIZACE ..................................................................................................... 41 4.3 SOCIÁLNÍ CHOVÁNÍ HMYZU .......................................................................................................................... 43 4.3.1 Mravenci a termiti................................................................................................................................ 45 4.3.2 Optimalizace pomocí virtuálních mravenc ........................................................................................ 46 4.4 HEJNA........................................................................................................................................................... 48 4.4.1 Ryby ..................................................................................................................................................... 48 4.4.2 Lidé ...................................................................................................................................................... 49 4.4.3 Ptáci..................................................................................................................................................... 50 5 EVOLU NÍ VÝPO TY................................................................................................................................... 53 5.1 GENETICKÉ ALGORITMY ............................................................................................................................... 53 5.1.1 Operace algoritmu ............................................................................................................................... 54 5.2 GENETICKÉ PROGRAMOVÁNÍ ........................................................................................................................ 55 5.2.1 P íprava ............................................................................................................................................... 56 5.2.2 Vlastní genetické programování .......................................................................................................... 57 5.3 EVOLU NÍ PROGRAMOVÁNÍ .......................................................................................................................... 58 5.3.1 Operace algoritmu ............................................................................................................................... 59 5.4 EVOLU NÍ STRATEGIE .................................................................................................................................. 60 5.4.1 Operace algoritmu ............................................................................................................................... 60
-V-
6 ZÁV R ............................................................................................................................................................... 61 7 POUŽITÁ LITERATURA ............................................................................................................................... 62
- VI -
1 Úvod Cílem této práce je vypracování úvodní studie do problematiky swarm intelligence. Práci jsem se snažil psát takovým stylem, aby byla snadno a pohodln
itelná i pro zájemce,
kte í s podobnou problematikou zatím nep išli do styku. Zpracování tohoto tématu jsem si vybral z isté zv davosti. Jistou p edstavu o tématu jsem m l již z p edem prostudovaných materiál , ale musím íci, že b hem zpracování práce jsem se dozv d l spoustu zajímavých v cí, které, doufám, upot ebím i v pozd jším život . Jako hlavní zdroje informací mi posloužily dv knihy. Jsou jimi Swarm Intelligence od Jamese Kenedyho a Russella C. Eberharta [1] a Evolu né algoritmy od Vladimíra Kvasni ky, Ji ího Pospíchala a Petera Ti a [22]. Z t chto dvou zdroj
jsem na erpal majoritní ást
informací, kterou jsem dotvo il poznatky získanými z internetu. Práce za íná kapitolou, která má uvést tená e do problematiky modelování um lého života a inteligence. Pokud chceme, aby za nás n kdo vy ešil jistý problém, jist toto ešení nesmí postrádat projev inteligence. Zárove je inteligence projevem života a tak jsem tuto kapitolu zpracoval jako po áte ní. Dále následuje ást v novaná optimalizaci metodou pokusu a omylu. Jsou problémy, které nejsou jenom vy ešeny nebo ne. Jsou i takové, které mají mnoho ešení, ale ne všechna jsou efektivní. Problémem najít nejefektivn jší ešení se práv zabývá optimalizace. Jak je uvedeno v podtitulu této práce, swar intelligence se zabývá modelováním algoritm a za ízení ešících problémy inspirované kolektivními návyky len kolonií hmyzu a ostatních zví at, žijících ve spole enství. Práv
tvrtá kapitola se zabývá
sociálními projevy živo ich , aby tená mohl nap íklad zjistit, odkud v dci, zabývající se swarm intelligencí, berou inspiraci. Nakonec uvádím ást o evolu ních výpo tech. Jde o konkrétní metody optimalizace, které jsou v sou asnosti hojn používány. Na za átek bych se pokusil nalákat tená e jedním takovým post ehem, který jsem si uv domil b hem psaní této práce. Znáte spisovatele Douglase Adamse? Pokud ne, nevadí. Jeho styl tvorby by se dal nazvat jako bláznivá sci-fi, ale to není v tuto chvíli podstatné. Podstatné je to, že v jedné z jeho knih (konkrétn Stopa v pr vodce po galaxii) vyslovil myšlenku, že celá Zem se všemi živo ichy i rostlinami je jakýsi druh po íta e, který eší nep edstaviteln složitý problém. A práv o tomto je swarm intelligence.
-1-
2 Modely a návrhy života a inteligence 2.1 Co je živé a co ne? Již z po átku psané historie se lidé snažili p ijít na to, jak se od sebe odlišují živé a neživé v ci. Rozdíly se zdály být z ejmé, ale lidem se je stále neda í jednozna n do detail specifikovat. Již Aristoteles nap íklad tvrdil, že : „To co má v sob duši se odlišuje od toho, co ji nemá v tom, že se vyzna uje životem… Žití m že znamenat myšlení a nebo rozpoznání okolního pohybu i klidu, nebo pohyb ve smyslu vyživování, rozkladu a r stu… Tato moc sebe-vyživování… je p vodní síla, jejíž vlastnictví nás vede k uvažování o v cech jako živých.“ Je pozoruhodné, že tato filozofie definovala ortodoxní pohled na tisíc let do p edu a na další tisíc let jej ovlivnila. Teprve až v sedmnáctém století bylo objeveno, že lidské t lo se skládá jenom z neživých ástic. Tento objev zve ejnil pan William Harvey ve své publikaci „O pohybu srdce a krve ve zví atech“ (On the Motion of the Heart and Blood in Animals). Zde bylo poprvé popsáno, jak krev cirkuluje v lidském t le za pomocí srdce. Rázem bylo srdce považováno za b žnou pumpu jako každou jinou. Rok poté reagoval ne tento poznatek známý filosof Descartes svým výrokem, jež vytvo il pojítko mezi t lesnou schránkou a psychikou jedince. Výrok zn l : „Zkoušením funkcí, které by m ly… existovat v tomto t le, shledal jsem p esn všechny t mi, které v nás mohou být i bez naší moci myšlení a následovn bez naší duše. Té naší ásti, odd lené od t la, jejíž p irozeností je myslet.“ Descartes takto znovu odsunul duši do t žko srozumitelného rozm ru. P esto je nesporné, že je n jak spojena se zbytkem našich bytostí, ale nikdo neví jak. D sledkem tohoto vývoje bylo uv dom ní, že lidské t lo je složeno výhradn z anorganické hmoty jako každý jiný objekt v reálném sv t . V té dob jist revolu ní a zcela zásadní objev. Jak pokro ily možnosti a potenciál v dy, p išla na sv t myšlenka organické chemie. Za organické v ci se dodnes považují ty, v jejichž složení lze nalézt hydrokarboxylové slou eniny (složené z vodíku a uhlíku). Možností uspo ádání t chto dvou atom v molekule je obrovské
-2-
množství a tak existuje spousta organických látek. Na druhou stranu je zajímavá následující hypotetická situace. Zástupci lidské rasy objeví jiné organismy. Vyvstane otázka, zda je také považovat podle lidských m ítek za živé. Pokud se budou nalézat na jiném míst ve vesmíru, zcela jist budou jinak, a hlavn z jiné hmoty, stav ny jejich t lesné schránky. Zcela jist je také budeme považovat za živé. V nedávné dob
biologové, zapojeni do „Projektu minimální genové výbavy“,
zkoumali kolik a jaké geny jsou nezbytné pro organismus pro p ežití. Tedy proto, aby byl stále považován za živý prvek. Projekt vedl John Craig Venter. Pokus byl provád n na jednobun ném živo ichu metodou kombinováním jeho genetické výbavy. Záv rem byl poznatek, že 265 až 350 z 480 gen živo icha Mycoplasma genitalium jsou nezbytné pro jeho p ežití v laboratorních podmínkách. Vyvstává myšlenka, zda by takto bylo možné v ideálních podmínkách pro život zkonstruovat zcela jinou genetickou sadu a importovat ji do systému laboratorního jedince. Kdyby byl tento jedinec poté schopný vykazovat životní funkce, musel by být uznán živým. Ve všech známých sm rech, organismy jsou jako stroje (e.g., Wooldridge, 1968). Lidé dokáží popsat procesy v bu ce na úrovni molekul. V této hloubce poznání jsou biologické pochody ne nepodobny pracovním postup m z u ebnic chemie a zcela jist by se mohly i um le provozovat. Nap íklad princip stahování sval
pracuje na stejném principu jako
mechanické písty ovládané tlakem vnit ní tekutiny. Ke každé ásti našeho t la by se dala vymyslet „náhradní sou ástka“. Zcela jist i k mozku, a koliv se jedná o výjime n složitý a komplexní systém. Jsou známy a popsány d sledky, jak zásahy do mozku ovliv ují psychiku jedince, a na druhou stranu, jak myšlení vyvolává na nervových synapsích elektromagnetické vzruchy. Kdyby v dci byli schopni vytvo it ke každé ásti p edem zvoleného organismu implantáty, zastupující funkci jednotlivých orgán , a postupn by celý organismus nahradily t mito um lými orgány, m li bychom celý organismus vyrobený lov kem. V tento moment by lidmi p estal být považován za živý.
2.2 Stochastické p izp sobování Zajímavý poznatek je, že rozdíl mezi živým organismem a neživou hmotou spo ívá ve schopnosti se n emu p izp sobit. Uvedu jednoduchý p íklad. P edstavte si, že n jakým
-3-
zp sobem p ijdete o ruku, kterou píšete. Každý se po a už kratší i delší dob nau í psát druhou rukou, p izp sobí se dané situaci. Proces p izp sobování tak jak jej známe z p írody je v tšinou stochastický. To znamená, že v sob obsahuje jistou dávku náhody. Jedna z mnoha definic náhodnosti íká, že náhodnost existuje, jestliže opakované uskute n ní jednoho a toho samého jevu za stejných podmínek vyústí v odlišné výstupy. S dnešními znalostmi fyziky a matematiky je z ejmé, že k náhodným událostem dochází pramálo kdy.
ísla, která se generují v po íta i jako náhodná, jsou výsledkem
n jakého algoritmu. Ten m že být sebevíc složit jší, ale po íta žádnou jinou innost schopen vykonávat není a tak se vnucuje, že tato ísla jsou vlastn p edem ur ená. Spousta lidí rozhoduje „náhodn “ házením mincí. Je ale jasné, že kdyby se poda ilo dvakrát opakovat ten a samý hod (musela by být stejná síla, sm r hodu a stejné okolní podmínky), tak je jisté, že výsledek by byl stejný. Taktéž kdybychom znali p esn všechny vstupní prom nné a znali všechny fyzikální zákonitosti, tak bychom mohli i p edpovídat, s jakým výsledkem onen „náhodný“ hod dopadne. Lidem se zdá náhodné to, co podléhá velmi složitým pravidl m a na první pohled není z ejmé, jaký výstup lze o ekávat. Po v tšinu dvacátého století byla uznávána náhodnost na subatomární úrovni. Spo ívala v objevení foton a v poznání, že fotony se mohou vyskytovat ve dvou formách. Jak ástice tak vlny energie. A práv o tom, v jakém stavu se tento prvek bude vyskytovat, m la rozhodovat náhoda. O tuto skute nost se p eli dva fyzikové. Niels Bohr tvrdil, že stav ástice je opravdu náhodnou vlastností. Proti tomuto tvrzení byl Albert Einstein, který v il, že je to nemožné a argumentoval tvrzením, že „b h p eci nehraje kostky“. Bohr byl donedávna považován za vít ze tohoto sporu, avšak v roce 1998 fyzici Stephan Dürr, Thomas Nonn a Gerhard Rempe [1] zpochybnili Bohrovu teorii. Nyní považují v dci za jediný zdroj náhodných rozhodnutí výsledek interakcí mezi jednotlivci, jejichž chování je ve skute nosti p edur ené. U p izp sobivých po íta ových program se stochastické chování vyskytuje ve dvou formách. Za prvé jako vyjád ení nejistoty. Program neví, jakým sm rem má nap íklad pokra ovat, tak zvolí podle kvazi-náhodného ísla sm r. Druhá forma p edstavuje vyjád ení kreativity a animace. To spo ívá v zanesení náhodnosti do kreativního procesu v nad ji, že p inese n co nového. -4-
2.3 Dva obrovské stochastické systémy Stochastické p izp sobování je pozorovatelné ve všech živých organism a to jak v mysli tak v evoluci. Ty pojmenoval Gregory Beteson v roce 1979 jako „Dva obrovské stochastické systémy“ (Two great stochastic systems). Evoluce probíhá jako hledání možností a výb r t ch, které obstojí. Slabý jedinec má malou šanci na p ežití i p edání své genetické výbavu. Naopak silný jedinec má tuto šanci mnohem v tší a taktéž snáze obstojí i v rozmnožovacím aktu. Jeho geny obsahující dobré vlastnosti jsou p edány dalším generacím, které ovliv ují. Náhoda se zde vyskytuje ve form dlouhodobého kolísání pravd podobností r zných genetických znak
jedinc
a jejich
fyzických vlastností jako je váha, výška a podobn . Nejrozší en jší pohled na mysl je takzvaný „memetický“, který p edložil Dawkins v práci „Sobecký gen“ (The Selfish Gene) v roce 1976. Název vznikl z eckého slova „mimeme“, což znamená napodobovat. Jedinci jsou myšleny jako „memy“, což jsou myšlenky a jiné znaky, které jsou produktem mysli, a chovají se podobn jako geny. Jestliže je jakákoliv myšlenka úsp šná a perspektivní, má nárok na dlouhý „život“. Taktéž musí být schopná se p izp sobovat novým situacím. Jen takováto myšlenka potom m že ovliv ovat jiné. Dawkins vyslovil tvrzení, že tak jako geny jsou i memy schopny reprodukce a to prost ednictvím napodobování (odtud název memy) p edchozích myšlenek. Tato situace nastává, když lov k , dejme tomu v rozhovoru, vyslechne n jakou myšlenku a rozhodne se ji p edat dál. Tím p vodní myšlenku rozmnoží a ješt ji n jakým zp sobem ovlivní, poupraví ji. Tyto dva systémy jsou naprosto odlišné ve svém chování a tím i ve zp sobu, jak se p izp sobují zm nám. Jak bylo e eno, evoluce p izp sobuje výb rem nejlepšího z celé populace a eliminuje slabé lánky. Mysl pozm uje stavy jedinc , kte í p etrvají jistou dobu. Bateson v práci „Mysl a p íroda“ (Mind and Nature) [2] up esnil svých šest kritérií, která musí být spln na, aby se cokoliv dalo nazvat myslí. 1) mysl je celek složený z ástí, které navzájem na sebe p sobí 2) p sobení ástí navzájem je spoušt no zm nou stavu jednoho z ú astnících se prvk 3) mentální procesy musí mít zajišt n p ísun energie 4) mentální procesy vyžadují kruhovité, nebo více komplexn jší rozhodovací et zce -5-
5) b hem mentálních proces , d sledky rozdíl jsou pokládány za zm ny t ch rozdíl , které jím p edcházely 6) popis a za azení t chto proces p em n odkrývá hierarchii logických typ Zajímavé je Batesonova poznámka, že sama biologická evoluce tato kritéria spl uje a tudíž je sama jakousi formou mysli. A na druhou stranu mysl je jistou formou evoluce. Evolu ní procesy p evedené do sousledu p íkaz v po íta ových programech jsou využívány k ešení zdánliv ne ešitelných problém (kapitola 6). Tyto problémy jsou definovány jako analogie ekologické lokality, kde se kombinují a testují možnosti, poté jsou nejlepší z nich na základ ohodnocení vybrány a dále používány. Kdybychom mohli dostate n bohatý systém interakcí vytvo it v po íta i, vyvolali bychom n co velmi podobného lidské inteligenci.
2.4 Hra na život Tento nápad se stal odrazovým m stkem pro jev zvaný um lý život (artifical life). Byl publikován v íjnu roku 1970 v asopise Scientific American v ásti matematických her Martina Gardnera. Konkrétní lánek autora Johna Conwaye m l název „Hra na život“ (Game of Life) [3]. Celá „hra na život“ [4] je koncipována jako dvourozm rné pole bun k. Bu ky mohou nabývat dvou stav – živá nebo mrtvá. Pole bun k se postupem asu m ní. Každá bu ka sleduje okolí kolem sebe (svých osm soused ) a v závislosti na jejich stavu se její stav zm ní nebo setrvá. Stav se m ní podle t í pravidel : 1) jestliže má sledovaná bu ka v okolí jenom dva a mén živých soused , pak zem e na osam lost – to znamená že v p íštím kole bude její stav „mrtvá“ 2) jestliže má sledovaná bu ka t i a více soused živých, pak zem e z d vodu p emnožení 3) jestliže je daná bu ka mrtvá a v jejím okolí jsou p esn t i živí sousedé, pak se narodí – to znamená, že v p íštím kole se její status zm ní na „živá“ Pokud se tato jednotlivá pravidla vloží do jednoduchého programu a jako bun k bude použito pixel , pak výsledný efekt bude vypadat trochu zmate n . S kapacitami dnešních
-6-
po íta
se provád jí tyto operace velice rychle. Jako ešení by se dalo využít zpožd ní, aby
vývoj na obrazovce byl lépe vnímatelný. Pole je také asto implementováno jako torus grid. Jde o tvar anuloidu a takovéto (imaginární) pokroucení pole má za následek jednu zásadní zm nu. Pro okrajové bu ky se po ítají jako sousedé i bu ky z opa ného okraje. To znamená, že bu ka na kraji nemá jen p t soused , jak by se mohlo zdát, ale osm jako bu ka uvnit pole. Za b hu programu se zjevn náhodné stavy bun k zm ní na soudržné vzory a putují po poli. Sražení dvou vzor má více následk . Mohou se rozpadnout na více takovýchto vzor , p vodní dva vzory mohou zmizet nebo se prolnou a pokra ují ve své trajektorii. N které jednoduché vzory setrvávají na míst a jakoby problikávají, jejich stav se periodicky m ní, zatímco n které byly p irovnány k d l m. Ty zdánliv vyst elují nové vzory putující po poli. B hem asu se pro r zné tvary ustálily konkrétní názvy. Konkrétní pojmenování zn jí : -
blinkers
-
b-hemptaminos
-
brains
-
bookends
-
gliders
-
glider guns
-
r-pentaminos
Obr. . 2.1 - tento obrázek znázor uje tvar zvaný klouzák a jeho pohyb po poli v ase; p evzato z [1]
-7-
Celá záležitost ale nemusí vždy po jisté dob kon it stavem, kdy všechny bu ky vym ou. V dci zabývající se um lým životem našli mnoho znak , ve kterých se hra na život podobá biologickému životu. Také bylo navrhováno, že by tento algoritmus mohl být implementován jako univerzální po íta . Ba co více i jako simulace reálného života v procesu. Na CD p íloze této práce m žete najít program WinLife, který je jinou implementací Game of Life.
2.5 Celulární automaty Celulární automaty se v jistých charakteristikách podobají p edchozímu modelu. Jde o jednoduchý stroj, který vykazuje životu podobné chování. V nejjednodušší form
je
implementován jako sled jedni ek a nul (bitový et zec). Každý bit p edstavuje jednotlivou bu ku, jejíž stav závisí na stavu jejích bezprost edních soused . Pravidla pro zjišt ní stavu musí být p edem p esn nadefinována, takže tato skute nost zajiš uje obrovské množství takovýchto systém s r zným chováním. Je i možno m nit velikost okolí. Pokud se jedná o bitový et zec, bezprost edními sousedy budou bity napravo a nalevo od námi zvolené bu ky. V p ípad krajního bodu je chyb jící soused nahrazen bu kou z opa ného konce, aby každá bu ka m la dva sousedy. Lze si to p edstavit v prostoru, jako kdybychom oba konce spojili a vznikla by kružnice. V takovém p ípad má rozhodovací tabulka o stavu bu ky 8 ádk (23). soused napravo
sledovaná
soused
bu ka
nalevo
p íští hodnota bu ky
1
1
1
0
1
1
0
1
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
Tab. 2.1 : rozhodovací tabulka pro p íští stav jednotlivé bu ky -8-
Nemusíme se ale omezovat na krajní sousedy, ale vytvo it rozhodovací tabulku, která by zohled ovala dva sousedy napravo a dva nalevo.
ádk by m la 32 (25) a výsledný efekt
by byl více r znorodý než u p edchozího p ípadu. Pro znázorn ní se používají místo jedni ek a nul odlišn obarvené pixely na monitoru. V první interakci se bitový et zec vybarví pouze jako pruh erných a bílých pixel . Už v druhé interakci ale za íná být celá v c zajímav jší. Nov propo ítaný et zec nep epíše p edchozí, namísto toho se vykreslí pod n j a tak je i vid t historie p edchozích stav .
Obr.
. 2.2 - zde je pár p íklad
automat ; p evzato z [1] -9-
jednorozm rných binárních celulárních
Stephen Wolfram (1984/1994) poznamenal, že chování celulárních automat m že být rozd leno do ty kategorií [1] : 1) evoluce vede k homogennímu stavu, kdy dosahují všechny bu ky stejného stavu (point attractor) 2) evoluce vede k vytvo ení stálých, nebo periodicky se opakujících struktur (periodic attractor) 3) evoluce vede k chaotickému chování (strange attractor) 4) evoluce vede ke komplexním strukturám, které jsou asto dlouhobodé tvrtý typ je nejzajímav jší ze všech. Jistá pravidla dávají vznik charakteristickým a identifikovatelným objekt m, které se ale nikdy neopakují. Stephen Wolfram ukázal, jakým zp sobem mohou celulární automaty
tvrtého typu fungovat jako univerzální po íta e.
Langton [5] zase demonstroval, jak klouzavé a nebo pohybující se ástice mohou být použity pro provád ní výpo t a statické objekty (pokud se periodicky rozsv cují) mohou uchovávat informace. Langton se v roce 1991 domníval, že nekon ící složitost celulárních automat tvrtého ádu, skoro porozumitelná ale nep edvídatelná, m že být vedena a ovliv ována takovým zp sobem, že by mohla provád t jakékoliv myslitelné výpo etní operace. Chování takovýchto systém
není p edvídatelné a ani náhodné, je komplexní. Proto se také tyto
systémy nazývají „na hranici chaosu“ (systems at the edge of chaos).
- 10 -
Obr.
. 2.3 - takto mohou vypadat typické objekty vzniklé v celulárních
automatech tvrtého ádu; p evzato z [1]
2.6 Um lý život v po íta ových programech Život v po íta i není považován za život, tak jak si ho mnozí p edstavujeme z biologického hlediska. Tyto programy nenapodobují reálné biologické procesy a to z toho d vodu, že kus programového kódu se m že kopírovat (množit), aniž by docházelo k d lení bun k a podobn . Pro posouzení, jestli program se chová jako živý jsou mnohá kritéria. Jedním z nich je tvrzení, že živé v ci (a už jakékoliv) jsou odolné v i nár stu entropie ve svém systému b hem jeho existence. V systémech také dochází k rozkladu a úpadku a proto živé systémy musí svoji strukturu pr b žn obnovovat.
tvrtý typ celulárních automat tuto
podmínku spl uje a z toho d vodu se tento systém stal symbolem výzkumu um lého života
- 11 -
2.6.1 Slepý hodiná
Obr. . 2.4 - p íklady možných mutací biomorf ; p evzato z [1] Jeden z prvních program , který m že být považován za um lý život, se jmenuje „Slepý hodiná “ (The Blind Watchmaker). Autorem byl Richard Dawkins v roce 1987 [6]. Tento program demonstruje ú inky genetických mutací na fenotypových formách jedinc . V programu se vyskytují graficky znázorn ní jedinci, zvaní biomorfy. Jejich vzhled je odvozen od chromozomu o devíti genech, p i emž každý gen m že nabývat hodnot od 0 do 9. Tyto geny p edur ují p edem dané vlastnosti biomorf (nap íklad délku nebo úhel ramene). Tyto hodnoty se také b hem programu m ní a to vždy u náhodn vybraných gen o jeden stupe (gen s hodnotou 5 m že zmutovat na hodnotu 4 nebo 6). Tato operace zajiš uje simulaci genové mutace. Díky mutacím se z jednoho konkrétního jedince vyvine nová generace devíti odlišných potomk . Uživatel vybere jednoho potomka, který se dál vyvíjí. Uživatel takto zastupuje roli p irozeného výb ru v p írod , ur uje který jedinec má právo p edat své genetické informace dál.
- 12 -
2.6.2 Sv t Karla Simse Další p íklad je oproti p edchozímu o mnoho složit jší, ale také o mnoho zajímav jší. Je založen na principu dodaného prost edí, kterému se r zná stvo ení (jakoby živo ichové nebo rostliny) p izp sobují a vyvíjejí se v n m. V roce 1994 Karl Sims stvo il celý um lý t ídimenzionální sv t. Jako nadefinované byly informace o prost edí (fyzikální vlastnosti), povrch sv ta a pružnost objekt . Poté jsou do tohoto sv ta vloženy zárodky um lých stvo ení, jež mají povoleno vyvíjet svá t la a nervový systém. Navíc je t mto stvo ením z d vodu zajišt ní simulace evoluce p i azen n jaký úkol (konkrétn v jedné verzi aby obsadili kostku uprost ed sv ta), aby byla zjišt na jejich zp sobilost pro další život. T la tvor jsou tvo ena z kvádr s r znými rozm ry, takže na pohled se t lo jeví jako celek pospojovaných desek. Mysli t chto tvor jsou poskládány z um lých neuron , které tvo í matematické operace, jež také prošly selekcí evoluce. Je až p ekvapující, jaké zp soby pohybu se u takovýchto tvor vyvinuly a to jak na souši tak ve vod . N kte í se pohybují ch zí, skákáním, plazením (na souši), jiní máváním ploutví, vrt ním ocasem nebo kroucením t la (v kapalin ). Jenom pohyb je vlastn
ešením
problému. A to nap íklad p edem zmín ného úkolu. Aby tvor dosáhl cíle d íve než jeho protivník, musí vyvinout lepší zp sob pohybu a ten kdo se k cíli dostane rychleji je vít zem a m že pokra ovat v evoluci. Na CD p íloze této práce je umíst no video s p íkladem pohybu t chto tvor Sims.mpg [7]. Dále jsem do CD p ílohy umístil dva .pdf dokumenty o Simsov postupu p i vývoji jedinc [8].
- 13 -
Obr. . 2.5 - p íklady genotyp a jejich zobrazení ve virtuálním sv t ; p evzato z [8]
- 14 -
Obr. . 2.6 - další p íklady Simsových tvor . Tito jsou sou ástí jeho projektu Galapagos z roku 1997; p evzato z [9]
- 15 -
2.7 Inteligence v p ístrojích – Turing v test Již p ed více než padesáti lety napsal slavný britský matematik Alan Turing lánek s názvem "Computing Machinery and Intelligence" [10], ve kterém navrhl první variantu dodnes diskutovaného Turingova testu. Jaké otázky se od dob Turinga poda ilo zodpov d t a jaké nové problémy naopak vyvstaly? Ve své p vodní podob vychází Turing v test z tzv. imita ní hry, ve které jde o to odlišit dva lidi podle pohlaví. Pozorovatel, na jehož pohlaví nezáleží, má proti sob nap . ženu a muže, který p edstírá, že je žena. Trojice lidí spolu nep ijde samoz ejm do fyzického kontaktu, sedí v odd lených místnostech a zprost edkovatel mezi nimi p enáší popsané lístky. Turing pak problém posunul: Co kdyby namísto simulace opa ného pohlaví byl imitátorem lov ka po íta ? Dokáže po íta simulovat chování ženy stejn dob e jako muž? Motivací pro vývoj um lé inteligence existovala už v polovin 20. století celá ada. Jedná se jist o obrovskou teoretickou výzvu. Zkoumání inteligence um lé nám z ejm dokáže mnoho íci o inteligenci vlastní. Dalším d vodem je prostá radost z konstrukce stále dokonalejších mechanism , která historicky sahá minimáln poslední ad zde jsou motivy ryze praktické:
ke Golemovi. A nikoliv v
adu úkol musí plnit inteligentní bytosti,
nicmén lidem se do nich p íliš nechce (jsou nap . stereotypní, nebo naopak nebezpe né). Zde bychom velmi rádi vid li myslící stroje, by jsou možné i jiné cesty - nap . roboti ízení na dálku prost ednictvím "lidského" rozhraní, cyberwaru. Jaký je stav problému padesát let poté, co jej britský matematik poprvé zformuloval? Existuje celá ada více i mén dokonalých imitací ur itých lidských inností. Známá Eliza (tento program se objevil již v roce 1966) p edstavuje program napodobující chování psychoterapeuta. Tzv. Parry je jejím prot jškem, tedy po íta ovou simulací pacienta postiženého paranoiou. Praktický význam mají tzv. expertní systémy, tedy software snažící se zastoupit nap . odborníka na burzovní prognózy i léka e stanovujícího diagnózu. Jak ukážeme dále, test jako celek se však dosud žádnému programu splnit nepoda ilo tak, aby s tím celá v decká obec souhlasila. Jaké jsou další vyhlídky? Známý vizioná a spisovatel Ray Kurzweil nedávno uzav el sázku [11] že ke spln ní podmínek Turingova testu dojde do roku 2029. Pochybující protistranou je Mitchell Kapor z Electronic Frontier Foundation. Magazín Wired ovšem sázku za adil do jedné ady s dalšími bláznivými nápady, které p icházejí na lidi ze sv ta IT. Wired v této souvislosti zmi uje - 16 -
Craiga Mundieho z Microsoftu, který se domnívá, že ve stejné dob už bude existovat komer ní provoz bezpilotních letadel. Jeden z pr kopník superpo íta
Danny Hillis se zase
vsadil, že se vesmír nebude rozpínat v n ; protistranou je v tomto p ípad Nathan Myhrvold (d íve Microsoft, nyní analytik pro oblast biotechnologií). Sou asné poznatky o temné hmot a kosmologické konstant dávají ovšem za pravdu Myhrvoldovi. Sázky tohoto druhu "spravuje" nezisková organizace Long Bets Foundation [12] . Už sám Turing v p vodním
lánku uvedl n kolik možných námitek proti celé
koncepci. Pozd ji byla ada výhrad z ejm vyvrácena, jiné p ibyly. Polemiky samoz ejm trvají. Galantn
za neme námitkou, kterou vypracovala žena, nadto se jedná o úvahu
historicky nejstarší, p edcházející samotný Turing v test o více než 100 let. Ada Lovelaceová, dcera lorda Byrona a spolupracovnice konstruktéra mechanických parních po íta
Charlese
Babaggea, p išla již v 1. polovin 19. století s tvrzením, že po íta nemyslí, protože myšlení je spojeno s p vodností. Z po íta e však dostaneme pouze modifikaci toho, co do n j vložíme. Za sou asného stavu vývoje IT není tato námitka p íliš relevantní. P edn nevíme, jak vlastn definovat onu "p vodnost" - nap . báse je taktéž variací již existujících slov, tedy de facto je ur itou kombinatorickou operací. Programy dnes již každopádn dokáží psát povídky nerozpoznatelné od t ch lidských nebo odhalit taková tajemství šachové hry, která z stávala jejich tv rc m zcela skrytá. Program tedy svým chováním dokáže své tv rce p ekvapit (nejen ve smyslu chyby), což je snad možné chápat jako ekvivalent p vodnosti. P itom pomíjíme psychologické a sociologické úvahy o tom, že ada lidí rovn ž není n jak "p vodní", aniž bychom na tomto základ mohli tvrdit, že v bec nemyslí nebo nejsou inteligentními bytostmi. Rozsáhlá literatura existuje o tzv. paradoxu ínského pokoje, s nímž p išel filozof John Searl. Searlova námitka [13] uvádí, že spln ní Turingova testu ješt nemusí znamenat n jaké myšlení a uv domování. V p vodní formulaci Searl ukazuje, že lov k m že být nap . schopný smyslupln t ídit tabulky s ínskými znaky, aniž rozumí ínsky a chápe, co text na tabulkách znamená. Podobn po íta , i když projde Turingovým testem, bude stále pouze n co imitovat a sám nebude nap . nic "chápat". Turing ovšem již ve svém p vodním lánku poznamenává, že k tomu, abychom mohli hodnotit, co po íta prožívá, bychom jím také museli sami být. Sv toznámý fyzik Stephen Hawking p ímo dodává, že má smysl posuzovat pouze jevy viditelné navenek - tedy - 17 -
inteligenci a myšlení - nikoliv kvality, které lze uvid t pouze zevnit (v domí, prožívání apod.). Podle Hawkinga prost nevíme, zda po íta má "v domí", stejn jako nevíme, zda ho budou mít p edstavitelé n jaké hypotetické mimozemské civilizace. Dokonce to jist nevíme ani v p ípad druhých lidí (jistotu máme pouze u sebe) [10]. Existuje velice zajímavý myšlenkový experiment tzv. Chalmersových zombií [14]. Zkuste si p edstavit, že všichni lidé kolem vás jsou pouze p edprogramovanými automaty, bezv domými zombiemi. Nikdy si nem žeme být jisti opakem, na v domí druhých lidí usuzujeme pouze podle jejich chování - a totéž je tedy logické init i v p ípad po íta . Z tohoto hlediska jsou Searlovy výhrady p ekonané. Zajímavé námitky proti um lé inteligenci se týkají zdánliv tak "strojového" oboru, jakým je matematika. V p vodních Turingových poznámkách se uvádí, že po íta by mohl být v testu odhalen práv tím, že ned lá chyby, eventuáln po ítá rychleji než lov k (tedy by paradoxn byl nápadný tím, že je dokonalejší). Na druhou stranu není problém ve výpo etním algoritmu použít funkci pozdržení výpo tu a implementovat na základ pravd podobnosti frekvenci špatného výpo tu, nap íklad pozm n ním znaménka a podobn . Hawking v spolupracovník Roger Penrose p išel s další matematickou námitkou, která má dokázat, že lidské myšlení má v sob krom algoritm ješt n co jiného - po íta e podle n j nejsou schopny matematického d kazu, nap . odhalit, že prvo ísel je nekone n mnoho. Penrose se domnívá, že nejde jen o otázku softwaru a výpo etní kapacity, n které matematické úlohy jsou ne ešitelné i pro obecný Turing v stroj [10]. Nastín ný problém je velmi široký a souvisí mj. s protikladem myšlení induktivního a deduktivního, taktéž se dotýká nap . Goedelových teorém
o neúplnosti matematických
systém . Penrose sám p ichází s hypotézou, že lidské myšlení nedosp je k matematickému d kazu krok za krokem, ale jakousi zkratkou, kterou on sám vysv tluje naší schopností p ijít do kontaktu s "platónským" sv tem matematických objekt . Premiéru si programy v matematických d kazech odbyly již v roce 1976, když se podílely na potvrzení d kazu " ty barev" (viz obrázek . 3.7). V rámci dokazování bylo t eba klasifikovat ur itý po et map. Úkol p esahoval lidské možnosti, po íta e jej však již tehdy zvládly - nikoliv ovšem samy od sebe, postupovaly podle instrukcí zadaných z vn jšku. D kaz ale p esto provázejí ur ité "filozofické" pochybnosti, jeden z matematik výsledek dokonce komentoval slovy: "Takže to ukazuje, že to prost nebyl dobrý problém." Cht l tím nazna it, - 18 -
že regulérní matematický d kaz by se nem l d lat vý tem prvk - a ada d kaz takto ud lat opravdu nejde. Nicmén i proti Penrosov argumentaci samoz ejm existují protinámitky, n kdy bývá dokonce pokládána za již p ekonanou (tento názor zastává nap . Paul Thagard v knize Úvod do kognitivní v dy).
Obr. . 2.7 : problém ty barev; p evzato z [10] Co se tý e praktických problém spojených s konstrukcí myslících po íta , už Turing p išel s myšlenkou program schopných se samy u it. Možná je obtížné zkonstruovat rovnou "dosp lého lov ka", uvažoval Turing, zkusme to tedy nejprve s "dít tem". Po Turingovi tyto myšlenky ožily díky experiment m, které se snažily nap . modelovat biologickou evoluci. Bun né automaty ukázaly, že i velmi komplexní systémy mohou vzniknout aplikací n kolika jednoduchých pravidel, složitost se vyno uje "sama od sebe". Pokud pro tvorbu systém um lé inteligence použijeme techniky typu genetického programování, je ovšem docela dob e možné, že p ed námi vyvstane nová erná sk í ka. Nakonec budeme mít inteligentn se chovající systém, aniž se toho ovšem mnoho dozvíme o inteligenci nás samých. Jestliže je však naším cílem p edevším praktické nasazení expertního systému, který by dokázal simulovat práci odborník , pak nám fenomén erné sk í ky zase p íliš nevadí.
- 19 -
3 Optimalizace metodou pokusu a omylu Optimalizace je termín, který je autory vykládán r zn . Bezpochyby to je proces p izp sobování systému tak, aby byly dosaženy co možná nejlepší výstupy. asto je dosažení nejlepších výsledk m jak pro ešitele tak pro výpo etní techniku beznad jné a nebo ne až tak nutné, a proto se velice asto spokojí s pouze vyhovujícím výsledkem.
3.1 Jednoduchý optimaliza ní problém ešený problém má vždy konkrétní charakteristiky, které dovolí dop edu odhadnout ohodnocení výsledku (fitness). Tato procedura obvykle za íná odhadem chyby (omylu) ešení. (nap íklad když máme vy ešit jednoduchou rovnici a p edpovíme výsledek, se kterým se bude jedna strana rovnice o deset jednotek lišit od druhé strany, pak tato chyba je deset) Chyba je faktor, který klesá s r stem ohodnocení ešení. Problém optimalizace tak m že být popsán jako procedura, p i níž se zmenšuje chyba (respektive zvyšuje ohodnocení) se stejným výsledkem. Závislost mezi chybou a ohodnocením ale není rovnom rná. Míra ohodnocení je odvrácená hodnota chyby, takže nabývá nekone na, jestliže je chyba nulová a je nedefinovaná, když je jmenovatel roven nule. V takovémto p ípad je ale už problém vy ešen a nula ve jmenovateli není p ekážkou. Další zp sob m ení ohodnocení je rozší it obor hodnot o záporná ísla a faktor chyby vynásobit (-1). Pak ím v tší ísla (blíže nule) dostáváme, tím je ešení lepší. Základní princip optimalizace metodou pokusu a omylu spo ívá, jak již název napovídá, ve zkoušení r zných hodnot. Nejprve se vybere první hodnota. Ur í se u ní faktor chyby a v závislosti na chybu se vybere hodnota následující. Jestliže hodnota první byla vybrána s velkou chybou, pak rozdíl mezi první a druhou hodnotou bude relativn zna ný. Jestliže byla chyba malá, pak je vhodné postupovat po malých krocích. D ležitá informace je také, jestli se v pr b hu procesu p ibližujeme optimu, nebo vzdalujeme. Proto se v každém kroku porovnává velikost a znaménko chyby. Jestliže se velikost zmenšuje, pak se optimu blížíme a naopak. Pokud se zm ní stav znaménka, znamená to, že byla zvolena moc velká hodnota kroku a optimum bylo p ekro eno. Porovnávání chyb (jak velikostí tak znaménka) poskytuje gradientní informace o p ibližném sm ru optima a
- 20 -
podle toho se poupravuje další zkoušená hodnota. Optimem jako takovým je vždy myšleno minimum nebo maximum optimalizované funkce a tak p i jeho hledání za poskytování pouze gradientních informací program, pokud má funkce více lokálních maxim a minim, odhalí jeden extrém. O tom, zda je tento nalezený extrém lokální nebo globální, rozhoduje, v jakém bod program zapo ne prohledávání.
3.2 Dimenze optimalizace U optimalizace se uvádí prostor parametr (parameter space). Jde o množinu která popisuje, jakých všech možných hodnot mohou prom nné problému nabývat, jinak též defini ní obor. P i ešení jednoduchých matematických rovnic s jednou prom nnou se prostor parametr jeví jako íselná osa. V p ípad úloh s více prom nnými za íná být problematika zajímav jší. Prostorem funkce (function space) se nazývá množina výsledk operací s prom nnými, ili obor hodnot. Obvyklý jednorozm rný prostor funkce je zvláštní p ípad, jak mohou být zvažovány výstupy o více rozm rech v jistém okamžiku. Nap íklad jestliže hodnotíme automobil, celkové hodnocení závisí na jeho vlastnostech, jako jsou bezpe nost, vzhled, výkon a cena. Každá z t chto vlastností je dále závislá na dalších parametrech. Hodnocení vlastnosti vzhledu bude závislé na barv , stylu provedení kapoty, ozdobných prvcích atd. Prostor ohodnocení (fitness space) je jednorozm rný. Ozna uje stupn
úsp chu
s kterými vzory parametr optimalizují hodnoty v prostoru funkce. Tyto stupn jsou vyjád eny mírou ohodnocení nebo chyby. S použitím p íkladu automobilu, tento prostor ur uje, jestli si jej koupíme nebo ne. Jestliže jsou všechny vlastnosti (bezpe nost, vzhled, výkon a cena) ustáleny, je pot eba tyto r zné funkce zkombinovat do jedné veli iny podporující rozhodování. Každý bod v prostoru parametr je namapován na práv jeden bod v prostoru funkce. Poté jsou i oboru hodnot funkce p i azeny body z prostoru ohodnocení. Ve v tšin p ípad
je možno prostor parametr
mapovat p ímo na prostor ohodnocení. V p ípad
maximalizace funkce o jedné prom nné jsou prostory funkce a ohodnocení totožné (v p ípad minimalizace jsou p evrácené), avšak je nutno mít na pam ti rozdíl mezi ob ma prostory.
- 21 -
3.3 Znázorn ní ohodnocení Pro znázorn ní výsledku optimalizace se používají tzv. krajiny ohodnocení (fitness landscapes). Jde o znázorn ní zm ny míry ohodnocení se zm nou hodnot parametr a proto vytvá í novou funkci, která je o jeden rozm r v tší, než funkce optimalizovaná. Pro znázorn ní se používají dv
vlastnosti. Bu to míra ohodnocení a nebo míra chyby.
V nejjednodušším p ípad , kdy pracujeme s rovnicí o jedné neznámé a ohodnocení vyjád íme jako : C = E * (-1) V tomto p ípad je krajina lineární. Jestliže ale použijeme vyjád ení ohodnocení jako p evrácenou hodnotu chyby, pak krajina v bod optima exponenciáln roste do nekone na, jemuž se limitn blíží. Tento bod se nazývá vrcholem ohodnocení a jasn zna í dosažené optimum. Multi-modální funkce mají více než jedno optimum. Jako jednoduchý p íklad m že posloužit rovnost x2 = 100. Krajina má pak dva vrcholy a to jak v bod x = 10, tak v bod x = (-10). Mezi t mito body se tvo í sedlo a míra ohodnocení z vrcholu x = (-10) klesá až do bodu x = 0. Zde následuje zlom a míra za ne r st až do vrcholu x = 10. V tomto p ípad m žeme zapo ít hledání na libovolné hodnot a jenom sledováním gradientu vypátráme optimum. John Holland [15] charakterizoval úkol vyhledání ešení pro složitý problém jako úkolem „optimálního rozmíst ní pokusných hodnot“. Vzhledem k tomu, že p i hledání optima je k dispozici jenom ur itý as, pak je tato myšlenka zásadním poznatkem. Pro vyhledání optima v krajin se praktikují dva r zné p ístupy. Prvním je „pr zkum“ (exploration). Prozkoumávání je termín, který ozna uje celkové prohledávání krajiny pro relativn dobrou oblast ešení. Jeho cílem je nalezení globálního optima a nebo nejlepšího lokálního optima v možném ase. Více zam eným zp sobem je „t žba“ (exploitation). Tento p ístup p i vyhledání dobré oblasti snaží najít co nejvyšší možný bod na vrcholku a tak se s blížícím optimem zkracují intervaly zkoušených hodnot. Nejb žn jší metodou je „horolezecký algoritmus“ (hill climbing), p i kterém za íná nové prohledávání, jakmile je nalezen výhodn jší výchozí bod než p edešlý. Existuje mnoho variací na schéma horolezeckého algoritmu a všechny jist najdou extrém, ale žádný jist nenajde extrém
- 22 -
globální. Práv
kompromis mezi ob ma p ístupy je st edem p edm tu hledání opravdu
dobrého algoritmu pro optimalizaci.
3.4 Vícerozm rný rozpoznávací prostor Jeden z nejzajímav jších objev
v oblasti rozpoznávání v posledních desetiletí je
spojen s po íta ovými algoritmy pro nacházení významu slov z textu. Dv skupiny v dc nezávisle na sob objevili p ístupy pro statistické odvozování významu slov podle jejich kontextu. Vše za alo v padesátých letech dvacátého století, kdy Charles Osgood, George Suci a Percy Tannebaum [16] vypátrali zp sob, jak lze rozložit slova v závislosti na jejich významu do vícerozm rného prostoru. Jejich p ístup, nazvaný „sémantický diferenciál“ (semantic differential) [17], spo íval v ohodnocení vlastností významu slov podle subjektivního pocitu hodnotícího. Tento význam byl hodnocen mnoha faktory, jak ukazuje následující ilustrativní tabulka . 3.1.
- 23 -
slovo dobré kruté ošklivé smutné negativní nep íjemné bezcenné slabé malé jemné lehké m lké submisivní jednoduché pasivní uvoln né pomalé chladné tiché matné hladké
1 1 1 1 1 1 1
ohodnocení 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4
5 5 5 5 5 5 5
špatné milé krásné š astné pozitivní p íjemné hodnotné
1 1 1 1 1 1 1
p sobení 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4
5 5 5 5 5 5 5
silné velké drsné t žké hluboké asertivní složité
1 1 1 1 1 1 1
aktivita 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4
5 5 5 5 5 5 5
aktivní napjaté rychlé horké hlu né jasné hrbolaté
Tab. 3.1 : kategorie ohodoncení slov; p evzato z [1] Evidentn se zde také uplat uje haló-efekt. Je z ejmé, že když hodnotíme jistou vlastnost kladn , tak nebude jedinou kladnou vlastností daného objektu. Z toho vyplívá, že ohodnocení nad r znými veli inami mají tendenci spolu navzájem korelovat. Tyto souvztažnosti jsou zjistitelné statistickými analytickými metodami, díky kterým byl schopen tým Charlese Osgooda ukázat, že význam slov lze roz lenit do t í rozm r . Nejd ležit jším prostorem je ohodnocení. Vlastnosti jsou zde hodnoceny jako dobré nebo špatné. Zbývající dva rozm ry p sobení a aktivita nejsou redundantní, ale už nejsou tak relevantní jako první dimenze.
- 24 -
V devadesátých letech minulého století týmy v dc
z University of Colorado a
University of California, Riverside za ali p ezkoumávat a rozši ovat výše zmín nou práci. Nejd íve odhalili z ejmou slabinu, a sice ve zp sobu výb ru cílových slov a jejich hodnocení. Výb r p vodn provád li sami v dci a u t chto slov známkovali vlastnosti. Tato skute nost vhodnost výb ru zcela zpochyb uje, jelikož oby ejní lidé myslí a vnímají zcela jinak než intelektuální elita. Tento nedostatek byl odstran n výb rem velkého množství textu, nazvaného „t lo“ (corpus), a ten byl po slovech analyzován. Konkrétn
bylo toto t lo
odebráno z diskusního serveru Usenet [18]. Psychologové Curt Burgess a Kevin Lund z Riverside zkopírovali z diskuzí Usenetu t i sta milión slov a nechali je analyzovat svým programem nazvaným HAL (hyperspace analogue to language). Program projde celým t lem a všechny slova uspo ádá jako názvy ádk a sloupc jedné obrovské matice (m la rozm r 170 000 * 170 000). Matice se zpo átku naplní nulami. Potom se prozkoumávají slova v textu a jejich sousedé (deset z každé strany). Jestliže slovo Y je p ímým sousedem námi zvoleného slova X, pak se hodnota bu ky, kde se protíná ádka slova X se sloupcem slova Y, zvedne o deset. Pokud jde o slova vzdálená dv pozice, pak se obsah bu ky zvedne o 9 a tak dále. Tak program projde celý text a vyplní matici. Samoz ejm , že p i pokusu došlo k tomu, že slova asto se vyskytující se budou reprezentována o hodn v tšími hodnotami, než slova mén
ast ji používaná. Dále byla slova, která se objevovala
velice z ídka, odstran na a vznikla tak matice o rozm rech 70 000 * 70 000, což je stále p íliš velké sousto pro efektivní operace. Kurt Bugress a Kevin Lunt dále spojili vektor sloupce a ady jednoho slova dohromady a vznikla tak ada tvo ená váhami slov, které sousedily s daným slovem v textu . Ješt byla pot eba adu jakýmkoliv zp sobem zten it. Po bližším prozkoumání se zdálo, že mnohá slova nejsou pro provád nou analýzu v bec relevantní. Z tohoto d vodu spoustu slov z ad bylo vypušt no a bylo zachováno jen dv
st
nejd ležit jších slov z celé ady o p vodní délce sedmdesáti tisíc hodnot. Tak vzniklo sedmdesát tisíc ad o délce dv st . Každá ada ozna uje jedno slovo a hodnoty v ad
míry výskytu v sousedství ostatních slov. Každé slovo je tím pádem
reprezentováno 200-rozm rným vektorem . Nakonec Kurt Burgess a jeho tým znázornili každé slovo ve dvourozm rném prostoru za použití techniky vícerozm rné zm ny m ítka. V dci objevili, že slova podobného významu jsou vázána ke stejným oblastem sémantického prostoru. - 25 -
Podobná práce probíhala sou asn na Colorádské univerzit . Pracovali na ní Thomas Landauer a Susan Dumais. Jejich výsledkem bylo paradigma pojmenované „Latentní sémantická analýza“ (Latent Semantic Analysis – LSA) [19]. Tato analýza využívá k nalezení shluk slov statistickou metodu rozkladu singulární hodnoty, ale výsledek je v podstat stejný jako u p edcházející metody. Využití vícerozm rného sémantického prostoru pro znázorn ní významu slov tak umož uje pohled zespoda nahoru (bottom-up) na celou strukturu jazyka.
3.5 NK krajiny V p ípadech, kdy jsou prom nné navzájem nezávislé, je optimalizace relativn jednoduchou záležitostí. V mnoha p ípadech jsou ale prom nné navzájem závislé a ovlivn ní jedné za ú elem lepšího výsledku má za následek zhoršení situace u ostatních. Podle Stuarta Kaufmanna [1] ovliv ují složitost problému dv veli iny. Jsou jimi veli ina N, která vyjad uje po et prom nných problému, a veli ina K, jejíž velikost zna í množství závislostních propojení mezi prom nnými. K je definováno jako po et vstup
do každé prom nné od
prom nných ostatních. Tato veli ina se nazývá epistáze (epistasis). Tento termín byl p evzat z genetiky, kde je asté, že gen na jedné stran chromozómu ovliv uje gen na stran druhé Pro p ípad zjednodušení budeme uvažovat, že každá prom nná m že nabývat stavu 0 nebo 1. Pokud jsou komponenty navzájem nezávislé, K = 0, pak po et krok pro optimalizaci je roven po tu prom nných. V každém kroku se zam ní u jedné prom nné hodnota a pokud se míra ohodnocení celku zvýšila, p ejde se na další. Pokud se míra ohodnocení naopak snížila, hodnota se vrátí na p vodní. Tento postup se nazývá „hladový algoritmus“ (greedy algorithm). Pokud je K=1, pak stav každé prom nné závisí na její vlastní hodnot a na stavu prom nné, jíž je ovlivn na. Pro získání optimálního stavu je zapot ebí více než N krok . Je zcela b žné, že p i zlepšení situace jedné prom nné se situace druhé zhorší a naopak. Pro úsp ch je nutné najít nejlepší stavy všech dvojic, které se ovliv ují, a teprve poté ešit optimalizaci celku. Typický problém s hodnotou K=1 znázor uje obrázek 1.
- 26 -
Obr. 3.1 : typický problém o p ti prom nných s mírou závislosti K=1 Pokud hodnota K nabývá dvou, pak stav každé prom nné závisí na její vlastní hodnot a stavu dalších dvou prom nných, na kterých je závislá. Všeobecn platí, že velikost tabulky, která znázor uje všechny možné kombinace hodnot a stavy komponent, má po et ádk roven L = N*2(K+1) V tomto p ípad tedy po et prom nných vynásobený osmi. Takto lze popsat složitost každého existujícího systému. Pokud ale problém rozši ujeme, záhy se stane vzhledem k množstvím kombinací ne ešitelným a jediným ešením je op t zúžení výb ru na co možná nejperspektivn jší hodnoty defini ního oboru, které jsou optimem, nebo se nacházejí v jeho okolí.
3.6 Kombinatorická optimalizace Optimalizace problém s prom nnými, které nabývají diskrétních hodnot, je podstatn odlišná od optimalizace kvantitativních nebo numerických problém . Kombinatorická optimalizace je áste n spojována s um lou inteligencí a hlavn s problémy, kdy je cílem uspo ádat n jaké p íkazy tak, aby odpovídaly jisté logice a bylo jimi dosaženo p edem daného úkolu. Takovéto uspo ádávání logických celk úkonu je problém, který eší kombinatorické optimalizace.
- 27 -
Vyjád ením cíle optimaliza ního problému je „cílová funkce“ (objective function). V p ípad sv toznámého problému obchodního cestujícího je cílovou funkcí najít takovou cestu, aby prošla všemi m sty, byla co nejkratší a aby kon ila ve stejném bod , kde za ala. Pokud k ešení použijeme permutací, dostaneme sice všechny možné varianty potenciálního ešení, ale po et permutací z n prvk
je n! a tak velikost prohledávaného
prostoru rapidn roste. Už jenom p i po tu deseti prvk vznikne problém, který má 3 628 800 možných permutací. Takové množství ješt není pro dnešní techniku velkým problémem, ale p i v tším množství prvk , nap íklad sto, už je sou asná technika p íliš pomalá a konce prohledání by se nedožil žádný sou asn žijící lov k. Proto je op t nutné p ijít na zp sob, jak otestovat co nejmenší po et možností a dosáhnout optima. Pro
prezentaci
prohledávaných
prostor
se
používají
stromy,
nazývají
se
prohledávacími stromy, a úkolem optimalizace je najít nejkratší možnou cestu práv takovýmto stromem. Pro prohledávání se používají dva nejrozší en jší algoritmy. Prohledávání do ší ky (breadth-first search) a do hloubky (depth-first search). Prohledávání do ší ky prochází postupn po úrovních všechny v tve stromu, kdežto prohledávání do hloubky projde nejd íve jednu celou v tev, najde tak jedno možné ešení, pak se vrátí k poslednímu uzlu, kde se cesty rozv tvují a pokra uje druhou cestou.
Obr. 3.2 : prohledávací strom kombinatorického problému o ty ech prvcích; p evzato z [1]
- 28 -
Heuristika by se dala uvést jako vylepšení prohledávací strategie, které eliminuje z prohledávaného prostoru možnosti, o kterých lze s jistotou íci, že nevedou k optimálnímu výsledku. P i prohledávání do ší ky se dá heuristika používat následovn . Pokud používáme strom z obrázku 3.2 a máme za úkol najít nejkratší cestu mezi vrcholy A,B,C a D, pak se musíme rozhodnout, jakým vrcholem za ít. Prohledávání se z pravidla ídí podle abecedy a tak zapo ne ve vrcholu A první úrovn . Prohledá všechny cesty z A první úrovn ke všem jeho následník m . Poté p ejde na vrchol B v první úrovni u kterého op t otestuje cesty ke všem jeho následník m a pokra uje na vrcholu C v první úrovni. Už v tomto kroku lze porovnat vzdálenosti z vrcholu A a B k jejich následník m a pokud jsou u n které z porovnávaných vrchol oproti ostatním o mnoho v tší tak, že je jist m žeme ozna it za nevedoucí k ešení, jednoduše už tyto vrcholy dále neuvažujeme a jakoby je ze stromu odebereme i s jejich následníky. B hem prohledávání do hloubky se lze vyhnout zbyte ným úkon m tak, že když práv prohledávaná cesta dosáhne v tší délky, než jakákoliv, která je již prohledaná, pak tuto cestu p estane prohledávací algoritmus uvažovat jako vedoucí k ešení a p ejde na další možnou.
3.7 Binární optimalizace Binární optimalizace je druh optimalizace kombinatorické. Platí zde jedna podmínka a sice, že prom nné nabývají binárních hodnot, jedni ky nebo nuly. Binární kódování má jisté výhody.
Jeho mnohostrannost umož uje ve dvojkové soustav
implementovat cokoliv
s požadovanou p esností. Binárního et zce lze používat jak pro numerické tak kvalitativní vyjád ení. Numerické vyjád ení se používá pro vyjád ení íselné hodnoty, která se získá p evodem binárního et zce z dvojkové na desítkovou íselnou soustavu. Nap íklad et zec 1010 v binární soustav
odpovídá
íslu 10 v soustav
desítkové. Kvalitativní vyjád ení
ozna uje hodnoty (jejich existenci nebo neexistenci) p edem daných vlastností. Nap íklad p i popisu docházky na seminá by et zec 1010 mohl znamenat, že pan Novák byl p ítomen, pan Slezák ne, pan Vágner byl a pan Šnobl nebyl. Jediné ztížení p i použití takovýchto et zc nastává v nutnosti rozlišení, jestli se jedná o numerický i kvalitativní et zec.
- 29 -
Množství možných kombinací bit v et zci se s každým dalším bitem zdvojnásobuje. Proto velikost celého prostoru je 2N, kde N je po et bit v et zci, neboli také N je rozm r tohoto prostoru. Prostor, který odpovídá et zci o jednom bitu je tudíž jednorozm rný a je znázor ován za pomocí úse ky. Na koncích úse ky jsou hodnoty jedna a nula a p edstavují tak stavy, kterých m že et zec nabývat, jak ukazuje obrázek 3.3.
Obr. 3.3 : úse ka znázor ující binární et zec o jednom bitu P i dvou rozm rech je prostor reprezentován tvercem, jehož rohy p edstavují všechny kombinace, jakých m že et zec s dv ma bity nabývat.
Obr. 3.4 : tverec znázor ující binární et zec o dvou bitech Pro t i rozm ry se používá pro znázorn ní pravidelná krychle. Prostor se rozší il o hloubku a jednotlivé konkrétní et zce jsou reprezentovány na rozích této krychle.
- 30 -
Obr. 3.5 : krychle znázor ující binární et zec o t ech bitech Je-li pot eba znázornit vícerozm rný prostor než t í, používá se útvaru, jež je znám jako hyperkrychle. Ta má stejné charakteristiky jako p i znázorn ní t írozm rného prostoru a tak na jejích rozích op t nalezneme jednotlivé binární et zce s konkrétními hodnotami. P i znázorn ní prostoru o
ty ech rozm rech hyperkrychle p ipomíná krychli vno enou do
krychle.
Obr. 3.6 : hyperkrychle znázor ující binární et zec o ty ech bitech
- 31 -
Použití znázorn ní geometrickými tvary má za výhodu jednu užite nou vlastnost. Pokud jsou dva stavy et zce mezi sebou p ímo propojeny (nap íklad hranou krychle), lze z jednoho stavu pozm n ním hodnoty jednoho bitu dosáhnout stavu druhého. Pokud mezi sebou propojeny p ímo nejsou, po et pozic, ve kterých se liší, nám vypovídá o jejich vzájemné vzdálenosti mezi sebou na použitém t lese, a už je to krychle, nebo hyperkrychle. Tato vzdálenost se nazývá „Hammingova vzdálenost“ (Hamming distance) [1] a zna í jak míru odlišnosti tak vzdálenost mezi porovnávanými et zci. Dále udává po et krok , který musí algoritmus provést, aby se p emístil z jednoho stavu do druhého.
3.7.1 Náhodné a hladové prohledávání Velikost binárního prostoru roste exponenciáln s r stem po tu prom nných (bit ). Jenom dvaceti p ti bitový problém skrývá neuv itelných 33 554 432 možností. Aby byl postup prohledávání rychlý a elegantní, musí poznat, kde hledat a neuvažovat neperspektivní možnosti. První otázkou je kde za ít. Lidský smysl pro uspo ádanost nám velí zažít od za átku a nebo od konce. To znamená, nap íklad u deseti bitového problému, že bychom za ali na hodnot 0000000000 nebo 1111111111 a postupn p echázeli mezi možnostmi, až bychom našli tu pravou. Pokud se ale ešení bude nacházet na opa né stran , než na jaké jsme zapo ali hledání, nezbude nám jiná možnost, než projít nap í celou hyperkrychlí. Jako logické se potom jeví poznatek, že nejlepší je za ít n kde uprost ed. To znamená v našem p ípad , že za neme prohledávání na hodnot
et zce, který obsahuje p t nul a p t jedni ek s náhodným
po adím. Zapo ali bychom tedy nap íklad na hodnot 1001011010. Pokud neznáme žádné další podrobnosti o ešeném problému, lze použít p ístup zvaný „vygeneruj a otestuj“ (generate and test). Tato „strategie“ využívá generátor pseudonáhodných
ísel. Vygeneruje náhodný binární
et zec o požadované délce a otestuje
ohodnocení takovéhoto ešení. V pam ti si uchovává nejperspektivn jší již vygenerovaný et zec a ten po p edem daném po tu krok (generování a otestování) p edloží jako nejlepší nalezené ešení. Samoz ejm se od takovéhoto p ístupu nedají o ekávat oslnivé výsledky a pro rozsáhlejší binární prostory je tento postup zcela nevhodné používat.
- 32 -
Dalším p ístupen s použitím náhodných veli in se nazývá „náhodný pr chod“ (random walk) prostorem problému. Tento algoritmus na po átku vygeneruje náhodný
et zec
požadované délky. Pak v každém dalším kroku na náhodné pozici et zce zm ní hodnotu práv jednoho bitu. Otestuje ohodnocení nov vzniklého ešení a pokud je v tší než všechny již p edem zjišt né, pak si jej uloží do pam ti. Po p edem daném po tu kroku op t kon í a nabídne nejlepší ešení, které našel. Pokud si pr b h tohoto algoritmu p edstavíme na výše znázorn né hyperkrychli, bude pr chod vypadat velice chaoticky. Rovn ž tento postup není velice efektivní. Další je „hladový“ (greedy) p ístup. P i tomto postupu se na po átku vygeneruje et zec s náhodnými hodnotami. Algoritmus pak u každé pozice p em ní hodnotu bitu a et zec p ehodnotí. Pokud nov vzniklý et zec bude lepší než p edešlý, pak algoritmus p ejde na další bit. Pokud byl p vodní et zec výhodn jší, pak algoritmus hodnotu bitu vrátí (jakoby nic nezm ní) a pokra uje na další pozici. Takto projde každý bit et zce a p edá nejlepší variantu et zce. Pro každý bit (prvek) musí algoritmus n co vykonat a tak množství operací, které se musí vykonat se rovná po tu prvk a tudíž O = (n). Tento algoritmus ale nejde použít vždy. Pokud jsou prom nné navzájem závislé není možno tento postup aplikovat. Tento p ístup se používá jen u malých a jednoduchých systém .
3.7.2 Horolezecký algoritmus (Hill Climbing) Tato prohledávací strategie je variantou náhodného pr chodu prostorem problému, která pozm uje za chodu schéma prohledávání, p ijímá zm ny, pokud vedou k vylepšení a ty pak aplikuje a vytvo í tak nové schéma pr chodu. Stuart Kaufmann tento zp sob nazývá „p izp sobivý náhodný pr chod“ (adaptive random walk). V první interakci se nastaví „práh pravd podobnosti“ (probability threshold). Dejme tomu 0.1, tedy 10 %. Toto íslo udává s jakou pravd podobností se zm ní hodnota aktuálního bitu. Pro každý bit et zce se vygeneruje náhodné íslo v rozmezí nula až jedna a pokud je vygenerované íslo menší než práh pravd podobnosti, pak se u daného bitu zm ní hodnota. Nakonec se ohodnotí celý et zec a pokud je lepší, než p edchozí et zec, je uchován pro další zpracování. Pokud není, algoritmus se vrátí k p edešlému et zci. Z tohoto d vodu se nalézané ohodnocení vždy zvyšuje a proto také se tento postup nazývá horolezecký algoritmus.
- 33 -
Ovšem i tento p ístup má svá úskalí. V p ípad že je „míra zm ny“ (mutation rate) relativn malá, nap íklad že se v pr m ru b hem jedné interakce zm ní hodnota jen jednoho bitu, pak algoritmus sice postupem asu nalezne maximum (respektive minimum), ale tento nalezený extrém je pouze lokální. Aby se algoritmus neomezoval jen na jeden lokální extrém je nutno míru zm ny zv tšit. To umožní algoritmu p eskakovat z jednoho „kopce“ prohledávané krajiny na druhý. M ítkem, jak zjistit jak velké okolí je algoritmus schopen prohledat, je Hammingova vzdálenost mezi stavy et zce v úsp šných interakcích. Celý tento p ístup je kompromisem mezi dv ma zp soby prohledávání. Mezi „pr zkumem“ a „t žbou“. Náhodný pr chod skv le projde prostorem a testuje jeden region za druhým, ale je naprosto nevhodný pro nalezení extrému. Na druhou stranu horolezecký algoritmus spolehliv najde nejlepší ešení ve svém opera ním regionu, ale není použitelný pro prohledávání region nových.
3.7.3 Simulované žíhání (Simulated Annealing) Pod tímto názvem je známa jedna z nejsiln jších metod binární optimalizace. Tato metoda získala název od procesu ustalování molekul v hmot
b hem chladnutí, až po
vytvo ení krystalické m ížky (v našem p ípad optima). Simulované žíhání p evzalo hlavní nápad z metody slézání kopce do kterého bylo p idáno stochastické rozhodování a „chladnoucí schéma“ (cooling schedule). Binární et zec je pozm ován zm nou hodnoty vybraných bit a pokud je upravený et zec lepší, nahradí p vodní. V p ípad , že je nový et zec horší než p vodní, nemusí být nutn zamítnut. I ten je vybrán, pokud projde testem náhody. Zde je práh pravd podobnosti použit jako funkce p edstavující jakoby teplotu celku (který se v ase zmenšuje). Jistá výhoda tohoto použití tkví v tom, že algoritmus zpo átku prochází široce prostor problému po lokálních „kopcích“ a postupem asu se zam uje na více perspektivní regiony prostoru problému.
3.7.4 Binární a Grayovo kódování P i procházení binárních prostor v dci objevili zajímavý problém. A sice jestliže program bude pot ebovat p ejít z hodnoty nap íklad 15 (01111) na hodnotu 16 (10000), pak Hammingova vzdálenost ve dvojkové soustav t chto po sob jdoucích ísel je p t. Tyto úkazy se v prostoru problému vyskytují jako „Hammingovy útesy“ (Hamming cliffs). Aby se - 34 -
t mto jev m zamezilo, používá se Grayovo kódování, které tento nedostatek eší p i zachování platností operací s binárními ísly. Prakticky umož uje toto kódování p epsat ísla do et zc z jedni ek a nul tak, aby Hammingova vzdálenost mezi následujícími ísly byla rovna jedné. Algoritmus pro vytvo ení je následující. Máme binární et zec B a Bi zna í i-tý bit v binárním et zci. Výsledný et zec bude G, kde Gi znamená taktéž i-tý bit ve výsledném et zci. Platí, že : Gi = Bi XOR B(i-1) V tabulce . 4.2. je uvedeno prvních patnáct hodnot p irozených ísel v binárním a Greyov kódování. desítková soustava 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
dvojková soustava 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Greyovo kódování 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Tab. 3.2 : binární a Greyovo kódování; p evzato z [1]
- 35 -
4 Sociální organismy Dodnes se v dci neshodli na teorii vzniku života na Zemi, tak aby tato teorie byla p ijatelná pro všechny. P i hledání odpov di na tuto filozofickou otázku dochází ke st etu dvou zcela zásadn odlišných p ístup k poznání. Na jedné stran stojí materialismus a na stran druhé víra. Každý máme právo na svoji víru a každý lov k pot ebuje v n co v it. A už jde o boha, Alláha nebo jakékoliv jiné bohy i hodnoty. Tato esenciální lidská vlastnost je v ná a její zásluhou vznikají více i mén neuv itelné p íb hy o stvo ení sv ta. Každý jist známe k es anskou verzi o týdenním tvo ení, ale mnohem zajímav jší je nap íklad vznik sv ta podle severského náboženství. Podle seve an nejd íve existovaly dva b ehy, jeden ohnivý a druhý ledový, a mezi nimi bezedná propast. Postupn pak ohnivý b eh p evážil nad ledovým tak, že ten celý roztál, a celou propast vyplnil vodou. Z té vznikli první severští bohové.
4.1 Pohledy na evoluci Naše planeta vznikla p ibližn p ed 4,5 miliardami let a první známky života se datují do doby p ed 3,45 miliardami let. V té dob byla naše planeta velmi nehostinným místem. Formování povrchu m lo na sv domí stovky inných sopek, které chrlily do atmosféry množství jedovatých plyn . Uran 235 byl padesátkrát bohatší, než jak jej známe dnes a tak i množství radiace nebylo zanedbatelné. Práv v takovýchto podmínkách se za al vyvíjet život. Složitost tehdejších organism se pohybovala na úrovni molekul, ale i p esto byly schopni reprodukce a s reprodukcí p išla i mutace. U n kterých jedinc zm na p ivedla zlepšení jejich situace, jiným zp sobila smrt. P íroda tak na sebe p evzala roli p irozeného soudce, který rozhoduje o právu na život, a tím pádem i roli ukazatele sm ru vývoje organism na Zemi.
4.1.1 Hypotéza Gaia Naší celou planetu lze s dávkou p edstavivosti považovat za jeden velký organismus. Stavebními prvky tohoto organismu jsou rostliny a zví ata, vyskytující se na Zemi, která plní svoje funkce jako bu ky v našem t le. Je také možné vnímat druhy rostlin a zví at jako jeden distribuovaný organismus, který je tvo en jedinci, jež jsou nositeli a propagátory svojí genetické informace. Pokud se zam íme ješt hloub ji, z poznatk biologie m žeme s jistotou
- 36 -
íci, že i každý jedinec je celek jistých
ástí. Takto bychom mohli neustále zvyšovat
rozpoznávací schopnost a skon ili bychom až na úrovni atom . Hypotézu o Zemi jako jednom obrovském organismu jako první vyslovil v osmnáctém století James Hutton. Tento v dec je považován za otce geologie a domníval se, že Zemi, jakožto jeden velký organismus, je možno zkoumat metodami rozkládající fyziologii. O dv st let pozd ji na Jamese Huttona navázal anglický chemik James Lovelock a tento pohled nazval „hypotéza Gaia“ (Gaia hypothesis). [1] Také v roce 1972 napsal v akademickém asopisu Atmospheric Environment slavné kontroverzní tvrzení : „Život nebo biosféra reguluje a udržuje klima a složení atmosféry v optimu pro sebe sama.“
4.1.2 Sv t sedmikrásek Lovelock demonstroval teorii Gaia a její dynami nost na po íta ové simulaci, kterou pojmenoval „Sv t sedmikrásek“ (Daisyworld). [1] Daisyworld znázor uje virtuální planetu, která sousedí se sluncem a na níž rostou t i druhy sedmikrásek (daises). Jsou to tmavé, šedivé a sv tlé sedmikrásky. Z po átku simulace modelu, kdy okolní slunce ješt nedosáhlo plného žáru, jsou nejlépe situované tmavé sedmikrásky. Za nou se množit rychleji než ostatní druhy a obsadí v tšinu povrchu planety. Jak se tyto rostliny rozší í po povrchu, za nou absorbovat teplo planety a tím jí i ochlazují. Tudíž planeta by bez t chto rostlin m la v tší teplotu, než s populací sedmikrásek. Tmavý druh takto bude ovládat v tšinu povrchu, dokud klima pro n j neza ne být moc teplé. Poté populace tohoto druhu rapidn klesne a nastane éra sv tlejších druh . Ty se mohou díky tmavým sedmikráskám, které jim p ipravily ideální prost edí, za ít intenzivn rozmnožovat. Šedivé a sv tlé druhy ochlazují planetu tím, že dopadající sv tlo odrážejí a tak se rozdíl mezi teplotou planety s populací sedmikrásek a bez ní neustále zv tšuje. Jakmile blízké slunce dosáhne plné síly, jsou ideální podmínky pro sv tlé sedmikrásky. Práv ony se nakonec stanou nejzastoupen jším druhem a nadále udržují teplotu planety a celou biosféru v optimálním stavu. Tato simulace je na po átku ovlivn na mnoha parametry. Mezi nejrelevantn jší pat í nap íklad po áte ní teplota planety, po et druh
a množství tepla vydávaného okolním
sluncem. Výsledek této simulace vypovídá o tom, že a zvolíme jakoukoliv kombinaci rozložení druh sedmikrásek na planet , celý systém biosféry bude populací regulován a teplota planety se bude pohybovat v ur itém rozsahu. V rozsahu jež obsahuje optimální stav.
- 37 -
4.1.3 Diferenciální selekce V roce 1962 skotský ekolog Vero C. Wynne-Edwards vyslovil myšlenku, že evoluce vybírá opat ení proti zví at m, která se množí až moc a tak hrozí p emnožení a vymírání druh . Wynne-Edwards poznamenal [1] : „Experiment hlavn ukázal, že hodn , ne-li všechny, druhy vyšších zví at mohou omezit hustotu jejich populací. Nejd ležit jší ze všeho je, že jsme našli tyto samoregula ní homeostatické metody, které jsou natolik univerzálními operacemi, že neprobíhají jen za experimentálních podmínek, ale i v p irozeném prost edí zkoumaných zví at.“ Díky tomuto poznatku mohou být vysv tleny jevy, které p edtím vysv tleny nebyly, jako nap íklad spole né p ehlídky zví at, hlasité vydávání zvuk celou skupinou a zimní sesedací sešlosti. Díky t mto událostem mohou
lenové zví ecích druh
zjistit jejich
zastoupení a tomuto faktu p izp sobit míru reprodukce tak, aby stav jejich populace nadále vyhovoval optimálnímu stavu a nezp sobil p írodní katastrofu zp sobenou jejich p emnožením. Vyskytuje se zde ovšem jeden paradox. Jedinec se musí dobrovoln vzdát svého práva na rozmnožování. Na první pohled by se mohlo zdát, že genetická informace tohoto jedince zcela zanikne, ale pravda je taková, že v t chto p ípadech jsou ob ti podstupovány pro jedincovy p ímé p íbuzné. Ti v sob nesou alespo
ást jedincovy genetické výbavy a tak, i
když ne celá, bude jeho informace p edána dál. Na druhou stranu se i jedinec, který vstoupí do rozmnožovací procesu, vystavuje nezanedbatelnému nebezpe í. Zví ata v dob pá ení jsou velice zranitelná. A to a už p ímo p i pohlavním aktu, tak v dob b ezosti. Matka je mén pohyblivá a musí zajistit více potravy i pro vyvíjející se potomky. V p írod lze takovýchto p ípad
sebeob tování nalézt bezpo et. Nap íklad matka chránící mlá ata p ed dravcem
riskuje sv j život, aby predátora odlákala a tak ochránila potomky. Darwin také zkoumal rozdíly mezi pohlavími u téhož druhu. Výsledky zkoumání se zdají být paradoxní. Nap íklad sloní samec váží ty ikrát více než samice. Vyvstává otázka, jak se mohl vyvinout takový rozdíl v t lesné váze, když aby druh p ežil, musela ob pohlaví žít ve stejném prost edí a tudíž elit stejným problém m a tím pádem se i stejn vyvíjet. Samc m n kterých druh se b hem evoluce vyvinuly obrovské kly jako znamení síly nebo - 38 -
okrasné ope ení pro zd razn ní jedince, aby zap sobil na sami ku. Tyto znaky zcela o ividn zt žují jedincovu schopnost uniknout p ed dravcem. Darwin jako odpov
na tyto paradoxy
vytvo il druhou evolu ní teorii, která pokrývá evoluci pohlavních charakteristik jedinc . P estože zpo átku nebyla tato teorie p ijímána, dnes je „teorie sexuálního výb ru“ (theory of sexual selection) považována za d ležitou sou ást evolu ní teorie. Dále je patrné, že investice do reprodukce se liší podle pohlaví a to zvlášt u druh , kde je dlouhé t hotenství a narozená mlá ata jsou bezbranná. Sami ky preferují samce, kte í jim mohou poskytnout úto išt a ochranu. Naopak samci preferují samice, které mají t lesné proporce p íznivé pro rození potomk . A protože, kdo je matkou, je jisté, ale, kdo je otcem, je ve v tšin p ípad nejisté, tak je snahou samc si u svojí partnerky vydobýt dlouhodobý závazek. Na druhou stranu, pokud je samec schopen oplodnit více sami ek, pak je na n j vyvíjen menší tlak být pro sami ku výjime ný. Tento fenomén je pojmenován „Coolidg v efekt“ (Coolidge efect) a je ilustrován jednou úsm vnou p íhodou. Prezident Spojených stát amerických byl na výlet se svojí ženou na farm . První dáma si prohlížela farmu doprovázena zdejším farmá em. P i návšt v výb hu se slepicemi se místní farmá zmínil, že kohouti jsou schopni kopulovat mnohokrát b hem jednoho dne. Na ež první dáma požádala pr vodce : „Prosím, zmi te se o tomto panu prezidentovi“. Když byl pan prezident Calvin Coolidge na prohlídce stejného místa, poslušný pr vodce mu zopakoval o co ho první dáma požádala. Prezident se po chvíli optal : „A pokaždé se stejnou slepicí?“. Farmá odpov d l : „Pro ? Ne.“, na ež pan prezident : „Prosím, zmi te se o tom paní Coolidgeové“. V roce 1990 v dci Bert Hölldobler a Edward O. Wilson [20] dokazovali, že na mraven í kolonii by m lo být pohlíženo jako na jeden organismus. A abychom se dozv d li n co o jejich chování, musíme tudíž na kolonii pohlížet jako na jeden celek. U n kterých druh mravenc je míra úmrtnosti dokonce šest procent populace za den a tak je z ejmé, že u t chto druh zkoumání konkrétního jedince nenabízí velký p ínos. U hmyzu z ádu blanok ídlí (hymenoptera) (pat í sem mravenci, termiti, v ely a vosy) je zajímavá jedna vlastnost. A sice až otrocká pod ízenost jedince k jeho kolonii. Hamilton zjistil, že živo ichové tohoto ádu se rozmnožují haplodiploidní metodou. Sami ky zd dí p lku svých alel od své matky. Tudíž jedna tvrtina gen , které dv sestry zd dí po matce, budou stejné. Hmyzí samci vyr stají z neoplodn ných vají ek a tak všichni získají stejnou - 39 -
genetickou výbavu od své matky, královny. Dále sam í pohlavní bu ky vznikají d lením (mitózou) a tak zde neexistuje zp sob, jakým by mohlo dojít k odlišení genetické výbavy jednoho jedince od výbavy jedince druhého. Díky tomuto získají všechny nové sami ky od otc stejnou genetickou výbavu. Z tohoto d vodu sterilní d lnice rad ji než aby hledaly, jak p edat dál svojí genetickou výbavu, rad ji slouží královn a tak zvyšují šanci na úsp ch gen , které jsou stejné jako ty jejich. Jeden pohled na teorii evoluce byl popsán ve druhé kapitole. Jedná se o pohled Richarda Dawkinsna, který byl publikován v knihách The Selfish Gene (1976) a The Blind Watchmaker (1985) (kapitola 2.3 a 2.6.1). Ross Buck a Benson Ginsburg mají však jiný názor na evoluci sociálního chování [1]. Domnívají se, že spole enství vyžaduje komunikaci, která má vrozené základy v projevech organism . Tento sv j pohled dávají do kontrastu s „hypotézou sobeckého genu“ (The Selfish Gene hypothesis). Zatímco Dawkins nazna uje, že komunikace je vrozen manipulovatelná a využitelná, tak podle Bucka a Ginsbrucka sociální komunikace tvo í základ, jež umož uje organism m podporovat p ežití druhu. Buck a Ginsbruck tvrdí, že „základní p íbuzenský fenomén“ (general affiliative phenomenon) je obsažen už v samotné protoplazm , elementárním znaku všech živých v cí. Sociální a emotivní komunikace byla popsána Darwinem jako nástroj pro vytvo ení a udržování spole enského ádu. Buck a Ginsbruck oponují, že spontánní komunikace existuje ve všech živých tvorech ve form základní spole enské znalosti, která je neproporcionální a p ímá. Nap íklad zví e ví, jestli je jiné zví e naštvané. Tato znalost je p ímá, není to nic, co si musí zví e nejd íve uv domit.
4.1.4 Teorie vnit ního symbiontu Tato teorie se zam uje na prvky v bu kách zvané mitochondrie. Mitochondrie se vyskytují ve všech živo išných eukariotických bu kách a jsou jakousi „bu kou v bu ce“. Vztah bu ky a mitochondrie je kardinality 1 : N. Tyto organely jsou tvo eny dv ma membránami a pomáhají bu ce spalovat cukry a tím dodávají bu ce energii. V rostlinách jsou ekvivalentem mitochondrií chloroplasty, které p etvá ejí sv telnou energii na energii ukrytou v cukrech. Jde o projev fotosyntézy. „Teorie vnit ního symbiontu“ (endosymbiont theory) íká, že tyto organely byly p vodn formou bakterií, které postupn pronikly do rostlin a živo ich b hem po áte ních
- 40 -
fází evoluce. Jak mitochondrie tak chloroplasty si vytvá ejí svojí vlastní genetickou výbavu, která je odlišná od DNA nebo RNA hostitelské bu ky, a dokonce provád jí i syntézu n kterých bílkovin. Nejenom že se pohybují uvnit bu ky a m ní tvar, tyto organely dokonce ovládají svoje rozmnožování. P i pohlavním rozmnožování bylo vypozorováno, že genetická informace organely pochází z bu ky matky, nikoliv však otce. Analýzy genetické informace organely ukázaly, že tato genetická informace pochází z primitivní formy bakterií. V díle „Životy bu ky“ (Lives of Cell) z roku 1974 od Thomase Lewise autor prohlašuje, že to, co my nazýváme organismem, je pouhý stroj pro propagování „nad azené rasy“ a to mitochondrií a chloroplast [1]. Pro každého z nás je pak úkolem dodávat t mto organelám živiny a žijeme proto, abychom p edali dál jejich genetickou informaci dalším generacím. A tudíž je od nás požadováno, abychom se p izp sobovali okolnostem, p ežili a rozmnožovali se. A už je naše role v p írod
jakákoliv, zahrnuje schopnost minimalizovat chybu
v procesu p izp sobování se prost edí. Jakmile se objeví p ekážka, n které druhy skoro vždy naleznou cestu jak danou p ekážku obejít. Lidé se dokázali i bez techniky p izp sobit tak ka každému prost edí na Zemi za pomoci využití dostupných zdroj . Naše schopnost myšlení, inteligence, nám dovoluje zvyšovat šanci na p ežití a po etí potomk .
4.2 Sociální chování jako optimalizace Samotná evoluce se zcela o ividn chová jako optimalizace. Jde o proces, kdy se jedinci p izp sobují danému prost edí a situaci. P izp sobují se proto, aby co nejvíce zvýšili svoji šanci na p ežití a p edání svojí genetické informace. A práv díky mutaci, kombinování a výb ru gen , které probíhají b hem evoluce, je tato metoda optimalizace schopna usp t i na krajinách velmi složitých problém . Mutace a kombinování gen zajiš ují možnost nalezení zcela nového ešení. Výb r gen naopak rozhoduje mezi dv ma geny a vybere pro reprodukci ten lepší. Úsp šná ešení problému jsou tak uchovávána a postupn se z nich vyvíjejí ešení ješt lepší. Schopnost vykazovat náhodné chování je pro organismy velice relevantní. Díky náhodnému chování je jedinec schopen snáze uniknout dravci. Jeho budoucí pohyb nelze p edpovídat a tak tato vlastnost zvyšuje jeho šance na únik p ed predátorem. Tato vlastnost ješt vylepšuje jednu innost a tou je hledání. A už jídla, partnera nebo místa pro hnízdo.
- 41 -
Jsou dva druhy spole enství, která živo ichové vytvá ejí. Jeden druh tvo í monogamní pár. Výhodou v tomto uspo ádání je vyšší šance pro vychování potomka, protože se o n j starají oba rodi e, a vyšší schopnost ubránit hnízdo. Druhým je skupina. Skupiny vznikly v moment , kdy byl same ek schopen oplodnit více sami ek, a tudíž lenové skupiny vykazují polygamní chování. Zcela z ejmou výhodou je, že každý jedinec najde partnera pro pá ení. Na druhou stranu v takovýchto skupinách vznikají spory o v d í postavení jedince a soupe ení m že kon it i smrtí jednoho ze zú astn ných. Zví ata žijící ve skupinách si navzájem vychovávají potomky, sdílejí potravu, navzájem se varují v p ípad ohrožení. Skupina je sice z eteln jší, než jeden živo ich, ale unikání dravci ve skupin má také svou výhodu.
ím v tší skupina, tím se pro každého
jedince snižuje pravd podobnost, že bude práv on vybrán za ob . Víc o í víc vidí a tak i hledání potravy je p ínosn jší ve skupin , než individuáln . To platí i pro dravce, proto lze pozorovat spoustu druh i spole n lovících ko ist. Veliký potenciál skrývá sociální soužití v d lb práce. Tuto výhodu využívá hlavn hmyz. Jisté p izp sobivé a sociální chování bylo vypozorováno již u nejjednodušších organism
– bakterií. V roce 1995 v dec Doug Hoskins ukázal, že chování bakterie
Escherichia coli m že být vysv tleno jako fungování optimaliza ního algoritmu. [1] Tato bakterie se pohybuje dv ma zp soby, jež jsou popsány jako „b h“ (run) a „kutálení se“ (tumble) a v závislosti koncentrace toxických látek v prost edí se tyto dva zp soby pohybu mezi sebou st ídají. To zvyšuje šance bakterie na p ežití a jde tudíž o nejjednodušší vypozorovaný jev p izp sobení se okolnímu prost edí. Eshel Ben-Jacobs z univerzity v Tel Avivu dokonce tvrdí, že kolonie bakterií mezi sebou komunikují a vym ují si mezi sebou genetický materiál i mimo rozmnožovací procesy jako d sledek reakce na podn ty z okolí. Dále dodává, že i skromná kolonie bakterií je schopna provád t výpo etní operace lépe než nejvýkonn jší sou asná technika a p isuzuje jí vlastnost inteligence, tvo ivosti ba dokonce i uv dom ní si sama sebe. Z mnoha studií vyplívá, že bakterie mohou mutovat nenáhodn a zcela cílen . Tyto mutace jsou také reakce na vn jší podn ty z okolí. Na základ t chto podklad Ben-Jacobs teoretizuje, že genom funguje jako „p izp sobivá kybernetická jednotka“, která je schopna ešit složité problémy p ijímané z okolí. Bakterie se nejenom adaptují jako samostatní jedinci, ale v d sledku p ímých (ovliv ování konkrétního jedince jedincem) i nep ímých (jedinec ovliv uje prost edí, v n mž - 42 -
se vyskytují ostatní jedinci) fyzických a chemických interakcí, které byly vypozorovány, jsou schopny vytvo it celek, který se chová jako jeden organismus.
4.3 Sociální chování hmyzu Hmyzí organismus obsahuje jen pár stovek nervových bun k v nervovém gangliu, avšak tito tvorové jsou schopni vybudovat architektonické zázraky, složité komunika ní systémy a jsou jako celek velice odolní v i nástrahám p írody. Konrad Lorenz je v dec, který p evzal v roce 1973 Nobelovu cenu za medicínu a je známý pro sv j objev nazvaný „fixní ú inek akce“ (fixed action pattern). Jde o instinktivní reakci n kterých zví at na konkrétní podn ty. To se projevuje nap íklad u n kterých druh pták . Mlá ata ihned jak se vyklubou, p ijmou za své rodi e první v c, kterou vidí. Na jedné slavné fotografii je zachycen Lorenz, jak vede zástup mladých kachen, jež jej p ijali za svou matku. Konrad Lorenz vyu oval dalšího d ležitého v dce, který navšt voval jeho hodiny na Harvardské univerzit . Je jím Edward O. Wilson, který za al svoje úsilí v novat studiu chování mravenc v roce 1953. Wilson objevil, že za všemi úsp chy mravenc mohou práv jejich instinktivní reakce na vn jší podn ty. T mito podn ty není nic jiného, než feromony, které mravenci jak cítí, tak je mohou i samy žlázami vylu ovat. Feromon existuje více druh a všechny byly Wilsonem popsány i s odpovídajícími reakcemi mravenc na každý druh. Z toho je z ejmé, že feromony slouží mravenc m jako komunika ní médium. Problém vytvo ení chování mraven í kolonie jako celku z chování jednotlivc byl pro Wilsona zcela zásadní v oblasti sociobiologie hmyzu. Chování jednoho izolovaného jedince je v tšinou náhodné, ale chování celé populace poskytuje potravu a ochranu všem jedinc m, kte í ji tvo í. Je zajímavé, že na p íkladech s mravenci jsou vysv tlovány d ležité body z oboru um lé inteligence. Tyto p íklady také odrážejí historii pohledu na danou problematiku. Po átkem se stala negativní práce Norberta Wienera „Lidské využití lidských stvo ení“ (The Human Use of Human Beings) z roku 1950 [1]. Jelikož tato práce byla vyhotovena po druhé sv tové válce, Wiener odsuzoval pohled na lidské spole enství jako podobné mraven ímu. A to z toho d vodu, že se Wienerovi tento pohled zdál být fašistický. V mraven í spole nosti p ece v dce vládne navždy a následovníci budou v dce vždy následovat. Mravenci jsou tak autorem popisováni jako od p írody hloupí a neu enliví jedinci, kte í žijí v prost edí, jež
- 43 -
nem že být rozší eno do v tších rozm r . Lidé jsou naopak popisováni jako komplexní, tvo iví, p izp sobiví a u enliví jedinci, kte í jsou schopni kontrolovat svoje chování. V roce 1969 Herbert Simon ve své práci „V dy um lého“ (The Sciences of the Artifical) upozornil na skute nost, že cesta mravence p es v trem a vlnami zvrásn né pís ité pob eží je velice nepravidelná, n kdy až náhodná, avšak zachovávající si ur itý sm r. Simon z toho vyvodil záv r, že složitost cesty není d sledkem mravencova chování, protože mravenec je velmi jednoduché zví e neschopné vytvo it cokoliv složitého, ale je odrazem prost edí v n mž se jedinec nachází. Simon se rozhodl navzdory Wienerovi zam nit slovo „mravenec“ za „ lov k“ a jeho záv r zn l : „ lov k, zkoumaný jako systém vykazující chování, je jednoduchý. asto zjevná složitost jeho chování je odrazem složitosti prost edí, ve kterém se nachází.“ [1] Ozna ení lidí jako chováním podobným mravenc m dalo nad ji v dc m zkoumající um lou inteligenci k vytvo ení simulace lidského chování a v domí. Pokud by se lidé chovali jako mravenci, pak by v dci m li být schopni implementovat programy, které by se chovaly jako lidé, používající složité datové struktury a relativn jednoduché operace. Tento problém ale bohužel doposud nebyl vy ešen. Mravenec je opravdu jednoduchý tvor a celá síla a krása, kterou vykazují mraven í kolonie, vzniká spoluprácí mravenc . A stejn tak je tomu i u lidí. Deset let poté, v roce 1979, vyslovil Douglas Hofstadter v práci „Mravene ník“ (Anteater) domn nku, že celý lidský mozek se chová jako populace mravenc . Neuron sám v sob není schopen uchovat jakoukoliv informaci. Myšlení vzniká na základ jejich interakce. A jak Hofstadter popisuje, i mravenci vykazují jistou minimální komunikativní innost. Tato minimální komunikace má zabránit, aby se všichni mravenci potulovali zcela náhodn , a zajistit, aby si každý jedinec uv domoval p ítomnost jeho spolupracovník . Navíc takovéto fungování vyžaduje spolupráci hodn jedinc , aby innost mohla být udržována po delší asový úsek. Toto poznání vede Hofstadtera k záv ru, že práce neuron v lidském mozku je vlastn principieln velice podobná innost. Práv popsaný pohled na chování mravenc je v souladu se sou asným pohledem na vznik komplexních dynamických systém . A sice jako na produkt interakcí jednoduchých prvk s jednoduchým chováním. V simulaci virtuálních mravenc , kterou vytvo il Christopher Langton, vznikají vždy úsp chy vykazující jistou dávku inteligence ešení práv interakcí jedinc , neinteligentních agent . A k dokon ení mraven ích chvalozp v dodávám jenom - 44 -
takovou zajímavost, a sice že mravenci byli prohlášeni za neoficiální maskoty komunity, jež se zabývá um lou inteligencí.
4.3.1 Mravenci a termiti N kte í tropi tí termiti jsou schopni vystav t svá obydlí se zjevnou uspo ádaností a systémem v jejich konání. V po átku stavby vyrostou základy pro sloupy, které termiti dále staví do výšky, dokud se nesetkají a nevytvo í klenbu. Tito tvorové provád jí stavbu bez jakéhokoliv centrálního ízení. Nepot ebují „architekta“, který by jim íkal, co kde mají ud lat. Každý termit nabere materiál (hlínu) do úst, zpracuje ji a pak se ídí dv ma jednoduchými pravidly : -
pohybuj se na místo, kde se nachází nejv tší koncentrace feromonu
-
kde je koncentrace feromonu nejsiln jší, tam polož sv j náklad Feromon je velice d ležitý prvek v život jak mravenc a termit , tak i jiných druh
hmyzu. Jde o látku, kterou umí jedinci vytvá et a zna it jí cesty a místa a také dokáží vycítit její p ítomnost. Feromon má ješt jednu vlastnost a tou je vypa ování. Vypa ování feromonu probíhá lineárn v závislosti na ase a tak se koncentrace látky na míst postupem asu snižuje, až je nulová. Toto zabra uje vzniku nadm rného množství sloup p i stavb termitišt a i dokonce nadm rné výstavb termitiš po krajin . Stav ní sloup
do výšky vyplývá z autokatalytické nebo pozitivní zp tné vazby.
Autokatalýza je aspekt mnoha komplexních systém , který dovoluje d sledk m p er st v závažné.
asto triviálním
ím v tší je po et termit , kte í staví na jednom míst , tím je
toto místo atraktivn jší i pro ostatní jedince. B hem stavby se okolo místa stavby sloup zvyšuje koncentrace feromonu a jedinec se asto rozhoduje mezi dv ma sloupy se stejnou atraktivitou. Nez stane stát uprost ed, na jeden ze dvou sloup
sv j náklad složí, ale
podstatn jší d sledek je, že na sloup vyleze a náklad složí jakoby na vnit ní stranu sloupu, na stranu p ivrácenou ke sloupu se tejnou koncentrací feromonu, jako m l termitem vybraný. Tímto postupem se vystavované sloupy k sob vrcholy p ibližují, až se nakonec setkají a vytvo í klenbu.
- 45 -
V tšina komunikace mezi leny roje se odehrává pomocí nep ímé komunikace, která byla v roce 1955 entomologem P.P.Grassém nazvána stigmergy [1]. Jde o p sobení jedince na okolí, které ovlivní ostatní (proto nep ímá komunikace). Tato komunikace je dvou druh . Prvním je „podm tová“ (cue-based). Využitím této metody zm na v prost edí vyvolá v jedinci podm t pro provedení konkrétního chování. Druhá je „zna kovací“ (sign-based). V tomto p ípad zm na v prost edí zasílá signály, upozor uje na sebe všechny zú astn né jedince. P i stavb termitišt jsou termity používány oba druhy této nep ímé komunikace. Další zajímavý postup používají mravenci p i vynášení mrtvých z mraveništ . Díky tomuto postupu vznikají známé mraven í h bitovy. Jestliže jedinec zem e, ihned po smrti si ho ostatní nevšímají. Zm na nastává za pár dní, kdy se t lo mravence za ne rozkládat a ostatní to mohou vycítit. Mravenec je pak vynesen ven z mraveništ a jestliže se kolem mraveništ vyskytují mrtvoly voln roztroušeny po prostoru, ostatní mravenci je za nou p enášet a postupn se tak tvo í hromádky mrtvých t l. Jean-Louis Deneubourg a jeho kolegové ukázali, že i tento postup m že být vysv tlen jednoduchými pravidly. Jde dokonce o stejný zp sob, jakým mravenci p erovnávají kukly a termiti d ev né odšt pky. Princip lze jednoduše vysv tlit pravidlem, které íká, že jestliže je p edm t osamocen, pak jej jedinec uchopí a položí na místo, kde se vyskytuje více p edm t stejného druhu jako ten, který je p enášen. Postup vysv tluje v podstat dvojice pravidel : -
pokud neneseš p edm t a narazil jsi na n jaký, pak ho uchop
-
jestliže p edm t neseš a narazil jsi na jiný stejného druhu, pak polož sv j náklad
Jak je zjevné, jde také o nep ímou komunikaci, která vyvolává u jedinc jistý podm t.
4.3.2 Optimalizace pomocí virtuálních mravenc Marco Dorigo, Vittorio Maniezzo a Alnerto Colorni v roce 1996 p edvedli zp sob, jak jednoduchý postup který je využíván mravenci pro nalezení nejkratší spojnice mezi dv ma místy, zpravidla mraveništ m a zdrojem potravy, m že být využit pro efektivní ešení a optimalizaci problému obchodního cestujícího [1]. Tento zp sob ešení byl pojmenován „optimalizace mraven í kolonií“ (ant colony optimalization). Op t je využíván feromon jako
- 46 -
prost edek komunikace a op t je ešení výsledkem spolupráce mnoha jedinc , kte í plní jednoduché úkoly. Jak se mravenci pohybují, zanechávají za sebou stopu. Touto stopou není nic jiného, než jejich feromon. Jak jsem již zmínil, feromon má tendenci se vypa ovat. Pokud ale po daném bod bude jedinec p echázet vícekrát, pak bude danému místu množství feromonu dodávat a jeho intenzita a atraktivita pro ostatní tak poroste. Celý postup vyhledání nejkratší cesty je demonstrován na jednoduchém p ípad . Jsou dána dv místa. Mraveništ a zdroj potravy. Mezi t mito místy jsou dány dv cesty, které jsou r zn dlouhé. Celou situaci znázor uje obrázek 4.1. Když mravenci vyrazí z hnízda a narazí na potravu, pak se i stejnou cestou vrací zp t po cest , kterou si vyzna ili feromonem. Ti kte í vyšli po kratší cest se zákonit dostanou zp t d ív než ti, kte í šli po delší. V moment , kdy se ti rychlejší vrátí do hnízda, tak na kratší cestu je od každého z nich položena dvojitá dávka feromonu (jedna na cest za potravou a druhá p i cest zp t). Na delší cestu je ale položena jen jedna dávka od každého mravence, protože ti se ješt nevrátili z jejich delší cesty. Proto je kratší cesta pro mravence, kte í vyrážejí podruhé atraktivn jší než cesta delší. Jakmile se vrátí mravenci z delší cesty, bude kratší ozna kována t ikrát, zatímco delší jen dvakrát. Proto kratší cesta bude atraktivn jší i pro ty, kte í šli delší cestou a vrátili se. V pr b hu asu se bude po delší cest pohybovat stále mén mravenc a vrstva feromonu se v d sledku vypa ování bude stále zten ovat, zatímco kratší cesta bude stále více pro mravence p itažliv jší, jelikož její vrstva feromonu bude stále sílit. Tento postup má ale i své nevýhody. Jakmile už je populací mravenc nalezena kratší cesta a je hojn využívána, pak po p idání ješt kratší cesty mravenci tuto novou cestu nenaleznou a budou využívat tu, kterou nalezli p edtím. Stejn tomu tak je i se zdroji potravy. Pokud jsou populaci mravenc nabídnuty dva zdroje, mravenci za nou využívat ten bohatší. Jestliže ale už jeden zdroj využívají a je jim nabídnut bohatší, pak nejsou schopni se na nový zdroj p eorientovat.
- 47 -
Obr. 4.1 : p íklad prost edí, v n mž mravenci hledají kratší cestu Záv re ná implementace pro ešení problému obchodního cestujícího není složitá. Zp sob z stane stejný, jak probíhá v p írod , jenom pravd podobnost, že si mravenec vybere jednu z mnoha cest, je vyjád ena pravd podobnostní funkcí, která je závislá na množství položeného virtuálního feromonu na dané cest .
4.4 Hejna Pohyb mravenc jako jedinc se zdá více i mén náhodný. Jsou ale živo ichové, v jejichž pohybu se vyskytuje jistá pravidelnost. Na mysli mám nap íklad rybí hejna.
4.4.1 Ryby P i pozorování se zdá, že se celé hejno pohybuje jako jeden celek, a koliv je složeno ze stovek nebo dokonce tisíc jedinc , kte í neustále m ní sm r a rychlost. V roce 1954 si Charles Marcus Breder vzal za úkol sestrojení matematického modelu, který by popisoval chování hejna ryb. Po prozkoumání základních biologických údaj
Breder usoudil, že
soudržnost hejna je funkcí množství ryb v hejn , vzdáleností mezi rybami a potenciálem - 48 -
každého jedince (hodnota, která mimo jiné závisí na jeho velikosti). Dále zkoumal atraktivnost celého hejna pro osamocené ryby. M ení probíhalo jako pokus, kde v p ed leném akváriu byla v jedné ásti samotná ryba a v ásti druhé celé hejno. Breder pak akorát pozoroval tendenci a snahu osamoceného jedince dostat se k hejnu. Nakonec z pozorování vyvodil záv r, že atraktivnost hejna pro ostatní lze vyjád it vzorcem : c = kN t kde k a t jsou konstanty a N je po et ryb v jedné ásti akvária. V jednom z jeho p íklad jsou konstanty k = 0,355 a t = 0,818. Jakmile je exponent t menší než jedna, je z ejmé, že atraktivnost c se bude sice s rostoucím N zvyšovat, ale ím v tší N bude, tím c poroste pomaleji, jak ukazuje obrázek 4.2. Jinými slovy, diferenciál funkce bude klesat.
Obr. 4.2 : funkce c v závislosti na N
4.4.2 Lidé Breder v záv r je zejména zajímavý z pohledu nov jší teorie lidského sociálního chování. Tato teorie byla vytvo ena v sedmdesátých letech dvacátého století a dodnes se vyvíjí. Za jejím zrodem stál v dec Bibb Latané. Ten p išel na to, že vliv skupiny na jedince je funkcí její „síly“ (strenght), „blízkosti jedinc “ (immediacy) a „po tu zdroj vlivu“ (nuber of sources of influence) [1]. Síla je druh prom nné, ukazuje sílu vlivu, potenciál skupiny. - 49 -
Blízkost jedinc vyjad uje p evrácenou hodnotu vzdálenosti. Jakmile vzdálenost mezi jedinci klesá, blízkost roste. A po et zdroj vlivu není nic jiného než po et jedinc ve skupin . Latané nap íklad zjistil, že výše obnosu, kterou skupina v restauraci zanechá jako spropitné, je funk n závislá na po tu jedinc skupiny. Nejen na tomto p ípadu bylo zjišt no, že vztah mezi vlivem a po tu zdroj vlivu odpovídá vzorci : i = kN t kde i je výsledný vliv skupiny a N je onen po et zdroj vlivu. Dále k a t jsou konstanty a t < 1. Z hodnoty t vyplívá d sledek, že vliv monotónn roste s po tem len skupiny, ale p ír stek vlivu se snižuje. Stejn jak tomu bylo u rybího hejna.
4.4.3 Ptáci Velice zajímavá simulace pta ího hejna Boids (autorovo pojmenování simulovaných pták ) byla zpracována v roce 1987 Craigem Reynoldsem. Podle n j ptáci v hejn dodržují t i zásady. Jsou jimi vyvarování se srážce, srovnávání rychlosti s okolními jedinci a vyst e ování hejna. Pravidla by se daly shrnout jako : -
vzdal se, než narazíš do ostatních
-
snaž se let t stejnou rychlostí jako ostatní v hejnu
-
pohybuj se sm rem ke st edu hejna Implementací t chto pravidel vytvo il Reynolds realistické hejno jedinc , kte í simulují
chování pták . Pohybují se v t írozm rném prostoru, rozd lují se, aby se vyhnuli p ekážkám, a vzáp tí se zase spojují do jednoho celku, jak ilustruje obrázek 4.3. Dále v se p íloze nalézá video Boids.mov (p evzato z [21]), které znázor uje pohyb tohoto hejna. Bohužel video neoplývá kvalitou, ale doufám, že pro názornost posta í.
- 50 -
Obr 4.3 : simulace pta ího hejna s p ekážkami; p evzato z [21] V roce 1971 p išel William Donald Hamilton s prací „Geometrie pro sobecký houf“ (Geometry for the selfish herd). V ní odhaluje vysv tlení, pro živo ichové jako ryby a ptáci využívají spole enská uskupení a pohybují se v hejnech. Tyto uskupení se vyskytují jen u druh , které jsou loveni dravci. Pokud jsou zví ata v hejnu, pak predátor zaúto í pouze na jedince, který se nachází na kraji hejna. A jestliže se všichni chovají podle pravidla „pohybuj se sm rem ke st edu hejna“, pak se práv vyhýbají pozici na kraji a snaží se být co nejvíc ve st edu. To každému jedinci dává jistou šanci, že práv on se nestane potravou pro lovce a práv pro tuto skute nost bylo v názvu práce použito slovo „sobecký“. Craig Reynolds v roce 1987 v „Davy, houfy a hejna : Distribuovaný model chování“ (Flocks, herds and chools : A distributed behavioral model) porovnával sv j model s typickým systémem ástic (particle system) [1].
ásticové systémy jsou druhem metody
po íta ové grafiky, která se skládá z mnoha jednotlivých agent (objekt ), z nichž má každý svoje vlastní chování. Reynolds došel k záv ru, že chování jeho simulace je složit jší než ásticový systém, avšak na druhou stranu je jednodušší než chování skute ného hejna pták . Ve stejné dob pozoroval pta í hejna i biolog Frank Heppner z Univerzity na Rhode Islandu. Ten natá el pta í hejno dv ma kamerami, které byly umíst ny tak, aby jejich záb ry svíraly úhel devadesát stup
. Rychlost natá ení byla t i snímky za sekundu. Heppner si pak
celý záznam poušt l snímek po snímku a p išel na další skute nosti, které ješt nebyly objeveny. Nap íklad, že celé hejno se pohybuje bez jakéhokoliv centrálního vedení. Jakýkoliv len mohl ud lat kdykoliv libovolný manévr. Ze záb r vyplynulo, že pohyb celého hejna není nijak organizován a hejno udržuje dynamickou rovnováhu. Heppner dále experimentoval s programem, který implementoval Conwayovu Game of Life (kapitola 2.4), protože se - 51 -
domníval, že chování kluzák je podobné chování, jaké se objevuje v pta ích hejnech. Pro realizaci projektu sestavil tým, který se sestával z n ho samotného, matematika Ulfa Grenandera a programátora Daniela Pottera. Projekt m l dokázat, že komplexní chování hejna m že vyplývat z n kolika prostých pravidel. Pravidla, která implementovali byly podobné jako použil Reynolds. Také implementoval jistou p itažlivou sílu, která p itahuje jedince k sob , pokud nehrozí kolize. Heppner dále p idal, narozdíl od Reynoldse, sílu, která ptáky láká k místu, na které mohou usednout. ím blíže k tomuto místu jsou, tím více jsou k n mu p itahováni. Další odlišnou vlastností je, že tito ptáci mají tendenci dosáhnout a udržovat cílovou rychlost, která je p edem daná. Jako poslední v c je náhodné vychylování jedinc z hejna, které slouží jako simulace v tru. Jako výsledek vzešla velice d v ryhodná, jednoduchá a decentralizovaná simulace pohybu pta ího hejna. Nedávno, v roce 1999, p išli dva fyzici John Toner a Yuhai Tu z laborato e IBM v New Yorku s matematickou analýzou nazvanou „Davy, houfy a hejna : Kvantitativní teorie houfování“ (Flocks, herds and chools : A quantitative theory of flocking) [1]. Jejich model analyzuje chování a pohyb velkého množství jedinc . P ipomíná, že hejno je složeno z mnoha jedinc , kte í se snaží pohybovat ve stejném sm ru jako ostatní. Dále jedinec uvažuje jenom svoje nejbližší sousedy. Za t etí, náhodnost je použita jako zm ny v pohybu jedince a tak hejno není nikdy dokonalé. A za tvrté, je udržována st edová soum rnost hejna. Podle Tonera a Tu je zajímavé, že díky náhodnosti, která se vyskytuje v pohybu pták , nikdy houf nedosáhne rovnováhy a neustálí se. Stejn tak jako celulární automaty tvrtého ádu (kapitola 2.5). Hejno se pohybuje podle charakteristických rys , ale nikdy ne p edvídateln a po dlouhý asový úsek.
- 52 -
5 Evolu ní výpo ty Je t žké ur it, v jaké dob mají evolu ní výpo ty ko eny. Jde o velice diskutabilní téma. V podstat se za položení základ evolu ních výpo t považuje práce Darwinovské syntézy, kterou vytvo il John Burdon Sanderson Haldane v první polovin dvacátého století. V té dob se za ala rozvíjet problematika evolu ních výpo t . Pole evolu ních výpo t se podle v tšiny zainteresovaných v dc rozd luje na ty i hlavní oblasti : -
genetické algoritmy (genethic algorithms)
-
genetické programování (genethic programming)
-
evolu ní programování (evolution programming)
-
evolu ní strategie (evolution strategies) Podle mnohých je genetické programování sou ástí genetických algoritm . M že být
ale uvedeno i samostatn . Tyto ty i hlavní v tv jsou odlišn zastoupeny v mí e využití v praxi. Dalo by se íci, že dnes jsou nejpoužívan jší metodou genetické algoritmy, ale zárove nar stá popularita zp sob
ešení, které zasahují do více oblastí.
5.1 Genetické algoritmy Genetické algoritmy jsou v podstat prohledávací algoritmy, které jsou inspirovány p írodní evolucí, a poskytují velice efektivní mechanismy, které jsou použitelné p i optimalizaci nebo klasifikaci aplikací. Tyto postupy pracují s „populací“. Jde o populaci potenciálních ešení, která jsou reprezentovány vícerozm rnými vektory. Každý vektor je tudíž jedincem v dané populaci a asto se používá i název „chromozóm“ v d sledku analogie s genetickým vývojem organism . Jelikož vektory asto reprezentují reálná ísla vyjád ená v binární soustav , pak rozm r vektoru nemusí vždy odpovídat rozm ru problému. Po et složek každého vektoru odráží po et reálných parametr v optimaliza ním problému. Každá složka vektoru m že být vyjád en libovolným po tem bit . Tento po et závisí na reprezentaci každého parametru zvláš . Celkový po et bit vektoru prozrazuje rozm r prostoru, který je prohledáván. Pokud je nap íklad genetický algoritmus použit pro nalezení optimálních vah pro
- 53 -
nervovou sí , pak po et složek vektor
odpovídá po tu vah v nervové síti. Pokud je
v problému w vah a je pot eba vypo ítat každou váhu s p esností b bit , pak se každý vektor bude skládat z w x b bit a rozm r binárního prostoru, který je pot eba prohledat bude roven 2wb. [1]
5.1.1 Operace algoritmu Operace, které provádí genetický algoritmus jsou vyjád eny následovn : 1) zave populaci 2) vypo ítej ohodnocení pro každý vektor (každého jedince) 3) rozmnož vybrané jedince pro vytvo ení nové populace 4) prove k ížení (crossover) a mutaci (mutation) chromozóm na populaci 5) p ejdi na druhý krok, pokud není spln na podmínka pro ukon ení V n kterých implementacích genetických algoritm jsou použity i jiné operace než k ížení a mutace chromozóm . Ty se pop ípad vykonávají také ve tvrtém kroku algoritmu. Vým na gen mezi páry je považována za základní operaci všech genetických algoritm . V podstat genetické algoritmy pracují na principu vyvíjení populace bitových et zc . Populace je na po átku ve v tšin p ípadu zavedena náhodn , bit po bitu. Stále ast ji se objevují p íklady, v nichž je n kolik prvních jedinc ur eno heuristicky a teprve zbylí jsou dotvo eni stochastickou metodou. Déle algoritmus ohodnotí podle jistých pravidel celou populaci vektor a na základ získaného ohodnocení stochasticky z každé populace vybírá jedince, kte í p ežijí do nové populace. Vybraní jedinci si mezi sebou „vym ní informace“ (analogie p írody) za pomocí k ížení chromozóm . Tato operace m že být dvojího druhu. A to jednobodová nebo dvoubodová. Oba typy ilustruje obrázek 5.1.
- 54 -
Obr. 5.1 : jednobodové a dvoubodové k ížení; p evzato z [22] Následuje mutace. Mutace probíhá jako stochastické p em ování hodnoty bit , které prochází celou populaci a aplikuje se na každý bit odd len . Princip je jednoduchý. Je dána pravd podobnost provedení této operace. Ve v tšin p ípad jde o pravd podobnost jedné desetiny procenta. A pokud je vygenerované pseudonáhodné íslo menší než nap íklad 0,001, pak je hodnota daného bitu zm n na. Tyto operace (krom zavedení populace) jsou provád ny do té doby, než se v populaci vyskytne jedinec, který spl uje podmínky pro ukon ení algoritmu.
5.2 Genetické programování Všechny oblasti evolu ních výpo t
používají pro reprezentaci populace et zce,
neboli jinými slovy vektory. Až na problematiku genetického programování. Procesy genetického programování vyvíjejí po íta ové programy, které jsou reprezentovány stromovými strukturami. Navíc tyto struktury v celé populaci nemají fixní délku, tvar ani složitost a tudíž se jedinci populace v t chto parametrech odlišují. Jak už jsem zmínil, genetické programování m že být považováno za sou ást genetických algoritm . Sou ást, která vyvíjí spustitelné programy. Rozdíly mezi genetickými algoritmy a genetickým programováním jsou následující : -
jednotlivci populace jsou spustitelné struktury a ne et zce bit
-
ohodnocení jedinc v genetickém programování je provád no spušt ním jedince - 55 -
Cílem implementace genetického programování je nalezení programu, který poskytuje uspokojivé výstupy s použitím daných vstup , z celé populace potenciálních program . Dalo by se íci, že po íta , na kterém je provozována metoda genetického programování, se tímto postupem u í, jak psát sv j vlastní kód. Každý jedinec (program) je reprezentován stromem, kde funkce problému p edstavují vnit ní vrcholy stromu a prom nné a konstanty se nacházejí v krajních vrcholech, listech.
5.2.1 P íprava V p íprav pro spušt ní genetického programování je zapot ebí uskute nit p t krok : 1) specifikovat kone nou sadu (terminal set) 2) specifikovat funk ní sadu (function set) 3) specifikovat m ení ohodnocení (fitness measure) 4) vybrat parametry kontroly systému (system control parameters) 5) specifikovat podmínky ukon ení (terminal conditions) Kone ná sada zahrnuje prom nné a konstanty, které jsou spojeny s vy ešením problému. Do funk ní sady jsou vybírány funkce definované programovacím jazykem, který bude použit pro b h program
vyvíjených genetickým programováním. Mohou se zde
vyskytnout aritmetické, matematické a logické operace. Také funkce v tvení, cyklu a rekurze.. Každá funkce z funk ní sady má pevn dán po et argument (aritu). Na hodnoty z kone né sady lze také pohlížet jako na funkce s aritou nula. Jedním z úkol p i definování funk ní sady je zvolení pokud možno minimální sady, za pomocí které je program schopen splnit úkol. Z tohoto plynou dv základní vlastnosti každé aplikace genetického programování. Jde o „uzav enost“ (closure) a „posta itelnost“ (sufficiency). Vlastnosti uzav enosti zaru uje, že každá funkce musí být schopna operovat s jakoukoliv funkcí z funk ní sady a jakoukoliv hodnotou všech datových typ , které jsou definovány v kone né sad . Posta itelnost jednoduše íká, že jistá kombinace funkcí a prom nných nebo konstant musí vést k ešení problému. K vyvození záv ru, jestli je tato podmínka spln na, je zapot ebí jisté znalosti ešeného problému. V n kterých p ípadech je ale podmínka rozpoznatelná na první pohled.
- 56 -
Nap íklad za použití logických funkcí je známo, že sada obsahující funkce AND, OR, NOT je posta itelná pro jakýkoliv problém. M ení ohodnocení se ve v tšin p ípad realizuje jako p evrácená hodnota chybovosti programu. Mezi dva hlavní kontrolní parametry pat í velikost populace a maximální po et generací, které budou vytvo eny. Ostatní parametry vyjad ují nap íklad pravd podobnost reprodukce, k ížení a maximální povolenou velikost jedince ve smyslu maximální hloubky stromu. Ukon ovací podmínky jsou v tšinou zadány po tem generací, které budou vytvo eny a vít zný jedinec je program s nejv tším ohodnocením ze všech populací. Vít zný jedinec je tedy hledán ve všech generacích, ne jenom v poslední vytvo ené.
5.2.2 Vlastní genetické programování Po p ípravných krocích následuje vlastní pr b h genetického programování, který je popsán následujícími kroky : 1) zave populaci program 2) ur i p ínos každého jedince 3) prove reprodukci jedinc v závislosti na jejich ohodnocení a pravd podobnosti reprodukce 4) prove k ížení výraz 5) jdi na krok dv , pokud nejsou spln ny ukon ovací podmínky Vše probíhá jako u genetických algoritm až na n kolik odlišností. Jelikož genetické programování operuje se stromy, pak zavád ní populace probíhá odlišn , než u genetických algoritm . Nejd íve se z funk ní sady náhodn vybere funkce, která vytvo í ko en stromu. Po et v tví stromu tak závisí na arit vybrané funkce. Po ur ení ko ene se pak dotvo í stochastickým výb rem zbytek stromu. Dotvá ení probíhá dv mi metodami : „p ír stkovou“ (grow) a nebo plnou (full) metodou. P ír stková metoda pracuje na principu postupného p idávání vrchol , které rozši ují strom. Vybere se náhodn jeden prvek z kone né nebo funk ní sady a ten je dosazen na místo
- 57 -
nového vrcholu. Pokud je vybraný prvek prom nná nebo konstanta, pak p idaný vrchol p edstavuje list stromu. Jestliže je ale p idána funkce, pak se strom dále v tví v závislosti na arit dané funkce a jako její následníci jsou vybírány další vrcholy. Pokud se vybírá vrchol, po jehož p idání strom dosáhne maximální hloubky, pak je vrchol vybírán jen z konstant a prom nných. Tím se zamezí dalšímu prohlubování stromu. P i použití plné metody se rozvinou v tve do maximální hloubky. Vrchol m se p i azují náhodn funkce, dokud strom nedosáhne maximální délky. Pak se volí listy stromu z množiny dostupných prom nných a konstant. Body 3) a 4) jsou také zvláštní. Pravd podobnosti k ížení a reprodukce jsou nastaveny tak, aby jejich sou et byl jedna. Z toho vyplývá, že prob hne jen jedna varianta. Bu
dojde
k reprodukci nebo ke k ížení. Jestliže dojde k reprodukci, pak jsou jedinci vybíráni na základ jejich ohodnocení. Pravd podobnost, že bude jedinec vybrán pro reprodukci je roven podílu jeho ohodnocení a sumy ohodnocení celé populace. Pokud dojde k p ek ížení, pak jsou vybráni první dva jedinci s pravd podobností, jež se používá u reprodukce. Ur í se náhodn „bod k ížení“ (crossover point) u každého jedince. Tento bod m že být ur en kdekoliv. V ko eni, vnit ním vrcholu i listu. Nakonec si dva vybraní jedinci vym ní všechny následníky vrcholu, který byl ozna en jako bod k ížení. Když dojde k situaci, kdy k ížením vznikne program vetší, než je jeho povolená délka, tak je automaticky p i dalším k ížení zkopírován do nové populace nezm n ný podstrom, který obsahuje všechny následníky bodu k ížení, na místo bodu k ížení programu jiného.
5.3 Evolu ní programování Evolu ní programování také využívá pro vývoj nejlepšího ešení daného problému celou populaci jedinc , ale liší se koncentrací projev adaptace. Taktéž klade velký d raz na vyvíjení model chování, což jsou modely pozorovatelných interakcí systému s jeho okolím. Vývoj evolu ního programování je velice významn
ovlivn n teoriemi reálné p írodní
evoluce. Evolu ní programování je odvozeno ze simulace p izp sobivého chování v evoluci. Zde je patrná odlišnost od genetických algoritm . Ty operují v „prostoru genotyp “ (genotype
- 58 -
space), kdežto evolu ní programování pracuje s prostorem fenotyp (phenotype space). Tato metoda proto vyvíjí p ímo chování, které vede k vy ešení problému. Tento p ístup je flexibiln jší než ostatní evolu ní výpo ty. Evolu ní programování provádí v populaci pouze mutace. Dále tento p ístup v každé generaci vytvá í stejný po et potomk , jako byl po et p edk v generaci p edchozí. Rodi e jsou z populace vybírání formou „turnaje“. Vlastnosti rodi
jsou mutovány a vytvo í tak potomky. Potomci jsou p idáni do
populace, ímž se populace zdvojnásobí. Pak následuje výb r lepší poloviny podle ohodnocení jedinc z celého výb ru rodi
i potomk , která vytvo í populaci další generace.
Podstatný dopln k ke klasickému evolu nímu programování je samo-p izp sobení. které povoluje schopnost pro strategické parametry, aby se vyvíjely. To usm r uje mutace do slibn jších oblastí prohledávaného prostoru. V sou asnosti jsou používány t i druhy evolu ního programování, které se liší mírou samo-p izp sobení [1] : -
standard evolution programming
-
meta - evolution programming
-
Rmeta - evolution programming
5.3.1 Operace algoritmu Vlastní pr b h evolu ního programování se sestává z následujících krok : 1) zave populaci 2) p edstav populaci prost edí 3) vypo ítej ohodnocení pro každého jedince 4) náhodn mutuj každého jedince z rodi ovské populace 5) ohodno rodi e a potomky 6) vyber leny populace nové generace 7) jdi na krok dv , dokud nejsou spln ny podmínky pro ukon ení Populace je zavád na op t náhodn . Každý jedinec je reprezentován reálným íslem, které se pohybuje v jistém intervalu. Množství jedinc v populaci se v tšinou pokaždé liší, jelikož závisí na povaze ešeného problému. Obvykle se velikost populace pohybuje od n kolik desítek po n kolik stovek jedinc .
- 59 -
5.4 Evolu ní strategie Evolu ní strategie vyvíjejí modely ešení problému jako populaci „druh jedinc “ místo toho, aby vyvíjely populaci vektor roztroušených po krajin ohodnocení. Vlastnost populací u evolu ních strategií, která jim dovoluje se p izp sobovat prost edí (obvykle testovací funkci nebo obtížnému optimaliza nímu problému), je evoluce jejich schopnosti vyvíjení se. Pokud jsou biologické procesy optimalizovány evolucí a evoluce je biologický proces, pak evoluce optimalizuje samu sebe. Proto princip evolu ních strategií lze popsat jako „evoluce evoluce“. [1] Mezi evolu ním programováním a evolu ními strategiemi je mnoho podobného a oba tyto p ístupy se stále více sob p ibližují. Oba používají „vodopádovitý“ (top-down) p ístup. Oba také zd raz ují použití fenotypového prostoru p ed použitím genotypového. Evolu ní strategie stejn jako evolu ní programování používají pro prom nné reálné hodnoty.
5.4.1 Operace algoritmu Následující seznam zahrnuje procedury provád né u v tšiny evolu ních strategií : 1) zave populaci 2) prove p ek ížení za použití x rodi
k vytvo ení y potomk
3) prove mutaci na všech potomcích 4) ohodno y nebo (x + y) len populace 5) vyber x jedinc k vytvo ení populace nové generace 6) jdi na krok dv , dokud nejsou spln ny podmínky pro ukon ení Mutace v evolu ních strategiích je aplikována na vlastnosti rodi , tudíž jsou tvo eni potomci, kte í se rodi m podobají, ale stochasticky se od nich odlišují. Každá sou adnice pozice vybraného jedince z x možných pro k ížení je vložena dle normálního rozd lení, korespondující strategický parametr je vložen jako rozptyl i jako sm rodatná odchylka a vektor potomka je generován pro ob pozice jeho rodi e i pro oba strategické parametry. Tito potomci jsou vyvinuti, je proveden výb r a cyklus se opakuje. Evolu ní strategie zahrnují evoluci vyvíjení a p izp sobování mutace druh , které hledají optimální stav, na n mž se ustálí. - 60 -
6 Záv r Cíl vyty ený v úvodu práce se mi dle mého názoru poda ilo splnit. Rozsah práce jsem se snažil uzp sobit na on ch padesát až šedesát stran, což bylo moje dlouhodobé p edsevzetí. P eci jenom se jedná o úvodní studii a myslím, že by spoustu tená
odradilo íst dokument,
který má p es sto stran. V kapitolách jsem se snažil problematiku co nejlépe popsat, aniž bych zabíhal do složitých matematických a jiných odborných detail . Zvlášt
v kapitole o
optimalizaci a evolu ních výpo tech jsem se snažil vyvarovat p episování matematických výraz z publikací do této práce. Osobn si myslím, že nejzajímav jší ást celé práce je kapitola 4 – Sociální organismy. I téma této kapitoly je natolik rozsáhlé, že by mohlo být samo tématem celé práce a nejenom bakalá ské. Stejn tomu tak je i u ostatních ástí. Zvlášt u kapitoly o evolu ních výpo tech. Když jsem se do dané problematiky hloub ji pono il, zjistil jsem, že jenom obor genetických algoritm je téma, kterému by se mohl lov k v novat celý život. Z tohoto d vodu jsem se snažil u každé probírané látky vystihnout pouze nejd ležit jší a nejzajímav jší principy a poznatky. Doufám, že se mi toto p edsevzetí poda ilo naplnit a tená bude s touto prací spokojen. Mým dalším cílem je umístit html prezentaci této práce na internet. Odhaduji, že v pr b hu dvou m síc se mi i toto p edsevzetí poda í s jistotou splnit. Pokud by se kdokoliv rozhodl pokra ovat tam, kde jsem já skon il, doporu il bych hlubší propracování ant colony optimalization a evolu ních výpo t . To jsou oblasti , myslím, hodn zajímavé a praktické. Dále bych doporu il rozší ení o „optimalizaci rojem ástic“ (particle swarm optimalization) a uvedení praktických p íklad využití poznatk v praxi.
- 61 -
7 Použitá literatura [1] – KENNEDY, J., EBERHART, R., C. Swarm Intelligence. 1.vyd. San Diego : Academic Press, 2001, 512 s. The Morgan Kaufmann Series in Evolutionary Computation. ISBN 1-55860-595-9 [2] – BATESON, Gregory, Mind and Nature – A Necessary Unity (citace prosinec, 2., 2003) URL : http://www.oikos.org/mind&nature.htm [3] – GARDNER, Martin, The fantastic combinations of John Conway' s new solitaire game "life" (citace prosinec, 2., 2003) URL : http://ddi.cs.unipotsdam.de/HyFISCH/Produzieren/lis_projekt/proj_gamelife/ConwayScientificAmerican.htm [4] – MARTIN, Edwin, Life is a bit (citace prosinec, 4., 2003) URL : http://www.bitstorm.org/gameoflife/ [5] - RENNAND, Jean-Philippe, Introduction to Artificial Life and Java Illustration (citace prosinec, 10. 2003) URL : http://www.rennard.org/alife/english/acintrogb05.html [6] – neznámý autor, The Blind Watchmaker : Why the Evidence of Evolution Reveals a Universe Without Design (citace prosinec, 11., 2003) URL : http://www.2think.org/tbw.shtml [7] – SIMS, Karl, Evolved virtual creatures (citace prosinec, 15., 2003) URL : http://dynamics.org/~altenber/GA_ART/Sims.mpg [8] - SIMS, Karl, Karl Sims Homepage (citace prosinec, 15., 2003) URL : http://www.genarts.com/karl/ [9] - SIMS, Karl, Galapagos, 1997 (citace prosinec, 17., 2003) URL : http://www.genarts.com/galapagos/index.html [10] – HOUSER, Pavel, Paradoxy um lé inteligence: Turing v test 50 let poté, 2003 (citace prosinec, 20. 2003) URL : http://www.root.cz/clanek/1562 [11] – neznámý autor, By 2029 no computer - or "machine intelligence" - will have passed the Turing Test, 2002 (citace prosinec, 20., 2003)http://www.longbets.org/1 [12] – KELLY, Kevin, Long Bets (citace prosinec, 20., 2003) - 62 -
URL : http://www.longbets.org/ [13] – HOUSER, Pavel, Námitky proti ínskému pokoji, 2003 (citace leden, 15., 2004) URL : http://www.scienceworld.cz/sw.nsf/page/cinsky_pokoj [14] – HOUSER, Pavel, V domí a automatismy: Chalmersova zombie (citace leden, 16., 2004) URL : http://www.scienceworld.cz/sw.nsf/ID/C1256CB8004086B3C1256B56004750FC [15] – neznámý autor, John Holland, 1998 (citace únor, 2., 2004) URL : http://cscs.umich.edu/~crshalizi/notebooks/john-holland.html [16] – DAVIS, T., C., Semantic Differential Analysis (citace únor, 5., 2004) URL : http://www.nichols.edu/faculty/Davis/PDS/semdiffdesii.htm [17] – UNDERWOOD, Mick, Semantic differential, 2003 (citace únor, 5., 2004) URL : http://www.cultsock.ndirect.co.uk/MUHome/cshtml/introductory/semdif.html [18] – neznámý autor, UseNet, 2003 (citace únor, 20., 2004) URL : http://www.usenet.com [19] – neznámý autor, Latent Semantic Analysis, 2003 (citace b ezen, 7., 2004) URL : http://lsa.colorado.edu/ [20] - CAMPBELL , Anthony, Bert Hölldobler and Edward O. Wilson - JOURNEY TO THE ANTS, 2002 (citace b ezen, 10., 2004) URL : http://homepage.ntlworld.com/anthony.campbell1/bookreviews/r/holldoblerwilson.html [21] – REYNOLDS, Craig, Boids, 1995 (citace b ezen,15., 2004) URL : http://www.red3d.com/cwr/boids/ [22] – KVASNI KA, V. POSPÍCHAL, J. TI O, P. Evolu né algoritmy. 1. vyd. Bratislava : Vydavate stvo STU, 2000, 223s. Edícia vysokoškolských u ebníc ISBN 80-227-1377-5
- 63 -
