[Artikel] Simulierte Evolution

[Luckie]

Simulierte Evolution

Um was geht es dabei? Kurz gesagt geht es darum, dass sich Computerprogramme selber schreiben und verbessern. Sich also entwickeln, sich verbessern und sich der gestellten Aufgabe immer besser "anpassen" bzw. sie immer besser lösen können. Und faszinierend ist, was man damit zum Schluss in der Praxis selber, überraschenderweise oder auch nicht, erleben kann.

Artikel: Simulierte Evolution

[negaH]

Zitat:

Ich seh den unterschied darin, dass man wenn man zum Beispiel das Maximum einer Funktion sucht, dann sucht man mit dem GA die Koordianten, mit der GP aber erstellt man ein Programm dass das Maximum einer Funktion bestimmt. Also das eine erstellt Punkte im Raum, das andere Lösungsmethoden.
Die Lösung des GAs ist dann problemspezifisch, die Lösung des GPs idealerweise nicht.

Gut, und wie erstellt man GPs ?
Meine Antwort ist mit Hilfe von GAs bzw. mit der Theorien der GAs. Ergo: GPs sind nur eine Anwednungsmöglichkeit für Genetische Algorithmen (häng dich mal nicht so sehr an dem Wort Algorithmus auf, der bezieht sich auf die Theorie WIE man mit Kodierungen als Gene arbeiten muß).


Gruß Hagen

[stoxx]

wo ist (siehst) Du jetzt nochmal den Hauptunterschied zwischen Evolutionsstrategien und GA´s ?
Das hab ich irgendwie noch nicht ganz verstanden.
Danke !

[negaH]

Nun in der Historie

Die ES sind im Grunde einfache Arrays of Float. Jeder dieser Flaot beschreibt einen Parameter in einer Formel, zb. eben die Stärke, Anzahl, Winkel von Stahlträgern in einem Kran. Man verändert benutzt nunr in der Selektierungsfunktion diese Parameter um rechnerisch einen Kran zu simulieren. Als Resultat dessen kommt eine Fintness raus, also wie verhält sich unser Kran unter Windlast, bei wieviel Last bricht er usw. Danach wird eine neue Population von Kranen erzeugt. Eben mit Vererbung, indem man die besten Krane untereinander deren Parameter in den Arrays[] rekombiniert -> Crossover und daraus dann neu Kinder erzeugt. Als letztes werden nun per Zufall einige Floatzahlen in den Kinderarrays leicht verändert, so ca. 2.3 Prozent. Und dann beginnt wieder alles von vorne.
Da man die nächste Generation zum großen Teil aus den vorher besten Eltern erzeugt hatte heist dies auch das diese Evolution sich immer besser an die Selektierungsfunktion anpassen wird. Und diese Selektierungsfunktion ist das was wir als Zielsetzung erreichen wollen, WIR spielen Gott und entscheiden wer sich wohin und wie entwickeln soll.

Die GAs konzentieren sich auf die Fragestellung WIE man Informationen am besten kodiert. Als Vorbild diente die Natur mit ihren Genen. Dabei stellte man fest das es auf unserer DNA Genübergreifend bestimmte Muster gibt, also kodierte Abschnitte von Genen. Man erkannt eine Hirarchie in der Wirkungsweise dieser Genstrukturen. Gene bilden Allele (Funktionsgruppen) die sicherstellen das eine Abfolge von Genen auch einen Sinn ergeben. Solche Allele ergeben dann Chomosomen die dann im besoinderen sicherstellen sollen das bei einem Crossover (geschlechtliche Vererbung) nicht die Gene, Allele zerstört werden und so ein lebensunfähiges Individuum ergeben. Die Natur rekombiniert also Chromosomen beim Sex. Desweiten betrachtet man den Einfluß der Mutation. Zu wenig Mutation lässt die Evolution zu langsam vorranschreiten, zo viel Mutation zerstörte die Evolution. Die Mutation arbeitet immer auf allen Genen, und nicht wie zb. die Verrebungen auf Chmosomen/Allelen als in sich funktionale Genketten.
Die nächst höhere Stufe der Betrachtungen in der GA sind die Populationen. Man erkannte und experimentierte mit ganzen Populationen, einige isoliert auf Inseln, andere mit regem Genaustasuch zu anderen Populationen.

