なぜ、クロスオーバーは微分進化において有益なのですか？

Question

私がやっていたサイドプロジェクトに差分進化アルゴリズムを実装しました。クロスオーバ・ステップにはパラメータの選択肢（クロスオーバ確率など）が多かったようですが、私はそれをスキップして突然変異を使用することにしました。この方法はうまくいくように見えましたが、クロスオーバーを導入するとパフォーマンスが向上するかどうかは不明です。

メイン質問：差動進化にクロスオーバーを導入する背景には何がありますか？クロスオーバーを導入することで純粋な突然変異を凌駕するおもちゃの例を提供できますか？

私の直感は、クロスオーバが2次元で次のようなものになるということです。ふと 私たちは2つの親ベクトル（赤）を持っています。均一なクロスオーバは、青の点の1つで新しいトライアルベクタを生成することができます。

私は探検のこの種のは有益であると期待される理由はわかりません。実際、高性能ソリューションがある種の線形傾向に従うと、パフォーマンスが悪化する可能性があるようです。下の図では、赤い点が現在の母集団であり、最適解が右下隅に向いているとします。人口は、右上と左下のコーナーが悪い解決策を生み出すように谷を下っています。左上隅には「大丈夫ですが最適ではない解」が生成されます。均一なクロスオーバが改善の方向にと直交するである試行（青色で）を生成することに注目してください。私はクロスオーバー確率1を使用し、突然の突然変異を無視して私のポイントを示しました（コード参照）。この状況は、最適化の問題で非常に頻繁に発生する可能性があると思いますが、何かを誤解する可能性があります。

注：上記の例では、私は暗黙のうちに、この空間全体に（均一に）人口がランダムに初期化されたと仮定していますし、中央の谷（トップダウン正しい解に収束し始めています左から右下）。

このおもちゃの例は凸であるため、微分の進化は適切な技術でさえありません。しかし、このモチーフがマルチモーダルのフィットネス・ランドスケープに埋め込まれていれば、クロスオーバーが有害であるように思えます。クロスオーバは有益な探査をサポートしていますが、私はこの特定の方向で探検することをなぜ選択するのかはわかりません。上記の例のための

Rコード：

N = 50 

x1 <- rnorm(N,mean=2,sd=0.5) 
x2 <- -x1+4+rnorm(N,mean=0,sd=0.1) 
plot(x1,x2,pch=21,col='red',bg='red',ylim=c(0,4),xlim=c(0,4)) 

x1_cx = list(rep(0, 50)) 
x2_cx = list(rep(0, 50)) 
for (i in 0:N) { 
    x1_cx[i] <- x1[i] 
    x2_cx[i] <- x2[sample(1:N,1)] 
} 

points(x1_cx,x2_cx,pch=4,col='blue',lwd=4) 

フォローアップの質問：クロスオーバーは、特定の状況で有益である場合は、あなたの特定の問題は、クロスオーバーから恩恵を受けるかどうかを判断するに賢明なアプローチ）があります、およびb）アルゴリズムを最適化するためにクロスオーバパラメータを調整する方法は？

関連stackoverflowの質問（私はインスタンスのおもちゃの例を、より具体的な何かを探しています）：what is the importance of crossing over in Differential Evolution Algorithm?

同様の問題ではなく、具体的な進化を差動に：Efficiency of crossover in genetic algorithms

Answer 1

は、私は特にないですDEアルゴリズムの詳細に精通していますが、一般にクロスオーバーのポイントは、高い適応度を持つ2人の非常に異なる個人がいる場合、どちらかと特に似ていることなく中間にある子孫を生み出すということです。突然変異は、個体群の残りの部分を考慮に入れずに、各個体の局所的な近傍を探索するだけである。ある高次元のベクトル空間でゲノムを点と考えると、突然変異はランダムな方向にシフトします。したがって、突然変異は小さなステップを取る必要があります。ランダムポジションよりもはるかに優れている場合、進化したゲノムにエントロピーを導入するだけなので、ランダムな方向の長いステップは事態を悪化させることがほぼ確実です。あなたは、ある親から別の親へのステップとしてクロスオーバーを考えることができます。他の親もランダムよりも優れているので、その方向でもっと長いステップを取ることがより有望です。これにより、フィットネス景観の有望な部分の探索をより迅速に行うことができます。

実際の生物において、ゲノムは、しばしば、互いに依存する遺伝子が同じ染色体上で互いに接するように編成される。これは、クロスオーバが相乗的な遺伝子の組み合わせを破壊する可能性が低いことを意味する。実際の進化は、これを達成するために遺伝子を実際に動かすが（個々の遺伝子の進化よりもはるかに遅いが）、ゲノムの高次構造（DNAの3次元形状）は、特に敏感な領域での交差を防ぐために進化する。これらのメカニズムは、進化的アルゴリズムではほとんどモデル化されていませんが、お互いに接近する可能性のある遺伝子を配置するようにゲノムを注文すれば、クロスオーバーからさらに逃れることができます。

Answer 2

ダニエルによれば、クロスオーバーは問題の景色全体に大きなステップを取る方法であり、単一の突然変異がそうすることができないことを地元の最大値から逃れることができます。それが適切か否か

遺伝子型か、問題空間の複雑さに依存します - >表現型の式が働くが（関連遺伝子が一緒に近くなります）、など

より形式的にこれはという概念でありますローカル検索アルゴリズムでは「接続性」があり、ローカル検索近隣が十分に大きいので、ローカルミニマムから逃れる十分な演算子を提供します。

Answer 3

いいえ、クロスオーバは役に立ちません。そこに私はそれを言った。 ：P

私はクロスオーバーの必要性を見いだせませんでした。人々はそれがある種の魔法をすると思っているようです。しかし、単純な突然変異よりも有用なことはしません（そしてできません）。大きな突然変異を用いて問題空間全体を探索することができ、小さな突然変異を用いてニッチを利用することができる。

私が読んだすべての説明は（それを軽く置くために）不満足です。クロスオーバはアルゴリズムを複雑にするだけです。できるだけ早くドロップしてください。あなたの人生はよりシンプルになります。 .... 私見では。