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

Solving traveling salesman problem based on monkey algorithm

作　　者：徐小平[1] 张东洁[1] 

机构地区：[1]西安理工大学理学院,西安710054

出　　处：《计算机工程与应用》2018年第2期144-148,共5页Computer Engineering and Applications

基　　金：陕西省自然科学基础研究计划项目(No.2014JM8325);陕西省教育厅专项科研计划项目(No.14JK1538);西安理工大学科技创新计划项目(No.2016CX013)

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]