Man erkennt also schon das sich die GAs viel stärker auf die Fragestellung wie man Informationen kodieren sollte, wie man über diese Kodierungen eine Evolution in Gang setzt, und wie sich Populationen entwickeln sollten, auseinander setzt. Man versucht also die Natur, die Evolution in der Natur, im Computer zu simulieren und daraus Erkenntnisse zu gewinnen.

Klar gibt es auch konkrete Anwendungsgebiete der GAs. Zb. das Travelsman/Salesman Problem (Problem des Handlungsreisenden). Allerdings wenn man es genauer betrachtet so sind die ES auf diesem Gebiet den GAs überlegen. Dh. viele der Problemlösungen der GAs lassen sich über die ES viel leichter und logischer lösen.

Mittlerweile sind aber die ES nur eine "Unterform" der GAs (laut Meinung der führenden Forscher in diesem Gebiet, und das sind die Amis). ES sind im allgemeinen GAs ohne spezielle Kodierungen.

Historisch gesehen sind es aber zwei komplette andere Ansätze zum gleichen Problem der Evolution. An beiden lassen sich die Gesetzmäßigkeiten demonstrieren, der Evolution etc.pp. Nur das Kodierungsproblem der Gene in der Natur ist mit den GAs simulierbar,m aber das ist garnicht die Aufgabe der ES. Ingeniuerstechnisch betrachtet sind die ES effektiver. Informationstheoretisch betrachtet sind die GAs ertragsreicher.

Gruß Hagen

[Tubos]

Ich habe noch eine Frage dazu an negaH, oder an jemand anderen, der sich damit auskennt.

Wie funktioniert das Erstellen einer neuen Generation beim Genetischen Programmieren?
Die erfolgreichen Algorithmen werden oft kopiert, die erfolglosen gar nicht. Nach dem Kopieren mutieren einige zufällige Individuen. Soweit hab ichs kapiert.
Dann gibt es noch die Variante, dass sich zwei Individuen zu einem neuen zusammenkopieren. Aber wird dabei nicht meistens der zuvor erfolgreiche Algorithmus zerstört? Ich kann ja nicht beurteilen, ob ein bestimmter Teil davon gut ist, weil ich nur einen Fitnesswert für das gesamte Individuum habe.
Kann diese sexuelle Fortpflanzung alleiniger Bestandteil eines GP-Systems sein oder ist das eine Form, die man per Zufall mit der monogamen Fortpflanzung mischen sollte?

mfg. Tubos

[Luckie]

Ich habe gerade ein Mail zu diesem Artikel bekommen. In der wurde ich auf diese Homepage aufmersam gemacht: http://www.cambrianlabs.com/Mattias/ Man sollte sich mal da das Schlangen Programm angucken. Dort wird demonstriert, wie die Schlage lernt sich fortzubewegen. (OK, eigentlich ist es wohl eine Raupe. )

[jus]

Um Hagen's Aussagen wissenschaftlich zu untermauern gebe ich hier die Literaturangaben zu den Original-Artikeln in den Bereichen. Der Grund ist, dass ich gerade an einer Arbeit schreibe, die GA einsetzt, und habe somit auch die Literaturquellen für Interessierte gleich zur Hand.

Evolutionsstrategien (ES) begründet durch
Rechenberg I., Evolutionsstrategie, Stuttgart: Friedrich Frommann-Verlag, 1973

Evolutionäres Programmieren (EP) begründet durch
Fogel L. J., Owens A. J., Walsch M. J., Artificial Intelligence through Simulated Evolution, New York: John Wiley, 1966

Genetische Algorithmen (GA) begründet durch
Holland J., Adaption in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control and Artificial Systems, Ann Arbor: The University of Michigan Press, 1975

