# A running gene crossover function for a Genetic Algorithm

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))))


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)) )) nil)
"Elapsed time: 287.335904 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) )) nil)
"Elapsed time: 6160.856827 msecs"
nil

• I actually prefer the look of mine, but I can't deny that efficiency increase. That will definitely help down the road. Thank you. Apr 3, 2018 at 10:58