補遺: 遺伝的アルゴリズムとアニーリング――正の行列から収束を示す

遺伝的アルゴリズム（GA）、シミュレーテッドアニーリング（SA）、量子アニーリング（QA）は、同じ最適化問題に取り組めますが、動かしている状態が異なります。 GAは候補解の集団、SAは一つの候補解の確率分布、閉じた量子系のQAは確率振幅を動かします。それでも、適切な正の行列を取り出すと、最大固有値と他の固有値の隔たりを共通の道具で評価できます。

ここでは、選択・交叉の後に全個体を独立に突然変異させる有限集団GAを定式化し、Hopfの定理を使って緩和の下限を求めます。次に、突然変異を弱め、選択圧を強めるスケジュールの下で最適解への収束を示します。正の作用素による定式化と詳しい評価は文献 [1] [2] に基づきます。

証明は三段階です。 パラメータを固定したときに初期状態を忘れること、パラメータを変えても定常分布についていけること、定常分布が最適解へ集中すること。この三つを区別すると、Hopfの定理が何を保証し、何を別に証明すべきかが明確になります。QAの収束定理とSAの補遺も、この観点から読み直せます。

1. 一つの候補を動かすか、集団を作り直すか

長さ $L$ の二進文字列 $g\in \{0,1{\}}^L$ に対して、コスト $E(g)$ を最小にします。GAでは、たとえば四つの候補を並べて一つの集団とし、良い候補を親に選び、親同士の一部を組み合わせ、最後にビットを反転させて新しい候補を作ります。

手法	一つの状態	探索を作る操作	固定パラメータでの基準
SA	一つの候補 $g$	提案とMetropolis受理・棄却	Gibbs分布
GA	集団 $x=(g_1,\dots ,g_M)$	選択・交叉・突然変異	集団上の定常分布。一般にGibbs分布ではない
閉じた量子系のQA	候補の重ね合わせ	横磁場などを含むユニタリ時間発展	瞬間基底状態。時間発展が自動的に緩和するわけではない

SAでは、現在の候補より悪い提案も温度に応じて受け入れます。GAでは、集団内で相対的に良い親を多く選びます。同じ低エネルギーを好む操作でも、判定する対象が異なります。

さらに、GAの一世代は一般に $M$ 個の子を作ります。一世代とSAの一提案を、そのまま同じ計算量として数えることはできません。

2. 証明するGAの更新則を決める

状態は順序付き集団 $x=(g_1,\dots ,g_M)$ です。集団全体のビット数を $d=ML$ と書くと、状態数は $s=2^d$ になります。順序を残すのは、誰がどの子を作ったかを曖昧にせず、遷移行列を定義するためです。

一世代の操作を次の順序に固定します。

1. 現在の全ての親を含む候補リスト $C$ を作る。交叉で作った候補を加えてもよい。
2. リストから $M$ 個体を、復元抽出で独立に選ぶ。
3. 選ばれた全個体の全ビットを、それぞれ確率 $0<\mu \le 1/2$ で独立に反転する。

候補リストには同じ文字列が複数回含まれても構いません。リストの長さは $|C|\le J$、リストを作る確率は $R(C|x)$ とします。最適化の証明では $R$ が $\mu ,\beta$ に依存しないことを仮定します。選択確率は

$$w_j(C)=\frac{e^{-\beta E(c_j)}}{\sum _{k=1}^{|C|}{e}^{-\beta E(c_k)}}$$

です。$\beta$ は選択圧で、物理的な温度を測っている必要はありません。値が大きいほど、リスト内の低コスト候補を強く選びます。

突然変異前の集団を $z=(z_1,\dots ,z_M)$ とすると、選択・交叉の行列は

$$A_{\beta }(z|x)=\sum _{C}R(C|x)\prod _{a=1}^M[\sum _{j=1}^{|C|}{w}_j(C){\mathbf{1}}_{z_a=c_j}],\sum _z{A}_{\beta }(z|x)=1.$$

角括弧は一人の子を選ぶ確率、その積はリストを固定したときの独立な抽出を表します。リストを共有するので、リストについて平均した後まで子が無条件に独立とは限りません。

集団間のHamming距離を $h(y,z)$ とすると、突然変異と一世代の行列は

$$B_{\mu }(y|z)={\mu }^{h(y,z)}(1-\mu {)}^{d-h(y,z)},K_{\mu ,\beta }=B_{\mu }{A}_{\beta },p_{n+1}=K_{\mu ,\beta }{p}_n.$$

