Solving travelling salesman problem using multiagent simulated annealing algorithm with instance-based sampling

Abstract

Simulated annealing (SA) algorithm is extremely slow in convergence, and the implementation and efficiency of parallel SA algorithms are typically problem-dependent. To overcome such intrinsic limitations, we present a multi-agent SA algorithm with instance-based sampling (MSA-IBS) by exploiting learning ability of instance-based search algorithm to solve travelling salesman problem (TSP). In MSA-IBS, a population of agents run SA algorithm collaboratively. Agents generate candidate solutions with the solution components of instances in current population. MSA-IBS achieves significant better intensification ability by taking advantage of learning ability from population-based algorithm, while the probabilistic accepting criterion of SA keeps MSA-IBS from premature stagnation effectively. By analysing the effect of initial and end temperature on finite-time behaviours of MSA-IBS, we test the performance of MSA-IBS on benchmark TSP problems, and the algorithm shows good trade-off between solution accuracy and CPU time.