遺伝的アルゴリズムとは：遺伝的アルゴリズムの特徴から遺伝子の交叉と突然変異について解説

遺伝的アルゴリズム（G.A.:Genetic Algorithm）とは、1975年にミシガン大学の John Henry Holland によって提案された、生物の進化論を模した最適解を探索する最適化アルゴリズムです。

遺伝的アルゴリズムでは、データを遺伝子で表現します。プログラムでは「個体」を複数用意し、適応度がより高い個体を優先的に選択して交叉・突然変異などの操作を繰り返して解を探索します。
ここでは、目的関数Fxの最大化（局所解が複数存在）における遺伝的アルゴリズム(GA)のイメージを例にとって説明します。

設計空間全体に偏りなく個体（計算点）を発生します。

各個体の適合度を評価し、適合度 (目的関数の値) の高いものが生き残り、次の 世代の親となる確率が高くなります。

生き残った個体に交叉、突然変異の操作を行い、子個体を発生します。
適合度の高い遺伝情報を掛け合わせることで、より適合度の高い個体が期待できます。

• 長所
  • 様々な最適化問題に適用できる汎用的なアルゴリズム
  • 初期点不要（初期点に依存しない）
  • 前世代の情報を元に次世代を生成する反復形式
  • 収束条件は局所的最適化手法とは異なる
      例
        指定した計算回数に達したとき
        目的関数の改善が見られないとき
        個体群が設計空間の特定箇所に収束したとき
• 短所
  • 計算回数が比較的多い
  • 問題によって適切なオプション（交叉確率や突然変異率など）が異なる

基本的な遺伝的アルゴリズムでは設計変数をコード化して遺伝子を形成します。

交叉とは、遺伝子を一部交換することです。親個体の遺伝情報を掛け合わせてより良い個体を生成します。その結果、親に似た個体が生成されます。

突然変異とは、遺伝子のランダムな変動を指します。突然変異によって探索空間内の探索範囲を限定してしまうことを回避できます。また、親にはない遺伝情報を与えることで、局所解から脱出します。