進化的アルゴリズム（EA）は、生殖、突然変異、組換え、選択などの生物学的進化のメカニズムに着想を得た、集団ベースのメタヒューリスティック最適化手法の一種である。正確な解法や満足な解法が未知である困難な最適化問題に対して、近似解を見つけるために使用される。進化的計算および計算知能の一部として、EAは候補解の集団を操作し、適応度関数を用いてその品質を評価し、進化的演算子を反復的に適用して世代を重ねるごとに集団を改善する。その主な利点は、基礎となる適応度景観についてほとんど仮定を置かないことであり、幅広い問題に取り組むことを可能にするが、その計算複雑性はしばしば適応度評価のコストに起因する。
一般的なアルゴリズム
典型的な進化的アルゴリズムは、以下の反復プロセスに従う：
- 個体の初期集団（第一世代）をランダムに生成する。
- 集団内の各個体の適応度を評価する。
- 目標が達成されたかどうかを確認し、達成されていれば終了する。
- 個体を親として選択し、できれば適応度が高いものを選ぶ。
- 交叉（生殖を模倣）と任意の突然変異を通じて子孫を生成する。
- 子孫に突然変異操作を適用する。
- 置換用の個体を選択し、できれば適応度が低いものを選んで、次世代を形成する。
- ステップ2に戻り、終了まで繰り返す。
この一般的な枠組みは、各々が特定の表現と演算子を持つ様々なEAタイプに適応される。
進化的アルゴリズムの種類
遺伝的表現と実装詳細が異なるいくつかのEA変種が存在する：
- 遺伝的アルゴリズム（GA）：最も一般的なタイプであり、解は数値の文字列（しばしばバイナリ）として表現される。組換えや突然変異などの演算子が適用される。GAは最適化問題で広く使用されている。
- 遺伝的プログラミング（GP）：解はコンピュータプログラムであり、適応度は計算問題を解く能力によって決定される。変種には、デカルト遺伝的プログラミング、遺伝子発現プログラミング、文法的進化、線形遺伝的プログラミング、多重表現プログラミングが含まれる。
- 進化戦略（ES）：1960年代から1970年代にインゴ・レヒェンベルク、ハンス＝パウル・シュヴェーフェルらによって開発され、数値および工学的最適化に焦点を当てる。実数値ベクトルを操作し、突然変異、組換え、および決定的選択を使用する。特徴的な点は、突然変異分布の自己適応であり、(1+1)-ES、(μ, λ)-ES、(μ+λ)-ESなどの形式がある。後の発展には、共分散行列適応（CMA-ES）や自然進化戦略が含まれる。
- 差分進化（DE）：ベクトル差分に基づき、主に数値最適化に適している。
- 進化的多目的最適化：複数の競合する目的を持つ問題にEAを拡張し、パレートフロント上のトレードオフ解を近似する集団を維持する。
- 共進化的アルゴリズム：解は他の解との相互作用に基づいて評価され、競合または協力することができる。動的または競争的な適応度景観に有用である。
- ニューロ進化：ゲノムが人工ニューラルネットワークを表し、構造と接続重みを直接的または間接的に符号化する。
- 学習分類子システム（LCS）：解は分類子（ルール）の集合である。ミシガン型LCSは個々の分類子を進化させ、ピッツバーグ型LCSは分類子集合の集団を進化させる。適応度は強化学習または教師あり学習を通じて決定される。
- 品質多様性（QD）アルゴリズム：高品質で多様な解を同時に目指し、問題空間全体にわたって幅広い解を探索する。
理論的背景
ノーフリーランチ定理
最適化のノーフリーランチ定理は、すべての可能な最適化問題を考慮すると、すべての最適化戦略は同等に効果的であると述べている。これは、いかなる進化的アルゴリズムも、すべての問題にわたって他のものより根本的に優れているわけではないことを意味する。しかし、実際には問題の集合は制限されており、EAは適切な表現や演算子の選択など、問題固有の知識を活用することで改善できる。
計算複雑性
ほとんどの実応用では、EAの計算複雑性は主に適応度関数評価のコストにより、重要な要因となる。適応度近似技術はこの問題を軽減できる。興味深いことに、単純なEAが複雑な問題を解くことがしばしばあり、アルゴリズムの複雑性と問題の複雑性の間に直接的な関連がないことを示唆している。
応用と限界
進化的アルゴリズムは、工学設計、スケジューリング、機械学習（例：ニューロ進化）、多目的最適化など、多様な分野に適用されている。探索空間が大きく、非線形であるか、または十分に理解されていない場合に特に価値がある。しかし、その性能はパラメータ調整と問題表現に依存する。EAの技術は、生物学的微視的進化や細胞プロセスのモデル化にも使用されるが、限界がある。