📂最適化理論

遺伝的アルゴリズムとは何か?

定義 ¹

$$ \argmax_{\mathbf{x} \in X} f \left( \mathbf{x} \right) $$ 目的関数 $f : X \to \mathbb{R}$ を最大化する 最適化問題において，次の三つの操作^operationを反復する方法を 遺伝的アルゴリズム^{genetic algorithm}という。

• 自然選択^selection: 現在の解集合から優れた解を選び次世代の解集合を構成する。
• 交叉混合^crossover: 解集合から複数の解を選び一部の情報を交換して新しい解を生成する。
• 変異^mutation: 解集合の一部の解の情報をランダムに変更して多様性を確保する。

説明

遺伝的アルゴリズムはダーウィンの進化論における 適者生存^{survival of the fittest}に着想を得た 個体群メソッドであり，各個体は 染色体^chromosomeと呼ばれる ベクトル $\mathbf{x} \in X$ で表現され，$f \left( \mathbf{x} \right)$ のように評価されその関数値自体を 適合度^fitnessとする。進化論の比喩において $f$ は環境^enviromentそのものを意味し，我々が求めるのはこの環境で最もよく生き残る、すなわち $f$ が最大となる $\mathbf{x}$ を見つけることである。

自然選択

進化論で自然選択を説明するのと同様に，進化は何らかの意図をもって器官や生理を発達させるのではなく，単に適合度の低い個体が淘汰され適合度の高い個体が生き残ることが反復されて起こる現象である。

遺伝的アルゴリズムにおける自然選択とは単に解集合から適合度が低い解が除去されるようにする操作として実装され，根本的に遺伝的アルゴリズムを動作させる原動力でもある。

交叉混合

最適化の観点から交叉混合とは解空間全体を広く探索するためのグローバル探索法であり，漸進的な変化ではなく急激な変化を通じて局所最適解への陥りを防ぐ役割を果たす。これは実際の自然でも同様であり，主に寄生に対する抵抗戦略として説明される有性生殖が爆発的な多様性を確保するのに有利であるという点と文脈を同じくする。

変異

変異は染色体に小さな変化を与える形で実装され，交叉混合とは逆に局所探索法の性格を持つ。変異なしに自然選択だけを反復するならば，実質的に世代を重ねる必要がなく初代で最終的な解が決定されてしまうのと同じであり，失敗を顧みず少しずつ変化を与えてより良い解を探そうとするものである。