Software-Projekt SW09

- N a v i g a t i o n - - - - - - - -

- VI-ANEC

- Über das Institut

- Software-Projekte

- Hardware-Projekte

- Best-Paper-Best-Program-Awards

- Sponsoring

- Dienste

- Kontakt

Evolutionäre Algorithmen und Chaos-Theorie

In ES besitzen Individuen a(i) eine Struktur, die aus dem n-dimensionalen Objektvariablenvektor x(i), dem Fitnesswert f(x(i)) und einem n-dimensionalen Schrittweitenvektor delta(i), der zusammen mit einer stochastischen Verteilungsfunktion wie der Gauss-Funktion, einen Mutationsprozess beschreibt, der als ein Bewegungsmodell innerhalb der Fitnesslandschaft betrachtet werden kann. Die evolutionäre Selbstadaption wirkt dabei direkt auf den Objektvariablenvektor x(i), da eine Bewertung f(x(i)) vorhanden ist, die selektionsrelevant ist. Bezüglich des Schrittweitenvektors delta(i) findet eine indirekte Selbstadaption statt, da für den Schrittweitenvektor keine direkte Bewertung vorhanden ist, die selektionsrelevant ist.

Ein Schrittweitenvektor spezifiziert die freien Parameter einer stochastischen Verteilungsfunktion, wobei im Prinzip auch andere Verteilungsfunktionen anwendbar sind. Beispielsweise kann als Verteilungsfunktion auch eine Cauchy-Funktion verwendet werden (siehe z.B. Bachelier (1998b:88f), Chellapilla (1998)). Allgemein kann die Mutation m(.) als eine Form von Kernel-Operation betrachtet werden, bei der eine Kernel-Funktion mit Hilfe von bestimmten Parametern ein Mutationsobjekt als Argument aufnimmt, und daraus ein mutiertes Objekt erzeugt (siehe Bachelier (1998b:90)):

m(Mutationsobjekt | Kernel-Funktion, Parameter) = mutiertes Objekt.

Denkbar wäre die Verwendung iterierender Funktionssysteme als Kernel-Funktion einer Mutations-Operation, um ein Bewegungsmodell innerhalb einer ES zu erzeugen, wobei IFS deterministisch wie stochastisch definiert sein können. Der grosse Vorteil einer solchen Vorgehensweise besteht darin, dass die Kodierung eines IFS wesentlich kleiner ist als die n Parameter, die zur Spezifizierung eines Schrittweitenvektors notwendig sind. Bei einer IFS-Kodierung wird ein n-dimensionaler Strategievektor just-in-time erzeugt, wenn die Mutation eines Individuums notwendig wird. Ausgehend von einer oder einer kleinen Anzahl von IFS-Parametern, die dem Individuum in seiner Datenstruktur zugeordnet sind, wird ein Schrittweitenwert erzeugt, indem z.B. der zuletzt erzeugte Wert bzw. eine feste Anzahl der zuletzt erzeugten Werte in die Funktionsgleichung des IFS eingesetzt wird. Der neue Wert wird für die Erzeugung des nächsten Schrittweitenwertes verwendet, bis n Schrittweiten vorliegen, die den n Komponenten des Objektvariablenvektors zugeordnet werden. Es sind unterschiedliche Zuordnungsstrategien möglich, wobei die einfachste die zufällige Paarung ist. Die Vorgehensweise besitzt eine Analogie in der sequentiellen, monoton sinkenden Komponenten-Mutation (siehe Kimura (1983), Voigt (1995:14), Bachelier (1998b:91ff)).

Eine deterministische IFS ist aus Gründen der Effizienz vorzuziehen, da bei stochastischen IFS zusätzlich Zufallsexperimente in Verbindung mit einer Verteilungsfunktion notwendig werden, wobei die Verteilungsfunktion selbst extern vorgegeben werden muss. Bei einer indirekten Selbstadaption der Verteilungsfunktion würde nochmals eine Steigerung des Rechenaufwandes notwendig, sodass ausschliesslich deterministische IFS betrachtet werden sollen.

Die Parameter der individuellen IFS unterliegen Rekombinations- und Selbstmutations-Operationen, sodass eine indirekte Selbstadaption im Generationsverlauf erfolgt, analog der indirekten Selbstadaption der Mutationsschrittweitenvektoren. Im Generationsverlauf erzeugen Individuen somit eine fraktale aber deterministische Bewegung innerhalb der Fitnesslandschaft, im Gegensatz zu einer stochastischen Bewegung mit Hilfe einer Gauss- oder Cauchy-Funktion. Durch den Selbstadaptionsprozess wird diese Bewegung an die Struktur der Fitnesslandschaft angepasst.

