Automat komórkowy

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Definicja intuicyjna:
Automat komórkowy to system składający się z pojedynczych komórek, znajdujących się obok siebie. Ich układ przypomina szachownicę lub planszę do gry. Każda z komórek może przyjąć jeden ze stanów, przy czym liczba stanów jest skończona, ale dowolnie duża. Stan komórki zmieniany jest synchronicznie zgodnie z regułami mówiącymi, w jaki sposób nowy stan komórki zależy od jej obecnego stanu i stanu jej sąsiadów.

Automaty komórkowe, których struktury opisane są przez siatkę komórek oraz ich stany, przejścia i reguły tych przejść, są modelami matematycznymi. Tworzą one środowisko dla większych dyskretnych klas modeli, ponieważ wszystkie opisujące je struktury przyjmują wartości dyskretne.

Każdy automat komórkowy składa się z n-wymiarowej regularnej, dyskretnej siatki komórek, każda komórka jest taka sama (jest kopią poprzedniej), cała przestrzeń siatki musi być zajmowana w całości przez komórki ułożone obok siebie. Każda z nich posiada jeden stan ze skończonego zbioru stanów. Ewolucja każdej komórki przebiega według tych samych ściśle określonych reguł lokalnych (jednorodność), które zależą wyłącznie od poprzedniego stanu komórki oraz od stanów skończonej ilości komórek - sąsiadów. Ewolucja następuje w dyskretnych przedziałach czasowych, jednocześnie dla każdej komórki (równoległość). W automacie komórkowym komórka jest automatem.

[edytuj] Definicja formalna

Jeżeli przez $α$ oznaczymy regularną, uporządkowaną siatkę złożoną z jednakowych komórek $c$ o budowie zależnej od rozmiaru przestrzeni i od kształtu pojedynczej komórki,
natomiast przez $S$ - skończony zbiór stanów, jaki może przyjąć komórka $c$ ,
oraz przez $N$ - skończony zbiór sąsiadów, spełniający warunek:

$\forall c \in N, \forall r \in \alpha : r+c \in \alpha$

a funkcję przejścia definiującą reguły ewolucji automatu w kolejnych krokach oraz dynamikę tych przejść zapiszemy jako:

$f:S^{m} \to S$

to automat komórkowy definiujemy jako czwórkę:

$A \equiv (\alpha, S, N, f)$

Aby opis automatu komórkowego był pełny, niezbędne jest określenie warunków brzegowych i początkowych.

[edytuj] Definicja wg Edwarda Fredkina

Podstawą jego definicji jest dwuwymiarowa, kwadratowa siatka, w której każda komórka jest opisana przez wektor pozycji: $\vec{r}=(i, j)$ , gdzie $i, j$ są indeksami kolumn i wierszy siatki. Stan każdej komórki w iteracji $t$ jest opisywany przez $\phi_{t}(\vec{r}, t)$ i może przyjmować wartości binarne 0 i 1. Na automat komórkowy składają się:

Regularna siatka o $d$ -wymiarowej przestrzeni;
Ustawienie początkowe: $\phi(\vec{r}, t)= \{\phi_{1}(\vec{r}, t), \phi_{2}(\vec{r}, t), \dots, \phi_{m}(\vec{r}, t),\}$ zmiennych boolowskich w każdym miejscu $\vec{r}$ siatki;
Reguła $R = \{R_{1}, R_{2}, \dots, R_{m} \}$ , która ustala stan $\phi(\vec{r}, t)$ w czasie, w następujący sposób: $\phi_{j}(\vec{r}, t+\tau) = R_{j}(\phi(\vec{r}, t), \phi(\vec{r}+\vec{\delta_{1}}, t), \phi(\vec{r}+\vec{\delta_{2}}, t), \dots, \phi(\vec{r}+\vec{\delta_{q}}, t))$ w którym $\vec{r}+\vec{\delta_{q}}$ oznacza komórki należące do skończonego zbioru sąsiadów $\vec{r}$

