遺伝的アルゴリズム

遺伝的アルゴリズム (GA = Genetic algorithm) は DNA の進化などにヒントを 得て考え出された集団最適化法の一つであるが，ここでは今まで述べてきた 方法との関連を明らかにしておく．

遺伝的アルゴリズムは基本的には，$N$ 個の集団に対して， 以下の３つの操作を施すことによって定義される確率過程である．

1. 選択: 確率 $p_T(x_i)$ に従ってリサンプリングを行う．
2. 突然変異: ある確率分布 $q(x_{t+1}\mid x_t)$ に従って各 $x_t$ から $x_{t+1}$ を作る (通常は微小ノイズを加える)．
3. 交差： ある確率分布 $r(x_{t+1}^{(j)}, x_{t+1}^{(k)}\mid x_t^{(j)},x_t^{(k)})$に従って二つの個体 $x^{(j)}$, $x^{(k)}$ から 新たな個体 $x_{t+1}^{(j)}$, $x_{t+1}^{(k)}$ を作る (例えば $x$ が 文字列のときそれらを途中で切って「交差」させる)．

さて，まず「選択」については，前節で見たリサンプリング法と同様の 手続きである． ただし，$r(x)=1$ にしたものになっているので，現在の集団が $p_{T_t}(x)$ に従うものであったとすると， $p_T(x)$ でリサンプリングすることによって得られる集団の分布は

$$p_{T_{t+1}}(x) = p_{T_t}(x)p_T(x)=\exp(-f(x)/T_{t+1})/Z_{t+1},$$ (14)

$$T_{t+1}=1/(1/T_t+1/T) = T_t / (1+T_t/T)< T_t$$ (15)

という分布になる． つまり，集団の温度の値はどんどん低くなり， リサンプリングと同時にシミュレーテッドアニーリングを行っている ことになる． リサンプリングとシミュレーテッドアニーリングの効果により，集団は 単一化する傾向にあるが，これは遺伝的浮動 (genetic drift) と呼ばれる． 探索の多様性を保つためにはこれを避けたほうがよいこともある[1].

次に「突然変異」については MCMC 法の中で提案分布に従って候補を生成する ステップとみなせる． 候補の採択・不採択はないが， 分布への収束は 「選択」におけるリサンプリングで行うということである．

最後の「交差」は遺伝的アルゴリズムに特有のステップである． 4 節において，1 変数 MCMC から多変数 MCMC への拡張 について言及したがそれを具体化したものと言える． 二つの個体を使っているという点ではパラレルテンパリング法と同じだが， パラレルテンパリング法では交換のみを行っていた⁷． ただし，実際に採択率の高い「交差」の確率過程がどんなものになるかは 与えられた問題の性質に大きく依存するはずであり，その辺りの議論が 必要となるであろう．