Using the Improved Ant Colony Algorithm to Solve the Chinese TSP

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)

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  -