Генетический алгоритм - упорядоченный кроссовер в питоне

Question

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

def crossover(self, mum, dad):
    """Implements ordered crossover"""

    size = len(mum.vertices)

    # Choose random start/end position for crossover
    alice, bob = [-1] * size, [-1] * size
    start, end = sorted([random.randrange(size) for _ in range(2)])

    # Replicate mum's sequence for alice, dad's sequence for bob
    for i in range(start, end + 1):
        alice[i] = mum.vertices[i]
        bob[i] = dad.vertices[i]

    # # Fill the remaining position with the other parents' entries
    # current_dad_position, current_mum_position = 0, 0
    #
    # for i in chain(range(start), range(end + 1, size)):
    #
    #     while dad.vertices[current_dad_position] in alice:
    #         current_dad_position += 1
    #
    #     while mum.vertices[current_mum_position] in bob:
    #         current_mum_position += 1
    #
    #     alice[i] = dad.vertices[current_dad_position]
    #     bob[i] = mum.vertices[current_mum_position]
    #
    # # Return twins
    # return graph.Tour(self.g, alice), graph.Tour(self.g, bob)
    return mum, dad

Закомментированная часть заставляет мою программу работать с ~ 7 секунддо 5-6 минут (я бегу 5000 итераций ГА).Есть ли способ, которым этот заказанный кроссовер может быть выполнен более эффективно?

---

Что делает функция кроссовера

Для тех, кто незнаком, я реализую кроссовер на основе порядка (OX2).Учитывая два массива последовательных целых чисел (родителей), выбираются две случайные начальные / конечные позиции.

  mum   =   4   9   2   8   3   1   5   7   6
  dad   =   6   4   1   3   7   2   8   5   9
                    ^           ^
                  start        end

Затем два потомка разделяют получившиеся срезы:

  child 1   =   _   _   2   8   3   1   _   _   _
  child 2   =   _   _   1   3   7   2   _   _   _
                        ^           ^

Теперь оставшиесяСлоты заполняются записями других родителей в том порядке, в котором они появляются, при условии, что повторений не происходит.Таким образом, так как ребенок 1 получил свой кусок от мамы, остальные записи взяты от папы.Сначала мы берем 6, затем 4, затем затем мы берем 7 (не беря 1 и 3, так как они уже появляются у ребенка 1 от мамы), затем 5, затем 9. Итак

  child 1   =   6   4   2   8   3   1   7   5   9

и аналогично

  child 2   =   4   9   1   3   7   2   8   5   6

Это то, что я реализую в функции.

Answer 1

Хорошо, зная, что проблема однозначно решаема благодаря строительству, вот как она должна выглядеть:

import random
import numpy as np

def crossover(mum, dad):
    """Implements ordered crossover"""

    size = len(mum.vertices)

    # Choose random start/end position for crossover
    alice, bob = [-1] * size, [-1] * size
    start, end = sorted([random.randrange(size) for _ in range(2)])

    # Replicate mum's sequence for alice, dad's sequence for bob
    alice_inherited = []
    bob_inherited = []
    for i in range(start, end + 1):
        alice[i] = mum.vertices[i]
        bob[i] = dad.vertices[i]
        alice_inherited.append(mum.vertices[i])
        bob_inherited.append(dad.vertices[i])

    print(alice, bob)
    #Fill the remaining position with the other parents' entries
    current_dad_position, current_mum_position = 0, 0

    fixed_pos = list(range(start, end + 1))       
    i = 0
    while i < size:
        if i in fixed_pos:
            i += 1
            continue

        test_alice = alice[i]
        if test_alice==-1: #to be filled
            dad_trait = dad.vertices[current_dad_position]
            while dad_trait in alice_inherited:
                current_dad_position += 1
                dad_trait = dad.vertices[current_dad_position]
            alice[i] = dad_trait
            alice_inherited.append(dad_trait)

        #repeat block for bob and mom
        i +=1

    return alice, bob

с

class Mum():
    def __init__(self):
        self.vertices =[  4,   9,   2,   8,   3,   1,   5,   7,   6 ]

class Dad():
    def __init__(self):
        self.vertices =  [ 6 ,  4  , 1  , 3 ,  7 ,  2  , 8  , 5 ,  9 ]

mum = Mum()  
dad = Dad()
a, b =  crossover(mum, dad) 
# a = [6, 4, 2, 8, 3, 1, 5, 7, 9]

Answer 2

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

     while current_dad_position < size and dad.vertices[current_dad_position] in alice:
         current_dad_position += 1

     while current_mom_position < size and mum.vertices[current_mum_position] in bob:
         current_mum_position += 1

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

Чтобы кто-нибудь мог проверить это, я бы порекомендовал дополнить ваш код простым вводным примером и не комментировать рассматриваемый код, а отметить его BEGIN и END.с комментариями.