IFS erzeugen Fraktale, die durch eine Masszahl wie die Fraktale Dimension, oder durch ein Dimensionsspektrum wie die verallgemeinerte Renyi-Dimension (Bronstein et al. (1993:560f); Peinke et al. (1992)) beschrieben werden. Die selbstadaptive Anpassung von IFS an eine Fitnesslandschaft bedeutet somit, dass dadurch eine Schätzung der fraktalen Eigenschaften der Fitnesslandschaft gebildet wird, die genutzt wird, um Punkte mit extremalen Eigenschaften zu suchen. Es kann die Hypothese erstellt werden, dass IFS-Bewegungsmodelle dort erfolgreich sein werden, wo die Fitnesslandschaft eine gebrochene, fraktale Dimension besitzt.

Neben einfachen IFS können auch Multi-Fraktale (Peitgen et al. (1994: 624ff)) eingesetzt werden, was insbesondere bei Fitnesslandschaften erfolgreich sein dürfte, die aus Real-World-Daten erzeugt wird.

Es sei noch darauf hingewiesen, dass die Betrachtung der Mutation als Kernel-Funktion ihre allgemeine Ausformung dort besitzt, wo die Kernel-Funktion als Programm betrachtet wird, die durch einen Evolutions- bzw. Iterationsprozess adaptiert wird, d.h. wenn die Mutations-Kernel-Funktion als GP-/HP-Programm betrachtet wird.

Im Software-Projekt SW05 wurden Mathematikprogramme, die eine eigene universelle Programmiersprache besitzen, um eine Komponente des Genetic- bzw. des Heuristic-Programming erweitert, wobei mit Heuristic hybride Suchverfahren gemeint sind, die neben der populationsbasierten Suche auch Local-Search-Strategien wie Tabu-Search, zu einem Gesamtverfahren integrieren.

Verschiedene Mathematikprogramme besitzen bereits Funktionen, die zur Analyse dynamischer Systeme, deterministischen Chaos und Fraktale geeignet sind. Unter den nicht-kommerziellen Programmen ist hierbei Scilab hervorzuheben, das zum einen entsprechende Funktionen integriert hat (siehe "Tools for dynamical systems" und "Tools for fractal analysis" im Scilab-Manual (2.4) S. 501ff bzw. 511ff). Zum anderen existiert mit Fraclab ein Programm zur fraktalen Analyse, das insbesondere im Bereich des Signal Processings eingesetzt werden kann, und das einen Schwerpunkt im Bereich der Multifraktal-Analyse besitzt, dessen Funktionen in Scilab integrierbar sind. Bezüglich dynamischer Systeme existiert mit Scicos ein Scilab-Package zur Modellierung und Simulation dynamischer Systeme einschliesslich kontinuierlicher und diskreter Subsysteme.

Die Funktionen, die zur Analyse von fraktalen Strukturen eingesetzt werden, können von den GP/HP-Programmen direkt genutzt werden, um Algorithmen zu entwickeln, die auf bestimmte Anwendungen spezialisiert sind z.B. im Bereich Fractal-Signal-Processing oder -Image-Processing (siehe Fraclab) zu erzeugen.

Andere Mathematikprogramme wie Mathematica oder Matlab besitzen externe Wavelet-Toolboxen (siehe Mathematica-Toolbox bzw. Matlab-Toolbox), die zur Analyse von Fraktalen eingesetzt werden können, doch die Verwendung kommerzieller Programme mit einem GP-Teil ist aus den Gründen, die im Software-Projekt SW05 geschildert wurden, nicht ratsam. Demgegenüber wäre die Erweiterung von Scilab um "Tools for wavelets" eine überschaubare Aufgabe, um die entsprechenden Funktionen einer GP/HP-Anwendung zur Verfügung zu stellen.

Die Überführung eines chaotischen Systems in ein System mit einer definierten, nicht-chaotischen Dynamik ist die Aufgabe der Chaos-Control (s.a. Applied Chaos Lab of Georgia Tech). Hierzu sind mehrere Möglichkeiten bekannt, wie das OGY-Verfahren oder das Tracing (siehe Ditto & Pecora (1993), Ditto et al. (1995)).

Die Nutzung von ES zur Regelung von Systemen wird beispielsweise von To Thanh Binh genutzt, der in diesem Zusammenhang eine Mehr-Zielregelung als Aufgabenstellung formuliert, und ein Multi-Objective- und Constraint-ES entwickelt (s.a. Bachelier (1998b)). Die dort betrachteten Aufgabenstellungen gehen jedoch nicht explizit auf die Regelung von chaotischen Systemen ein.

