焼きなまし法
各状態の近傍は、アプリケーション固有の方法で、通常ユーザーによって指定される。たとえば、巡回セールスマン問題において、個々の状態は、一般に「ツアー」(訪問する都市の順列)と呼ばれる。その場合、近傍とは、都市の順列の中で一箇所だけ都市の順番を入れ替えた順列と考えることができる。
現在状態 s から新たな状態候補 s' への遷移確率は、二つの状態のエネルギー e = E(s) と e' = E(s' ) の関数 P(e, e' , T) で与えられる。ここで T は「温度」に相当し、時間と共に変化するグローバルなパラメータである。
遷移確率 P の基本的な必須条件として、e' > e のときにゼロでない値を返さなければならないという点があげられる。これは、ときには「悪い」と思われる状態(エネルギーの高い状態)へもシステムが遷移可能であることを意味する。これは「ローカルな極小状態」に張り付いてしまうのを防ぐ機能である。「ローカルな極小状態」とは、そのエネルギーが真の極小には程遠いが、近傍とだけ比べれば極小であるような状態を意味する。
一方で、Tが 0に近くなるにつれて、e' > e であれば P(e, e' , T) の値をゼロに近づけ、e' < e であればその値を大きくする。これにより、Tが十分に小さくなれば、システムは極小に向かい、逆の動きは封じられる。特に T が 0 になると、山登り法を使うことで近傍の極小に確実に向かわせることもできる。
関数 P は e' −e の値が増大する際には確率を減らす値を返すように設定される。つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、どんどん上昇している場合よりも高いという考え方である。しかし、この条件は必ずしも必須ではなく、上記の必須条件が満たされていればよい。
これらの特性により、状態 s の変化は温度 T に大きく依存する。大まかに言えば、sの変化は T が大きいときには劇的に変化し、T が小さくなるとゆるやかに変化する。