LIU Shufen, LENG Huang, HAN Lu. Pheromone Model Selection in Ant Colony Optimization for the Travelling Salesman Problem[J]. Chinese Journal of Electronics, 2017, 26(2): 223-229. 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[J]. Chinese Journal of Electronics, 2017, 26(2): 223-229. doi: 10.1049/cje.2017.01.019

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

doi: 10.1049/cje.2017.01.019
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (210) PDF downloads(946) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return