Ein möglicher Ansatz des Chaos-Control mit EA wäre der applikationsspezifische Entwurf von Control-Algorithmen durch ein CGP/CHP-System, mit der Erwartung, dass Regelalgorithmen erzeugt werden, die zum einen robust sind, und zum anderen wesentlich effizienter als die General-Purpose-Methoden des Chaos-Control.

Wird ein GP/HP-Ansatz im Zusammenhang mit einem Mathematikprogramm wie Scilab durchgeführt, so können die Funktionen der "Robust control toolbox" (siehe Scilab-Manual (2.4) S. 255ff) verwendet werden.

System-Identifikation, d.h. Modellbildung von chaotischem System ist eine damit verknüpfte Aufgabe, wenn ein Regelsystem erzeugt wird, das ein Systemmodell beinhaltet, wobei das Verhalten des zu regelnden, dynamischen Systems und des Systemmodells in einer Adaptionsphase angeglichen wird. Diese Sichtweise entspricht derjenigen der Dual-Control-Theorie (Aström & Wittenmark (1989)), einer speziellen Sichtweise des Aktiven Lernens bei der ein Controler die Möglichkeit besitzt, das externe System, das er regeln soll, nach einem Output zu einem gegebenen Input zu fragen. Der Controler kann gleichzeitig ein Modell des externen Systems aufbauen, wodurch er zum aktiven Lerner wird, oder er kann einen modell-freien Ansatz verwenden (RayChaudhuri (1997: 161)), um seine Regelaufgabe direkt zu erfüllen. Diese Zusatzaufgabe kann ebenfalls durch ein CGP/CHP-System oder ein GP/HP-System innerhalb Scilab durchgeführt werden, wobei im letzten Fall Funktionen des Package Scicos zur Modellierung und Simulation dynamischer Systeme einschliesslich kontinuierlicher und diskreter Subsysteme genutzt werden kann.

Ein Teilprojekt ist die Entwicklung von GP/HP-Programmen zur nicht-linearen Zeitreihenanalyse. Zeitreihenanalyse kann als eine Form von überwachtem Lernen betrachtet werden, wobei die Eignung von GP für diese Aufgabe von Chris Gathercole in "An investigation of Supervices Learning in Genetic Programming" gezeigt wurde.

Als Referenzbasis könnten die Arbeiten von Kantz & Schreiber in Nonlinear Time Series Analysis verwendet werden. Umfangreiche Datenbestände nicht-linearer Zeitreihen könnten z.B. über das Max-Planck-Institut für Physik komplexer Systeme in Dresden bezogen werden, an dem Holger Kantz arbeitet. Ideal könnte sich das Teilprojekt entwickeln, wenn Holger Kantz als Koordinator gewonnen werden könnte, der einige Diplomarbeiten zu diesem Themenbereich an deutschen oder osteuropäischen Universitäten betreuen würde, wobei die vielfältigen Beziehungen der Max-Planck-Gesellschaft zu osteuropäischen Forschern genutzt werden sollte.

Zeitlich könnte dies nach den Software-Projekten SW01 und SW02 durchgeführt werden, um mit dem internet-basierten EA-System Maschinen-Code-GP bzw. -HP zu erzeugen.

In Bachelier (1999b) wurden Verfahren zum Vergleich zweier nachfolgender Populationen vorgestellt, mit dem Ziel, bestimmte Parameter zu regeln, wie den Selektionsdruck, der bei einer kontinuierlichen Verbesserung erhöht werden sollte, um eine Konvergenz zu erhalten. Deutet der Vergleich eine Stagnation an, so kann der Selektionsdruck verringert werden, um aus einem lokalen Optimum zu entkommen.

Wird eine Population mit einer konstanten Anzahl von Individuen als Vielteilchensystem betrachtet, so können die Populationen in einem Generationsverlauf als Trajektorie in einem Zustandraum interpretiert werden. Die Populationsdynamik lässt sich durch Analysemethoden aus der statistischen Mechanik als nicht-lineares System beschreiben, wie etwa in Bornhold (1998). Dort wird mit Hilfe einer Energie-Korrelation das optimale Mass an Rauschen geschätzt, das zu einer optimalen Performance des verwendeten EAs führt, wobei dieses Mass als Mutationsrate in den nächsten Reproduktionsprozess eingeht.

