Information Technology Reference
In-Depth Information
in den Vektoren der Nachkommen einzelne Komponenten vertauscht. In einem Vektor der
Form (1,0,0,1,0) würde die Inversion der ersten und der letzten Komponente demnach den
Vektor (0,0,0,1,1) erzeugen, was allerdings bei diesem einfachen Bewertungsverfahren offen-
sichtlich nichts bewirkt. Man kann die Inversion auch mit mehreren zusammenhängenden
Komponenten, so genannten Blöcken (Building Blocks), gleichzeitig durchführen, z. B. im
obigen Beispiel die Komponenten (1, 2) mit den Komponenten (3, 4); wir haben auf das Prin-
zip der Building Blocks bereits oben verwiesen. Dann wird die Inversion offenbar ein „inne-
res“ Crossover, also eines, das nicht zwischen zwei Vektoren, sondern innerhalb eines Vektors,
durchgeführt wird. Für den Fall, dass die Blöcke jeweils nur aus einem Element bestehen, kann
man die Inversion auch als 1-elementiges Crossover auffassen. Das ist dann lediglich eine
Frage der Semantik.
Gemäß der obigen Unterscheidung zwischen deterministischen und stochastischen Optimie-
rungsverfahren lässt sich der GA als ein „semistochastisches“ Verfahren charakterisieren: Er
enthält stochastische Elemente wie die Mutation und die Zufallsgenerierung der Anfangs-
population; auch das Crossoverschema kann stochastisch durchgeführt werden, indem die
Vektorkomponenten, die zur Rekombination verwendet werden, aus den Elternvektoren per
Zufall ausgewählt werden. Dies wird sogar ziemlich häufig benutzt. Gleichzeitig jedoch führt
die Bewertung deterministische Elemente ein, die auch von statistischen Gleichverteilungen
weit entfernt sind: Es werden gewöhnlich nur die jeweils besten zur Rekombination heran-
gezogen und die verschiedenen Schritte des Pseudocodes werden immer streng reproduziert.
Der GA lässt sich demnach als ein rekursiver Algorithmus mit stochastischen Elementen ver-
stehen und das macht auch seine immer wieder demonstrierte Effektivität aus. 2
Aus dem obigen Pseudocode und dem Beispiel geht hervor, dass man mit dem bisher darge-
stellten GA streng genommen ein Algorithmusschema hat, das im konkreten Fall durch Angabe
des jeweiligen Heiratsschemas, des speziellen Crossoververfahrens, der Codierung,Mutations-
rate, Abbruchbedingungen und vor allem der Bewertungsfunktion erst zu einem praktikablen
Algorithmus gemacht wird. Welche jeweiligen Möglichkeiten man wählt, hängt von dem Prob-
lem ab, das mit einem GA gelöst werden soll. Man sieht daran, dass es „den“ GA nur im Sinne
eines Schemas gibt; gleichzeitig erweist sich dies Schema jedoch auch als äußerst variabel, das
den verschiedensten Zwecken angepasst werden kann. Es gibt dabei zahlreiche Faustregeln, die
sich praktisch bewährt haben (unter anderen Schöneburg u. a. 1994; Michalewicz 1994): So
sollte die Anzahl der Vektorkomponenten, die beim Crossover eingesetzt werden, höchsten
50 % der Gesamtkomponenten betragen, da sonst, wie man rasch einsieht, ständig Redundan-
zen produziert werden, d. h., das Crossover verändert die Vektoren nicht wesentlich. Entspre-
chend gilt, dass Mutationsraten gering gehalten werden sollten, wenn es nur darum geht, über-
haupt praktikable Lösungen zu finden, wenn also ggf. lokale Optima bzw. Suboptima im
Suchraum ausreichen. Die Produktivität des Zufalls, die oben angesprochen wurde, wirkt sich
praktisch oft störend aus; in dem kleinen obigen Beispiel etwa wäre es sinnvoller, auf Mutation
völlig zu verzichten.
Einige besonders wichtige Aspekte der GA-Konstruktion sollen noch gesondert angesprochen
werden:
(1) Ersetzungsschema: Der „Standard“-GA, der von Holland relativ streng nach dem Modell
der biologischen Evolution konstruiert worden war, hat kein „Gedächtnis“, d. h., die jeweilige
2
Unter rekursiven Algorithmen versteht man solche, die zur Erzeugung neuer „Elemente“ - z. B. be-
stimmte Werte oder Systemzustände - jeweils auf die in den vorangegangenen Schritten erzeugten
Elemente zurückgreift (daher „re“kursiv) und nach immer gleichen Verfahren daraus die neuen Ele-
mente generiert. ZA z. B. sind klassische Exempel für rekursive Algorithmen, wie wir gesehen haben.
Search WWH ::




Custom Search