VIII Ogólnopolska konferencja "GIS w Nauce"

Wykorzystanie automatów komórkowych w badaniach geoprzestrzennych

Piotr Werner

Uniwersytet Warszawski

Wykorzystanie automatów komórkowych w analizach geoprzestrzennych w systemach GIS i teledetekcyjnych ma już ugruntowaną pozycję, jakkolwiek nie zyskały one tak znaczącej popularności jak inne metody. Zainicjowane przez Johna von Neumanna (z inspiracji Stanisława Ulama – polskiego matematyka z przedwojennej szkoły lwowskiej): automaty komórkowe można traktować jako model komputerowego przetwarzania równoległego (Wolfram, 1982). Automaty komórkowe są modelami matematycznymi złożonych systemów zawierających dużą liczbę identycznych (lub podobnych) komponentów oddziałujących lokalnie i globalnie.

W sposób niejawny zaimplementowane są w systemach oprogramowania GIS jako funkcje algebry map.

Automaty komórkowe konstruowane są w siatce pól, z których każda ma skończony zbiór możliwych wartości. Wartość miejsc ewoluuje synchronicznie w dyskretnych krokach czasowych zgodnie z identycznymi regułami. Wartość konkretnego pola determinowana jest matematycznie lub statystycznie zależnie od wartości pól sąsiadujących.

Zazwyczaj płaszczyzna anamorficzna (mapa), pokryta siatką komórek, jest uważana za podstawę badania zmian geoprzestrzennych za pomocą automatów komórkowych. Automaty komórkowe wykorzystywano m.in. w badaniach użytkowania ziemi. Jest to pewien sposób kwantyfikacji przestrzeni. W ten sposób pojawia się model dwuwymiarowego automatu komórkowego z odpowiednimi, policzalnymi stanami. Zwykle definiuje się dwa rodzaje sąsiedztwa: von Neumanna lub Moore’a. Istnieją ponadto inne sąsiedztwa, np: von Neumann-Moore’a i rozbudowany Moore’a.

Reguła przejścia definiuje ewolucję automatu komórkowego: stan każdej komórki w centrum zmienia się w każdym kroku w zależności od jego stanu początkowego, a także początkowego stanu komórek w sąsiedztwie. Reguły przejścia można opisać za pomocą algorytmu, tabelarycznie lub za pomocą zestawu ustalonych reguł. Ważne są również warunki brzegowe.

Stephen Wolfram (2002, s. 231) sklasyfikował wszystkie (256) jednowymiarowe, dwustanowe automaty komórkowe, rozróżniając cztery główne klasy ich zachowania:

  • Klasa 1: Prostych automatów komórkowych, dla których prawie wszystkie warunki początkowe prowadzą do dokładnie takiego samego jednolitego stanu końcowego;
  • Klasa 2: Automaty komórkowe ewoluujące do wielu różnych możliwych stanów końcowych, ale wszystkie składają się tylko z pewnego zestawu prostych struktur, które albo pozostają zawsze takie same albo ujawniony wzór przestrzenny powtarza się cyklicznie;
  • Klasa 3: Automaty komórkowe, które zachowują się w sposób bardziej skomplikowany
    i losowy;
  • Klasa 4: Automaty komórkowe, które wiążą w sobie porządek i losowość: lokalne struktury, które same w sobie są proste, oddziałujące jednak ze sobą w bardzo skomplikowany sposób.

Szereg przykładów zastosowań automatów komórkowych o większej liczbie stanów w analizach geoprzestrzennych dowodzi ich przydatności, a ich potencjał objaśniający można powiązać z ich głównymi typami zachowań.