Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (2): 144-148.DOI: 10.3778/j.issn.1002-8331.1608-0072

Previous Articles     Next Articles

Solving traveling salesman problem based on monkey algorithm

XU Xiaoping, ZHANG Dongjie   

  1. School of Sciences, Xi’an University of Technology, Xi’an 710054, China
  • Online:2018-01-15 Published:2018-01-31

基于猴群算法求解旅行商问题

徐小平,张东洁   

  1. 西安理工大学 理学院,西安 710054

Abstract: In view of Traveling Salesman Problem(TSP) is a NP hard problem, Monkey Algorithm(MA) is a new swarm intelligent optimization algorithm. Therefore, in this paper, it uses MA to solve TSP. Firstly, after the characteristics of TSP are analyzed, the method of integer encoding is adopted to set the position of monkeys, which overcomes climbing process failure problem when optimization problem with discrete variable is solved using MA. Then, TSP can be effectively solved using MA. Next, in order to improve the performance of MA, it proposes an improved algorithm that an active strategy is introduced in the climbing process of MA, and it is applied to solve TSP. Finally, in the simulation experiment, compared with the existing methods, the results show that the proposed algorithm can be used to effectively solve TSP.

Key words: Traveling Salesman Problem(TSP), optimization, integer encoding, Monkey Algorithm(MA), climb process, active strategy

摘要: 鉴于旅行商问题是一个NP难问题,而猴群算法是一种新的群体智能优化算法,因此,利用猴群算法给出旅行商问题的求解。在分析了旅行商问题的特点后,采用整数编码的方式来表示猴群的位置,这样就解决了猴群算法在求解含有离散变量的组合优化问题时,算法中的爬过程失效的问题,有效地利用猴群算法求解旅行商问题。为了提高猴群算法的性能,在猴群算法的爬过程中,引入好动策略,给出改进算法,并将其应用到求解旅行商问题。在仿真实验中,与其他算法进行比较,结果表明利用改进猴群算法能够有效地求解旅行商问题。

关键词: 旅行商问题, 优化, 整数编码, 猴群算法, 爬过程, 好动策略