CODEWITHSUNDEEP
algorithmartificial-intelligencetraveling-salesmansimulated-annealing
Undefined
Undefined

Reputation: 1929

Simulated annealing cost function for TSP

How does the cost function work for the TSP? Say I have a tour which has a distance of 100, and I change the tour slightly, making 4 changes to the original and it now has a distance of 50.

Would the cost function give me 4, because that's the number of changes; or 50, because of the change in distance? Or maybe I'm missing something and it's neither?

Upvotes: 1

Views: 939

Answers (2)

user8578151
user8578151

Reputation: 63

The cost function is the total distance, yes, but it is also the energy parameter $E$ in Simulated Annealing. It is not the "energy" $E$ that directly determines the probability of transitioning to that state, but it is rather $\Delta{E}$, the change in energy (the change in cost), that determines the probability $P(\Delta{E})=exp(-\Delta{E}/T)$.

So the transition from $E=100$ to $E=50$ would be $\Delta{E}=-50$ (100% probability).

The transition from $E=100$ to $E=150$ would be $\Delta{E}=50$, and a probability of ~0.7% if the temperature were 10. $P(\Delta{E}=50)=e^{-50/10}$.

Upvotes: 1

Thiago Curvelo
Thiago Curvelo

Reputation: 3740

The cost function is the total distance.

It is exactly what you want to be minimal.

Upvotes: 1

Related Questions