遺伝的アルゴリズム概要

遺伝的アルゴリズム(Genetic Algorithms : GAs)とは,生物が環境に適応して進化していく過程を工学的に模倣した学習的アルゴリズムである.

自然界における生物の進化過程では,ある世代を形成している個体の集合の中で環境に適応した個体が高い確率で生き残り,次の世代に子を残す.このメカニズムをモデル化し,環境に対して最もよく適応した個体,すなわち目的関数に対して最適値を与えるような解を求めようというのがGAの概念である.

GAでは,個体(Individual)は設計変数の値がコーディングされた染色体(Chromosome)と呼ばれる文字列上で表現され,この染色体をデコーディングすることにより設計変数を読み出し,目的関数の値を計算する.このとき,染色体の構造のことを遺伝子型(Geno Type),これによって定まる個体の形質を表現型(Pheno Type)と呼ぶ.また,個体の集団のことを母集団(Population)と呼ぶ.GAはこの母集団に対して選択(Selection),交叉(Crossover),突然変異(Mutation)などの遺伝的操作を繰り返し行うことによって解探索を行う.

GAの概念図

遺伝的アルゴリズムの流れ

GAの解探索の流れについて説明する.右下図は一般的なGAのフローチャートである.

GAの流れ

遺伝的アルゴリズムの特徴

Goldbergによれば,GAは従来の最適化手法と比較して次の4つの特徴を持つとされている[1]

より詳しい研究内容

我々は遺伝的アルゴリズムの持つ特徴を利用して,新たなアルゴリズムの開発,実問題への応用などの研究を行っている.

参考文献

[1] D.E.Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning",Addison-Wasley Publishing Company,1989