[edytuj] Historia

Twórcą automatów komórkowych jest jeden z największych myślicieli ery komputerowej, który wprowadził koncepcję samo-reprodukcji - John von Neumann. Docelowo chciał stworzyć model maszyny samosterującej, tzn. takiej, iż powielałaby ona swoją budowę i przekazywała swoje cechy. Na przełomie lat czterdziestych i pięćdziesiątych Neumann opracował swoją teorię opierając się na maszynie Turinga. Opracował on pięć modeli samo-replikujących się automatów, realizacja jednak okazała się zbyt trudna jak na owe czasy. Trafiły one na półkę.

Pracami Neumanna zainteresował się dopiero Edgar Frank Codd, który uczynił automaty możliwymi do wykorzystania. Codd zaprojektował automat komórkowy, który mógł obliczyć wszystkie możliwe funkcje, i który mógł się rozmnażać. Jednak mimo że ten projekt zawierał o wiele prostszą koncepcję od pomysłu von Neumanna, również nie został zrealizowany. Posłużył natomiast do skonstruowania powszechnie stosowanej Gry w życie.

Mimo że w obu przypadkach brakowało realizacji projektów, prace obu teoretyków uważa się za fundamenty powstania automatów komórkowych.

Następnym przełomowym wydarzeniem w historii automatów komórkowych było sklasyfikowanie ich.
Po wcześniejszych czysto teoretycznych projektach w 1983 roku Stephen Wolfram dokonuje klasyfikacji automatów komórkowych.

[edytuj] Konstrukcja

Każdy automat odpowiada wyżej wymienionym definicjom. Jego budowa musi się opierać na konkretnych danych. Nie mogą istnieć w jednym automacie dwie komórki, które nie mają wszystkich elementów takich samych (różnią się choćby ilością sąsiadów). Budowa wszystkich komórek musi być identyczna (muszą mieć tyle samo sąsiadów, takie same zbiory stanów, itp.). Budowa elementów automatu może również wpłynąć znacząco na jego jakość.

[edytuj] Siatka automatu komórkowego

Każdy automat posiada przestrzeń, w której następuje jego ewolucja. Z definicji automatu taką przestrzeń tworzą jednakowe komórki, a nazywamy ją siatką $α$ . Każda komórka przechowuje swój stan – zależny od przestrzeni stanów. Komórki różnią się, są niezależne oraz każdą komórkę można jednoznacznie zidentyfikować poprzez jej położenie na siatce.

Istnieją trzy konstrukcyjne czynniki automatu komórkowego, które w zasadniczy sposób wpływają na strukturę siatki:

wymiar przestrzeni, zależny od wielkości badanego problemu (siatka 1D, 2D, 3D);
warunek regularności, mówiący o całkowitym zapełnieniu siatki przez jednakowe komórki (komórki trójkątne, kwadratowe, heksagonalne);
liczba sąsiadów (zależna od obu powyższych).

[edytuj] Sąsiedztwo komórek

[edytuj] Sąsiedztwo von Neumanna

Jeśli oznaczymy kierunki na zasadzie róży wiatrów: N, S, E, W oraz kierunki pośrednie NW, NE, SE, SW, to sąsiedztwem von Neumanna będzie zbiór czterech komórek: N, S, E, W

Sąsiedztwo von Neumanna

Sąsiedztwo von Neumanna dla siatki trójkątnej i kwadratowej

[edytuj] Sąsiedztwo Moore'a

Posługując się powyższymi oznaczeniami, sąsiedztwem Moore'a będzie zbiór wszystkich ośmiu komórek dookoła komórki centralnej

Sąsiedztwo Moore'a

[edytuj] Sąsiedztwo Moore'a - von Neumanna

Jest to połączenie dwóch poprzednich sąsiedztw w jedno.

Sąsiedztwo Moore'a - von Neumanna

[edytuj] Sąsiedztwo Margolusa

