陈科胜,鲜思东,郭 鹏

(重庆邮电大学复杂系统智能分析与决策重点实验室,重庆 400065)

1 引言

旅行商问题(traveling salesman problem,TSP)是一个非确定性多项式难度的优化问题,其问题可以描述为给定一系列城市坐标集,一个旅行者从起点城市出发,如何经过各个城市一次并回到出发点的路径规划问题.其问题的解可以被描述为各个城市出现一次且仅出现一次构成的排列方案,该排列方案代表着旅行者将第一个城市作为出发点,依次按排列顺序对城市进行仿问,最后再回到第一个城市的路径规划方案.TSP问题的最优解就是旅行者所经历过的最短路径.

TSP问题可以简单地描述为已知n个城市以及各个城市相互之间的距离,求出某一旅行商经过所有城市并回到出发点的最短路线.设d(Vi,Vj)为Vi到Vj的距离,问题可以抽象为已知一点集V{Vi,1 ≤i≤n},寻找一个排列X{V1,……,Vn}来最小化

多年来研究人员不断地探究该问题,文献[1]梳理了许多针对TSP问题的算法方案.总体上可以将算法分为两个类别:一类是在已有成熟的启发式算法中,结合TSP问题的特点对算法机制进行改良,使得算法具有更强的寻优能力;一类是借助仿生学等思想提出新的启发式算法.

其中，在改良现有启发式算法的方面,文献[2]中提出了离散型萤火虫群优化算法(discrete glowworm swarmoptimization algorithm,DGSO),文献[3]中提出的自适应离散粒子群算法(self-adaptive discrete particle swarm optimization algorithm,SADPSO)及文献[4]中提出的具有变异特征的蚁群算法(ant colony algorithm with mutation features,ACO)、文献[5]基于已有的非支配排序遗传算法–II(non-dominated sorting genetic algorithm–II,NSGA–II),利用平均距离将种群划分为若干个