Information Technology Reference
In-Depth Information
+
/
x
3
8
2
Abbildung 12.10: Parse-Baum eines symbolischen Ausdrucks mit der Bedeutung
(+ (
3
x
)(
/82
))
Günstig für die Implementierung eines GP ist die Darstellung des symbolischen
Ausdrucks durch einen sogenannten
Parse-Baum
.Parse-Bäumewerdenz.B.imPar-
ser eines Compilers verwendet, um arithmetische Ausdrücke darzustellen und an-
schließend zu optimieren. Solch ein Parse-Baum zur symbolischen Regression ist in
Abbildung 12.10 gezeichnet. In Lisp bzw. Scheme sind Ausdrücke verschachtelte Li-
sten. D. h., das erste Listenelement entspricht dem Funktionssymbol bzw. Operator,
während die nachfolgenden Elemente die Argumente bzw. Operanden des Opera-
tors sind.
Der Ablauf von einem GP, der stark an einen Standard-EA erinnert, ist wie folgt.
Zuerst erzeugen wir eine
Anfangspopulation
zufälliger symbolischer Ausdrücke. Da-
nach
bewerten
wir die Ausdrücke durch die Berechnung der Fitness. Bei Booleschen
Funktionen wäre eine Fitnessfunktion beispielsweise der Anteil korrekter Ausgaben
für alle Eingaben bezüglich einer Stichprobe. Bei der symbolischen Regression wäre
es einfach die Summe der Fehlerquadrate über gegebene Messpunkte: Bei eindimen-
sionalen Daten (
x
i
,
y
i
) für
i
= 1, . . . ,
n
wäre die Fitness
f
(
c
)=
i
=1
(
c
(
x
i
)
y
i
)
2
,wo-
bei
c
das Chromosom bzw. GP ist. Die
Selektion
erfolgt mit einem der im Abschnitt
11.2 besprochenen Verfahren. Nach der Selektion wenden wir
genetische Operatoren
,
meist allerdings nur Crossover, auf die selektierten Individuen an. Die einzelnen
Schritte wollen wir nun kurz erörtern.
12.4.1
Initialisierung
Der Erzeugungsprozess einer Anfangspopulation von Programmen obliegt minde-
stens einem Parameter, nämlich der maximalen Verschachtelungstiefe (der maxima-
len Baumhöhe)
d
max
oder der maximalen Anzahl an Knoten im Baum
n
max
.Zu-
sätzlich können wir mit einer Wahrscheinlichkeit für die Wahl eines Terminalsym-
bols arbeiten. Basierend darauf existieren drei verschiedene Methoden, um eine GP-
Population zu initialisieren [Koza 1992]:
wachsen
(engl.
grow
),
voll
(engl.
full
)und
aufsteigend halb-und-halb
(engl.
ramped half-and-half
). Wie bei einem Standard-EA kön-
nen wir auch hier Kopien vermeiden. Anschließend führen wir die drei Methoden
anhand ihres Pseudocodes ein. Der initiale Aufruf zur Generierung einer Anfangs-
population mittels
wachsen
und
voll
sei I
NITIALISIERE
(Wurzel, 0).
Die Methode
wachsen
erzeugt Bäume von irregulärer Form. In jedem Knoten (bis
auf dieWurzel) treffenwir eine zufällige Auswahl aus
F
und
T
.EinZweigmiteinem
Te rmi na l symbo l kann a l so auch vor dem Er re i chen von
d
max
enden. Der Pseudocode
dieser Methode ist in Algorithmus 15 gelistet.
