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

A hybrid evolutionary algorithm for multiobjective travelling salesman problem

作　　者：王娜 刘生[2] 王洪峰 

机构地区：[1]沈阳师范大学计算机与数学基础教学部,沈阳110034 [2]东北大学信息科学与工程学院,沈阳110819

出　　处：《沈阳师范大学学报（自然科学版）》2017年第4期425-429,共5页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(71671032)

摘　　要：许多科学与工程优化问题往往需要转化为多目标旅行商问题进行求解,由于目标函数之间的冲突性,使得这类问题不存在能够优化所有目标函数的唯一最优解,而是存在一个Pareto最优解集或者Pareto Front。为了获得一个高质量的Pareto最优解集,提出了一种基于蚁群优化和差分进化的混合多目标进化算法。在提出的算法中,一方面采纳分解机制利用蚁群优化算子实现对Pareto最优解的开发,另一方面采纳拥挤度概念利用差分进化算子实现对Pareto Front的探索。通过对一组标准测试算例的仿真实验,结果表明所提出的算法比现有的算法能够获得分布性和收敛性更优的Pareto解集。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.

关 键 词：旅行商问题 进化多目标优化 蚁群优化 差分进化 

分 类 号：O229[理学—运筹学与控制论]