Apply the simulated annealing search algorithm (Algorithm 15D) to a TSP with 8 cities. Generate your own distance matrix randomly use integers in Excel. Moreover, use Excel to find the random interchanges (you can use the randbetween function) and to generate the random numbers needed for accept/reject decisions (you can use the rand() function). Let t_max be 15. Pick your own starting temperature to be reduced by 20% after the 10th iteration. Give your results as a table like in the book but with more details (the calculated probabilities, the generated random numbers, ...). Also make sure to provide your distance matrix

ALGORITHM 15D: SIMULATED ANNEALING SEARCH Step 0: Initialization. Choose any starting feasible solution xo), an iter- ation limit tmax, and a relatively large initial temperature q > 0. Then, set incumbent solution x) and solution index to. Step 1: Stopping. If no move Ax in move set M leads to a feasible neighbor of current solution x(+), or if t = tmax, then stop. Incumbent solution X is an approximate optimum. Step 2: Provisional Move. Randomly choose a feasible move AxEM as a provisional Ax(t+1), and compute the (possibly negative) net objec- tive function improvement Aobj for moving from x() = (0,0,0,1) to (x(t) + Ax(t+1)) (increase for a maximize, decrease for a minimize). Step 3: Acceptance. If Ax(+1) improves, or with probability Aobi/a if Aobj = 0, accept Ax(+1) and update x(t+1) X(t) + Ax(t+1) Otherwise, return to Step 2. Step 4: Incumbent Solution. If the objective function value of x(t+1) is superior to that of incumbent solution X, replace x(t+1). Step 5: Temperature Reduction. If a sufficient number of iterations have passed since the last temperature change, reduce temperature q. Step 6: Increment. Increment tot + 1, and return to Step 1. ALGORITHM 15D: SIMULATED ANNEALING SEARCH Step 0: Initialization. Choose any starting feasible solution xo), an iter- ation limit tmax, and a relatively large initial temperature q > 0. Then, set incumbent solution x) and solution index to. Step 1: Stopping. If no move Ax in move set M leads to a feasible neighbor of current solution x(+), or if t = tmax, then stop. Incumbent solution X is an approximate optimum. Step 2: Provisional Move. Randomly choose a feasible move AxEM as a provisional Ax(t+1), and compute the (possibly negative) net objec- tive function improvement Aobj for moving from x() = (0,0,0,1) to (x(t) + Ax(t+1)) (increase for a maximize, decrease for a minimize). Step 3: Acceptance. If Ax(+1) improves, or with probability Aobi/a if Aobj = 0, accept Ax(+1) and update x(t+1) X(t) + Ax(t+1) Otherwise, return to Step 2. Step 4: Incumbent Solution. If the objective function value of x(t+1) is superior to that of incumbent solution X, replace x(t+1). Step 5: Temperature Reduction. If a sufficient number of iterations have passed since the last temperature change, reduce temperature q. Step 6: Increment. Increment tot + 1, and return to Step 1