基于双种群的 Pareto 局部搜索算法

来源：计算机技术与发展杂志2018年第11期北京时间：

作者：汪欣;夏超

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

关键词：多目标组合优化;Pareto 局部搜索;双种群;分解框架;多目标旅行商问题