遺伝的アルゴリズム詳細 | ASAHIネット

遺伝的アルゴリズム（いでんてき-、Genetic Algorithm、GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。

概要

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

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

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