今までちょっとアルゴリズムをスルー気味だったので、ちょっとまとめておきます。Local Search は Tabu Search / Simulated Annealing / Late Acceptance がいい感じに働いてくれるので、Benchmarker 使って、まずはざっくりこの3つを比較して、一つ選べばいいんじゃないかな。各パラメータの調整も Benchmarker で。
Hill Climbing
Local Search の基本。常により良いスコアになる Move を採用します。このアルゴリズムの問題は「いったんスコアを下げないと、もっと良いスコアを達成できない」という状況に対応できず、そこで留まってしまうことです。このような「一時的な山」を Local Optima (局所最適) といいます。実際には Hill Climbing を使うケースは無いでしょう。
Tabu Search
http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#tabuSearch
tabu list という有限サイズのリストを保持し、直近に動かした Entity (あるいは Move など)をリストにいれます（FIFO）。tabu list に入っている Entity は採用されません（タブーだということ）。より良いスコアになる Move が採用されますが、tabu list の制約により、最善の Move で、スコアが悪くなる場合もあります。そしてその場合 Move は許容されます。よって Local Optima を脱することができます。tabu list のサイズが小さすぎるとやはり Local Optima にハマるかもしれません。逆に tabu list のサイズが大きすぎるといつまでたっても良いスコアにならないかもしれません。
Simulated Annealing
焼きなまし法と訳されます。これはスコアが悪くなる Move のとき、ランダムチェックを行い、OKなら採用します。このチェックの合否の確率は温度(temperature)に左右されます。ステップが進むにつれて、temperature は下がるので、「スコアが悪くなる Move」を受け入れる確率は下がっていきます。
Late Acceptance
Late Acceptance list という有限サイズのリストを保持し、Nステップ前のスコアを記憶しておきます。Move を採用するとき、現在よりスコアが悪くなるとしても、「Nステップ前のスコア」以上であれば採用します。
