GenI Process

Der GenI-Prozess beschreibt einen zeitdiskreten stochastischen Prozess $X:[0;1]\times \mathbb {N} _{0}\mapsto 2^{E}$ in die endlichen Teilmengen einer abzählbaren Menge E, zusammen mit einer Abbildung $\rho :2^{E}\rightarrow \mathbb {C} ^{n}$ der Produktmenge in einen n-dimensionalen komplexen Vektorraum. Er lässt sich als Markow-Kette einordnen, während seine besonderen Eigenschaften an den Galton-Watson-Prozess erinnern.

Hintergrund

Der Zufallsprozess führt sprunghafte Veränderungen im komplexen Vektorraum zurück auf das zufällige Verhalten uabhängiger Individuen innerhalb eines schwarmähnlichen Konstruktes. Der Schwarm besitzt einen Zustand $\sum _{j=1}^{n}\beta _{j}e_{j}\in \mathbb {C} ^{n}$, der über eine Metrik die individuellen Aktivitäten steuert. Er bewirkt, dass der Schwarm nach endlich vielen Schritten fast immer einen Zustand $\gamma e_{j}$annimmt mit der wohldefinierten Wahrscheinlichkeit ${\frac {\vert {\beta _{j}}\vert ^{2}}{\sum _{k}{\vert \beta _{k}\vert }^{2}}}$. Die Individuen folgen dabei definierten Regeln und dürfen Fehler machen, angelehnt an die Vorgänge in simulierten Fischschwärmen. Der GenI-Algorithmus simuliert einen chaotischen Entscheidungsprozess als Wettbewerb von Ideen ( = Amplituden $\beta _{j}e_{j}$), wie er beispielsweise in einem Team abläuft, das unter einer begrenzten Anzahl von Lösungen für eine vorgegebene Aufgabenstellung zu wählen hat. Ein Selektionsmechanismus führt im Laufe des Prozesses dazu, dass Ideen nacheinander aussterben, bis schließlich genau eine überlebt, die die Lösung der Aufgabe repräsentiert. Die besonderen Eigenschaften des GenI-Prozesses machen ihn interessant auch zur Deutung physikalischer Vorgänge.

Der GenI-Prozess: Der Schwarm nimmt ständig Nullringe aus seiner Umgebung auf und "verbrennt" diese zufällig. Der GenI-Prozess bestimmt einen Gradienten zur Reduzierung der Anregung. Der Zustand des Schwarms konvergiert schließlich zu einer der gegebenen Optionen.

Definition

Begriffe

Es sei E eine abzählbare Menge und ${\tilde {E}}:=\{S\subset E:\vert S\vert <\infty \}\subset 2^{E}$, $B=(e_{1},\ldots ,e_{n})$ die kanonische Basis in $\mathbb {C} ^{n}$, ${\tilde {B}}:=\{i^{k}e_{j}:k=0\ldots 3,j=1\ldots n\}$. Eine Abbildung $\rho :E\mapsto {\tilde {B}}$ bildet jedes Element aus E auf einen der Basisvektoren, multipliziert mit einer komplexen Einheit, ab, so dass $\forall e\in {\tilde {B}}:\vert \rho ^{-1}(\{e\})\vert =\infty$. Für einen Schwarm $S\in {\tilde {E}}$ bezeichnet $\rho (S):=\sum _{s\in S}\rho (s)=\sum _{j}\beta _{j}e_{j}$ seinen Zustand mit Amplituden $\beta _{j}$.

Ein Paar $s,t\in E$ mit $\rho (s)+\rho (t)=0$ ist ein Nullpaar. Ein Tupel $(s_{0},s_{1},s_{2},s_{3})$ heißt von $s_{0}$ erzeugter Nullring, wenn $\exists j:\rho (s_{k})=i^{k}e_{j}$.

