遺伝的アルゴリズム
遺伝的アルゴリズムは一般に以下の流れで実装される。なお、下記では個体数を N, 最大世代数を G と置く。
あらかじめ N 個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。
現世代に N 個の個体をランダムに生成する。
評価関数により、現世代の各個体の適応度をそれぞれ計算する。
ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。 個体を二つ選択(選択方法は後述)して交叉(後述)を行う。 個体を一つ選択して突然変異(後述)を行う。 個体を一つ選択してそのままコピーする。
次世代の個体数が N 個になるまで上記の動作を繰り返す。
次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。
3. 以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。
初期収束とは、最初の方の世代で「偶然」他の個体より適応度が圧倒的に高い個体が生まれたとき、その個体の遺伝子が集団中に爆発的に増えて探索がかなり早い段階で収束してしまう現象である。ルーレット選択の設定が甘い場合や、突然変異の効果が上手く表れないときに起こりやすい。
対策としては、ルーレット選択を使う場合の適切な設定や適用する問題に合わせて効果的になるように突然変異の操作を変更したり、突然変異率を増やしたり、または集団の数を増やすなどの設定を行うことで防ぐことができる。しかしながら明確な解決法というものはなく、各パラメータを何度も繰り返し設定しなおすしかない。