Elemente evolutionärer Algorithmen - Computational Intelligence - page 165

binär Gray
0000

binär Gray
0100

binär Gray
1000

binär Gray
1100 0000 0110 1100 1010

0001 0001 0101 0111 1001 1101 1101 1011

0010 0011 0110 0101 1010 1111 1110 1001

0011 0010 0111 0100 1011 1110 1111 1000

Tabe l l e 11 . 1 : Gr ay-Kode für 4 -B i t -Zahl en

Man muss wissen, dass Gray-Kodes nicht eindeutig sind. Generell jeder Kode,
in dem sich die Kodierungen benachbarter Zahlen nur in einem Bit unterscheiden,
heißt Gray-Kode. Gray-Kodes werden meist aus einer Binärzahlkodierung berech-
net. Die häufigste Form der Kodierung bzw. Dekodierung ist

k 1

z
2

g
2 i

g = z bzw. z = ,

i =0

wobei das Exklusiv-Oder der Binärdarstellung sei.
Zur Verdeutlichung dieser Berechnungsvorschrift verweisen wir wieder auf das
bereits behandelte Beispiel. Im Intervall [ 1, 2 ] mit einer Genauigkeit von 10 6
sollen wir x = 0.637197 als Gray-Kode darstellen:

0.637197 ( 1 )
2 (1)

g = 1000101110110101000110 2
100010111011010100011 2
= 1100111001101111100101 2

(2 22 1)

z =

= 2288966 10
= 1000101110110101000110 2

11.1.2 Problem der Epistasie

Ähnlich kodierte Lösungskandidaten sollten eine ähnliche Fitness haben.
Diese Anforderung befasst sich mit dem Problem der Epistasie. In der Biologie
beschreibt die Epistasie das Phänomen, dass ein Allel eines Gens (des sogenannten
epistatischen Gens) die Wirkung aller möglichen Allele eines anderen Gens (oder
auch mehrerer anderer Gene) unterdrückt. In evolutionären Algorithmen beschreibt
sie die Wechselwirkung zwischen den Genen eines Chromosoms. Die Änderung der
Fitness durch die Änderung eines Gens hängt stark von den Ausprägungen der an-
deren Gene ab.
Die Epistasie erklärt in der Biologie z. B. Abweichungen der Mendelschen Ge-
setze. Werden beispielsweise reinerbige schwarz- und weißsamige Bohnen gekreuzt,
so werden in der zweiten Nachkommengeneration schwarz-, weiß und braunsami-
ge Bohnen im Verhältnis 12:1:3 gezüchtet, was den Mendelschen Gesetzen wider-
spricht.
Um die Epistasie bei evolutionären Algorithmen an einem Beispiel herauszustel-
len, ziehen wir das Problem des Handlungsreisenden in Betracht.