Prírodou inšpirované algoritmy

Wolframov Celulárny Automat

Podkapitoly:

Applet

Wolframov CA

Nový impulz do výskumu CA priniesol Stephen Wolfram (Wolfram, 1984) . Podľa jeho názoru dospela veda pri štúdiu rôznych foriem zložitých systémov od turbulencie kvapalín cez ekonomické systémy až k živým organizmom do štádia prechodu, od experimentov s reálnym materiálom k experimentom na počítači. Prostredie, poskytované počítačom je totiž na jednej strane abstraktné, na strane druhej je ale reálne existujúce. A práve štúdium správania CA sa mu javilo vhodným experimentom tohto druhu.

Wolfram študoval vlastnosti jednorozmerných CA: ich výhodou bol pomerne malý počet možných pravidiel a názorná reprezentácia postupností generácií v riadkoch pod sebou. V najjednoduchšom prípade sa jedná o dvojstavový systém, kde okolie pozostáva z dvoch bezprostredných susedov. Nová hodnota bunky je teda určená trojicou starých hodnôt. Táto trojica môže mať osem podôb a tejto osmici možno priradiť 28 výstupných kombinácií, teda výsledný počet možných skupín pravidiel je 256. Na ďaľších obrázkoch sú uvedené pravidlá v grafickej podobe (trojica buniek tvoriaca okolie a pod ňou nová hodnota). Obvykle sa udáva číslo sady pravidiel ako dekadický ekvivalent binárne interpretovaného vektora nových hodnôt. Na obrázku vľavo je sada 22 a vpravo 109.

Dynamiku 1D automatu je možné dobre znázorniť tak, že v prvom riadku je východzí stav automatu (čas t=0) a pod ním sa zakreslujú postupne stavy v časoch t=1, 2, 3,...

Wolfram rozdelil týchto 256 CA do štyroch skupín podľa zložitosti chovania (tieto triedy sa vyskytujú u všetkých ďalších CA a to nielen 1D):

• CA1 - celý riadok sa rýchlo vyprázdni (sada 40 - nasledujúci obrázok) alebo zaplní




• CA2 - počiatočná aktivita sa postupne utlmuje a začínajú prevládať stabilné zhluky (sada 228 - na ďaľšom obrázku vľavo), prípadne pomerne jednoduché, cyklicky sa opakujúce štruktúry (sada 109 - Na ďaľšom obrázku vpravo)

  . .

  Periodický režim lepšie vynikne pri väčšom rozmere automatu, ako je vidieť na ďalšom obrázku.





• CA3 - prevláda zdanlivo chaotický vývin; voľným okom nie je možné pozorovať nejakú pravidelnosť; obrazce pôsobia ako náhodný šum (sada 22)




• CA4 - vykazujú zložitú, ale zrejmú pravidelnosť, generujú sa nové - obvykle posuvné štruktúry (napr. klzáky v LIFE); štruktúry žijú pomerne dlho (sada 110); tieto CA sú schopné realizovať univerzálny počítač.

V uvedených príkladoch sa proces začínal vždy náhodne generovaným riadkom. Niektoré sady pravidiel generujú zaujímavé fraktálové obrazce. Napríklad sada 90 s jedinou bunkou uprostred riadku generuje Szierpinského trojuholníky (na nasledovnom obrázku je prvých 128 generácií).

Wolfram poukázal tiež na zaujímavú skutočnosť: mnohé lastúry majú navlas rovnakú textúru, aká mu vyšla z CA4.