列が出発集団、行が到着集団です。各列の和は1になります。固定パラメータでのスペクトル評価は、実は任意の列確率行列 $A$ に対する $K_{\mu }=B_{\mu }A$ に成り立ちます。一方、最適解への集中には、ここで指定したBoltzmann選択を使います。

全ての子に最後の突然変異を施すことが重要です。 最良個体を無変異で必ず残すエリート保存、突然変異後の棄却、状態に含めていない履歴への依存を加えると、ここで扱う行列とは変わります。GA一般の全ての実装を一つの定理で覆っているわけではありません。

3. 一ビット・二個体なら行列を手で書ける

$L=1,M=2$ とし、候補リストを現在の親だけにします。順序付き状態は $00,01,10,11$ の四つです。この更新則では、1を持つ個体数 $k=0,1,2$ だけで次世代の個体数の分布が決まるので、三状態にまとめられます。

選ばれた親が1である確率を $u_k$、突然変異後の子が1である確率を $v_k$ と書くと、

$$u_k=\frac{k{e}^{-\beta E(1)}}{(2-k)e^{-\beta E(0)}+k{e}^{-\beta E(1)}},v_k=(1-\mu )u_k+\mu (1-u_k)=\mu +(1-2\mu )u_k.$$

二人の子を独立に作るので、次世代の1の個体数は二項分布になります。

$$K_{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}}=\left(\begin{array}{ccc}(1-v_0{)}^2& (1-v_1{)}^2& (1-v_2{)}^2\\ 2v_0(1-v_0)& 2v_1(1-v_1)& 2v_2(1-v_2)\\ v_0^2& v_1^2& v_2^2\end{array}\right).$$

各列について $(1-v{)}^2+2v(1-v)+v^2=1$ を確認してください。これは四状態の過程を対称性により厳密にまとめたもので、近似ではありません。

たとえば $E(0)=1,E(1)=0,\beta =\log 2$ なら、混合集団の親選択で $u_1=2/3$ です。$\mu =1/10$ とすると $v_0=1/10,v_1=19/30,v_2=9/10$ となり、

$$K_{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}}=\left(\begin{array}{ccc}81/100& 121/900& 1/100\\ 18/100& 418/900& 18/100\\ 1/100& 361/900& 81/100\end{array}\right).$$

良い候補1を持つ集団ほど1を選びやすい一方、突然変異があるので全ての集団間を移れます。$\mu =1/2$ では全ての列が $(1/4,1/2,1/4{)}^{\mathsf{T}}$ になり、選択の結果を一世代で完全に忘れます。探索を強めれば常に良いわけではないことも、この極限から分かります。

4. 正の行列とHopfの定理

4.1 突然変異が全ての行列要素を正にする

$0<\mu \le 1/2$ なら、各ビットについて小さい方の確率は $\mu$、大きい方は $1-\mu$ です。したがって

$${\mu }^d\le B_{\mu }(y|z)\le (1-\mu {)}^d.$$

$K_{\mu }(y|x)=\sum _z{B}_{\mu }(y|z)A(z|x)$ はこの値の確率平均なので、同じ上下限を満たします。

$${\mu }^d\le K_{\mu }(y|x)\le (1-\mu {)}^d.$$

全ての要素が正であるため、Perron–Frobeniusの定理から最大固有値は1で単純、正の定常分布 ${\pi }_{\mu }$ は一意です。他の固有値の絶対値は1より小さく、固定したパラメータなら初期分布によらず定常分布へ収束します。これに数値的な下限を与えるのがHopfの定理です。

4.2 固有値の隔たりを評価する

正の行列 $G$ のPerron固有値を $\rho$ とします。森田・西森のQAの解析で用いられるHopfの評価は、次の形で使えます。[3]

$$\kappa (G)=\underset{i,j,k}{max}\frac{G_{ik}}{G_{jk}},|\lambda |\le \rho \frac{\kappa (G)-1}{\kappa (G)+1}(\lambda \ne \rho ).$$

正の行列でも、対称でなければ固有値が複素数になることがあります。この評価は絶対値についてのものなので、その場合も使えます。固有ベクトルの完全な組を仮定する必要もありません。

GAでは $\rho =1$ で、式008から $\kappa \le [(1-\mu )/\mu {]}^d$ です。右辺が $\kappa$ の増加関数であることを使うと、

$$|\lambda |\le q_{\mu }=\frac{(1-\mu {)}^d-{\mu }^d}{(1-\mu {)}^d+{\mu }^d},1-|\lambda |\ge \frac{2{\mu }^d}{(1-\mu {)}^d+{\mu }^d}.$$

