Shuoben Bi; Xueshi Dong; Yan Ma

International Journal of Education and Management Engineering (IJEME)

IJEME Vol. 2, No. 9, 29 Sep. 2012

Cover page and Table of Contents: PDF (size: 127KB)

The Design and Analysis of TSP Problem Based on Genetic Algorithm and Ant Colony Algorithm

Full Text (PDF, 127KB), PP.56-60

Views: 0 Downloads: 0

Author(s)

Shuoben Bi ^1,* Xueshi Dong ¹ Yan Ma ¹

1. School of Computer & Software, Nanjing University of Information Science & Technology, Jiangsu Nanjing 210044, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijeme.2012.09.09

Received: 15 Jun. 2012 / Revised: 20 Jul. 2012 / Accepted: 25 Aug. 2012 / Published: 29 Sep. 2012

Index Terms

Genetic Algorithm, Ant Colony Algorithm, TSP, The shortest path, Combinatorial optimization

Abstract

This paper firstly makes a brief introduction about TSP problem, Genetic Algorithm and Ant Colony Algorithm, then gives the basic principles and steps of the two kinds of algorithms in solving the TSP problem, does design analysis and experiments of the two kinds of algorithms for solving TSP problem, and draws some useful conclusions: under the experimental conditions, while the population during 5 to 15, the Ant Colony Algorithm for TSP problem is more effective; when the population is 1~2.5 times than cities, it can get better results by using Genetic Algorithm for solving TSP.

Cite This Paper

Shuoben Bi,Xueshi Dong,Yan Ma,"The Design and Analysis of TSP Problem Based on Genetic Algorithm and Ant Colony Algorithm", IJEME, vol.2, no.9, pp.56-60, 2012. DOI: 10.5815/ijeme.2012.09.09

Reference

[1] Pan Zhengjun, Kang Lishan, Chen Yuping. Evolutionary Computation[M]. Beijing: Tsinghua University Press, 1998,5(in chinese).
[2] Duan Haibin. Ant colony algorithm theory and its applications [M]. Beijing: Science Press , 2005: 112-116(in chinese).
[3] Rudolph C. Convergence properties of canonical Genetic Algorithms[J]. IEEE Trans on Neural Networks, 1994, 5(1): 96-101.
[4] Thomas S, Holger H H, MAX-MIN ant system[J]. Fulture Generation Computer Systems, 2000, 16(8): 889 914.
[5] Cao Luyin, Luo Bin, Qing Minghao. A Genetic Algorithm for Finding Shortest Paths[J]. Journal of Hefei University of Technology (Natural Science), 1996, 19 (3): 112-116(in chinese).
[6] Wang Ying, Xie Jianying. An Adaptive Ant Colony Algorithm and Simulation[J]. Journal of System Simulation, 2002,2 :39-47(in chinese).
[7] Xu Jingming, Cao Xianbin, Wang Xufa. Polymorphic Ant Colony Algorithm [J]. Journal of University of Science and Technology of China, 2005,35 (1) :59-65(in chinese).