Software-Projekt SW10

- - - - - - - -
Ein-Problem-EA	Im Rahmen von EA-Systemen wird der Regelfall betrachtet, dass zu einem Zeitpunkt ein Problem vorliegt, das durch eine evolutionäre Vorgehensweise gelöst werden soll, wobei zu einem Zeitpunkt des Lösungsversuches mehrere Lösungsvorschläge als Population vorliegen. Die nachfolgenden Darstellungen sollen am Beispiel des Genetic-Programmings (GP) beschrieben werden, als einem EA-Spezialfall, der aber auch als Generalisierung betrachtet werden kann.
Multi-Problem-EA	Wird das Immunsystem als Problemlösungssystem betrachtet, so ist dort eine andere Sichtweise von Problem und Lösungsvorschlag zu beobachten (siehe Computer-Immunologie). Die Aufgabe des Immunsystems ist die Unterscheidung zwischen Selbst und Nicht-Selbst, sowie die Vernichtung von Objekten aus der Klasse Nicht-Selbst. Die Objekte der Klasse Nicht-Selbst sind dabei sehr unterschiedlich, d.h. das Problemlösungssystem ist zu einem Zeitpunkt mit der potentiellen Lösung sehr vieler unterschiedlicher Probleme konfrontiert, bzw. es ist durch seine Strukturen auf die Lösung vieler Probleme vorbereitet. Wird eine solche Sichtweise auf ein Problemlösungssystem wie ein GP-System übertragen, so bedeutet dies, dass zu einem Zeitpunkt viele Probleme bzw. Problemtypen in dem System aktiv sind, und dass ein Lösungsvorschlag, der im Rahmen eines Problems erzeugt wurde, auch an anderen Problemen bzw. Problemtypen getestet wird. Neue Probleme kommen permanent von Aussen hinzu, zu denen alte Lösungsansätze versucht werden, die, wenn sie nicht adäquat sind, durch neue Lösungen ergänzt werden, die durch Variationsoperationen aus den alten Lösungen erzeugt werden. Im Gegensatz zu einem Mehr-Ziel-Optimierungsansatz müssen diese Probleme nicht in einer gemeinsamen Lösung angegangen werden, d.h. es muss keine globale Pareto-Strategie angewendet werden. Da die Probleme jedoch nicht vollständig verschieden sind, kann vermutet werden, dass Lösungen, die sich bei einem Problemtyp bewährt haben, bei einem ähnlichen Problem auch anwenden lassen.
P- und L-Individuen	Die Programm-Individuen werden als Lösungsvorschläge für Probleme interpretiert, die in dem betrachteten System durch Beispielsmengen bzw. durch formale Beschreibungen vorliegen, und ebenfalls in Programmen verpackt sind, sodass zwischen Problem(P)- und Lösungs(L)-Individuen unterschieden werden kann. Denbar wäre eine eigene Problembeschreibungssprache, mit det die P-Individuen formuliert werden, und die durch GP-Operatoren ebenso manipulierbar ist wie eine Lösungsbeschreibungssprache. Beim GP und insbesondere bei CGP stellt sich jedoch die Frage, ob und wie diese beiden Sprachen unterscheidbar sind, bzw. ob eine Unterscheidung überhaupt angestrebt werden soll, was im Rahmen dieses Projektes untersucht werden soll. Aufgrund des hohen Aufwandes von Programmevaluationen kann nicht jeder Lösungsvorschlag (L-Programm) mit jedem Problem (P-Programm) verglichen werden, sodass eine wichtige Untersuchungsrichtung im Rahmen dieses Projektes in der Entwicklung und Prüfung von Strategien besteht, mit denen L-Individuen an P-Individuen evaluiert werden.
Zeitlich variierende Problemprioritäten	Ein naheliegender Ansatz sind extern vorgegebene, zeitlich variierende Problemprioritäten, d.h. in einem bestimmten Zeitraum werden eine Anzahl von Problemen als wichtig klassifiziert, mit der Folge, dass in Abhängigkeit von den verfügbaren Ressourcen Evaluationen von L-Individuen sich auf diese Probleme beschränken.
Strukturierung von Individuen, z.B. Clusterung	Besteht die Möglichkeit der unüberwachten Strukturierung der einzelnen Individuen, so wäre dies ein wesentlicher Fortschritt. Die Bildung von Individuen-Clustern in einer Population durch ein unüberwachtes Verfahren wurde bereits in Bachelier (1998b:96ff) vorgeschlagen. Die Verwendung von SOM-Modellen als unüberwachte Verfahren hat in der Folge zu einer Reihe von Erweiterungen von EA geführt bis hin zu den Fitness-Approximationsmodellen auf der Basis von SOMs (Bachelier (1999d)). Genutzt werden können im Zusammenhang dieses Projektes auch die Ansätze des Clusterings im Rahmen von EA (siehe Software-Projekt SW04). Im Fall von Programm-Individuen muss ein entsprechendes ähnlichkeitsmass auf der Basis der verwendeten Sprachelemente und der Struktur gebildet werden, wie diese Sprachelemente kombiniert werden. Ein Ähnlichkeitsmass auf der Basis von GP-Graphen ist dabei wesentlich komplexer, als ein Ähnlichkeitsmass auf der Basis eines linearen Genoms, wie z.B. bei den CGP. Diese Ähnlichkeitsmasse verwenden die absoluten und relativen Auftrittshäufigkeiten der einzelnen Sprachelemente, wobei eine Vielzahl von Massen aus dem Information Retrieval (IR) genutzt werden kann (Bachelier (1995)), indem die Sprachelemente als Terme und die Programme als Dokumente interpretiert werden. Können Klassen von L-Individuen durch ihre Struktur gebildet werden, so könnten L-Prototypen ermittelt werden, die bezüglich aller oder einer Auswahl von P-Individuen evaluiert werden. Liegen auf der anderen Seite gute Evaluierungsergebnisse eines L-Individuums auf der Basis eines Problems vor, so können ähnliche L-Individuen bezüglich des gleichen Problems evaluiert werden, oder das L-Individuum wird bezüglich ähnlicher Probleme (P-Individuen) getestet, was voraussetzt, dass Probleme aufgrund eines Ähnlichkeitsmasses in einer Problembeschreibungssprache geclustert werden können. Die weitest gehenden Ansätze können durchgeführt werden, wenn P- und L-Individuen in einer gemeinsamen Sprache formuliert sind, wie z.B. als Sequenz von Maschinenbefehlen beim CGP. In diesem Fall können P- und L-Individuen in einem gemeinsamen, metrischen Beschreibungsraum dargestellt werden, dessen Koordinatenachsen durch die Sprachelemente aufgebaut werden. Lösungsansätze können dann an naheliegenden Problemen getestet werden. Die Sichtweise, dass Dokumente durch Terme definiert sind, wird im IR durch die Term-Dokument-Matrix erweitert, die auch so interpretiert werden kann, dass Terme durch Dokumente definiert werden, indem jedem der t Terme ein d-dimensionaler Vektor zugeordnet wird. Jede Komponente dieses Vektors korrespondiert zu einem der d Dokumente in der Dokumentenkollektion, und wird von einem Gewichtsfaktor (Deskriptor) besetzt. Dies ergibt zum einen den t-dimensionalen Dokumentraum, in dem Dokumente durch Terme dargestellt werden, und einen d-dimensionalen Termraum, indem Terme durch Dokumente in einer konstanten Dokumentkollektion dargestellt werden. Beide metrische Räume sind miteinander eng gekoppelt, da die Veränderung der Position von Objekten in einem der beiden Räume das Koordinatensystem des anderen Raumes verändert, sodass unter bestimmten Bedingungen von rekursiv definierenden Räumen gesprochen werden kann (siehe Bachelier (1995:137ff)). Dies gilt, wenn in einem Raum Cluster gebildet werden, die zur Rekodierung des anderen Typs von Objekten genutzt wird, indem ein neues Koordinatensystem aufgebaut wird, das soviele Achsen besitzt, wie Cluster in dem anderen Raum aufgebaut wurden.  Neben der Term-Kodierung von Dokumenten existieren noch Möglichkeiten durch eine Multi-Dimensionale Skalierung (MDS) metrische Räume zu erzeugen. Liegen die Dokumente bzw. Individuen z.B. als String von Sprachelementen vor, so kann die Ähnlichkeit zwischen zwei Strings als Funktion der Anzahl der Ersetzungsoperationen beschrieben weren, die notwendig sind, um einen String in den anderen umzuwandeln. Aus den Ähnlichkeitswerten lässt sich durch eine Multi-Dimensionale Skalierung ein metrischer Raum erzeugen, in dem jedem String eine Position entsprechend seinem Ähnlichkeitsvektor zugewiesen werden kann. Der prinzipielle Nachteil aller dieser Verfahren besteht jedoch darin, dass eine Form von Repräsentation und Ähnlichkeitsfunktion extern gegeben sein muss. Bei der Beschreibung eines Dokumentes durch eine Menge von Termen wird aus der absoluten und der relativen Häufigkeit des Auftretens des Term seine Wichtigkeit in Form eines Gewichtes oder Deskriptors gebildet, wobei die Deskriptorfunktion extern gegeben werden muss. Bei einer MDS muss die Art der Ähnlichkeitsfunktion extern spezifiziert werden.
(my x p)-Fitnessmatrix	Eine Strukturierungsmöglichkeit, die ohne die externe Festlegung von Deskriptor- und Ähnlichkeitsfunktionen auskommt, würde sich ergeben, wenn als Voraussetzung jedes L-Individuum für jedes P-Individuum eine Fitness besitzen würde. Es ergibt sich dann eine Fitnessmatrix, in der alle my L-Individuen und alle p P-Individuen in einer (my x p)-Matrix verknüpft sind. Die Fitnesswerte können verwendet werden, um einen p-dimensionalen L-Individuenraum aufzubauen, genauso wie ein my-dimensionaler P-Individuenraum aufgebaut werden kann. In beiden Räumen können wiederum unüberwachte Strukturierungen vorgenommen werden.
Generationsüberdauernde Speicherung von Individuen	Durch eine multiple Zuordnung eines L-Individuums zu mehreren P-Individuen gelangt man bereits im gewissen Umfang zu einer generationsübergreifenden Speicherung von L-Individuen. Sollte bei einer (my+lamda)-EA im Generationsverlauf ein L-Individuum in der L-Population eines P-Individuums nicht in die Nachfolgepopulation übernommen werden, so existiert es möglicherweise in der L-Population eines anderen P-Individuums weiter, und könnte wieder in die betrachtete L-Population migrieren. Es existieren im Bereich der EA auch andere Strategien, mit denen Individuen oder Individuenbestandteile für einen Zeitraum von der Selektion ausgenommen werden, d.h. sie werden explizit als selektionsneutral festgelegt, wie z.B. die verschiedenen Formen des Genetic Load (GL) oder Polyploide (siehe Bachelier (1998b:102ff)). Selektionsneutral bedeutet dabei, dass sie nicht gelöscht werden dürfen, wobei sie durchaus an Reproduktionsoperationen teilnehmen dürfen, z.B. wenn mit einer Wahrscheinlichkeit von 1 aus der normalen L-Population der erste Reproduktionspartner bei einer zweigeschlechtlichen Reproduktion ausgewählt wird, und mit einer Wahrscheinlichkeit 0,3 aus der GL-L-Population der zweite Reproduktionspartner bzw. mit 0,7 aus der normalen L-Population. Weitere Ansätze zur generationsübergreifenden Speicherung von Individuen könnten durch die Einbeziehung von Culture Algorithms eingeführt werden.
Migration zwischen P-Individuen-Populationen	Liegen beispielsweise die P-Individuen in einer strukturierten und konstanten Datenbank vor, so kann ein L-Individuum, das in einer Generation erzeugt wurde, an einer Teilmenge von P-Individuen getestet werden. Das L-Individuum kann dann den P-Individuen zugeordnet werden, für das es eine gute Fitness aufweist, sodass sich problemspezifische Subpopulationen bilden, die weiter entwickelt werden können. Cluster von P-Individuen können als eine Form von Population interpretiert werden, sodass eine Clusterstruktur einer Multi-Populations-Struktur entspricht (siehe auch Bachelier (1998b:94ff)). Entsprechend der Vorgehensweise bei Multi-Populations-EA sind Migrationsstrategien formulierbar, wobei jedoch keine P-Individuen wechseln, sondern L-Individuen, die den einzelnen P-Individuen zugeordnet sind.
P-Individuen-Hierarchie	Eine ganz wesentlich Effizienzsteigerung eines solchen GP-Systems könnte durchgeführt werden, wenn es gelingen würde, eine Hierarchie bzw. mehrere Hierarchien von Problemen zu etablieren, unabhängig ob diese extern vorgegeben werden, oder durch ein unüberwachtes Verfahren (hierarchische Clusterung) erzeugt werden. Michalewicz (1996:289ff) befasst sich mit Hierarchien von Evolutions Programmen, d.h. von L-Individuen in der hier verwendeten Terminologie, was aber als Ansatzpunkt verwendet werden könnte. Gelingt die Erzeugung einer Hierarchie, so könnte ein L-Individuum entlang des Hierarchiebaumes an Problemen getestet werden, bis ein Abbruchkriterium erfolgt, wobei eine Baumstruktur als Teilmenge der Hierarchie spezifiziert wird, die P-Individuen enthält, für die das betrachtete L-Individuum eine hinreichende Lösung darstellt, wobei dieses Kriterium absolut oder temporär für eine Generation betrachtet werden kann. Der potentielle Vorteil in einer Hierarchie besteht darin, die Anzahl der Tests zwischen einem L-Individuum und den vorliegenden P-Individuen gegenüber einer flachen Clusterung weiter zu verringern.
Externes Löschen und Einfügen von P-Individuen	Eine konstante, unveränderliche Menge von P-Individuen in einem System ist jedoch nur ein temporärer Zwischenzustand, da nach einiger Zeit L-Individuen auftreten, die ein bestimmtes P-Individuum gemäss einem extern vorgegebenen Mass hinreichend gut lösen. Gelöste Probleme werden aus der Selektion herausgenommen, wobei eine vollständige Löschung oder eine Inaktivierung durchgeführt werden kann. Wird, wie weiter unten beschrieben, eine Reproduktion von P-Individuen und damit eine Selbstorganisation und Koevolution von Problem und Problemlösung zulässig, so entspricht eine Inaktivierung einer Form von selektionsneutralen Repräsentationsanteilen wie dem Genetic Load oder Polyploiden (siehe Bachelier (1998b:102ff)). Im Laufe der Reproduktionsfolge von P-Individuen können diese Bestandteile nach unterschiedlichen Strategien wieder aktiviert werden, d.h. gelöste Probleme können wieder als Reproduktionspartner in die P-Individuenreproduktion aufgenommen werden. Ist keine P-Individuen-Reproduktion zulässig, so werden gelöste Probleme aus der P-Individuenstruktur entfernt, sodass frei werdende Ressourcen auf die verbleibenden Probleme verteilt werden, oder andere Probleme werden von aussen hinzugefügt, die in eine gegebene P-Individuen-Clusterung eingefügt werden, die sich dadurch adaptiert.
Reproduktion von P-Individuen und Koevolution zwischen P- und L-Individuen	Bislang wurde von extern vorgegebenen P-Individuen ausgegangen, während in einer Generation die Anzahl der L-Individuen bei einer Population durch ihren Reproduktionsprozess my bzw. lamda beträgt. Durch die Aufgabe des Constraint der konstanten P-Individuen werden neue Klassen von Verfahren möglich, indem P-Individuen sich reproduzieren dürfen. Die Reproduktion von P-Individuen durch Rekombinations- und Mutations-Operationen ist jedoch dann kein Problem, wenn sie wie die L-Individuen als GP in einer, womöglich gemeinsamen Sprache formuliert sind. Zur P-Individuen-Selektion können unterschiedliche Verfahren angewendet werden, die jedoch eine Zuordnung einer Bewertung zu den P-Individuen benötigen, was das eigentliche Problem im Rahmen der Koevolution ist. Eine Klasse dieser Verfahren steht im Kontext der konkurrierenden Koevolution, wie sie von Hillis (1992) beschrieben wird. Die Evolution der Probleme und der Problemlösungen konkurrieren hierbei um Ressourcen, wobei immer komplexere Probleme erzeugt werden, die für die L-Individuen schwerer lösbar sind. Die Fitnessstruktur der P- und L-Individuen sind dabei invers definiert, d.h. besitzt ein L-Individuum für ein Problem eine hohe Fitness, so besitzt das Problem an der Stelle des L-Individuums eine kleine Fitness. Neben der konkurrierenden existieren auch Formen der kooperierenden Koevolution (Symbiose), bei denen die Fitnessfunktion nicht invers definiert ist (siehe auch Potter (1997)).
Fokussierungsarten auf ungelöste Probleme	Berücksichtigt man, dass es sich bei den P-Individuen um Probleme handelt, so sollten die P-Individuen fokussiert werden, zu denen bislang keine hinreichende Lösung gefunden wurde. Eine Fokussierung kann zum einen dadurch erfolgen, dass die Ressourcen erhöht werden, die zur direkten Lösung des Problems aufgewendet werden, d.h. indem mehr L-Individuen erzeugt und evaluiert werden, die zu diesem P-Individuen gehören. Es existierten auch indirekte Methoden der Fokussierung, indem Probleme reformuliert werden, oder indem verwandte Probleme erzeugt werden, zu denen eine Lösung gesucht wird. Dies bedeutet, dass zur Fokussierung auch eine erhöhte Reproduktion dieser P-Individuen gehört. Indirekt ist damit auch eine Erhöhung der Reproduktions- und Evaluationstätigkeit von zugehörigen L-Individuen verbunden, da für die neuen P-Individuen Lösungen in Form von L-Individuen gesucht werden. Gelingt es, hinreichende Lösungen für die Nachkommen von ungelösten Problemen zu erzeugen, so werden diese L-Individuen für die alten P-Individuen getestet, d.h. sie migrieren in die L-Individuen-Population dieser Probleme, die dann neue Phasen der Reproduktion und Evaluation durchlaufen.
Biologische Methapher von koevolutionärer P- und L-Entwicklung	Die Kopplung von L-Individuen an P-Individuen, der Austausch von L-Individuen und die Reproduktion beider Individuentypen kann durch eine biologische Metapher verdeutlicht werden. Ein P-Individuum wird dabei als ein Mitglied einer Spezies aus grossen Individuen betrachtet, die von einem Schwarm kleiner Individuen (L-Individuen) umgeben sind. Die Umgebung eines P-Individuums ist für den zugehörigen L-Schwarm quasi ein eigenes Ökosystem, in dem die L-Individuen leben und sich reproduzieren. Gelegentlich kommt es zu Begegnungen zwischen P-Individuen, mit der Folge, dass einige L-Individuen in einen anderen Schwarm wechseln, was einer Migration entspricht, unabhängig nach welchen Regeln diese durchgeführt wird. Begegnungen zwischen P-Individuen können unterschieden werden zwischen reproduktiven und nicht-reproduktiven Begegnungen, wobei im Rahmen der reproduktiven Begegnungen z.B. zwei P-Individuen einen P-Nachkommen erzeugen, der von beiden Schwärmen seiner Eltern Initialisierungs-L-Individuen erhält, die einen eigenen, unabhängigen Schwarm erzeugen, während die fehlenden L-Individuen bei den Eltern durch Reproduktion der verbleibenden L-Individuen aufgefüllt wird.
Meme, Offene Welt und individuelle Prozessoren	Die dargestellte Sichtweise von P- und L-Individuen besitzen einen Bezug zu dem Begriff der Meme von Richard Dawkins (The World of Richard Dawkins) und der "Offenen Welt" von Karl Popper (The Karl Popper Web). Meme könnten als Programme interpretiert werden, die durch individuelle Prozessoren (kognitive bzw. mentale Systeme) innerhalb von Kulturen verarbeitet und weiterverbreitet werden. In dem betrachteten Zusammenhang wären P- und L-Individuen Ausprägungen von Memen, die einer Selbstorganisation unterliegen, wenn P- und L-Individuen sich reproduzieren können, und wenn eine koevolutionäre Definition der Fitness zwischen diesen beiden Individuentypen oder Spezies existiert. Insbesondere sind Szenarien denkbar, bei denen Meme an die reale, offene Welt gekoppelt werden, indem neue P-Individuen in das System eingefügt werden, und indem Formen des Aktiven Lernens (siehe Software-Projekt SW07) durchführbar sind, bei denen L-Individuen als Experimente in der offenen Welt ausgeführt werden, und deren Ausgang als Fitnessbewertung oder Bestandteil einer Bewertung in das System wieder eingehen. Dadurch wird eine Open-End-Evolution initiiert, wobei zu deren interner Repräsentation Programme im Prinzip beliebig gross werden können, oder indem die Auflösung der Koordinatenachsen der metrischen Räume beliebig klein werden kann. Der Aspekt individueller Prozessoren muss hier noch eingefügt werden. Es wäre naheliegend, den EA als Prozessor zu interpretieren, wodurch individuelle Prozessoren auf ein Meta-EA-System verweisen, d.h. ein Prozessor ist ein individueller EA mit speziellen Strategieparametern wie Anzahl der Individuen pro Population, Anzahl der Nachkommen, Art der Rekombination, Art der Mutation und Selektionsart. In biologischen Immunsystemen und Computer-Immunsystemen sind individuelle Prozesse und Prozessoren der Garant für ein robustes Gesamtsystem, da jedes Individuum über andere Antigene verfügt, sodass in einer hinreichend grossen Population immer eine Teilpopulation gegen einen Immunangriff geschützt ist. In Herdy (1993) wird die Anzahl der Nachkommen als Strategieparameter in einer hierarchischen ES einem Selbstadaptionsprozess unterzogen. Entsprechend dieser Vorgehensweise kann eine Hierarchie wie z.B. Familie(Gattung(Art(Varietät))) aufgestellt werden, wobei daraus jedoch nicht folgt, auf welcher Ebene welche der Parameter dem evolutionären Selbstadaptionsprozess überlassen wird.
- - - - - - - -
Referenzen	Dawkins, Richard: The selfish Gene. 1989. Herdy,Michael: The number of offsprings as strategy parameter in hierarchically organized evolution strategies. SIGBIO Newsletter 13 (2), 1993, S. 2 - 7. Hillis, W. D.: Coevolving Parasites Improve Simulated Evolution as an Optimization Procedure. In: Langton, C. G.; Taylor, C.; Farmer, J. D.; Rasmussen, S. (eds): Artificial Life II. Addison-Wesley, 1992, S. 313 - 324. Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. 3 Auflage, 1996 . Potter, Michael A.: The Design and Analysis of a Computational Model of Cooperative Coevolution,1997.

Zum Seitenanfang

VI-ANEC | Über das Institut | Software-Projekte | Hardware-Projekte | Best-Paper-/Best-Program-Awards | Sponsoring | Dienste | Kontakt