Umíme recyklovat myšlenky?

Abstrakt
Artificial life je oblastí umělé inteligence, která se více než jiné oblasti nechává inspirovat procesy, probíhajícími v živé přírodě. Většinou ale tyto procesy převádí do abstraktní roviny a realizuje zcela odlišným způsobem - často pomocí virtuálního paralelního počítače. Tento článek se zabývá především otázkou, zda nám může v návrhu a konstrukci těchto vitruálních počítačů pomoci znalost historické výpočetní techniky. Jako příklady software budu používat především systémy Tierra a Avida, které znám nejlépe.

Úvod

Simulátory přírodního prostředí (dále jen SPP1) mají pravděpodobně kořeny v experimentech s celulárními automaty. Ty, přestože jejich činnost je definována pomocí malé skupiny pravidel, mohou projevovat komplexní vlastnosti jako je replikace informace, její propagace apod. Jako příklad může posloužit např. Codův CA, který podle Kelemena [1] "byl teoreticky schopen emulovat Turinguv stroj a též vytvořit svou vlastní kopii", přestože používal síť stavových automatů pouze s osmi stavy a pouze 500 pravidly (z 82 tj. 32768 možných). Návrh celulárních automatů je poměrně obtížným úkolem, zvláště pokud chceme dosáhnout přesně určeného chování systému, pokud se však podaří, může vzniknout systém, který svým chováním připomíná např. kolonie bakterií a lze jej tedy považovat za druh life-like systému.

Další velkou skupinou jsou genetické algoritmy. Programování pomocí tohoto nástroje využívá jen poměrně malé části z rysů typických pro biologické systémy, a to především rysy, které mají přímou vazbu na evoluci. GA jsou vhodné především pro úlohy optimalizační a aproximační. V praxi známe mnoho problémů, které jsou obecně těžko nebo zcela neřešitelné, je ale možné je řešit stylem pokus-omyl. Např. u jednocestných algoritmů dokážeme provést výpočetní postup pouze jedním směrem.

Právě pro takové úlohy se genetické programování velmi hodí. Jednotlivá možná řešení jsou představována genomem (někdy se též používá termín string). Na počátku běhu programu je vytvořena populace s rozmanitým genomem (buď zcela náhodně nebo např. na základě nějakých znalostí problému - např. přibližného řešení). Jednotlivé organismy (genomy) jsou potom vyhodnoceny pomocí tzv. fitness funkce, která zjišťuje, nakolik vhodné řešení daný organismus představuje. Jedinci s nejvyšší fitness-hodnotou se do příští generace přenášejí s větší pravděpodobností. Do procesu vytváření následující generace zasahují náhodné mutace - vytváří se tak nová množina potenciálních řešení. Tento postup se neustále opakuje. V průběhu běhu programu se tak nalezená řešení postupně přibližují hledanému maximu fitness-funkce. Zajímavým rysem tohoto postupu, díky kterému jsou pravděpodobně GA tak populární je náhodné prohledávání definičního oboru fitness funkce, přičemž "rozptyl" hledání se se zvyšující dobou běhu programu zmenšuje a dočasné optimální řešení se přibližuje skutečnému optimu. Takovéto prohledávání je však výhodné pouze pro funkce s určitým průběhem - pro funkce silně chaotické (s velkou amplitudou a velkou strmostí na malém úseku definičního oboru) se efektivita prohledání přibližuje efektivitě prohledávání náhodného. (více o GAs viz např. [2])

Mimo jiné také kvůli obtížnosti návrhu jsou složitost chování CA a možnosti jeho použití ve výzkumu přírodních systémů omezené. Nevýhodou genetických algoritmů je zase velmi omezený rozsah chování, které můžeme považovat za life-like (prakticky pouze jakýsi druh evoluce nalézaných řešení). Vznikl tedy jiný přístup, který nazývám SPP. Jejich společným rysem je definování prostředí, ve kterém "žijí" virtuální organismy. Tyto mohou interagovat mezi sebou i s prostředím a mohou tedy vytvářet i specifické druhy chování, typické pro jejich jednotlivé druhy. Tím se tyto systémy skutečným biologickým soustavám opět o krok přiblížily. Za jistých podmínek zde můžeme hovořit o fylogenezi (velmi omezeně nebo vůbec o ontogenezi), fenotypu, společenství,nice atd. tedy o pojmech, které byly donedávna vyhrazeny pouze biologům, ekologům a sociobiologům.

