旅行商问题的改进差分进化方法  

An improved differential evolution algorithm for TSP

作　　者：梅觅[1] 薛惠锋[1] 谷雨[1] 

机构地区：[1]西北工业大学自动化学院,西安710072

出　　处：《信息技术》2011年第2期20-23,共4页Information Technology

基　　金：国家自然科学基金资助项目(10702065);陕西省自然科学基金项目(2005F45)

摘　　要：TSP(Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题,目前大多采用遗传算法求解。差分进化算法(Differential Evolution Algorithm,DE)作为一种新型的进化算法,与遗传算法有很多相似之处。提出用改进的差分进化算法解决TSP问题。采用基于整数序规范的辅助算子解决变异问题,并引入刘海交叉算子。实验结果表明该方法有效地提高了算法的收敛速度与寻优质量,表现出了良好的特性。TSP（Traveling Salesman Problem） is a kind of typical NP problems,and currently is solved by genetic algorithm（GA） generally.As a new kind of evolution algorithm,differential evolution algorithm（DE） shares many common performances with GA.In order to solve TSP more conveniently,an improved differential evolution algorithm was proposed.The new method added an auxiliary operator for regulating integer sequence in the mutation process and used Liuhai crossover operator to replace the original crossover operator.Through several experiments,it could be concluded that this method can significantly improve the speed of convergence and the quality of optimal results,features well characteristic in TSP.

关 键 词：差分进化算法 旅行商问题 遗传算法 

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