Stosuje się je w automatach do symulacji spadającego piasku, czy też interakcji cząsteczek gazu. Reguły przejścia opierają się na kwadratowych blokach tworzonych przez cztery sąsiadujące komórki. Stany tych sąsiednich komórek zmieniają się jednocześnie, przy czym komórki przyjmują wartości binarne 1 i 0. Tak dzieje się na całej siatce automatu. W następnym kroku reguły są obliczane podobnie, tylko że zmieniają się grupy komórek. Bloki tworzące owe grupy przesuwają się o jeden w prawo i w dół.

Otoczenie Margolusa. Krok pierwszy, drugi i trzeci. Widać zmianę bloków w poszczególnych krokach. Bloki w kroku pierwszym i trzecim obejmują te same komórki.

[edytuj] Warunki brzegowe

[edytuj] Periodyczne (przenikające).

Definiują one zamkniętą siatkę w taki sposób, że np. symulując poruszającą się cząstkę po dojściu do krawędzi pojawi się ona z drugiej strony. Komórka znajdująca się na brzegu siatki ma za sąsiada komórkę leżącą po drugiej stronie siatki. Ten typ przejść bardzo dobrze opisuje nasze otoczenie – środowisko, w którym wszystko również odbywa się na periodycznej przestrzeni, jaką jest kula ziemska.

[edytuj] Zamknięte pochłaniające (o stałej wartości).

Siatka jest zdefiniowana w taki sposób, że brzegi siatki wypełnione są z góry ustaloną wartością, która poprzez funkcję przejścia ustala wpływ na zachowanie automatu. W praktyce, symulując np. cząstkę gazu, po przekroczeniu krawędzi siatki przestaje ona istnieć. Najczęściej stosuje się je w automatach, w których generuje się automatycznie komórki i niezbędna jest ich redukcja, aby nie zagęścić liczby komórek w automacie.

[edytuj] Zamknięte odbijające (o stałej wartości).

Warunki brzegowe na krawędzi siatki tworzą barierę, od której symulowane cząstki się odbijają. Stosowane do symulacji zamkniętych przestrzeni doświadczalnych.

[edytuj] Przestrzeń stanów

Przestrzeń stanów określamy poprzez zdefiniowanie wartości wybranej ze skończonego zbioru $Q$ , który może być podzbiorem zbiorów podstawowych (np. liczb, liter) lub złożonych (struktury, obiekty).
Poprzez przestrzeń stanów opisane zostają wszystkie możliwe stany komórki. Stan komórki zależy od aktualnych stanów komórek z otoczenia, jak i komórka swoim stanem wpływa bezpośrednio na stany swoich sąsiadów. Od dobrego określenia przestrzeni stanów zależy szybkość automatu komórkowego, jak i jego podstawowe cechy charakterystyczne.

[edytuj] Reguły przejść

Reguły przejść określają ewolucję automatu komórkowego w dyskretnym czasie. Stany poszczególnych komórek aktualizuje się w każdej dyskretnej chwili t = 1, 2, 3, ... Tym samym każdy automat komórkowy jest obiektem dynamicznym w czasie. Jak już wcześniej wspomniano, stan każdej komórki można określić na podstawie aktualnych stanów komórek sąsiednich.

Stan komórki $x$ w chwili $t$ oznaczmy jako $x t$ , a stan sąsiedztwa jako $u (x t)$ . Dla takich kryteriów stan komórki $x$ w kolejnym kroku iteracji można opisać wzorem:

x t + 1 = f (u (x t), x t)

gdzie $f$ określa funkcję przejścia, która może być opisana różnego rodzaju zależnościami, np. jako tabela przejść, w postaci algorytmicznej lub jako zbiór reguł. Reguły przejść muszą być zdefiniowane obok przestrzeni stanów oraz zdefiniowanego sąsiedztwa, ponieważ w innym przypadku automat nie mógłby ewoluować.

[edytuj] Warunki początkowe