これが、Hopfの定理によるGAの緩和評価です。 固定した $d$ で $\mu \downarrow 0$ とすると、下限は $2{\mu }^d$ の次数になります。突然変異を極端に弱めると、集団が初期状態を忘れるまでの時間が長くなりうると分かります。ただし、これは最悪の場合を含む下限で、個々のGAが必ずこの遅さになるという意味ではありません。

5. SA・QAと同じところ、異なるところ

SAの対称提案 $Q$ にMetropolis受理を組み合わせると、異なる候補間の遷移は

$$K_{\beta }^{\mathrm{S}\mathrm{A}}(g^{\prime }|g)=Q(g^{\prime }|g)min\{1,e^{-\beta [E(g^{\prime })-E(g)]}\},{\pi }_{\beta }^{\mathrm{S}\mathrm{A}}(g)\propto e^{-\beta E(g)}.$$

対角要素は各列の和が1になるよう定めます。連結性に加え、必要なら自己ループを加えて周期性を除けば、固定温度でこの分布へ緩和します。詳細釣り合いがGibbs分布を保証します。SAの冷却と障壁の関係には、既に厳密な理論があります。[4]

固定パラメータの確率行列 $K$ をPoisson率 $\nu$ で更新する過程では、$\dot{p}=\nu (K-I)p$ です。$\mathrm{\Pi }=\mathrm{diag}\pi$、$p={\mathrm{\Pi }}^{1/2}\psi$ と置くと、

$$-{\partial }_t\psi =H_K\psi ,H_K=\nu {\mathrm{\Pi }}^{-1/2}(I-K){\mathrm{\Pi }}^{1/2}.$$

詳細釣り合いがあれば $H_K$ は実対称で、非対角要素は非正、基底ベクトルは $\sqrt{\pi }$ です。これはstoquasticなハミルトニアンですが、一般に通常の横磁場Ising型と同じ形ではありません。GAでは詳細釣り合いを仮定していないので、対応する作用素は一般に非エルミートです。

一方、横磁場QAでは

$$H_{\mathrm{\Gamma }}^{\mathrm{Q}\mathrm{A}}=\sum _{g}E(g)|g⟩⟨g|-\mathrm{\Gamma }\sum _{\ell =1}^L{\sigma }_{\ell }^x,G_{\tau }=e^{-\tau H_{\mathrm{\Gamma }}^{\mathrm{Q}\mathrm{A}}}$$

を考えます。$\hslash =1$ とし、$\tau$ はエネルギーの逆数の単位を持ちます。$\mathrm{\Gamma }>0$ なら横磁場が全ての文字列をつなぎ、$\tau >0$ の虚時間行列 $G_{\tau }$ は要素ごとに正です。その固有値は $e^{-\tau E_j}$ なので、

$$\frac{{\lambda }_1(G_{\tau })}{\rho (G_{\tau })}=e^{-\tau (E_1-E_0)}.$$

正の行列の固有値比の上限は、QAのエネルギーギャップの下限へ変わります。森田・西森の解析では、適切にシフトしたハミルトニアンのべきを正の行列にして、同じHopfの評価を用います。[3] [9]

証明の段階	GA	閉じた量子系のQA
正の行列	一世代の確率行列 $B_{\mu }A$	虚時間行列、またはシフトしたハミルトニアンの適切なべき
Hopfで抑える量	非Perron固有値の絶対値	励起状態と基底状態に対応する固有値の比
そこから得るもの	緩和率の下限	エネルギーギャップの下限
変化する目標への追従	確率分布の収縮と定常分布の移動量	実時間の断熱追従と励起誤差の評価

GAで $\zeta =\nu (1-\lambda )$ と置けば、$\mathrm{Re}\zeta \ge \nu (1-|\lambda |)$ です。この実部の隔たりはPoisson化した過程の緩和を表します。QAの実時間ユニタリ発展を、GAの確率更新と同一視することはできません。正の行列は共通のスペクトル評価の道具であって、実時間QAが確率的に緩和するという意味ではありません。

6. 分布の重なりを見ると、評価が鋭くなる

Hopfの評価は、行列の最小・最大要素だけを使います。突然変異が作る分布全体の重なりを使うと、さらに強い収縮評価が得られます。二つの分布の全変動距離と、確率行列のDobrushin係数を

$$\parallel p-q{\parallel }_{\mathrm{T}\mathrm{V}}=\frac{1}{2}\sum _x|p_x-q_x|,\eta (K)=1-\underset{x,x^{\prime }}{min}\sum _{y}min\{K(y|x),K(y|x^{\prime })\}$$

