解决多目标旅行商问题的改进NSGA-Ⅱ算法

Improved NSGA-Ⅱ Method for Multi-objective Travelling Salesman Problem

多目标旅行商问题是经典TSP问题的扩展和延伸,具有很强的实际研究意义。在多目标进化算法NSGA-Ⅱ的基础上设计了一种双目标进化算法以求解该问题,其中,在非劣解排序的基础上混合了局部搜索策略2opt以提高局部寻优能力,并采用了动态变化的变异算子体现出自适应的思想。用MATLAB编程实现该算法并对几个标准双目标TSP算例进行仿真测试。实验结果表明,提出的算法比NSGA-Ⅱ具有更好的优化性能。

Multi-objective traveling salesman problem is a classical expansion and extension of the TSP problem,having a strong practical research significance.This paper designs a multi-objective evolutionary algorithm based on the NSGA-II to solve this problem,it used the method of non-dominated sorting and the local search 2opt to improve the efficiency of searching,and the mutation operator is dynamic changed to reflect the thought of adaptation.It is implemented by MATLAB and simulation on a kind of benchmark functions.