用語解説　第93回テーマ：　遺伝的アルゴリズム（GA：Genetic Algorithm）

宮坂 史和 （大阪大学）

1. はじめに

遺伝的アルゴリズム（以下GA と略す）とは，1975 年にミシガン大学のJohn Holland によって提案された解探索手法である。本手法は，生物の進化の仕組みを模倣する形で，与えられた問題に対する最適な解を探索する。

本手法は，解探索に用いるパラメータを染色体の集団として模倣し，これらに対して比較的単純な手順により最適な解パラメータを求める手法となっている。

2. GA の手順

GA では，図1 に示すように解探索のためのパラメータを遺伝子の集まりであるとし，その遺伝子一つ一つに0 または1 の情報を割り当てる。そして各個体の遺伝子情報をパラメータとして作業者が設定した評価関数の評価値を算出し，評価値の優位な個体を選抜し，次世代への親とする。

図1　交叉手順例

ここで選出された親個体群から次世代の子個体を作出する手順として“交叉”や“突然変異”等の操作が挙げられる。“交叉”は一例として図1 に示す通り遺伝子の集まりを前後二つの集団に分割し，二つの親世代の遺伝子情報を交換するものである。これ以外にも“多点交叉”や“一様交叉”等があり，交叉手法の取り方で効率が変化する。また“突然変異”は，多峰性を持つような解空間において最適解を探索する過程で局所解に陥らないようにするために行う操作である。親世代から子世代へ遺伝子情報を引き継ぐ際に，一定の確率でランダムに遺伝子情報を変化させる。一般的に良く用いられている最急降下法等の最適化手法では解空間の単峰性の保証が必要であったが，GA ではこの“突然変異”の操作により多峰性の問題にも対応が可能となっている。ただし局所解に陥らない保証とはなっていないことに注意が必要である。

【電気学会論文誌B，138巻，12号，2018に掲載】