と定めます。距離が0なら同じ分布、1なら支持が重ならない分布です。係数 $\eta$ は一回の更新で残りうる距離の最大割合で、

$$\parallel Kp-Kq{\parallel }_{\mathrm{T}\mathrm{V}}\le \eta (K)\parallel p-q{\parallel }_{\mathrm{T}\mathrm{V}},\eta (BA)\le \eta (B)\eta (A)\le \eta (B)$$

を満たします。[8]

突然変異の二つの入力について、同じビットの出力分布は共通なので重なりの計算から取り除けます。異なるビットを増やすほど二つの出力を区別しやすくなるため、最小の重なりは $0^d$ と $1^d$ の組で生じます。1の数が $j$ の出力に対して、二つの確率は ${\mu }^j(1-\mu {)}^{d-j}$ と ${\mu }^{d-j}(1-\mu {)}^j$ です。小さい方を足せば、

$$\begin{array}{rl}{\epsilon }_d(\mu )& =1-\eta (B_{\mu })\\ & =2\sum _{j>d/2}(\genfrac{}{}{0ex}{}{d}{j}){\mu }^j(1-\mu {)}^{d-j}+{\mathbf{1}}_{d\text{ even}}(\genfrac{}{}{0ex}{}{d}{d/2}){\mu }^{d/2}(1-\mu {)}^{d/2}.\end{array}$$

偶数の場合、ちょうど半分のビットが反転した項は一回だけ数えます。小さい例では

$${\epsilon }_1={\epsilon }_2=2\mu ,{\epsilon }_3={\epsilon }_4=6{\mu }^2-4{\mu }^3,{\epsilon }_d\sim c_d{\mu }^{r_d},r_d=\lceil d/2\rceil .$$

ここで $c_{2r}=(\genfrac{}{}{0ex}{}{2r}{r})$、$c_{2r-1}=2(\genfrac{}{}{0ex}{}{2r-1}{r})$ です。漸近形は $d$ を固定したものです。したがって

$$|\lambda |\le 1-{\epsilon }_d(\mu ),\underset{\zeta \ne 0}{min}\mathrm{Re}\zeta \ge \nu {\epsilon }_d(\mu ).$$

例えば $d=6$ なら、Hopfの要素ごとの評価は $2\nu {\mu }^6$ の次数、重なりの評価は $20\nu {\mu }^3$ の次数です。この改善はHopfの式に代入し直した結果ではなく、突然変異の構造を使う追加の収縮評価です。

6.1 多数決が最悪の遅さを実現する

集団ビットの多数派が0なら $0^d$、1なら $1^d$ に全てを揃え、同数なら確率 $1/2$ でどちらかに揃える操作 $A$ を考えます。突然変異後に多数派が逆転する確率は

$$a=Pr(Z>d/2)+\frac{1}{2}Pr(Z=d/2),Z\sim \mathrm{Bin}(d,\mu ),C=\left(\begin{array}{cc}1-a& a\\ a& 1-a\end{array}\right).$$

縮約した行列の固有値は $1$ と $1-2a=1-{\epsilon }_d$ です。元の行列も同じ非零固有値を持つので、この広い $A$ のクラスでは評価が達成されます。$L=1,M=d$ なら、多数派に依存した選択と複製として解釈できます。これは最悪の緩和を作る例で、決められたコストの最適解を選ぶ方法ではありません。突然変異だけの場合の緩和率 $2\nu \mu$ と比べると、集団操作がかえって遅いモードを作ることも分かります。

7. 突然変異を下げても定常分布についていけるか

世代ごとに行列を変え、$K_n{\pi }_n={\pi }_n$ とします。追従誤差と定常分布の移動量を

$$e_n=\parallel p_n-{\pi }_n{\parallel }_{\mathrm{T}\mathrm{V}},b_n=\parallel {\pi }_{n+1}-{\pi }_n{\parallel }_{\mathrm{T}\mathrm{V}}$$

と置きます。三角不等式と収縮から、

$$\begin{array}{rl}{e}_{n+1}& =\parallel K_n{p}_n-{\pi }_{n+1}{\parallel }_{\mathrm{T}\mathrm{V}}\\ & \le \parallel K_n(p_n-{\pi }_n){\parallel }_{\mathrm{T}\mathrm{V}}+b_n\\ & \le [1-{\epsilon }_d({\mu }_n)]e_n+b_n.\end{array}$$

