第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]。而多模态多目标优化问题 (mul￾timodal 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 al￾gorithm，SMPSO-MM)。该算法使用自组织映射网 络构建粒子间的邻域关系并进行邻域间信息交 流；另外引入精英策略避免算法陷入停滞。实验 结果表明该算法能够定位到更多等价解，决策空 间解的分布也较均匀；Li 等 [6] 提出一种基于适应 度排序与强化学习的多模态多目标算法 (differen￾tial evolution based on reinforcement learning with fit￾ness ranking，DE-RLFR)，该算法首先使用适应度 函数联合排序值确定种群中每个个体的分层状 态，再根据分层状态确定进化方向和变异策略， 最后利用强化学习来引导种群搜索。实验证明该 算法可以显著提高决策空间中种群搜索效率，在 解决多模态多目标问题时有较好表现； Fan 等 [7] 则使用分区的概念来提高种群在决策空间中的 多样性和降低问题的求解复杂度。研究表明，该 方法能够辅助 MO-Ring-SO-SCD 找到更多等价 解。Zhang 等 [8] 提出一种基于聚类的多模态多目 标粒子群算法 (cluster based PSO with leader updat￾ing mechanism and ring-topology，MMO-CLR￾PSO)。该算法使用决策变量聚类方法划分子种 群，利用带有领导粒子更新机制的全局粒子群算 法独立地更新每一个子种群的粒子，并在子种群 之间建立环形结构探索未被开发的区域以搜索更 多的非支配解。实验结果证明该算法在决策空间 与目标空间的解集都能维持较好的多样性；Li￾ang 等 [9] 提出一种多模态多目标差分进化优化算 法 (multimodal multi-objective differential evolution optimization algorithm，MMODE)。该算法使用预 选择机制将所有个体进行适应度值排序后再根据 决策空间中的拥挤距离选择个体进行变异，同时 引入新的边界处理方法将停留在边界的个体重新 调整。实验结果证明利用 MMODE算法获得的 Pareto 解在决策空间和目标空间中都有一个较好 的表现；Liu 等 [10] 提出一种基于归档和重组策略 的多模态多目标算法 (multimodal multi-objective evolutionary algorithm using two-archive and recom￾bination strategies，TriMOEA-TA&R)。该算法使用 决策变量分析技术将种群个体分别归入多样性存 档和收敛性存档中，各自从两个存档中选择父代 进行交叉复制。此外，多样性存档中使用聚类算 法及清除策略来保证目标空间多样性。最终将两 个存档的解重组以形成最终解集。实验结果证 明，两个存档的分工减少了环境选择的难度，且 算法的整体性能明显优于比较算法；Lin 等 [11] 提 出一种决策空间和目标空间双重聚类的多模态多 目标进化算法 (multimodal multi-objective evolu￾tionary 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 optimiza￾tion based on gaussian sampling, GS-MOPSO) 的多 目标粒子群优化算法以求解多模态多目标问题。 该算法在搜索前期利用全局高斯采样方法来进行 全局搜索，在搜索后期则采用局部高斯采样来寻 找有潜力解的邻域。此外，GS-MOPSO 算法采用 一种新的外部存档策略来储存历史解。实验结果 表明，该算法能够找到更多 Pareto 解。 虽然诸多学者对多模态多目标进化算法进行 改进，但如何保持/提高种群多样性和提高局部搜 第 4 期 胡洁，等：融合分区和局部搜索的多模态多目标优化 ·775·