Die Betrachtung von Populationen als Vielteilchensysteme ermöglicht auch die Anwendung von fraktalen und multi-fraktalen Analyseverfahren, wie sie in Fraclab enthalten sind.

Neben der Anwendung innerhalb eines EA-Laufes zur Parameterregelung sind solche Analyseinstrumente auch zur a-posteriori-Analyse eines EA-Laufes geeignet, wobei die gesamte Sequenz aus Eltern- und Zwischenpopulationen über den Generationsverlauf als Datenmaterial gespeichert und analysiert wird.

Beispielsweise können bezüglich eines Problemtasks verschiedene Parametereinstellungen oder Strategien zur Parameterregelung getestet werden.

Eine wesentliche Fragestellung aller iterativen Optimierungsverfahren besteht in der Festlegung eines geeigneten Abbruchkriteriums bzw. eines zufälligen oder selektiven Restartkriteriums. Die Dynamik einer Population dürfte hierbei wesentliche Hinweise liefern, um entsprechende Kriterien eventuell auch domänenabhängig zu formulieren.

Skalierungsindex-Methoden gehen von einem extern definierten Zustandsraum des betrachteten dynamischen Systems aus, der durch die Variablen gebildet wird, die gemessen werden können (siehe z.B. Morfill & Scheingraber (1994), Morfill (1995), Morfill et al. (1995). Jede Messung wird somit als Datenpunkt innerhalb des Zustandsraumes repräsentiert, ohne dass in dieser Grundversion eine zeitliche Strukturierung existiert. Jedem Datenpunkt wird ein Skalierungsindex zugeordnet, der quasi als fraktale Dimension der gesamten Datenmenge aus der Sichtweise eines Datenpunktes interpretiert werden kann. Die fraktale Dimension wird durch die wachsende Anzahl der Datenpunkte in der Umgebung eines Punktes bestimmt, wenn konzentrische Kreise (im 2-dimensionalen Fall) oder Hyperkugeln (im n-dimensionalen Fall) mit wachsenden Radien um den betrachteten Datenpunkt erzeugt werden, und wenn die Anzahl der anderen Datenpunkte in den so definierten Raumgebieten ermittelt wird. Die Zugehörigkeit wird durch eine Distanzbestimmung und einen Vergleich mit dem jeweiligen Radius durchgeführt, wobei von einer euklidischen Metrik innerhalb des Zustandsraumes ausgegangen wird, was jedoch eine Vereinfachung darstellt. Die Distanzberechnungen stellen aufgrund ihrer Anzahl den grössten Anteil an dem sehr hohen Aufwand dar, der z.B. bei einem 3-dimensionalen Zustandsraum mit einigen hunderttausend Datenpunkten Terra- bis Peta-FP-Operationen betragen kann, wobei ein solcher Beispielsfall die Analyse eines Farbbildes darstellt, dessen einzelne Pixel jeweils einen Datenpunkt in dem 3-dimensionalen Farbraum bilden. Der Skalierungsindex jedes Datenpunktes wird in einem Skalierungsindex-Histogramm aggregiert, aus dem relevante Informationen gewonnen werden können, die eine Klassifikation der Datensätze z.B. in Rauschen und informationstragende Daten ermöglicht.

Skalierungsindex-Methoden sind geeignet, komplexe Muster zu identifizieren und diese aus stark verrauschten Daten zu extrahieren, d.h. eine Form von Rauschunterdrückung durchzuführen, die allen anderen momentan bekannten Methoden deutlich überlegen ist.

Der unbestreitbaren Nützlichkeit einer solchen Analsysemethode steht der enorme Rechenaufwand gegenüber. Der Vorteil von Skalierungsindex-Methoden liegt darin, dass die Berechnung der Skalierungsindexe für die einzelnen Datenpunkte ein SIMD-Problem ist, sodass dies mit entsprechender Hardware parallelisierbar ist. Trotzdem muss jeder Prozess über die gesamte Datenverteilung verfügen, sodass nur eine grobe Parallelisierung mit grossen lokalen Speichern sinnvoll ist, da die sonst notwendige hohe Kommunikation zwischen den Prozessen den Parallelisierungsvorteil überwiegen würde.

Mit Skalierungsindex-Methoden lassen sich auch Zeitreihen analysieren, wobei die zeitlichn Muster als Trends interpretiert werden. Der Zustandsraum kann dabei um eine Zeitdimension erweitert werden, und die Daten, die in einem festzulegenden Zeitintervall eingehen, werden als Teilmuster interpretiert. Auf diese Weise steigt die Anazahl der zu analysierenden Punkte im Zustandsraum jedoch proportional mit der Zeit, was aufgrund des starken Anwachsens des Aufwandes der Berechnung von Skalierungsindex-Histogrammen in Abhängigkeit von der Anzahl der Datenpunkte im Zustandsraum nicht handhabbar ist. Sinnvoll wäre demgegenüber ein konstantes Zeitintervall zu verwenden (Zeitfenster), sodass zu jedem Analysezeitpunkt eine Menge von Punkten im Zustandsraum neu hinzu kommen, und eine Menge alter Punkte entfernt werden.

Ein Ziel dieses Teilprojektes ist zunächst die Entwicklung Methoden, um den Aufwand der Musteridentifikation um einige Zehnerpotenzen zu senken, sodass Echtzeitanalysen möglich werden, bis hin zu deren Anwendung im Rahmen von Echtzeitregelungen. Hierbei sollen Software- wie Hardwareentwicklungen geprüft werden. Auf der Hardware-Seite sind parallele Implementierungen auf Standard-Graphik-Prozessoren zu erwägen, da Bildverarbeitung prinzipiell ein SIMD-Problem ist, sodass entsprechende Hardware wie insbesondere FUZION 150 von PixelFusion oder C-RAM-Architekturen hierfür besonderes geeignet sind (siehe Hardware-Projekt HW01). Von besonderer Bedeutung sind aber FPGA-Implementierungen, die massiv parallele Distanzberechnungen in unterschiedlich dimensionalen Zustandsräumen mit möglicherweise flexiblen Metriken durchführen.

Im Rahmen von Software-Entwicklungen könnten zwei Typen unterschieden werden:

1) Effizienzsteigerung bei der Einzelberechnung eines Skalierungsindex-Histogramms.

