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

An improved differential evolution algorithm for TSP

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.