遺伝的アルゴリズム概要
遺伝的アルゴリズム（Genetic Algorithms : GAs）とは，生物が環境に適応して進化していく過程を工学的に模倣した学習的アルゴリズムである．
自然界における生物の進化過程では，ある世代を形成している個体の集合の中で環境に適応した個体が高い確率で生き残り，次の世代に子を残す．このメカニズムをモデル化し，環境に対して最もよく適応した個体，すなわち目的関数に対して最適値を与えるような解を求めようというのがGAの概念である．
GAでは，個体（Individual）は設計変数の値がコーディングされた染色体（Chromosome）と呼ばれる文字列上で表現され，この染色体をデコーディングすることにより設計変数を読み出し，目的関数の値を計算する．このとき，染色体の構造のことを遺伝子型（Geno Type），これによって定まる個体の形質を表現型（Pheno Type）と呼ぶ．また，個体の集団のことを母集団（Population）と呼ぶ．GAはこの母集団に対して選択（Selection），交叉（Crossover），突然変異（Mutation）などの遺伝的操作を繰り返し行うことによって解探索を行う．
遺伝的アルゴリズムの流れ
GAの解探索の流れについて説明する．右下図は一般的なGAのフローチャートである．
- Initialization : 母集団の初期化
あらかじめ設定された数だけ個体を生成する．生成した個体の数のことを母集団サイズ（Population Size）や単に個体数（Number of Individuals）と呼ぶ．
- Evaluation : 評価
各個体の持つ染色体を問題空間にデコードして解を求める．ここで求めた解のことを評価値（Evaluation Value）という．
- Selection : 選択
生物の適者生存を模倣したものである．この操作では，まず各個体の評価値から次世代への生き残りやすさを求め，これに基づいて次世代の母集団を形成する．この次世代への生き残りやすさのことを適合度（Fitness）と呼ぶ．
- Crossover : 交叉
生物の有性生殖を模倣したものである．この操作により，個体間で染色体情報が交換される．最適解を表す個体の一部分を持った個体同士が交叉すればより最適解に近い個体が得られる可能性が高くなる．個体集団のうち何割の個体が交叉するかを交叉率（Crossover Rate）と呼ばれるパラメータによって定める．
- Mutation : 突然変異
染色体は遺伝子（Gene）を格納する複数の遺伝子座（locus）から構成され，遺伝子座に入りうる遺伝子のことを対立遺伝子という．突然変異とは，染色体上の遺伝子座の遺伝子を別の対立遺伝子に置き換える操作のことであり，自然界におけるDNA複写の際に起こるコピーミスにあたる．染色体のうち何割の遺伝子座が変異するかを突然変異率（Mutation Rate）と呼ばれるパラメータによって定める．
- Terminate Check : 終了判定
あらかじめ定められた終了条件に基づいてGAを終了させる．
遺伝的アルゴリズムの特徴
Goldbergによれば，GAは従来の最適化手法と比較して次の４つの特徴を持つとされている[1]．
- 設計変数を直接操作せずにコード化した状態で扱う
- 一点探索ではなく，多点探索である
- サンプリングによる探索で，ブラインドサーチである
- 決定論的規則ではなく，確率的オペレータを用いる探索である
より詳しい研究内容
我々は遺伝的アルゴリズムの持つ特徴を利用して，新たなアルゴリズムの開発，実問題への応用などの研究を行っている．
参考文献
[1] D.E.Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning"，Addison-Wasley Publishing Company，1989