メタヒィーリスティックスという言葉は、知っておいたほうがいいです。ヒューリスティックスを日本語で説明すると、「問題解決や意思決定の場において、システマティックないしは数理的な手順（アルゴリズム）によらずに、ほどほどに満足できる近似的な解を得る手法」です。探索しながら、なるべくよい解を見つける・・AIや機械学習よりも、人間的かもしれないですね。
Simulated Annealing （以下 SA）法、メタヒィーリスティックス手法の一つで、最適化（最適解）を求めます。
海外の論文を含めた、SAとはという内容を集めて、文脈が合うように、かつ、分かりやすくまとめました。
海外の論文は私自身が翻訳しています。
SAアルゴリズムは、Kirkpatricらによって導入された、組み合わせ最適化問題を解決するための局所最適から逃れることができる局所探索手順である。一言で説明すると、与えられた初期状態から探索を始め、状態を遷移させて探索を続けることで、最終的にエネルギが最小となる状態、つまり目的関数の大域的(グローバル)最適解を発見することを目的としている。
手順を開始するにあたり，SAは初期解を求めて近傍解を生成する。近傍解が現存する解よりも優れている場合、その優れている解に置き換わる。そうでない場合は、現存する解が使用される。このプロセスは、近傍の解決策に有意な改善が見られないか、事前に設定された条件が満たされるまで繰り返される。SAでは、この反復的な改善アプローチを使用しているが、特に、探索アルゴリズムが局所最適から抜け出すことを可能にする。
SAアルゴリズムは、高い初期温度Tで開始し、温度を下げる変数（パラメータ）aを設定して、そのエネルギー差Itを算出する。エネルギー差Itが0以下であれば，新しい解を受け入れる。それ以外の場合は，大域的(グローバル)最適解を探索しながらランダムに見つけ出す。次の状態が現在の状態よりも悪い目的関数となる改悪方向への遷移も、一定の確率特性exp（It/kT）（Kは定数）、つまり、ある確率で受け入れられる。悪い解は、局所最適解の確率から飛び出して、最終的には大域最適解に近づく可能性がある。SAの特徴は、多くの最適化手法が局所最適解に陥ってしまうという欠点を持っているのに対して、SAは改良方向のみに向かって探索を行うのではなく、改悪方向にも探索が進むので、局所最適解に陥らず、真の最適解に到達することができる。
次回は、SAの弱点、課題をまとめてブログします。