TSP的模拟退火成本函数

Question

成本函数对于TSP如何工作？假设我有一个距离为100的巡演，并且我稍微改变了巡视路线，对原来的巡视路线进行了4次更改，现在它的距离为50.

成本函数会给我4，因为这是数字变化;或50，因为距离的变化？或者，也许我错过了一些东西，它不是？

Answer 1

成本函数是总距离。

这正是你想要的最小。

Answer 2

成本函数是的总距离，是的，但它是也在模拟退火的能量参数$ E $。它不是直接确定过渡到该状态的概率的“能量”$ 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}$。