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

x Schließlich wird geprüft, ob alle Knoten vom Knoten 1 aus erreichbar sind. Dazu ist die

Erreichbarkeitsmatrix R zu bestimmen. Die Erreichbarkeitsmatrix ist die Matrix, die durch
Addition aller Potenzen von der ersten bis zur n-ten der Adjazenzmatrix gebildet wird. Da
eine k-te Potenz der Adjazenzmatrix durch ein Element x ij > 0 anzeigt, dass ein Weg zwi-
schen den Knoten i und j mit der Anzahl k der zu passierenden Kanten (Weglänge) exis-
tiert, gibt die Erreichbarkeitsmatrix demzufolge an, zwischen welchen Knoten überhaupt
eine Verbindung irgendeiner Länge vorliegt. Bei unserem Beispiel mit maximal (n-1)
Kanten und Baumstruktur genügt es, bis zur Potenz (n-1) zu addieren und festzustellen, ob
alle Knoten Verbindung mit dem Anfangsknoten 1 haben; in dem Falle darf also die erste
Zeile der Erreichbarkeitsmatrix - außer dem Element R 11 , der Verbindung von Knoten 1
mit sich selbst - keine weitere Null enthalten.

n1
¦

A k R

(3.16)

k 1

Da bei dem Beispielproblem die Richtung der Kanten keine Rolle spielt, mathematisch formu-
liert also ein schwach zusammenhängender Digraph die Bedingungen der Netzkonstruktion
erfüllt, wird die Adjazenzmatrix vor der Berechnung von R symmetrisiert, d. h., für jedes a ij =
1 wird auch a ji =1 gesetzt.
Wenn in der ersten Zeile der entstehenden Matrix R an der Position j eine Null steht, dann ist
der Knoten j nicht vom Knoten 1 aus erreichbar. Im Beispielprogramm wird dies einfach da-
durch korrigiert, dass eine Verbindung vom Knoten 1 zum Knoten j hinzugefügt wird; dafür
wird eine etwa vorhandene andere Verbindung zum Knoten j gelöscht.
Das Beispielprogramm arbeitet mit einem Netz von 12 Knoten. Die Population der Genvekto-
ren besteht aus 20 jeweils 12-dimensionalen Adjazenzmatrizen, von denen die jeweils 10 am
besten bewerteten nach einem festgelegten Rekombinationsschema („Heiratsschema“) neu
kombiniert werden; dies Schema entspricht im Wesentlichen dem oben dargestellten Standard-
schema. Die Bewertung („Fitness-Werte“) besteht wie bemerkt in der Berechnung bzw. Mini-
mierung der Summe der Distanzen zwischen den verknüpften Knoten.
Die Beispielrechnungen haben ergeben, dass nur eine elitistische Variante des GA zu hin-
reichend schneller und guter Optimierung führt. Auch dann sind Schrittzahlen von 10.000 bis
20.000 für eine hinreichende Optimierung erforderlich. 15
Die Optimierungsgeschwindigkeit hängt allerdings sehr stark von der Wahl der GA-Parameter
ab wie Stärke des Crossover und der Mutation, vom Rekombinationsschema, sogar von der
Reihenfolge der eingegebenen Koordinaten der Knoten und von der Wahl der Startwerte
(seeds) der im Programm aufgerufenen Zufallsgeneratoren.

15 Das ist allerdings bei einer Anzahl von größenordnungsmäßig 11 11 möglichen Netzstrukturen
vertretbar.