vorige nächste

die Mutation


Einige zufällig ausgewählte "Gene" werden an zufällig ausgewählten Stellen verändert. Beim tsp wird z.B. eine Stadt durch eine andere ersetzt.

Auch in diesem Prozeß sind zwei Schritte zu berücksichtigen :

  1. was ist im Modul inhaltlich zu realisieren?
  2. wie wird das Zufallsprinzip eingebaut?

Der zweite Schritt ist einfach zu beantworten: Alle Auswahlschritte haben zufällig zu erfolgen! In unserem Beispiel des tsp ist es die Auswahl der beiden u.a. Städte.

Es geht also zuerst um die Frage: Wie kann der biologische Prozeß der Mutation bei unseren informatischen Systemen modelliert werden?

Konkret bei unserem Problem des tsp: Wie kann man eine vorhandene Rundtour so verändern, dass sie -noch ein lebensfähiges Individuum bleibt- zwar verändert wurde, aber eine Rundtour bleibt? Dafür bieten sich prinzipiell zwei einfache Möglichkeiten an:

Einmal kann man einfach zwei der Städte der Tour austauschen. In der folgenden Zeichnung habe ich es mir einfach gemacht und zwei benachbarte Städte ausgetauscht. Das können aber beliebige Städte sein!

 

Bei der zweiten Variante tauscht man einen Abschnitt der Tour zwischen zwei Städten aus. Im Bild oben ergibt sich dasselbe, weil es sich um zwei benachbarte Städte handelt. Nimmt man aber beliebig weit aus einander liegende Städte, dann entstehen unterschiedliche Ergebnisse. Das läßt sich besser an folgendem Beispiel erläutern:

A B
L C
K D
J E
I F
H G
Tausch
von
Stadt
B
und
J
ergibt
A J
L C
K D
B E
I F
H G

Bei der zweiten Variante gibt es zwei Möglichkeiten, die aber zu inhaltlich symmetrischen Ergebnissen führen:

A B
L C
K D
J E
I F
H G
Tausch
von
Stadt
B
und
J
ergibt
K J
L C
A D
B E
I F
H G

Beide Grundvarianten sind zwar prinzipiell sinnvoll, führen aber zu unterschiedlichen Veränderungen. Während die erste Variante die Städte innerhalb der Tour stark durcheinander würfelt, bleibt bei der zweiten der gesamte Abschnitt erhalten, er kehrt sich nur in der Reihenfolge der Städte um. Es ist zu vermuten, dass die erste Variante daher am Anfang, bei den ersten Generationenfolgen, erfolgreicher zu verbesserten Wegen führt, die andere am Ende, wenn schon relativ viel Ordnung entstanden ist. Beide sollten aber in der Lage sein, sich überschneidende Wegabschnitte zu entfalten und so für eine Verbesserung zu sorgen.