Question

solve travelling salesman problem using different simulated annealing cooling schedule

Answer 1

salesman problem using different simulated annealing cooling schedule:::----------

Simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. Parameters’ setting is a key factor for its performance, but it is also a tedious work. To simplify parameters setting, we present a list-based simulated annealing (LBSA) algorithm to solve traveling salesman problem (TSP). LBSA algorithm uses a novel list-based cooling schedule to control the decrease of temperature. Specifically, a list of temperatures is created first, and then the maximum temperature in list is used by Metropolis acceptance criterion to decide whether to accept a candidate solution. The temperature list is adapted iteratively according to the topology of the solution space of the problem. The effectiveness and the parameter sensitivity of the list-based cooling schedule are illustrated through benchmark TSP problems. The LBSA algorithm, whose performance is robust on a wide range of parameter values, shows competitive performance compared with some other state-of-the-art algorithm

Traveling Salesman Problem (TSP)
– Given 6 cities and the traveling cost between
any two cities
– A salesman need to start from city 1 and travel
all other cities then back to city 1
– Minimize the total traveling cost

Example: SA for traveling salesman

• Solution representation
– An integer list, i.e., (1,4,2,3,6,5)
• Search mechanism
– Swap any two integers (except for the first one)
• (1,4,2,3,6,5)
 (1,4,3,2,6,5)
• Cost function

Example: SA for traveling salesman
• Annealing schedule (i.e. How to reduce the
temperature)
– A constant value is subtracted to get new temperature, T’
= T – Td
– For instance new value is 90% of previous value.
• Depending on solution space coverage rate