基于双种群的 Pareto 局部搜索算法-《计算机技术与发展》

文章信息/Info

Author(s):: WANG Xin; XIA Chao; School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211100,China

Keywords:: multi-and many-objective combinatorial optimization; Pareto local search; dual population; decomposition based framework; multi-objective traveling salesman problem

摘要:: 多目标组合优化问题是工程实际和现实生活中常见的问题,随着目标数目的增多,其求解的难度也越发增加,现有的多目标组合优化算法大多只能解决两至三个目标问题,对于超过三个目标的超多目标组合优化问题却没有好的解决方案。在基于分解的框架和 Pareto 局部搜索算法的基础上,提出了一种基于双种群的 Pareto 局部搜索算法用于解决超多目标组合优化问题。算法在进化过程中维持两个种群,分别为工作集和外部集。工作集利用分解的思想将多目标优化问题分解成单目标问题进行解决以加速收敛过程,工作集则进行 Pareto 局部搜索来产生更为高效的解以保证搜索效率。为验证算法的有效性,基于多目标旅行商问题的多个目标和多个实例进行仿真实验。通过与现有算法的比较可知,算法在超多目标的组合优化问题上有着非常好的效果。

Abstract:: Multi-objective combinatorial optimization problem is common in engineering practice and real life. Difficulty for solving it increases with the increasing number of objectives. Most of the existing multi-objective combinatorial optimization algorithms can only solve two or three objective problems,and there is no better solution to the many-objective combinatorial optimization problem with more than three objectives. Therefore,we propose a dual population based Pareto local search algorithm based on the decomposition framework. The algorithm maintains two populations,i. e. working and external archives,during evolution. Working archive decomposes the multi-objective optimization problem into a number of single-objective problems to speed up convergence process by using the idea of decomposition,while the external archive generates more efficient solutions by using Pareto local search to ensure the search efficiency.To verify the effectiveness of the algorithm,a simulation experiment is carried out based on multi-and many-objectives instances of multiobjective traveling salesman problem,which validates the effectiveness and efficiency of proposed algorithm over the existing algorithmson many-objective combinatorial optimization problems.