2) Effizienzsteigerung bei Berechnungen innerhalb einer Domäne.

In einer Domäne wird eine Problemstellung zusammengefasst, bzw. es wird Vorwissen über ein Problem und dessen Lösungseigenschaften benutzt, um schneller eine Lösung zu finden. Die Integration von Vorwissen kann als Erzeugung einer geeigneten Bias interpretiert werden. Ein Beispiel ist die Darstellung von physiologischen Messwerten über einen längeren Zeitraum in einem Zustandsraum, in dem sich im Normalfall bestimmte Muster bilden, die bei Krankheitsbildern abweichen, wobei durch die physikalischen Eigenschaften des zugrundeliegenden physikalischen Systems nur bestimmte Teile des Zustandsraumes belegt werden können. Werden Skalierungsindex-Methoden als Diagnoseinstrument eingesetzt, so können Prototypen für den Normalfall und bestimmte Formen von Abweichungen gebildet werden. Eine Diagnose ist ein Klassifizierungsproblem, d.h. eine zu verarbeitende Datenmenge muss einem der Prototypen zugeordnet werden, sodass dies bei der Skalierungsindex-Methode berücksichtigt werden kann, um frühzeitig Informationen zu gewinnen, die aus dem Skalierungsindex-Histogramm gewonnen werden. Denkbar wären GP-Pre-Processing-Modelle, mit denen Datenpunkte im Zustandsraum gefiltert werden, bevor sie einer Skalierungsindex-Methode zugeführt werden, ähnlich der Entwicklung von Bildverarbeitungsfunktionen oder Filter durch GP. Dies bedeutet z.B. die Ermittlung einer Zerlegung des Zustandsraumes in Regionen unterschiedlicher Wichtigkeit für die betreffende Domäne, sodass ein Datenpunkt, der in einer, für die Domäne irrelevanten Region liegt, direkt ausgefiltert wird. Vergleichbar wäre eine unüberwachte Clusterung des Zustandsraumes z.B. durch SC-SOMs (siehe Bachelier (1998c) und Software-Projekt SW03), verbunden mit der Auswahl von Teilmengen der Daten, mit denen die Skalierungsindex-Methode durchgeführt wird.

Versuche könnten auch in Richtung eines Combining-Verfahrens im Rahmen einer Klassifikation mit Prototypen gemacht werden (Skalak (1996), siehe auch Software-Projekt SW04). Liegt die gesamte Datenmenge vor, so werden unabhängige Samplings von Teilmengen, mit denen unabhängig unter Ausnutzung von Paralellisierungsmöglichkeiten Skalierungsindex-Histogramme gebildet werden. Die einzelnen Histogramme werden in einem Combining-Verfahren dann integriert, bzw. aus den einzelnen Histogrammen werden die einzelnen Informationen gewonnen, die dann integriert werden.

