第16卷第4期 智能系统学报 Vol.16 No.4 2021年7月 CAAI Transactions on Intelligent Systems Jul.2021 D0:10.11992/tis.202010026 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20210407.1558.007html 融合分区和局部搜索的多模态多目标优化 胡洁，范勤勤2，王直欢 (1.上海海事大学物流研究中心，上海201306,2.上海交通大学系统控制与信息处理教有部重点实验室，上海 200240) 摘要：为解决多模态多目标优化中种群多样性维持难和所得等价解数量不足问题，基于分区搜索和局部搜 索，本研究提出一种融合分区和局部搜索的多模态多目标粒子群算法(multimodal multi-.objective particle swarm optimization combing zoning search and local search,ZLS-SMPSO-MM)。在所提算法中，整个搜索空间被分割成多 个子空间以维持种群多样性和降低搜索难度：然后，使用已有的自组织多模态多目标粒子群算法在每个子空间 搜索等价解和挖掘邻域信息，并利用局部搜索能力较强的协方差矩阵自适应算法对有潜力的区域进行精细搜 索。通过14个多模态多目标优化问题测试，并与其他5种知名算法进行比较；实验结果表明ZLS-SMPSO MM在决策空间能够找到更多的等价解，且整体性能要好于所比较算法。 关键词：多模态多目标优化；分区搜索；局部搜索：协方差矩阵自适应策略；种群多样性：等价解：多模态多目标 粒子群算法 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2021)04-0774-1】 中文引用格式：胡洁，范勤勤，王直欢.融合分区和局部搜索的多模态多目标优化.智能系统学报，2021,16(4)：774-784. 英文引用格式：HU Jie,.FAN Qingin,.WANG Zhihuan..Multimodal multi-.objective optimization combining zoning and local search[JI.CAAI transactions on intelligent systems,2021,16(4):774-784. Multimodal multi-objective optimization combining zoning and local search HU Jie',FAN Qinqin2,WANG Zhihuan' (1.Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China;2.Key Laboratory of System Control and In- formation Processing,Ministry of Education of China,Shanghai JiaoTong University,Shanghai 200240,China) Abstract:To maintain population diversity and find a sufficient number of equivalent solutions in multimodal multi-ob- jective optimization,a multimodal multi-objective particle swarm optimization algorithm with zoning and local searches (ZLS-SMPSO-MM)is proposed in this study.In the proposed algorithm,which is based on zoning search and local search,the entire search space is divided into several subspaces to maintain population diversity and reduce search diffi- culty.Subsequently,an existing self-organizing multimodal multi-objective particle swarm algorithm is used to search equivalent solutions and mine neighborhood information in each subspace,and the covariance matrix adaptation al- gorithm,which has a better local search ability,is utilized for a refined search in promising regions.Lastly,the perform- ance of ZLS-SMPSO-MM is tested on 14 multimodal multi-objective optimization problems and compared with that of other five state-of-the-art algorithms.Experimental results show that the proposed algorithm can find more equivalent solutions in the decision space and its overall performance is better than that of the compared algorithms. Keywords:multimodal multi-objective optimization;zoning search;local search;covariance matrix adaptation evolu- tionary strategy;population diversity;equivalent solutions;multimodal multi-objective particle swarm optimization 收稿日期：2020-10-23.网络出版日期：202104-07. 基金项目：国家重点研发计划项目(20I6YFC0800200):国家自 现实生活中的问题往往会涉及多个优化目 然科学基金项目(61603244)：中国博士后科学基金 项目(2018M642017). 标，且它们可能彼此冲突、相互制约，这类问题被 通信作者：范勤勤.E-mail:foreverl23fan@l63.com 称为多目标优化问题(multi--objective optimization
DOI: 10.11992/tis.202010026 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20210407.1558.007.html 融合分区和局部搜索的多模态多目标优化 胡洁1 ，范勤勤1,2，王直欢1 （1. 上海海事大学 物流研究中心，上海 201306; 2. 上海交通大学 系统控制与信息处理教育部重点实验室，上海 200240） 摘 要：为解决多模态多目标优化中种群多样性维持难和所得等价解数量不足问题，基于分区搜索和局部搜 索，本研究提出一种融合分区和局部搜索的多模态多目标粒子群算法 (multimodal multi-objective particle swarm optimization combing zoning search and local search，ZLS-SMPSO-MM)。在所提算法中，整个搜索空间被分割成多 个子空间以维持种群多样性和降低搜索难度；然后，使用已有的自组织多模态多目标粒子群算法在每个子空间 搜索等价解和挖掘邻域信息，并利用局部搜索能力较强的协方差矩阵自适应算法对有潜力的区域进行精细搜 索。通过 14 个多模态多目标优化问题测试，并与其他 5 种知名算法进行比较；实验结果表明 ZLS-SMPSOMM 在决策空间能够找到更多的等价解，且整体性能要好于所比较算法。 关键词：多模态多目标优化；分区搜索；局部搜索；协方差矩阵自适应策略；种群多样性；等价解；多模态多目标 粒子群算法 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2021)04−0774−11 中文引用格式：胡洁, 范勤勤, 王直欢. 融合分区和局部搜索的多模态多目标优化 [J]. 智能系统学报, 2021, 16(4): 774–784. 英文引用格式：HU Jie, FAN Qinqin, WANG Zhihuan. Multimodal multi-objective optimization combining zoning and local search[J]. CAAI transactions on intelligent systems, 2021, 16(4): 774–784. Multimodal multi-objective optimization combining zoning and local search HU Jie1 ，FAN Qinqin1,2 ，WANG Zhihuan1 (1. Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China; 2. Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai JiaoTong University, Shanghai 200240, China) Abstract: To maintain population diversity and find a sufficient number of equivalent solutions in multimodal multi-objective optimization, a multimodal multi-objective particle swarm optimization algorithm with zoning and local searches (ZLS-SMPSO-MM) is proposed in this study. In the proposed algorithm, which is based on zoning search and local search, the entire search space is divided into several subspaces to maintain population diversity and reduce search difficulty. Subsequently, an existing self-organizing multimodal multi-objective particle swarm algorithm is used to search equivalent solutions and mine neighborhood information in each subspace, and the covariance matrix adaptation algorithm, which has a better local search ability, is utilized for a refined search in promising regions. Lastly, the performance of ZLS-SMPSO-MM is tested on 14 multimodal multi-objective optimization problems and compared with that of other five state-of-the-art algorithms. Experimental results show that the proposed algorithm can find more equivalent solutions in the decision space and its overall performance is better than that of the compared algorithms. Keywords: multimodal multi-objective optimization; zoning search; local search; covariance matrix adaptation evolutionary strategy; population diversity; equivalent solutions; multimodal multi-objective particle swarm optimization 现实生活中的问题往往会涉及多个优化目 标，且它们可能彼此冲突、相互制约，这类问题被 称为多目标优化问题 (multi-objective optimization 收稿日期：2020−10−23. 网络出版日期：2021−04−07. 基金项目：国家重点研发计划项目 (2016YFC0800200)；国家自 然科学基金项目 (61603244)；中国博士后科学基金 项目 (2018M642017). 通信作者：范勤勤. E-mail：forever123fan@163.com. 第 16 卷第 4 期 智 能 系 统 学 报 Vol.16 No.4 2021 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2021
第4期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·775· problem,MOP)0。而多模态多目标优化问题(mul- ang等提出一种多模态多目标差分进化优化算 timodal multi-objective optimization problem. (multimodal multi-objective differential evolution MMOP)是其中一类较特殊的问题。相比于传统 optimization algorithm,MMODE)。该算法使用预 的多目标优化问题，它在决策空间的多个解可能 选择机制将所有个体进行适应度值排序后再根据 会有相同的目标值。故多模态多目标优化问题不 决策空间中的拥挤距离选择个体进行变异，同时 仅要找到多样性好和逼近性好的近似帕累托前 引入新的边界处理方法将停留在边界的个体重新 沿(pareto front,PF),而且要在决策空间找到尽可 调整。实验结果证明利用MMODE算法获得的 能多的等价解回。 Pareto解在决策空间和目标空间中都有一个较好 由于多模态多目标问题在近几年才受到学者 的表现；Liu等1提出一种基于归档和重组策略 们的重视和研究，故相比于多目标优化算法的研 的多模态多目标算法(multimodal multi-objective 究，其成果相对较少。基于L)提出的无参数小 evolutionary algorithm using two-archive and recom- 生境算法，Yue等在此基础上提出基于环形拓 bination strategies,.TriMOEA-TA&R)。该算法使用 扑结构的粒子群算法(multi-objective particle 决策变量分析技术将种群个体分别归入多样性存 swarm optimizer using ring-topology, 档和收敛性存档中，各自从两个存档中选择父代 MO Ring PSO SCD)来解决多模态多目标问题， 进行交叉复制。此外，多样性存档中使用聚类算 该算法除引入基于索引的环形拓扑结构外，还在 法及清除策略来保证目标空间多样性。最终将两 决策空间和目标空间中设计一种新的特殊的拥挤 个存档的解重组以形成最终解集。实验结果证 距离来进行粒子选择与更新。结果表明，该算法 明，两个存档的分工减少了环境选择的难度，且 能定位和保持大量的等价解；Liang等提出一种 算法的整体性能明显优于比较算法；Lin等)提 自组织多模态多目标粒子群算法(self-organizing 出一种决策空间和目标空间双重聚类的多模态多 multi-objective particle swarm optimization al- 目标进化算法(multimodal multi-objective evolu- gorithm,SMPSO-MM)。该算法使用自组织映射网 tionary algorithm with dual clustering in decision and 络构建粒子间的邻域关系并进行邻域间信息交 objective spaces,MMOEA/DC)。该算法在决策空 流；另外引入精英策略避免算法陷入停滞。实验 间和目标空间均采用聚类算法来保持两个空间的 结果表明该算法能够定位到更多等价解，决策空 多样性。在决策空间根据邻域关系将父代与子代 间解的分布也较均匀；Li等向提出一种基于适应 结合并划分为多个类别，将这些类中获得的非支 度排序与强化学习的多模态多目标算法(differen- 配解及其他收敛性好的解对应在目标空间中的解 tial evolution based on reinforcement learning with fit- 重新划分为多个类。实验结果表明该算法能够有 ness ranking,DE-RLFR),该算法首先使用适应度 效定位到全局Pareto解和局部Pareto解，并且在 函数联合排序值确定种群中每个个体的分层状 两个空间中都有较好的多样性。Zhang等提出 态，再根据分层状态确定进化方向和变异策略， 一种改进的粒子群算法(modified particle swarm 最后利用强化学习来引导种群搜索。实验证明该 optimization,MPSO)求解多模态多目标问题。该 算法可以显著提高决策空间中种群搜索效率，在 算法引入一种基于邻域的动态学习策略代替全局 解决多模态多目标问题时有较好表现；Fan等 学习策略，并使用子代竞争机制来提高算法的多 仞则使用分区的概念来提高种群在决策空间中的 样性。实验结果证明该算法在多数测试函数上的 多样性和降低问题的求解复杂度。研究表明，该 表现都优于其他比较算法。Li等)提出一种基 方法能够辅助MO-Ring-SO-SCD找到更多等价 于高斯采样(multi objective particle swarm optimiza-. 解。Zhang等提出一种基于聚类的多模态多目 tion based on gaussian sampling,.GS-MOPSO)的多 标粒子群算法(cluster based PSO with leader updat- 目标粒子群优化算法以求解多模态多目标问题。 ing mechanism and ring-topology,MMO-CLR- 该算法在搜索前期利用全局高斯采样方法来进行 PSO)。该算法使用决策变量聚类方法划分子种 全局搜索，在搜索后期则采用局部高斯采样来寻 群，利用带有领导粒子更新机制的全局粒子群算 找有潜力解的邻域。此外，GS-MOPSO算法采用 法独立地更新每一个子种群的粒子，并在子种群 一种新的外部存档策略来储存历史解。实验结果 之间建立环形结构探索未被开发的区域以搜索更 表明，该算法能够找到更多Pareto解。 多的非支配解。实验结果证明该算法在决策空间 虽然诸多学者对多模态多目标进化算法进行 与目标空间的解集都能维持较好的多样性：L 改进，但如何保持/提高种群多样性和提高局部搜
problem, MOP)[1]。而多模态多目标优化问题 (multimodal multi-objective optimization problem, MMOP) 是其中一类较特殊的问题。相比于传统 的多目标优化问题，它在决策空间的多个解可能 会有相同的目标值。故多模态多目标优化问题不 仅要找到多样性好和逼近性好的近似帕累托前 沿 (pareto front, PF)，而且要在决策空间找到尽可 能多的等价解[2]。 由于多模态多目标问题在近几年才受到学者 们的重视和研究，故相比于多目标优化算法的研 究，其成果相对较少。基于 Li[3] 提出的无参数小 生境算法，Yue 等 [4] 在此基础上提出基于环形拓 扑结构的粒子群算法 (multi-objective particle swarm optimizer using ring-topology ， MO_Ring_PSO_SCD) 来解决多模态多目标问题， 该算法除引入基于索引的环形拓扑结构外，还在 决策空间和目标空间中设计一种新的特殊的拥挤 距离来进行粒子选择与更新。结果表明，该算法 能定位和保持大量的等价解；Liang 等 [5] 提出一种 自组织多模态多目标粒子群算法 (self-organizing multi-objective particle swarm optimization algorithm，SMPSO-MM)。该算法使用自组织映射网 络构建粒子间的邻域关系并进行邻域间信息交 流；另外引入精英策略避免算法陷入停滞。实验 结果表明该算法能够定位到更多等价解，决策空 间解的分布也较均匀；Li 等 [6] 提出一种基于适应 度排序与强化学习的多模态多目标算法 (differential evolution based on reinforcement learning with fitness ranking，DE-RLFR)，该算法首先使用适应度 函数联合排序值确定种群中每个个体的分层状 态，再根据分层状态确定进化方向和变异策略， 最后利用强化学习来引导种群搜索。实验证明该 算法可以显著提高决策空间中种群搜索效率，在 解决多模态多目标问题时有较好表现； Fan 等 [7] 则使用分区的概念来提高种群在决策空间中的 多样性和降低问题的求解复杂度。研究表明，该 方法能够辅助 MO-Ring-SO-SCD 找到更多等价 解。Zhang 等 [8] 提出一种基于聚类的多模态多目 标粒子群算法 (cluster based PSO with leader updating mechanism and ring-topology，MMO-CLRPSO)。该算法使用决策变量聚类方法划分子种 群，利用带有领导粒子更新机制的全局粒子群算 法独立地更新每一个子种群的粒子，并在子种群 之间建立环形结构探索未被开发的区域以搜索更 多的非支配解。实验结果证明该算法在决策空间 与目标空间的解集都能维持较好的多样性；Liang 等 [9] 提出一种多模态多目标差分进化优化算 法 (multimodal multi-objective differential evolution optimization algorithm，MMODE)。该算法使用预 选择机制将所有个体进行适应度值排序后再根据 决策空间中的拥挤距离选择个体进行变异，同时 引入新的边界处理方法将停留在边界的个体重新 调整。实验结果证明利用 MMODE算法获得的 Pareto 解在决策空间和目标空间中都有一个较好 的表现；Liu 等 [10] 提出一种基于归档和重组策略 的多模态多目标算法 (multimodal multi-objective evolutionary algorithm using two-archive and recombination strategies，TriMOEA-TA&R)。该算法使用 决策变量分析技术将种群个体分别归入多样性存 档和收敛性存档中，各自从两个存档中选择父代 进行交叉复制。此外，多样性存档中使用聚类算 法及清除策略来保证目标空间多样性。最终将两 个存档的解重组以形成最终解集。实验结果证 明，两个存档的分工减少了环境选择的难度，且 算法的整体性能明显优于比较算法；Lin 等 [11] 提 出一种决策空间和目标空间双重聚类的多模态多 目标进化算法 (multimodal multi-objective evolutionary algorithm with dual clustering in decision and objective spaces，MMOEA/DC)。该算法在决策空 间和目标空间均采用聚类算法来保持两个空间的 多样性。在决策空间根据邻域关系将父代与子代 结合并划分为多个类别，将这些类中获得的非支 配解及其他收敛性好的解对应在目标空间中的解 重新划分为多个类。实验结果表明该算法能够有 效定位到全局 Pareto 解和局部 Pareto 解，并且在 两个空间中都有较好的多样性。Zhang 等 [12] 提出 一种改进的粒子群算法 (modified particle swarm optimization, MPSO) 求解多模态多目标问题。该 算法引入一种基于邻域的动态学习策略代替全局 学习策略，并使用子代竞争机制来提高算法的多 样性。实验结果证明该算法在多数测试函数上的 表现都优于其他比较算法。Li 等 [13] 提出一种基 于高斯采样 (multi objective particle swarm optimization based on gaussian sampling, GS-MOPSO) 的多 目标粒子群优化算法以求解多模态多目标问题。 该算法在搜索前期利用全局高斯采样方法来进行 全局搜索，在搜索后期则采用局部高斯采样来寻 找有潜力解的邻域。此外，GS-MOPSO 算法采用 一种新的外部存档策略来储存历史解。实验结果 表明，该算法能够找到更多 Pareto 解。 虽然诸多学者对多模态多目标进化算法进行 改进，但如何保持/提高种群多样性和提高局部搜 第 4 期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·775·
·776· 智能系统学报 第16卷 索能力来找到更多等价解仍需得到进一步研究。 HV这两种评价指标来评价多模态多目标优化 为提高多模态多目标进化算法的性能，本文提出 算法的性能。 一种融合分区和局部搜索的多模态多目标粒子群 1)PSP (multimodal multi-objective particle swarm op- PSP=IG CR (2) timization combining zoning search and local search, ZLS-SMPSO-MM)。在ZLS-SMPSO-MM算法中， ∑ah,Psy 整个决策空间首先被划分成多个子空间；然后在 IGDx(PS",PS)= (3) PSI 各个子空间内，自组织映射网络被用来构建各个 1/2D 子空间的邻域，并使用协方差矩阵自适应算法 (4) (covariance matrix adaptation evolutionary strategies, CMA-ES)来增强算法的局部搜索能力：最后对所 1, B“=B 有子空间得到的解集进行合并选择。为验证所提 0 b≥BIb≤B (5) 算法性能，本文选取5种知名多模态多目标进化 min(b,Bm)-max(bmi,B) 其他 算法和14个多模态多目标问题进行比较与测 Baax-Bmnin 试。所得实验结果表明，ZLS-SMPSO-MM不仅能 式中：CR(cover rate)表示所得解集中解个数与真 够维持种群多样性以找到更多的等价解，而且能 实PS中解个数的比值，也称为解的覆盖率；IG- 够在较短时间内找到高质量的解。 Dx表示决策空间中的反向世代距离；b和 b是算法获得的解集PS中第j个变量的最大值 1预备知识 和最小值；Bx和B是PS中第j个变量的最大 值和最小值；d(b,PS)是b与PS中最近点的欧几 1.1多目标优化问题 里得距离；PS表示PS中解的数量。PSP主要评 不失一般性，多目标优化问题（以最小化问题 为例)的数学形式表示如下3： 价得到的解集PS与PS之间的相似性。PSP的值 越大，表示算法得到的等价解越多，算法的性能 min y=F(x)=(fi(x),f(x),...,fa(x)) s.t.r=(d,x,…,xD)∈XRD (1) 就越好。 式中：x为D维的决策矢量；X为D维的决策空 2)HV 间；y=(y1,y2,…ym)∈YSRm为m维的目标矢量； HVPS)=VoLU.[f(r,r]×[Uf(x),r]×…× Y为m维的目标空间。其他一些相关概念如下阿 [f(x).r])=[(fi(x)-ri)(fi(x)-ri)]+[(f(x)- 定理1支配关系：向量p支配另一个向量 r)f(x)-r)门…+[fm(x)-rn)fm(x)-r)门 q(记作pF(x),就称x为Pareto解，所有Pareto解构 P℉的收敛性和多样性。HV的值越大，代表算法 成的集合（记作X被称为Pareto解集。 获得的PF逼近越接近真实P℉，多样性也越好。 定理3 Pareto前沿：在多目标优化问题中， 2融合分区和局部搜索的多模态多 Pareto解集对应目标空间中的目标向量被称为 目标粒子群算法 Pareto前沿，表示为PF={F(x)r'∈X*。 1.2多模态多目标优化问题及评价指标 2.1分区搜索 多模态多目标优化问题是一种特殊的多目标 对于求解多模态多目标优化问题来说，提高/ 优化问题，其主要表现为两种情况：1)决策空间 维持种群多样性是影响其最后结果的一个重要因 中每个解都有多个等价解：2)决策空间中部分解 素。同时，降低问题求解复杂度也能辅助算法找 有多个等价解刀。由于多模态多目标优化问题不 到质量更好的解。鉴于文献[7]中所提方法能够 仅需要在目标空间获得逼近性及多样性较好的 实现以上两个目标，故所提算法使用分区搜索 P℉逼近，也需要在决策空间中获得足够多等价 (zoning search,ZS)来求解多模态多目标优化问 解。因此，本文引入帕累托解集近似(pareto set 题。搜索空间分割步骤：首先从决策空间X的 proximity,PSP)I和超体积值(hypervolume, D维优化问题中随机选取h(1≤h≤D)个变量，将
索能力来找到更多等价解仍需得到进一步研究。 为提高多模态多目标进化算法的性能，本文提出 一种融合分区和局部搜索的多模态多目标粒子群 算法 (multimodal multi-objective particle swarm optimization combining zoning search and local search, ZLS-SMPSO-MM)。在 ZLS-SMPSO-MM 算法中， 整个决策空间首先被划分成多个子空间；然后在 各个子空间内，自组织映射网络被用来构建各个 子空间的邻域，并使用协方差矩阵自适应算法 (covariance matrix adaptation evolutionary strategies, CMA-ES) 来增强算法的局部搜索能力；最后对所 有子空间得到的解集进行合并选择。为验证所提 算法性能，本文选取 5 种知名多模态多目标进化 算法和 14 个多模态多目标问题进行比较与测 试。所得实验结果表明，ZLS-SMPSO-MM 不仅能 够维持种群多样性以找到更多的等价解，而且能 够在较短时间内找到高质量的解。 1 预备知识 1.1 多目标优化问题 不失一般性，多目标优化问题 (以最小化问题 为例) 的数学形式表示如下[13-14] : min y=F(x) = (f1(x), f2(x),··· , fm(x)) s.t. x = (x1, x2,··· , xD) ∈ X ⊆ R D (1) x y = (y1, y2,··· ym) ∈ Y ⊆ R m 式中： 为 D 维的决策矢量；X 为 D 维的决策空 间 ； 为 m 维的目标矢量； Y 为 m 维的目标空间。其他一些相关概念如下[15] ： p ≺ q ∀θ ∈ {1,2,··· ,φ}, pθ ⩽ qθ p , q 定理 1 支配关系：向量 p 支配另一个向量 q ( 记 作 ) 的条件是：如果 ，并且 。 x ∗ ∈ X x ∈ X F (x) ≻ F (x ∗ ) x ∗ X ∗ 定理 2 Pareto 最优解集 (pareto set，PS)：一个 向 量 ，若不存在其他向量 ，使得 ，就称 为 Pareto 解，所有 Pareto 解构 成的集合 (记作 ) 被称为 Pareto 解集。 PF = {F (x ∗ )|x ∗ ∈ X∗} 定理 3 Pareto 前沿：在多目标优化问题中， Pareto 解集对应目标空间中的目标向量被称为 Pareto 前沿，表示为 。 1.2 多模态多目标优化问题及评价指标 多模态多目标优化问题是一种特殊的多目标 优化问题，其主要表现为两种情况：1) 决策空间 中每个解都有多个等价解；2) 决策空间中部分解 有多个等价解[7]。由于多模态多目标优化问题不 仅需要在目标空间获得逼近性及多样性较好的 PF 逼近，也需要在决策空间中获得足够多等价 解。因此，本文引入帕累托解集近似 (pareto set proximity， PSP)[ 4 ] 和超体积值 (hypervolume， HV)[16] 这两种评价指标来评价多模态多目标优化 算法的性能。 1)PSP PSP = CR IGDx (2) IGDx(PS∗ ,PS) = ∑ b∈PS d(b,PS∗ ) |PS| (3) CR = ∏D j δj 1/2D (4) δj = 1, B max j = B min j 0, b min j ⩾ B max j ||b max j ⩽ B min j min(b max j ,B min j )−max(b min j ,B max j ) B max j − B min j , 其他 (5) b max j b min j B max j B min j 式中：CR (cover rate) 表示所得解集中解个数与真 实 PS 中解个数的比值，也称为解的覆盖率；IGDx 表示决策空间中的反向世代距离[14] ； 和 是算法获得的解集 PS*中第 j 个变量的最大值 和最小值； 和 是 PS 中第 j 个变量的最大 值和最小值；d(b, PS* ) 是 b 与 PS 中最近点的欧几 里得距离；|PS|表示 PS 中解的数量。PSP 主要评 价得到的解集 PS*与 PS 之间的相似性。PSP 的值 越大，表示算法得到的等价解越多，算法的性能 就越好。 2)HV HV(PS∗ ) = VOL( ∪ x∈PS ∗ [ f1(x),r ∗ 1 ] × [ f2(x),r ∗ 2 ] × ···× [ fm(x),r ∗ m ] ) = [(f1(x)− r ∗ 1 )(f1(x)− r ∗ 1 ) T ]+[(f2(x)− r ∗ 2 )(f2(x)− r ∗ 2 ) T ]···+[(fm(x)− r ∗ m )(fm(x)− r ∗ m ) T ] (6) r ∗ = ( r ∗ 1 ,r ∗ 2 ,··· ,r ∗ m ) 式中：VOL() 是勒贝格测度； 是选 择的参考点，该参考点被目标空间中所有获得的 PF 逼近中的个体所支配。HV 可以用来衡量 PF*的收敛性和多样性。HV 的值越大，代表算法 获得的 PF 逼近越接近真实 PF，多样性也越好。 2 融合分区和局部搜索的多模态多 目标粒子群算法 2.1 分区搜索 对于求解多模态多目标优化问题来说，提高/ 维持种群多样性是影响其最后结果的一个重要因 素。同时，降低问题求解复杂度也能辅助算法找 到质量更好的解。鉴于文献 [7] 中所提方法能够 实现以上两个目标，故所提算法使用分区搜索 (zoning search，ZS) 来求解多模态多目标优化问 题。搜索空间分割步骤：首先从决策空间 X 的 D 维优化问题中随机选取 h(1≤h≤D) 个变量，将 ·776· 智 能 系 统 学 报 第 16 卷
第4期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·777· 每个变量都分割成>1)段，最终，整个决策空间 元及每个获胜神经元的邻域神经元，将获胜神经 被分为·个子空间。 元及其邻域神经元对应的粒子组成引导粒子的备 2.2自组织多模态多目标粒子群算法 选库，并采用非支配排序法选择排序在第一位的 在所提算法中，选取自组织多模态多目标粒 粒子作为当前的引导粒子。 子群算法(self-organizing multi--objective particle 3)粒子速度和位置更新。 swarm optimization algorithm for multimodal multi- vl=wxy+cir(xpbes-x)+ (12) objective problems,.SMOPSO)为基本的搜索算法， C2r2(Xabes-x) 其主要步骤如下： x8+=x+y,8+ (13) l)构建自组织映射网络(self-organizing maps, 式中：p=(W,2,vo)表示粒子速度；w为惯性权 SOM)。该步骤主要利用SOM网络为粒子群算法 重；1和r2是在(0,1)区间正态分布间的随机数； 中的粒子构建邻域关系，并在根据邻域关系获得 c1和c2是两个加速因子；xp是个体历史最优； 的神经元集合中选取合适的引导粒子指导种群进 nbest是个体邻域最优。 化。SOM网络构建邻域关系主要有以下几步11 4)粒子速度和位置超出临界值修正。在进行 粒子速度和位置更新时，若粒子速度超出临界 ①判断获胜神经元。 值，则将其设置为临界值；若粒子位置超出临界 SOM网络中输入的数据维度为D,将种群的 值，则将粒子位置设置为临界值并将该点粒子的 位置信息x=(x1,2,…xD)输入网络，隐藏层中的 速度设置为当前速度的相反数。 每个神经元与输入层是全连接的结构，所以神经 5)当g≥G时，算法停止。否则回到1)。 元的权值矩阵的行秩与输入空间的维度相同，神 2.3协方差矩阵自适应策略搜索 经元权值矩阵的列秩则与神经元个数相同。因 协方差矩阵自适应策略(covariance matrix ad- 此，整个隐藏层的权值矩阵表示为 aptation evolutionary strategies,CMA-ES)主要步骤 [w11w12·w1D 如下： W21W22·w2D W= (7) 1)对种群内所有粒子进行采样。采样即利用 正态分布得到粒子的A个新搜索点作为进入下一 其中ε代表SOM网络中神经元个数。 代进化的候选解，其采样公式为 (14) 竞争过程就是找到与输入向量x最佳匹配的 x*1=e+σN(0,C)为 权值向量，等价于找到与向量x欧几里得距离最 e-wxt. (15) 小的权值向量，该权值向量所对应的神经元也被 1】 称之为获胜神经元。其主要公式为 (16) d(x,w)=(x-w)'(x-w) (8) 之%，=1，w1≥w2≥w3≥…≥w1>0, 式中：p∈(1，)；p代表获胜神经元编号；w= 式中：1>≥221；k代表第g+1代中第k个个体； [Wol Wel…wol'。 e∈R"是已被挑选入第g代种群的所有个体的加 用索引I(u)来标识与输入向量x最佳匹配的 权平均位置；o~∈R*是第g代种群进化的步长； 权值向量，其公式为 C∈Rw是第g代种群进化的协方差矩阵； I(up)=argminx-w N(0,C)是均值为0，协方差矩阵为C的多元正态 (9) 分布；W:是采样后产生的个体的权值。 ②获取邻域神经元信息并更新权值。 采样完成后，重新计算e1并设置每个个体 根据竞争过程产生的获胜神经元的索引确定 的权值，使质量更好的个体有更大概率进行下一 获胜神经元在隐藏层中的位置，并根据邻域半径 步操作。 确定其邻域神经元。根据已获得的获胜神经元的 2)协方差矩阵更新。使用秩-μ更新模式来计 信息更新邻域神经元的权值信息，权值更新为 算连续进化代之间的变异步长，并调整协方差矩 w=w+n(x-w5) (10) 阵。协方差矩阵的更新分为两个部分，第1部分 =rx-是G) (11) 是对进化路径进行更新，公式为 式中：g为当前代数；G为最大迭代代数；)为学习率。 Pg*1=h.Vc.(2-c)4n(e8+1-e)/o8+(1-ce)P(17) 2)获得合适的引导粒子。根据1)中构建的 1,c≥0 SOM网络，记录种群内每个粒子对应的获胜神经 h(c)=0. c<0 (18)
每个变量都分割成 l(l>1) 段，最终，整个决策空间 被分为 l h 个子空间。 2.2 自组织多模态多目标粒子群算法 在所提算法中，选取自组织多模态多目标粒 子群算法[5] (self-organizing multi-objective particle swarm optimization algorithm for multimodal multiobjective problems，SMOPSO) 为基本的搜索算法， 其主要步骤如下： 1) 构建自组织映射网络 (self-organizing maps， SOM)。该步骤主要利用 SOM 网络为粒子群算法 中的粒子构建邻域关系，并在根据邻域关系获得 的神经元集合中选取合适的引导粒子指导种群进 化。SOM 网络构建邻域关系主要有以下几步[5,17-18] ： ①判断获胜神经元。 D x = (x1, x2,··· xD) SOM 网络中输入的数据维度为 ，将种群的 位置信息 输入网络，隐藏层中的 每个神经元与输入层是全连接的结构，所以神经 元的权值矩阵的行秩与输入空间的维度相同，神 经元权值矩阵的列秩则与神经元个数相同。因 此，整个隐藏层的权值矩阵表示为 w = w11 w12 ··· w1D w21 w22 ··· w2D . . . . . . . . . wε1 wε2 ··· wεD (7) 其中ε 代表 SOM 网络中神经元个数。 竞争过程就是找到与输入向量 x 最佳匹配的 权值向量，等价于找到与向量 x 欧几里得距离最 小的权值向量，该权值向量所对应的神经元也被 称之为获胜神经元。其主要公式为 d 2 (x,wuρ ) = (x−wuρ ) T (x−wuρ ) (8) ρ ∈ (1,ε) uρ wuρ = [ wρ1 wρ1 ··· wρD ]T 式中： ； 代表获胜神经元编号； 。 用索引 I(uρ) 来标识与输入向量 x 最佳匹配的 权值向量，其公式为 I(uρ) = argmin x−wuρ (9) ②获取邻域神经元信息并更新权值。 根据竞争过程产生的获胜神经元的索引确定 获胜神经元在隐藏层中的位置，并根据邻域半径 确定其邻域神经元。根据已获得的获胜神经元的 信息更新邻域神经元的权值信息，权值更新为 w g+1 = w g +η g (x−w g ) (10) η g+1 = η g × ( 1− g 1−G ) (11) 式中：g 为当前代数；G 为最大迭代代数； η 为学习率。 2) 获得合适的引导粒子。根据 1) 中构建的 SOM 网络，记录种群内每个粒子对应的获胜神经 元及每个获胜神经元的邻域神经元，将获胜神经 元及其邻域神经元对应的粒子组成引导粒子的备 选库，并采用非支配排序法选择排序在第一位的 粒子作为当前的引导粒子。 3) 粒子速度和位置更新。 vi g+1 = w ′ ×vi g +c1r1(xpbest − xi g )+ c2r2(xnbest − xi g ) (12) xi g+1 = xi g +vi g+1 (13) v = (v1, v2,··· vD) w ′ xpbest xnbest 式中： 表示粒子速度； 为惯性权 重；r1 和 r2 是在 (0，1) 区间正态分布间的随机数； c1 和 c2 是两个加速因子； 是个体历史最优； 是个体邻域最优。 4) 粒子速度和位置超出临界值修正。在进行 粒子速度和位置更新时，若粒子速度超出临界 值，则将其设置为临界值；若粒子位置超出临界 值，则将粒子位置设置为临界值并将该点粒子的 速度设置为当前速度的相反数。 5) 当 g≥G 时，算法停止。否则回到 1)。 2.3 协方差矩阵自适应策略搜索 协方差矩阵自适应策略 (covariance matrix adaptation evolutionary strategies，CMA-ES) 主要步骤 如下[19] ： λ 1) 对种群内所有粒子进行采样。采样即利用 正态分布得到粒子的 个新搜索点作为进入下一 代进化的候选解，其采样公式为 xk g+1 = e g +σ gN(0,C g ), (14) e g = ∑λ 1⩽i⩽λ wixi g , (15) ∑λ i=1 wi = 1,w1 ⩾ w2 ⩾ w3 ⩾ ··· ⩾ wλ > 0, (16) λ ⩾ 2 e g ∈ R n σ g ∈ R + C g ∈ R D×D N (0,C g ) C g wi 式中： [ 2 0 ] ； k 代表第 g+1 代中第 k 个个体； 是已被挑选入第 g 代种群的所有个体的加 权平均位置； 是第 g 代种群进化的步长； 是 第 g 代种群进化的协方差矩阵； 是均值为 0，协方差矩阵为 的多元正态 分布； 是采样后产生的个体的权值。 e 采样完成后，重新计算 g+1 并设置每个个体 的权值，使质量更好的个体有更大概率进行下一 步操作。 2) 协方差矩阵更新。使用秩-µ 更新模式来计 算连续进化代之间的变异步长，并调整协方差矩 阵。协方差矩阵的更新分为两个部分，第 1 部分 是对进化路径进行更新，公式为 P g+1 c = hσ √ cc(2−cc)µw(e g+1 −e g )/σg+(1−cc)P g c (17) hσ(c) = { 1, c ⩾ 0 0, c < 0 (18) 第 4 期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·777·
·778· 智能系统学报 第16卷 (19) 均使用基于特殊拥挤距离的非支配排序法进行 排序，排在第一位的粒子取代原本参与局部搜索 的粒子进入粒子群，其余非支配解均加入外部存 式中：h。为Heaviside函数；ce为权值系数；uw为 档。当外部存档内的非支配解个数大于外部存档 方差有效选择质量。第2部分是对协方差矩阵 容量Q时，继续使用基于特殊拥挤距离的非支配 进行更新，公式为 排序法进行排序，将前Q个解保留。若外部存档 C1=(1-C,)C+c,P*'(Pl) (20) 内非支配解个数小于Q则全部保留。 其中c,是协方差矩阵的学习率。 6)循环3)5)，直到A,≥A1时跳出循环。 3)全局步长控制。全局步长控制进化路径更 7)将每个子空间内最后一代粒子群与子空间 新与2)的进化路径相似，公式为 外部存档合并，使用基于特殊拥挤距离的非支配 P=Co(2-Co)uer(est!-es)/+(1-co)P) (21) 排序法选出每个子空间的非支配解。将4个子空 式中：c。为进化路径的学习率；4m为方差有效选 间的解集合并后使用环境选择得到最终解集 择质量，计算方式与4一致0。 PS=selection(PS,*UPS,UPS,'UPS,)和近似帕累 全局步长更新公式为 托前沿PF=selection(PF,'UPF2UPF;UPF,)。 = (22) 3实验结果与分析 其中d.是接近阻尼1的系数。 3.1测试函数 4)停止准则。当算法消耗评价次数大于 为验证ZLS-SMPSO-MM的性能，本文选取 CMA-ES算法最大评价次数时，算法停止。否则， 14个多模态多目标优化问题对其进行测试。其 回到2) 中，8个MMF问题I、3个SYM-PART问题2 2.4融合分区和局部搜索的多模态多目标进化 3个OMNI问题四，详情见表1。所有优化问题的 算法 目标个数均为2，MMF问题与SYM-PART问题的 基于2.12.3节，融合分区和局部搜索的多模 空间维度为2，OMNI问题的空间维度分别为3、 态多目标算法的具体实现步骤如下： 4、5。PSs的数量表示决策空间中的不同PS对应 输入种群规模NP;算法最大评价次数A; 目标空间同一个PF的数量，PSs的数量越大，问 分区数量m:粒子群参数w、、2、C、c2;子空间外 题的求解难度也会相应增大。最后一列表示的是 部存档容量Q:CMA-ES算法参数c,、c、c。、局部 P$s在决策空间的每一维度是否重叠，一般情况 搜索步长σ、单个个体进行CMA-ES搜索消耗的 下，PSs在决策空间的重叠会增加问题的复杂度。 最大评价次数A1;单个个体进行CMA-ES搜索消 表1多模态多目标优化问题的相关特征 耗的累计评价次数A2:CMA-ES算法加入时消耗 Table 1 Features of multimodal multi-objective optimiza- 的算法总评价次数A;算法累计评价次数A4。 tion problems 输出PS和PF。 问题 目标个数空间维度PSs的数量是否重叠 1)初始化种群x=(x,,…xp),子空间外部存 MMF 2 否 档Q,A1=12,A2=0,A=0,A=0;CMA-ES算法其他 MMF2 2 凉 参数与文献[19]保持一致。 MMF3 2 2 2 是 2)根据2.1节对决策空间进行分割，得到4个 MMF4 3 ￥ 否 子空间。 MMF 3 否 3)在各个子空间中使用2.2节的多模态多目 MMFs 2 2 是 标进化算法进行搜索。 MMF7 2 否 4)当A=0时，分别对各个子空间中得到的非 MMFs 2 2 4 否 支配解使用2.3节的局部搜索算法。当单个粒子 SYM-I 2 9 是 消耗的累计评价次数大于A1时，该粒子的局部搜 SYM-II 2 9 索过程结束。下一粒子继续进行局部搜索。直 SYM-III 2 9 是 到NP个粒子完成局部搜索，或者A,≥A时局部搜 OMNI-TEST 2 3 27 是 索结束。 OMNI-TEST2 2 4 72 曾 5)每个参与局部搜索的粒子与其产生的子代 OMNI-TEST: 2 J 360 是
µw = 1 ∑λ i wi 2 (19) 式中： hσ 为 Heaviside 函数；cc 为权值系数； µw 为 方差有效选择质量[20]。第 2 部分是对协方差矩阵 进行更新，公式为 C g+1 = (1−cγ)C g +cγP g+1 c (P g+1 c ) T (20) 其中cγ 是协方差矩阵的学习率。 3) 全局步长控制。全局步长控制进化路径更 新与 2) 的进化路径相似，公式为 P g+1 σ = √ cσ(2−cσ)µeff(e g+1 −e g )/σg+(1−cσ)P (g) σ (21) cσ µeff µw 式中： 为进化路径的学习率； 为方差有效选 择质量，计算方式与 一致[20]。 全局步长更新公式为 σ g+1 = (σ g ) 1 dσ ∥pσ g+1 ∥ E∥N(0,I)∥ −1 (22) 其中 dσ 是接近阻尼 1 的系数。 4 ) 停止准则。当算法消耗评价次数大 于 CMA-ES 算法最大评价次数时，算法停止。否则， 回到 2)。 2.4 融合分区和局部搜索的多模态多目标进化 算法 基于 2.1~2.3 节，融合分区和局部搜索的多模 态多目标算法的具体实现步骤如下： cγ cc cσ σ 输入 种群规模 NP；算法最大评价次数 A； 分区数量 zn；粒子群参数 w、r1、r2、c1、c2；子空间外 部存档容量 Q；CMA-ES 算法参数 、 、 、局部 搜索步长 、单个个体进行 CMA-ES 搜索消耗的 最大评价次数 A1；单个个体进行 CMA-ES 搜索消 耗的累计评价次数 A2；CMA-ES 算法加入时消耗 的算法总评价次数 A3；算法累计评价次数 A4。 输出 PS*和 PF*。 1) 初始化种群 x = (x1, x2,··· xNP) ，子空间外部存 档 Q，A1=12，A2=0，A3=0，A4=0；CMA-ES 算法其他 参数与文献 [19] 保持一致。 2) 根据 2.1 节对决策空间进行分割，得到 4 个 子空间。 3) 在各个子空间中使用 2.2 节的多模态多目 标进化算法进行搜索。 4) 当 A3=0 时，分别对各个子空间中得到的非 支配解使用 2.3 节的局部搜索算法。当单个粒子 消耗的累计评价次数大于 A1 时，该粒子的局部搜 索过程结束。下一粒子继续进行局部搜索。直 到 NP 个粒子完成局部搜索，或者 A4≥A 时局部搜 索结束。 5) 每个参与局部搜索的粒子与其产生的子代 均使用基于特殊拥挤距离的非支配排序法[4] 进行 排序，排在第一位的粒子取代原本参与局部搜索 的粒子进入粒子群，其余非支配解均加入外部存 档。当外部存档内的非支配解个数大于外部存档 容量 Q 时，继续使用基于特殊拥挤距离的非支配 排序法进行排序，将前 Q 个解保留。若外部存档 内非支配解个数小于 Q，则全部保留。 6) 循环 3)~5)，直到 A4≥A1 时跳出循环。 PS∗ = selection(PS1 ∗ ∪PS2 ∗ ∪PS3 ∗ ∪PS4 ∗ ) PF∗ = selection(PF1 ∗ ∪PF2 ∗ ∪PF3 ∗ ∪PF4 ∗ ) 7) 将每个子空间内最后一代粒子群与子空间 外部存档合并，使用基于特殊拥挤距离的非支配 排序法选出每个子空间的非支配解。将 4 个子空 间的解集合并后使用环境选择得到最终解集 和近似帕累 托前沿 。 3 实验结果与分析 3.1 测试函数 为验证 ZLS-SMPSO-MM 的性能，本文选取 14 个多模态多目标优化问题对其进行测试。其 中，8 个 MMF 问题[4] 、3 个 SYM-PART 问题[21] 、 3 个 OMNI 问题[22] ，详情见表 1。所有优化问题的 目标个数均为 2，MMF 问题与 SYM-PART 问题的 空间维度为 2，OMNI 问题的空间维度分别为 3、 4、5。PSs 的数量表示决策空间中的不同 PS 对应 目标空间同一个 PF 的数量，PSs 的数量越大，问 题的求解难度也会相应增大。最后一列表示的是 PSs 在决策空间的每一维度是否重叠，一般情况 下，PSs 在决策空间的重叠会增加问题的复杂度。 表 1 多模态多目标优化问题的相关特征 Table 1 Features of multimodal multi-objective optimization problems 问题 目标个数 空间维度 PSs的数量 是否重叠 MMF1 2 2 2 否 MMF2 2 2 2 否 MMF3 2 2 2 是 MMF4 2 2 4 否 MMF5 2 2 4 否 MMF6 2 2 4 是 MMF7 2 2 2 否 MMF8 2 2 4 否 SYM-I 2 2 9 是 SYM-II 2 2 9 是 SYM-III 2 2 9 是 OMNI-TEST1 2 3 27 是 OMNI-TEST2 2 4 72 是 OMNI-TEST3 2 5 360 是 ·778· 智 能 系 统 学 报 第 16 卷
第4期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·779· 3.2 实验设置 coxon得到的统计分析结果也在表2中显示。从 为验证ZLS-SMPSO-MM的性能，本文选取 表2可以看出，所提算法在14个测试函数上所得 5种多模态多目标进化算法来进行比较。其分别 结果都要显著好于DN-NSGA-II、Omni-optimizer、 是DN-NSGA-r、Omni-optimizer2a、MO-Ring- MO-Ring-PSO-SCD、ZS-MO-Ring-SCD-PSO。相比 psO-sCD、SMPSO-MM、Zoning-MO-Ring-SCD- 于SMPSO-MM,除在MMF,函数上取得相似的结 PSO。同时，所有比较算法的参数设置与原文献 果，ZLS-SMPSO-MM在其他测试函数上都能得到 一致。本实验中所有测试函数均为2目标问题， 更好的结果。同时，这6种算法得到的PSP值排 所有测试函数的种群数量均设置为800，最大评 序结果如下表3，在该表中，利用Friedman非参数 检验方法对实验结果进行统计分析时，将所有算 价次数为80000，单个粒子使用CMA-ES算法的 法得到的测试函数的PSP值均取为其相反数，故 评价次数设置为12。外部存档容量设置为800。 排序值越小，算法性能越佳。根据表3结果可得， 每种算法在测试函数上均独立运行20次。为保 ZLS-SMPSO-MM在所有比较算法中性能最佳。 证实验结果分析的可靠性，采用Wilcoxon21和 这是因为使用多模态多目标进化算法进行搜索前 Friedman非参数检验方法对实验结果进行统计 先使用分区策略划分了决策空间。在各个互不重 分析，显著性水平设置为5%。其中“+”、“-”分别 叠的子空间区域使用相同规模的粒子群分别进行 表示所提算法优于、劣于相比较算法；“≈”表示所 空间搜索，提升种群多样性的同时也降低了各个 提算法与相比较的算法性能相近。 子空间的搜索难度：每个子空间内都引入局部搜 3.3结果对比 索算法，在每次全局搜索后的潜力区域用局部搜 ZLS-SMPSO-MM与其他5种比较算法所得 索能力强的CMA-ES算法进行精细搜索，因此能 PSP值的平均值和标准方差见表2。同时，由W- 够找到更多高质量的解。 表2不同算法得到的PSP平均值与标准方差 Table 2 PSP average and standard deviation values obtained by different algorithms 测试函数ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO 1.1264×10 4.2091×10 4.8032×10 6.7124×10 8.6367×10 9.2158×10 MMF (6.52) (4.12)+ (4.94+ (3.45+ (4.27)+ (5.40+ 1.9043×102 6.9429×10 7.0615×10 1.0835×102 1.5201×102 1.3487×10 MMF2 (1.45×105 (2.30×10+ (3.63×10+ (1.12×10+ (1.05×10+ (1.61×10+ 1.8482×10 7.4018×10 7.6312×10 1.3604×10 1.8638×10 1.3081×102 MMF3 (2.18×10 (3.53×10)+ (1.89×10)H (1.97×10)+ (1.80×10)≈ (1.64×10+ 2.4566×101 4.3684×10 3.7380×10 1.1580×10 1.3739×10 1.9306×102 MMF4 (1.11) (8.32)+ (7.87)+ (4.06)+ (5.93+ (5.81+ 4.9755×101 1.4495×10 1.4948×10 3.3537×10 4.0297×10 4.3840×10 MMFs (2.61) (1.64+ (1.31+ (1.10+ (1.51+ (2.42)+ 6.3460×10 1.7753×10 1.7389×10 3.6583×10 4.1892×10 5.5919×10 MMF6 (2.82) (1.57)+ (1.32+ (1.62)+ (1.11+ (2.24+ 2.2123×101 9.3871×10 9.9213×10 1.1043×10 1.4425×10 1.7973×10 MMF7 (1.10) (1.34×10+ (1.69×10+ (2.24t (5.30+ (7.96+ 9.2198×101 1.7057×10 1.6267×10 4.6517×10 6.3190×10 6.4822×10 MMFs (9.26 (6.22)H (5.81+ (2.09+ (2.46H (2.60+ 4.6080×10 4.4185×10 6.3622×10 2.1583×10 3.1509×10 2.0969×10 SYM-I (6.61) (1.98×10+ (8.98×10+ (1.08+ (3.16+ (1.44+ 4.2609×10 4.1357 1.9233 1.8262×10 1.7334×10 1.9878×10 SYM-Π (3.65) (4.95+ (2.28+ (1.27)+ (9.63x10+ (1.11+ 4.2446×10 8.3235 1.2277 9.2998 1.6145×10 1.0844×10 SYM-III (8.28) (1.18×10+ (2.04+ (5.04+ (2.67)+ (2.13×103r
3.2 实验设置 为验证 ZLS-SMPSO-MM 的性能，本文选取 5 种多模态多目标进化算法来进行比较。其分别 是 DN-NSGA-II[2] 、Omni-optimizer[22] 、MO-RingPSO-SCD[4] 、SMPSO-MM[5] 、Zoning-MO-Ring-SCDPSO[7]。同时，所有比较算法的参数设置与原文献 一致。本实验中所有测试函数均为 2 目标问题， 所有测试函数的种群数量均设置为 800，最大评 价次数为 80 000，单个粒子使用 CMA-ES 算法的 评价次数设置为 12。外部存档容量设置为 800。 每种算法在测试函数上均独立运行 20 次。为保 证实验结果分析的可靠性，采用 Wilcoxon[23] 和 Friedman[24] 非参数检验方法对实验结果进行统计 分析，显著性水平设置为 5%。其中“+”、“−”分别 表示所提算法优于、劣于相比较算法；“≈”表示所 提算法与相比较的算法性能相近。 3.3 结果对比 ZLS-SMPSO-MM 与其他 5 种比较算法所得 PSP 值的平均值和标准方差见表 2。同时，由 Wilcoxon 得到的统计分析结果也在表 2 中显示。从 表 2 可以看出，所提算法在 14 个测试函数上所得 结果都要显著好于 DN-NSGA-II、Omni-optimizer、 MO-Ring-PSO-SCD、ZS-MO-Ring-SCD-PSO。相比 于 SMPSO-MM，除在 MMF3 函数上取得相似的结 果，ZLS-SMPSO-MM 在其他测试函数上都能得到 更好的结果。同时，这 6 种算法得到的 PSP 值排 序结果如下表 3，在该表中，利用 Friedman 非参数 检验方法对实验结果进行统计分析时，将所有算 法得到的测试函数的 PSP 值均取为其相反数，故 排序值越小，算法性能越佳。根据表 3 结果可得， ZLS-SMPSO-MM 在所有比较算法中性能最佳。 这是因为使用多模态多目标进化算法进行搜索前 先使用分区策略划分了决策空间。在各个互不重 叠的子空间区域使用相同规模的粒子群分别进行 空间搜索，提升种群多样性的同时也降低了各个 子空间的搜索难度；每个子空间内都引入局部搜 索算法，在每次全局搜索后的潜力区域用局部搜 索能力强的 CMA-ES 算法进行精细搜索，因此能 够找到更多高质量的解。 表 2 不同算法得到的 PSP 平均值与标准方差 Table 2 PSP average and standard deviation values obtained by different algorithms 测试函数 ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO MMF1 1.126 4×102 (6.52) 4.209 1×101 (4.12)+ 4.803 2×101 (4.94)+ 6.712 4×101 (3.45)+ 8.636 7×101 (4.27)+ 9.215 8×101 (5.40)+ MMF2 1.904 3×102 (1.45×101 ) 6.942 9×101 (2.30×101 )+ 7.061 5×101 (3.63×101 )+ 1.083 5×102 (1.12×101 )+ 1.520 1×102 (1.05×101 )+ 1.348 7×102 (1.61×101 )+ MMF3 1.848 2×102 (2.18×101 ) 7.401 8×101 (3.53×101 )+ 7.631 2×101 (1.89×101 )+ 1.360 4×102 (1.97×101 )+ 1.863 8×102 (1.80×101 )≈ 1.308 1×102 (1.64×101 )+ MMF4 2.456 6×102 (1.11) 4.368 4×101 (8.32)+ 3.738 0×101 (7.87)+ 1.158 0×102 (4.06)+ 1.373 9×102 (5.93)+ 1.930 6×102 (5.81)+ MMF5 4.975 5×101 (2.61) 1.449 5×101 (1.64)+ 1.494 8×101 (1.31)+ 3.353 7×101 (1.10)+ 4.029 7×101 (1.51)+ 4.384 0×101 (2.42)+ MMF6 6.346 0×101 (2.82) 1.775 3×101 (1.57)+ 1.738 9×101 (1.32)+ 3.658 3×101 (1.62)+ 4.189 2×101 (1.11)+ 5.591 9×101 (2.24)+ MMF7 2.212 3×102 (1.10) 9.387 1×101 (1.34×101 )+ 9.921 3×101 (1.69×101 )+ 1.104 3×102 (2.24)+ 1.442 5×102 (5.30)+ 1.797 3×102 (7.96)+ MMF8 9.219 8×101 (9.26) 1.705 7×101 (6.22)+ 1.626 7×101 (5.81)+ 4.651 7×101 (2.09)+ 6.319 0×101 (2.46)+ 6.482 2×101 (2.60)+ SYM-I 4.608 0×101 (6.61) 4.418 5×10−1 (1.98×10−1)+ 6.362 2×10−1 (8.98×10−1)+ 2.158 3×101 (1.08)+ 3.150 9×101 (3.16)+ 2.096 9×101 (1.44)+ SYM-II 4.260 9×101 (3.65) 4.135 7 (4.95)+ 1.923 3 (2.28)+ 1.826 2×101 (1.27)+ 1.733 4×101 (9.63×10−1)+ 1.987 8×101 (1.11)+ SYM-III 4.244 6×101 (8.28) 8.323 5 (1.18×101 )+ 1.227 7 (2.04)+ 9.299 8 (5.04)+ 1.614 5×101 (2.67)+ 1.084 4×101 ((2.13×10−2))+ 第 4 期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·779·
·780· 智能系统学报 第16卷 续表2 测试函数ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO 1.6533×10 1.0624 9.0269×10 7.6712 7.7015 9.0821 Omni-I (1.24 (1.36×10+ (1.33×10+ (1.42)+ (1.46+ (1.09+ 1.2953 4.4938×10 4.0180x10 9.3771×10 9.5369×10 1.0120 Omni-Ⅱ (1.18×103 (1.03×10+ (8.04×10+ (4.98×103+ (1.02×10+ (7.30×103+ 5.2940×10 2.6451×10 2.5518×10 4.9687×10 4.8556×10 5.0214×10 Omni-III 1.69×103 (7.38×10+ (6.75×103)+ (1.98×103+ (1.29×10+ (2.13×10+ +/-≈ 14/0/0 14/0/0 14/0/0 13/0/1 14/0/0 表3所有比较算法在PSP上的性能排序 表4中可以看出，ZLS-SMPSO-MM只在MM7、 Table 3 Performance rankins of all compared algorithms SYM-I、SYM-I、SYM-III和OMNI-I这5个测试 on PSP 函数中得到较好的结果，Omni-optimizer则在剩余 算法 排序 的9个测试函数中占优势，但它们之间的数值差 ZLS-SMPSO-MM 1.4 异并不是很显著。这6种比较算法得到的HV值 ZS-MO-Ring-SCD-PSO 2.53333 排序结果见表5，ZLS-SMPSO-MM排在第二位。 SMPSO-MM 2.73333 主要原因是ZLS-SMPSO-MM中采取的分区策略 MO-Ring-PSO-SCD 3.66667 和局部搜索只能改变算法在决策空间的性能，对 DN-NSGA-II 5.13333 目标空间的影响十分有限。目标空间中仍旧采取 5.53333 了之前的选择策略，因此性能提升效果不明显， Omni-optmizer 但相对于除Omni-optimizer外的其他算法，所提 ZLS-SMPSO-MM与其他5种比较算法所得 算法在目标空间的表现还是要优于其他4种算 HV值的平均值和标准方差见表4。同时，由W- 法。因此，若是想提升算法在目标空间的性能就 coxon得到的统计分析结果也在表4中显示。从 必须在目标空间中使用合适的多目标处理技术。 表4不同算法得到的V平均值与标准方差 Table 4 HV average and standard deviation values obtained by different algorithms 测试函数ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO 3.6652 3.6651 3.6654 3.6645 3.6651 3.6648 MMF (3.29×10 (3.57x10≈ (1.10×10- (3.87×10+ (3.44×10≈ (5.00×10+ 3.6589 3.6653 3.6657 3.6497 3.6572 3.6528 MMF2 (2.00×10 (7.09×10 (8.01×105- (6.31×10+ (2.58×103+ (5.20×10+ 3.6579 3.6634 3.6657 3.6530 3.6591 3.6497 MMF3 (2.24×103 (9.03×10 (3.58-05 (6.48×10)+ (2.39x10 (6.67×10+ 3.3308 3.3319 3.3323 3.3304 3.3313 3.3309 MMF4 (1.30×103 (2.44×10 2.93x105- (8.13×10= (9.04×10)= (9.14×10= 3.6653 3.6652 3.6657 3.6646 3.6651 3.6650 MMFs (4.36×10 (2.42×10= (2.37×105- (4.77×10+ (3.64×10= (5.17×10 3.6654 3.6652 3.6657 3.6647 3.6650 3.6650 MMF (3.76×10 (2.88×10= (2.64×105- 3.64×10+ (4.03×10+ (3.90x10+ 3.6659 3.6641 3.6654 3.6649 3.6654 3.6655 MMF7 (2.68×10 (6.57×x10+ (5.96×10+ (1.41×103+ (1.97×10+ (3.66×10+ 3.2135 3.2122 3.2136 3.2106 3.2124 3.2119 MMFs (3.51×10 (9.03×10+ (6.14x10= (1.41×10+ (8.45×10+ (1.18×103+ 1.3269 1.3222 1.3227 1.2984 1.3094 1.2990 SYM-I (2.50×10 (3.12×10+ (3.51×10+ 1.74×103+ (1.60×10+ (1.93×10+ 1.3253 1.3187 1.3207 1.2910 1.2868 1.2959 SYM-II (1.97×10 (3.90×10+ (1.65×10+ (2.91×10+ (2.87×10+ (2.03×10+
ZLS-SMPSO-MM 与其他 5 种比较算法所得 HV 值的平均值和标准方差见表 4。同时，由 Wilcoxon 得到的统计分析结果也在表 4 中显示。从 表 4 中可以看出，ZLS-SMPSO-MM 只在 MM7、 SYM-I、SYM-II、SYM-III 和 OMNI-I 这 5 个测试 函数中得到较好的结果，Omni-optimizer 则在剩余 的 9 个测试函数中占优势，但它们之间的数值差 异并不是很显著。这 6 种比较算法得到的 HV 值 排序结果见表 5，ZLS-SMPSO-MM 排在第二位。 主要原因是 ZLS-SMPSO-MM 中采取的分区策略 和局部搜索只能改变算法在决策空间的性能，对 目标空间的影响十分有限。目标空间中仍旧采取 了之前的选择策略，因此性能提升效果不明显， 但相对于除 Omni-optimizer 外的其他算法，所提 算法在目标空间的表现还是要优于其他 4 种算 法。因此，若是想提升算法在目标空间的性能就 必须在目标空间中使用合适的多目标处理技术。 续表 2 测试函数 ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO Omni-I 1.653 3×101 (1.24) 1.062 4 (1.36×10−1)+ 9.026 9×10−1 (1.33×10−1)+ 7.671 2 (1.42)+ 7.701 5 (1.46)+ 9.082 1 (1.09)+ Omni-II 1.295 3 (1.18×10−2) 4.493 8×10−1 (1.03×10−1)+ 4.018 0×10−1 (8.04×10−2)+ 9.377 1×10−1 (4.98×10−2)+ 9.536 9×10−1 (1.02×10−1)+ 1.012 0 (7.30×10−2)+ Omni-III 5.294 0×10−1 (1.69×10−2) 2.645 1×10−1 (7.38×10−2)+ 2.551 8×10−1 (6.75×10−2)+ 4.968 7×10−1 (1.98×10−2)+ 4.855 6×10−1 (1.29×10−2)+ 5.021 4×10−1 (2.13×10−2)+ +/−/≈ 14/0/0 14/0/0 14/0/0 13/0/1 14/0/0 表 3 所有比较算法在 PSP 上的性能排序 Table 3 Performance rankins of all compared algorithms on PSP 算法 排序 ZLS-SMPSO-MM 1.4 ZS-MO-Ring-SCD-PSO 2.533 33 SMPSO-MM 2.733 33 MO-Ring-PSO-SCD 3.666 67 DN-NSGA-II 5.133 33 Omni-optmizer 5.533 33 表 4 不同算法得到的 HV 平均值与标准方差 Table 4 HV average and standard deviation values obtained by different algorithms 测试函数 ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO MMF1 3.665 2 (3.29×10−4) 3.665 1 (3.57×10−4)≈ 3.665 4 (1.10×10−3)− 3.664 5 (3.87×10−4)+ 3.665 1 (3.44×10−4)≈ 3.664 8 (5.00×10−4)+ MMF2 3.658 9 (2.00×10−3) 3.665 3 (7.09×10−4)− 3.665 7 (8.01×10−5)− 3.649 7 (6.31×10−3)+ 3.657 2 (2.58×10−3)+ 3.652 8 (5.20×10−3)+ MMF3 3.657 9 (2.24×10−3) 3.663 4 (9.03×10−3)− 3.665 7 (3.58-05)− 3.653 0 (6.48×10−3)+ 3.659 1 (2.39×10−3)− 3.649 7 (6.67×10−3)+ MMF4 3.330 8 (1.30×10−3) 3.331 9 (2.44×10−4)− 3.332 3 (2.93×10−5)− 3.330 4 (8.13×10−4)≈ 3.331 3 (9.04×10−4)≈ 3.330 9 (9.14×10−4)≈ MMF5 3.665 3 (4.36×10−4) 3.665 2 (2.42×10−4)≈ 3.665 7 (2.37×10−5)− 3.664 6 (4.77×10−4)+ 3.665 1 (3.64×10−4)≈ 3.665 0 (5.17×10−4)≈ MMF6 3.665 4 (3.76×10−4) 3.665 2 (2.88×10−4)≈ 3.665 7 (2.64×10−5)− 3.664 7 (3.64×10−4)+ 3.665 0 (4.03×10−4)+ 3.665 0 (3.90×10−4)+ MMF7 3.665 9 (2.68×10−4) 3.664 1 (6.57×10−4)+ 3.665 4 (5.96×10−4)+ 3.664 9 (1.41×10−3)+ 3.665 4 (1.97×10−4)+ 3.665 5 (3.66×10−4)+ MMF8 3.213 5 (3.51×10−4) 3.212 2 (9.03×10−4)+ 3.213 6 (3.14×10−4)≈ 3.210 6 (1.41×10−3)+ 3.212 4 (8.45×10−4)+ 3.211 9 (1.18×10−3)+ SYM-I 1.326 9 (2.50×10−4) 1.322 2 (3.12×10−4)+ 1.322 7 (3.51×10−4)+ 1.298 4 1.74×10−3+ 1.309 4 (1.60×10−3)+ 1.299 0 (1.93×10−3)+ SYM-II 1.325 3 (1.97×10−4) 1.318 7 (3.90×10−4)+ 1.320 7 (1.65×10−4)+ 1.291 0 (2.91×10−3)+ 1.286 8 (2.87×10−3)+ 1.295 9 (2.03×10−3)+ ·780· 智 能 系 统 学 报 第 16 卷
第4期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·781· 续表4 测试函数ZLS-SMPSO-MMDN-NSGA-ⅡOmni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO 1.3216 1.3192 1.3209 1.2875 1.2783 1.2888 SYM-III (6.10×10 (3.77×10+ (3.13×10+ (2.70×103+ (3.89×10+ (2.63×10+ 6.2099×10 6.2057×10 6.2059×101 6.1970×10 6.1977×10 6.1984×10 Omni-I (7.60×103 (5.03×10+ (2.31×10+ (1.34×103+ (1.18×10+ (9.82×10+ 7.7276×10 7.7542×10 7.7547×10 7.7011×10 7.6990×10 7.7056×10 Omni-Ⅱ (4.07×103 (1.83×10- (7.17×103 (8.13×10+ (1.01×10+ (5.68×103+ 9.3591×10 9.4590×10 9.4600×10 9.2858×10 9.2626×10 9.2801×10 Omni-Ⅲ (1.92×10 (7.15×10 (4.16×103 (2.74×10+ (2.30x10+ (2.12×10+ +/- 6/5/3 5/8/1 13/1/0 10/1/3 12/0/2 表5所有比较算法在V上的性能排序 到更多的等价解。主要是由于分区搜索能够维持 Table 5 Performance rankins of all compared algorithms 算法种群多样性和降低问题求解难度，而局部搜 on HV 索能够提高搜索精度。另外，从ZS-SMPSO-MM 算法 排序 与SMPSO-MM的结果来看，除MMF,、SYM-I Omni-optimizer 1.6 SYM-I这3个测试函数外，其余测试函数的PSP ZLS-SMPSO-MM 2.6 值均显著优于SMPSO-MM,从实验结果可知，分 DN-NSGA-II 2.66667 区搜索能够帮助SMPSO-MM算法定位到更多的 SMPSO-MM 4.06667 等效解，该结论与文献[)一致。 ZS-MO-Ring-SCD-PSO 4.26667 表6 SMPSO-MM.及其变种得到的PSP平均值与标准方差 MO-Ring-PSO-SCD Table 6 PSP average and standard deviation values ob- 5.8 tained by SMPSO-MM and its variant algorithms 综合各算法的PSP值和HV值实验结果，所 测试函数ZLS-SMPSO-MMZS-SMPSO-MM SMPSO-MM 提ZLS-SMPSO-MM算法获得的帕累托解集能够 1.1264×10 1.2141×10 8.6367×10 较好地逼近真实帕累托前沿，相比于其他算法具 MMF (6.52) (4.90- (4.27+ 有更好的收敛性和多样性。 1.9043×10 1.6992×10 1.5201×10 3.4算法分析 MMF2 (L.45×10 (1.63×10+ (1.05×10+ 3.4.1分区搜索与局部搜索对算法的影响 1.8482×10 1.7744×10 1.8638×102 为验证分区搜索与局部搜索的有效性，该部 MMF3 (2.18×10 (1.42×10户 (1.80×10)= 分实验分别选取没有分区搜索和局部搜索的 2.4566×10 2.5395×10 1.3739×10 SMPSO-MM、有分区搜索但没有局部搜索的 MMF (1.11) (1.01×10- (5.93)+ SMPSO-MM(命名为ZS-SMPSO-MM)来和所提算 4.9755×101 4.9625×10 4.0297×10 法进行性能比较。同时，所有算法参数设置与 MMFs (2.61) (2.14) (1.51+ 3.2节一致；并挑选3.2节14个测试函数进行实 6.3460×10 7.2977×10 4.1892×10 验，所得结果见表6。 MMF. (2.82) (2.82) (1.11+ 从ZLS-SMPSO-MM和ZS-SMPSO-MM的结 2.2123×10 2.5292×10 1.4425×10 果来看，除MMF:、MMF4、MMF6、MMF; MMF, (1.10) (1.10×10- (5.30+ MMF,这5个测试函数外，ZLS-SMPSO-MM在其 9.2198×10 余测试函数上得到的PSP值均明显优于ZS 7.5982×10 6.3190×10 MMFs SMPSO-MM,尤其是在较复杂的SYM函数与 (9.26 (4.39)+ (2.46)+ OMNI函数上。这说明局部搜索策略能够有效辅 4.6080×101 2.2080×10 3.1509×10 SYM-I 助多模态多目标进化算法找到更高质量和更多的 (6.61) (1.66+ (3.16+ 等效解。从ZLS-SMPSO-MM与SMPSO-MM的 4.2609×10 1.6895×10 1.7334×10' SYM-II 结果来看，除MMF,测试函数外，所提算法能够 (3.65 (1.78+ (9.63×10+ 在所有测试函数上取得更佳效果。这表明分区搜 4.2446×10 2.0026×10 1.6145×10 SYM-III 索和局部搜索能够有效帮助SMPSO-MM算法找 (8.28) (1.67)+ (2.67)+
综合各算法的 PSP 值和 HV 值实验结果，所 提 ZLS-SMPSO-MM 算法获得的帕累托解集能够 较好地逼近真实帕累托前沿，相比于其他算法具 有更好的收敛性和多样性。 3.4 算法分析 3.4.1 分区搜索与局部搜索对算法的影响 为验证分区搜索与局部搜索的有效性，该部 分实验分别选取没有分区搜索和局部搜索的 SMPSO-MM、有分区搜索但没有局部搜索的 SMPSO-MM(命名为 ZS-SMPSO-MM) 来和所提算 法进行性能比较。同时，所有算法参数设置与 3.2 节一致；并挑选 3.2 节 14 个测试函数进行实 验，所得结果见表 6。 从 ZLS-SMPSO-MM 和 ZS-SMPSO-MM 的结 果来看， 除 MMF 1 、 MMF 4 、 MMF 6 、 MMF 5 、 MMF7 这 5 个测试函数外，ZLS-SMPSO-MM 在其 余测试函数上得到 的 PSP 值均明显优 于 ZSSMPSO-MM，尤其是在较复杂的 SYM 函数与 OMNI 函数上。这说明局部搜索策略能够有效辅 助多模态多目标进化算法找到更高质量和更多的 等效解。从 ZLS-SMPSO-MM 与 SMPSO-MM 的 结果来看，除 MMF3 测试函数外，所提算法能够 在所有测试函数上取得更佳效果。这表明分区搜 索和局部搜索能够有效帮助 SMPSO-MM 算法找 到更多的等价解。主要是由于分区搜索能够维持 算法种群多样性和降低问题求解难度，而局部搜 索能够提高搜索精度。另外，从 ZS-SMPSO-MM 与 SMPSO-MM 的结果来看，除 MMF3、SYM-I、 SYM-II 这 3 个测试函数外，其余测试函数的 PSP 值均显著优于 SMPSO-MM，从实验结果可知，分 区搜索能够帮助 SMPSO-MM 算法定位到更多的 等效解，该结论与文献 [7] 一致。 续表 4 测试函数 ZLS-SMPSO-MM DN-NSGA-II Omni-optimizer MO-Ring-SCD-PSO SMPSO-MM ZS-MO-Ring-SCD-PSO SYM-III 1.321 6 (5.10×10−4) 1.319 2 (3.77×10−4)+ 1.320 9 (3.13×10−4)+ 1.287 5 (2.70×10−3)+ 1.278 3 (3.89×10−3)+ 1.288 8 (2.63×10−3)+ Omni-I 6.209 9×101 (7.60×10−3) 6.205 7×101 (5.03×10−4)+ 6.205 9×101 (2.31×10−4)+ 6.197 0×101 (1.34×10−2)+ 6.197 7×101 (1.18×10−2)+ 6.198 4×101 (9.82×10−3)+ Omni-II 7.727 6×101 (4.07×10−2) 7.754 2×101 (1.83×10−3)− 7.754 7×101 (7.17×10−3)− 7.701 1×101 (8.13×10−1)+ 7.699 0×101 (1.01×10−1)+ 7.705 6×101 (5.68×10−2)+ Omni-III 9.359 1×101 (1.92×10−1) 9.459 0×101 (7.15×10−3)− 9.460 0×101 (4.16×10−3)− 9.285 8×101 (2.74×10−1)+ 9.262 6×101 (2.30×10−1)+ 9.280 1×101 (2.12×10−1)+ +/−/≈ 6/5/3 5/8/1 13/1/0 10/1/3 12/0/2 表 5 所有比较算法在 HV 上的性能排序 Table 5 Performance rankins of all compared algorithms on HV 算法 排序 Omni-optimizer 1.6 ZLS-SMPSO-MM 2.6 DN-NSGA-II 2.666 67 SMPSO-MM 4.066 67 ZS-MO-Ring-SCD-PSO 4.266 67 MO-Ring-PSO-SCD 5.8 表 6 SMPSO-MM 及其变种得到的 PSP 平均值与标准方差 Table 6 PSP average and standard deviation values obtained by SMPSO-MM and its variant algorithms 测试函数 ZLS-SMPSO-MM ZS-SMPSO-MM SMPSO-MM MMF1 1.126 4×102 (6.52) 1.214 1×101 (4.90)− 8.636 7×101 (4.27)+ MMF2 1.904 3×102 (1.45×101 ) 1.699 2×102 (1.63×101 )+ 1.520 1×102 (1.05×101 )+ MMF3 1.848 2×102 (2.18×101 ) 1.774 4×102 (1.42×101 )≈ 1.863 8×102 (1.80×101 )≈ MMF4 2.456 6×102 (1.11) 2.539 5×102 (1.01×101 )− 1.373 9×102 (5.93)+ MMF5 4.975 5×101 (2.61) 4.962 5×101 (2.14)≈ 4.029 7×101 (1.51)+ MMF6 6.346 0×101 (2.82) 7.297 7×101 (2.82)− 4.189 2×101 (1.11)+ MMF7 2.212 3×102 (1.10) 2.529 2×102 (1.10×101 )− 1.442 5×102 (5.30)+ MMF8 9.219 8×101 (9.26) 7.598 2×101 (4.39)+ 6.319 0×101 (2.46)+ SYM-I 4.608 0×101 (6.61) 2.208 0×101 (1.66)+ 3.150 9×101 (3.16)+ SYM-II 4.260 9×101 (3.65) 1.689 5×101 (1.78)+ 1.733 4×101 (9.63×10−1)+ SYM-III 4.244 6×101 (8.28) 2.002 6×101 (1.67)+ 1.614 5×101 (2.67)+ 第 4 期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·781·
·782· 智能系统学报 第16卷 续表6 3.4.3局部搜索评价次数A敏感值分析 测试函数ZLS-SMPSO-MMZS-SMPSO-MM SMPSO-MM 使用局部搜索的时间对算法性能会产生影 1.6533×10 9.4856 7.7015 Omni-I 响。直观来看，过早使用局部搜索会因为所寻得 (1.24 (9.65×10+ (1.46+ 的区域潜力不足而浪费计算资源，过晚使用则可 1.2953 1.0195 9.5369×10 Omni-Π 能无法发挥局部搜索的真正作用。因此，本节对 (1.18×103 (6.76×102+ (1.02×10+ 局部搜索的使用时间进行分析，并用P$P性能指 5.2940×10 4.9946×10 4.8556×101 Omni-III 标来对实验结果进行评价。选取3.1节的14个测 (1.69×103 (2.15×10+ (1.29×102+ +/-≈ 试函数进行实验。将局部搜索的使用时间设置为 8/4/2 13/1/0 算法已消耗的评价次数。使用时间分为A=0、 由于测试函数的帕累托解在整个决策空间并 A3=2000、A3=4000和A3=6000。除该参数外其 非均匀分布，因此均衡的分区策略会浪费一些计 余实验参数设置同3.2节。 算资源，如测试函数MMF;,SMPSO-MM加入分 所得结果使用Friedman测试来进行性能排 区搜索后，其PSP值反而下降。但总体来说，同 序，见图2。从图2中可以看出，在种群进化前期 时使用分区搜索与局部搜索能够提高算法求解多 加入局部搜索能够更加有效帮助算法找到更 模态多目标问题的能力。 多的等效解。其主要原因是局部搜索能够在较 3.4.2局部搜索评价次数A,敏感值分析 短时间内辅助多模态多目标进化算法找到高质 由于局部搜索会消耗一定的计算量，局部搜 量的解。当然，这完全取决于算法能否在进化前 索过多消耗计算资源可能使算法全局求解能力下 期就能找到有潜力的搜索区域。另外，图2表示 降，而过少消耗计算资源则可能导致局部搜索算 当算法已消耗评价次数不小于2000时，其能使 法能力发挥不足。故本部分对单个粒子进行局部 所提算法性能达到最佳，因此在所提算法中设置 搜索使用的评价次数进行分析，并用PSP性能指 A3=2000。 标来对实验结果进行评价。选取3.1节的14个测 试函数进行实验，并将单个粒子进行局部搜索使 3.5 用的评价次数A1设定为4、8、12、16，其他参数设 3.0 3.0000 定同3.2节。 2.64292.71432.7857 所得结果使用Friedman测试来进行性能排 2.5 序，见图1。从图1中可以看出，一开始随着局部 20 搜索评价次数的增加，算法的性能也会得到相应 的提升，但随着评价次数增加到一定的程度，算 1.5 法的性能反而会降低。这是因为合适的局部搜索 10 40006000 评价次数能平衡局部搜索能力与全局搜索能力。 0 2000 A 另外，根据图1的结果显示，当A1=12时，算法的 图2A3对所提算法的影响 性能表现最佳，因此在所提算法中将A设置为12。 Fig.2 Impact of A3 on the proposed aglroithm 3.0 3.4.4种群规模敏感值分析 2.7143 2.6429 为分析种群规模对算法的影响，本实验选取 2.5 2.4286 第3.1节的14个测试函数：使用PSP作为算法性 2.2143 能评价指标；并将种群规模分别设定为400、800、 2.0 1200、1600,其他参数设定同第3.2节。最大评 1.5 价次数均为80000。 所得结果使用Friedman测试来进行性能排 1.0 8 12 6 序，见图3。从图3中可以看出，随着种群规模的 A 增加，算法的性能逐渐降低。其主要原因是，虽 图1A1对所提算法的影响 然大的种群规模可以提高各个分区的种群多样 Fig.1 Impact of A1 on the proposed aglroithm 性，但在计算资源有限的情况下，搜索代数会减
由于测试函数的帕累托解在整个决策空间并 非均匀分布，因此均衡的分区策略会浪费一些计 算资源，如测试函数 MMF3，SMPSO-MM 加入分 区搜索后，其 PSP 值反而下降。但总体来说，同 时使用分区搜索与局部搜索能够提高算法求解多 模态多目标问题的能力。 3.4.2 局部搜索评价次数 A1 敏感值分析 由于局部搜索会消耗一定的计算量，局部搜 索过多消耗计算资源可能使算法全局求解能力下 降，而过少消耗计算资源则可能导致局部搜索算 法能力发挥不足。故本部分对单个粒子进行局部 搜索使用的评价次数进行分析，并用 PSP 性能指 标来对实验结果进行评价。选取 3.1 节的 14 个测 试函数进行实验，并将单个粒子进行局部搜索使 用的评价次数 A1 设定为 4、8、12、16，其他参数设 定同 3.2 节。 A1 = 12A1 所得结果使用 Friedman 测试来进行性能排 序，见图 1。从图 1 中可以看出，一开始随着局部 搜索评价次数的增加，算法的性能也会得到相应 的提升，但随着评价次数增加到一定的程度，算 法的性能反而会降低。这是因为合适的局部搜索 评价次数能平衡局部搜索能力与全局搜索能力。 另外，根据图 1 的结果显示，当 时，算法的 性能表现最佳，因此在所提算法中将 设置为 12。 3.0 2.5 2.0 1.5 1.0 排序值 0 8 12 16 4 A1 2.714 3 2.428 6 2.214 3 2.642 9 图 1 A1 对所提算法的影响 Fig. 1 Impact of A1 on the proposed aglroithm 3.4.3 局部搜索评价次数 A3 敏感值分析 A3 = 0 A3 = 2 000 A3 = 4 000 A3 = 6 000 使用局部搜索的时间对算法性能会产生影 响。直观来看，过早使用局部搜索会因为所寻得 的区域潜力不足而浪费计算资源，过晚使用则可 能无法发挥局部搜索的真正作用。因此，本节对 局部搜索的使用时间进行分析，并用 PSP 性能指 标来对实验结果进行评价。选取 3.1 节的 14 个测 试函数进行实验。将局部搜索的使用时间设置为 算法已消耗的评价次数。使用时间分为 、 、 和 。除该参数外其 余实验参数设置同 3.2 节。 A3 = 2 000 所得结果使用 Friedman 测试来进行性能排 序，见图 2。从图 2 中可以看出，在种群进化前期 加入局部搜索能够更加有效帮助算法找到更 多的等效解。其主要原因是局部搜索能够在较 短时间内辅助多模态多目标进化算法找到高质 量的解。当然，这完全取决于算法能否在进化前 期就能找到有潜力的搜索区域。另外，图 2 表示 当算法已消耗评价次数不小于 2 000 时，其能使 所提算法性能达到最佳，因此在所提算法中设置 。 3.5 3.0 2.0 2.5 1.5 1.0 排序值 0 2 000 4 000 6 000 A3 3.000 0 2.642 9 2.714 3 2.785 7 图 2 A3 对所提算法的影响 Fig. 2 Impact of A3 on the proposed aglroithm 3.4.4 种群规模敏感值分析 为分析种群规模对算法的影响，本实验选取 第 3.1 节的 14 个测试函数；使用 PSP 作为算法性 能评价指标；并将种群规模分别设定为 400、800、 1 200、1 600，其他参数设定同第 3.2 节。最大评 价次数均为 80 000。 所得结果使用 Friedman 测试来进行性能排 序，见图 3。从图 3 中可以看出，随着种群规模的 增加，算法的性能逐渐降低。其主要原因是，虽 然大的种群规模可以提高各个分区的种群多样 性，但在计算资源有限的情况下，搜索代数会减 续表 6 测试函数 ZLS-SMPSO-MM ZS-SMPSO-MM SMPSO-MM Omni-I 1.653 3×101 (1.24) 9.485 6 (9.65×10−1)+ 7.701 5 (1.46)+ Omni-II 1.295 3 (1.18×10−2) 1.019 5 (6.76×10−2)+ 9.536 9×10−1 (1.02×10−1)+ Omni-III 5.294 0×10−1 (1.69×10−2) 4.994 6×10−1 (2.15×10−2)+ 4.855 6×10−1 (1.29×10−2)+ +/−/≈ 8/4/2 13/1/0 ·782· 智 能 系 统 学 报 第 16 卷
第4期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·783· 小，这将直接影响算法的搜索效率。同时，当算 ing multimodal multi-objective problems[J].IEEE transac- 法种群规模在400时，算法的性能最佳。但为与 tions on evolutionary computation,2018,22(5):805-817. 第3.2节中比较算法的种群规模保持一致，所提 [5]LIANG Jing,GUO Qiangian,YUE Caitong,et al.A self- 算法的种群规模仍设置为800。 organizing multi-objective particle swarm optimization al- gorithm for multimodal multi-objective problems[C]//Pro- 35 3.2000 ceedings of the 9th International Conference on Swarm In- 3.0 telligence.Shanghai,China:Springer,2018:550-560. 2.7333 [6]LI Zhihui,SHI Li,YUE Caitong,et al.Differential evolu- 2.5 tion based on reinforcement learning with fitness ranking 2.0000 2.0667 2.0 for solving multimodal multiobjective problems[J].Swarm and evolutionary computation,2019,49:234-244. 1.5 [7]FAN Qing,YAN Xuefeng.Solving multimodal multiob- 1.0 jective problems through zoning search[J].IEEE transac- 400 800 12001600 种群规模 tions on systems,man,and cybernetics:systems,2019. [8]ZHANG Weizheng,LI Guoqing,ZHANG Weiwei,et al.A 图3种群规模对所提算法的影响 Fig.3 Impact of population size on the proposed aglroithm cluster based PSO with leader updating mechanism and ring-topology for multimodal multi-objective 4结束语 optimization[J].Swarm and evolutionary computation, 2019.50:100569. 为提高多模态多目标进化算法在搜索过程中 [9]LIANG Jing,XU Weiwei,YUE Caitong,et al.Multimod- 的种群多样性和搜索等价解的能力，本文提出一 al multiobjective optimization with differential 种融合分区和局部搜索的多模态多目标粒子群算 evolution[J].Swarm and evolutionary computation,2019, 法ZLS-SMPSO-MM。在该算法中，首先将整个搜 44:1028-1059 索空间分成多个子空间，然后使用多模态多目标 [10]LIU Yiping,YEN G,GONG Dunwei.A Multimodal mul- 粒子群算法对各个子空间进行搜索，并使用局部 tiobjective evolutionary algorithm using two-archive and 搜索来提高算法的搜索效率，最后将各个子空间 recombination strategies[.IEEE transactions on evolu- 所得解集进行合并选择。为验证ZLS-SMPSO- tionary computation,2019,23(4):660-674. MM算法的性能，选取14个多模态多目标优化问 [11]LIN Qiuzhen,LIN Wu,ZHU Zexuan,et al.Multimodal 题，并将其与DN-NSGA-lⅡ、Omni-optimizer、MO- multiobjective evolutionary optimization with dual clus- Ring-PSO-SCD、SMPSO-MM、ZS-MO-Ring-SCD- tering in decision and objective spaces[J].IEEE transac- tions on evolutionary computation,2021,25(1):130-144. PSO等多模态多目标算法进行比较。实验结果表 [12]ZHANG Xuewei,LIU Hao,TU Liangping.A modified 明，分区搜索和局部搜索能够有效帮助SMPSO: particle swarm optimization for multimodal multi-object- MM找到更多的等价解。 ive optimization[J].Engineering applications of artificial 参考文献： intelligence,2020,95:103905 [13]LI Guosen,YAN Li,QU Boyang.Multi-objective particle [1]BRANKE J.Multiobjective optimization[M].Berlin: swarm optimization based on Gaussian sampling[J].IEEE Springer,2008. access,2020,8:209717-209737 [2]LIANG JJ.YUE C T,QU B Y.Multimodal multi-object- [14]DEB K.Multi-objective evolutionary algorithms:introdu- ive optimization:a preliminary study[C]//Proceedings of cing bias among pareto-optimal solutions[M]//GHOSH A, 2016 IEEE Congress on Evolutionary Computation.Van- TSUTSUI S.Advances in Evolutionary Computing.Ber- couver,Canada:IEEE,2016:2454-2461 lin:Springer,2003. [3]LI Xiaodong.Niching without niching parameters:particle [15]DEB K.Multi-objective genetic algorithms:problem dif- swarm optimization using a ring topology[J].IEEE trans- ficulties and construction of test problems[J].Evolution- actions on evolutionary computation,2010,14(4): ary computation,1999,7(3):205-230. 150-169 [16]ZITZLER E,THIELE L.Multiobjective evolutionary al- [4]YUE Caitong,QU Boyang,LIANG Jing.A multi-object- gorithms:a comparative case study and the strength ive particle swarm optimizer using ring topology for solv- Pareto approach[J].IEEE transactions on evolutionary
小，这将直接影响算法的搜索效率。同时，当算 法种群规模在 400 时，算法的性能最佳。但为与 第 3.2 节中比较算法的种群规模保持一致，所提 算法的种群规模仍设置为 800。 3.5 3.0 2.5 2.0 1.5 1.0 排序值 400 800 1 200 1 600 种群规模 2.000 0 2.066 7 2.733 3 3.200 0 图 3 种群规模对所提算法的影响 Fig. 3 Impact of population size on the proposed aglroithm 4 结束语 为提高多模态多目标进化算法在搜索过程中 的种群多样性和搜索等价解的能力，本文提出一 种融合分区和局部搜索的多模态多目标粒子群算 法 ZLS-SMPSO-MM。在该算法中，首先将整个搜 索空间分成多个子空间，然后使用多模态多目标 粒子群算法对各个子空间进行搜索，并使用局部 搜索来提高算法的搜索效率，最后将各个子空间 所得解集进行合并选择。为验证 ZLS-SMPSOMM 算法的性能，选取 14 个多模态多目标优化问 题，并将其与 DN-NSGA-II、Omni-optimizer、MORing-PSO-SCD、SMPSO-MM、ZS-MO-Ring-SCDPSO 等多模态多目标算法进行比较。实验结果表 明，分区搜索和局部搜索能够有效帮助 SMPSOMM 找到更多的等价解。 参考文献： BRANKE J. Multiobjective optimization[M]. Berlin: Springer, 2008. [1] LIANG J J, YUE C T, QU B Y. Multimodal multi-objective optimization: a preliminary study[C]//Proceedings of 2016 IEEE Congress on Evolutionary Computation. Vancouver, Canada: IEEE, 2016: 2454−2461. [2] LI Xiaodong. Niching without niching parameters: particle swarm optimization using a ring topology[J]. IEEE transactions on evolutionary computation, 2010, 14(4): 150–169. [3] YUE Caitong, QU Boyang, LIANG Jing. A multi-objective particle swarm optimizer using ring topology for solv- [4] ing multimodal multi-objective problems[J]. IEEE transactions on evolutionary computation, 2018, 22(5): 805–817. LIANG Jing, GUO Qianqian, YUE Caitong, et al. A selforganizing multi-objective particle swarm optimization algorithm for multimodal multi-objective problems[C]//Proceedings of the 9th International Conference on Swarm Intelligence. Shanghai, China: Springer, 2018: 550−560. [5] LI Zhihui, SHI Li, YUE Caitong, et al. Differential evolution based on reinforcement learning with fitness ranking for solving multimodal multiobjective problems[J]. Swarm and evolutionary computation, 2019, 49: 234–244. [6] FAN Qing, YAN Xuefeng. Solving multimodal multiobjective problems through zoning search[J]. IEEE transactions on systems, man, and cybernetics: systems, 2019. [7] ZHANG Weizheng, LI Guoqing, ZHANG Weiwei, et al. A cluster based PSO with leader updating mechanism and ring-topology for multimodal multi-objective optimization[J]. Swarm and evolutionary computation, 2019, 50: 100569. [8] LIANG Jing, XU Weiwei, YUE Caitong, et al. Multimodal multiobjective optimization with differential evolution[J]. Swarm and evolutionary computation, 2019, 44: 1028–1059. [9] LIU Yiping, YEN G, GONG Dunwei. A Multimodal multiobjective evolutionary algorithm using two-archive and recombination strategies[J]. IEEE transactions on evolutionary computation, 2019, 23(4): 660–674. [10] LIN Qiuzhen, LIN Wu, ZHU Zexuan, et al. Multimodal multiobjective evolutionary optimization with dual clustering in decision and objective spaces[J]. IEEE transactions on evolutionary computation, 2021, 25(1): 130–144. [11] ZHANG Xuewei, LIU Hao, TU Liangping. A modified particle swarm optimization for multimodal multi-objective optimization[J]. Engineering applications of artificial intelligence, 2020, 95: 103905. [12] LI Guosen, YAN Li, QU Boyang. Multi-objective particle swarm optimization based on Gaussian sampling[J]. IEEE access, 2020, 8: 209717–209737. [13] DEB K. Multi-objective evolutionary algorithms: introducing bias among pareto-optimal solutions[M]//GHOSH A, TSUTSUI S. Advances in Evolutionary Computing. Berlin: Springer, 2003. [14] DEB K. Multi-objective genetic algorithms: problem difficulties and construction of test problems[J]. Evolutionary computation, 1999, 7(3): 205–230. [15] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE transactions on evolutionary [16] 第 4 期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·783·
