Information Technology Reference
In-Depth Information
12.3.3 Vergleich von Plus- und Komma-Strategie
Abschließend wollen wir die beiden Selektionsprinzipien miteinander vergleichen,
lies die
+
-Strategie und die ,-Strategie. Offensichtlich können wir ganz klar einen
Vo r t e i l de r
+
-gegenüberder,-Strategieherausstellen:Estreten,wegendesstrengen
Eliteprinzips, nur Verbesserungen auf. Die Nachteile der
+
-Strategie sind allerdings
nicht zu unterschätzen. Auch hier besteht die Gefahr des Hängenbleibens in lokalen
Minima. Für eine
(
µ
+
)
-Evolutionsstrategie mit
µ
/
„beste Wahrscheinlichkeit
für eine erfolgreiche Mutation“
(
1
/
5
)
haben die Chromosomen einen Selektions-
vorteil, die ihre Varianz
2
möglichst klein halten, da nicht genügend große Mutatio-
nen durchgeführt werden, um eine „echte“ Verbesserung zu erreichen. Dies kommt
einer „Beinahe-Stagnation“ gleich. Die übliche Wahl des Verhältnisses von
µ
und
ist in etwa 1:7. Wenn über mehrere Generationen keine Verbesserungen aufgetreten
sind, wird oft von der +-Strategie vorübergehend auf die ,-Strategie umgeschaltet,
um die Diversität in der Population wieder zu erhöhen.
12.4 Genetische Programmierung
Genetische Programmierung (GP) basiert auf der Idee, eine Problemlösung durch
ein Computerprogramm zu beschreiben, das gewisse Eingaben mit gewissen Ausga-
ben verbindet. Wir müssen also nach einem passenden Computerprogramm suchen.
Viele verschiedene Probleme können als Suche nach einem Programms interpretiert
werden: z. B. Regelung, Planen, Suchen, Wissensrepräsentation, symbolische Regres-
sion, Induktion von Entscheidungsbäumen [Nilsson 1998]. GP ist einen genereller
Weg , Comput e rprogr amme zu l e rnen bzw. zu e r zeugen .
Während wir die bisherigen Lösungskandidaten durch Chromosomen mit einer
festen Länge (also einem Vektor von Genen) beschrieben haben, werden wir nun
Funktionsausdrücke bzw. Programme betrachten. Ein
genetisches Programm
(eben-
falls durch „GP“ abgekürzt) ist ein komplexeres Chromosom variabler Länge. Die
formale Grundlage ist eine Grammatik zur Beschreibung der Sprache eines GP. Da-
für legen wir zwei Mengen fest:
F
die Menge der
Funktionssymbole und Operatoren
und
T
die Menge der
Te rmi na l s ymb o l e
(Konstanten und Variablen). Diese Mengen
F
und
T
sind problemspezifisch und demnach mit der Kodierung von Standard-
Chromosomen vergleichbar (siehe Abschnitt 11.1).
F
und
T
sollten nicht zu groß
sein, um den Suchraum zu beschränken. Und dennoch sollten sie „reichhaltig“ ge-
nug sein, um eine Problemlösung zu ermöglichen.
Zur Anschauung geben wir zwei Beispiele verschiedener Symbolmengen an. Sol-
len wir z. B. Boolesche Funktion erlernen, so bieten sich die folgenden Symbolmen-
gen an:
F = {
and, or, not, if . . .then . . .else . . ., . . .
}
,
T = {
x
1
,...,
x
m
,1,0
}
bzw.
T = {
x
1
,...,
x
m
,
t
,
f
}
.