Jedním z prvních zástupců SPP je program Tierra Thomase Raye[3]. V tomto programu je prostředí tvořeno virtuálními počítači, organismy jsou symbolizovány kódem, který je na těchto počítačích spouštěn. Nejvzácnějším zdrojem, o který všechny organismy vedou boj není jako v přírodním prostředí potrava nebo energie, ale strojový čas, přidělovaný jenotlivým virtuálním procesorům ná základě nejrůznějších kriterií - podle délky genomu, hodnoty fitness apod.

Jinou implementací SPP je software Avida, vyvíjený na California Institute of Technology[4],který je systémem Tierra inspirovaný a v mnohém podobný. Od Tierry se odlišuje především ještě větším přiblížením biologické realitě - prostředí je zde totiž reprezentováno pravoúhlou sítí, kde je na každém uzlu umístěn jeden virtuální počítač. Děje v prostředí tak zíkávají i rozměr délkový, zatímco v Tieře je pouze jediný rozměr - čas. Jinými rysy Avidy se nebudu dále zabývat, protože to není hlavní náplní tohoto článku.

Speciální kapitolou jsou programy simulující chování společenských zvířat - nejčastěji hmyzu. Hmyz je pro modelování a výzkum velmi vhodný, protože kombinuje jednoduché a značně deterministické chování jednotlivce se složitým chování společenství - hodí se tedy především ke studiu emergence. Zcela jinou oblastí, která také hledá inspiraci v biologii a využívá výpočetní techniku, je robotika. Jelikož s těmito skupinami aplikací teorií artificial life nemám zkušenosti, odkážu případného zájemce pouze na literaturu - v češtině je nejlepším studijním pramenem série Umělá inteligence 1-3 od nakladatelství Academia a knihy J.Kelemena, v angličtině je literatury opravdu hodně, mnoho z ní je k dispozici v on-line formě na Internetu - jen pro ilustraci: [2],[5-8].

Kontrukce SPP

Problematiku realizace SPP můžeme rozdělit do několika problémových oblastí:

  1. Návrh virtuálního počítače
  2. Propojení těchto počítačů a způsob výměny informací mezi nimi
  3. Návrh instrukční sady
  4. Návrh organismů
Znalost historie výpočetní techniky nám může pomoci především s body 1-3, proto jim budu věnovat nejvíce prostoru.

Nice place for living: Virtuální počítač

Implementace virtuálních počítačů do značné míry určuje využitelnost SPP-software. Je to totiž hlavní výkonná část, která propůjčuje organismům život. Běžně se prostředí v simulátorech skládá z několika virtuálních počítačů, které meyi sebou mohou přesně definovaným způsobem interagovat. Vzniká tak virtuální paralelní stroj typu MIMD (multiple instructions multiple data). Existují sice i pokusy implementovat SPP na masivně paralelní výpočetní technice (např. connection machine), ale jelikož jsou tyto počítače pro většinu z nás naprosto nedostupné, nebudu se jim dále věnovat.

Virtuální počítač v Avidě i v Tieře je tvořen na základě von Neumannova schématu a blíží se tak skutečnému počítači. Domnívám se, že výkon těchto strojů je porovnatelný se skutečnými počítači přibližně v době sedumdesátých let (z hlediska konstrukce bychom je však mohli symbolicky zařadit do 1,5-té gnerace - většinou namají žádnou podporu vyšších programovacích prostředků, ale např. velikostí disponibilní paměti historické počítače první generace překonávají). Poměrně malá rychlost je způsobena tím, že simulátor obvykle obsahuje značně náročnou režijní část. Kvůli snaze o maximální přiblížení skutečně paralelnímu běhu jsou aktivní CPU přepínány i třeba po jedné instrukci, což může být značně neefektivní, ale pro dané využití potřebné. Náročné na strojový čas je i statistické sledování dění v simulátoru, popř. jeho grafické znázornění (pokud jej software obsahuje). Rozdíl oproti historickým počítačům spočívá především ve značně přizpůsobené instrukční sadě (především Tierra), která např. obsahuje velmi omezené nástroje pro aritmetiku. Dalším velkým rozdílem je šířka "datové sběrnice" - tedy maximální rozsah zpracovávaných čísel. Ten se může odvíjet od hostitelské architektury a může tedy historické počítače silně překonat. Naopak velmi podobné jsou vstupně/výstupní buffery v Avidě - jsou čteny a zapisovány sekvenčně, čímž připomínají děrnou pásku.

