Open Access Open Access  Restricted Access Subscription or Fee Access

Comparative Analysis of Genetic Algorithm, Particle Swarm Optimization and Ant Colony Optimization for TSP

Neha Goyal, Pradeep Mittal

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


Ant Colony, Optimization, Particle Swarm, Genetic Algorithm, Travelling Salesman

Full Text:

PDF

References


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.