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

Authors: ChangYing Wang; Min Lin; YiWen Zhong; Hui Zhang

Addresses: College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou, 350002, China ' College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou, 350002, China ' College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou, 350002, China ' Pervasive Technology Institute, Indiana University, Purdue University Indianapolis, USA

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.

Keywords: multi-agent simulated annealing; travelling salesman problem; TSP; instance-based sampling; finite-time behaviour; multi-agent systems; MAS; agent-based systems.

DOI: 10.1504/IJCSM.2015.071818

International Journal of Computing Science and Mathematics, 2015 Vol.6 No.4, pp.336 - 353

Received: 19 Jul 2014
Accepted: 22 Sep 2014
Published online: 19 Sep 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article