Zelluldre Automaten

Geschichte der zelluldren Automaten

Die "Erfindung" von zelluldren Automaten steht in Zusammenhang mit der Erschaffung k|nstlichen Lebens. Dahingehende Versuche gibt es schon weit vor dem Beginn des Informationszeitalters: Man denke dabei an den Homunkulus der Alchimisten, Frankenstein als literarischen Ausdruck wissenschaftlichen Ehrgeizes oder konkretere mechanische Versuche wie die Ente des Jacques de Vaucanson (Schuster und ?, S. 160). Von Neumann meinte, Lebewesen wdren nichts weiter als informationsverarbeitende Maschinen mit der Fdhigkeit zur Fortpflanzung (Reproduktion) und Fortentwicklung (Evolution). Er dachte dabei zundchst an einen Apparat, der in einem See aus Bauteilen schwimmt und sich gemd_ eines in ihm selbst enthaltenen Bauplans nvtige Bauteile herausfischt, zusammenbaut und sich so reproduziert. Das war das Prinzip der DNS - vor ihrer Entdeckung. Dieser Apparat war eine Vision, aber mathematischer Formalisierung schlecht zugdnglich. Sein Freund Stanislaw Ulam schlug deshalb ein Gitter von endlichen Automaten vor - einen zelluldren Automaten.
Von Neumann bewies die Existenz eines selbstreproduzierenden Gebildes mit 29 Zustdnden, mehrere 100000 Zellen gro_, 150000 Zellen gro_er Bauplan.
Evolution sollte durch (zufdllige) Fehlinterpretation der DNS geschehen.

Game of Life

Conway war |berzeugt, da_ sich das gleiche Ziel mit wesentlich geringerem Aufwand erreichen lie_. Er nannte seinen Automaten das "Game of Life", und unter diesem zugkrdftigen Namen geriet er in das Licht einer breiteren Vffentlichkeit, insbesondere der Hacker und Freaks, und so wurden bald Gleiter, Gleiterkanonen, logische Gatter und mehr entdeckt - Life war erwiesenerma_en berechnungsuniversell, und es lie_en sich |berschaubare Konfigurationen finden, die zur Selbstreproduktion fdhig waren. Life war ein Automat mit lediglich zwei Zustdnden und simplen Regeln:
Eine Zelle "lebt" im ndchsten Zeitschritt, wenn au_er ihr drei oder mit ihr drei Zellen der Nachbarschaft "leben".

Drei Ebenen der Beobachtung/des Verhaltens: Durch das Zusammenspiel von Gebilden, die aus einigen Zellen bestehen, entsteht (emergentes) globales Verhalten.

Eigenschaften:

diskret in Raum und Zeit
regelmd_iges Gitter von Zellen
Nachbarschaft: Menge von (einer Zelle benachbarten) Zellen, die den Zustand dieser Zelle im ndchsten Zeitschritt bestimmen.
deterministisch: ergangsregel bildet Zustand der Nachbarschaft einer Zelle eindeutig auf Zustand der Zelle ab
homogen: lokale Regeln gelten f|r alle Zellen gleich
synchron: Regeln gelten f|r alle Zellen gleichzeitig

andere Interpretation: Jede Zelle ist ein endlicher Automat, die Konfiguration der Zellen in der Nachbarschaft sind die Eingabe.

weitere Begriffe:

totalistisch: ergangsregeln arbeiten auf Anzahl der Zellen einer Nachbarschaft in einem bestimmten Zustand (d.h. bei bindren Automaten auf der Summe)
legal: Wenn alle Zellen der Nachbarschaft im (Ruhe-) Zustand 0 sind, bleibt die Zelle im Zustand 0
probabilistisch: Die ergangsregel enthdlt Zufallsfaktoren
Garden of Eden: Konfiguration des Automaten, der von keiner anderen Konfiguration aus erreicht werden kann.
reversibel: Die ergansregel ist eineindeutig, es gibt keine Garden of Eden. D.h. die Information der Anfangskonfiguration bleibt vollstdndig erhalten.
Randbedingungen: Dem klassischen Automaten liegt ein unendliches Gitter zugrunde. Andere Mvglichkeiten sind die Verbindung der Kanten eines begrenzten Gitters (zweidimensional zum Zylinder bzw. Torus), die Spiegelung an der Kante (die vorletzte Reihe wird au_en an die du_erste angef|gt), oder spezielle Regeln f|r die Kanten.

Einteilung der zelluldren Automaten in vier Kategorien nach Steven Wolfram durch eine Untersuchung der 32 totalistischen legalen eindimensionalen Automaten

