INFORMATION CHANGE THE WORLD

International Journal of Education and Management Engineering(IJEME)

ISSN: 2305-3623 (Print), ISSN: 2305-8463 (Online)

Published By: MECS Press

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

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

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


Views:76   Downloads:7

Author(s)

Shuoben Bi,Xueshi Dong,Yan Ma

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.

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).