Árpád
-1 °C
9 °C

A gépi evolúció építőkövei

2003.07.12. 20:05
A sejtautomaták a computer-tudomány és a mesterségesintelligencia-kutatás több elméleti problémájának elemzésére alkalmas modellek, például a tömbszámítógépek által történő párhuzamosítás, vagy annak kérdésének, hogy képesek-e önreprodukálásra a gépek. Az ágensek kisszámú, egyszerű, uniformizált és lokális szabályt hajtanak végre.
Ám ezek az egyszerű szabályok igen gyakran eredményeznek komplex és emergens viselkedésmintákat_ Olyan mintákat, melyek (s a hozzájuk vezető folyamatok) tanulmányozása a "valós élet" különböző jelenségeire adhat választ.

Egy és kétdimenziós automaták

A sejtautomata (cellular automaton) "az azonos szomszédsági mintázat szerint összekapcsolt, szinkronizáltan működő sejtek (cellák) olyan összessége, ahol az egyes sejtek állapota csak saját és szomszédainak állapotától függ" - definiál Roska Tamás. "A következő állapotot az átmeneti függvény adja meg." Mind memória-, mind processzorelemekként sejteket, sejtek tömbjét használja. Stilizált univerzumokként is felfogható dinamikus rendszerek.

A legegyszerűbb modell, az egydimenziós automata sejtjei két lehetséges állapotban (on vagy off, még tetszetősebben: élve, vagy holtan) találhatók. Gyorsan változik a kezdeti konfiguráció: egy sejtsor véletlenszerűen kerül egyik, vagy másik állapotba (Line 1). Az alatta lévő sor már a második generáció (Line 2), melyben az összes sejt állapotát szabálysor határozza meg. Minden egyes sor állapota a felette elhelyezkedő sortól függ.

A legegyszerűbb szabály három sejtre vonatkozik: a második sor tetszőleges elemét a közvetlenül felette lévőtől, az attól jobbra és balra található példányok alakítják. A három sejt nyolcféleképpen fordulhat elő: 000, 001, 010, 011, 100, 101, 110, 111. Grafikusan megjelenítve, érdekes (és látványos) diagramokat kapunk. S még ezek a rendkívül szimpla szabályok is vezethetnek elképesztően bonyolult, önhasonló (self-similar) mintázatokhoz.

Önhasonló mintázatok

A kétdimenziós automaták bonyolultabbak, izgalmasabbak - John Horton Conway hatvanas évek végén, hetvenes évek elején kidolgozott Életjátéka (Game of Life) a legismertebb (négyzetháló) modell.

A sejtautomaták története

Stanislaw M. Ulam még a negyvenes években, Los Alamosban különböző számítógépes mintajátékokat talált ki. Meghatározott szabályok alapján a computer állandóan átalakuló, "szinte élő" mintázatokat, geometriai formákat nyomtatott ki. A sejtekből összeálló alakzatok gyakran egymást megsemmisítve küzdöttek az élettérért. Egy-egy adott sejt "élete" a szomszédos sejtektől függött.

Ulam javaslatára az akkoriban a gépi reprodukciót tanulmányozó Neumann János a mintajátékokat egy végtelenített sakktáblára alkalmazta. A sejtstruktúrára (s így egy - az absztrakt világot működtető - leegyszerűsített fizikára) azért volt szüksége, mert nélküle rendkívül nagy, szinte mérhetetlen mennyiségű kapcsolat jönne létre a komponensek között. Végül sikerült megvalósítania az elméleti modellt, és "bebizonyította, hogy megfelelő átmeneti függvény esetén a sejtautomata univerzális és önreprodukáló." (Roska Tamás)

Neumann munkáját Arthur Burks fejlesztette tovább, majd az adaptáció és az optimalizálás problémájára alkalmazva, a "genetikus algoritmusok atyjaként" emlegetett John Holland egy általános sejtautomata-szimuláló programot fejlesztett.

John Conway

John Horton Conway a sejtautomata-tervét a minimumig igyekezett egyszerűsíteni. Két állapotot, négy egyszerű szabályt használt, sejtenként nyolc szomszédos cellával, cellánként maximum egy sejttel:

John Horton Conway

- ha egy élő sejtnek kettőnél kevesebb szomszédja van, akkor meghal,
- ha háromnál több szomszédja van, akkor is meghal,
- ha egy halott sejtnek (üres cellának) pontosan három szomszédja van, akkor életre kel;
- máskülönben, az összes többi sejt eredeti állapotában marad.

A gyorsan (számítógéppel másodpercenkénti több generációs sebességgel) pergő játék során különös alakzatok keletkeznek, csoportok bukkannak elő, tűnnek el, aszimmetrikus formák szimmetrikusokká fejlődnek - mint a tényleges életben. A sikló (glider) a legjellegzetesebb közülük. Egy "ágyú" lövi ki, majd rendszerességgel újabb és újabb "sikló-testvérkékkel" népesíti be az univerzumot.

Sejtautomaták és emergencia

Stephen Wolfram, a sokak szerint az új tudomány alapművét (A New Kind of Science, 2002) jegyző fizikus a Neumann-automata egydimenziós változatán, azaz egy felettébb egyszerű modellen végezte kísérleteit a nyolcvanas években. Azt a konklúziót vonta le, hogy az összes egydimenziós automata a következő négy kategória valamelyikébe tartozik: homogén, ismétlődő minták (első osztály), periodikus stabil struktúrák (második osztály), véletlenszerű, rendezetlen alakzatok, mint a televíziós fehér zaj (harmadik osztály), komplex, időtálló szerkezetek (negyedik osztály). Utóbbi a legizgalmasabb, s egyben újabb példája az egyszerű összetevőkből emergens módon létrejövő, alapokból nem magyarázható bonyolult rendszereknek. Valószínűleg az Univerzális Turing-gép követelményeinek megfelelő formákat szintén találunk a negyedik osztályban.

A Wolfram-féle kategóriák mintái

Napjaink legintenzívebb sejtautomata-fejlesztései - talán nem véletlenül - a Santa Fe Intézetben (SFI) történnek. Genetikus algoritmusok segítségével vizsgálják, miként vezet az evolúció bonyolult információfeldolgozó-műveletekhez.

Az alkalmazások - a pirinyó organizmusoktól közlekedési dugók, egész városok életének a szimulálásáig - széles skálát ölelnek fel. Kémiai rendszereket, hangya-, vagy termeszrajokat, hópelyheket, ökoszisztémákat, a gazdaságot sejtautomatákkal is vizualizálják.

Felfedeznéd Portugáliát?

Itt a remek alkalom, hogy megismerd. Beszámolók, fotók - böngéssz!

Kreuzenstein mesevára

Nézd meg Te is Laczko legújabb fotóit!