探索と活用
活用 (exploitation) は今わかっている良い場所を深掘りすること。 探索 (exploration) はまだ見ていない場所を調べること。 限られた評価回数をこの 2 つにどう配分するかが、非凸問題での性能を決める。
なぜ両立しないのか#
評価回数は有限なので、片方に使えばもう片方には使えない。
- 活用に偏る → 最初に見つけた谷を掘り続け、局所最適解で終わる
- 探索に偏る → 広く浅く見るだけで、どこも十分に詰められない
各手法がどう配分しているか#
| 手法 | 配分の仕組み |
|---|---|
| 焼きなまし法 | 温度。高温では悪化も受け入れ（探索）、下げるにつれ活用へ |
| CMA-ES | 探索分布の広がり。ステップサイズ が縮むと活用に寄る |
| PSO | 個体の最良と群れの最良、どちらに強く引かれるかの係数 |
| ベイズ最適化 | 獲得関数。予測値（活用）と不確かさ（探索）を明示的に足す |
| ABC | Scout Bee。停滞した解を捨てて無作為に打ち直す |
強化学習の多腕バンディット問題でも同じ構図が現れ、そちらでは -greedy や UCB として定式化されている。
参考文献#
- Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 2002. https://doi.org/10.1023/A:1013689704352
- 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
- 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