Startseite Seitenanfang Seitenende Progamm Seite 2



Anwendung des allgemeinen Programmes auf das ...

travelling salesperson problem

Haupt - 'Programm'
;;;                                                tsp mit GA.scm
(require-library "breakpoint.scm")

; Die problemabhängigen Teilfunktionen werden durch Laden der
; Spezialprogramme definiert.

; Mutationswahrscheinlichkeit und Selektionswahrscheinlichkeit
; sind positive ganze Zahlen zwischen 0 und 100 ( also % )

;;; ===== Entwurfsentscheidungen ====================================
; Auch wenn der Name 'genetischer-Algorithmus' anderes andeutet, es
; gibt nicht den genetischen Algorithmus, dies ist einer !
; Zu den einzelnen Entwurfsentscheidungen siehe auch bei den
; einzelnen Teilprozessen.
; In der Funktion selbst steckt z.B. die Entwurfsentscheidung, den
; Abbruch allein von der Zahl der Schritte abhängig zu machen. Man
; kann auch andere Abbruchkriterien wählen.

; Eine weitere wichtige Entwurfsentscheidung betrifft die Bewertung
; der Individuen in den Populationen. Wenn auch der eigentliche Sinn
; der GA für die Informatik in der Tatsache steckt, dass die Bewer-
; tungen erheblich 'billiger' sind als das Generieren von Lösungen,
; steckt in der Verwaltung dieser Werte eineabzuwägender Verwaltungs-
; aufwand. Ich habe mich hier daher so entschieden, während der
; Bearbeitung die Bewertungen an die Individuen zu koppeln.
; Jedes von ihnen stellt während der Bearbeitung daher ein Paar
; (Individuum Bewertung) dar!
; Das setzt voraus, dass beim jedem Erzeugen eines neuen Individuums
; sofort eine Bewertung durchgeführt wird.

