Főoldal|Keresés|Oldaltérkép
Hírek|Konferenciák|Publikációk|Források|Linkek
Agent Portál a jövő információtechnológiájáról az AITIA International Zrt szerkesztésében az NHIT együttműködésével
Általános MI
MI részterületek
Magyar kutatók
Külföldi kutatók
Emergencia, ágensek
Mesterséges élet, szimuláció
Robotika
Internet, networking
Információs társadalom
NHIT
Hírközlés
Biotech, nanotech
Rövid hírek
 > Főoldal >  Hírek  >  Mesterséges élet, szimuláció  > 
Sejtautomaták
2011.02.02.
A sejtautomaták a számítástudomány sok elméleti problémájának (párhuzamosítás, képesek-e önreprodukálásra a gépek) elemzésére alkalmas modellek. Elemeik 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, amelyek (és a hozzájuk vezető folyamatok) tanulmányozása a való világ különböző jelenségeire adhat választ.

Egy és kétdimenziós automaták

A sejtautomaták (cellular automaton) diszkrét modellek, elemeik szabályos (elvileg akárhány dimenziós) rácsozatban elrendezett cellák (sejtek); mindegyik sejt véges számú állapot valamelyikét veheti fel, állapota csak a saját és a szomszédjai állapotától függ. Egyforma szabályok alapján működnek, amelyek végrehajtásakor mindig egy új generáció jön létre. Az automata mind memória-, mind processzorelemekként sejteket, sejtek tömbjét használja. Stilizált univerzumként is felfogható dinamikus rendszer.

A legegyszerűbb modell, az egydimenziós automata sejtjei két lehetséges állapotban (on vagy off, 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. Az alatta lévő sor már a második generáció, 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 egyszerű szabályok is vezethetnek elképesztően bonyolult, önhasonló (self-similar) mintázatokhoz.

A kétdimenziós automaták bonyolultabbak, izgalmasabbak – John Horton Conway 1960-as é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 az 1940-es é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 számítógép á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 sejt „élete” a szomszédoktól függött.

Ulam javaslatára az akkoriban a gépi reprodukciót tanulmányozó Neumann János a mintajátékokat 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 az összetevők között. Végül sikerült megvalósítania az elméleti modellt, és bebizonyította, hogy megfelelő átmeneti függvénnyel a sejtautomata univerzális és önreprodukáló.

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 általános sejtautomata-szimuláló programot fejlesztett.

John Horton Conway a sejtautomata-tervét a minimumig igyekezett leegyszerű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: 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 az életben.

Sejtautomaták és emergencia

Az 1980-as években Stephen Wolfram a Neumann-automata egydimenziós változatával, egy felettébb egyszerű modellel kísérletezett. Azt a következtetést vonta le, hogy az összes egydimenziós automata 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 szép példája az egyszerű összetevőkből emergens módon létrejövő, alapokból nem magyarázható bonyolult rendszereknek. (Wolfram gondolatait a cyberpunk íróként is ismert Rudy Rucker dolgozta tovább egy 2005-ös dolgozatban.)

A múlt évtized első felének legintenzívebb sejtautomata-fejlesztéseit a Santa Fe Intézetben (SFI) jegyezték. Genetikus algoritmusokkal vizsgáltá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.

(kf)

A www.agent.ai vebszájton található tartalom az AITIA International Zrt. szellemi tulajdona.
A cikkek másodközlését megelőzően vegye fel a kapcsolatot szerkesztőségünkkel.
Cikk küldése ismerősnek
Nyomtatóbarát verzió
Feliratkozás
hírlevélre

Feliratkozás az Rss csatornára RSS
Hajrá Peti!
Jogvédelem|Oldaltérkép|Impresszum