Науковий вісник НГУ

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

• 
• 

User Rating:  / 0

PoorBest 

Details

Category: Information technologies, systems analysis and administration

Last Updated on 08 February 2016

Published on 08 February 2016

Hits: 4294

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.

2015_06_lan
2016-02-08  560.88 KB  964

• < Prev
• Next >