遺伝的アルゴリズムとは？わかりやすく解説

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

概要

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

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

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

アルゴリズムの流れ

遺伝的アルゴリズムは一般に以下の流れで実装される。なお、下記では個体数を N, 最大世代数を G と置く。

あらかじめ N 個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。
現世代に N 個の個体をランダムに生成する。
評価関数により、現世代の各個体の適応度をそれぞれ計算する。
ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。
1. 個体を二つ選択（選択方法は後述）して交叉（後述）を行う。
2. 個体を一つ選択して突然変異（後述）を行う。
3. 個体を一つ選択してそのままコピーする。
次世代の個体数が N 個になるまで上記の動作を繰り返す。
次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。
3. 以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。

遺伝的操作

遺伝的アルゴリズムでは一般的に次の遺伝的操作が用いられる。

選択（淘汰、再生）
交叉（組み換え）
突然変異

交叉する確率を交叉率、突然変異する確率を突然変異率という。一般には（交叉率）>>（突然変異率）とすることが望ましいとされる。また上記のアルゴリズムの流れからわかるとおり（交叉率）+（突然変異率）+ (再生確率) = 1である必要がある。

選択

選択は生物の自然淘汰をモデル化したもので、適応度にもとづいて個体を増やしたり削除したりする操作である。選択のアルゴリズムには次のようなものがある。

ルーレット選択

ルーレット選択は個体 i を選ぶ確率を p_i と置いたとき、

p_{i}={\frac {f_{i}}{\sum _{k=1}^{N}f_{k}}}

カテゴリ（最適化 • アルゴリズム） • ソフトウェア

[1]

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法拡張ラグランジュ関数法逐次二次計画法逐次線形計画法

遺伝的アルゴリズムとは？わかりやすく解説