A simple binary genetic algorithm in Clojure, to demonstrate one way to write an evolutionary loop.

evolvesum.clj

(ns evolvesum) ;; Lee Spector (lspector@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 possibly 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.