Information Technology Reference
In-Depth Information
Im letzten Schritt
()
haben wir die vorher abgeleiteten Beziehung
N
(
h
,
t
+
t
s
)=
N
(
h
,
t
) ·
f
rel
(
h
) ·|
pop
|
zweimal verwendet.
Die Auswirkungen der Mutation beschreiben wir durch die Ordnung:
N
(
h
,
t
+ 1)=
N
(
h
,
t
+
t
s
+
t
x
+
t
m
)
=
N
(
h
,
t
+
t
s
+
t
x
) · (
1
p
m
)
ord(
h
)
.
Hierbei erwähnen wir noch einmal, dass
p
m
die Mutationswahrscheinlichkeit für je-
des Bit ist, d. h. jedes Bit wird mit Wahrscheinlichkeit
p
m
mutiert (umgedreht) und
mit Wahrscheinlichkeit (1
p
m
) unverändert gelassen. Damit also die Passung nicht
verlorengeht, dürfen wir keines der ord(
h
) Gene verändern, die im Schema
h
festge-
legt sind. An dieser Stelle sind alternative Modelle möglich, z. B. könnte jedes Chro-
mosom genau einer Bitmutation unterworfen werden, was der 1-Bit-Mutation ent-
spricht. Demnach könnten wir die Auswirkungen der Mutation beschreiben durch:
N
(
h
,
t
+
1
)=
N
(
h
,
t
+
t
s
+
t
x
+
t
m
)
1
ord(
h
)
L
=
N
(
h
,
t
+
t
s
+
t
x
) ·
,
wobei
ord
(
h
)
/
L
die Wahrscheinlichkeit ist, dass durch eine 1-Bit-Mutation ein in
h
fest-
gelegtes Gen verändert wird. Dies entspricht einer gleichwahrscheinlichen Auswahl
des Bits.
Schlussendlich können wir (hier mit der Binär-Mutation)
N
(
h
,
t
+
1
)
approximie-
ren durch
dl(
h
)
L
1
N
(
h
,
t
+ 1)
f
rel
(
h
) ·|pop|·
1
p
x
· (1
N
(
h
,
t
) ·
f
rel
(
h
))
· (
1
p
m
)
ord(
h
)
·
N
(
h
,
t
)
.
Ein Einsetzen des Fitnessverhältnisses liefert das sogenannte
Schematheorem
:
N
(
h
,
t
+ 1)
f
t
(
h
)
f
t
dl
(
h
)
L
1
1
N
(
h
,
t
)
|
pop
|
·
f
t
(
h
)
f
t
1
p
x
· (
1
p
m
)
ord(
h
)
·
N
(
h
,
t
)
.
Die Interpretation dieses Theorems ist, dass Schemata mit überdurchschnittlicher
mittlerer Bewertung, kurzer definierender Länge und geringer Ordnung vermehren
sich besonders stark (etwa exponentiell). Die Implikationen des Schematheorems
lassen sich für einige weitere Argumentationen benutzen. Diese sind die sogenannte
Baustein-Hypothese, die Analogie des zweiarmigen Banditen sowie das Prinzip der
kleinsten Alphabete.
Das Schematheorem besagt, dass der Suchraum besonders gut in Hyperebenen
(Regionen) durchsucht wird, die Schemata mit hoher mittlerer Fitness, kleiner defi-
nierender Länge und geringer Ordnung entsprechen. Der Grund dafür ist, dass in
diesen Regionen sich die Chromosomen am stärksten vermehren. Solche Schema-
ta heißen
Bausteine
(engl.
building blocks
). Die obige Aussage heißt daher auch
Bau-
stein-Hypothese
.Hierbeimussmanbeachten,dassdieobigeFormderBaustein-Hy-
pothese nur für Bitfolgen, fitnessproportionale Selektion, Binär-Mutation und Ein-
Punkt-Crossover gilt. Verwendet man z. B. anderer genetischer Operatoren werden
