genetische Algorithmen - Crossing Over

Projektnavigation: Einleitung Pool cross over Mutation Bewertung Selektion Ausgabe Steuerung

Crossing Over

von Janko Raschke, Jochen Frömming, Alexej Völler und Mirko Bartsch

Beschreibung

Crossing over bedeutet, dass zufällig ausgewählte Wegabschnitte aus den Wegen mit dem gleichen Abschnitt eines anderen, zufällig gewählten Weges ausgetauscht bzw. "gecrosst" werden.
Auf diese Weise wird dafür gesorgt, dass zufällig einige Wegabschnitte an andere Wege weitergegeben werden.
Dies ist ein genetischer Vorgang, der abgewandelt und wesentlich komplexer auch in der Natur vorkommt.

Parameter

pool: Der Parameter ist eine Liste der kompletten Wege. Dies entspräche in der Natur der Population
akku: Der Akku liefert eine leere Liste, um dort später die neu entstandenen Wege hineinzupacken
wert: Der Paramter Wert gibt an, wie viel Prozent der Liste an Wegen mit Hilfe von Crossing Over modifiziert wird.

Modulbeschreibung

Funktionsaufruf: (crossing-over pool akku wert)
mische-liste: (mische-liste pool '()) Verändert die Reihenfolge der Wege in der übergebenen Liste zufällig, so dass nacheinander ausgewählte Wege zum crossen zufällig gewählt sind.
grenzwert: (grenzwert (* wert (length pool))) Der Grenzwert wird am Anfang des Schleifenaufrufs cross-schleife berechnet.

schleife: cross-schleife
Bedingung

Wenn der schleifen-pool leer ist, soll der schleifen-akku ausgegeben.
Wenn die Restliste des schleifen-pool leer ist, also nur noch ein Element in der Liste vorhanden ist, soll der schleifen-akku und das erste Element der Liste schleifen-pool zusammengefügt werden. Wichtig ist, dass das erste Element aus der Liste schleifen-pool noch zu einer Liste gemacht wird, da ansonsten nur die Elemente des ersten Elements der Liste schleifen-pool an die Liste schlefien-akku angehängt werden.
Wenn die Liste größer ist als der Grenzwert, werden nur etwa 80% der Liste an den Akku gehängt. Ist die Liste kleiner, wird sie ohne bearbeitet zu werden an den Akku gehängt.

Quellcode:

(load "../cross-gruppe/crossing.scm")
(load "../cross-gruppe/mische-liste.scm")
(load "../cross-gruppe/zufallspunkt.scm")
(define

;  WICHTIG:
;
;  pool => Stellt den Pool an Wegen mit einzelnen Knoten dar
;  akku => Wird eine leere Liste übergeben!
;  wert => Ist der Wert der zu bearbeitenden Wege (0.2 -> 20%, 0.6 -> 60%, 1 -> 100%)
;

  (cross-over pool akku wert)
  (let
      cross-schleife
      ((schleifen-pool (mische-liste pool '()))
       (schleifen-akku akku)
       (grenzwert (* wert (length pool))))
    (cond
      ((null? schleifen-pool) schleifen-akku)
      ((null? (cdr schleifen-pool)) (append schleifen-akku (list (car schleifen-pool))))
;Bei einer ungeraden Anzahl von Wegen wird der letzte ignoriert!
      ((> grenzwert (length schleifen-akku)) (cross-schleife (cddr schleifen-pool)
      	(append schleifen-akku (crossing (zufallspunkt (length(car schleifen-pool)))
      	(zufallspunkt (length(cadr schleifen-pool))) (car schleifen-pool)
      	(cadr schleifen-pool))) grenzwert))
      (else
       (reverse (append schleifen-pool (reverse schleifen-akku)))))))