cshepp

Keybase proof

I hereby claim:

• I am cshepp on github.
• I am cshepp (https://keybase.io/cshepp) on keybase.
• I have a public key ASChEeeBYX7vBD8kKgLmRU7lvvxMrwBigrlsZr8MpNR-yQo

To claim this, I am signing this object:

cshepp

;; single-generation cycle: select -> crossover -> mutate
(defn next-generation [population]
  ""
  (->> (sort-by calculate-fitness population)
        vec
        roulette-select
        pair
       (map cycle-crossover)
       (reduce into)
       (map (fn [x] (if (should-mutate?)

cshepp

(map (fn [x] (if (should-mutate?)
                 (mutate x)
                 x)
      population))

(defn mutate [genome]
  "swaps two sets of random elements in the given genome"
  (let [a (rand-int (count genome))
        b (rand-int (count genome))
        c (rand-int (count genome))

cshepp

(map cycle-crossover (pair population))

(defn pair [vec]
  "splits a 1d array into a 2d array of pairs"
  (mapv (fn [i] (subvec vec i (+ 2 i)))
        (map #(* 2 %)
             (range (/ (count vec) 2)))))

(defn cycle-crossover [[a b]]
  "returns both permuations of the parents'

cshepp

(defn find-all-cycles [a b]
  "finds all possible cycles in the parents"
  (loop [idx 0
         cyl (order-preserving-set)]
    (let [c (find-cycle a b idx)]
      (if (= idx (count a))
        (vec (seq cyl))
        (recur (inc idx) (into cyl [c]))))))

(defn find-cycle [a b seed]

cshepp

(def fitness-multiplier 100)

(defn roulette-select [population]
  "randomly selects solutions - 
   probability of being selected is
   weighted using fitness score"
  (let [roulette-wheel  (reduce #(conj %1 (+ (* (- 700 %2) fitness-multiplier) (last %1))) [0] (map calculate-fitness population))
        total           (last roulette-wheel)]
    (mapv (fn [x] (nth population (.indexOf roulette-wheel (first (filter #(< (rand-int total) %1) roulette-wheel)))))
          (range (count population)))))

cshepp

(def num-participants 4) ;; how many solutions should take part in each tournament

(defn tournament-select [population]
  "order the members of the population according
   to their success in...battles to the death!"
  (mapv (fn [x] (let [idxs (repeatedly num-participants #(rand-int (count population)))
                      participants (map #(population %) idxs)]
                 (first (sort-by calculate-fitness participants))))
       (range (count population))))

cshepp

(defn calculate-fitness [genome]
  "Returns the total distance travelled for a given solution"
  (let [path (pathify genome)
        distances (map get-distance path)]
    (reduce + distances)))

(defn pathify [vec]
  "turns a vector into a vector of transitions,
   including last element back to the first

cshepp

;; data from http://www.codeproject.com/Articles/259926/Introduction-to-Genetic-Algorithm-Encoding-Camel
;; licensed under the CPOL: http://www.codeproject.com/info/cpol10.aspx
(def distances [[ 0   28  57  72  81  85  80  113 89  80  ]
                [ 28  0   28  45  54  57  63  85  63  63  ]
                [ 57  28  0   20  30  28  57  57  40  57  ]
                [ 72  45  20  0   10  20  72  45  20  45  ]
                [ 81  54  30  10  0   22  81  41  10  41  ]
                [ 85  57  28  20  22  0   63  28  28  63  ]
                [ 80  63  57  72  81  63  0   80  89  113 ]
                [ 113 85  57  45  41  28  80  0   40  80  ]

cshepp

(defn create-population [gen-size genome-size]
  "creates a random population of size gen-size,
   with each genome of size genome-size"
  (map (fn [x] (vec (unique-random-numbers genome-size)))
       (range gen-size)))

;; from https://clojuredocs.org/clojure.core/rand-int
(defn unique-random-numbers [n]
  "Generates a list of unique random ints between 0 and n"
  (let [a-set (set (take n (repeatedly #(rand-int n))))]