Information Technology Reference
In-Depth Information
3 1425 4 6
3 1 6 2 5 4 6
Abbildung 11.9: Beispiel einer Standardmutation. Austausch der Ausprägung eines
Gens durch eine andere.
3 1425 4 6
3542146
Abbildung 11.10: Beispiel eines Zweiertauschs. Austausch der Ausprägungen zwei-
er Gene eines Chromosoms.
In Algorithmus 4 ist mit der
selbstadaptiven Gauß-Mutation
eine Erweiterung die-
ses Mutationsoperators gegeben. Hierbei wird für jedes reellwertige Chromosom
x
IR
L
eine Zusatzinformation
x
.
s
1
abgespeichert, die die chromosomenspezifi-
schen Varianz der Gauß-Mutation darstellt. Durch diese Erweiterung ist es möglich,
Chromosomen ganz unterschiedlich schnell bzw. langsam entwickeln zu lassen.
Algorithmus 4
Selbstadaptive Gauß-Mutation
Eingabe:
Individuum
x
mitG = IR
L
Ausgabe:
variiertes Individuum
x
mit
G =
IR
L
1:
u
wähle zufällig gemäß
N
(
0, 1
)
2:
x
.
s
[
1
]
x
.
s
[
1
] ·
exp
(
1
/
L
u
)
3:
for all
i
{
1, . . . ,
L
}
do
4:
u
wähle zufällig gemäß
N
(
0,
x
.
s
[
1
])
[
x
5:
]
i
[
x
]
i
+
u
i
[
x
]
i
max
{[
x
6:
]
i
,
ug
i
}
// u n t
e
r
e W e r
e b e r
e
c h s g r
e n z
e
ug
i
[
x
]
i
min
{[
x
7:
]
i
,
ug
i
}
// o b e
r
e W e r
t e b e r
e
c h s g r
e n z
e
og
i
8:
end for
9:
return
x
Bei der
Standardmutation
tauscht man die Ausprägung eines Gens durch eine an-
dere aus (siehe Abbildung 11.9. Gegebenenfalls werden mehrere Gene mutiert (ver-
gleiche das
n
-Damen-Problem im Abschnitt 10.3.1). Die Standardmutation besitzt
einen Parameter, die sogenannte Mutationswahrscheinlichkeit
p
m
mit 0
<
p
m
1.
Für Bitstrings ist
p
m
=
1
/
L
annähernd optimal wobei
L
die Länge des Chromosoms
darstellt.
Der
Zweiertausch
tauscht die Ausprägungen zweier Gene eines Chromosoms mit-
einander aus (siehe Abbildung 11.10). Die Voraussetzung dafür ist, dass die ausge-
tauschten Gene gleiche Allelmengen besitzen. Eine Verallgemeinerung des Zweier-
tauschs ist der zyklische Tausch von 3, 4, . . . ,
k
Genen.
Des Weiteren stellen wir nun kurz drei bekannte Variationsverfahren vor, die alle
auf Teilstücken operieren:
Ve r s c h i e b en
,
Mischen/Permutieren
und
Inversion (Umdrehen)
eines Teilstücks (siehe Abbildung 11.11). Alle diese Verfahren setzen voraus, dass
gleiche Allelmengen im betroffenen Bereich vorhanden sind. Gegebenenfalls kann
man eine Wahrscheinlichkeitsverteilung über Längen (und Verschiebungsweiten für
das Verschieben eines Teilstücks) nutzen.
