交叉アルゴリズム



 交叉とは、2つの染色体のある位置で、お互いに遺伝子を交換する作業である。

例えば、染色体が5つの遺伝子からなる場合(下図参照)を考える。交叉位置

は一般に乱数に基づき決定される。下図の場合には左から3番目と4番目の間で

交叉が行われる。上の染色体の4番目と5番目の遺伝子が下の染色体の4番目と

5番目の遺伝子になり、下の染色体の4番目と5番目の遺伝子が上の染色体の遺

伝子となっている。

  解くべき問題によっては交叉位置は中央一点だけでも良い場合もある。交叉は

ルーレット選択方式では交叉に選ばれる染色体が優秀な染色体である場合が多い。

このため、交叉によって次第に優秀な染色体の遺伝子並び(スキーマ)が集団全

体に拡散していく。これはつまり、次第に最高値周辺を重点的に調査することに

等しい。

  選択された染色体の交叉は一般に交叉確率に基づいて確率的に実施する。

  多峰性問題では、交叉が逆に局所最適解への引き寄せの役割を果たすことがあ

り、交叉確率を高くしすぎると逆効果となる場合もないわけではない。これは

ケースバイケースであり、パラメータの調整が必要である。


GAの説明に戻る