Generalized Genetic Programming (GGP)


(Contents)(Previous)(Next)

GGP ist eine Verallgemeinerung von GP, welche bisher nur auf Probleme der symbolischen Regression angewendet wurden, eine viel komplexere Struktur aufweist als GP und bei praktischen Beispielen viel effizienter ist als GP. GGP beinhaltet verschiedenartigste Konzepte und insbesondere eine Kombination mit verallgemeinerten Fourierreihen.

Bekanntlich kann eine in I Punkten vorgegebene Funktion durch eine Fourierreihe mit I Parametern so approximiert werden, dass der Fehler in den I Punkten verschwindet, bzw. numerisch nahezu Null wird. Die Grundfrequenz hängt dabei üblicherweise vom Beobachtungsintervall ab und die Approximation wird periodisch weil die höheren Frequenzen ganzzahlige Vielfache der Grundfrequenz sind. Da die gegebene Funktion keinerlei Periodizität haben kann, oder aber periodisch mit einer völlig andern Grundfrequenz sein kann, ist die Fourierapproximation neben den Beobachtungspunkten ungenau und vor allem ausserhalb des Beobachtungsintervalls fast immer völlig falsch. Standard Fourierreihen eignen sich deshalb nicht für die Extrapolation von Messdaten. Insbesondere wenn die gegebenen Werte f(xi) fehlerbehaftet sind ist es sinnvoll, die Fourierreihe nach K<I Koeffizienten abzubrechen. Dies führt zu einem überbestimmten Gleichungssystem dessen Lösung (im Sinne der kleinsten Fehlerquadrate ein lineares Optimierungsproblem!) zwar relativ schnell durchgeführt werden kann, aber erheblich mehr Rechenzeit erfordert, als die Auswertung der üblichen Formeln für die Fourierkoeffizienten. Diese erste Verallgemeinerung erweist sich praktisch als sehr vorteilhaft, ist jedoch für die Extrapolation nach wie vor ungeeignet. Ist die gemessene Funktion tatsächlich eine Überlagerung von sinusförmigen Funktionen, jedoch mit unterschiedlichen Frequenzen, so ist es naheliegend die Fourierreihe weiter zu verallgemeinern, indem die einzelnen Frequenzen zu Parametern gemacht werden, welche ebenso zu optimieren sind, wie die zugehörigen Amplituden. Allerdings ergibt sich daraus ein nichtlineares Optimierungsproblem für die Frequenzen, welches noch viel aufwendiger ist als das lineare Optimierungsproblem für die Amplituden. Erfüllt die gegebene Funktion die eben gemachte Voraussetzung, so ermöglicht die zweite Verallgemeinerung der Fourierreihen gute Extrapolationen wenn ausreichend viele Frequenzen verwendet wurden und wenn ausreichend viele, ausreichend genaue Daten zur Verfügung stehen. Erfüllt jedoch die gegebene Funktion die Voraussetzung nicht, so kann eine weitere Verallgemeinerung gemacht werden, indem man die sinusförmigen Basisfunktionen durch beliebige Basisfunktionen fk ersetzt. Diese können entsprechend der Amplitude und der Frequenz einen linearen und einen nichtlinearen Parameter haben, man kann aber auch mit mehreren nichtlinearen Parametern arbeiten. Neben dem linearen und dem nichtlinearen Optimierungsproblem kommt nun die Erzeugung der Basisfunktionen hinzu. Dieses ist offenbar ein Selektionsproblem und kann mit einem GP behandelt werden.

Arbeitet man mit einem überbestimmten Gleichungssystem (K<I) zur Lösung des linearen Optimierungsproblems, so dient die Fehlernorm einerseits als Ziel für die nichtlineare Optimierung (Minimierung) und andererseits der Fitnessdefinition für GP. Dabei stellt sich das Problem, dass man der gesamten Reihenentwicklung zum Beispiel 1 durch die Fehlernorm als Fitnesswert zuweisen kann, dass aber dabei mehrere Basisfunktionen involviert sind und GP eine Bewertung der einzelnen Individuen erfordert. Man kann die Situation mit einem Team vergleichen, welches gemeinsam eine Aufgabe löst. Dabei können einzelne Mitglieder kaum einen nützlichen Beitrag leisten oder kontraproduktiv sein und andere die Hauptlast tragen. Für GGP ergibt sich deshalb das Problem, nicht nur eine Gruppenfitness für das ganze Team, sondern auch noch eine individuelle Fitness für die einzelnen Mitglieder zu bestimmen. Offenbar hängt die individuelle Fitness nicht nur von der Form der entsprechenden Basisfunktion, sondern auch von den entsprechenden Parametern ab. Die nichtlinearen Parameter simulieren dabei eine Art Lernfähigkeit der Individuen. Sie sind oft zunächst schlecht gewählt und das Individuum damit wenig nützlich. Mit der nichtlinearen Parameteroptimierung steigt die Nützlichkeit der „lernfähigen" Individuen oft stark an. Damit erhöht sich die Fitness des betreffenden Individuums, aber auch diejenige der Gruppe.