Aktives Lernen kann als ein Spezialfall eines sequentiellen Sampling interpretiert werden, wobei solche Datensätze gesucht werden, welche z.B. die Unsicherheit des aufzubauenden Modells minimiert, bis ein Abbruchkriterium erfüllt ist (siehe Software-Projekt SW07). Denkbar wäre eine Anpassung der Vorgehensweise des Aktiven Lernens, wobei sequentiell solche Datensätze bearbeitet werden, welche die Unsicherheit und die Bias des Skalierungsindex-Histogramms bzw. der daraus gewonnenen Informationen minimieren.

Andere Ansätze verwenden adaptive Auflösungen des Zustandsraumes bzw. Renormierungsstrategien, bei denen der Zustandsraum in disjunkte Hyper-Kuben zerlegt wird, wobei alle Datenpunkte innerhalb einer solchen Region als ein Datenpunkt verarbeitet werden.

Da die Dimension des Zustandsraumes bei den Distanzberechnungen einen wesentlichen Einfluss auf den Aufwand besitzt, könnte im Rahmen einer Domäne untersucht werden, ob ein niedrig dimensionaler Zustandsraum eventuell ähnliche Leistungen erbringt, was durch Faktorenanalysen oder durch SOMs möglich ist. Eine domänenspezifische SOM projiziert einen Datenpunkt in einen niederdimensionalen Raum, wobei diese neuen Koordinaten in die Skalierungsindex-Methode eingehen.

Neben der Dimension spielt die verwendete Metrik des Zustandsraumes eine wesentliche Rolle für den Gesamtaufwand der Skalierungsindex-Methode, sodass eine Suche nach einer problemspezifischen Metrik im Zustandsraum ein weiterer Ansatzpunkt für eine Effizienzverbesserung ist.

Das zweite Ziel dieses Teilprojektes ist die Anwendung von Skalierungsindex-Methoden, eventuell der optimierten und hardware-unterstützten Methoden auf Probleme der EA, wie die Analyse von Populationseigenschaften im Generationsverlauf (siehe Bachelier (1999b)), was auch als eine Form von Zeitreihenanalyse interpretiert werden kann. Denkbar wäre die Entwicklung von Regelungsverfahren auf der Basis von Skalierungsindex-Analysen, mit denen gewünschte Individuen- bzw. Populationseigenschaften wie beste Einzelfitness mit möglichst wenigen Generationen oder wenigen Fitnessevaluationen erreicht werden. Denkbar wäre auch die Entwicklung von optimalen, progressiven Evaluationsumgebungen in einer Domäne, die dann nicht mehr extern oder durch zufälliges Sampeln erzeugt werden müssten.

In Langton (1991) wurde argumentiert, dass Systeme, die sich am Rande des Chaos befinden, komplexe Informationsverarbeitungsprozesse durchführen können. Charakterisiert wird das Systemverhalten durch einen Parameter lamda, der im Intervall [0, 1] liegt. Das Systemverhalten "am Rande des Chaos" wird durch einen Parameterwert lamda nahe 0,5 beschrieben, d.h. dem Systemverhalten ist kein einzelner Wert, sondern ein Intervall I(EoC) zugeordnet, dessen Grenzen noch undefiniert sind, bzw. dessen Grenzen unscharf sind. Links des Intervalls liegen einfache, deterministische Systeme, die nur einfache Computing-Fähigkeiten besitzen. Rechts des Intervalls liegen Systeme, die mit grösser werdendem lamda zunehmend von zufälligen Einflüssen bestimmt werden, bis bei lamda = 1 ein vollständig zufälliges System entsteht, in dem keinerlei Informationsverarbeitung oder Informationsleitung durchführbar ist.

Konkrete Anwendungen dieses Prinzips, sowie eine Weiterentwicklung der Theorie von Systemen am Rande des Chaos und ihren Computing-Fähigkeiten, sind seitdem jedoch nicht bzw. kaum durchgeführt worden. In Kauffman (1991:95) wurde gezeigt, wie Boolsche Netze durch einen Evolutionsprozess, der ausschliesslich Mutation als Reproduktionsoperation verwendet, an den Rand des Chaos gebracht werden können. Die Verwendung eines EAs, um Boolsches Netze an den Rand des Chaos zu bringen zeigt, dass diese Klasse von Verfahren geeignet erscheint, um in dieser Domäne einen Erkenntnisgewinn zu erlangen.

Zunächst muss bei diesem Teilprojekt gefragt werden, ob die zu untersuchenden Fragen durch eine Software-Simulation (chaotische Software) angegangen werden sollen, oder ob analoge physikalische Systeme (chaotische Hardware) hierzu verwendet werden sollen, was die Zugehörigkeit zu den Software- bzw. Hardware-Projekten definiert.

