Information Technology Reference
In-Depth Information
Für eine symbolische Regression
1
können wir folgende Mengen nutzen:
F = {+, , ,/,
,sin,cos,log,exp,...},
T = {
x
1
,...,
x
m
}
IR .
Eine wünschenswerte Eigenschaft von
F
und
T
ist deren Abgeschlossenheit.
D. h., Funktionen aus
F
sollten alle möglichen Eingabewerte akzeptieren. Z. B. bei
einer Division durch Null würde die Ausführung eines GP mit einem Fehler been-
det werden. Solch ein Verhalten ist unerwünscht, da zur Laufzeit keinerlei Fehler in
einem GP auftreten sollten. Falls die Abgeschlossenheit der Mengen nicht gilt, dann
würden wir ein Optimierungsproblem mit Nebenbedingungen lösen müssen. Wie
wir bereits erwähnt haben, wären in diesem Fall Reparaturmechanismen oder die
Einführung eines Strafterms nötig (vergleiche Abschnitt 11.1.3). Es gibt verschiedene
Strategien, die eine Abgeschlossenheit garantieren. Einerseits können wir gesicherte
Ve r s i onen von an f ä l l i gen Ope r a t o r en imp l emen t i e r en , wi e z . B . e i ne ge s i c he r t e Di v i -
sion, die Null oder den Maximalwert zurückgibt, oder eine gesicherte Wurzelfunk-
tion, die mit dem Absolutwert operiert. Eine gesicherte Logarithmusfunktion wäre
z. B.
x
0: log
(
x
)=
0. Andererseits können wir auch verschiedene Funkti-
onsarten kombinieren, um Abgeschlossenheit zu gewährleisten. Dies sehen wir am
einfachsten bei numerischen und Booleschen Werten:
false
=
0,
true
=
0. So können
wir u. U. einen bedingten Vergleichsoperator implementieren:
if x
<
0
then
....
Eine weitere wichtige Eigenschaft ist die Vollständigkeit der Symbolmengen
F
und
T
.EinGPkannnureffizientundeffektiveinProblemlösen,wenn
F
und
T
hinreichend bzw. vollständig sind, um ein angemessenes Programm zu finden.
Beispielsweise sind in der Booleschen Aussagenlogik
F = {
,
¬}
und
F = {
,
¬}
vollständige Operatormengen,
F = {}
allerdings nicht. Dieses generelle Pro-
blem taucht im Bereich des
maschinellen Lernens
unter dem Namen
Merkmalsauswahl
(engl.
feature selection
)aufundistbisheuteungelöst.DasFindenderkleinstenvoll-
ständigen Menge ist (meistens) NP-schwer. D. h. für gewöhnlich, dass
F
mehr Funk-
tionen enthält als eigentlich notwendig sind.
Anhand der Symbolmengen definieren wir über die gegebene Grammatik Chro-
mosomen als GP. Chromosomen sind Ausdrücke, die sich zusammensetzen aus Ele-
menten aus C = FT und gegebenenfalls schließenden und öffnenden Klammern.
Allerdings beschränken wir uns nur auf „wohlgeformte“ Ausdrücke. Es ist üblich,
dass man Chromosomen anhand einer
rekursiven Definition
durch eine Präfixnotati-
on darstellt. Diese lautet wie folgt:
• Konstanten- und Variablensymbole sind symbolische Ausdrücke.
• Sind
t
1
,...,
t
n
symbolische Ausdrücke und ist
f
F
ein (
n
-stelliges) Funkti-
onssymbol, so ist
(
ft
1
...
t
n
)
ein symbolischer Ausdruck.
• Keine anderen Zeichenfolgen sind symbolische Ausdrücke.
So ist z. B. „
(+ (
3
x
)(
/82
))
“einsymbolischerAusdruck,derunsaneineLisp-
bzw. Scheme-artige Schreibweise erinnert und 3
·
x
+
8
/
2
bedeutet. Hingegen ist
„2 7
(
3/“keinsymbolischerAusdruck.
1
Eine Regression ist die Bestimmung einer Ausgleichsfunktion zu gegebenen Daten unter der Mini-
mierung der Fehlerquadratsumme —
Methode der kleinsten Quadrate
.
