Information Technology Reference
In-Depth Information
Mutationen einzelner Gene führen zu ähnlichen Genotypen. Das bedeutet, dass
einzelne Alleländerungen zu einer kleinen Änderung des Chromosoms führen. Stel-
len wir ähnliche Phänotypen nicht durch ähnliche Genotypen dar, können nahelie-
gende Verbesserungen u. U. nicht erzeugt werden. Es wäre dann eine große Ände-
rung des Genotyps erforderlich, um zu einem ähnlichen (und vielleicht besseren)
Phänotyp zu gelangen.
Dies verdeutlichen wir anhand eines einfachen Beispiels wie folgt. Nehmen wir
an, dass eine
n
-stellig reellwertige Funktion
y
=
f
(
x
1
,...,
x
n
)
optimiert werden soll.
Die reellwertigen Argumente sollen durch Binär-Kodes dargestellt werden. Das Pro-
blem hierbei ist, dass eine einfache Kodierung einer Zahl als Binärzahl zu sogenann-
ten
Hamming-Klippen
führt.
Dafür erwähnen wir kurz, wie eine Binärkodierung reeller Zahlen berechnet wer-
den kann. Gegeben ein reelles Intervall
[
a
,
b
]
und eine Kodierungsgenauigkeit
.Ge-
sucht ist eine Kodierungsvorschrift für die Zahlen
x
[
a
,
b
]
als Binärzahl
z
,sodass
die kodierte Zahl
z
um weniger als
von ihrem tatsächlichen Wert
x
abweicht. Die
Idee hierbei ist, das Intervall
[
a
,
b
]
in gleich große Abschnitte der Länge
einzu-
teilen. Somit entstehen 2
k
Abschnitte mit
k
=
log
2
b
a
kodiert durch die Zahlen
x
a
0, . . . , 2
k
1. Die Kodierung ergibt sich somit aus
z
=
b
a
(
2
k
1
)
oder alternativ
x
a
b
a
(
2
k
1
)+
1
/
2
aus
z
=
.BeiletztererKodierungsvorschriftreichenunsdannal-
log
2
b
a
b
a
lerings
k
=
2
k
1
.
Dies erklären wir nun an einem Zahlenbeispiel. Angenommen wir sollen im Inter-
vall
Abschnitte. Die Dekodierung erfolgt durch
x
=
a
+
z
·
2
von 10
6
die Zahl
x
= 0.637197 kodieren. So
[1, 2] mit einer Genauigkeit
ergeben sich
k
und
z
wie folgt.
2 (1)
10
6
log
2
3
·
10
6
k
=
log
2
=
=
22
0.637197 (1)
2
(
1
)
(
2
22
1
)
z
=
=
2288966
10
=
1000101110110101000110
2
Das Problem was dabei zu Tage kommt, ist, dass benachbarte Zahlen sehr ver-
schieden kodiert sein können. Das bedeutet, dass die Kodierungen einen großen
Hamming-Abstand (Anzahl verschiedener Bits) haben. Große Hamming-Abstände,
die sogenannten „Hamming-Klippen“, können durch Mutationen und Crossover
nur sehr schwer überwunden werden.
Als erklärendes Beispiel dieses Problems betrachten wir den Bereich der Zahlen
von 0 bis 1 durch 4-Bit-Zahlen. D. h. wir nutzen die Abbildung der reellen Zahl
k
/
15
auf
k
.DannhabendieKodierungenvon
7
/
15
(also 0111) und
8
/
15
(lies 1000) den
Hamming-Abstand 4, denn jedes Bit ist verschieden. Also, obwohl die phänotypi-
sche Änderung zwischen beiden Zahlen sehr klein ist, ist die genotypische Ände-
rung maximal.
Eine Lösung dieses Problems ist die Einführung von
Gray-Kodes
,d.h.benachbar-
te Zahlen unterscheiden sich nur in einem Bit. Für 4-Bit-Zahlen zeigen wir einen
Gray-Kode in Tabelle 11.1.
