Articles

TSP problem solving method based on big-small ant colony algorithm

User Rating:  / 0
PoorBest 

Authors:

Yihua Lan, Nanyang Normal University, Nanyang, China

Yanwei Tian, Anyang Normal University, Anyang 455002, China

Yan Tian, Nanyang Normal University, Nanyang, China

Jinjiang Liu, Nanyang Normal University, Nanyang, China

Xiao Jia, Southern Medical University, Guangzhou 510515, China

Abstract:

Purpose. The traditional ant colony optimization algorithms have been used to solve the NP-hard problem, Traveling Salesman Problem (TSP), which is based on the rule that ants tend to choose high pheromone concentrated path. The max-min ant system (MMAS) most commonly achieves the nearest neighbouring city and always formulates the local optimal solution.

Methodology. The “big-small ant colony” algorithm with a kind of “jump pit strategies” has been formulated. Where, the big ants can carry much more pheromones and are prone to making mistakes.

Findings. First, the “big-small ant colony” algorithm was employed to accelerate the convergence speed. Then, by using a kind of jump pit concepts, a wider range path searching was provided, where the “small jumping strategy” allowed more than one ant to go along a different path, and the “big jumping strategy” put a barrier on the pheromone convergence path forcing the ants to choose other different paths. The experimental results showed that the modified algorithm always converges to the optimal results unlike the MMAS.

Originality. The modified ant colony optimization algorithm was studied and the effectiveness of the idea, which was put forward, was discussed.

Practical value. The proposed algorithm may be employed to solve other problems, especially together with some deterministic algorithm to realize quick global optimization.

References:

  1. Pang, S., Ma, T., and Liu, T. (2015), “An improved ant colony optimization with optimal search library for solving the traveling salesman problem“. Journal of Computational & Theoretical Nanoscience, vol.12, no.5, pp. 440−1444.

  2. Bu, Y., Li, T. Q., and Zhang, Q. (2015), “A weighted max-min ant colony algorithm for tsp instances“. Ieice Trans Fundamentals, vol.98, no.3, pp. 894−897.

  3. Basheerjasser, M., Sarmini, M., and Yaseen, R. (2014), “Ant colony optimization (ACO) and a variation of bee colony optimization (BCO) in solving tsp problem, a comparative study“. International Journal of Computer Applications, vol.96, no.1, pp. 1−8.

  4. Camp, C. V., and Bichon, B. J. (2014), “Design of space trusses using ant colony optimization“. Journal of Structural Engineering, vol.130, no.5, pp. 741−751.

  5. Shuang, B., Chen, J., and Li, Z. (2011), “Study on hybrid ps-aco algorithm“. Applied Intelligence, vol.34, no.1, pp. 64−73.

  6. Mavrovouniotis, M., and Yang, S. (2011), “A memetic ant colony optimization algorithm for the dynamic travelling salesman problem“. Soft Computing, vol.15, no.7, pp. 1405−1425.

  7. Dorigo, M., and Blum, C. (2005), “Ant colony optimization theory: a survey“. Theoretical Computer Science. Vol.344, no.1, pp. 243−278

  8. Dorigo, M. (1997), “Ant colonies for the traveling salesman problem“. Biosystems, vol.12, no.2, pp. 667−670.

  9. Dorigo, M., and Stützle, T. (1999), “The ant colony optimization meta-heuristic“. New Ideas in Optimization, vol.28, no.3, pp. 11−32.

 

Files:
2015_06_lan
Date 2016-02-08 Filesize 560.88 KB Download 408

Visitors

3124215
Today
This Month
All days
266
5396
3124215

Guest Book

If you have questions, comments or suggestions, you can write them in our "Guest Book"

Registration data

ISSN (print) 2071-2227,
ISSN (online) 2223-2362.
Journal was registered by Ministry of Justice of Ukraine.
Registration number КВ No.17742-6592PR dated April 27, 2011.

Contacts

D.Yavornytskyi ave.,19, pavilion 3, room 24-а, Dnipro, 49005
Tel.: +38 (056) 746 32 79.
e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.
You are here: Home