algorithm - TSP のシミュレートされたアニーリング コスト関数

Question

TSP のコスト関数はどのように機能しますか? 距離が 100 のツアーがあり、元のツアーに 4 つの変更を加えてツアーをわずかに変更し、距離が 50 になったとします。

変更の数なので、コスト関数は 4 を返します。または50、距離の変化のため？それとも、何かが欠けていて、どちらでもないのでしょうか?

Answer 1

コスト関数は合計距離です。

それはまさにあなたが最小限にしたいものです。

Answer 2

コスト関数は総距離ですが、シミュレーテッド アニーリングのエネルギー パラメータ $E$でもあります。その状態に遷移する確率を直接決定するのは「エネルギー」$E$ ではなく、確率を決定するの$\Delta{E}$はエネルギーの変化 (コストの変化)$P(\Delta{E})=exp(-\Delta{E}/T)$です。

したがって、$E=100$ から $E=50$ への遷移は$\Delta{E}=-50$(100% の確率) になります。

$E=100$ から $E=150$ への遷移は $\Delta{E}=50$ となり、温度が 10 の場合、確率は ~0.7% になります$P(\Delta{E}=50)=e^{-50/10}$。