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}$.