Kategorie 1: Automat erreicht rasch einen stationdren homogenen Zustand.
Kategorie 2: Automat zeigt einfaches statisches Muster oder einfache periodische Muster.
Kategorie 3: Automat zeigt chaotisches Verhalten.
Kategorie 4: Automat zeigt komplexe periodische Muster oder deutliche, aber unvorhersehbare Strukturen.

Die Einteilung ist auch f|r hvhere Dimensionen und andere Arten von Regeln sinnvoll; die Hdufigkeit von Automaten der Kategorie 3 nimmt zu, die Hdufigkeit von Automaten der Kategorie 4 nimmt ab.

(s. Steven Wolfram, )

Informationsausbreitung und Differenzbilder

Differenzbilder erhdlt man, wenn man die Konfigurationen von zwei zelluldren Automaten zum gleichen Zeitpunkt voneinander abzieht. F|r gleiche Regeln und leicht unterschiedliche Initialkonfigurationen kann man so erkennen, auf welchen Raum und in welcher Weise sich dieser Unterschied im Laufe der Zeit auswirkt.

In Kategorie 1 verschwinden die Unterschiede sehr bald: totaler Informationsverlust.
In Kategorie 2 rdumlich begrenzte Ausbreitung.
In Kategorie 3 sind die Differenzbilder dhnlich den Automaten, also chaotisch, der Unterschied wirkt sich schnell auf den gesamten Automaten aus.
In Kategorie 4 Differenzbilder dhnlich komplex und strukturiert wie die Automaten. Die Information wird in spezifischer Weise propagiert. Diese Automaten eignen sich am ehesten f|r Berechnungen.

(s. Martin Hinsch)

Einige dieser zelluldre Automaten sind nachweisbar berechnungsuniversell. Dazu gen|gt es, zu zeigen, da_ sich logische Gatter und Input-Vervielfacher kodieren lassen, oder da_ die Regeln selbst eine Turingmaschine kodieren.

(s. FAQ)

Mean Field Theory

Problem: Gibt es aus den Regeln ableitbare Parameter, die das Verhalten des Automaten insgesamt beschreiben?
Steven Wolfram: Statistical Mechanics of Cellular Automata
Christopher Langton: Lambda-Parameter
Anteil der Konfigurationen der Nachbarschaft einer Zelle, die einen Zustand != 0 der Zelle zur Folge haben. z.B. Life:
140
--- = 0.273
512

Die Komplexitdt, aufgetragen gegen Lambda, ist symmetrisch, deshalb nur Betrachtung 0 <= Lambda <= 0.5
Langtons Hypothese war, da_ unter einem kritischen Wert Lambda_C Automaten der Kategorien 1 und 2 zu finden wdren (relativ "homogenisierende" Regeln), dar|ber der Kategorie 3 (relativ "heterogenisierende" Regeln). Nur in einem schmalen Band dazwischen wdre die Wahrscheinlichkeit recht gro_, Automaten der Kategorie 4 (komplexes Verhalten) zu finden.

Diese Hypothese trifft gut zu f|r eindimensionale bindre Automaten, weniger gut f|r mehr Zustdnde und hvhere Dimensionen. Ein besser zutreffender genereller Indikator ist mir nicht bekannt.
(s. Mitchell, Crutchfield)

Beispiel und Modifikationen des klassischen Konzepts

Klassischer zelluldrer Automat:
Life: s.o.
Density-Problem: Gesucht wird ein Regelset, das dazu f|hrt, da_ der Automat in einer statischen Konfiguration endet, in dem alle Zellen in dem Zustand sind, den die meisten Zellen in der Ausgangskonfiguration hatten. Interessant daran: Eine globale Information (Durchschnitt aller Zellen kleiner/grv_er 0.5) soll durch die lokal wirkenden Regeln berechnet werden.

Probabilistischer Automat:
Forest Fires: Simulation der Ausbreitung von Feuer im Wald
Annahme homogenen Bewuchses, jede Zelle ist von maximal einem Baum besetzbar. Die Regeln:
Ein Feuer entz|ndet sich mit gegebener Wahrscheinlichkeit in einer bewachsenen Zelle (z.B. durch Blitzschlag, Zigaretten)
Das Feuer breitet sich auf benachbarte bewachsene Zellen aus.
Ein verbrannter Baum hinterld_t eine leere Zelle.
Auf einer leeren Zelle siedelt sich mit gegebener Wahrscheinlichkeit ein neuer Baum an.
Es entsteht komplexes Globalverhalten mit sich ausbreitenden Feuerfronten.