Genetische Programmierung (GP) begründet durch
Koza J. R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, Cambridge, MA.: The MIT Press, 1992

Zitat von negaH:

...Zb. die Frage: wieviel Prozent der Gene werden durchsachnittlich durch Mutationen verändert ? DIe Antwort, ca. 2.3 Prozent und das frappieende ? die Natur mutiert nachweislich ca. 2.3 Prozent der Gene. Man fand also unabhängig voneinander heraus, also die Biologen und die Informatiker, das sich dieser Prozentsatz als am besten erwies. (so schlagt mich bitte nicht wenn es nicht 2.3 Prozent sind,...

@negaH
kannst du mir den Artikel(n) mit den ~2,3 Prozent nennnen, oder irgendwie zukommen lassen, das würde mich brennend interessieren.



Grüsse,
jus

[negaH]

Zitat:

Ich habe noch eine Frage dazu an negaH, oder an jemand anderen, der sich damit auskennt.

Wie funktioniert das Erstellen einer neuen Generation beim Generischen Programmieren?
Die erfolgreichen Algorithmen werden oft kopiert, die erfolglosen gar nicht. Nach dem Kopieren mutieren einige zufällige Individuen. Soweit hab ichs kapiert.
Dann gibt es noch die Variante, dass sich zwei Individuen zu einem neuen zusammenkopieren. Aber wird dabei nicht meistens der zuvor erfolgreiche Algorithmus zerstört? Ich kann ja nicht beurteilen, ob ein bestimmter Teil davon gut ist, weil ich nur einen Fitnesswert für das gesamte Individuum habe.
Kann diese sexuelle Fortpflanzung alleiniger Bestandteil eines GP-Systems sein oder ist das eine Form, die man per Zufall mit der monogamen Fortpflanzung mischen sollte?

mfg. Tubos

Uff viele Fragen. Vorweg ich kenne mich mit den EP und GP (siehe vorherigen Thread) nicht konkret aus deshalb versuche ich mal übertragen auf die GAs zu antworten.

Deine Annahme das durch das Zerteilen der Gene sehr oft Kinder entstehen die nicht lebensfähig sind ist absolut berechtigt. Das ist nämlich ein Grundproblem und auch eine Fragestellung in den GAs -> also wie müssen die Genketten organisiert (strukturiert) sein, das eben bei der Vererbung möglichst keine Kinder entstehen die nicht lebensfähig sind. Lebensfähig heist also in unserem Sinne auch einen Sinn ergeben und unsere gesetzten Optimeirungsziele erreichen können. In deinem Sinne ist es eben die Frage wie man sicherstellt das ein so erzeugtes "Program" auch wirklich syntaktisch korrekt ist.

Und diese Syntax ist es auch die man zu logisch zerlegen muß das man sie dann in den Gene umkodieren kann. Ich sprach oben schon die Allele an. In den GAs steht diese Wort für eine Funktionsgruppe, eine ganze Kette von Genen die man bei der Vererbung/Rekombination/Crossover eben nicht in der Mitte zerlegen sollte. In der Biologie sind Allele ein bischen anders definiert. Dort stellen sie zwar auch Funktionsgruppen dar (zb. die Augenfarbe oder Farbe der Blüten oder Blutgruppenmerkmale) aber sie sind auch quasi Redundanz-Schnittstellen. Dh. es ist oft so das es mehrere Allele in der DNA gibt die alle zb. die Augenfarbe bestimmen aber meistens ist nur eines dieser Allele auch dominant und die meisten sind reszessiv. Der wichtige und übertragebare Zusammenhang zwischen Biologie und Informatik ist aber das Allele immer Funktionsgruppen sind und meistens aus ganzen Ketten/Sequenzen von Genen bestehen. In der Biologie sind solche "Allele" Abschnitte im DNA Strang die durch besondere Sart/Stop Gene markiert sind. Beim Reproduktionsprozess über die RNA kann über diese Markergene auch quasi eine "Prüfsumme" erzeugt werden und sogar beschädigte Gene können repariert werden.
In der Informatik sind Allele nur eine Definitionsfrage und sie führen dazu das man in der Kodierung der Gene die Datenstrukturen entsprechend anpasst.

Mal ein Beispiel: Wir wollen einen GA entwickeln der in der Lage ist zu einer Menge von Zahlen -> X und einer Menge von Zahlen Y eine Formel zu finden die nach Möglichkeit sehr exakt Y = f(X) berechnen kann. Unser Individuuen in der Population sind also nichts anderes als mathem. Formeln. Eine solche Fornmal hat eine Syntax damit sich auch berechenbar ist. Es gibt also Operatoren wie +,-,*,/,Sqrt(),Power(),Exp() es gibt Konstanten wie +1, 0.1234, PI usw. und es gibt Variablen.

Konstanten und Variablen sind unary, (hm welches Wort gibts dafür im Deutschen?) sie sind also nur Eins.
Operatoren sind immer binary oder größer, sie benötigen also immer mindestens zwei formale Seiten.

Das ist die Syntax und es ist nun sehr wichtig das wir unsere Gene von Anfang an so kodieren das immer gültige Formeln rauskommen. Also sowas wie 1+2------3*SqrSqr/0 darf NICHT in den Gene vorkommen. Wir erledigen dies indem wir unsere Gene entsrepchend konstruieren, aus den Genen werden Allele da sie nun zusammenhängende Funktionsgruppen darstellen. Man darf sie bei der Rekombination also nicht mehr auseinander reisen.

Ein solches Allel könnte so aussehen:

1. Gen -> Typus (binary Operator wie +,- oder trinary Operator wie Power(), oder Konstante, oder Variable)
2. Gen -> 1. Data (bei Konstanten/Variablen usw.)
3. Gen -> 2. Data (bei trinary Operator)

Es besteht also aus mehreren Gene, ist variabel in der Genanzahl und ist eine funktiuonale/informationstheoretische Einheit unserer angestrebten Syntax.

Wenn wir also Mutieren dann arbeiten wir immer auf allen Genen. Aus einem Allel das vorher noch Operator + darstellte könnte durch Mutation des 1. Genes also auf einmal ein Konstante entstehen.

Wenn wir Rekombinieren, egal wie dann machen wir dies aber immer auf Allele Ebene, niemals auf die einzelnen Gene betrachtet.

Somit entstehen quasi nur per Definition aus der "Syntax" der Gene immer auch vollwertige und Funkionsfähige Formeln.

Nun können wir aber eine Division durch Null NICHT über diese Regel ausschließen, das wäre nämlich evolutionär gesehen falsch, da die KEIN problem der Syntax -> der Sprache ist. Solche "Fehl-Individuuen" filtern wir raus indem wir sie in der Bewertungsfunktion bei der Selektion einfach als schlecht bewerten. Ein Formel-Individuum das eine Divison durch Null rechnet vermehrt sich also fats garnicht und somit vererbet es auch nicht seine fehlerhaften Gene in die nächste Population.

So, dieses einfache Beispiel kannst du nun auf die Syntax einer Programmiersprache weiterdenken und kämst bei einigen Grundregeln der EP/GP an.

Eine weitere und oft benutzte Möglichkeit ist der Einfluß im Crossover/Rekombination zu beschränken. Ziel ist es die Wahrscheinlichkeit lebensunfähige Individuuen zu erzeugen auf eine Weise zu reduzieren indem man eben weniger "zerschneidet". Zwei Individuuen mit sehr langen Genketten werden also beim Crossover nur in zwei Genkettenteilen zerlegt, mehr nicht. Man bestimt nur per Zufall WO man diese DNA eines Individuums zerschneidet. Nun erzeugt man zwei Kinder indem man einfach über kreuz diese 4 Teil DNA Stränge wieder zusammensetzt. Trennt man eine DNA->Genkette immer an Allel-Grenze so wird zumindestens nicht die Syntax zerstört. Die Wahscheinlichkeit das diese neuen Kinder immer noch funktionieren ist direkt umgekehrt proportional zur Anzahl der Individuuen innerhalb einer Population. Je größer die Population je geringer die Wahscheinlichkeit das diese Kinder fehlerhaft sind. In der nächsten Selektion erkennt man ja das solche fehlerhaften Kinder, nun potentielle Eltern, nicht überleben dürfen und lässt sie sich nicht vermehren, sie sterben quasi aus.

Denoch kann es bei bestimmten Problemstellung nicht vermieden werden das viele nicht lebensfähige Kinder erzeugt werden. Man versucht das über eine Co-Evolution in Co-Populationen zu lösen. Quasi macht man während der Evolution einer Population immer wieder Backup-Populationen. Stagniert nun die aktuelle Evolution der Population dann injeziert man Genmaterial->Individuuen dieser Backup-Population hinein. Das ist also so als ob man aus der Zeit von Da Vinci par Menschen auftaut und sie in unserer Zeit sich vermehren lässt.

Oder aber man benutzt die Co-Evolution. Dabei arbeitet man qausi mit mehreren Evolutionen in parallel. Der Unterchied zischen diesen ist das man andere Parameter für die Selektierungsfunktionen benutzt. Das Stichwort hier sind die Eliten. Es gibt also eine Eliten-Population die mit enorm strengen Selektierungsfunktionen arbeiten. Diese entwickeln sich im günstigen Falle rapide haben aber im schlechtesten Falle die Angewohnheit in einem Schlage komplett auszusterben. Man verhindert dies nun indem man in einer Cor-Evolution keine Eliten züchtet, die Selektierungsfunktion also auf Robustheit einstellt. Im Falle einer Stagnation einer Eliten-Evolution injeziert man über einen Gentransfer->Individuenaustasuch wiederum neue Erbmasse in diese Populationen.

Du siehst das es mehrere Ansatzpunkte gibt:

1.) die Kodierung der Gene in Funktionsgruppen wie Allele und Chromosomen und das Berücksichtigen dieser Kodierungsmerkmale bei der Rekombination/Vererbung
2.) die Selektierungsfunktion
3.) die Evolution über Co-Populationen und Eliten

