Prírodou inšpirované algoritmy

Modelovanie samoreprodukcie

Táto kapitola je prakticky prekladom úvodnej časti článku Reggia, Lohn, Chou, 1998

Výpočtové modelovanie samoreprodukujúcich sa štruktúr/strojov bolo často založené na celulárnych automatoch (bunkové automaty, cellular automata, CA). K modelovaniu pomocou celulárnych automatov sa pristupovalo troma spôsobmi. Prvé samoreprodukujúce sa štruktúry (60. a 70. roky) boli rozmerné, zložité univerzálne systémy modelované podľa Turingových strojov. Poskytovali prvý dôkaz toho, že samoreprodukujúce sa štruktúry sa v zásade dajú zostrojiť a teda aj teoreticky simulovať. V druhej generácii samoreprodukujúcich sa štruktúr (80. roky) boli skúmané samoreprodukujúce sa slučky navrhnuté tak, aby boli kvalitatívne jednoduchšie ako ich predchodcovia. Toto sa dosiahlo vynechaním kritéria, že reprodukované štruktúry musia byť tiež schopné univerzálneho výpočtu a konštrukcie. Neskôr sa rozhodlo pre tretí prístup, ktorý sa zameriava skôr na samoreprodukciu ako na vznikajúcu vlastnosť na rozdiel od minulého prístupu, ktorý bol založený výlučne na ručne zostrojených kópiách. Táto štruktúra ukazuje, že samoreprodukcia môže vzniknúť z náhodných počiatočných stavov a že pravidlá na ovládanie samoreprodukcie sa dajú objavovať použitím metód umelej evolúcie (genetické algoritmy). Tiež sa stanovilo, že samoreprodukujúce sa štruktúry sa počas rozmnožovania súčasne môžu používať na riešenie problémov.

Nasledujúce modely samoreprodukcie sú implementované v štruktúrach celulárnych automatov (Farmer et al., 1984; Gutowitz, 1991; Wolfram, 1994). Pri každom modeli celulárneho automatu sú všetky zmeny stavu bunky riadené sústavou prechodových pravidiel, ktoré tvoria prechodovú funkciu. Každé prechodové pravidlo je jednoduché a založené výlučne na “miestne“ prístupnej informácii. "Miestnosť" výpočtu vyjadruje skutočnosť, že bunka môže meniť svoje stavy len na základe stavov svojich susedov (vrátane jej vlastného aktuálneho stavu), teda je základným hľadiskom výpočtov celulárnych automatov. Napriek takému “miestnemu“ spracovaniu informácie, skúsenosť ukazuje, že celá sústava pravidiel zmien a zároveň ich aplikáciou vo všetkých bunkách v modeli, dokáže vytvoriť veľmi bohaté a niekedy prekvapivé správanie.

Matematik John von Neumann použil ako prvý celulárne automaty na skúmanie logického usporiadania samoreprodukujúcich sa štruktúr (von Neumann, 1966). V jeho a väčšine ďalších prác sú použité dvojrozmerné priestory celulárnych automatov, kde bunky môžu byť v jednom z niekoľkých možných K stavov. Väčšina buniek je vždy v pokoji alebo neaktívna. Tie bunky, ktoré sú aktívne boli nazvané prvkami (components, zložkami). Samoreprodukujúca sa štruktúra je reprezentovaná ako usporiadanie navzájom prepojených činných buniek, z ktorých každá predstavuje prvok reprodukujúceho stroja. Pretože v každom okamihu simulovaného času každá bunka určuje svoj nasledujúci stav ako funkciu jej súčasného stavu a stavov jej najbližších susedov, akékoľvek samoreprodukujúce sa štruktúry pozorované v uvažovaných modeloch musia byť vznikajúcim správaním pochádzajúcim z prísne miestneho vzájomného pôsobenia. Výhradne na základe týchto súbežných miestnych interakciách, samoreprodukujúca sa štruktúra (určená na začiatku) prechádza postupnosťou krokov, aby vytvorila svoju kópiu (ktorá je vzhľadom na originál umiestnená na inom mieste a možno pootočená).

Von Neumannova pôvodná samoreprodukujúca sa štruktúra je zložitý univerzálny počítač - konštruktér uložený vo veľkom dvojrozmernom priestore celulárnych automatov, ktorý sa skladá z 29 stavových buniek. Je založený na Neumannovom okolí (päťbunkovom usporiadaní) a je to doslova simulovaný digitálny počítač (Turingov stroj), ktorý používa "konštrukčné rameno" spôsobom krok po kroku na vytváranie svojich kópií pomocou inštrukcií na "páske". Počiatočný stroj je univerzálnym konštruktérom a môže vytvoriť kópiu akejkoľvek štruktúry presne popísanej na svojej páske (Burks, 1970). Tiež môže skopírovať svoju vstupnú pásku a pripojiť ju k novej štruktúre. Samoreprodukcia teda môže nastať ak dáme pôvodnému stroju pásku s popisom svojej vlastnej štruktúry. Jedna z dôležitých myšlienok uvedených vo von Neumannovom univerzálnom počitači - konštruktérovi je myšlienka signálových ciest (data path), po ktorých môžu prúdiť signály. Konštrukcia von Neumannovho univerzálneho počítača - konštruktéra sa dá nájsť v (Burks, 1970; von Neumann, 1966).

Zatiaľ čo John von Neumann potvrdil, že samoreprodukcia je možná, otvorená ostala otázka minimálneho logického usporiadania potrebného pre samoreprodukciu. Veľa ďalších prác bolo zameraných na hľadanie jednoduchších samoreprodukujúcich sa štruktúr. Napríklad, výskumníci ukázali, že isté zjednodušenie Von Neumannovskej konfigurácie bolo možné rekonštrukciou určitých prvkov (Thatcher, 1970) alebo zvýšením zloženosti stavov bunky (Arbib, 1996). Najvplyvnejšia z pomedzi týchto starších prác bol Coddov dôkaz, že ak prvky alebo stavy buniek splnia určité požiadavky na súmernosť, potom John Von Neumannov model sa dá urobiť jednoduchšie, použitím buniek, ktoré majú len 8 stavov oproti pôvodným 29 (Codd, 1968). Codd dokázal, že použitím súmerných prvkov sa dá zostrojiť jednoduchší model a zostrojil univerzálny počítač - konštruktér, ktorý bol síce jednoduchší, ale aj tak podobný von Neumannovmu.