QUESTION $2$: $($Travelling Salesman Problem$-$Simulated Annealing Local Search$)$

$[5$ POINTS$]$

Use Simulated Annealing $($SA$)$ algorithm for solving the Travelling SalesmanProblem $($TSP$).$ The salesman has to travel all cities only once and return back to thestarting city. The cities and the distances between them are shown in the figure below.

Consider the following points:

Randomly select starting city $($e$.$g$.$ ABCD$).$

Allow search to occasionally go on an ascending direction. By allowing occasional

ascent in the search process, we might be able to escape the trap of local minima.

Assume the performance change in the search direction is AE$.$

Always accept a descending step, i$.$e$.$ AE$<=0$

Accept ascending step only if it passes a random test,

T$)>$ random$[0,1)$

T$.$ the annealing temperature, is the parameter that control the frequency of

acceptance of ascending steps, and k is the iteration$/$time value $(1,2,3...).$

We gradually reduce temperature $7($k$).$

At each temperature, search is allowed to proceed for a certain number of steps.

L$($k$).$

The choice of parameters $($T$($k$),$ L$($k$))$ is called the cooling scheduleTwo route are neighbors iff two neighboring cities in one design are in the opposite

order in another design.

Neighbors are processed by the order of lower to higher indices

Simulated Annealing Algorithm:

$0)$k$=0$

$1)$ Search $($i j$).$ performance difference A:

$2)$ If A$<0$ then accept. else

if exp$(-$A$/$T$($k$))>$ random$[0,1)$ then accept:$3)$ Repeat $1)$ and $2)$ for L$($k$)$ steps:

$4)$ k$=$k$+1$:

$5)$ Repeat $1)-4)$ until stopping criterion is met