Comparative Analysis of Genetic Algorithm, Particle Swarm Optimization and Ant Colony Optimization for TSP
Abstract
As a typical combinatorial problem, the travelling
salesman problem (TSP) has attracted extensively research interest.
Ant Colony optimization (ACO), Genetic Algorithm (GA), Particle
swarm optimization(PSO) stochastic search methods that mimic the
natural evolution and/or the social behavior of species , have great
potentials to solve the combination optimization problems,
respectively used in solving traveling salesman problem.
Performance comparative analyses have been done by using ACO,
GA and PSO respectively in solving TSP in this paper. The
experiments show the advantages and disadvantages used only ACO,
GA and PSO. The comparative results are shown. And it is devised
that GA is better approach to solve the traveling salesman problem.
Keywords
Full Text:
PDFReferences
K. A. Smith, ―Neural networks for combinatorial optimization: A review
of more than a decade of research,‖ INFORMS J. Comput., vol. 11, no.
, pp. 15–34, 1999.
G. Reinelt, ―TSPLIB—A traveling salesman problem library,‖ ORSA J.
Computing, vol. 3, no. 4, pp. 376–384, 1991.
G. Laporte, ―The vehicle routing roblem: An overview of exact and
approximate algorithms,‖ Eur. J. Oper. Res., vol. 59, pp. 345–358, 1992.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and
MachineLearning. Reading, MA: Addison-Wesley, 1989.
N. Krasnogor and J. Smith et al., ―A memetic algorithm with selfadaptive
local search: TSP as a case study,‖ in Proc. enetic Evolutionary
Computation Conf., D. Whitley et al., Eds., 2000, pp. 987–994.
J. Knox, ―Tabu search performance on the symmetric traveling salesman
problem,‖ Comput. Oper. Res., vol. 21, pp. 867–876, 1994.
Z. B. Xu, H. D. Jin, K. S. Leung, L. Leung, and C. K. Wong, ―An
automata network for performing combinatorial optimization,‖
Neurocomputing, vol. 47, pp. 59–83, Aug. 2002.
D. S. Johnson and L. A. McGeoch, ―The travelling salesman problem: A
case study,‖ in Local Search in Combinatorial Optimization, E. Aarts
and J. Karel, Eds. New York: Wiley, 1997, pp. 215–310.
M. Dorigo and L. M. Gambardella, ―Ant colony system: A cooperative
learning approach to the traveling salesman problem,‖ IEEE Trans.
Evol. Comput., vol. 1, pp. 53–66, Apr. 1997
H. Al-Mulhem and T. Al-Maghrabi, ―Efficient convex-elastic net
algorithm to solve the Euclidean traveling salesman problem,‖ IEEE
Trans. Syst., Man, Cybern. B, vol. 28, pp. 618–620, Aug. 1998.
M. Budinich, ―A self-organizing neural network for the traveling
salesman problem that is competitive with simulated Annealing,‖ Neural
Comput., vol. 8, pp. 416–424, 1996.
Holland J. ―Adaptation in natural and artificial systems‖. Ann Arbor,
MI: University of Michigan Press; 1975.
Colorni A, Dorigo M, Maniezzo V. ―Distributed optimization by ant
colonies‖. In: The First European conference on Artificial Life,
France:Elsevier, 1991:134-142
Dorigo M. ―Optimization, Learning and Natural Algorithm‖.
Ph.D.thesis, Dipartimento di Elettronica, Politecnico di Mi2 lano, IT,
Jing Feng, Ning Shu. ―Swarm Intelligent Theory and its Study of
Application‖.Computer Engineering and Application, 2006.
http://www.iwr.uni~heidelberg.de/groups/comopt/software/TSPLI
B95/tspB95/tsp
Eberhart R ,Kennedy J. ―A New Optimizer Using Particles Swarm
Theory‖, Roc. Sixth Intemational Symposium on Micro Machine and
Human Science (Nagoya, Japan) IEEE Service Center, Piscataway,
NJ:39-43, 1995
Eberhart R, and Shi Y. ―Comparison between Genetic Algorithms and
Particle Swarm 0ptimization‖.The 7thAnnual .Conference on
Evolutionary Programming, San Diego, USA,1998
Angeline P. ―Evolutionary Optimization versus Particle Swarm
Optimization‖: Philosophy and Performance Difference.The 7th Annual
Conference. On Evolutionaxy Programming, San Diego,USA,1998.
Kennedy J, and Spears W. ―Matching Algorithms to Problems: An
Experimental Test of the Particle Swarm and some Genetic Algorithms on the Multimodal Problem Generator‖. IEEE Intemational Conference
on Evolutionaxy Computation, Anchorage, Alaska, USA,1998
Wang kang-Ping, Haung Lan,Zhou Chun-Guang: ―Particle swarm
optimization for Travelling Salesman Problem‖. Proceeding of the
second International Conference on machine Learning and
Cybermetics,‘Xi‘an,2-5 November 2003.
Refbacks
- There are currently no refbacks.