Soweit das was ich von damals noch über GAs gelernt habe (immerhin schon wieder 15 Jahre her )

Gruß Hagen

[negaH]

Achso noch was ganz ganz Wichtiges!

Die Redundanz in den Genen:

Oben sprach ich als Beispiel eine Formel-GA an. Wir hatten

1. Gen -> Typus (binary Operator wie +,- oder trinary Operator wie Power(), oder Konstante, oder Variable)
2. Gen -> 1. Data (bei Konstanten/Variablen usw.)
3. Gen -> 2. Data (bei trinary Operator)

definiert. Nun die Redundanz besteht darin das zb. der Typus erweitert wird durch "inaktiv". D.h. dieses komplette Allel ist garnicht aktiv und kein Bestandteil der sich ergebenden Formel. Aber! es ist als Genkette im Individuuem und wird auch weiter vererbt, das ist wichtig. Es ist also quasi Müll-DNA oder eben redundant.

Das gleiche gilt für die Gene 2. und 3. in unserem Allel, nämlich immer dann wenn zb. nur ein unary Operator im Allel kodiert wurde und somit das Gen 3. garnicht benötigt wird für eine sinnvolle Formel. Wird vererben und auch mutieren denoch diese Gene immer mit.

Denn in einer spärteren Population in einem späten Nachfahre könnte diese Allel durch Mutation wieder aktiviert werden und komplett neue und unbekannte Formeln erzeugen. Diese damasl noch aktiven Allele könnten nämlich ein Bestandteil eines Individuums gewesen sein das sehr sehr potent, also sehr gut gewesen wäre aber auf Grund anderer Gene/Allele nur durchschnittlich gut gewesen ist. Durch die Mutation auf inaktiv geht diese Erbmasse nicht verloren und führt dann in der späteren Evolution nach Aktivierung im Zusammenhang mit nun anderen Genen in einem Individuum dazu das dies besonder gut/potent wird. Wir erzeugen somit quasi in unserer Kodierung übr diese Gene ein Gedächtniss der Evolution innerhalb der Erbmasse.

