Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (5): 1278-1283.DOI: 10.11772/j.issn.1001-9081.2019112019

• Artificial intelligence • Previous Articles     Next Articles

Multi-scale quantum free particle optimization algorithm for solving travelling salesman problem

YANG Yunting1,2, WANG Peng3   

  1. 1.Chengdu Institute of Computer Application, Chinese Academy of Sciences, ChengduSichuan 610041, China
    2.University of Chinese Academy of Sciences, Beijing 100049, China
    3.School of Computer Science and Technology, Southwest Minzu University, ChengduSichuan 610041, China
  • Received:2019-11-28 Revised:2019-12-24 Online:2020-05-10 Published:2020-05-15
  • Contact: WANG Peng, born in 1975, Ph. D., professor. His research interests include intelligent optimization algorithm, cloud computing.
  • About author:YANG Yunting, born in 1994, M. S. candidate. Her research interests include intelligent optimization algorithm, cloud computing.WANG Peng, born in 1975, Ph. D., professor. His research interests include intelligent optimization algorithm, cloud computing.
  • Supported by:

    This work is partially supported by the National Natural Science Foundation of China (60702075).


杨云亭1,2, 王鹏3   

  1. 1.中国科学院 成都计算机应用研究所,成都 610041
    2.中国科学院大学,北京 100049
    3.西南民族大学 计算机科学与技术学院,成都 610225
  • 通讯作者: 王鹏(1975—)
  • 作者简介:杨云亭(1994—),女,河北定州人,硕士研究生,主要研究方向:智能优化算法、云计算; 王鹏(1975—),男,四川乐山人,教授,博士,CCF会员,主要研究方向:智能优化算法、云计算。
  • 基金资助:



Aiming at the problem of slowness of the current meta-heuristic algorithms when solving Travelling Salesman Problem (TSP) in combinatorial optimization problems, a multi-scale adaptive quantum free particle optimization algorithm was proposed based on the inspiration of the wave function in quantum theory. Firstly, the particles representing the city sequences were randomly initialized in the feasible region as the initial search centers. Then, the new solution was obtained by taking each particle as the center to perform the sampling with uniformly distributed function and exchanging the city numbers in the sampling positions. Finally, according to the comparison result of the new solution with the optimal solution in the previous iteration, the search scale was adaptively adjusted, and the iterative search was carried out at different scales until the end condition of the algorithm was satisfied.The algorithm was compared with Hybrid Particle Swarm Optimization (HPSO) algorithm, Simulated Annealing (SA), Genetic Algorithm (GA) and Ant Colony Optimization(ACO) algorithm on TSP. The experimental results show that the multi-scale quantum free particle optimization algorithm is suitable for solving combinatorial optimization problems, and increases the solving speed by over 50% on average compared with the current better algorithms on the TSP datasets.

Key words: free particle, dynamic search, optimization algorithm, combinatorial optimization, Travelling Salesman Problem (TSP), wave function



关键词: 自由粒子, 动态搜索, 优化算法, 组合优化, 旅行商问题, 波函数

CLC Number: