アニーリング（焼きなまし，Annealing）は，鉄または鋼の軟化，結晶組織の調整または内部応力の除去のため，適当な温度に加熱した後，ゆっくりと冷却する操作をいう。内部応力の除去または軟化を目的とする場合には、適当な温度（変態点以下の温度）まで加熱後徐冷する熱処理を，一方，結晶組織の調整を目的とする場合には，Ac3変態点＋50℃程度の温度に加熱後徐冷却する熱処理をいう。この冷却プロセスにより系がある安定した平衡状態まで収束するエネルギーの変化を模擬し，組合せ最適化問題を解く方法をシミュレーティド・アニーリングと呼んでいる。すなわち，初期の不安定状態（非最適解）を冷却しエネルギー最小の安定状態（最適解）を得るプロセスである。

　最適化問題によく使われる局所探索法では，最小化問題を扱うとき，現在解より常に改善方向に降下するが，この方法では大域的最適解よりも局所最適解に収束する場合が多い。シミュレーティド・アニーリング法では，評価値が改善される解を採択することに加えて，ある制限のもとで評価値が悪化する解も採択することが特徴である。高温時での初期段階では，良くない解を採択する確率を高くし，探索処理が進むに従い温度が低くなれば，良くない解を採択する確率も低くし，温度が下がった最終段階では大域的最適解が採択されるように改善されている。

　

　熱力学の法則では，新しい状態のエネルギーEjが現在のエネルギーEiよりも低いならばその移動が採択され，逆の場合には次式に示す確率で新しい状態が採択される。

　

　

　これを最適化問題（最小化問題）に利用すれば，目的関数SがSiからSjへの遷移に対し，減少する（すなわち改善される）ケースでは確率1で採択されるのに対し，悪化するケースでは温度Tと増分ΔSに依存した確率で採択されると考える。

　

　

　すなわち，生成された新しい解が採択されるかどうかの確率は，評価値（一つ前の状態との差）と，そのときの温度に依存している。これをFig. 4に示す。

　

　

　シミュレーティド・アニーリング手法では，以下のパラメータの値を指定することにより決定される。

（1）冷却係数　α

　冷却係数とは，採択確率式の温度を変化させる係数であり，一定の計算を繰り返すごとに温度TはαTに減少する。冷却係数を決定する際に，出来る限り正確な値を得るためTは徐々に減少する方が望ましく，一般には0-8≦α≦0.99とする。ここではα=0.99とした。

（2）初期温度　T0

　初期状態ではほとんどの状態で採択されなければならないために，初期温度T0における採択確率は1に近づくようにする。ここではT0=100℃とした。

（3）マルコフ連鎖の長さ　M

　これは，一定温度における計算回数を示したものである。この計算回数の中で処理を平衡状態に到達させなければならないため，Mは温度が低下するに従って増える事が望ましい。ここではM=100とした。

（4）終了時間　Time（または最終温度）

　マルコフ連鎖の最終解が連続して変化しない場合，または解が目的の値に達した場合に，処理を停止する時間または温度。今回は計算回数100,000を終了条件とした。

（5）推移係数　β

　一定の温度における計算回数を変化させる係数であり，一定の計算を繰り返すごとにマルコフ連鎖MはβMに変化する。ここではβ=1とした。

　

2）現在解Siの近傍解Sj(j∈S)をランダムに選ぶ。

3）冷却スケジュールαに基づいてTを冷却。

4）停止条件を満たすならば停止