Andere Nachbarschaften:
Standard bei zwei Dimensionen: Von-Neumann-Nachbarschaft: direkte Nachbarzellen in N-O-S-W
oder Moore-Nachbarschaft: acht angrenzende Zellen
Margolus-Nachbarschaft:
Sand-Pile-Rule: Besonders bei Vielteilchen-Simulationen ergeben sich Konflikte, wenn mehrere Teilchen dieselbe Zelle |ber ihre Kapazitdt hinaus besetzen wollen. Im Sandhaufen ist die Kapazitdt gleich 1. Konfliktsituation z.B.:

-------
|y| |y|
-------
|x|o|x|
-------

Von welcher der mit y bezeichneten Zellen "fdllt" das Partikel in die mit o bezeichnete Zelle?

Bei der Margolus-Nachbarschaft bilden jeweils vier Zellen einen Block, jede Position im Block besitzt eigene Regeln, das Verhalten der Zellen hdngt nur von den |brigen Zellen im Block ab. Der Block wird in jedem Zeitschritt eine Position nach rechts unten verschoben.

-------      -------
|ol|or|      &  &  &
----------   ----------
|ul|ur|  &   &  |ol|or|
----------   ----------
&  &  &      |ul|ur|
-------      -------

Zelluldre Automaten mit Margolus-Nachbarschaft sind inhomogen (verschiedene Regeln f|r verschiedene Zellen), aber relativ einfach als klassische Automaten mit Moore-Nachbarschaft zu kodieren, indem in jeder Zelle kodiert wird, in welchem Quadranten des aktuellen Blockes sie sich befindet (2 Bit).

Anderer Ansatz: Aufgabe der Synchronitdt, Berechnung des ndchsten Zeitschrittes z.B. von links unten: Teilchen von links haben "Vorfahrt".

Lattice Gas Automata: Unabhdngig von zelluldren Automaten entwickelt, zur Simulation physikalischer und chemischer Vorgdnge, insbesondere Vielteilchensimulationen.

Einfache Agenten, mFSM (movable Finite State Machines):
Solange die Raumbeschreibung und Zeitbehandlung diskret bleiben, lassen sich Multi-Agenten-Systeme wohl immer als zelluldre Automaten kodieren; die Intuition legt aber eine Interpretation als endliche Automaten, die auf einem zelluldren Automaten als Raum agieren, nahe. Von mFSMs spricht man, solange die Automaten wenige Zustdnde annehmen kvnnen und die Beziehung zur Umwelt relativ einfach ist (z.B. Teilchen mit Geschwindigkeit und Richtung, die kollidieren oder Krdften ausgesetzt sind). Von Agenten sollte man dann sprechen, wenn die Automaten viel Zustand enthalten und/oder eine sinnvolle Interpretation im Sinne von Agent-Umwelt-Beziehung, Wahrnehmung und Entscheidung mvglich ist.
Ant-Rule (Langton): Eine Ameise (Zustand nur Richtung N-O-S-W) dreht sich um 90 Grad nach links, wenn die Zelle wei_, um 90 Grad nach rechts, wenn die Zelle schwarz ist, und invertiert die Zelle.
Nach einigen tausend chaotischen Anfangsbewegungen baut die Ameise "Highways", gerade Streifen mit einem bestimmten Muster. Nachfolgende Ameisen kvnnen sich auf diesen Highways sehr viel schneller bewegen. Holen sie die Baumeister ein, wird der Bauvorgang unterbrochen, und bald bauen beide Ameisen in verschiedene Richtungen weiter.

weitere Modifikationen:
andere Gitterstrukturen:
hexagonal: Vorteil: gleicher Abstand zu allen Nachbarn, geschlossene Nachbarschaft, rdumliche Anordnung der Nachbarzellen f|r alle Zellen gleich
dreieckig: Vorteil: gleicher Abstand zu allen Nachbarn
unregelmd_ige Graphen, z.B. f|r soziale Netzwerke, Boolean Networks mit unterschiedlich vielen Eingdngen (Kauffman)

inhomogen: verschiedene Regeln f|r verschiedene Zellen
z.B. Boolean Networks: logische Gatter mit unterschiedlich vielen Eingdngen; geraten sehr schnell in einen stabilen oder periodisch wiederkehrenden Zustand

hvhere Dimensionen

Agentensysteme

Bezeichnungen: autonomous agents, multi-agent-systems, individual based modelling

Ein Agent ist gewisserma_en ein "Individuum", das sich in einer Umwelt bewegt; zu einem Agentensystem gehvrt also au_er den Agenten selbst die Umwelt.
Agenten nehmen ihre Umwelt wahr, haben also einen Wahrnehmungsapparat, eine interne Reprdsentation eines Ausschnittes ihrer Umwelt; sie treffen Entscheidungen aufgrund ihres internen Zustandes und ihrer Reprdsentation der Umwelt, und wirken auf ihre Umwelt ein.