Wird die Software-Simulation gewählt, so ist ein Bezug zum Software-Projekt SW08 notwendig, in dem Evolutionäre Zelluläre Automaten (ECA) untersucht werden, d.h. dieses Teilprojekt kann als Schnittmenge zwischen den Software-Projekten SW08 und SW09 betrachtet werden, da CA am Rande des Chaos durch evolutionäre Verfahren untersucht werden sollen.

In einem ECA-System wird nach CA-Individuen gesucht, deren Systemverhalten durch ein lamda in dem unscharf und ungenau definierten Intervall I(EoC) liegt. Dies ist eine inverse CA-Aufgabe (siehe Worsch (1997:1)), d.h. gegeben ist ein globales Systemverhalten, und gesucht werden CA mit Updateregeln, die ein solches Verhalten generieren. Im Rahmen des Software-Projektes SW08 werden Updateregeln als Updateprogramme in einer Zellulären Programmiersprache (CPL) interpretiert, die durch einen GP/HP-Mechanismus manipuliert werden.

Ein Ansatz ist die Erzeugung einer grossen Menge von diversen CA-Individuen, die diese Eigenschaft besitzt, und die als EoC-Individuen bezeichnet werden sollen. In einem Postprozess sollen sie klassifiziert und analysiert werden, d.h. es soll untersucht werden, welche Konstrukte der CPL zu der EoC-Eigenschaft führen. Eine Möglichkeit der Clusterung besteht unter Verwendung der Computing-Fähigkeiten der EoC-Individuen. Hierbei können die Vorgehensweisen genutzt werden, die von Moshe Sipper mit seinen evolutionären, non-uniformen CA verwendet werden, um CA zu finden, die bestimmte globale, emergente Informationsverarbeitungen leisten können. Andererseits können die Verfahren genutzt werden, die Sinha & Ditto (1999) anwenden, um mit chaotischen Systemen bestimmte Informationsverarbeitungsprozesse durchzuführen. Die Arbeiten von Sinha & Ditto (1999) sollten geprüft werden, ob sich diese Systeme innerhhalb des lamda-Intervalls I(EoC) befinden, was kompatibel mit den Darstellungen von Langton (1991) wäre, da die Computing-Fähigkeiten von stärker chaotischen Systemen wieder abnimmt.

Indem verschiedene Problemklassen mit unterschiedlicher algorithmischer Komplexität an Systemen mit unterschiedlichem lamda getestet werden, können die unscharfen Intervallgrenzen durch jeweils eine Zugehörigkeitsfunktion spezifiziert werden. Im Intervallinneren existiert ein Zugehörigkeitswert von Eins, was bedeutet, das diese Systeme universelle, d.h. Turing-Computing-Fähigkeiten besitzen. Ausserhalb des Kernintervalls, wo Zugehörogkeitswerte kleiner Eins aber grösser Null herrschen, liegen Systeme mit zunehmend eingeschränkten Computing-Fähigkeiten. Diese Systeme können bestimmte Problemtypen prinzipiell nicht lösen, oder sie benötigen dafür grössere Ressourcen, wie z.B. O(n^2) für ein Problem, das eine universelle Maschine in O(n) lösen kann.

Der Projektbereich EA und Chaos-Theorie gliedert sich in eine Reihe von Teilbereichen, die in Kooperation mit verschiedenen Institutionen durchgeführt werden soll.

Angestrebt werden sollte eine Kooperation mit dem Center for Complex Systems and Visualization (CeVis) in dem Heinz-Otto Peitgen und Dietmar Saupe arbeiten (siehe Referenzen). Die Aktivitäten umfassen Forschungen in den Gebieten Chaos-Theorie, Fraktale, Zelluläre Automaten und nicht-lineare Zeitreihenanalyse. Der Projektbereich EA und Chaos-Theorie umfasst Einzelprojekte, die alle diese Bereiche berühren, wobei die Nutzung von EA zur Erkenntnisgewinnung und zur Anwendungsentwicklung in jeweils verschiedenen Ansätzen geprüft werden sollen.

Eine weitere Kooperationsschiene, die direkt oder indirekt über CeVis aufgebaut werden könnte, besteht zu der französischen INRIA-Forschungsgruppe "Fraktale", die sich bereits mit der Nutzung von EA im Bereich der Fraktalen, und insbesondere der Multi-Fraktalen beschäftigt, und die das Software-Paket Fraclab zur fraktalen Analyse herausgegeben hat.

