Projektnavigation: Einleitung Pool cross over Mutation Bewertung Selektion Ausgabe Steuerung

Mutationsmodul

von Patrick Stöhr

Abstrakt

Biologisch

Eine Mutation (v. lat.: mutare = (ver)ändern, tauschen) ist eine Veränderung des Erbgutes eines Organismus durch Veränderung der Abfolge der Nucleotidbausteine oder durch Veränderung der Chromosomenzahl, die nicht auf Rekombination oder Segregation beruht. Dieser Begriff wird daher nur für einen Teilbereich aller möglichen Chromosomenaberrationen verwendet. Durch eine Mutation wird die in der DNA gespeicherte Information verändert und dadurch können einzelne Merkmale (der Phänotyp) verändert werden.

Der Entwicklungslehre Darwins zufolge ist die Mutation mit für die Artenvielfalt auf der Erde verantwortlich. Mutationen sind so (aber nicht nur) ein natürliches Phänomen und ermöglichen erst die Entwicklung der Arten (siehe: Evolutionslehre). Obwohl die Mutation die Dynamik der Evolution ausmacht, ist nur in den selteneren Fällen mit einer Veränderung im Genom ein Vorteil für das Individuum zu erwarten.

(aus: Wikipedia - Mutation)

In Scheme

Die Mutation wird im genetischen Algorithmus emuliert (funktionelles Nachbilden eines Systems), indem in den übergebenen "Lebensformen" (Wege, Graphen mit einer Anzahl von Knoten) nach einer vorher festgelegten Wahrscheinlichkeit (siehe "Parameter") Teilkoordinaten des Graphen mit einem neu erzeugten Zufallswert, der unabhängig vom Vorwert generiert wird, ersetzt werden. Der genetische Algorithmus emuliert eine Punktmutation, in der die Länge der Erbinformation unverändert bleibt und nur eine Base (hier: Knoten) verändert wird.

Parameter

Folgende Parameter stehen beim Aufruf von (mutiere) zur Verfügung:

(mutiere genpool wahrscheinlichkeit-wege wahrscheinlichkeit-knoten)

genpool
Enthält die zu verarbeitenden Wege. Die Syntax ist systemweit festgelegt durch das Poolerzeugungsmodul:
(((1 . 2)(3 . 4)(5 . 6)(7 . 8))((1 . 2)(3 . 4)(5 . 6)(7 . 8)))
Der Beispielcode definiert zwei Wege mit jeweils 4 Knoten.
wahrscheinlichkeit-wege
Gibt die relative Wahrscheinlichkeit in Prozent an, mit der ein einzelner Weg zur potentiellen Mutation weitergegeben wird. Das Parameter ist ein Integer von 0 bis 100, 0 für "keine Mutation", 100 für "sichere Mutation".
wahrscheinlichkeit-knoten
Gibt die relative Wahrscheinlichkeit an, dass ein einzelner Knoten eines zu mutierenden Weges mutiert wird. Wie im vorhergehenden Parameter ein Integer von 0 bis 100.

Parametertest

Die Parameter wahrscheinlichkeit-wege und wahrscheinlichkeit-knoten sind insofern abgesichert, als dass nur Integer von 0 bis 100 angenommen werden. Ungültige Angaben werden ersetzt mit 60 für Wege und 90 für Knoten.

Das Parameter genpool wir direkt übernommen und bearbeitet. Der Grund dafür ist, dass die Gültigkeit dieser Liste bereits vom Steuerungsmodul überprüft wird, eine zweite Prüfung ist nicht notwendig.

Quellcode

(define
  (mutiere genpool wahrscheinlichkeit-wege wahrscheinlichkeit-knoten)
  (cond
    ((null? genpool)(error "Kein Genpool an Mutationsmodul übergeben"))
    ((null? wahrscheinlichkeit-wege)(mutiere genpool 60 wahrscheinlichkeit-knoten))
    ((< wahrscheinlichkeit-wege 0)(mutiere genpool 60 wahrscheinlichkeit-knoten))
    ((> wahrscheinlichkeit-wege 100)(mutiere genpool 60 wahrscheinlichkeit-knoten))
    ((null? wahrscheinlichkeit-knoten)(mutiere genpool wahrscheinlichkeit-wege 90))
    ((< wahrscheinlichkeit-wege 0)(mutiere genpool wahrscheinlichkeit-wege 90))
    ((> wahrscheinlichkeit-wege 100)(mutiere genpool wahrscheinlichkeit-wege 90))
    (else (finde-lebewesen genpool wahrscheinlichkeit-wege wahrscheinlichkeit-knoten))))

(define
  (finde-lebewesen liste wk-wege wk-knoten)
  (cond
    ((null? liste)())
    ((>= wk-wege (random 101))(cons (mutiere-werte '() (car liste) wk-knoten) (finde-lebewesen (cdr liste) wk-wege wk-knoten)))
    (else
     (cons (car liste) (finde-lebewesen (cdr liste) wk-wege wk-knoten)))))

(define
  (mutiere-werte neueliste urliste w-knoten)
     (cond
       ((null? urliste)(reverse neueliste))
       ((>= w-knoten (random 101))(mutiere-werte (cons (gib-zufallskoordinate) neueliste) (cdr urliste) w-knoten))
       (else
        (mutiere-werte (cons (car urliste) neueliste) (cdr urliste) w-knoten))))

(define
  (gib-zufallskoordinate)
  (cons (random 101) (random 101)))