相対的高温ではより良い局所への到達が、相対的低温では局所での収束が、行われる傾向にあります。 図のとおり、局所での収束よりもより良い局所への到達のほうが改善量が大きいです。 また、低温ほどランダムウォークが不活発になるため、局所での収束のほうが時間対効果が悪いです。 この2つが事由としてあるため、スコアが最良になるように温度スケジュールを調整すると、実行時間のほとんどがより良い局所への到達に割かれます。 （そのため、たとえ焼きなましの結果が収束していなくとも不安がらなくていいんです。）
局所での収束の冷遇を説明したところで、どちらも欲張りたいというのがこのページの主旨です。
まず部分状態に注目します。 部分状態というのは、強く関連しあう要素だけからなる状態の一部、もしくは問題を分割した小問題上と関連する要素だけからなる状態の一部とします。 例えば、2次元グリッド問題におけるサブグリッドなどです。 多くの状態要素同士が強く関連するばあい、意味のある部分状態がないこともあります。 部分状態の局所はたくさんあり1つ1つは小さいです。 そして、部分状態の局所のすべてを状態の局所が包含します。 そのため、部分状態の局所の改善は劣りますが、大きくは劣らないのではないかと考えています。 なぜなら、小さくない局所の突破は焼きなましに委ねているので状態の局所は小さく、状態の局所とすべての部分状態の局所は一致度が高いと思われるからです。
一致度が低いと遠くおよばない。
一致度が高いと遜色がない。
というわけで部分状態の収束で代替できそうです。 部分状態は小さいがゆえ時間対効果がとても良くなります。
- TopCoder KnightsAttacks / nika / ボードを分割して焼きなます
- TopCoder CrystalLighting / nika, 他 / ボードを分割して焼きなます / eldidou さんの解説
まず普通に焼きなまして、できるだけ良い局所に到達します。 次に部分状態の1つを選んでしばらく焼きなますというのを繰り返して、部分状態の局所を収束させます。
- TopCoder CrossStitch / hakomo, 他 / 焼きなまし後に DP
- TopCoder KnightsAndPawns / blackmath / 焼きなまし後に DP
部分状態の未収束パターンが単純なばあい、焼きなまし後の DP, greedy などで収束させれることがあります。 決定的アルゴリズムは焼きなましより時間対効果が劇的に良いので、前述の部分状態の焼きなましより優れます。
yukicoder stick xor / hakomo, 他
未収束パターンが状態要素依存であるとき（普通は要素らの関係依存）、それらの要素を含めずに焼きなまします。 それらの要素は焼きなまし後に別アルゴリズムで決定します。 それらの要素が常に最適であるかのように振る舞う（ランダムウォークに追従する）ところがヤバいです。