AI研究所 - AI(人工知能)に脅かされないために、AI(人工知能)を作る側の人間になる -

HOME  >  AI(人工知能)用語集  >  遺伝的アルゴリズム

遺伝的アルゴリズムとは

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


データ群をランダムに複数個作成し、現世代とします。現世代の適応度を計算し、選択したデータ群に対して交差、突然変異、複製のいずれかを行います。
選択の方法には適応度比例期待値ランキングエリート保存などの指標を用いた戦略があります。
交差は2種類のデータ群を部分的にシャッフルすることで、単純交差・一様交差・部分一致交差などがあります。突然変異はデータ群の一部を変更します。

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

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

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

直観的なアルゴリズムながら、遺伝的アルゴリズムの応用分野は幅広く、制御・設計などの工業分野、機械翻訳、人工生命、バイオインフォマティクスなどがあります。
身近な活用事例では、N700系東海道新幹線の車両先頭部の設計デザインに用いられています。


参考になったら「いいね!」と「シェア」をお願いします!!

このエントリーをはてなブックマークに追加

AI(人工知能)入門セミナー開催中
AI(人工知能)入門セミナー AI(人工知能)入門セミナー IoT入門セミナー

AI入門ブログの中の人

AI研究所 研究スタッフ
通称:マサミ
アメリカ・サンフランシスコにある情報メディアの専門学校を卒業。大手金融会社での事務経験を経て、2016年9月よりAI研究所に入所。見習い研究員として、AI技術を日々勉強中。

Facebookページ