Information Technology Reference
In-Depth Information
12.3.1 Selektion
Die Selektion verfolgt ein strenges Eliteprinzip, denn nur die besten Individuen kom-
men in die nächste Generation. Mit
µ
bzw.
bezeichnen wir die Anzahl der Indivi-
duen in der Elterngeneration bzw. die Anzahl der (durchMutation) erzeugten Nach-
kommen. Es gibt zwei prinzipielle Selektionsstrategien, die
+
-Strategie und die ,-
Strategie. Bei der
+
-Strategie (Plus-Strategie,
(
µ
+
)
-Strategie) wählt man aus den
(
µ
+
)
Individuen der Elterngeneration und der erzeugten Nachkommen die be-
sten
µ
Chromosomen aus. Bei dieser Strategie gilt meist
<
µ
.Beider,-Strategie
(Komma-Strategie,
(
µ
,
)
-Strategie) erzeugt man
>
µ
Nachkommen, aus denen
man die besten
µ
Chromosomen auswählt. Die Chromosomen der Elterngeneration
gehen auf jeden Fall verloren.
Als Beispiel wollen wir den Spezialfall der
(
1
+
1
)
-Strategie analysieren. Die an-
fängliche „Population“
x
0
IR
n
ist ein zufällig erzeugter Vektor reeller Zahlen. Die
nächste Generation ergibt sich aus
x
t
=
x
t
+
r
t
,wobei
r
t
IR
n
ein neu initialisierter
reeller Zufallsvektor ist. Der Selektionsschritt setzt dann
x
t
, fas
f
(
x
t
)
f
(
x
)
,
x
t
+1
=
x
t
, .
Es werden weitere Generationen erzeugt bis ein Abbruchkriterium erfüllt ist. Dies
entspricht offenbar dem im Abschnittt 12.2.1 besprochenen Zufallsaufstieg. Die all-
gemeine +-Strategie können wir folglich als parallelen Zufallsaufstieg sehen, der
gleichzeitig an mehreren Orten des Suchraums durchgeführt wird, wobei wir stets
die erfolgversprechendsten
µ
Wege ve r f o l gen .
Zur Erinnerung aus Abschnitt 10.1.1 erwähnen wir die evolutionsstrategischen
Prinzipien: Optimiert werden nicht nur die Organismen, sondern auch die Mecha-
nismen der Evolution: Vermehrungs- und Sterberaten, Lebensdauern, Anfälligkeit
gegenüber Mutationen, Mutationsschrittweiten, Evolutionsgeschwindigkeit etc. Die
Evolutionsstrategien passen die Varianz des Zufallsvektors (die Mutationsschritt-
weite) an. Eine geringe Varianz bedeutet kleine Änderungen an den Chromosomen
und entspricht somit einer lokalen Suche (Ausbeutung). Eine hohe Varianz ist mit ei-
ner große Änderungen an den Chromosomen und demnach einer globalen Suche
(Erforschung, Exploration) gleichzusetzen. Weitere Möglichkeiten, Parameter des
Evolutionsprozesses anzupassen, sind die Wahl der Zahl der zu ändernden Gene
(Vektorelemente) oder die Wahl der Zahl
der zu erzeugenden Nachkommen.
Globale Varianzanpassung
Die globale Varianzanpassung arbeitet chromosomenunabhängig. Die Grundidee ist,
2
bzw.
so zu wählen, dass die mittlere Konvergenzrate möglichst hoch ist. Ein An-
satz von Rechenberg [1973] war, eine allgemeingültige Regel für verschiedene Funk-
tionen zur Varianzanpassung abzuleiten. Rechenberg [1973] bestimmte die optima-
le Varianz
für
f
1
(
x
1
,...,
x
n
)=
a
+
bx
1
und
f
2
(
x
1
,...,
x
n
)=
i
=1
x
i
,indemdie
Wahr s che i n l i chke i t en f ür e i ne e r f o l gre i che ( d . h . ve rbe s s e rnde ) Mut a t i on be s t immt
werden. Diese sind
p
1
0.184 für
f
1
und
p
2
0.270 für
f
2
.AusdiesemErgebnis
leitete Rechenberg [1973] heuristisch die
1
/
5
-Erfolgsregel ab: In der
+
-Strategie ist
die Mutationsschrittweite richtig, wenn etwa
1
/
5
der Nachkommen besser sind als
