求解TSP问题的离散型差分进化算法  

A Discrete Differential Evolution Algorithm for TSP Problem

作　　者：宁桂英[1] 曹敦虔 周永权 

机构地区：[1]广西科技大学鹿山学院,柳州545616 [2]广西民族大学理学院,南宁530006 [3]广西民族大学信息科学与工程学院,南宁530006

出　　处：《计算机与数字工程》2017年第11期2136-2142,共7页Computer & Digital Engineering

基　　金：国家自然科学基金项目(编号:61463007);2015年度广西高校科学技术研究项目(编号:KY2015YB521);2015年度广西教育厅科学研究项目(编号:KY2015YB081)资助

摘　　要：针对旅行商(TSP)问题,提出了一种离散型差分进化算法,在该算法中,一方面,采用一种新的编码方法,把仅用于求解连续域上优化问题的差分进化算法推广到能用于求解离散TSP问题;另一方面,引入了2-OPT算子,将全局搜索与局部搜索有机地结合,通过对经典的TSP问题实例进行了测试,仿真结果表明,论文提出的算法具有较强的稳定性,是求解TSP问题的一种有效的方法。A discrete differential evolution algorithm is proposed for solving traveling salesman problem（TSP）in this article.In the algorithm,on the one hand,the differential evolution algorithm with a new coding method is used to solve a discrete TSP,which is often used to solve problems on a continuous domain. On the other hand,the 2-OPT algorithm is also introduced;the newalgorithm combined the global search with the local search effectively. The classical TSP has been tested,the simulation resultsshow that the proposed algorithm has strong stability and it is an effective method for solving TSP.

关 键 词：差分进化 旅行商 启发式算法 适应度 2-OPT 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]