遺伝的アルゴリズム

遺伝的アルゴリズムとはある問題に対してベターな解を求めていくアルゴリズムです。最適な解、ベストな解を求めていくアルゴリズムではないことに注意してください。優れた個体（解きたい問題に対する解）を次の世代に残し、そうではない個体は採用しない方法で新しい世代を次々に作り解を求めていきます。世代が進むにつれて、個体は問題に対して良くなっていきます。遺伝的アルゴリズムは主に５つのフェーズに分けられます。

1. 初期世代の生成
2. 評価
3. 選択
4. 交叉
5. 突然変異

1. 初期世代の生成

遺伝的アルゴリズムは初期世代を生成するところからスタートします。染色体(Chromosome、解きたい問題に対する解)の数はあらかじめ定めておきます。その染色体は遺伝子(Gene、変数)で特徴付けられます。また遺伝子の数もあらかじめ定めておきます。

2. 評価

評価はフィットネス関数と呼ばれる関数に基づいて行われます。この関数はそれぞれの染色体が解きたい問題に対して、どれだけ適合しているかを示します。またフィットネス関数はそれぞれの染色体に対してフィットネススコアというスコアを与えます。より良いスコアを持つ染色体は次の世代に残る可能性が大きくなります。つまり、生き残る可能性が大きいということです。

3. 選択

選択のフェーズでは、フィットネススコアの良い個体が選ばれ、2つの個体がペア(親)となって交叉が行われ、次の世代に渡されます。

4. 交叉

それぞれのペアを交叉させるために交叉ポイント(Crossover point)がランダムに選ばれ、そのポイントまでペア同士で遺伝子を交換させながら子孫を作ります。

5. 突然変異

遺伝子の値が突然変異によって変わります。突然変異が起こる確率はあらかじめ定めておきます。突然変異のフェーズが終了したら、次の世代が始まり、再び、評価、選択、交叉、突然変異を繰り返して最後の世代までいきます。世代の数はあらかじめ決めておきます。

全体像

世代数を100、個体の数を1500、変数の数を15に設定したときの全体像です。

遺伝的アルゴリズム終了後

最後の世代が終了した後に全ての個体の中から最も優れた個体を採用します。図では、第N世代のグレーの色で示した個体が解きたい問題に対する最も優れた個体(解)です。