一种求解旅行商问题的进化多目标优化方法

An evolutionary multiobjective optimization method for traveling salesman problems

为了克服传统小生境(Niching)策略中的参数设置难题,提出一种求解旅行商问题的进化多目标优化方法:建立以路径长度和平均离群距离为目标的双目标优化模型,利用改进非支配排序遗传算法(NSGAII)进行求解.为了在全局探索能力与局部开发能力之间保持平衡,算法中采用一种使路径长度相同的可行解互不占优的评价策略,并通过一种新的离散差分进化算子和简化的2-Opt策略生成候选解.与已有算法的数值试验结果比较表明,求解旅行商问题(TSP)的改进非支配排序遗传算法(NSGAII-TSP)能够更好地保持种群多样性,从而克服局部最优解的吸引并具有更鲁棒的全局探索能力.通过借助特殊的个体评价策略,所提出的算法可以更好地进行全局优化,甚至同时得到多个全局最优解.

An evolutionary multi-objective optimization method is proposed for the traveling salesman problem(TSP) to overcome the parameter-setting trouble in traditional niching strategies, where we develop an optimization model minimizing the tour length as well as the averaged mutual distance, and solve it to get the global optimal solutions of TSPs via the nondominated sorting genetic algorithm II(NSGAII). To strike a balance between global exploration and local exploitation, it incorporates an evaluation strategy that makes different solutions of the same length nondominated,and generates new candidate solutions via a novel discrete differential evolution strategy as well as a simplified 2-Opt strategy. Numerical comparisons with existing algorithms demonstrate that the NSGAII for TSP(NSGAII-TSP) can better keep the population diversity, be kept away from the absorption of local optima, and consequently has robust global exploration ability. With assistance of the special strategy making different solutions of the same length nondominated, the proposed algorithm can perform global optimization better, and locate several global optimal solutions at a time.