焼きなまし法（やきなましほう、、SAと略記、疑似アニーリング法、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案し、1985年に V. Cerny が再発見した。その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。SAアルゴリズムは、解を繰り返し求め直すにあたって、現在の解のランダムな近傍の解を求めるのだが、その際に与えられた関数の値とグローバルなパラメータ "T"（温度を意味する）が影響する。そして、前述の物理過程との相似によって、"T"（温度）の値は徐々に小さくなっていく。このため、最初は"T"が大きいので、解は大胆に変化するが、"T"がゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。焼きなまし法では、探索空間の各点「s」は物理システムの「状態」に対応し、最小化すべき関数 "E"("s") は物理状態の「内部エネルギー」に対応する。従って、目標はシステムを任意の「初期状態」からできる限りエネルギーが最小の状態にすることである。各ステップでは、SAのヒューリスティックは、現在状態 "s" のいくつかの近傍 "s' "を検討し、現在状態 "s" のままがよいか、いずれかの近傍状態に遷移するのがよいかを確率的に決定する。その際、システムが最終的にエネルギーの低い状態へ向かうよう考慮する。このステップは、十分よい結果が得られるまで、あるいは予定された計算時間が尽きるまで繰り返される。各状態の近傍は、アプリケーション固有の方法で、通常ユーザーによって指定される。たとえば、巡回セールスマン問題において、個々の状態は、一般に「ツアー」（訪問する都市の順列）と呼ばれる。その場合、近傍とは、都市の順列の中で一箇所だけ都市の順番を入れ替えた順列と考えることができる。現在状態 "s" から新たな状態候補 "s' " への遷移確率は、二つの状態のエネルギー "e" = "E"("s") と "e' "= "E"("s' ") の関数 "P"("e

出典:wikipedia