ga.rkt

#lang racket

;; Computes the fitness function of chromosome c
(define (fitness c)
  (for/sum ([a (in-string c)]
            [b (in-string "Hello, world!")])
     (if (char=? a b)
         1
         0)))

;; Runs the entire algorithm until we get an exact match.
(define (run pop-size num-mutate num-cross)
  (define initial-population (random-population pop-size))
  (let loop ([generation 0]
             [population initial-population])
    (cond
     [(= 13 (population-fitness population))
      (printf "Done in ~a generations\n" generation)]
     [else
      (printf "Gen. ~a: Fitness: ~a ~s\n"
              generation (population-fitness population) (take-top 5 population))
      (define new-population (cross-population num-cross population))
      (mutate-population! num-mutate new-population)
      (loop (add1 generation) new-population)])))

;; Creates a random starting chromosome
(define (random-chromosome)
  (list->string
   (for/list ([i (in-range 13)])
     (random-letter))))

;; Make a random population with `size' chromosomes
(define (random-population size)
  (for/list ([i (in-range size)]) (random-chromosome)))

;; Find the fitness of the best member of the population.
(define (population-fitness population)
  (apply max (map fitness population)))

;; Destructively changes a letter in 'c'
(define (mutate! c)
  (string-set! c (random (string-length c)) (random-letter)))

;; Mutate N members of the population.
(define (mutate-population! n population)
  (for ([i (in-range n)])
     (mutate! (random-pick population))))

;; Interleave letters from a and b, making two children
(define (cross a-chromosome b-chromosome)
  (define split (random (string-length a-chromosome)))
  (list
   (string-append (substring a-chromosome 0 split)
                  (substring b-chromosome split))
   (string-append (substring b-chromosome 0 split)
                  (substring a-chromosome split))))

;; Replace the bottom N performers of the population with new ones,
;; returning a new population
(define (cross-population n population)
  (define population-length (length population))
  (define candidates (take-top (- population-length n)
                               population))
  (append* candidates
           (for/list ([i (in-range (/ n 2))])
                     (cross (random-pick candidates)
                            (random-pick candidates)))))

;; Take the top N performing chromosomes from the population.
(define (take-top n population)
  (define (compare a b)
    (> (fitness a) (fitness b)))
  (take (sort population compare) n))

;; picks a random element from `list'
(define (random-pick list)
  (list-ref list (random (length list))))

;; picks a random letter in the printable ASCII set
(define (random-letter)
  (integer->char (+ 32 (random 94))))


(run 100 10 50)