Tamtamy, kouřové signály a halekání přes údolí: Komunikace mezi body sítě

Jak jsem se již zmínil výše, Avida se od Tierry liší především přidáním délkového rozměru. v Tieře má program právo zápisu pouze do svého paměťového prostoru. Obsah pamětí ostatních počítačů však může číst nebo spouštět, přičemž nejsou dány žádné prostorové vztahy (tzv. globální interakce). V Avidě může naopak vCPU přistupovat pouze k paměťovým prostorům sousedních uzlů mřížky (lokální interakce). Analogii ve světě skutečných počítačů zde najdeme spíše v současnosti než minulosti - např. v podobě lokálních sítí s přístupem k počítačům ve stejném segmentu (LAN) a globální síti Internet (TCP/IP).

1+1=2: Instrukční sada

Instrukční sady Avidy (je jich několik a je možné mezi nimi přepínat) se podle jejích autorů řídí následujícími pravidly [9]:

  1. IS by měly by být pokud možno kompletní (v Turingově smyslu a také obecně - aby umožnily zápis základních operací pouze několika instrukcemi)
  2. Každá instrukce by měla být robustní a univerzální - svoji činnost by měla vykonávat při každém spuštění, nezávisle na okolnostech
  3. Redundance v IS by měla být co nejmenší
K tomu bych ještě dodal poznámku (autoři manuálu ji zřejmě považovali za samozřejmost), že jelikož v průběhu běhu simulace dochází k vzniku náhodných kombinací instrukcí, musí být IS implementována tak, aby v žádném případě nedošlo k "zatuhnutí" nebo zacyklení simulace. V tom se IS SPP od skutečných počítačů liší - v nich je totiž program pečlivě připraven podle daných pravidel IS. Výsledkem je, že velká skupina kombinací instrukcí z množiny všech možných kombinací je buď neplatná nebo přímo způsobí nucené zastavení běhu programu. Tato situace nesmí v SPP nikdy nastat a na návrh IS jsou tedy v tomto ohledu tedy kladeny vyšší nároky.

Instrukční sady SPP se od IS skutečných počítačů liší, ale zároveň se jim i podobají. Znalost IS historických počítačů nám může pomoci navrhovat IS pro SPP efektivněji, jelikož prostředky virtuálních počítačů jsou podobně omezené jako prostředky historické výpočetní techniky (např. instrukce v Tieře jsou kódovány pouhými pěti bity). Konstrukce IS může velmi značně ovlivnit vlastnosti simulace. U systémů Avida a Tierra jsou instrukce velmi jednoduché (jakoby paralela RISC procesorů) a lze tedy považovat za úspěch, pokud se organismus zvládne rozmnožit. Na druhou stranu existují simulátory s instrukcemi vyšší úrovně (CISC), ve kterých mohou vznikat organismy se složitějším chováním. Typická instrukce takové IS může být např. "Zkopíruj svůj genom na sousední buňku".

Zvláštností IS v SPP je adresace, která bývá relativní a většinou je implementována systémem komplementárních adres - k adrese uvedené za instrukcí se nalezne komplementární adresa a na té je provedena operace. To umožňuje "relokaci" kódu - nezáleží na tom, na jakém místě v genomu je instrukce umístěna.

Problematice instrukčních sad v SPP by bylo možno věnovat samostatný článek - zde bohužel nemám prostor pro detailnější rozbor. Skončím pouze konstatováním, že mezi IS historických počítačů a SPP lze vystopovat podobnosti, které by možná stály za podrobnou analýzu, která by nám mohla pomoci návrh IS pro SPP zefektivnit.

Tělo je duch: Organismy

Zatímco v našem světě mnozí filosofové zdůrazňovali rozdíl mezi tělem a duší, v umělém životě je tomu právě naopak - organismy jsou totiž tvořeny jen informací a tedy rodíl mezi tělem a duší (lze-li tento pojem vůbec použít) se u nich smazává. Interpretace genomu může být různá - můžeme jej např. definovat jako sled instrukcí, které se budou v průběhu života provádět (např. Avida,Tierra), jako předpis k vytvoření funkční struktury, jejíž formou může být např. neuronová síť (např.LEE), nebo kombinace výše zmíněného, obohacená např. o možnost dědění některých získaných vlastností (tzv. lammarckistická dědičnost, s realizací v rámci artificial life jsem se zatím nesetkal). Pokud bychom se chtěli maximálně přiblížit biologickým systémům, byla by pravděpodobně nejlepší volbou neuronová síť, vytvořená na základě genomu a schopná učení v průběhu života organismu, případně ještě přenášející část svého stavu na potomstvo.

