Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem

LIU Shufen; LENG Huang; HAN Lu

doi:10.1049/cje.2017.01.019

Volume 26 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(2): 223-229

LIU Shufen, LENG Huang, HAN Lu, “Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem,” Chinese Journal of Electronics, vol. 26, no. 2, pp. 223-229, 2017, doi: 10.1049/cje.2017.01.019

Citation:

LIU Shufen, LENG Huang, HAN Lu, “Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem,” Chinese Journal of Electronics, vol. 26, no. 2, pp. 223-229, 2017, doi: 10.1049/cje.2017.01.019

Citation:

PDF( 535 KB)

Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem

doi: 10.1049/cje.2017.01.019

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61472160).

More Information

Corresponding author: HAN Lu (corresponding author) was born in Jilin Province, China, in 1977. She received the M.S. degree from Jilin University, China. Currently she is affiliated with College of Computer Science and Technology of Jilin University. Her research area covers computer supported cooperative work, software engineering, etc. (Email:hanlu@jlu.edu.cn)
Received Date: 2015-12-04
Rev Recd Date: 2016-02-17
Publish Date: 2017-03-10

Abstract

Abstract

As a meta-heuristic approach, Ant colony optimization (ACO) has many applications. In the algorithm selection of pheromone models is the top priority. Selecting pheromone models that don't suffer negative biases is a natural choice. Specifically for the travelling salesman problem, the first order pheromone is widely recognized.When come across travelling salesman problem, we study the reasons for the success of ant colony optimization from the perspective of pheromone models,and unify different order pheromone models. In tests, we have introduced the concept of sample locations and the similarity coefficient to pheromone models. The first order pheromone model and the second order pheromone model are compared and are further analysed. We illustrate that the second order pheromone model has better global search ability and diversity of population than the former. With appropriate-scale travelling salesman problems, the second order model performs better than the first order pheromone model.
- Ant colony optimization (ACO),
- Pheromone model selection,
- The travelling salesman problem

FullText(HTML)

References(16)

References

M. Dorigo, V. Maniezzo and A. Colorni, "Ant system:Optimization by a colony of cooperating agents", IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society, Vol.26, No.1, pp.29-41, 1996.

X.J. Lei, S. Wu, L. Ge and A.D. Zhang, "Clustering ppi data based on ant colony optimization algorithm", Chinese Journal of Electronics, Vol.22,No.1, pp.118-123, 2013.

X.D. Zhang, X.Y. Cui and S.Z. Zheng, "Heuristic task scheduling algorithm based on rational ant colony optimization", Chinese Journal of Electronics, Vol.23, No.2, pp.311-314, 2014.

X.Q. Wang, T.T. Zha, C.M. Wu, J.L. Fang and M. Jiang, "Text semantics based automatic summarization for Chinese videos", Chinese Journal of Electronics, Vol.24, No.3, pp.462-467, 2015.

T. Stutzle and H.H. Hoos,"MAX-MIN ant system", Future Generation Computer Systems, Vol.16, No.8, pp.889-914, 2000.

C. Blum and M. Dorigo, "Search bias in ant colony optimization:On the role of competition-balanced systems", IEEE Transactions on Evolutionary Computation, Vol.9, No.2, pp.159-174, 2005.

D. Merkle and M. Middendorf, "Modeling the dynamics of ant colony optimization", Evolutionary Computation, Vol.10, No.3, pp.235-262, 2002.

J. Verwaeren, K. Scheerlinck and B.D. Baets, "Countering the negative search bias of ant colony optimization in subset selection problems", Computers & Operations Research, Vol.40, No.4, pp.931-942, 2013.

B.L. Chen, L. Chen and H.Y. Sun, "A method for avoiding the searching bias in ACO deceptive problem solving", Web Intelligence & Agent Systems, Vol.12, No.1, pp.51-62, 2014.

C. Blum and M.J. Blesa, "New metaheuristic approaches for the edge-weighted K-cardinality tree problem", Computers & Operations Research, Vol.32, No.6, pp.1355-1377, 2005.

A. Roli, C. Blum and M. Dorigo, "Aco for maximal constraint satisfaction problems", Proceedings of the 4th Metaheuristics International Conference, Vol.1, pp.187-191, 2001.

C. Blum and M. Sampels, "Ant colony optimization for fop shop scheduling:A case study on different pheromone representations", Congress on Evolutionary Computation, Vol.2, pp.1558-1563, 2002.

J. Montgomery, M. Randall and T. Hendtlass, "Automated selection of appropriate pheromone representations in ant colony optimization", Artificial Life, Vol.11, No.3, pp.269-291, 2005.

J. Montgomery, M. Randall and T. Hendtlass, "Solution bias in ant colony optimisation:Lessons for selecting pheromone models", Computers & Operations Research, Vol.35, No.9, pp.2728-2749, 2008.

M. Dorigo and C. Blum, "Ant colony optimization theory:A survey", Theoretical Computer Science, Vol.344, No.2-3, pp.243-278, 2005.

C. Blum and M. Dorigo, "The hyper-cube framework for ant colony optimization", IEEE Transactions on Systems Man & Cybernetics Part B (Cybernetics), Vol.34, No.2, pp.1161-1172, 2004.

Relative Articles

Supplements(0)

Cited By

Proportional views