Prírodou inšpirované algoritmy

Programovanie samoreprodukujúcich sa slučiek

Táto kapitola je prakticky prekladom 4.kapitoly článku Reggia, Lohn, Chou, 1998

Spôsob programovania samoreplikátorov sa dá nájsť už vo von Neumannových pôvodných univerzálnych počítačoch - konštruktéroch (Neumann, 1966). Množina inštrukcií (signálov) alebo popisov na páske reprodukujúcej sa štruktúry, ktoré popisujú jej vlastnú štruktúru sa môže nazvať programom stroja. Podobne postupnosť inštrukcií ktoré obiehajú po samoreprodukujúcej sa slučke tvorí program, ktorý riadi jej reprodukciu. Takéto programy sa v minulosti týkali len reprodukcie slučky. Počas nedávnych rokov však myšlienka programovania samoreprodukujúcich sa slučiek sa upiera tým smerom, aby robili aj niečo iné ako rozmnožovanie a teda získava stále väčšiu pozornosť. Základnou myšlienkou je, že postupnosti signálov riadiacich reprodukciu štruktúry môžu byť nejakým spôsobom rozšírené, aby riešili určitú triedu úloh, zatiaľ čo sa objaví reprodukcia. Motiváciou pre takéto programované replikátory je, že poskytujú nové, výrazne súbežné výpočtové prostredie, ktoré môže viesť od zdĺhavých ku silným, veľmi rýchlym výpočtovým metódam.

Jeden prístup ku programovaniu samoreprodukujúcich sa slučiek na riešenie úloh je rozšírenie postupnosti signálov obiehajúcich po slučke, pridanie ďalších signálov predstavujúcich program, ktorý nesie nejakú úlohu. Tento aplikačný program sa skopíruje zároveň s programom reprodukcie pričom sa nemení z generácie na generáciu počas reprodukovania slučky a spúšťa sa každou slučkou raz medzi jednotlivými reprodukciami. Uskutočniteľnosť tohoto prístupu bola nedávno predvedená naprogramovaním čiastočne zapuzdrených slučiek na zostrojenie istej vzorky vo vnútri každej novej slučky (Tempesti, 1995). Pri použití slučky so štyrmi ramenami s 9 bunkovým okolím sa dal vytvoriť na slučke prázdny priestor pre aplikačný program spravovaním väčšej časti reprodukčného procesu do funkcie zmien slučky. Cena, ktorú sme zaplatili za samočinný rast slučky a spustenie aplikačného programu závisí na zložitosti množiny pravidiel. V tejto situácii je obyčajne potrebných 100 000 pravidiel (Tempesti, 1995).

Praktický problém s vyššie uvedeným prístupom k programovaniu slučiek je obmedzené množstvo voľného priestoru, ktorý je v slučke použiteľný pre údaje aplikačného programu. Tento problém sa dá vyriešiť pridaním "pások" ku slučkám (Perrier et al., 1996). Tieto sú podobné páskam použitým v skorších počítačovo - konštruktérových replikátoroch (Codd, 1968; Neumann, 1966). Ak použijeme dve pásky, jedna sa môže použiť na uloženie postupnosti signálov predstavujúcej aplikačný program, zatiaľ čo druhá na uloženie údajov úlohy. Použitie tohto prístupu pri päťbunkovom okolí ukázalo, že je možné naprogramovať samoreprodukujúcu sa slučku na kontrolovanie zátvoriek (Perrier et al., 1996). Výraz so zátvorkami je zapísaný na údajovej páske a program kontroluje, či sú zátvorky tvarované alebo súmerné, výpočet zhodujúci sa s rozpoznávaním podľa neregulárneho jazyka. Tento proces používa bunky so 63 stavmi a zhruba 8500 stavové pravidlá zmien vo funkcii zmien. Dá sa ukázať, že slučky rozšírené o pásku sú schopné spustenia akéhokoľvek programu Perrier et al., 1996). V zásade teda takéto rozšírené samoreprodukujúce sa slučky vykazujú výpočtovú všestrannosť tak ako tie najskoršie samoreprodukujúce sa štruktúry, ale sú oveľa jednoduchšie.

Vyššie popísané programovateľné samorozmnožujúce sa slučky presne zapisujú množinu inštrukcií, ktoré riadia riešenie úlohy na slučke alebo na pripojenej páske. Tento aplikačný program je bez zmeny kopírovaný z rodiča do dieťaťa, takže každá generácia slučiek spúšťa presne ten istý program s presne tými istými údajmi. Nedávno sme skúšali iný prístup v ktorom možné riešenia sú pripojené k postupnosti inštrukcií pre reprodukciu, ktorá obieha v slučke (Chou & Reggia, 1998). Na rozdiel od minulých prístupov nie je počiatočné riešenie úlohy skopírované presne z rodiča do dieťaťa, ale sa z generácie na generáciu mení. Každá detská slučka dostáva iné čiastočné riešenie úlohy. Ak slučka nájde správne úplné riešenie úlohy, prestane sa rozmnožovať a ponechá si to riešenie ako svoju obiehajúcu vzorku. Na druhej strane ak toto riešenie nie je použiteľné, slučka "zomrie" (zmizne) bez potomkov. Takže na proces vytvárania kolónie slučiek sa môžeme pozerať ako na súbežné prehľadávanie stavového priestoru a priestoru riešení úloh. Na konci tohto procesu, keď sa reprodukcia zastaví, bunkový priestor obsahuje jednu alebo viac nereprodukujúcich sa slučiek, každú s obiehajúcou postupnosťou signálov, ktoré obsahujú správne riešenie úlohy (za predpokladu, že také riešenie jestvuje).

