algorithm - 遗传算法 : How to do crossover on ordered collections of unique elements?

Question

此问题基于 another one .

我们如何有效地对由唯一元素的有序集合形成的染色体进行交叉操作？

两个这样的父染色体是 {'a','b','c','d'} 和 {'e','f','a', 'b'};这些 parent 的两个可能的子染色体是 {'e','f','c','d'} 和 {'a','f','c' ,'b'}.

Answer 1

你可以尝试一种统一的交叉。

一般Uniform Crossover使用两个亲本之间的固定混合比，运算符评估亲本染色体中的每个基因以进行交换，概率为 0.5。

使用 Python 语法:

import random

p = [['a','b','c','d'], ['e','f','a','b']]    # parents

for i in range(len(p[0])):
   offspring.append(p[random.randint(0, 1)][i])

鉴于唯一性约束，必须修改基本方案:

import random

p = [['a','b','c','d'], ['e','f','a','b']]    # parents

for i in range(len(p[0])):
    if p[1][i] in p[0]:    # cannot risk crossover, keep basic gene
        offspring.append(p[0][i])
    else:                  # standard uniform crossover
        offspring.append(p[random.randint(0, 1)][i])

约束“自动”满足，您有一个较小的搜索空间。

请注意，交叉在某种程度上绑定(bind)到第一个父级 (p[0])，我们得到的变体数量有限:

CHROMOSOME FREQUENCY
abcd       *************************
efcd       ************************
ebcd       ************************
afcd       ************************

在这方面的一个小改进是:

if p[1][i] in offspring or p[1][i] in p[0][i:]:
    offspring.append(p[0][i])
else:
    offspring.append(p[random.randint(0, 1)][i])

和

CHROMOSOME FREQUENCY
efcd       ******
afcd       ************
efad       ******
ebcd       ************
efcb       ******
efab       ******
ebad       ************
abcd       *************************
afcb       ************

但是这个“窍门”只对一些 parent 有效。例如。切换 parent :

p = [['e','f','a','b'], ['a','b','c','d']]

你又遇到了:

CHROMOSOME FREQUENCY
efcd       *************************
efcb       ************************
efad       *************************
efab       ************************

---

edge recombination operator是另一种可能性:

ERO creates a path that is similar to a set of existing paths (parents) by looking at the edges rather than the vertices. The main application of this is for crossover in genetic algorithms when a genotype with non-repeating gene sequences is needed such as for the travelling salesman problem.

(不确定是不是你的情况)