Sollen Projekte mit osteuropäischen Fakultäten durchgeführt werden, so finden sich Hinweise auf Personen, die in diesem Bereich tätig sind z.B. bei den "Experimental Chaos Conferences" z.B. Fifth Experimental Chaos Conference oder in der Zeitschrift Chaos -- An Interdisciplinary Journal of Nonlinear Science.

Alander, Jarmo T. (ed.): Proceedings of the First Nordic Workshop on Genetic Algorithms and their Applications (1NWGA), Helsinki, Finland, (ftp.uwasa.fi/cs/1NWGA), 1995.

Aström, K. J.; Wittenmark, B.: Adaptive Control. Addison-Wesley, 1989.

Babloyantz, A.; Lourenco, C.: Computing with chaos: A paradigma for cortical activity. Proc. Natl. Acad. Sci. USA, Vol. 91, pp. 9027 - 9031, September 1994, Biophysics.

Bornholdt, Stefan: Annealing Schedule from Population Dynamics. 1998.

Bronstein, I. N.; Semendjajew, K. A.; Musiol, G.; Mühlig, H.: Taschenbuch der Mathematik. Frankfurt a.M., 1993.

Chellapilla, K. : Combining Mutation Operators in Evolutionary Programming. IEEE Trans. on Evolutionary Computation , vol. 2, no. 3, pp. 91-97, Sept. 1998.

Ditto, William L.; Pecora, Louis M.: Das Chaos meistern. In: Spektrum der Wissenschaft, 11/1993, S. 46 - 53.

Ditto, William L.; Spano, Mark L.; Lindner, John F.: Techniques for the control of chaos. In: Physica D, 1995, S. 198 - 211.

Kantz, Holger; Schreiber, T: Nonlinear Time Series Analysis. Cambridge University Press, ISBN 0521 551447.

Kauffman, Stuard A.: Leben am Rande des Chaos. In: Spektrum der Wissenschaft, 10/1991, S. 90 - 99.

Kimura, M.: The Neutral Theory of Molecular Evolution. Cambridge University Press, 1983.

Langton, Christopher G.: Life at the Edge of Chaos. In: Langton, C.G.; Taylor, C; Farmer, J.D.; Rasmussen, S.: Artificial Life II, Addison-Wesley, 1991, S. 41 - 91.

Lindner, John F.; Ditto, William L.: Removal, suppression, and control of chaos by nonlinear design. Appl Mech Rev, vol 48, no 12, part 1, December 1995.

Morfill, G.; Scheingraber, H.: Charakterisierung komplexer Systeme - mit ausgewählten Anwendungen. In: Wiendahl, H.-P.; Ahrens, V.: Potentiale der Chaosforschung in den Produktionswissenschaften. 1994.

Morfill, G.: Die Identifikation komplexer Muster: Chancen in der Informationsgesellschaft. In: Deutsche Physikalische Gesellschaft (Hrsg.): Forschungsmanagement in der Physik (XIX), 1995, S. 32 - 58.

Morfill, G.; Scheingraber, H.; Wiedenmann, G.: Die Analyse komplexer Systeme mit Hochleistungsrechnern: Methoden und Beispiele. In: Schubert, V. (Hrsg.): Informatik Heute, Bd. 12, EOS Verlag, St. Ottilien, 1995, S. 75 - 103.

Peitgen, Heinz-Otto; Jürgens, Hartmut; Saupe, Dietmar: Fraktale: Bausteine des Chaos. Springer, Berlin, 1992.

Peitgen, Heinz-Otto; Jürgens, Hartmut; Saupe, Dietmar: Chaos: Bausteine der Ordnung. Springer, Berlin, 1994.

RayChaudhuri, Tirthankar: Seeking the Valuable Domain - Query Learning in a Cost-Optimal Perspective. PhD thesis, Macquarie University, Sydney, 1997.

Sinha, Sudeshna; Ditto, William L.: Computing with distributed chaos. In: PHYSICAL REVIEW E JULY 1999 VOLUME 60, NUMBER 1.

Skalak, David B.: Prototype Selection for Composite Nearest Neighbor Classifiers. Dissertation, Department of Computer Science, University of Massachusetts, 1996.

Voigt, Hans-Michael: Soft Genetic Operators. In: Alander (1NWGA), 1995, S. 1 - 21.

Worsch, Thomas: Programming Environments for Cellular Automata. Lehrstuhl Informatik für Ingenieure und Naturwissenschaftler, Universität Karlsruhe, Mai 1997.