Jednotlivá řešení mají výhody i nevýhody, jsou prováděny pokusy s různými implementacemi. Jelikož se ale jednotlivé systémy značně liší i v ostatních parametrech a ne jen v implementaci organismů, je posouzení efektivity jednotlivých řešení obtížné či zcela nemožné.

Shrnutí

Analogie mezi světem skutečných počítačů a virtuálních počítačů SPP existují a v některých případech jsou i velmi těsné. Studium historických prostředků výpočetní techniky, jejich řešení a koncepcí by nám podle mého mohlo při programování SPP pomoci zejména v těchto oblastech:
  1. Návrh instrukčních sad - především zlepšení využití prostoru daného šířkou instrukce
  2. Optimalizace - SPP mají prostředky podobně omezené jako počítače minulosti - zatímco skutečné počítače dneška jsou natolik výkonné, že optimalizací se programátoři zabývají čímdál méně (v kurzu jsou spíše systémy RAD - tedy rychlého vývoje SW, ale produkující pomalu běžící a zbytečně mohutný kód)
  3. Konstrukce jednoduchých programovacích jazyků, umožňující zápis genomů pohodlnějším způsobem než použitím nativního simulátorového "assembleru"2.

Závěr

Umělá inteligence prožívá po krizi přístupu "shora dolů" opět comeback v podobě přístupu "zdola nahoru". V dnešní době se už oblast AI dělí na mnoho podoblastí, které se vzájemně liší premisami, přístupem i metodologií. Význam artificial life vidím v tom, že nám může pomoci získat lepší vhled do procesů, probíhajících v biologických systémech. Nová vlna AI je zároveň velkou intelektuální výzvou a zároveň také "líhní" problémů i pro vzdálenější obory jako je například filosofie, etika, sociologie, apod. Zcela seriózně se řeší problémy, které bychom ještě před několika desetiletími považovali za výplod nerealisticky myslícího snílka - např. problém nevypojitelnosti - unpluggability (tedy nebezpečí, že evoluce s otevřeným koncem přeroste v existenci nepřátelskou lidskému druhu), problém obecné definice života (rozdíl pozemského života - life-as-we-know-it, Earth-life a eoretického obecného života - life-as-it-could-be)atp.


1 Tento termín by asi mnoha autorům popisovaných programů nevyhovoval - někteří považují svůj software nikoli za simulátor, ale za skutečnou instanci života (viz pojem silná AI). Jiní se ve svých programech od přírodních zákonů natolik odchylují, že jejich díla lze těžko považovat za simulátory přirozeného prostředí. Přesto tento termín budu dále v článku používat - laskavý čtenář mi to doufám promine a autoři programů o tom nemusi vědět.
2 Především by bylo vhodné vymyslet nějaký způsob zpětného překladu - často totiž výzkumník potřebuje analyzovat, jaké konstrukce v průběhu evoluce vznikly a analýza assembleru je značně náročná.

Literatura

[1] Kelemen,J.: Umělý život. v: Mařík,V.,Štěpánková,O.Lažanský,J.a kol.:Umélá inteligence 3. Praha:Academia.2001.
[2] Kelemen,J.,Sosík,P.(eds.): Advances in Artificial Life. Berlin:Springer.2001.
[3] www.hip.atr.co.jp/~ray/tierra/tierra.html
[4] dllab.caltech.edu/avida
[5] www.alife.org
[6] Linux AI&ALife HOWTO: http://www.ai.uga.edu/~jae/ai.html
[7] Journal of Artificial Intelligence Research: www.cs.washington.edu/research/jair/home.html
[8] Gomi,T.(ed.): Evolutionary Robotics. Berlin:Springer.2001. (některé tituly nakladatelství Springer jsou v plné verzi on-line k dispozici na www.springer.de)
[9] Avida User's Manual - on-line dllab.caltech.edu/avida/index.shtml#manuals