進化的アルゴリズム
| 人工知能 | ||||
|---|---|---|---|---|
 | ||||
| 研究手法
| ||||
| 歴史とできごと
| ||||
| 法規制
| ||||
| 著作
| ||||
| 一覧
| ||||
| 用語集
| ||||
 カテゴリ | ||||
|
進化的アルゴリズム（しんかてきアルゴリズム、evolutionary algorithm、EAと略記）は進化的計算の一分野を意味し、人工知能の一部である。個体群ベースのメタヒューリスティックな最適化アルゴリズムの総称である。そのメカニズムとして生殖、突然変異、遺伝子組み換え、自然淘汰、適者生存といった進化の仕組みに着想を得たアルゴリズムを用いる。最適化問題の解の候補群が生物の個体群の役割を果たし、コスト関数によってどの解が生き残るかを決定する。それが繰り返された後、個体群の進化が行われる。
EAの例を以下に示す。これらの技法は本質的には同様だが、実装の詳細は異なっており、適用される問題の分野が異なる。
- 遺伝的アルゴリズム
- これは EA の中でも最も一般的な手法である。問題の解を探索するにあたって数値の列を使用し（2進数を使うのが古典的だが、解決すべき問題に合わせて最適な形式が選択され、2進数になるとは限らない）、選択と変異に加えて事実上常に組み換えオペレータを適用する。
- 遺伝的プログラミング
- 基本は遺伝的アルゴリズムと同じだが、解は木構造の形式で表し数式やプログラムコードを表現する。適応度関数はその計算能力などで評価する。
- 進化戦略
- 実数のベクトルで解を表し、探索を行うと同時に自己変異用のパラメータも更新していく。
- 進化的プログラミング
- 解の適応度関数に集団中におけるその解の優位性を表した確率的な関数を用いる。
これらは適応度地形にいかなる仮定も持たないので、進化的アルゴリズムがあらゆるタイプの問題でうまく機能すると信じられている（ただし、ノーフリーランチ定理に注意）。このことは、工学、芸術、生物学、経済学(進化経済学)、遺伝学、オペレーションズリサーチ、ロボット工学、社会科学、物理学、化学などの分野で成功を収めていることで裏付けられている。
数学的なオプティマイザとしての使用法は別として、進化的計算とアルゴリズムは進化と自然淘汰の仮説の正当性を実験検証するのにも使われてきた。特に人工生命の分野がそれである。進化的アルゴリズムの手法は生物の進化モデルに適用する際には一般に小進化に限定される。もっとも、TierraやAvidaのようなコンピュータシミュレーションは大進化のモデル化を意図している。
進化的アルゴリズムの制限として、遺伝子型と表現型の区別が不明確という点が挙げられる。実際、受精した卵細胞は胚発生という複雑なプロセスを経て円熟した表現型になる。この間接的エンコーディングによって、間違った突然変異を低減させるなどの遺伝の頑強化がなされていると考えられ、有機体の進化可能性も改善される。人工胚発生や人工発生システムの研究では、これらの懸念への対処が最近の仕事となっている。
関連技術
- 差分進化 - ベクトルの差分に基づくもので、最適化問題を解くのに適している。
- 粒子群最適化 - 動物の群れのふるまいに基づくもので、これもまた最適化問題を解くのに適している。
- 蟻コロニー最適化 - 蟻の群れが経路上のフェロモンでコミュニケーションすることに基づくもので、組合せ最適化問題を解くのに適している。
- シミュレーティド・エボリューション - 生物一体の進化を模倣している。
関連項目
外部リンク
- Special Interest Group for Genetic and Evolutionary Computation of the ACM（英語）
- Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com.
- Global Optimization Algorithms - Theory and Application, free e-book
| ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 非線形(無制約) |
|  | ||||||||||||
| 非線形(制約付き) |
| |||||||||||||
| 凸最適化 |
| |||||||||||||
| 組合せ最適化 |
| |||||||||||||
| メタヒューリスティクス | ||||||||||||||
| ||||||||||||||
