-
世の中に存在する組み合わせ最適化問題は効率的なアルゴリズムが存在しない場合も多い。
-
SAT
-
巡回セールスマン問題
-
負の長さの閉路を持つグラフに対する最短経路問題
-
オセロ
-
-
有名な問題の場合は専用のソルバーが開発されている場合もあるがマイナーな問題の場合、専用ソルバーは存在しない
-
メタヒューリスティクス
-
様々な問題に対して汎用的に使えるヒューリスティック
-
-
有名なメタヒューリスティクス
-
山登り法
-
焼きなまし法
-
ビームサーチ
-
遺伝的アルゴリズム
-
-
適当な初期解を作る。例えば、巡回セールスマン問題(TSP)なら、都市の列をランダムシャッフルしたものを初期解とすることができる。
-
以下をスコアが改善する限り繰り返す:
-
現在の解の近傍からランダムに一つ選ぶ。例えば、TSP なら現在の都市の列から都市を2つ選んでswapしたものを近傍として定義できる。
-
選んだ近傍のスコアを計算し、もしスコアが改善しているならば現在の解をその解で置き換える。
-
山登り法は局所最適解に嵌ってしまうという問題がある。焼きなまし法はスコアが下がる方向にも確率的に遷移することで、局所最適解に陥るのを避けようとするアルゴリズムである。
-
適当な初期状態を作る。例えば、巡回セールスマン問題(TSP)なら、都市の列をランダムシャッフルしたものを初期状態とすることができる。
-
温度 を初期温度に設定する。
-
以下を時間が許す限り繰り返す:
-
現在の状態の近傍からランダムに一つ選ぶ。例えば、TSP なら現在の都市の列から都市を2つ選んでswapしたものを近傍として定義できる。
-
選んだ近傍のスコアを計算し、以下を行う:
-
もしスコアが改善しているならば、その近傍に遷移する。
-
そうでない場合は Acceptance probabilities を計算し、その確率でその近傍に遷移する。
-
-
アルゴリズムの進行状態に応じて温度を更新する。
-
-
状態
-
近傍
-
Acceptance probabilities
-
ΔS = 次のスコア - 現在のスコア
-
if ΔS >= 0 then
-
P = 1
-
-
else
-
P = exp(-ΔS / T)
-
-
-
The annealing schedule
-
温度をどういう式で変化させるか?
-