[Cs254f11] a complete genetic algorithm

[Lee Spector]

I think that it would be useful at this point for me to provide code for a complete, simple genetic algorithm in Clojure.

This just evolves a number as the sum of a vector of zeros and ones, so it's not solving a very interesting problem or using a very interesting representation. But it shows one way of making all of the pieces of an evolutionary algorithm (a GA, not a GP system because the individuals here aren't executed), and in particular one way of making the main evolutionary loop. I think it's pretty concise and readable, and you should feel free to adapt it to your own purposes. 

What follows is executable code.

 -Lee

(ns evolvesum) ;; Lee Spector (lspector at hampshire.edu) 20111009

;; We evolve a vector of 100 zeros and ones that sums to a particular number.

;; An individual is a vector of 100 random bits.

(defn new-individual 
  []
  (vec (repeatedly 100 #(rand-int 2))))

;; An individual is mutated by flipping a random bit.

(defn mutate
  [individual]
  (assoc individual (rand-int 100) (rand-int 2)))

;; The error of an individual is the difference between the sum of the bits
;; and the goal, which we hardcode here.

(defn error 
  [individual]
  (Math/abs (- (reduce + individual) 73)))

;; An individual is better than another if it has lower error.

(defn better
  [i1 i2]
  (< (error i1) (error i2)))

;; We evolve a solution by starting with a random population and repeatedly
;; sorting, checking for a solution, and producing a new population.
;; We produce the new population by selecting and mutating the better half
;; of the current population.

(defn evolve
  [popsize]
  (loop [population (sort better (repeatedly popsize new-individual))]
    (let [best (first population)]
      (println "Best error:" (error best))
      (if (zero? (error best))
        (println "Success:" best)
        (let [better-half (take (int (/ popsize 2)) population)]
          (recur 
            (sort better (map mutate 
                              (concat better-half better-half)))))))))

;; Run it with a population of 100:

(evolve 100)

;; Exercises:
;; - Create variables or parameters for the various hardcoded values.
;; - Avoid recomputing errors by making individuals pairs of [error genome].
;; - Print more information about the population each generation.
;; - Select parents via tournaments.
;; - Add crossover.
;; - Use a more interesting genome representation, for a more interesting
;;   problem.



--
Lee Spector, Professor of Computer Science
Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector at hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438