第一項は過去の誤差が消える効果、第二項は追いかける目標が動いて新しく生じる誤差です。これを繰り返すと、${\epsilon }_j={\epsilon }_d({\mu }_j)$ として

$$e_n\le e_0\prod _{j<n}(1-{\epsilon }_j)+\sum _{k<n}{b}_k\prod _{k<j<n}(1-{\epsilon }_j).$$

$\sum _n{\epsilon }_n=\mathrm{\infty }$ なら、初期誤差の項は $\prod (1-{\epsilon }_j)\le e^{-\sum {\epsilon }_j}$ により消えます。さらに $b_n/{\epsilon }_n\to 0$ なら、十分後では $b_n\le a{\epsilon }_n$ とできます。その後の和は積の差として望遠鏡和になり、高々 $a$ です。初めの有限個の項は消え、最後に $a\downarrow 0$ とすれば $e_n\to 0$ が示せます。

7.1 定常分布の移動量も評価する

$A$ を固定すると、$K_{\mu }$ の各要素は ${\mu }^h(1-\mu {)}^{d-h}$ の正の重み付き和です。各単項式の対数微分は $-d/(1-\mu )$ と $d/\mu$ の間にあります。

有限Markov連鎖の定常分布は、有向全域木の重み $T_i$ を用いて ${\pi }_i=T_i/\sum _j{T}_j$ と書けます。各木の重みは $s-1$ 個の遷移確率の積です。対数微分を取れば積は和になり、正の和の対数微分は各項の対数微分の重み付き平均になります。このため

$$\parallel {\partial }_{\mu }{\pi }_{\mu }{\parallel }_{\mathrm{T}\mathrm{V}}\le \frac{d(s-1)}{2\mu (1-\mu )},s=2^d.$$

定数は非常に保守的ですが、必要な $\mu$ 依存性が分かりました。

$${\mu }_n={\mu }_0(1+n/n_0{)}^{-\alpha },0<{\mu }_0\le \frac{1}{2},n_0>0$$

なら、隣の世代までの積分は $\log ({\mu }_n/{\mu }_{n+1})=O(n^{-1})$ の次数なので $b_n=O(n^{-1})$ です。${\epsilon }_d({\mu }_n)$ は $n^{-\alpha r_d}$ の次数ですから、

$$0<\alpha <\frac{1}{r_d}=\frac{1}{\lceil ML/2\rceil }⟹\parallel p_n-{\pi }_n{\parallel }_{\mathrm{T}\mathrm{V}}\to 0.$$

比較列を式022に代入すると $e_n=O(n^{\alpha r_d-1})$ も得られます。$A$ が固定なら、木の重みは多項式で定常分布は有理関数となり、$\mu \downarrow 0$ で有限の全変動を持ちます。この追加事実を用いれば端点 $\alpha =1/r_d$ も含めて極限定常分布への収束が示せます。選択圧も変える場合に、この固定 $A$ の端点の議論を無条件で流用はしません。

なお、鋭い重なり評価を使わずとも、式008から全ての列が一様分布を重み $2^d{\mu }^d$ 以上含むと分かります。これだけで $\eta (K)\le 1-(2\mu {)}^d$ となり、$b_n=O(n^{-1})$ の下で $0<\alpha <1/d$ という保守的な追従条件が得られます。Hopfのスペクトル評価に加え、このような時間依存過程の議論が必要です。

8. 定常分布が最適解へ集中することを示す

ここからは第2節のBoltzmann選択を使います。最適文字列を少なくとも一つ含む集団の集合を $\mathcal{O}$ とし、最適コストと最良の非最適コストの差を $\delta >0$ とします。全ての文字列が最適なら問題は自明です。

8.1 最適解の集合へ入る確率と、出る確率

$\mathcal{O}$ の外にいるとき、どの子からでも、指定した一つの最適文字列へ突然変異する確率は ${\mu }^L$ 以上です。集団全体の $ML$ ビットを同時に正しくする必要はなく、一人の子の $L$ ビットだけを考えます。

$\mathcal{O}$ の中にいるとき、候補リストには必ず最適個体が残ります。最適個体一つの重みを分母の下限に用いると、非最適な親を選ぶ確率は $J{e}^{-\beta \delta }$ 以下です。最適な親を選んでも、どこかで突然変異する確率が高々 $L\mu$ あります。子が全員非最適になる確率は、リストを固定した条件付き独立性から評価できます。

