遺伝的アルゴリズム
遺伝的アルゴリズムでは一般的に次の遺伝的操作が用いられる。
選択(淘汰、再生)
交叉(組み換え)
突然変異
交叉する確率を交叉率、突然変異する確率を突然変異率という。一般には(交叉率)>>(突然変異率)とすることが望ましいとされる。また上記のアルゴリズムの流れからわかるとおり(交叉率)+(突然変異率)+ (再生確率) = 1である必要がある。
一般に、3点以上の交叉点をもつ方法を多点交叉あるいは n 点交叉という。しかしながら一部の問題を除き、多点交叉は二点交叉と下記で述べる一様交叉のどちらかよりも良い値が出ることはほとんどなく、あまり使われていない。
突然変異は生物に見られる遺伝子の突然変異をモデル化したもので、個体の遺伝子の一部を変化させる操作である。局所(的)最適解に陥ることを防ぐ効果がある。
例えば、遺伝子型がビット列の場合は、ある遺伝子座の0と1を入れ換える。数字の場合は乱数と置き換える。他にも遺伝子座の位置を変更するなどの方法がとられる。
突然変異の確率は0.1%~1%、高くても数%である。確率が低すぎると局所(的)最適解に陥りやすくなり、高すぎるとランダム探索に近づいてしまう(解が収束しにくくなる)。
交叉(組み換え)は生物が交配によって子孫を残すことをモデル化したもので、個体の遺伝子の一部を入れ換える操作である。交叉はその性質上、最も重要な遺伝的操作と言うことができる。
交叉のアルゴリズムには次のようなものがある。
例として次の二つの個体を交叉する。
個体A: 0100111010 個体B: 1010101011
Estimation of Distribution Algorithm (EDA)。GAは個体の集合に対して、交叉や突然変異を行い、個体の集合が進化するが、EDA では、個体生成の確率分布を進化させる。アルゴリズムは、Population-based incremental learning (PBIL)など。