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

Viertens besitzt jede Ecke nur eine eingehende Kante, aber beliebig viele ausgehende Kanten
(Verzweigungen).
Der Digraph wird repräsentiert durch die Adjazenzmatrix, die aufgrund der genannten Bedin-
gungen einige spezielle Eigenschaften hat. Dies sei an dem Beispiel eines Netzes mit 5 Knoten
erläutert.
A 1 und A 2 stellen 2 verschiedene Strukturen des Netzes dar.

§ · § ·

01010
00100
00000
00001
00000

01010
00001
00000
00100
00000

¨
¨
¨
¨ ¨

¸
¸
¸
¸ ¸

¨
¨
¨
¨ ¨

¸
¸
¸
¸

A 1 A 2

© ¹ © ¹

Bild 3-5 Verschiedene Adjazenzmatrizen und dazugehörige Netzstrukturen

Für die Adjazenzmatrizen gelten die Bedingungen:
1. ein Element a ij = 1 ist zu lesen als: „von Ecke i geht eine Kante aus zur Ecke j“;

2. es gibt keine Schleifen, a ii = 0;

3. die Spalte j gibt die Anzahl der eingehenden Kanten;

4. die 1. Spalte enthält nur 0, da die Ecke 1 als Ausgangspunkt (Quelle) definiert ist;

5. jede weitere Spalte enthält nur eine 1, d. h., der Innengrad der Ecken 2 bis n ist stets 1;

6. die Zeilensumme (Außengrad) gibt an, wie viele Zweige von der jeweiligen Ecke aus-

gehen;

7. Zeilensumme 0 bedeutet, dass die betreffende Ecke eine Endecke (Senke) des Netzes ist.

Die Adjazenzmatrizen werden vom GA direkt als Genvektoren verwendet; die Genvektoren
sind hier also zweidimensional, was bestimmte Konsequenzen für die Art der vom GA verwen-
deten Variationen hat. Diese Zweidimensionalität ist jedoch nicht zu verwechseln mit der
Zweidimensionalität der RGA-Systeme. 14 Der GA basiert wie üblich auf zwei Operationen,
Crossover und Mutation.
Crossover geschieht in diesem Beispiel durch zufallsgesteuerten Austausch von Spalten zweier
Genvektoren/Adjazenzmatrizen. Im Beispiel der obigen Matrizen könnte das Crossover zwi-
schen A 1 und A 2 etwa den Austausch der (zufällig gewählten) Spalte 2 von A 1 mit der Spalte 5
von A 2 bedeuten. Damit entstünden 2 neue Genvektoren/Matrizen:

14 Eine vorteilhafte alternative Codierung ist hier möglich, weil jede Spalte der Matrix maximal eine
Eins und sonst Null enthält. Man kann die Matrix deswegen zu einem Vektor komprimieren, der als
Elemente die Position, also den ersten Index i der Matrix (a ij ) enthält; der Index j ist als Position des
Elements repräsentiert. Die Matrix A 1 wird damit beispielsweise als (0,1,2,1,4) dargestellt. Durch die
Darstellung als Vektor anstelle einer zweidimensionalen Matrix können die Algorithmen des Cross-
over sowie der Mutation in manchen Programmiersprachen erheblich beschleunigt werden.