第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(记作p<q)的条件是：如果Y0∈{1,2，…，p以， (6) P阳≤qe,并且p≠q。 式中：VOL0是勒贝格测度；r=(ri,2…,)是选 定理2 Pareto最优解集(pareto set,.PS):一个 择的参考点，该参考点被目标空间中所有获得的 向量x∈X,若不存在其他向量x∈X,使得 PF逼近中的个体所支配。HV可以用来衡量 F(x)>F(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 卷