Skip to content

Instantly share code, notes, and snippets.

@nojima

nojima/焼きなまし法.adoc

Last active March 8, 2021 02:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nojima/11524e3d0b1e4b2067a68554544dabc6 to your computer and use it in GitHub Desktop.
Save nojima/11524e3d0b1e4b2067a68554544dabc6 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
焼きなまし法.adoc

焼きなまし法

  • 世の中に存在する組み合わせ最適化問題は効率的なアルゴリズムが存在しない場合も多い。

    • SAT

    • 巡回セールスマン問題

    • 負の長さの閉路を持つグラフに対する最短経路問題

    • オセロ

    • ぷよぷよ

  • 有名な問題の場合は専用のソルバーが開発されている場合もあるがマイナーな問題の場合、専用ソルバーは存在しない

  • メタヒューリスティクス

    • 様々な問題に対して汎用的に使えるヒューリスティック

  • 有名なメタヒューリスティクス

    • 山登り法

    • 焼きなまし法

    • ビームサーチ

    • 遺伝的アルゴリズム

山登り法

  1. 適当な初期解を作る。例えば、巡回セールスマン問題(TSP)なら、都市の列をランダムシャッフルしたものを初期解とすることができる。

  2. 以下をスコアが改善する限り繰り返す:

    1. 現在の解の近傍からランダムに一つ選ぶ。例えば、TSP なら現在の都市の列から都市を2つ選んでswapしたものを近傍として定義できる。

    2. 選んだ近傍のスコアを計算し、もしスコアが改善しているならば現在の解をその解で置き換える。

焼きなまし法

山登り法は局所最適解に嵌ってしまうという問題がある。焼きなまし法はスコアが下がる方向にも確率的に遷移することで、局所最適解に陥るのを避けようとするアルゴリズムである。

  1. 適当な初期状態を作る。例えば、巡回セールスマン問題(TSP)なら、都市の列をランダムシャッフルしたものを初期状態とすることができる。

  2. 温度 を初期温度に設定する。

  3. 以下を時間が許す限り繰り返す:

    1. 現在の状態の近傍からランダムに一つ選ぶ。例えば、TSP なら現在の都市の列から都市を2つ選んでswapしたものを近傍として定義できる。

    2. 選んだ近傍のスコアを計算し、以下を行う:

      • もしスコアが改善しているならば、その近傍に遷移する。

      • そうでない場合は Acceptance probabilities を計算し、その確率でその近傍に遷移する。

    3. アルゴリズムの進行状態に応じて温度を更新する。

トピック

  • 状態

  • 近傍

  • Acceptance probabilities

    • ΔS = 次のスコア - 現在のスコア

    • if ΔS >= 0 then

      • P = 1

    • else

      • P = exp(-ΔS / T)

  • The annealing schedule

    • 温度をどういう式で変化させるか？

焼きなまし職人の朝は早い

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment