差分進化 — 知識ノート

集団内の 2 個体の差ベクトルを、別の個体に足して候補を作る手法。 Differential Evolution、DE。Storn と Price が 1997 年に提案した。

v_{i} = x_{r_{1}} + F \cdot (x_{r_{2}} - x_{r_{3}})

$r_{1}, r_{2}, r_{3}$ は互いに異なる無作為な添字、 $F$ はスケール係数（典型的に 0.5〜0.9）。作った $v_{i}$ と元の $x_{i}$ を交叉させ、良い方を残す。

差ベクトルを使う意味#

$x_{r_{2}} - x_{r_{3}}$ は集団が現在どう散らばっているかをそのまま反映する。集団が広く散っていれば大きく飛び、収束してくれば自然に小さく動く。ステップサイズを別途調整しなくても、探索の幅が集団の状態に追随する。 CMA-ES が共分散行列で明示的に行うことを、 DE は差ベクトルで暗黙に行っていると見ることもできる。

命名規則#

論文では DE/rand/1/bin のように書かれる。順に「基準にする個体（rand か best）／差ベクトルの本数／交叉方式（bin か exp）」。 DE/best/1/bin は最良個体を基準にするので収束は速いが局所解に落ちやすい。

改良版#

パラメータ $F$ と交叉率 $C R$ の設定が性能を左右するため、これを自動調整する系統が発展した。SHADE と L-SHADE は成功した設定の履歴からパラメータを引く方式で、ベンチマーク競技会で上位を占めてきた。ノイズ下での VQA 最適化の比較で iL-SHADE が使われているのもこの系譜。

参考文献#

Rainer Storn, Kenneth Price. Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization 11, 1997. https://doi.org/10.1023/A:1008202821328
Swagatam Das, Ponnuthurai N. Suganthan. Differential Evolution: A Survey of the State-of-the-Art. IEEE Transactions on Evolutionary Computation 15(1), 2011. https://doi.org/10.1109/TEVC.2010.2059031
Ryoji Tanabe, Alex Fukunaga. Success-History Based Parameter Adaptation for Differential Evolution. IEEE CEC, 2013. https://doi.org/10.1109/CEC.2013.6557555