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

概要

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

解のセットをパラメータとして一つのデータにまとめ、これを遺伝子に見立てる。はじめにいくつもの「個体」を用意（ランダムな値で生成することが多い）し、それぞれを評価関数にかけてより適合度の高いと思われる遺伝子を残す。

どの遺伝子を残してどれを捨てるか（選択）を決定する手法はいくつか提唱されているが、最もよく知られるルーレット選択では、適応度に比例して残す確率を決める。適応度が高い遺伝子の配列は次世代に多く残され、低い遺伝子はわずかしか残さない。

現世代の個体群から、生物の生殖や遺伝に相当する操作を行い、同じ数（個体を増やしていく手法もある）の次世代の個体を生成する。二つの遺伝子を同じ長さだけ相手の同じ位置の配列と入れ替える「交叉」、一定の低い確率でランダムに値を変化させる「突然変異」などが行われる。生命の遺伝と異なり、特に成績の良かった個体をそのまま次世代に残す「エリート保存」が行われることもある。

遺伝的アルゴリズムは推論や最適化などの問題に広く応用できる手法だが、良い結果を得るには世代数を大きくする必要があり、問題の種類によっては膨大な計算量が必要となることがある。各世代の個体群は単一の適合度の大小で順位付けするため、複雑な問題の場合は適合度を評価する評価関数を記述するのが難しい場合もある。

(2021.4.18更新)