Es ist also wichtig das du nicht versuchst in deinen GAs solche Dinge "weg zu optimieren" weil du es "gut" meinst

Ergo zu den obigen 3 Punkten kommt noch einer hinzu:

1.) die Kodierung der Gene in Funktionsgruppen wie Allele und Chromosomen und das Berücksichtigen dieser Kodierungsmerkmale bei der Rekombination/Vererbung
2.) die Selektierungsfunktion
3.) die Evolution über Co-Populationen und Eliten
4.) Redundanz und inaktive Müll-Gene

Gruß Hagen

[Tubos]

Zitat:

In deinem Sinne ist es eben die Frage wie man sicherstellt das ein so erzeugtes "Program" auch wirklich syntaktisch korrekt ist.

Also das habe ich eigentlich nicht gemeint. Ich habe dabei schon angenommen, dass eine Sprache konstruiert wird, bei der Syntaxfehler unmöglich sind ODER dass beim Mutieren darauf geachtet wird, dass das Programm syntaktisch korrekt bleibt.
Mit "Algorithmus zerstören" meinte ich vielmehr, dass der neue evolvierte Algorithmus nicht mehr die Aufgabe erfüllt.
Man nehme zwei Programme, die beide einer Wand folgen können. Dann nimmt man einen Teil des ersten Programms und einen Teil ds zweiten, fügt sie zusammen - und plötzlich kann das Programm überhaupt nichts mehr.
Deine Antwort war aber trotzdem hilfreich, danke!

