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

DOI10.1504/IJCSM.2015.071818MaRDI QIDQ2224031zbMATH OpenFDO

Authors ChangYing Wang, Min Lin, Yiwen Zhong, Hui Zhang

Publication date 3 February 2021

Published in International Journal of Computing Science and Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/IJCSM.2015.071818

zbMATH Keywords

agent-based systemsfinite-time behaviourinstance-based samplingMASmulti-agent simulated annealingmulti-agent systemstravelling salesman problemTSP

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: 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.

Recommendations

• A multi-agent approach for solving traveling salesman problem
• Simulated annealing-based ant colony algorithm for traveling salesman problems
• An Improved Simulated Annealing Algorithm with Genetic Characteristics and the Traveling Salesman Problem
• Simulated annealing versus Metropolis for a TSP instance
• A new simulated annealing approach for travelling salesman problem

Cited in

(5)

• A multi-agent approach for solving traveling salesman problem
• scientific article; zbMATH DE number 6867742 (Why is no real title available?)
• scientific article; zbMATH DE number 2112439 (Why is no real title available?)
• scientific article; zbMATH DE number 7158351 (Why is no real title available?)
• The adaptive two-stage ant colony simulated annealing algorithm for solving the traveling salesman problem

This page was built for publication: Solving travelling salesman problem using multiagent simulated annealing algorithm with instance-based sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2224031)