📂最適化理論

最適化理論におけるタブ探索

用語

最適化問題における タブー探索^{tabu search}とは、文字通り 禁忌^tabu事項を設けて反復する探索を防ぐメタヒューリスティック手法である。

説明

タブー探索は グローバー^Gloverによって1986年に提案され、任意の最適化問題に適用可能であるためメタヒューリスティック手法と呼ばれる¹。タブー探索が与えられた問題で本当に有用かどうかは別として、タブー探索のアイデアは理論的背景がどうであれ、用いる手法が何であれ 近傍^neighborhoodと タブーリスト^{tabu list}を定義することで適用できる。

例えば経路最適化問題があるとすると、ある パス $P$ の近傍は辺が一つだけ異なるパスの集合として定義できるだろう。経路探索にタブー探索を適用するというのは、その 目的関数 の値を計算しながら近傍をまず探索し、そこから最適化に寄与しないパスをタブーリストに追加して無駄な計算を避ける、ということである。こうして節約した資源をより深く広い探索に投入することで、結果的により良い最適化を目指す。

目的関数が ユークリッド空間 での 連続関数 であると仮定できるならば、関数値が悪い領域を丹念に探索するよりも、わずかでも可能性の高い領域を探索するほうが短期的には効率的であることがある。最適化の観点で良くない解をタブーリストに追加していき、新たな解候補がタブーリストのいずれかに十分近い――すなわち近傍に入るならば、その解を深掘りする理由はない。このようにタブー探索は問題が離散的であれ連続的であれ、どのような手法を用いるにせよ「わざわざこれ以上探索する必要のない場所」という概念が明確であればどこにでも適用できる²。