Crossover und Mutation

Nachdem Individuen für eine neue Generation selektiert wurden, wird ihr genetischer Code durch Crossover (Kreuzung) und Mutation verändert. Diese Vorgänge entsprechen direkt den beiden in der natürlichen Evolution vorkommenden Prozessen zur Veränderung des Erbgutes. Crossover findet zwischen jeweils zwei zufällig ausgewählten Individuen der neuen Generation statt, die zufällig ausgewählte Teile ihres genetischen Codes austauschen. Dies eröffnet den Zugang zu neuen Kombinationen des in einer Population vorhandenen Erbgutes.

Crossover zwischen zwei zufällig ausgewählten Individuen, die zufällig ausgewählte Teile ihres genetischen Codes austauschen

Crossover wird solange wiederholt, bis eine bestimmte Crossover-Rate erreicht ist. Dieser Vorgang ermöglicht die Kombination bestimmter Teile des genetischen Materials, die für sich genommen eine gute Teillösung des zu optimierenden Problems darstellen, zu einer insgesamt verbesserten Gesamtlösung. Die zweite der Evolution nachempfundene Operation ist eine Mutation. Die Mutation des genetischen Codes eines zufälligen Individuums wird durch die Veränderung eines zufällig gewählten Elements seines genetischen Materials erreicht. Auf den Bitstring angewandt, der das genetische Material eines Individuums repräsentiert, entspricht das dem Invertieren eines zufälligen Bits. Aus 1 wird 0 oder umgekehrt. Diese Operation erzeugt prinzipiell neues genetisches Material, was durch Crossover nicht möglich ist. Die Mutation wird mit einer fest vorgegebenen Wahrscheinlichkeit, der Mutations-Rate, auf das genetische Material der neuen Generation angewandt.

Veränderung eines zufälligen Bits im genetischen Code eines Individuums durch Mutation

Einfluß der Crossover- und Mutations-Rate auf den Verlauf der Optimierung

Crossover und Mutation stellen Operationen zur zufälligen Veränderung des genetischen Materials dar. Dies ist zugleich in Verbindung mit der Selektion besonders "fitter" Individuen der einzige Weg zur Verbesserung der Problemlösung von einer Generation zur Nächsten. Welchen Einfluss haben nun die Crossover- und Mutations-Rate auf diesen Vorgang? Crossover ermöglicht die Kombination guter Teillösungen zu einer besseren Gesamtlösung. Gleichzeitig kann sich die Gesamtlösung natürlich auch verschlechtern, insbesondere wenn der Schnitt durch das genetische Material mitten durch einen Bereich geht, der eine gute Teillösung repräsentiert. Diese Möglichkeit einer zufälligen Zerstörung nimmt mit der Crossover-Rate zu. Andererseits kann eine zu geringe Crossover-Rate ein sehr langsames Fortschreiten des Optimierungsprozesses zur Folge haben. In der Literatur finden sich deshalb viele Untersuchungen zu diesem Problem. Im Allgemeinen wird eine optimale Crossover-Rate von etwa 0.6 vorgeschlagen.

Anders sieht das Problem bei der Festlegung der Mutations-Rate aus. Einerseits stellt die Mutation die einzige Möglichkeit zur Erzeugung neuen genetischen Materials dar, weshalb sie nicht unwahrscheinlich sein sollte. Andererseits würde eine zu hohe Mutations-Rate den Zufallscharakter der Optimierung erhöhen. Im Extremfall einer Mutations-Rate von 1.0 wäre die Optimierung ein reines stochastisches Verfahren. In der Literatur wird im allgemeinen eine Rate von 0.001 vorgeschlagen. Dies ist mehr als zwei Größenordnungen weniger als die Crossover-Rate und lässt auf den unterschiedlichen Stellenwert der beiden Operationen für den Fortgang der Optimierung schließen.

© Prof. Dr. J. Gasteiger, Dr. Th. Engel, J. Sadowski, CCC Univ. Erlangen, Thu Apr 15 06:31:59 2004 GMT
 BMBF-Leitprojekt Vernetztes Studium - Chemie