Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (12): 2797-2808.DOI: 10.3778/j.issn.1673-9418.2104006

• Artificial Intelligence • Previous Articles     Next Articles

Dual Ant Colony Algorithm Based on Backtracking Migration and Matching Learning

CHEN Da1, YOU Xiaoming1,+(), LIU Sheng2   

  1. 1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620,;China
    2. School of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Received:2021-04-01 Revised:2021-06-07 Online:2022-12-01 Published:2021-06-15
  • About author:CHEN Da, born in 1997, M.S. candidate. His research interests include intelligent algorithm, path planning of mobile robot and embedded system.
    YOU Xiaoming, born in 1963, Ph.D., professor, M.S. supervisor. Her research interests include swarm intelligent systems, distributed parallel processing and evolutionary computing.
    LIU Sheng, born in 1966, Ph.D., professor, M.S. supervisor. His research interests include quantum inspired evolutionary computation, distributed parallel processing and evolutionary computing.
  • Supported by:
    National Natural Science Foundation of China(61673258);National Natural Science Foundation of China(61075115)


陈达1, 游晓明1,+(), 刘升2   

  1. 1.上海工程技术大学 电子电气工程学院,上海 201620
    2.上海工程技术大学 管理学院,上海 201620
  • 通讯作者: +E-mail:
  • 作者简介:陈达(1997—),男,江苏盐城人,硕士研究生,主要研究方向为智能算法、移动机器人路径规划、嵌入式系统。
  • 基金资助:


In order to solve the problems of slow convergence speed and easy to fall into local optimum of tradi-tional ant colony algorithm in solving traveling salesman problem (TSP), the dual ant colony algorithm based on backtracking migration and matching learning (BMACS) is proposed. Firstly, the population is dynamically graded into exploration ants and tracking ants. The ants with higher fitness are exploration ants and the ones with lower fitness are tracking ants. Secondly, a local feature transfer mechanism is proposed, in which there are two strategies: in the feature transfer strategy, the pheromone on the common path of exploration ants is rewarded, and this path is transferred into the pheromone matrix as a local feature, so as to improve the influence of exploration ants and acce-lerate the convergence speed of the algorithm; in the mutation learning strategy, the tracking ants are responsible for exploring the suboptimal path, and adaptively reconstruct the path of exploration ants to enrich the diversity of the population. Finally, when the algorithm stagnates, the matching learning mechanism is used to communicate and learn between the current optimal individual and the historical optimal individual with the highest similarity, and the pheromone is reorganized to increase the diversity of the population, thus improving the ability of the algorithm to jump out of the local optimal. Simulation experiments are carried out with MATLAB for multiple sets of cases in TSPLIB, and the results show that the improved algorithm balances diversity and convergence speed, and effecti-vely improves the quality of solution.

Key words: ant colony algorithm, traveling salesman problem (TSP), local feature migration, matching learning, dyna-mic classification



关键词: 蚁群算法, 旅行商问题(TSP), 局部特征迁移, 匹配学习, 动态分级

CLC Number: