遺伝的アルゴリズム

遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。

この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることである。

また、遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。

遺伝的アルゴリズムは一般に以下の流れで実装される。なお、下記では個体数を N, 最大世代数を G と置く。

1.あらかじめ N 個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。

2.現世代に N 個の個体をランダムに生成する。

3.評価関数により、現世代の各個体の適応度をそれぞれ計算する。

4.ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。

4-3.個体を一つ選択してそのままコピーする。

5.次世代の個体数が N 個になるまで上記の動作を繰り返す。

6.次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。

7.3. 以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。

引用元