Die Modellierung adaptiver Prozesse durch Evolutionäre Algorithmen - Modellierung komplexer Prozesse durch naturanaloge Verfahren - page 95

§ · § ·

00010
01100
00000
00001
00000

01011
00000
00000
00100
00000

¨
¨
¨
¨ ¨

¸
¸
¸
¸ ¸

¨
¨
¨
¨ ¨

¸
¸
¸
¸

A 1 A 2

© ¹ © ¹

Bild 3-6 Neue Adjazenzmatrizen und dazugehörige Netzstrukturen

Wie man sofort sieht, ist A 2 ' ein Digraph, der den genannten Bedingungen für das Netz genügt,
A 1 ' enthält jedoch ein Schleife a 22 , ist also ein „unzulässiger“ Digraph.
Grundsätzlich gibt es zwei Möglichkeiten, in einem GA-Programm mit einem derartigen Fall
umzugehen:
1. Man kann den „unzulässigen“ Digraphen/Genvektor verwerfen und das Crossover so lan-
ge wiederholen, bis ein zulässiger Genvektor erzeugt wird. Das hat den Nachteil, dass die
Anzahl der Wiederholungen nicht determiniert ist, dass sogar in „pathologischen“ Fällen
überhaupt kein zulässiger Genvektor durch den Crossover Algorithmus möglich ist.
2. Man führt geeignete Korrekturen für den „unzulässigen“ Genvektor ein. Dieser Weg wird
im vorliegenden Beispielprogramm beschritten. Die Korrekturen werden weiter unten,
nach der Erörterung der Mutation, genauer erläutert.
Das Crossover kann im Programm nun nicht nur durch Vertauschen eines Paares von Spalten,
sondern auch durch Vertauschen weiterer Paare geschehen; hierdurch erhält man einen Para-
meter, der gewissermaßen die „Stärke“ des Crossover reguliert.
Die Mutation geschieht im Programm einfach dadurch, dass per Zufall eine oder mehr der
Spalten 2 bis n (Spalte 1 darf nur Nullen enthalten, da Knoten 1 als Quelle definiert war) des
Genvektors ausgewählt werden; in diesen Spalten wird die vorhandene 1 (zur Erinnerung: in
zulässigen Genvektoren gibt es nur eine 1 in diesen Spalten) gelöscht und stattdessen an einer
anderen, zufälligen Position eine 0 durch 1 substituiert. Der Umfang der Mutation, also die
Anzahl der zu mutierenden Genvektoren und Spalten kann wiederum durch Parameter ein-
gestellt werden. Selbstverständlich sind auch die mutierten Genvektoren auf Zulässigkeit zu
prüfen und ggf. zu korrigieren.
Die Korrekturen unzulässiger Genvektoren, die im Programm vorgenommen werden, sind die
folgenden:
x Wenn ein Diagonalelement a ii = 1 ist, wird diese 0 gesetzt und eine 1 an eine zufällige

Position derselben Spalte eingesetzt.

x Wenn Knoten 1 keine Verbindung besitzt, also a 1j = 0 für alle j, dann wird in der 1. Zeile

an zufälliger Position k eine 1 eingesetzt; sofern in der k-ten Spalte noch keine 1 enthalten
ist.

x Bei doppelten Kanten, d. h., wenn a ij und a ji = 1, wird nach Zufall eine der Kanten ge-

löscht und dafür eine andere Kante, d. h. eine 1 in einer anderen Spalte, eingefügt.