2

在进化/遗传算法中有多种重组方法。他们中的大多数遭受与染色体长度相关的偏差（也称为位置偏差）。

Uniform crossover和shuffle crossover可以解决这个问题。但是，如果在统一交叉的情况下，我不明白两者之间的区别p(c)=0.5

解释

  • 与p(c)=0.5每个基因的均匀交叉是一个可能的交叉点。
  • 使用混洗交叉，首先对染色体序列进行混洗（均匀地），然后分配一个交叉点，最后恢复原始染色体序列 - 这实际上意味着尽管只发生了一次交叉，但它可能会独立影响染色体中的每个位置。

由于这两种方法都涉及完全随机化，我看不出结果应该不同的原因。

我想确切地知道，因此我写了一个小脚本来测试这两种机制。这是一些 R 代码，如果您想自己尝试一下

parent1 <- rep(0, 10000) # 10.000 genes in the chromosome - change at will
parent2 <- rep(1, length(parent1))

# Uniform crossover
offspring1_unif <- rep(-1, length(parent1)) # initialize offspring1_unif
offspring2_unif <- rep(-1, length(parent1)) # initialize offspring2_unif

for(i in 1:length(parent1)) {
  if (runif(1) < 0.5) {
    offspring1_unif[i] <- parent1[i]
    offspring2_unif[i] <- parent2[i]
  } else {
    offspring1_unif[i] <- parent2[i]
    offspring2_unif[i] <- parent1[i]
  }
}

# Shuffle crossover

## Shuffle
shuffler <- seq(1, length(parent1))
shuffler <- sample(shuffler, length(parent1))

## perform the crossover
crossover_point <- sample(1:length(parent1), 1)

offspring1_shuffle <- rep(-1, length(parent1)) # initialize offspring1_shuffle
offspring2_shuffle <- rep(-1, length(parent1)) # initialize offspring2_shuffle

for(i in 1:length(shuffler)) {
  if (i < crossover_point) {
    offspring1_shuffle[shuffler[i]] <- parent1[shuffler[i]]
    offspring2_shuffle[shuffler[i]] <- parent2[shuffler[i]]
  } else {
    offspring1_shuffle[shuffler[i]] <- parent2[shuffler[i]]
    offspring2_shuffle[shuffler[i]] <- parent1[shuffler[i]]

  }
}

mean(offspring1_unif) # 0.493
mean(offspring1_shuffle) # 0.3295

mean(offspring2_unif) # 0.507
mean(offspring2_shuffle) # 0.6705

sd(offspring1_unif) # 0.499976
sd(offspring1_shuffle) # 0.4700552

sd(offspring2_unif) # 0.499976
sd(offspring2_shuffle) # 0.4700552
4

2 回答 2

1

对于均匀交叉，可以有许多交叉点。交叉点的数量本质上变成了二项分布。p(c)=0.5你可以期望在一个有点长的遗传字符串中有交叉点K/2。K

另一方面，Shuffle 交叉选择一个，并且只有一个，随机位作为交叉点。

于 2013-10-07T17:11:42.097 回答
1

不同之处在于两种方法中掉期次数的分​​布情况。

  • 均匀交叉：
    我们选择一个基因以独立于其他交换的概率 p进行交换，即伯努利实验 ，我们对整个染色体进行这个伯努利实验，即假设n 个基因，所以交换的数量将遵循二项分布。

  • shuffle-cross-over：
    我们首先随机打乱染色体（这样做主要是为了避免位置偏差，即将概率交换与染色体中基因的位置解耦——我们确实在统一情况下处理了这种偏差与uniform case不同的是，我们只选择一个交叉点，这个交叉点一侧的所有元素都会被交换，所以我们以1/等概率交换任意数量的基因2.因此我们也避免了所谓的分布偏差，即互换次数不同的概率。

于 2016-09-12T18:40:25.200 回答