$$\begin{array}{rlrl}K(\mathcal{O}|x)& \ge {\mu }^L& & (x\notin \mathcal{O}),\\ K({\mathcal{O}}^c|x)& \le [J{e}^{-\beta \delta }+L\mu {]}^M& & (x\in \mathcal{O}).\end{array}$$

定常状態では、集合へ入る総確率流と出る総確率流が等しくなります。個々の状態対についての詳細釣り合いは不要です。

$$\sum _{x\notin \mathcal{O}}\pi (x)K(\mathcal{O}|x)=\sum _{x\in \mathcal{O}}\pi (x)K({\mathcal{O}}^c|x),\pi ({\mathcal{O}}^c)\le \frac{[J{e}^{-\beta \delta }+L\mu {]}^M}{{\mu }^L}.$$

8.2 選択圧と突然変異の共同スケジュール

$\beta =b\log (1/\mu )$ と置けば $e^{-\beta \delta }={\mu }^{b\delta }$ です。選択の間違いと突然変異のうち、遅く消える方が ${\mu }^{min(1,b\delta )}$ の次数になります。したがって

$${\pi }_{\mu ,\beta }({\mathcal{O}}^c)=O({\mu }^R),R=Mmin(1,b\delta )-L.$$

$R>0$、すなわち $M>L$ かつ $b\delta >L/M$ が、この評価による集中の十分条件です。必要条件であると主張しているわけではありません。

選択も変わるため、第7節の固定 $A$ の証明を一段補います。コストの幅を $F=maxE-minE$ とすると、${\partial }_{\beta }\log w_j=-E(c_j)+⟨E{⟩}_C$ の絶対値は $F$ 以下です。$M$ 人の積では $MF$、$\beta =b\log (1/\mu )$ の微分を含めると $MbF/\mu$ 以下です。これを突然変異の評価とともに木の公式へ入れれば、再び $b_n=O(n^{-1})$ となります。

以上をまとめると、次の十分条件が得られます。

$$\begin{array}{c}{\mu }_n={\mu }_0(1+n/n_0{)}^{-\alpha },{\beta }_n=b\log (1/{\mu }_n),\\ M>L,b\delta >L/M,0<\alpha <1/\lceil ML/2\rceil \\ ⟹Pr(X_n\in \mathcal{O})\to 1.\end{array}$$

証明の最後は、$Pr(X_n\notin \mathcal{O})\le e_n+{\pi }_n({\mathcal{O}}^c)$ と足すだけです。より具体的には

$$Pr(X_n\notin \mathcal{O})=O(n^{\alpha r_d-1})+O(n^{-\alpha R}).$$

第一項は追従の誤差、第二項は定常分布自体に残る非最適確率です。さらに、最適個体を含む集団から非最適な子が一人でも出る確率は高々 $M[J{e}^{-{\beta }_n\delta }+L{\mu }_n]$ なので、全員が最適になる確率も1へ向かいます。ただし、各試行軌道がある時点以降永久に最適集団に留まる、という概収束の主張ではありません。

9. 固定した選択圧では、最適解に集中しないことがある

第3節で用いた、0と1の適応度が1対2という固定比率を考えます。$\mu =0$ のとき、混合集団は個体数 $k=0,1,2$ へそれぞれ $1/9,4/9,4/9$ の確率で移ります。混合集団から劣った同質集団 $00$ へ最終的に吸収される確率 $a$ は、

$$a=\frac{1}{9}+\frac{4}{9}a,a=\frac{1}{5}.$$

優れた同質集団 $11$ へは $4/5$ で吸収されます。小さい突然変異を戻すと、どちらの同質集団からも混合集団へは $2\mu +O({\mu }^2)$ で移ります。したがって同質集団間の有効な移動率の比は $00\to 11$ が $4/5$、$11\to 00$ が $1/5$ となり、極限定常分布は

$${\pi }_{\mu }⟶(1/5,0,4/5)(k=0,1,2\text{ の順}).$$

定常分布を正確に追っても、最適解の成功確率は1になりません。 これが、固定パラメータでの混合、動く定常分布への追従、最適解への集中を分ける理由です。

10. 最適解を含むことだけなら、さらに緩い条件で示せる

集団分布全体の追従よりも、「最適解を一つ以上含む」という事象だけを示す方が容易な場合があります。失敗確率を $q_n=Pr(X_n\notin \mathcal{O})$ とすると、式027から直接

$$q_{n+1}\le (1-{\mu }_n^L)q_n+[J{\mu }_n^{b\delta }+L{\mu }_n{]}^M.$$

