Proceedings of the 2014 International Conference on Future Computer and Communication Engineering

Using the Improved Ant Colony Algorithm to Solve the Chinese TSP

Authors
Jing Sun, Yan-ping Bai, Hong-ping Hu, Jin-na Lu
Corresponding Author
Jing Sun
Available Online March 2014.
DOI
10.2991/icfcce-14.2014.28How to use a DOI?
Keywords
CTSP, Mixed ant colony algorithm, partial search strategy, population diversity
Abstract

In this paper, an improved mixed Ant Colony Algorithm is proposed. The introduced algorithm is based on the traditional ant colony system algorithm. At the beginning an initial result is constructed using the nearest neighbour method. Build on top of that, the result is improved using 2-opt partial search strategy. Only the best two colonies’ global pheromones are updated which used the rank-based ant colony system idea. Then we used MATLAB to simulate the classic Chinese TSP problem the dimension of which is 31. The best result we achieved is 15377. This result surpasses all the other results we have ever known. Afterwards we used a method of counting the sum of the route edges to measure the population diversity of our algorithm. Then we compared the population diversity of our improved mixed algorithm and the base ACO algorithm. The result shows our algorithm has higher population diversity which gives us a theory support why our algorithm can achieve best result than ever known.

Copyright
© 2014, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2014 International Conference on Future Computer and Communication Engineering
Series
Advances in Intelligent Systems Research
Publication Date
March 2014
ISBN
978-94-6252-005-9
ISSN
1951-6851
DOI
10.2991/icfcce-14.2014.28How to use a DOI?
Copyright
© 2014, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Jing Sun
AU  - Yan-ping Bai
AU  - Hong-ping Hu
AU  - Jin-na Lu
PY  - 2014/03
DA  - 2014/03
TI  - Using the Improved Ant Colony Algorithm to Solve the Chinese TSP
BT  - Proceedings of the 2014 International Conference on Future Computer and Communication Engineering
PB  - Atlantis Press
SP  - 116
EP  - 119
SN  - 1951-6851
UR  - https://doi.org/10.2991/icfcce-14.2014.28
DO  - 10.2991/icfcce-14.2014.28
ID  - Sun2014/03
ER  -