ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

A TSP algorithm based on clustering ensemble ACO and restricted solution space

  • 1.

    College of Information Science and Engineering, Ningbo University, Ningbo 315210, China

  • 2.

    College of Science & Technology, Ningbo University, Ningbo 315210, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2016.09.010
  • Received Date: 01 March 2016
  • Accepted Date: 17 September 2016
  • Rev Recd Date: 17 September 2016
  • Publish Date: 30 September 2016
    Abstract

  • Abstract

    Ant colony algorithm (ACO) is a metaheuristic search method, which can solve efficiently NP-complete problems such as the famous traveling salesman problem (TSP). To alleviate, to some extent, ACO’s drawback of getting stuck in a local optimum, a TSP algorithm based on clustering ensemble ACO and restricted solution space is proposed in this paper. The main idea is as follows: Firstly, a triangle algorithm is presented to generate initial TSPs, which are used to construct the primitive transfer probability matrix so that the randomness of trip of ants is reduced; Secondly, to avoid premature convergence, the k-means clustering method is employed repeatedly to produce co-association matrix (CM), which can be viewed as a perturbation factor and improve the selection of the next city for each ant, namely, city pairs with high values in CM are connected closely, or vice versa; Finally, a restricted solution space, namely, the restricted connections, is reconsidered to improve the solutions produced by ACO. The experiments on 9 benchmarks from TSPLIB demonstrate that the proposed method outperforms some of the state-of-art TSP algorithms.

    Abstract

    Ant colony algorithm (ACO) is a metaheuristic search method, which can solve efficiently NP-complete problems such as the famous traveling salesman problem (TSP). To alleviate, to some extent, ACO’s drawback of getting stuck in a local optimum, a TSP algorithm based on clustering ensemble ACO and restricted solution space is proposed in this paper. The main idea is as follows: Firstly, a triangle algorithm is presented to generate initial TSPs, which are used to construct the primitive transfer probability matrix so that the randomness of trip of ants is reduced; Secondly, to avoid premature convergence, the k-means clustering method is employed repeatedly to produce co-association matrix (CM), which can be viewed as a perturbation factor and improve the selection of the next city for each ant, namely, city pairs with high values in CM are connected closely, or vice versa; Finally, a restricted solution space, namely, the restricted connections, is reconsidered to improve the solutions produced by ACO. The experiments on 9 benchmarks from TSPLIB demonstrate that the proposed method outperforms some of the state-of-art TSP algorithms.
    • FullText(HTML)
  • loading
    • References(23)
  • [1]
    WIKIPEDIA. Travelling salesman problem[EB/OL]. http://en.wikipedia.org/wiki/Travelling salesman problem.
    [2]
    GREFENSTETTE J J, GOPAL R, ROSMAITA B J, et al. Genetic algorithms for the traveling salesman problem[C]// Proceedings of the First International Conference on Genetic Algorithms and their Applications. Pottsburg: IEEE Press, 1985: 160-168.
    [3]
    MEER K. Simulated annealing versus metropolis for a TSP instance [J]. Information Processing Letters, 2007, 104(6): 216-219.
    [4]
    DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man and Cybernetics, Part B, 1996, 26 (1): 29-41.
    [5]
    DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem [J]. Bio Systems, 1997, 43(2):73-81.
    [6]
    STTZLE T, HOOS H H. Max-min ant System and local search for the traveling salesman problem [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway: IEEE Press, 1997: 309-314.
    [7]
    DORIGO M, BIRATTARI M, STTZLE T. Ant colony optimization: Artificial ants as a computational intelligence technique [J].IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.
    [8]
    WU J Q, OUYANG A J. A hybrid algorithm of ACO and delete-cross method for TSP [C] //Proceedings of the International Conference on Industrial Control and Electronics Engineering. Xi’an: IEEE Press, 2012: 1694-1696.
    [9]
    HELSGAUN K. General k-opt submoves for the Lin-Kernighan TSP heuristic [J]. Mathematical Programming Computation, 2009, 1(2): 119-163.
    [10]
    CHEN S M, CHIEN C Y. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques [J]. Expert Systems with Applications, 2011, 38(12): 14439-14450.
    [11]
    HUANG L, ZHOU C G, WANG K P. Hybrid ant colony algorithm for traveling salesman problem [J]. Progress in Natural Science, 2003, 13(4): 295-299.
    [12]
    MAHI M, BAYKAN  K, KODAZ H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-Opt algorithms for traveling salesman problem [J]. Applied Soft Computing, 2015, 30(C): 484-490.
    [13]
    WIKIPEDIA. Ant colony optimization algorithms[EB/OL]. https://en.wikipedia.org/wiki/Ant colony optimization algorithms.
    [14]
    DORIGO M, GAMBARDELLA L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
    [15]
    百度百科.蚁群算法[EB/OL]. [2016-12-01]http://baike.baidu.com/link?url=nFMlbOVYTN1MEYrYUalwPCSx8pUreohumXgbIxmReFXX0rkyEdgnuyzOBK3xcazcfUiKQzHby7wrcaC-mOqCZa.
    [16]
    WIKIPEDIA. Hamiltonian path[EB/OL]. [2016-12-01]https://en.wikipedia.org/wiki/Hamiltonian_path.
    [17]
    FENG H M, LIAO K L. Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problems [J]. Information Sciences, 2014, 270: 204-225.
    [18]
    http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/
    [19]
    ZHONG C M, YUE X D, ZHANG Z H, et al. A clustering ensemble: Two-level-refined co-association matrix with path-based transformation [J]. Pattern Recognition, 2015, 48(8): 2699-2709.
    [20]
    KENNEDY J, EBERHART R. Particle swarm optimization [C]// Proceedings of International Conference on Neural Networks. Perth, Australia: IEEE Press, 1995, 4: 1942-1948.
    [21]
    数据堂.TSP数据集[EB/OL]. [2016-12-01]http://www.datatang.com/data/39337.
    [22]
    GNDZ M, KIRAN M S, ZCEYLAN E. A hierarchic approach based on swarm intelligence to solve traveling salesman problem [J]. Turkish Journal of Electrical Engineering Computer Science, 2015, 23(1): 103-107.
    [23]
    KAN J M, ZHANG Y. Application of an improved ant colony optimization on generalized traveling salesman problem [J]. Energy Procedia, Part A, 2012, 17(2): 319-325.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    WIKIPEDIA. Travelling salesman problem[EB/OL]. http://en.wikipedia.org/wiki/Travelling salesman problem.
    [2]
    GREFENSTETTE J J, GOPAL R, ROSMAITA B J, et al. Genetic algorithms for the traveling salesman problem[C]// Proceedings of the First International Conference on Genetic Algorithms and their Applications. Pottsburg: IEEE Press, 1985: 160-168.
    [3]
    MEER K. Simulated annealing versus metropolis for a TSP instance [J]. Information Processing Letters, 2007, 104(6): 216-219.
    [4]
    DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man and Cybernetics, Part B, 1996, 26 (1): 29-41.
    [5]
    DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem [J]. Bio Systems, 1997, 43(2):73-81.
    [6]
    STTZLE T, HOOS H H. Max-min ant System and local search for the traveling salesman problem [C]// Proceedings of the IEEE International Conference on Evolutionary Computation. Piscataway: IEEE Press, 1997: 309-314.
    [7]
    DORIGO M, BIRATTARI M, STTZLE T. Ant colony optimization: Artificial ants as a computational intelligence technique [J].IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.
    [8]
    WU J Q, OUYANG A J. A hybrid algorithm of ACO and delete-cross method for TSP [C] //Proceedings of the International Conference on Industrial Control and Electronics Engineering. Xi’an: IEEE Press, 2012: 1694-1696.
    [9]
    HELSGAUN K. General k-opt submoves for the Lin-Kernighan TSP heuristic [J]. Mathematical Programming Computation, 2009, 1(2): 119-163.
    [10]
    CHEN S M, CHIEN C Y. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques [J]. Expert Systems with Applications, 2011, 38(12): 14439-14450.
    [11]
    HUANG L, ZHOU C G, WANG K P. Hybrid ant colony algorithm for traveling salesman problem [J]. Progress in Natural Science, 2003, 13(4): 295-299.
    [12]
    MAHI M, BAYKAN  K, KODAZ H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-Opt algorithms for traveling salesman problem [J]. Applied Soft Computing, 2015, 30(C): 484-490.
    [13]
    WIKIPEDIA. Ant colony optimization algorithms[EB/OL]. https://en.wikipedia.org/wiki/Ant colony optimization algorithms.
    [14]
    DORIGO M, GAMBARDELLA L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
    [15]
    百度百科.蚁群算法[EB/OL]. [2016-12-01]http://baike.baidu.com/link?url=nFMlbOVYTN1MEYrYUalwPCSx8pUreohumXgbIxmReFXX0rkyEdgnuyzOBK3xcazcfUiKQzHby7wrcaC-mOqCZa.
    [16]
    WIKIPEDIA. Hamiltonian path[EB/OL]. [2016-12-01]https://en.wikipedia.org/wiki/Hamiltonian_path.
    [17]
    FENG H M, LIAO K L. Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problems [J]. Information Sciences, 2014, 270: 204-225.
    [18]
    http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/
    [19]
    ZHONG C M, YUE X D, ZHANG Z H, et al. A clustering ensemble: Two-level-refined co-association matrix with path-based transformation [J]. Pattern Recognition, 2015, 48(8): 2699-2709.
    [20]
    KENNEDY J, EBERHART R. Particle swarm optimization [C]// Proceedings of International Conference on Neural Networks. Perth, Australia: IEEE Press, 1995, 4: 1942-1948.
    [21]
    数据堂.TSP数据集[EB/OL]. [2016-12-01]http://www.datatang.com/data/39337.
    [22]
    GNDZ M, KIRAN M S, ZCEYLAN E. A hierarchic approach based on swarm intelligence to solve traveling salesman problem [J]. Turkish Journal of Electrical Engineering Computer Science, 2015, 23(1): 103-107.
    [23]
    KAN J M, ZHANG Y. Application of an improved ant colony optimization on generalized traveling salesman problem [J]. Energy Procedia, Part A, 2012, 17(2): 319-325.
    Recommended articles
    TrendMD
    Volume 46 Issue 9 page: 780-787
    Cover

    Article Metrics

    Article views (20) PDF downloads(76)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return