Bei GGP werden zunächst neben der Gruppenfitness verschiedenste Fitnesswerte berechnet, welche die Individuen charakterisieren. Ein Fitnesswert ist die Amplitudenfitness. Ist die Amplitude eines Individuums gross, so hat es einen grossen Einfluss auf das Resultat. Nun heisst das allerdings nicht, dass dieser Beitrag auch nützlich ist, weil eventuell andere Individuen „in entgegengesetzte Richtung" arbeiten. Um die Amplitude sinnvoll auszuwerten müssen ausserdem die Basisfunktionen normiert werden. GGP berechnet die Amplitudenfitness aus dem Amplitudenwert mit einer Formel, welche einen meist guten Defaultwert hat, aber auch vom Benutzer abgeändert werden kann und zumindest theoretisch durch ein externes GP optimiert werden könnte. Da ähnliche Individuen oft gemeinsam nicht viel mehr erreichen als ein einzelnes von ihnen, bestimmt GGP auch einen Ähnlichkeitsfitnesswert. Hinzu kommt eine Einzelfitness, welche angibt, wie gut das Individuum das Problem ohne Mithilfe der andern Gruppenmitglieder lösen könnte und natürlich die bereits erwähnte Gruppenfitness. Aus diesen Fitnesswerten errechnet GGP eine Individualfitness. Wie für die Amplitudenfitness werden für alle Fitnesswerte Formeln verwendet welche verbessert bzw. dem gestellten Problem besser angepasst werden können. Da sich die Fitness dynamisch ändern kann wenn die nichtlinearen Parameter verändert werden oder wenn das Individuum zu einer andern Gruppe stösst, werden neben den aktuellen auch die bisher besten Fitnesswerte und die entsprechenden Parameter gespeichert.

Für die Selektion eines Individuums spielt lediglich seine Individualfitness eine Rolle. Dabei ist zu beachten, dass die Selektion nicht nur zur Wahl der Eltern eine Rolle spielt, sondern auch bei der Zusammensetzung eines Teams zum Zuge kommt. Des weiteren arbeitet GGP mit einem Pool von Individuen, aus dem jeweils nur ein gewisser Teil gelöscht wird, wobei die erfolgloseren Individuen mit grösserer Wahrscheinlichkeit gelöscht werden. Auch hier spielt natürlich die Individualfitness eine wichtige Rolle.

GGP speichert erfolgreiche Pools und Individuen auf Dateien ab, auf welche zurückgegriffen werden kann, wenn ein neues Problem gelöst werden kann. GGP verfügt damit über eine Art genetische Datenbank. Darüber hinaus lassen sich erfolgreiche Formelteile als spezielle elementare Funktionen definieren.

Bei standard GP wachsen normalerweise die Formellängen im Laufe der Evolution markant an. Dadurch steigen die Rechenzeit zur Auswertung und natürlich auch die Redundanz. Da die Wahrscheinlichkeit für genaue Extrapolationen um so höher ist, je einfacher die zugehörigen Formeln sind (Einsteins Prinzip der Einfachheit einer Theorie), arbeitet GGP mit relativ kleinen Formeln und ausserdem mit relativ kleinen, verallgemeinerten Reihenentwicklungen mit lediglich 1-6 Basisfunktionen, d.h. die Teams oder Gruppen sind sehr klein. Es hat sich schliesslich bewährt, mit einer festen Formelarchitektur zu arbeiten. Dadurch wird nicht nur die Definition der Reproduktionsoperatoren und die Speicherverwaltung einfacher sondern auch die natürliche geschlechtliche Reproduktion richtiger implementiert.

width="333"

Figur: Voller, binärer GGP Baum der Tiefe 2 mit 4 Terminals x (Variable), 1.2 (Konstante), p (nichtlinearer Parameter), c (Konstante) und 3 elementaren Operatoren *, sim(a,b):=sin(a*b), ta1(a,b):=a. Resultierende Funktion: f(x) = p*sin(1.2*x)

Um die Redundanz zu vermindern und den zeitaufwendigen Einsatz nutzloser Individuen zu vermeiden, führt GGP eine numerisch einfache Vorprüfung der erzeugten Individuen durch. Individuen, welche die Prüfung nicht bestehen werden mittels Reparaturoperatoren repariert und gelöscht, wenn die Reparatur erfolglos verläuft.

GP kennt nur zwei Arten von Terminals, Konstanten und Variable. Dabei werden die konstanten Terminals üblicherweise durch Zufallsgeneratoren erzeugt. Insbesondere die Erzeugung passender Konstanten erweist sich dabei als enorm ineffizient und nimmt oft riesige Bereiche einer Formel in Anspruch. So ist beispielsweise bei x+(1.3*2.0-(x+x)/(2.0*x-x)) fast die ganze Formel mit der umständlichen Berechnung der Konstanten (1.3*2.0-(x+x)/(2.0*x-x))=0.6 beschäftigt. GGP kennt deshalb (nichtlineare) Parameter sowie symbolische Konstanten als weitere Terminals. Symbolische Konstanten werden normalerweise vom Benutzer definiert und enthalten Grössen die oft vorkommen, z.B. 1, p, e usw.

Eine einfache Mutation einer GP Formel kann den zugehörigen Phänotyp vollständig verändern. Dies gilt offensichtlich auch für die Rekombination zweier Eltern. GP sucht deshalb praktisch nicht in der „Nachbarschaft" erfolgreicher Individuen und ist daher nicht deutlich besser als Zufallssuche. Bei GGP wird die Nachbarschaftssuche verbessert, indem verschiedene Arten von „Minimutationen" eingeführt werden. So kann beispielsweise bei einem Parameterterminal der bisher beste Wert genommen und als Konstantenterminal eingesetzt werden. Dadurch bleibt das Individuum so fit wie es war, verliert aber seine Lernfähigkeit. Macht man nun ein Konstantenterminal zum Parameterterminal, so kann das neue Individuum einen Wert optimieren, der beim alten Individuum nahezu unveränderlich war.


(Contents)(Previous)(Next)