Zitat:

unary, (hm welches Wort gibts dafür im Deutschen?)

unär!

Zitat:

Konstanten und Variablen sind unary, (hm welches Wort gibts dafür im Deutschen?) sie sind also nur Eins.
Operatoren sind immer binary oder größer, sie benötigen also immer mindestens zwei formale Seiten.

Soweit bin ich auch schon gekommen. Das kann man dann als binären Baum darstellen:

Code:

Baum:
           +
          / \
         a   *
            / \
           b   c

(Quelle: http://www.cs.ucl.ac.uk/research/gen...q/gp2faq2.html)
Man kann das natürlich mit Operatoren und Befehlen erweitern und somit nicht nur bei den GAs, sondern auch beim EP anwenden.


Ich sehe also, es gibt viele Möglichkeiten zur Vermehrung und wenn ich das mal selber machen möchte (ich werde wohl mit diesem Baum-Interpreter anfangen), werde ich ein wenig experimentieren müssen.

[Go2EITS]

@Alle
Frage zum Thema, ohne gleich ein neuen Thread eröffnen zu müssen:

Es gab ein Programm, es ist ca. 10 Jahre her, ich sah es in einem Buch (wohl noch älter) für "Künstliche Intelligenz" in dem ein Wissenschaftler/Autor ein Programm geschrieben hat, dass "genetische" Programme erzeugt. Unter anderen durften Programme begrenze Schreib- und Leserechte nutzen, soweit ich weiss, Zugriff auf bestimmte Programmbefehle und hatten begrenzten Ramspeicher für sich zur Verfügung. Die Programme wurden im Laufe der Zeit "intelligenter" und überfluteten letztendlich den Rechner des Wissenschaftlers. - naja, die Zielvorgabe ist für solche Programme meines Erachtens das allererste Kriterium für ein 'genetic programming' und die in einem Pool zur Verfügung gestellten Resourcen, auf die alle Populationen/Programme zugreifen können und und in einem vom Menschen definierten Wertebereich zusätzlich optimieren.

Hat da jemand zu dem Buch noch Informationen darüber? Vielleicht ein Link etc.?

Grüße an die DP!
Go2EITS