Eine Menge $N\in {\tilde {E}}$ heißt Nullmenge, wenn $\rho (N)=0$. Eine maximale Nullmenge $N\subset S$ heißt Entropie von S und $S\setminus N$ ein entropiefreier Restschwarm.

Der Term $\epsilon _{j}(S):=2{\frac {\vert \beta _{j}\vert {\sqrt {\sum _{k<>j}\vert \beta _{k}\vert ^{2}}}}{\sum _{k}\vert \beta _{k}\vert ^{2}}}\in [0;1]$ bezeichnet die Anregung des Schwarms im Index j.

Algorithmus

Sei $S^{(l)}=S_{D}^{(l)}+N_{S}^{(l)}$ eine Folge von Schwärmen mit der jeweiligen Zerlegung in einen maximalen Nullschwarm $N_{S}^{(l)}$ und dem entropiefreien Restschwarm $S_{D}^{(l)}$, $\rho (S^{(l)})=\sum _{k=1}^{l}\beta _{k}^{(l)}e_{k}$ die entsprechenden Zustände und $\epsilon _{j}^{(l)}$ die Anregungen.

Schritt 0: Setze $l\leftarrow 0$

Schritt 1: Jedes Element $s\in S_{D}^{(l)}$ erzeugt einen zusätzlichen Nullring im Schwarm.

Schritt 2: Jedes Nullpaar $r,t\in N_{S}^{(l)}$ mit $\rho (r)=i^{k}e_{j}$, $\rho (t)=-i^{k}e_{j}$ wir mit einer Wahrscheinlichkeit $p=\epsilon _{j}^{(l)2}$ aufgeteilt ("verbrennt"). Danach verlässt t den Schwarm mit einer Wahrscheinlichkeit ${\frac {\epsilon _{j}(S\setminus \{r\})}{\epsilon _{j}(S\setminus \{r\})+\epsilon _{j}(S\setminus \{t\})}}$. Andernfalls bleibt t und r verlässt den Schwarm.

Schritt 3: Der resultierende Schwarm sei $S^{(l+1)}$ bezeichnet.

Schritt 4: Falls $\forall j:e_{j}^{(l+1)}=0$, dann beende den Prozess. Andernfalls setze $l\leftarrow l+1$ und gehe weiter mit Schritt 1.

Simulation

Die Referenzimplementierung unter JAVA zeigt eine extrem gute Konvergenz des Prozesses. Die Tabelle zeigt beispielhaft das Ergebnis aus 1000 Simulationsläufen:

	$\vert \beta _{1}\vert$	$\vert \beta _{2}\vert$	$\vert \beta _{3}\vert$	$\vert \beta _{4}\vert$	$\vert \beta _{5}\vert$	$\vert \beta _{6}\vert$	$\vert \beta _{7}\vert$	$\vert \beta _{8}\vert$	$\vert \beta _{9}\vert$	$\vert \beta _{10}\vert$
Soll	132	81	97	78	11	206	3	336	36	3
Ist	135	74	99	76	15	189	1	357	36	1
sigma	10,7	8,6	9,4	8,5	3,3	12,8	1,8	14,9	5,9	1,8
Messungen geplant			1000	davon divergent		17	konvergent			983
Statistiken Chi Quadrat Wert: 7,85 mittlere Schwarmgröße: 300.418 mittlerer Schwarmbetrag: 500			sigma: 281.543 sigma: 471		Chi kritischer Wert bei 95%: 16,9 maximal: 1.008.512 maximal: 4.084				minimal: 9.695 minimal: 23

Literatur

• Schweizer, Frank; Zimmermann, Jörg, Communication and Self-Organization in Complex Systems: A Basic Approach, Advances in Spatial Sciences 2001, ISBN 978 3 6620 4546 6 p. 275-296
• Siegfried Genreith: Bewusstsein, Zeit und Symmetrien. Books on Demand GmbH, Norderstedt 2010, ISBN 978 3 7460 6726 1