強制項を収縮量 ${\mu }_n^L$ で割ったものは $O({\mu }_n^R)$ でゼロへ向かいます。第7節と同じ積の議論により、$\sum _n{\mu }_n^L=\mathrm{\infty }$ なら $q_n\to 0$ です。

$$R>0,0<\alpha \le 1/L⟹Pr(X_n\in \mathcal{O})\to 1.$$

これは第8節より広いスケジュールを許しますが、その範囲全体で分布の追従を証明したわけではありません。最悪の緩和ギャップの指数と、最適化という事象の十分条件の指数は、必ずしも同じではないのです。

例えば $L=2,M=3,b\delta =1$ なら、$d=6,r_d=3,R=1$ です。分布追従から示すには $\alpha <1/3$、成功事象だけなら $\alpha \le 1/2$ で十分です。$\alpha =1/4$ を選べば式031は $O(n^{-1/4})$ になります。漸近次数の定数は問題・集団サイズに依存します。

11. 有限時間の成功確率と比較の限界

$\mu ,\beta$ を固定し、全ての子の独立性を使うと、最適解集合への入口確率は少なくとも $a=1-(1-{\mu }^L{)}^M$ です。出口の上限を $r=min\{1,[J{e}^{-\beta \delta }+L\mu {]}^M\}$ と置くと、

$$q_{n+1}\le (1-a)q_n+r,q_n\le (1-a{)}^n{q}_0+\frac{r}{a}[1-(1-a{)}^n]\le e^{-an}+\frac{r}{a}.$$

第一項を小さくするには世代数を増やし、第二項を小さくするには突然変異と選択圧を選びます。目標失敗確率 $0<ϵ<1$ に対し、$M>L$ として

$${\mu }_{ϵ}={\left[\frac{ϵ}{2(2L{)}^M}\right]}^{1/(M-L)},{\beta }_{ϵ}={\delta }^{-1}\log \frac{J}{L{\mu }_{ϵ}}$$

を取れば $r/a\le ϵ/2$ です。$a$ をこの ${\mu }_{ϵ}$ で評価して、

$$n_{ϵ}=\lceil \frac{\log (2/ϵ)}{-\log (1-a)}\rceil ⟹q_{n_{ϵ}}\le ϵ.$$

親だけの候補リストで親の評価値を再利用し、子一人につき目的関数を一回評価する数え方なら、初期集団も含む十分な評価回数は

$$M(n_{ϵ}+1)\le 2M+{\mu }_{ϵ}^{-L}\log (2/ϵ).$$

これは多項式時間の保証ではありません。選択圧を決めるには $\delta$ またはその既知の正の下限が必要で、交叉候補を追加する場合にはその生成・評価費用も加わります。この固定パラメータの有限時間保証と、世代ごとにパラメータを変える漸近収束定理は別のものです。

11.1 障壁を飛び越えることと、集団の優位性

$L\ge 2$ とし、$E(0^L)=0,E(1^L)=-1$、他の文字列では $E=H>0$ とします。$0^L$ から始め、常に ${\beta }_n^{\mathrm{S}\mathrm{A}}\ge {\beta }_0>0$ の一ビット反転SAなら、そこから一回で脱出する確率は高々 $e^{-{\beta }_{0}H}$ です。

$$Pr(n\text{ 提案後も失敗})\ge (1-e^{-{\beta }_{0}H}{)}^n.$$

GAの多ビット突然変異は障壁を直接飛び越えられます。しかしSAにも同じ対称な多ビット提案 $Q_{\mu }(g^{\prime }|g)={\mu }^{h(g^{\prime },g)}(1-\mu {)}^{L-h(g^{\prime },g)}$ を認めれば、通常のMetropolis受理で同じ直接ジャンプが可能です。高温から準備するSAも、この下限の仮定の外です。したがって、この比較だけでGAの集団操作の優位性は分かりません。

また、GAで ${\mu }_n$ がべき乗で減っても、${\beta }_n=b\log (1/{\mu }_n)$ は $\log n$ に比例します。「GAはべき乗、SAは対数だからGAが速い」とは言えません。パラメータの意味、提案、初期化、成功条件、評価回数を揃えて比較する必要があります。

12. 収束理論の研究の流れ

