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