|
Grundlagen Zellulärer Automaten
Ein zellulärer Automat stellt ein Computermodell
dar, welches meistens aus einer regelmäßigen Anordnung identischer
Zellen besteht. Jede Zelle kann bestimmte Zustände annehmen und
steht mit einer definierten Anzahl von Nachbarzellen in Wechselwirkung.
Die Grundbestandteile eines solchen Systems, die Zellen und Regeln
zur Berechnung des nächsten Zustandes einer Zelle, sind sehr einfach
strukturiert, können in ihrem Zusammenwirken jedoch komplexe Systeme
hervorbringen. Dabei sind vier Merkmale zu unterscheiden:
Das erste ist die Geometrie der Zellenanordnung.
Meist verwendet man ein rechtwinkliges Kästchen-Gitter aus identischen
Quadraten. Auch drei- oder vierdimensionale Anordnungen lassen
sich ohne weiteres konstruieren, allerdings nicht mehr so ohne
weiteres veranschaulichen.
Als zweites muss festgelegt werden, welche
Plätze in einer bestimmten Anordnung als benachbart zu einer beliebigen
Zelle gelten. Zwei häufig auftretende Nachbarschaften sind in
Abb. 01 dargestellt. Bei der von Neumann-
Abb.
01. links von Neumann- und
rechts
Moore-Nachbarschaft
|
Nachbarschaft
werden die vier unmittelbar benachbarten Zellen oben, unten, links
und rechts betrachtet. Rechnen neben diesen vier Zellen auch noch
die vier diagonal benachbarten mit, so spricht man Edward F. Moor
zu Ehren von Moore-Nachbarschaft.
Die dritte Kenngröße eines zellulären Automaten
ist die Zahl der Zustände pro Zelle.
Das vierte und letzte Merkmal, welches vor
allen anderen für die Vielfalt im Universum der zellulären Automaten
sorgt, ist die Regel, nach welcher der künftige Zustand einer
Zelle aus der momentanen Nachbarschafts-Konstellation ermittelt
wird (Transition Rule).
Zelluläre Automaten finden in der Architektur,
im Städtebau und der Geografie zahlreiche Anwendungsmöglichkeiten.
Wir konzentrieren uns in den nachfolgenden Darstellungen auf den
städtischen Kontext. Hier werden wir insbesondere Wachstums- und
Verkehrssimulationen, ökonomisches Handeln und die Dynamik der
Veränderungsvorgänge untersuchen. Nachdem die zugrunde liegenden
Prinzipien einmal aufgezeigt sind, wird es möglich, urbane Strukturen
zu generieren, die bestimmte Vorgaben erfüllen.
Algorithmen
Bei dem im folgenden betrachteten Zellulären
Automaten werden für jede Zelle in Spalte X und Reihe Y des Rasters
die Zustände (z.B. 0 oder 1) der Moore Nachbarschaft (ohne die
Zelle [X, Y] selbst) überprüft und das Ergebnis in einer Zwischenablage
(limboWorld) gespeichert.
for I := -1 to 1 do
begin
for K := -1 to 1 do
begin
summe
:= summe + Zelle[X+K,
Y+I].status;
end;
end;
limboWorld[X, I] := summe
- Zelle[X, Y].status;
Anschließend werden aufgrund der Transition Rule (limboWorld[X, I] >=
1)
die jeweiligen status-Werte der Zellen auf 0
oder 1 gesetzt:
for I := -1 to 1 do
begin
for K := -1 to 1 do
begin
If limboWorld[X,
I] >= 1 Then
begin
Zelle[X, Y].status := 1;
end else begin
Zelle[X, Y].status := 0;
end;
end;
end;
Durch die Zwischenspeicherung in der limboWorld erzeugen wir ein
so genanntes pseudoparalleles
Verfahren. Die sequentielle Abarbeitung der Nachbarschaftsüberprüfung
im ersten Durchgang verändert nicht die status-Werte der Zellen, sondern
speichert lediglich die Summen der Nachbar-status-Werte. Auf der Grundlage
dieser Summenwerte wird in der zweiten Schleife mittels der transition rule entschieden, welchen Zustand die Zellen
im nächsten Zeitschritt annehmen.
Formale
Konventionen
Die formale Notation des oben angegebenen
Algorithmus wird folgendermaßen definiert:
Die einzelnen Zellen werden mit dem fortlaufenden
Index i bezeichnet {i, i
= 1,2,3, …, N}. N
gibt die Gesamtzahl der im System vorhandenen Zellen an. Alternativ
können für eine exakte Positionsangabe die Zellen auch mit ihren
x und y
Koordinaten notiert werden. Die Eigenschaft Di(t)
einer Zelle gibt zu einem Zeitschritt (t) an,
ob die Zelle developed (Entwickelt) Di(t) = 1 ist, oder nicht Di(t) = 0. In anderen Zusammenhängen wird oft auch von
lebend/tot, an/aus oder ähnlichem gesprochen. Die Gesamtsumme
der Entwicklung zu einer bestimmten Zeit t,
N(t), wird durch die Summierung der Entwicklungsindexes
ermittelt:
. Die Nachbarschaft um eine Zelle i ist definiert durch
, wobei die Anzahl der Zellen in jeder Nachbarschaft mit K angegeben wird und die Summe der Entwicklung
in jeder Nachbarschaft zum Zeitpunkt t entsprechend durch
. Die Anzahl der Zustände, die eine Zelle annehmen kann,
wird durch D definiert.
In dem vorliegenden Beispiel D
= 2 für entwickelt und unentwickelt.
Jetzt kann der oben dargestellte Algorithmus
formal ausgedrückt werden. Die Zählregel basiert auf einer Moore-Nachbarschaft
um die jeweils betrachtete
Zelle i. Die Transition Rule wird dann
folgendermaßen dargestellt:
Programmierumgebung
Für die Programmierung der hier vorgestellten
Simulationen haben wir die Sprache Delphi
(ehemals Object Pascal) und die gleichnamige integrierte Entwicklungsumgebung
(IDE) von Borland verwendet. Für Neulinge
auf dem Gebiet der Simulation paralleler Prozesse empfehlen wir
Netlogo.
Dieses verfügt sowohl über vorgefertigte Elemente wie Agenten
(Turtles) und einer Zellenstruktur, auf welche mittels einfacher
Befehle zugegriffen werden kann. Weitere Simulationsumgebungen
sind z.B. Processing,
Repast,
Swarm,
Brahms
und VBA (z.B. für AutoCAD).
Literaturempfehlung
Für die Einführung in die Simulationskonzepte
haben wir auf die Bücher ‚Cities
and Complexity’ von Michael
Batty und ‚Geosimulation’
von Itzhak Benenson und Paul M. Torrens zurückgegriffen,
aus denen teilweise Ideen für die Beispiele übernommen wurden.
Für eine tiefergreifende Einführung Zellulärer
Automaten empfehlen wir die Recherche bei wikipedia.
WEITER >
|