Ważnym elementem konstrukcyjnym automatów komórkowych są warunki początkowe, czyli stany poszczególnych komórek w zerowej iteracji czyli na samym początku. To od ustawienia początkowego komórek zależy dalsza ewolucja automatu, jego zachowanie, stan końcowy, tym samym powodzenie całej symulacji.

Niektóre automaty komórkowe z założenia muszą mieć w odpowiedni sposób ustalone warunki początkowe. Weźmy pod uwagę Heavy triangles, układ ten zaczyna się od jednej komórki uaktywnionej umieszczonej w środku siatki 1D. Przykładowo w Game of Life, to od warunków początkowych zależy czy w efekcie końcowym otrzymamy wszystkie komórki martwe, czy też komórki, które będą żyły w cyklicznych formach, czy też będą do samego końca powstawały chaotycznie. Od ustawienia warunków początkowych może również zmienić się przynależność automatu komórkowego do różnych klas Stephena Wolframa - opisanych poniżej. Jednym słowem warunki początkowe danego automatu komórkowego zależą od jego charakteru i problemu – zadania przez niego symulowanego.

[edytuj] Ewolucja automatu komórkowego

Po ustaleniu i zdefiniowaniu wszystkich elementów składowych automatu komórkowego można przejść do nakładania reguł na siatkę czyli aktualizowania jej.

Cały proces ewolucji automatu można podzielić na kilka części:

Stan początkowy – jest to, wspomniane już, ustalenie warunków początkowych. Zwykle są to stany neutralne nie powodujące konfliktów w automacie.
Aktualizacja siatki automatu – w każdej iteracji każda z komórek automatu przechodzi przez poniższą sekwencję instrukcji:
1. Sprawdzenie reguł przejść – w tym kroku sprawdzany jest aktualny stan komórki, stany komórek sąsiednich jak i inne parametry automatu;
2. Sprawdzanie sąsiedztwa – bada się, czy któraś z komórek sąsiednich nie wchodzi w stan konfliktu. Jeżeli takie konflikty zaczynają występować, to należy wyeliminować wszystkie istniejące konflikty, według ustalonych wcześniej reguł dla takich przypadków;
3. Sprawdzanie warunków brzegowych – sprawdzane tu są komórki które są na krawędziach siatki. Usuwa się je gdy są zbędne (sąsiedztwo zamknięte pochłaniające) lub tworzy nowe (sąsiedztwo periodyczne);
4. Sprawdzenie ilości iteracji – jeśli jest to automat o skończonym, z góry określonym cyklu życiowym, to w tym kroku sprawdzamy czy może nastąpić koniec ewolucji. Czasami sprawdza się również w tym miejscu czy automat zmienił swój stan i czy przeszedł do stanu stabilnego i nic w nim się już nie zmieni w kolejnych krokach iteracji.
5. Zwiększenie licznika iteracji i przejście do kroku 2.1.

[edytuj] Podział wg Wolframa

Klasa I: Automaty niezmienne – ewoluują do czasu, kiedy wszystkie komórki osiągną identyczny stan niezależnie od stanu początkowego (zbieżne).
Klasa II: Automaty ewoluujące do stanu stabilnego lub okresowych wzorców (okresowe).
Klasa III: Automaty wykazujące nieporządek zarówno lokalnie jak i globalnie, nie wykazujące żadnego wzorca (chaotyczne).
Klasa IV: Automaty wykazujące bardziej złożone, długotrwałe zachowanie ("żywe").

[edytuj] Zastosowanie

Technika automatów komórkowych jest używana do symulacji komputerowych w wielu problemach nauki i techniki. Automaty te dostarczają również wielu zagadnień teorii dynamiki nieliniowej. Twórcami idei automatów komórkowych był Janosz von Neumann (Węgier wsławiony pracami nt. podstaw mechaniki kwantowej) i Stanisław Ulam (lwowski matematyk pracujący w USA).

[edytuj] Popularne automaty komórkowe

Źródło: "http://pl.wikipedia.org../../../a/u/t/Automat_kom%C3%B3rkowy.html"

Kategoria: Programowanie