遺伝的アルゴリズムとは

遺伝的アルゴリズムとは、生物の進化の過程をモデルに作られた進化的アルゴリズムのひとつです。

確率的探索の一手法であり、1975年に提案されました。遺伝子のようなモデルを用いて、表現したデータ群の中から、評価関数に対して、適応度の高いデータ群を優先的に選択し、交差(組み換え)や突然変異などの遺伝的操作を繰り返しながら最適解を探索します。

データ群をランダムに複数個作成し、現世代とします。現世代の適応度を計算し、選択したデータ群に対して交差、突然変異、複製のいずれかを行います。
選択の方法には、

• 適応度比例
• 期待値
• ランキング
• エリート保存

などの指標を用いた戦略があります。
交差は２種類のデータ群を部分的にシャッフルすることで、単純交差・一様交差・部分一致交差などがあります。突然変異はデータ群の一部を変更します。

このようにして作成された新たなデータ群を次世代とします。次世代のデータ群を現世代と同数個作成します。これらを新たな現世代とし、再び操作を最大世代まで繰り返します。こうして、現世代の中で最も適応度の高いデータ群が最適解となります。

遺伝的アルゴリズムの利点として、評価関数が微分可能かどうか、単峰性かどうかなどが定かでない場合でも適用できることです。
一方、遺伝的アルゴリズムの問題点としては、初期パラメータの設定によって最適解の探索がうまくいかないことが挙げられます。
例えば、最初の世代で適応度が高いデータ群が生成されることで、探索が比較的初期に収束してしまうことがあります(過剰適合)。
過剰適合は、選択の方法や突然変異の調整によって改善されます。また、適応度が低いデータが適応度が高いデータ群に入り混じったまま生存してしまうことがあります(ヒッチハイク)。ヒッチハイクに対しては、1/2の確率でデータを入れ替える一様交叉が有効です。

現実世界には、解の評価は可能でも、最適解が不明な問題(NP完全問題)は多数存在しています。
そのような解法が比較的確立されていない問題に対して、遺伝的アルゴリズムは威力を発揮します。巡回セールスマン問題などの組合せ最適化問題に適用することができます。

直観的なアルゴリズムながら、遺伝的アルゴリズムの応用分野は幅広く、

• 制御・設計などの工業分野
• 機械翻訳
• 人工生命
• バイオインフォマティクス

などがあります。身近な活用事例では、N700系東海道新幹線の車両先頭部の設計デザインに用いられています。