A running gene crossover function for a Genetic Algorithm

Question

I'm writing a Genetic Algorithm, and need to write a function that crosses two gene sequences. Basically, I want it to work like this:

(running-cross [1 2 3 4 5 6 7 8 9] ; Gene sequence 1
               [11 22 33 44 55 66 77 88 99] ; Gene sequence 2
               [2 5]) ; The "cross points"
=> [1 2 33 44 55 6 7 8 9]

Note how it crosses over to the second sequence at index 2, and back to the first sequence at index 5. See the related PPCG challenge for more examples.

I have two main concerns with my implementation:

• It's ugly. The reducing function is atrocious, but I don't know what can be improved. The short names don't help, but longer names would add significant bloat which wouldn't be great either.

• It's inefficient. It requires iterating the entire gene sequence, even if there are few, or even no cross over points. Of course I could add a special case and check if the points are empty first, but that still doesn't help much. Say there's a single cross over point at the end of the genes. It will require a full iteration regardless. I can't tell if O(n) is the best I'm going to get, but I'd prefer n be the number of cross-over points, not the number of genes per sequence.

---

(defn running-cross [genes other-genes cross-points]
  (let [cp-set (set cross-points)]
    (->> (map vector (range) genes other-genes)

      (reduce (fn [[g1? acc] [i g1 g2]]
                (let [g1?' (if (cp-set i) (not g1?) g1?)]
                  [g1?' (conj acc (if g1?' g1 g2))]))
              [true []])

      (second))))

Answer 1

I tried writing it with a recursive loop. I personally find it a bit easier to read, but I guess it depends on how familiar you are with recursion.

(defn running-cross
    [genes other-genes cross-points]
    (loop [remaining-cross-points cross-points 
           last-cross 0
           take-from-g1? true
           result []]
        (let [next-gene (if take-from-g1? genes other-genes)
              next-cross (first remaining-cross-points)]
            (if next-cross
                (recur (rest remaining-cross-points)
                       next-cross
                       (not take-from-g1?)
                       (concat result (subvec next-gene last-cross next-cross)))
                (concat result (subvec next-gene last-cross))))))

As for efficiency, my algorithm is a lot faster; especially when there are few cross-points. I believe this is mainly because it iterates over the cross-points instead of the full length of the genes, and then uses subvec and concat which are quite efficient when used on vectors.

Here are some times:

;; 5 000 000 length genes, crossing over on every index
user=> (do (time (running-cross-mine (vec (range 5000000)) (vec (range 5000000)) (vec (range 5000000)))) nil)
"Elapsed time: 3298.197955 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) (vec (range 5000000)))) nil)
"Elapsed time: 11672.627633 msecs"
nil

;; 5 000 000 length genes, crossing over once
user=> (do (time (running-cross-mine (vec (range 5000000)) (vec (range 5000000)) [2500000])) nil)
"Elapsed time: 287.335904 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) [2500000])) nil)
"Elapsed time: 6160.856827 msecs"
nil