📂最適化理論

遺伝的アルゴリズムにおけるエリート主義

定義 ^{1 2}

遺伝的アルゴリズムにおける エリート主義^elitismとは、自然選択が起こる各世代ごとに最も適合度が高い個体を数個、次世代へ無条件で渡す戦略を指す。

説明

エリート主義は自然選択でいう ランク選択^{rank selection}を極端化したものと見なせ、確率的要素なしに条件を満たす一部の個体を次世代へ渡す 切断選択^{truncation selection}の別名ともいえる。エリート主義を採用した遺伝的アルゴリズムでは、世代に伴う目的関数の形状は単調関数の形になる。

意外と最適化問題において「歴史上最も優れていた」解を失うことはよくあり、これは勾配降下法でも同様だ。例えば学習中にかなり早いタイミングで最良の解を得たが、エポックを最後まで回すとオーバーフィッティングが生じて最終的な解がそれより劣る場合がそれに当たる。もちろん通常はチェックポイントを置いて最良の解を保存することで回避できる。

一方、遺伝的アルゴリズムにおけるエリート主義はチェックポイントとして単に継承されるだけでなく、進化の過程で解集合に継続的に影響を与える点が異なる。やはり子世代はエリート親に似た遺伝型を持ち、実際に子も高い適合度を持つ確率が高いため次世代にもその遺伝子が伝わり続ける可能性が大きいからだ。個体群法の観点から見ると、局所最適解近傍をもう少し綿密に探索する意図があると見なせる。