Работает функция гена кроссовер для генетического алгоритма


Я пишу генетический алгоритм, и нужно написать функцию, которая пересекает две последовательности гена. В принципе, я хочу, чтобы она работала так:

(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]

Обратите внимание, как он переходит на второй последовательности по индексу 2и вернемся к первой последовательности по индексу 5. Смотрите обзоры проблемой PPCG дополнительные примеры.

У меня есть две основные проблемы с моей реализации:

  • Это некрасиво. Снижение функции является зверским, но я не знаю, что можно улучшить. Короткие имена не помочь, но больше имен будет добавить значительную наворотов, которые не идеальны.

  • Это неэффективно. Он требует повторяя всю последовательность генов, даже если там мало, или даже нет креста поверх очков. Конечно, я мог бы добавить особый случай и проверить, если точки стоят пустые, но все равно не очень помогает. Говорят, что есть один крест в конце генов. Это потребует полного итерации независимо от. Я не могу сказать, если O(n) Это лучшее, что я собираюсь сделать, но я бы предпочел n количество перекрестных точек, а не количество генов в последовательности.


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


Комментарии
1 ответ

Я пытался писать его с рекурсивной петли. Я лично считаю, что это немного легче читать, но я предполагаю, что это зависит от того, насколько вы знакомы с рекурсией.

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

Что касается эффективности, мой алгоритм намного быстрее, особенно когда есть несколько cross-points. Я считаю, что это в основном потому, что он перебирает кросс-точек вместо полной длины генов, а затем использует subvec и concat которые весьма эффективны при использовании на векторы.

Вот некоторые timeС:

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

1
ответ дан 3 апреля 2018 в 08:04 Источник Поделиться