Information Technology Reference
In-Depth Information
Die durchschnittliche Anzahl Nachkommen eines zu einem Schema
h
passenden
Chromosoms ist
f
rel
(
h
) ·|
pop
|
.DiezuerwartendeZahlChromosomen,dienachder
Auswahl zu einem Schema
h
passen, ist daher
(
ZahlvorherpassenderChromosomen
) ·
f
rel
(
h
) ·|
pop
|
.
Wir müssen nun weitere Betrachtungen zur relativen Fitness eines Schemas an-
stellen, um den Einfluss der Selektion messbar zu machen:
s
pop(
t
),
s
h
f
rel
(
s
)
|{
s
pop(
t
) |
s
h
}|
·|pop|
f
rel
(
h
) ·|pop| =
s
pop(
t
),
s
h
f
(
s
)
s
pop(
t
)
f
(
s
)
|{
s
pop(
t
) |
s
h
}|
=
·|pop|
s
pop(
t
),
s
h
f
(
s
)
|{
s
pop(
t
)|
s
h
}|
s
pop(
t
)
f
t
(
h
)
f
t
=
=
f
(
s
)
|
pop
|
wobei
f
t
(
h
) die mittlere Fitness der in der
t
-ten Generation zum Schema
h
passenden
Chromosomen und
f
t
die mittlere Fitness aller Chromosomen der
t
-ten Generation
sind. Die mittlere Anzahl Nachkommen kann so durch das Verhältnis der mittleren
Güte eines Schemas zur Gesamtdurchschnittsgüte ausgedrückt werden.
Für die genetischen Operatoren brauchen wir Maße, mit denen wir für ein Sche-
ma die Wahrscheinlichkeit angeben können, dass durch Anwendung eines Opera-
tors die Passung zu diesem Schema verloren geht bzw. erhalten bleibt. Um den Ein-
fluss der Mutation zu untersuchen, definieren wir daher das Maß der Ordnung:
Definition 12.4 (Ordnung (für 1-Bit- und Binär-Mutation))
Die
Ordnung ord
eines
Schemas h ist die Anzahl der Nullen und Einsen in h, also
ord
(
h
)=
#0
+
#1
=
L
#
wobei der Operator
#
die Anzahl des Auftretens ist.
So ist z. B. ord
(
**
0
*
11
*
10
*
)=
5. Somit geht die Passung zu einem Schema durch
die Binär-Mutation mit Wahrscheinlichkeit (1
p
m
)
ord(
h
)
nicht
verloren. Der Grund
dafür ist, dass jedes Bit wird mit Wahrscheinlichkeit
p
m
und mit Wahrscheinlich-
keit (1
p
m
) nicht invertiert wird. Sollte man die 1-Bit-Mutation als Variationsope-
rator benutzen, dann geht die Passung zu einem Schema
nicht
verloren mit Wahr-
scheinlichkeit 1
ord(
h
)
L
,fallsdasBitumgekehrtwird,bzw.mitWahrscheinlichkeit
1
ord
(
h
)
2
L
,fallsdasneueBitzufälligbestimmtwird.Dasliegtdaran,dassjedesder
L
Gene eines Chromosoms der Länge
L
mit gleicher Wahrscheinlichkeit für eine Muta-
tion ausgewählt wird.
Den Einfluss des Crossover untersuchen wir durch das Maß der definierenden
Länge:
Definition 12.5 (Definierende Länge (für 1-Punkt-Crossover))
Das Maß der
definie-
renden Länge dl
eines Schemas h ist die Differenz zwischen der Positionsnummer der letz-
ten
0/1
und der Positionsnummer der ersten
0/1
in h.
