タブー探索
直近に行った手を一定期間禁じることで、同じ場所を巡り続けるのを防ぐ局所探索。 Glover が 1986 年に提案した。
仕組み#
- 近傍の中で最良の手を選ぶ。改善しなくても選ぶ
- 選んだ手（あるいはその逆手）をタブーリストに入れる
- タブーリストにある手は、一定回数（tenure）の間は選べない
- 1 へ戻る
改善しない手も選ぶので局所解から出られる。 そのまま戻ってこないよう、来た道をタブーで塞ぐ。
焼きなまし法との違い#
| タブー探索 | 焼きなまし法 | |
|---|---|---|
| 悪化の扱い | 近傍最良なら決定的に受け入れる | 確率的に受け入れる |
| 記憶 | タブーリストという明示的な記憶を持つ | 持たない（マルコフ的） |
| 乱数 | 本質的には不要 | 本質的に必要 |
タブー探索は探索の履歴を明示的に使う点が特徴で、 Glover はこれを「適応的記憶」と呼んでいる。
願望基準#
タブーな手でも、それが現在の最良解を更新するなら許すという例外規則。 aspiration criterion。禁止が行き過ぎて良い解を逃すのを防ぐ。
tenure の設定#
- 短い … すぐ同じ場所へ戻る。堂々巡り
- 長い … 選べる手が減りすぎて探索が硬直する
問題規模に応じて 程度から始め、 停滞を見て動的に変える運用が多い。
参考文献#
- Fred Glover. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research 13(5), 1986. https://doi.org/10.1016/0305-0548(86)90048-1
- Fred Glover, Manuel Laguna. Tabu Search. Springer, 1997. https://doi.org/10.1007/978-1-4615-6089-0
- Holger H. Hoos, Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004. https://doi.org/10.1016/B978-1-55860-872-6.X5016-1