GenI Process

Der GenI Process ([dʒiːnɑɪ] für Generic Intelligence), deutsch GenI-Prozess, beschreibt einen zeitdiskreten stochastischen Prozess $X:[0;1]\times \mathbb {N} _{0}\mapsto 2^{E}$ im Zustandsraum der endlichen Teilmengen einer abzählbaren Menge E, zusammen mit einer Abbildung $\rho :2^{E}\rightarrow \mathbb {C} ^{n}$ der Potenzmenge auf E in einen n-dimensionalen komplexen Vektorraum. Er lässt sich prinzipiell als Markow-Kette 1. Ordnung klassifizieren, mit allerdings veränderlichen Übergangswahrscheinlichkeiten $P(X_{n+1}\vline X_{n})$ (Es sind Parallelen zum Galton-Watson-Prozess erkennbar).

Hintergrund

Der GenI-Zufallsprozess führt sprunghafte Veränderungen im komplexen Vektorraum zurück auf das zufällige Verhalten unabhängiger Individuen innerhalb eines schwarmähnlichen Konstruktes. Der Schwarm besitzt einen Überlagerungszustand $\sum _{j=1}^{n}\beta _{j}e_{j}\in \mathbb {C} ^{n}$, der über eine Zielgröße (Anregung) die individuellen Aktivitäten steuert. Die Amplituden $\beta _{j}e_{j}$ werden auch als Ideen bezeichnet (vgl. bzgl. "Generalized Quantum Modeling"). Der Schwarm nimmt so nach endlich vielen Schritten einen der Eigenzustände $\gamma e_{j}$ an, mit der wohldefinierten Wahrscheinlichkeit ${\frac {\vert {\beta _{j}}\vert ^{2}}{\sum _{k}{\vert \beta _{k}\vert }^{2}}}$. Dabei folgen die Individuen definierten Regeln und dürfen Fehler machen, angelehnt an die Vorgänge in simulierten Fischschwärmen. Der GenI-Algorithmus startet einen chaotischen Entscheidungsprozess als Wettbewerb von Ideen, 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.

Definition

Begriffe

Es sei E eine abzählbare Menge und ${\tilde {E}}:=\{S\subset E:\vert S\vert <\infty \}\subset 2^{E}$die Menge der endlichen Teilmengen von E. Weiter sei $B=(e_{1},\ldots ,e_{n})$ die kanonische Basis in $\mathbb {C} ^{n}$ und ${\tilde {B}}:=\{i^{k}e_{j}:k=0\ldots 3,j=1\ldots n\}$.

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.

Eine gegebene Abbildung $\rho :E\mapsto {\tilde {B}}$ bildet jedes Element aus E auf einen mit einer komplexen Einheit $\{1;i;-1;-i\}$ multiplizierten Basisvektor 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 komplexen 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\neq 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 (als Instanz von $X(\omega ,l)$) 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)}:=\epsilon _{j}(S^{(l)})$ die Anregungen.

1. Schritt: Setze $l\leftarrow 0$ und beginne mit einem gegebenen Schwarm $S^{(0)}$.
2. Schritt: Falls $\forall j:\epsilon _{j}^{(l)}=0$, dann beende den Prozess.
3. Schritt: Jedes Element $s\in S_{D}^{(l)}$ erzeugt einen zusätzlichen Nullring im Schwarm.
4. Schritt: Jedes Nullpaar $r,t\in N_{S}^{(l)}$ mit $\rho (r)=i^{k}e_{j}$, $\rho (t)=-i^{k}e_{j}$ wird mit einer Wahrscheinlichkeit $p=\epsilon _{j}^{(l)2}$ ausgewählt (und wird im nächsten Schritt "verbrannt").
5. Schritt: Für jedes ausgewählte Nullpaar $r,t\in N_{S}^{(l)}$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.
6. Schritt: Der resultierende Schwarm sei mit $S^{(l+1)}$ bezeichnet.
7. Schritt: Setze $l\leftarrow l+1$ und gehe weiter mit Schritt 2.

Erläuterung

Sobald die Anregung in jedem Index verschwindet, kommt der Prozess, abgesehen von der harten Abbruchbedingung in Schritt 2, auf natürliche Weise in Schritt 4 zur Ruhe, da kein Nullpaar mehr „verbrannt“ wird und der Zustand des Schwarms sich daher nicht mehr ändert. Die Rolle der Anregung erinnert hier an die Dynamik eines Sandkorns bei der Entstehung der Chladnischen Klangfiguren. Andererseits führt die Anregung als Zielgröße in Schritt 5 zu einer systematischen Verzerrung der Wahrscheinlichkeit für das Verbleiben eines Individuums. Dies führt hier zu einer Tendenz, die Anregung zu vermindern. Folgende Interpretation ist naheliegend in Anlehnung an biologisches Schwarmverhalten: Jedes Individuum folgt tendenziell der Regel „Vermindere die Anregung“. Dabei bleibt es frei in seiner Entscheidung, nichts zu tun (Schritt 4), der Regel zu folgen, oder sie zu missachten (Schritt 5).

Simulation

Ideenwettbewerb innerhalb eines Schwarms: Diagramm a zeigt die Entwicklung der absoluten Amplituden während eines GenI-Prozesses, der in einer Umgebung mit vier Optionen abläuft. Aufgrund seines intrinsisch chaotischen Verhaltens ist es unmöglich, die Entwicklung des GenI-Prozesses an irgendeinem Punkt vorherzusagen. Interessanterweise gewinnt hier die Option mit der niedrigsten Startchance. Diagramm b zeigt die entsprechende Entwicklung der Entropie, die am Ende dramatisch zunimmt für die Gewinneridee. Abbildung c zeigt die Pfade jeder Idee in der komplexen Ebene.

Die Referenzimplementierung unter JAVA zeigt eine extrem gute Konvergenz des Prozesses. Die Tabelle zeigt beispielhaft das Ergebnis aus 1000 Simulationsläufen (Abbruch jeweils nach mehr als 500 Iterationen oder bei Schwarmgrößen > 10 Mio.):

	$\vert \gamma e_{1}\vert$	$\vert \gamma e_{2}\vert$	$\vert \gamma e_{3}\vert$	$\vert \gamma e_{4}\vert$	$\vert \gamma e_{5}\vert$	$\vert \gamma e_{6}\vert$	$\vert \gamma e_{7}\vert$	$\vert \gamma e_{8}\vert$	$\vert \gamma e_{9}\vert$	$\vert \gamma e_{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 ; Chi kritischer Wert bei 95 % Vertrauen: 16,9
mittlere Schwarmgröße: 300.418					sigma: 281.543		maximal: 1.008.512		minimal: 9.695

Die Ergebnisse stützen folgende Konvergenzaussage (Hypothese):

Sei $S^{(0)}=S$ ein gegebener Schwarm mit $\rho (S)=\sum \beta _{j}a_{j}$, $b_{j}=\vert \beta _{j}\vert$, $\vert S\vert ={\sqrt {\sum b_{j}^{2}}}$.

Sei $S:\mathbb {N} _{0}\times [0;1]\mapsto {\tilde {E}}$ ein GenI-Prozess mit $\rho (S^{(m)}(\omega ))=\sum \beta _{j}^{(m)}(\omega )a_{j}$.

Dann ist $P\left({\tilde {S}}^{(m)}{\underset {m\rightarrow \infty }{\longrightarrow }}\gamma a_{j}\right)=P\left(\sum _{k\neq j}b_{k}^{(m)2}{\underset {m\rightarrow \infty }{\longrightarrow }}0\right)={\frac {b_{j}^{2}}{\vert {S}\vert ^{2}}}$.