遺伝的アルゴリズム 【genetic algorithm】

遺伝的アルゴリズムとは、プログラムによって問題に対する最適な解を求める手法の一つで、生物の進化における遺伝のメカニズムに似た操作を取り入れたアルゴリズム。生成論的アルゴリズムとも呼ばれる。1975年に米ミシガン大学のJohn Holland氏によって提唱された。

　解のセットをパラメータとして一つのデータにまとめ、これを遺伝子に見立てる。はじめにいくつもの遺伝子を用意し(ランダムな値に設定されることが多い)、それぞれを評価関数にかけてより適合度の高いと思われる遺伝子を残す。残った遺伝子を複数掛け合わせて(通常は2つの遺伝子を半分ずつつなげる)新しい遺伝子をつくり、これも同様に評価する。この操作を何世代も繰り返すことにより、次第に最適な解に近づけていく手法である。新しい遺伝子を作る際、低い確率でランダムにデータを変化させる「突然変異」のメカニズムも組み込まれる。

　探索や最適化の問題に広く応用できる手法だが、対象となる問題の何を遺伝子としてパラメータ化するか、どのような評価関数で適合度を評価するかによって、良好な結果が得られない場合もある。