2

進化的/遺伝的アルゴリズムには、複数の組換え方法があります。それらのほとんどは、染色体の長さに関連するバイアス (位置バイアスとも呼ばれます) に苦しんでいます。

一様交叉とシャッフル交叉は、この問題を解決できます。ただし、均一なクロスオーバーの場合、2つの違いがわかりませんp(c)=0.5

説明

  • p(c)=0.5すべての遺伝子との 均一なクロスオーバーは、可能なクロスオーバー ポイントです。
  • シャッフル交叉では、染色体配列が最初に (一様に) シャッフルされ、次に 1 つの交叉点が割り当てられ、最後に元の染色体配列が復元されます。これは実際には、交叉が 1 回しか発生していなくても、染色体のすべての位置に独立して影響を与える可能性があることを意味します。

どちらの方法も完全なランダム化を伴うため、結果が異なる理由はわかりません。

正確に知りたかったので、両方のメカニズムをテストするための小さなスクリプトを書きました。自分で試してみたい場合は、ここにいくつかの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/2K

一方、シャッフル クロスオーバーは、クロスオーバー ポイントとしてランダムに 1 つだけのビットを選択します。

于 2013-10-07T17:11:42.097 に答える
1

違いは、両方の方法でスワップの数がどのような分布になるかです。

  • 一様交叉:他のスワップとは独立した確率 p
    でスワップされる遺伝子を選択します。つまり、ベルヌーイ実験です。このベルヌーイ実験を、染色体全体に対して、つまりn 個の遺伝子に対して行います。したがって、スワップの数は二項分布に従います。

  • shuffle-cross-over :
    最初に染色体をランダムにシャッフルします (これは主に位置バイアスを回避するために行われます。つまり、染色体内の遺伝子の位置から確率スワップを切り離すためです。均一なケースではこのバイアスを処理します一様な場合との違いは、交差点を1 つだけ選択すると、この交差点の片側にあるすべての要素が交換されるため、任意の数の遺伝子を 1/ の等しい確率で交換することです。 2. したがって、いわゆる分布バイアス、つまりスワップ数が異なる確率も回避します。

于 2016-09-12T18:40:25.200 に答える