探索と活用のバランス

探索と活用を、 ブラックボックスという条件のもとで具体的にどう配分するか。

予算配分の問題として#

評価回数 $T$ を、まだ見ていない領域の調査と、 有望な領域の掘り下げにどう割り振るか。 最適な配分は問題の多峰性に依存するが、それは事前には分からない。 だから多くの手法は、探索の進み具合を見て配分を動的に変える。

各手法の具体的な調節点#

手法	調節するもの	探索へ寄せる操作
CMA-ES	$\sigma$、$\lambda$	$\lambda$ を増やす、${\sigma }^{(0)}$ を大きく取る
PSO	$w$、$c_1/c_2$、トポロジー	近傍を疎にする
ABC	limit	limit を小さくして打ち直しを増やす
ベイズ最適化	獲得関数の $\kappa$	不確かさの重みを上げる
焼きなまし法	温度	冷却を遅くする

時間変化させるのが定石#

序盤は探索、終盤は活用、という切り替えが広く使われる。 PSO の慣性重みを 0.9 → 0.4 と減らす、焼きなましの温度を下げる、 ベイズ最適化の $\kappa$ を減らす、いずれも同じ方針。

理屈は単純で、序盤は情報が無いので広く見るしかなく、 終盤は残り予算が少ないので確実に良い解を仕上げたいから。

測り方#

配分が適切だったかは事後にしか分からないが、手がかりはある。

• 集団の多様性（標準偏差、平均距離）が早期に潰れていれば活用に寄りすぎ
• 最良値がほとんど改善しないまま予算を使い切ったなら探索に寄りすぎ
• 最良解到達率のばらつきが大きいなら、 初期値依存が強く探索が足りていない

参考文献#

• Matej Črepinšek, Shih-Hsi Liu, Marjan Mernik. Exploration and exploitation in evolutionary algorithms: A survey. ACM Computing Surveys 45(3), 2013. https://doi.org/10.1145/2480741.2480752
• Bobak Shahriari et al. Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proceedings of the IEEE 104(1), 2016. https://doi.org/10.1109/JPROC.2015.2494218