;;; ===== genetischer-Algorithmus ===================================
(define
  (genetischer-Algorithmus
   Populations-Groesse
   Anzahl-Schritte
   Mutationswahrscheinlichkeit
   crossing-over-Wahrscheinlichkeit)
  (let
      loop
    ((Population
      (Bewertung (erzeuge-Population Populations-Groesse)))
     (zaehler Anzahl-Schritte))
    (Darstellung (bestes-Individuum Population))
    (cond
      ((zero? zaehler)
       (zeichne (bestes-Individuum Population) #t)
        (bestes-Individuum Population))
      (else
       (loop
        (Selektion
         (Kreuzen
          (Mutation Population Mutationswahrscheinlichkeit)
          crossing-over-Wahrscheinlichkeit)
         Populations-Groesse)
        (sub1 zaehler))))))


;;; ===== GA-Aufruf =================================================
; Eine Aufrufhülle für 'genetischer-Algorithmus', bei der die
; Parameter zur Laufzeit eingegeben werden können
(define
  (GA-Aufruf)
  (let
      ((Populations-Groesse
       (begin
         (display "Gib die Zahl der Individuen an [> 0] : ")
         (read)))
       (Anzahl-Schritte
       (begin
         (display "Wieviel Schritte ?             [> 0] : ")
         (read)))
       (Mutationswahrscheinlichkeit
       (begin
         (display "Mutationswahrscheinlichkeit ?  [00 .. 99] : ")
         (read)))
       (crossing-over-Wahrscheinlichkeit
        (begin
          (display
           "Wahrscheinlichkeit für crossing-over ? [00 .. 99] : ")
          (read))))
    (genetischer-Algorithmus 
     Populations-Groesse
     Anzahl-Schritte
     Mutationswahrscheinlichkeit
     crossing-over-Wahrscheinlichkeit)))


;;; ===== erzeuge-Population ========================================
; Erzeugt die Grundpopulation für den genetischen Prozess.
; Parameter sind: Anzahl der Individuen,
; Wert: Eine Liste von Individuen
(define
  (erzeuge-Population Anzahl)
  (let
      loop
    ((Population ())
     (n Anzahl))
    (cond
      ((zero? n)
       Population)
      (else
       (loop
        (cons
         (erzeuge-Individuum)
         Population)
        (sub1 n))))))

;;; ===== aktion? ===================================================
; Hilfsfunktion, die entscheidet ob eine Aktion stattfindet oder
; nicht. Die Entscheidung hängt von der übergebenen ganzzahligen
; Wahrscheinlichkeit p ab.
(define
  (aktion? p)
  (< (random 100) p))

;;; ===== waehle-Positionen =========================================
; Wählt zwei verschiedene Zahlen aus {0 .. n-1} und gib sie als Liste
; zurück. Wird als Hilsfunktion benötigt.
; Die Zahlen sind stets geordnet: (klein gross)
; Unzulässige Parameter für n lösen einen Fehler aus!
(define
  (waehle-Positionen n)
  (cond
    ((not (number? n)) (error "keine Zahl !" n))
    ((not (integer? n)) (error "keine ganze Zahl !" n))
    ((< n 2) (error "keine Auswahl möglich !" n))
    (else
     (let
         loop
       ((i (random n))
        (j (random n)))
       (cond
         ((and (= i j) (positive? i)) (list (sub1 i) j))
         ((= i j) (list i (add1 j)))
         ((> i j) (list j i))
         (else
          (list i j)))))))

;;; ===== Mutation ==================================================
; Steuert die Mutation für die gesamte Population.
; Die bei der Mutation neu erzeugten Individuen werden der Population
; hinzugefügt, dadurch ändert sich die Gesamtzahl. Deren Anpassung
; erfolgt bei der Selektion.
; Parameter sind: Population, Mutationswahrscheinlichkeit
; Wert: mutierte Population.
(define
  (Mutation Population Mutationswahrscheinlichkeit)
  (let
      loop
    ((Population Population)
     (akku ()))
    (cond
      ((null? Population)
       (reverse akku))
      ((aktion? Mutationswahrscheinlichkeit)
       (loop
        (cdr Population)
        (cons
         (bewerte (mutiere (caar Population)))
         (cons
          (car Population)
          akku))))
      (else
       (loop
        (cdr Population)
        (cons
         (car Population)
         akku))))))

;;; ===== Kreuzen ===================================================
; Steuert das Kreuzen für die gesamte Population.
; Da beim Kreuzen neue Individuen erzeugt und der Population hinzu-
; gefügt werden, ändert sich die Gesamtzahl. Deren Anpassung erfolgt
; bei der Selektion.
; Die zu kreuzenden Individuen werden nach dem Zufallsprinzip ausge-
; wählt.
; Parameter sind: Population, crossing-over-Wahrscheinlichkeit
; Wert: gekreuzte Population.
(define
  (Kreuzen Population crossing-over-Wahrscheinlichkeit)
  (let
      ((n (length Population)))
    (let
        loop
      ((Auswahlen (waehle-Positionen n))
       (i (length Population))                ; Zaehler
       (akku ()))
      (cond
        ((zero? i)
         (append akku Population))
        (((aktion? crossing-over-Wahrscheinlichkeit)
         (let
             ((neue
               (kreuze
                (car (list-ref Population (car Auswahlen)))
                (car (list-ref Population (cadr Auswahlen))))))
           (loop
            (waehle-Positionen n)
            (sub1 i)
            (cons
             (bewerte (car neue))
             (cons
              (bewerte (cadr neue))
              akku)))))
        (else
         (loop
          (waehle-Positionen n)
          (sub1 i)
          akku))))))

;;; ===== Selektion =================================================
; Es gibt viele veschiedene Selektionsmechanismen. Beispielsweise
; kann die Auswahl proportional zur Bewertungsfunktion erfolgen.
; Hier werden die vorhandenen Individuen einfach zufällig ausgewählt
; und einer paarweisen Auswahl unterzogen: Selektiert wird aus der
; Menge der Individuen durch direkten Vergleich von je zwei
; Individuen. Der Parameter Gesamtzahl gewährleistet, dass wieder
; die ursprüngliche Populationsgrösse hergestellt wird.
; Dazu wird mit der Selektion abgebrochen, wenn eine genügend grosse
; Zahl ausgewählt wurde.
(define
  (Selektion Population Gesamtzahl)
  (let
      loop
    ((Auswahlen (waehle-Positionen (length Population)))
     (n (length Population))
     (akku ()))
    (cond
      ((= Gesamtzahl (length akku))
       akku)
      (else
       (loop
        (waehle-Positionen n)
        n
        (cons
         (selektiere 
          (list-ref Population (car Auswahlen))
          (list-ref Population (cadr Auswahlen)))
         akku))))))

;;; ===== selektiere ================================================
; Selektiert von zwei Individuen das mit der höheren Bewertungszahl.
; Obwohl hier die Bewertungen der Individuen maximal zweimal bestimmt
; werden, kann es sich lohnen, diese Werte zunächst in einer neuen
; Liste oder in der Populationsliste mit abzulegen.
; So kann z.B. auch in der Ausgabe darauf zugegriffen werden.
; siehe-> Bewertung
(define
  (selektiere Individuum-1 Individuum-2)
  (if
   (besser? Individuum-1 Individuum-2)
   Individuum-1
   Individuum-2))

;;; ===== besser? ===================================================
; Das Prädikat 'besser?' ist das Vergleichsprädikat zur Bewertung und
; ist daher vom speziellen Problem abhängig. Hier wird einfach die
; kleinere (!) Bewertungszahl genommen.
(define
  (besser? Individuum-1 Individuum-2)
   (< (cadr Individuum-1) (cadr Individuum-2)))

;;; ===== Bewertung =================================================
; Führt die Bewertung der gesamten Population durch. Dazu wird die
; Populationsliste in eine Assoziationsliste mit Paaren
; (Individuum Bewertung) verwandelt.
(define
  (Bewertung Population)
  (let
      loop
    ((Population Population)
     (akku ()))
    (cond
      ((null? Population)
       (reverse akku))
      (else
       (loop
        (cdr Population)
        (cons
         (bewerte (car Population))
         akku))))))

;;; ===== bestes-Individuum =========================================
; Für die grafische Darstellung, aber auch für das Ergebnis des GA
; ist es sinnvoll, das 'beste' Individuum bestimmen zu können.
(define
  (bestes-Individuum Population)
  (let
      loop
    ((Population (cdr Population))
     (bestes (car Population)))
    (cond
      ((null? Population) bestes)
      ((besser? (car Population) bestes)
       (loop (cdr Population) (car Population)))
      (else
       (loop (cdr Population) bestes)))))

;;; ===== Zufallsgenerator-setzen ===================================
; Setzt den Zufallsgenerator je nach Parameter mit einer "zufälligen"
; Zahl oder der Zahl 123456789.
(define
  (Zufallsgenerator-setzen Zeit?)
  (random-seed
   (if
    Zeit?
    (remainder
     (abs (current-milliseconds))
     1000000000)
    123456789)))


;;; ===== Aufruf ====================================================
(Zufallsgenerator-setzen #f)
(load "tsp mit GA Funktionen.scm")
(genetischer-Algorithmus 50 1000 15 30)
Haupt - 'Programm'


Startseite Seitenanfang Seitenende Progamm Seite 2