📂最適化理論

遺伝的アルゴリズムにおけるクロスオーバーミキシングとは何ですか？

定義

遺伝的アルゴリズムで 交叉混合^crossoverとは 複数の個体の特徴を混ぜ合わせて新しい解を作る演算を指す。

説明 ^{1 2}

遺伝的アルゴリズムでの交叉混合、また短く 交雑 は 自然選択された個体の形質を混ぜて新しい子世代の個体を生成する方式だ。これは自然に起こる有性生殖のメカニズムに着想を得たもので³、解空間を丹念に探索することを放棄しても、多様な試行を通じてより良い解を見つけることを目的とする。

どうしても淘汰されなかった親なので適合度の高い特徴を伝える可能性が高い一方、あまりにエリートだけが回ると個体群の多様性が低下し無駄な計算に没頭するのを防ぐ役割もある。

点交叉

点交叉^{point crossover}はクロモソームで表現される解の特定の位置をランダムに選び、そこを境界にして親の形質を混ぜる。1点だけ選ぶ場合は実装がずっと簡単だが親のどちらかに偏った子が生じることがあり、2点を選ぶと実装自体はやや面倒になるがより均等に混ざった子が得られる。

均等交叉

均等交叉^{uniform crossover}は $p$ の確率で父、 $1-p$ の確率で母の形質を選んで子の形質を構成する。普通は $p = 0.5$ にしておき、子は親の形質を均等に受け継ぐ。実装も容易で偏りもなく交叉の趣旨もよく表現しているが、「あまりにも常識外れの解」が出る可能性が高い。

内挿交叉

$$ \mathbf{x} \gets p \mathbf{x}_{a} + (1 - p) \mathbf{x}_{b} $$ 解空間 $X$ が ベクトル空間であれば、父と母の解をそれぞれ $\mathbf{x}_{a} , \mathbf{x}_{b} \in X$ とすると上のように二つの解の中間点あたりに子を作ることもできる。これを 内挿交叉^{intermediate crossover}という。