Обработка дубликатов при использовании частично согласованного кроссовера для алгоритма Geneti c - PullRequest
Новая
       63

Обработка дубликатов при использовании частично согласованного кроссовера для алгоритма Geneti c

1 голос
/ 20 февраля 2020

Я новичок в Geneti c Алгоритмы и работаю над реализацией python. Я на шаге кроссовера и пытаюсь кроссовер с частичным совпадением. Для моего окончательного вывода я надеюсь на список, который не содержит дублированных номеров. Однако в некоторых случаях я представляю дубликаты. Например, возьмите списки

Mate 1 [1,2,3,5,4,6]

Mate 2 [6,5,4,3,2,1]

Если доля кроссовера равна [3,5,4] -> [4,3,2]

Тогда потомство перед картированием становится [1,2,4,3,2,6]. Мое понимание алгоритма - это отображение вне кроссовера 4 -> 3, 5 -> 3 and 2 -> 4. Тем не менее, это приводит к выводу [1,4,4,3,2,6], который имеет дубликаты и пропускает 5.

Как мне обойти эту проблему? Первые 4 просто становятся 5? И как бы это масштабировалось для больших списков, которые могли бы ввести несколько дубликатов?

1 Ответ

0 голосов
/ 21 февраля 2020

Я не уверен, что вы правильно это реализовали:

для Частично согласованного кроссовера ( см. Объяснение ), если ваши точки кроссовера равны 2 и 5, как предложено в примере, тогда вы можете получить 

offspring1 = [6, 2, 3, 5, 4, 1]
offspring2 = [1, 5, 4, 3, 2, 6]

только если вы выберете 3,5,4 от mate1 и заполните остаток в порядке mate2, вы получите потомство 1, но если вы выберете 4,3,2 от mate2 и заполните остаток в порядке mate 1, вы получите потомство 2

См. реализацию ниже: 

mate1 = [1,2,3,5,4,6]
mate2 = [6,5,4,3,2,1]


crossoverpoint1 = 2
crossoverpoint2=5
child = []

#fill in the initial genes in order of mate1
count = 0
for i in mate1:
    if(count == crossoverpoint1):
        break
    if(i not in mate2[crossoverpoint1:crossoverpoint2]):
        child.append(i)
        count= count+1

#select the genes within the crossover points from mate2          
child.extend(mate2[crossoverpoint1:crossoverpoint2])

#fill in the remaining genes in order of mate1
child.extend([x for x in mate1 if x not in child])

print(child)

output: 

[1, 5, 4, 3, 2, 6]

для получения swap mate1 потомка1 для mate2. Вы также можете попробовать разные точки пересечения, дайте мне знать, если это поможет

...