文献	主な論点	本補遺とのつながり
SAの冷却理論 [4]	局所的なエネルギー障壁と冷却スケジュール	Gibbs分布への集中と、障壁を越えながらの追従を結ぶ
GAの漸近理論 [7]	有限集団の進化をMarkov過程として扱う	集団状態空間と小さい雑音の下の収束を解析する先行研究
遺伝的操作の作用素理論 [5] [6]	突然変異・交叉・選択のスケーリング、エルゴード性と最適化	選択圧や集団サイズを含めたGAの収束条件は既に研究されている
QAの収束理論 [3] [9]	正の行列、Hopfの評価、断熱追従	最大固有値の分離を共通の枠組みで抑える
正の作用素と収縮 [8]	Markov作用素の収縮係数	スペクトル評価と分布間距離の評価を結び付ける
独立突然変異を用いた集団解析 [1] [2]	明示的な正の核、重なりの鋭い評価、入口・出口による最適化	本補遺で扱った更新則に対する証明と有限時間評価

共通するのは「目標となる状態を定め、そこへ近づく速さを評価し、目標自体の最適解への集中を確かめる」という構造です。詳細釣り合いがないGAでも正の行列の理論を利用できますが、非可逆にするだけで速くなるわけではありません。QAの収束定理とSTAの補遺では、量子側のギャップ評価と追従・制御の違いをさらに確認できます。

13. 手を動かすための演習

1. 式006の各列の和を確かめ、$\mu =1/2$ で選択の影響が消えることを式004から示してください。
2. $d=2$ の突然変異行列を $[(1-\mu )I+\mu {\sigma }^x{]}^{\otimes 2}$ として書き、最小要素と最大要素を求めてください。
3. 式009へ式008を代入してHopfの下限を導いてください。詳細釣り合いを使った箇所はあるでしょうか。
4. $d=3$ について二項分布を足し、${\epsilon }_3=6{\mu }^2-4{\mu }^3$ を求めてください。
5. 式023で、後半の $b_k$ を $a{\epsilon }_k$ に置き換えた和が $a$ 以下になることを示してください。
6. 集合への出入りの確率流が等しいことを、$\pi (\mathcal{O})=\sum _x\pi (x)K(\mathcal{O}|x)$ から導いてください。
7. $L=2,M=3,b\delta =1$ で、$\alpha =0.4$ はどの収束条件を満たしますか。分布全体の追従も証明されたと言えるでしょうか。

解答の手掛かり

1. 中央列は $(121+418+361)/900=1$ です。$\mu =1/2$ では $v_k=1/2$ になります。
2. 各ビットの行列は対角 $1-\mu$、非対角 $\mu$。二ビットでは最小 ${\mu }^2$、最大 $(1-\mu {)}^2$ です。
3. 列の規格化と要素の正値性を使います。詳細釣り合いは不要です。
4. $2[3{\mu }^2(1-\mu )+{\mu }^3]$ を展開します。
5. ${\epsilon }_k\prod _{k<j<n}(1-{\epsilon }_j)$ は、隣り合う積の差になります。
6. 和を $\mathcal{O}$ の内外に分け、$K(\mathcal{O}|x)=1-K({\mathcal{O}}^c|x)$ を使います。
7. $0.4\le 1/L=0.5$ なので成功事象の十分条件を満たします。$0.4>1/\lceil ML/2\rceil =1/3$ なので、ここで示した分布追従の十分条件からは結論できません。

参考文献

1. Masayuki Ohzeki, “Genetic Annealing in a Positive-Operator Framework,” 計算ノート、本文。

2. Masayuki Ohzeki, “Supplemental Material for Genetic Annealing in a Positive-Operator Framework,” 計算ノート、補足。

3. Satoshi Morita, Hidetoshi Nishimori, “Mathematical foundation of quantum annealing,” Journal of Mathematical Physics 49, 125210 (2008). 出典

4. Bruce Hajek, “Cooling Schedules for Optimal Annealing,” Mathematics of Operations Research 13, 311–329 (1988). 出典

5. Lothar M. Schmitt, “Theory of genetic algorithms,” Theoretical Computer Science 259, 1–61 (2001). 出典

6. Lothar M. Schmitt, “Theory of genetic algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling,” Theoretical Computer Science 310, 181–231 (2004). 出典

7. Raphaël Cerf, “Asymptotic convergence of genetic algorithms,” Advances in Applied Probability 30, 521–550 (1998). 出典

8. Stéphane Gaubert, Zheng Qu, “Dobrushin’s Ergodicity Coefficient for Markov Operators on Cones,” Integral Equations and Operator Theory 81, 127–150 (2015). 出典

9. Satoshi Morita, Hidetoshi Nishimori, “Convergence of Quantum Annealing with Real-Time Schrödinger Dynamics,” Journal of the Physical Society of Japan 76, 064002 (2007). 出典