Information Technology Reference
In-Depth Information
satz von Holland [1975]. Es werden dabei nur sogenannte Schemata von binären
Chromosomen (d. h. nur teilweise festgelegte Chromosomen) betrachtet und unter-
sucht, wie sich die Zahl der Chromosomen, die zu einem Schema passen, über die
Generationen hinweg entwickelt. Das Ziel ist, eine zumindest grobe stochastische
Aussage darüber zu treffen, wie ein GA den Suchraum erforscht. Zur Vereinfachung
der Darstellung beschränkte sich Holland auf Bitfolgen (Chromosomen aus Nullen
und Einsen) mit fester Länge
L
.DesWeiterengehenwirdavonaus,dassChro-
mosomen durch die fitnessproportionale Selektion (lies Glücksradauswahl wie im
Abschnitt 11.2.1 eingeführt) in die Zwischenpopulation gelangen. Als gentischen
Operatoren für Variation und Rekombination wählen wir Binär-Mutation (siehe Ab-
schnitt 11.3.1) und Ein-Punkt-Crossover (siehe Abschnitt 11.3.2). Der verwendete
Algorithmus zur Untersuchung der Evolution gewisser Schemata entspricht dem
Standard-GA in Algorithmus 6.
Zu allererst müssen wir klären, was wir unter einem Schema verstehen und wie
ein Schema zu einem Chromosom passt.
Definition 12.1 (Schema)
Ein
Schema
histeineZeichenkettederLängeLüberdemAl-
phabet
{0, 1, }
,d.h.h
{0, 1, }
L
.DasZeichen
heißt
Jokerzeichen
oder
Don't-Care-
Symbol
.
Definition 12.2 (Passung)
Ein Chromosom c
{0, 1}
L
passt zu einem Schema
h
{0, 1, }
L
,inZeichenc
h, wenn es mit h an allen Stellen übereinstimmt, an denen h eine 0
oder eine 1 enthält. Stellen, an denen ein
steht, bleiben unberücksichtigt.
Ein kleines Beispiel soll zur Erklärung der Begriffe beitragen. Es seien
h
ein Sche-
ma der Länge
L
= 10 und
c
1
,
c
2
zwei verschiedene Chromosomen der gleichen Län-
ge:
h
=
**
0
*
11
*
10
*
c
1
=
1100111100
c
2
=
1111111111
Man sieht leicht, dass
c
1
zu
h
passt, also
c
1
h
,während
c
2
nicht zu
h
passt, also
c
2
h
.
Generell gibt es 2
L
mögliche Chromosomen und 3
L
verschiedene Schemata. Jedes
Chromosom passt zu
i
=0
(
i
) =
2
L
Schemata. Eine Population der Größe
µ
kann bis
zu
µ
2
L
verschiedene Schemata besitzen. Normalerweise sind es allerdings viel weni-
ger aufgrund von ähnlichen Chromosomen, die sich über die Zeit durch den steigen-
den Selektionsdruck aufbauen (vergleiche Abschnitt 11.2). Holland [1975] glaubte,
dass die Betrachtung eines Chromosoms der gleichzeitigen Betrachtung vieler Sche-
mata gleichkommt. Er nannte dies einen
impliziten Parallelismus
.
Geometrisch betrachtet beschreibt jedes Schema eine Hyperebene in einem Hy-
per-Einheitswürfel. Allerdings sind durch Schemata nur Ebenen beschrieben, die
parallel oder senkrecht zu den Achsen stehen. Dies ist beispielhaft in Abbildung
12.1 dargestellt. In diesem Beispiel beschreibt das Schema
*
00
die Kante von
000
nach
100
(vorne unten). Der linke Würfel wird durch das Schema
0
**
dargestellt.
Das
***
, was nur aus Jokerzeichen besteht, beschreibt den gesamten Würfel.
Eine weitere Repräsentation von Schemata ist die Betrachtung gewisser Wertebe-
reiche von Funktionen. Sei eine reelle Funktion
f
:
[
0, 1
]
IR g e g e b e n , w o b e i d i e