Die Anfdnge der Agententheorie liegen in der KI/KL-Forschung sowie der Robotik.

Die Vorteile gegen|ber dem CA-Ansatz sind:
Der semantische Bezug zur Realitdt; |ber Agenten und ihre Aktionen spricht man mit gewisser Berechtigung in Begriffen der "Normalsprache".
Grv_ere Freiheiten bei der Modellierung, insbesondere nicht zwangsweise Anordnung in/Bewegung auf einem Gitter.
Heterogene Populationen (d.h. Individuen mit unterschiedlichen Eigenschaften) sowie verschiedene Populationen gleichzeitig (verschied. Arten) mvglich.
Entspricht mehr dem objektorientierten Paradigma.

Software zur Modellierung mit CAs und MAS:
Chaosbox: Tool zur einfachen Implementierung von klassischen CAs; Windows
s3s: Bibliothek zur einfachen C-Programmierung von CAs und stochastischen Modellen; X
StarLogo: Massiv paralleles Logo f|r einfache CA-Programmierung und eingeschrdnkte Multi-Agenten- (Turtle-) Systeme; Mac
MIMOSE/MASSIF: Programmierumgebung f|r Multi-Ebenen-Simulation; X bzw. Java
Swarm: parallelisierbare, ereignisgesteuerte Bibliothek zur (Objective-C-) Programmierung grv_erer Multi-Agenten-Systeme; diverse UNIXe/Windows

Zu beachten bei der Programmierung von zelluldren Automaten

Synchronitdt der Regelanwendung hei_t Buffering des Automaten: Lesen der alten Zellzustdnde aus einem Array, Schreiben in ein anderes.
Kodierung der ergangsregeln in einer Tabelle ist meist schneller als if-else-Anweisungen, die Zustdnde der Zellen einer Nachbarschaft ergeben einen Index in diese Tabelle; die Konstruktion aus komplizierten Regeln kann allerdings umstdndlich sein bzw. die Tabelle f|r zelluldre Automaten mit vielen Zustdnden oder gro_en Nachbarschaften sehr gro_ werden.
F|r regelmd_ige Nachbarschaften bietet sich ein Array als Reprdsentation des Automaten an, f|r unregelmd_ige Nachbarschaften (beliebige Graphen) eher ein objektorientierter Ansatz.

Literatur:

Heike Schuster, : Das digitale Universum
Leicht lesbar, gut verdaulich, deutsch

Die CA-FAQ des Santa-Fe-Institutes
Kurze Antworten auf klare Fragen, jeweils mit Literaturangaben, gro_e Bibliographie (etwa 1000 Eintrdge!)

Martin Hinsch: Dokumentation zu zelluldren Automaten www.usf.uni-osnabrueck.de/~mhinsch
einige Details zu Begriffen, eindimensionalen CAs und Wolframs Einteilung

Stephen Wolfram:
alle Details zur Einteilung in die vier Kategorien und zur Kodierung von Regeln

Stephen Wolfram: Statistical Mechanics
Grundlagenartikel zur Mean Field Theory, obwohl der Begriff nie erwdhnt wird

Choppard, :
erblick |ber Modellierungen mit CAs und dhnlichem, mit Schwerpunkt auf physikalischen/chemischen Anwendungen; in Ausz|gen

Franz, Sabine
Zwei Listen mit Kurzcharakterisierungen bzw. Literaturangaben zu Modellierungen mit CAs

Crutchfield, Mitchell: The "Edge of Chaos" revisited
Wie haltbar sind der Lambda- und andere Parameter? Kritische Auseinandersetzung mit der Voraussage globaler Eigenschaften von CAs

Stuart Kauffman:
(Bald) ein Buch |ber Agenten

:
Ein Beispiel f|r ein eher ungewvhnliches Vorhaben, ndmlich das Leben in einem Indiodorf mit einem Multi-Agenten-System zu simulieren

Steven Levy: Artificial Life - The Quest for a New Creation
Populdrwissenschaftliches Buch |ber K|nstliches Leben; von 1992, also nicht mehr ganz up-to-date


Software:
Chaosbox:
s3s: www.grumpy.ca??/~durrett
StarLogo:
MIMOSE/MASSIF: Institut f|r sozialwissenschaftliche Informatik Koblenz-Landau
Swarm: Santa-Fe-Institut www.santafe.edu/projects/swarm

Seitenanfang