５．ＧＡの様々な手法

---

選択の手法

ルーレット選択

各個体の適合度から選択確率を変え、この確率に沿ってルーレットを回すように選択を行う方法。適合度の高い個体ほど残りやすくなりますが、適合度の低い個体でもそれなりの確率で生き残れます。SGAで採用されています。

図５．１　ルーレット選択

期待値選択

適合度から、期待値を求め、ここから保存される個体数を決定します。ルーレット選択のように乱数を使うと、選択結果にある程度揺らぎが生じますが、このような揺らぎを防ぎたいときなどに有効です。

適合度	6	1	10	11	17	32	4	12	5	2
期待値	0.6	0.1	1.0	1.1	1.7	3.2	0.4	1.2	0.5	0.2
再生数	1	0	1	1	2	3	0	1	1	0

図５．２　期待値選択

ここで、再生数というのが選択されて残る個体の個数となります。

ランキング選択

適合度の高さから、大きい順にランキングを決め（順位付けをして）その順位に応じて、保存される個体数をあらかじめ決めておいた表から割り振ります。この方法は適合度にあまり差が出ないときに有効です。

ランク	1	2	3	4	5	6	7	8
再生数	3	3	2	2	1	1	0	0

図５．３　ランキング選択

トーナメント選択

ランダムにトーナメントを作り、各組ごとに大きいほうを残します。この作業を繰り返すことで必要な個体数だけ確保します。

図５．４　トーナメント選択

エリート保存

適合度の高い個体は無条件に残す方法です。選択を行う前に、適合度の高い個体はよけておいて、残りの個体群について何らかの方法で選択を行い、最後に保存しておいたエリート個体を戻します。

交叉

１点交叉

交叉点をランダムに選び、その点を境に、後ろを入れ換えます。SGAで採用されています。

多点交叉

複数の交叉点を設定し、交叉点ごとに二つの個体を入れ換えます。

一様交叉

マスクパターンをランダムに生成し、２つの親個体に対し、そのマスクのビットが１なら親１を、ビットが０なら親２をコピーする子個体をその逆をコピーする子個体を生成します。

図５．５　交叉