Steuerung

Projektnavigation: Einleitung Pool cross over Mutation Bewertung Selektion Ausgabe Steuerung
Genetische Algorithmen - Steuerung

Steuerung

Von Mirko Bartsch, Jan Pause und Johannes Kreuzer

Die Steuerung hat die Aufgabe, das natürliche zyklische Verhalten der Evolution auf einen Genetischen Algorithmus abzubilden. Hierzu werden die einzelnen Funktionen in einer Schleife immer wieder aufgerufen.

In unserem Beispiel soll die kürzeste Verbindung der linken oberen Ecke zur rechten unteren Ecke gefunden werden. Hierzu wird zufällig ein Gen-Pool generiert, in welchem sich eine bestimmte Anzahl von Wegen befindet. Ein Weg besteht aus vielen zufällig gewählten, mit einander verbundenen Punkten.

Programmablauf

  1. Einbinden aller benötigten Dateien
  2. Die Zufallsfunktionen initialisieren
  3. Abarbeiten der Hauptschleife:
    • Bei jedem 7. Durchlauf den 1. Weg im Pool grafisch ausgeben
    • Sonst ein 'a' ausgeben in die Konsole
    • Der Pool wird variiert mit folgenden Funktionen:
      1. Cross-Over [Pool Akku Wert]
      2. Mutiere [Pool Wahrscheinlichkeit-Wege Wahrscheinlichkeit-Knoten]
      3. Selektiere [Pool anzWege AnteilDerGutenWege]
    • Rekursives aufrufen der Hauptschleife mit verändertem Pool und reduzierten Iterator.

Parameter

  1. anzKnoten: Aus wie vielen Knoten soll jeder einzelne Weg bestehen?
  2. anzWege: Wie viele Wege sollen zur genetischen Manipulation bereit stehen?
  3. Schleifenanzahl: Wie viele Zyklen sollen simuliert werden.

Quellcode

;Steuerung fuer ein Grafensuchproblem mit Hilfe eines genetischen Algorithmus
;Von Mirko Bartsch, Jan Pause und Johannes Kreuzer
;Informatik LK S3 2. Halbjahr 06 + S4 1. Halbjahr 07

;Einbinden aller benötigten Dateien
(require (lib "breakpoint.ss"))
(load "../ausgabe-gruppe/grafik.scm")
(load "../bewertungs-gruppe/bewerte.scm")
(load "../cross-gruppe/cross-over.scm")
(load "../mutations-gruppe/mutiere-parameter.scm")
(load "../pool-gruppe/Poolerzeug-O-Mat.scm")
(load "../selektions-gruppe/selektion.scm")

;Sorgt jedesmal für eine wirklich zufällige Verteilung
(random-seed (abs(current-milliseconds)))

; Das Hauptprogramm _Steuerung_
; Parameter:
;   anzKnoten: Aus wie vielen Knoten soll jeder einzelne Weg bestehen?
;   anzWege: Wie viele Wege sollen zur genetischen Manipulation bereit stehen?
;   Schleifenanzahl: Wie viele Zyklen sollen simuliert werden.


(define
  (Steuerung anzKnoten anzWege Schleifenanzahl)
  (let
      hauptschleife
    ((Pool (gibPool anzKnoten anzWege))
     (i Schleifenanzahl))
       ; HAUPTSCHLEIFE
       ;  Pool: beinhaltet den Pool mit einer Liste aus Wegen
       ;  i: Iterator: beinhaltet die noch zu durchlaufenden Anzahl an Zyklen
    (cond
      ((< i 1) (gib_grafik (fuegePunkte(car Pool))) #t) ;Abbruchbedingung für den Iterator
      (else
       (cond
         ((= (modulo i 7)0) (gib_grafik (fuegePunkte(car Pool))))
         (else (write 'a)))
           ;Erneutes aufrufen der Hauptschleife mit verändertem Pool und reduziertem Iterator
       (hauptschleife
        (selektiere
         (append
              ;cross-over 1. Pool 2. leere Liste 3. Prozentsatz der zu crossenden Wege
          (append Pool (cross-over Pool '() 1))
              ;mutiere 1. Pool 2. P(Weg edit)60  3. P(Punkt edit)90
          (mutiere  Pool 70 10)
          )
         anzWege   ;Anzahl der Wege, die selektiere zurückgeben soll
         0.5)      ;Anteil der guten Wege am zurückgegebenen Pool
        (sub1 i))))))

;Beispiel Aufruf:
;Jeweils 15 Knoten in 40 Wegen
;Berechne 10.000 Durchläufe

(Steuerung 15 40 10000)