Nedávno sme použili tento prístup tvorby možných riešení a vyraďovania tých nepoužiteľných na riešenie úloh uspokojiteľnosti (SAT úlohy - satisfiability problem), klasického príkladu NP úplnej úlohy (NP-complete problem) (Hopcroft & Ullman, 1979). K danému booleovskému predikátu ako P = (~x1vx3)^(x1v~x2)^(x2v~x3), je úloha SAT: "Aké hodnoty booleovských premenných x1, x2 a x3 môžu vyhovieť tomuto predikátu?". V tomto prípade P bude pravdivý ak x1 = 1, x2 = 1 a x3 = 1. Tento predikát je v normálnom konjunktívnom tvare, kde sa každá časť predikátu v zátvorkách nazýva klauzula. Úloha SAT je obyčajne v tvare m-SAT úlohy, ak máme m booleovských premenných v klauzule predikátu. Predchádzajúci príklad P je teda 2-SAT úloha.

Nasledujúci obrázok znázorňuje proces vytvárania a výberu pre samorozmnožujúcu sa slučku, ktorá nesie tri dvojkové bity predstavujúce tri premenné x1, x2, x3 použité v predikáte P. V počiatočnej slučke v t = 0 sú nepreskúmané bity označené znakom A. Tieto A nahrádzajú niektoré z o tvoriacich signálovú cestu v slučke. Pôvodný signál rastu > je tiež nahradený znakom +, ktorý odráža niektoré malé rozdiely v reprodukčnom procese (znak údajovej dráhy O použitý v predchádzajúcich obrázkoch sa tu tiež zmenil na malé o aby sme zabránili zmýleniu s číslicou 0). Preskúmané bity sú v slučkách reprezentované buď číslicou 1 alebo 0. Postupnosť bitov, ktorú slučka nesie sa číta v smere hodinových ručičiek začínajúc hneď po písmene L. Takže napríklad ľavá dolná slučka na obrázku v t = 124 nesie postupnosť 001.

Bez vykonávania výberu by sa v troch generáciách objavilo všetkých osem možných hodnôt booleovských premenných použitých v P, nesených ôsmimi slučkami v priestore celulárneho automatu, za predpokladu, že nenastali žiadne zrážky. Slučky sa prestanú rozmnožovať akonáhle sú preskúmané všetky ich A bity. Keďže skúmanie bitov sa robí po jednom bite v každej generácii a pretože v každom kroku skúmania sa objaví v rodičovských a dcérskych slučkách iný bit, môžeme si byť istý, že všetky možné hodnoty premenných nájdeme počas generačného procesu, ak sa v priestore nevyskytnú žiadne zrážky slučiek. Ak sa zrážky vyskytnú, slučka, ktorá sa nebola na začiatku rozmnožovať sa bude snažiť tak urobiť pokiaľ sa bude objavovať na to potrebný priestor.

Pre odstránenie slučiek, ktoré nevyhovujú predikátu úlohy, každá bunka v priestore bude slúžiť ako monitor. Každý monitor testuje jednu z klauzúl predikátu. Ak sa podmienka, ktorú bunka pozoruje v úlohe monitora nájde, zničí slučky ktorá ňou prechádza. Pre určitý predikát P sú v priestore celulárneho automatu umiestnené tri triedy monitorov, z ktorých každý testuje jednu z nasledujúcich podmienok: x1^~x3, ~x1^x2 a ~x2 ^x3. Tieto podmienky sú len negované klauzuly predikátu P. Ak nie je vyhovené niektorej z klauzúl predikátu P, nie je vyhovené celému predikátu. Monitor zničí slučku, ktorá cez neho prechádza ak sa zistí, že jej príslušná klauzula nevyhovuje pre postupnosť bitov, ktorú slučka nesie. Tento proces zisťovania je vykonávaný v lineárnom čase pretože každý monitor je v podstate určitý automatický stroj a postupnosť bitov, ktorá cez neho prechádza sa dá chápať ako reťazec pre rozoznávanie bežného výrazu. S dostatočným množstvom správne rozmiestnených monitorov v priestore celulárnych automatov, tieto môžu účinne odstrániť všetky nevyhovujúce riešenia.

Niektoré kroky procesu vytvárania a výberu tej istej slučky 3x3 sú na obrázku. Začínajúc s jednou počiatočnou slučkou nesúcou úplne nepreskúmanú postupnosť bitov AAA v čase t = 0, sa v t = 44 v prvej generácii objaví v rodičovskej slučke 0AA a v dcérskej 1AA. V druhej generácii získame dve nové slučky nesúce 01A a 11A, ktorých rodičia teraz nesú 00A a 10A. Ak všetko prebieha v poriadku, v tretej a poslednej generácii by sme mali dostať ešte štyri slučky 011, 111, 001 a 101, ich štyria rodičia by niesli 010, 110, 000, 100. Ak nenastal žiadny výber a žiadna zrážka, mali by sme mať všetkých osem možných hodnôt pre trojbitovú dvojkovú postupnosť. Aj keď v tomto obrázku je vidieť, že niektoré zo slučiek sú zničené alebo neboli vôbec vytvorené po druhej generácii. Napríklad tá najvyššia slučka v t = 82 sa vymaže (t = 84, t = 86). Pretože pomocou monitorov sa zistilo, že čiastočne preskúmané bity 01A tejto slučky nevyhovujú jednej z klauzúl, už nie je potrebné skúmať ďalej, pretože všetci jej potomkovia budú niesť tie isté dvojkové bity. V troch generáciách ostávajú v priestore celulárnych automatov namiesto ôsmich len dve slučky (t = 134). Tieto slučky nesú presne tie dve hodnoty booleovských premenných, ktoré vyhovujú pôvodnému predikátu P SAT úlohy, ktoré sú 000 a 111.