一种求解多目标旅行商问题的混合进化算法

摘要

Many scientific and engineering problems can always transfer to multiobjective travelling salesman problems (TSPs),where there is only a set of Pareto optimal solution or Pareto front,rather than one single optimal solution that can optimize all objective functions simultaneously,due to the existence of multiple conflicting objectives.In this paper,a hybrid multiobjective evolutionary algorithm,which hybridizes the mechanism of ant colony optimization (ACO) and differential evolution (DE),is proposed for solving multiobjective TSP.Two different strategies are employed in the proposed algorithm,that is,ACO operators are used to make an exploration for a set of Pareto optimal solutions based on a decomposition mechanism and DE operators are used to makean exploitation to obtain a better Pareto front.Based on the experiments on a series of test instances,the proposed algorithmshows a Pareto solution set with better distribution and convergence than those from several state-of-the-art algorithms.%许多科学与工程优化问题往往需要转化为多目标旅行商问题进行求解,由于目标函数之间的冲突性,使得这类问题不存在能够优化所有目标函数的唯一最优解,而是存在一个Pareto最优解集或者Pareto Front.为了获得一个高质量的Pareto最优解集,提出了一种基于蚁群优化和差分进化的混合多目标进化算法.在提出的算法中,一方面采纳分解机制利用蚁群优化算子实现对Pareto最优解的开发,另一方面采纳拥挤度概念利用差分进化算子实现对ParetoFront的探索.通过对一组标准测试算例的仿真实验,结果表明所提出的算法比现有的算法能够获得分布性和收敛性更优的Pareto解集.