焼きなまし法の適用メモ

プログラミング

はじめに

焼きなまし法について、問題へ適用する際のメモ。

焼きなまし法とは

疑似コード

x:=初期解, T:=初期温度, R:=初期イテレーション回数
while 終了条件 do begin
  for i:=1 to R do begin
    y:=近傍解の一つ(y∈N(x))
    Δ:=score(y) - score(x)
    if Δ >= 0 then x:=y; else
      if exp(-Δ/T) >= frand() then x:=y
  end
  T:=CalcTemp(T)
  R:=CalcIter(R)
end
return 解;

c++でのコーディング例: 診断人さん, 焼きなまし法のコツ, http://shindannin.hatenadiary.com/entry/20121224/1356364040

重要なパラメータ

近傍定義
  • 解xの近傍集合N(x)をどのように定義するか？で解空間も変化しうる
  • 時間制約などがある場合は特に効率的な探索ができるよう解空間の構造、近傍サイズなども考慮
    • すべての実行解は、任意の実行解から到達可能、など
  • 効率的な探索を行えるようにするためには以下のような構造の近傍を避けたり、別な探索手法など検討
    • とげとげ、ぎざぎざ
    • 深いくぼみ
    • 平坦
冷却スケジュール
  • 初期温度T
    • 十分高い温度から始めるべき
    • ただし、場合によっては良い初期解＆低い温度にしてもよい可能性もある？
  • 温度の減少関数CalcTemp
    • 十分ゆっくり冷却させる
    • 冷却速度が時間に依る/依らない関数、複雑な速度変化の関数など様々考えられる
    • 例：T_k = r^k * 初期温度(ただし、r=0.8〜0.99程度)、T_k = 初期温度 / log_2(k+2)、など
  • 各温度での反復回数R
    • 近傍をまんべんなく探索できることが求められるが、近傍定義に依るのでそっちのほうが重要
  • 終了条件
    • 制限時間、解のスコアの変動がなくなる(小さくなる)、など
細かいチューニング
  • 高速化
    • 探索回数が稼げた方がよいので、スコア計算を差分でできるようにする、無駄な計算を省略するなどは重要
  • スコア関数の見直し
    • 解xでのスコアは直接的な評価値でなくても、状態の良い悪いの加点減点、整数ではなく小数、など工夫が可能
  • 遷移確率の見直し
    • 温度と悪化具合を考慮した確率であればよさそう
  • 焼きなまし処理終了後の探索
    • 最後に近傍付近で部分的に探索したり、など
  • 時間を延ばしてスコアが伸びるか？の確認
考え方、考えるべき点など

焼きなまし法を適用するべきかどうか

問題ごとの考察が重要だが、以下の概念や知見が役に立つ。

「文脈」
問題のタイプ
有名アルゴリズムの適用に囚われない

その他、概念とか用語とか

疑似平衡
  • 理論的な解析として、解の移動系列を確率過程としてのマルコフ連鎖と捉えて収束性が議論されるらしい
    • 反復は定常状態になるまで行える場合、かつ、温度をT→0にしていく場合、確率的に最適解に収束することが示される
    • 反復回数の限度を与える場合、温度パラメータの系列が十分ゆっくり冷却されるならば、収束が保証される
  • しかし、理論的に必要となる計算時間は膨大になりすぎてしまうので、実用的には(理論的枠組みからは外れるが)「各温度で、できるかぎり平衡に近い状態(疑似平衡)」を得られるようにチューニングすることが重要なポイントになるよう
受理率
  • ある温度Tでの全反復数に対して、実際に受理され移動が発生した回数の比率
    • η(T) = (温度Tでの移動回数) / (温度Tでの反復回数)
  • 受理率が低い場合、山登りと同様に局所最適解からの脱出が困難になってしまう
  • 場合によると思われるが、0.3〜0.5ぐらいだと効率の良い探索が行われるとのこと
近接最適性原理
  • 「良い解同士は何らかの類似構造を持っている」という経験的な原理
    • ある良い解と別の良い解の共通要素が多い、みたいな場合もこの原理が成り立つ
  • この原理が成り立つような解の偏りがあるならば、この類似構造を活用して効率的に最適解を探索できる可能性がある
集中化と多様化
  • 集中化
    • 「良い解の近傍により良い解が存在する」をもとに、良い解の近くを重点的に探索する戦略
  • 多様化
    • より遠くにある良い解を見つける戦略
  • 焼きなましの場合、温度や近傍構造などでこの集中化・多様化のチューニングや工夫をすることができる

参考