遺伝的アルゴリズム(genetic algorithm:GA)
- 2006.03.16 Thursday
- 13:03
自然界の生物の進化においては、ある世代の個体群の中で、環境ヘの適合度の高い個体が優先的に生き残るように再生されるとともに、交配、または交叉(cross-over)や突然変異(mutation)によって新たなつぎの世代の個体群が形成されていく。遺伝的アルゴリズムは、まさに、この進化のメカニズムを使って、解を探索しようとするものである。
遺伝的アルゴリズムは、真の最適解に到達する保証はない。探索される解は、世代数、個体集合の個体数、交配率、突然変異率などの演算のやり方に著しく依存する。しかし、(1)個体の集合から集合へと探索を進めるため初期値に左右され難く、(2)適合度の値を世代ごとに比較するだけで、その微係数などを使わないため目的関数の性質がはっきりわからなくても計算が可能であり、とくに、(3)確率的な遷移ルールにもとづいて演算を進めるので、局所的最適解にとどまらず、大局的最適解を探索できる可能性が高い、などの特長がある。
現実には、厳密解を求めることが不可能であったり、また、いわゆる次善の策を用意しておくことの方が得策だったりすることも多く、このような観点から、遺伝的アルゴリズムは、多くの例題ヘの適用が試みられている。
現代工学の基礎 第12巻