基于L_1/2范数拥挤度度量的多模态多目标优化算法

Multi⁃modal multi⁃objective optimization algorithm based on L_1/2⁃norm crowding measurement

摘要

为得到均匀性、多样性、收敛性更好的Pareto前沿及多样性较好的Pareto解集，提出了一种基于L_1/2范数的解空间和目标空间拥挤度度量方法。基于K⁃Means算法对解进行聚类，设计了非支配解的分解和合并策略，以得到更均匀Pareto前沿及多样化的Pareto解集。为验证算法的高效性，在CEC’2019标准函数中将改进的算法与5种基准测试算法进行对比，结果表明：改进的算法能够得到较优的rPSP、rHV、IGDX、IGDF度量指标。

Abstract

To obtain more uniformly， convergence distributed of Pareto Front （PF） and the diversity of Pareto Sets （PSs）， a crowding measurement strategy based on L_1/2 in the solution space and objective space was proposed. A non‑dominated solution decomposition and merging strategy， which clusters the solutions by using K⁃means， was designed to obtain uniformly PF and diversity PSs. For the sake of demonstrating the performance of the proposed algorithm， the experiments have been conducted on the CEC’2019 benchmark functions with five compared algorithms. Experimental results showed that the proposed algorithm could obtain a better metric value on rPSP， rHV， IGDX， IGDF.

Graphical abstract

关键词

多模态 / 多目标 / 拥挤度度量 / 解的合并

Key words

multi⁃modal / multi⁃objective / crowding measurement / merge of solutions

0 引言

多目标优化问题（Multi⁃Objective Problems， MOPs）作为复杂优化领域中的一个重要研究方向，涵盖众多实际问题的建模和求解，如网络通信中基站部署、网络优化、工业生产中的生产调度、交通运输等问题^［1-4］。优化问题可根据其定义和特征进行多维度分类，其中，根据优化问题的数目，可将其分为单目标优化算法和多目标优化算法^［5-7］。单目标优化致力于解决仅具有一个优化目标的问题，而多目标优化能够同时优化多个目标函数，全面考虑问题的多个方面，为问题提供更为综合和全面的解决方案，多目标的数学描述如式（1）：

\left\{\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}F(\mathit{x})=(f_{\mathrm{1}}(\mathit{x}),f_{\mathrm{2}}(\mathit{x}),\dots ,f_m{(\mathit{x}))}^{\mathrm{T}}\\ \mathrm{s}.\mathrm{t}.\\ g_j(\mathit{x})\le \mathrm{0},j=\mathrm{1},\dots ,p,\\ h_j(\mathit{x})=\mathrm{0},j=\mathrm{1},\dots ,q,\\ x={\left(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_n\right)}^{\mathrm{T}}\in {\mathbf{R}}^n;\end{array}\right.(1)

式中：g_{\mathrm{j}}(\mathit{x})是p个不等式约束，h_{\mathrm{j}}(\mathit{x})是q个等式约束，\mathit{x}\in {\mathbf{R}}^{\mathrm{n}}是n维的决策向量，F(\mathit{x})\in {\mathbf{R}}^{\mathrm{m}}是目标向量，包含m个优化目标。

多目标优化一般存在一系列的解，称为Pareto解集（Pareto Set， PS），映射到目标空间中称之为Pareto前沿（Pareto Front， PF）。多目标优化旨在为问题提供多样性的潜在解决方案，使决策者在多目标优化中拥有权衡不同目标的自主选择权，这更符合真实世界中决策过程的复杂性。因此，多目标优化能够更好地适应和解决复杂、多维度的问题，为处理现实中多层次、多约束的挑战提供更灵活的工具。

多模态多目标优化问题（Multi⁃modal Multi⁃Objective Optimization Problems， MMOPs）是一种特殊的多目标优化问题，即Pareto前沿具有两个及以上不同的Pareto解集，如图1所示。

相对于单模态优化，多模态优化能够显著提升信息的丰富度和解的多样性，从而增加潜在解。在不同任务和环境下，多模态优化具备灵活选择和切换不同模态信息的特性，从而有效提升系统的适应性。此外，多模态通过整合来自不同模态的信息，显著提高系统的鲁棒性，使其更能够适应各种环境和变化。与传统的单模态、单目标优化问题不同，MMOPs在问题结构中融合多个模态和多个目标，使得问题更加复杂、多样，呈现出更为丰富的多模态结构和多目标决策需求。

近些年，有学者对多目标多模态优化进行了研究^［8-10］。DEB等^［11］提出的Omni⁃optimizer，使用NSGAII算法框架，引入非支配排序方法，增加决策空间的多样性，筛选出优秀个体进入下一代种群。ZHANG等^［12］提出MOEA/D算法，将多目标问题分解为多个标量优化问题，并同时优化这些子问题，使用欧几里得距离来定义邻域关系，来处理不同规模的目标。LIANG等^［13］提出一种基于聚类的差分进化算法求解MMOPs，该算法在每个子空间中（不是在整个空间中）计算个体的拥挤度距离。ZHANG等^［14］提出MMO⁃EvoKnee算法找到全局膝关节解决方案和目标空间的边界，并且保留收敛性良好的解。LIU 等^［15］ 提出一种使用收敛档案及多样性档案协同获得多个Pareto最优解，提高决策空间的多样性，从而解决多目标多模态优化问题。ZHAO等^［16］提出一种基于强化进化的预测差分进化策略求解多模态多目标，使用预测策略、强化进化策略来加速种群收敛，从而逼近全局最优解。LI等^［17］提出一种基于强化学习的差分进化算法（DE⁃RLFR），设计奖励函数指导种群在全局趋近Pareto前沿。YUE等^［18］提出一种基于环形拓扑结构的粒子群算法，并使用特殊拥挤距离维持多个PS。ZITZLER等^［19］采用双存档的重组策略的多模态多目标进化算法，可以保证目标空间的多样性。

在决策空间中，采用拥挤距离^［20］（Crowding Distance， CD）来维护决策空间的多样性。通常情况下，决策空间多样性越高，意味着在决策空间中存在着良好的解的分布。然而，决策空间中种群的良好分布，并不能确保种群在客观空间中也存在着相应水平的良好多样性。因此，如何合理解决这个问题，需要进一步研究。

为解决这些问题，本文设计一种基于L_1/2范数的解拥挤度度量方法，通过定义距离函数构建解的拥挤度评价方法，为评价解的相似性提供依据，该方法可以保持种群多样性，提高种群分布的均匀性。

1 <italic>L</italic>₁<italic>_/</italic>₂范数拥挤度及解分类结果的合并

1.1 决策空间拥挤度

决策空间拥挤度度量公式为

\mathrm{C}{\mathrm{D}}_{j,x}={\displaystyle \sum _{i=\mathrm{1}}^n}\left(\frac{\sqrt[]{|x_{j_{\mathrm{1}},i}-x_{j_{\mathrm{2}},i}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}{\sqrt[]{|x_{\mathrm{m}\mathrm{a}\mathrm{x},i}-x_{\mathrm{m}\mathrm{i}\mathrm{n},i}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}\right),(2)

式中：CD _j，x 是解x_j 在决策空间拥挤度，x_{j_{\mathrm{1}},i}和x_{j_{\mathrm{2}},i}分别表示解x_j 在第i维决策空间上相邻的两个解，x_max，i 和x_min，i 则表示第i 维决策空间上边界解的最大值及最小值。如图2（a）所示，图中1，2，…，10分别表示2维决策空间中Pareto解集中的解x₁，x₂，…，x₁₀，则解x₃的拥挤度度量方式如下：

CD_3,x =\frac{\sqrt[]{|x_{\mathrm{9,1}}-x_{\mathrm{8,1}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}{\sqrt[]{|x_{\mathrm{10,1}}-x_{\mathrm{1,1}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}+\frac{\sqrt[]{|x_{\mathrm{4,2}}-x_{\mathrm{2,2}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}{\sqrt[]{|x_{\mathrm{8,2}}-x_{\mathrm{1,2}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}。(3)

1.2 目标空间拥挤度

在目标空间中，采用拥挤度度量方式的主要目的是维持Pareto前沿的多样性、均匀分布，并避免解决方案过度集中在某个局部区域。此外，拥挤度度量有助于在目标空间中实现均匀分布的解决方案，从而产生对决策者更具启发性的、多样性更强的解决方案集合。这种均匀分布使决策者能够更全面地了解可行解决方案的范围，有助于做出更为全面和明智的决策。

目标空间拥挤度度量公式为

\mathrm{C}{\mathrm{D}}_{j,f}={\displaystyle \sum _{i=\mathrm{1}}^m}\left(\frac{\sqrt[]{|y_{j_{\mathrm{1}},i}-y_{j_{\mathrm{2}},i}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}{\sqrt[]{|y_{\mathrm{m}\mathrm{a}\mathrm{x},i}-y_{\mathrm{m}\mathrm{i}\mathrm{n},i}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}\right),(4)

式中：CD _j，f 为二维目标空间的y_j 拥挤程度，y_{j_{\mathrm{1}},i}和y_{j_{\mathrm{2}},i}分别表示与Pareto非支配解y_j 在第i维目标空间中相邻的两个值，y_{\mathrm{m}\mathrm{a}\mathrm{x},\mathrm{i}}和y_{\mathrm{m}\mathrm{i}\mathrm{n},\mathrm{i}}表示第i维目标空间上边界解的最大值及最小值。如图2（b）所示，图中1，2，…，9分别表示2维目标空间Pareto非支配解对应的目标值y_{\mathrm{1}},y_{\mathrm{2}},\dots ,y_{\mathrm{9}}，则目标值y_{\mathrm{5}}的拥挤度度量方式如下：

CD_5,f =\frac{\sqrt[]{|y_{\mathrm{6,1}}-y_{\mathrm{4,1}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}{\sqrt[]{|y_{\mathrm{9,1}}-y_{\mathrm{1,1}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}+\frac{\sqrt[]{|y_{\mathrm{4,2}}-y_{\mathrm{6,2}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}{\sqrt[]{|y_{\mathrm{1,2}}-y_{\mathrm{9,2}}{|}^{\frac{\mathrm{1}}{\mathrm{2}}}}}。(5)

1.3 合并策略

在缺乏先验知识的背景下，确定哪些个体属于同一个Pareto前沿是一项困难的任务。然而在一般情况下，个体的邻居关系应当建立在其周围环境的基础上。因此，可以通过聚类算法将同一非支配层的解划分为多个类，同一类中的个体将来自同一个局部区域，例如采用K⁃Means算法。但是K⁃Means算法可能会导致解的分布不均匀，从而产生孤立解。因此设计增加一个合并机制，该机制的设计方法为：当分类出现极不均匀时，计算解相对较少的类与其他类的距离，如果距离小于其他类之间的平均距离，则将较少的类合并到最近的一类。以图3为例，文献［13］使用K⁃means算法决策空间的解划分为三个类，分别为（1，2，3，4）、（5）、（6，7，8，9）。在这个分类结果后进行自动化解的分类判断，计算孤立的个体5离个体4的类的距离，如果其距离小于其他几个类之间的平均距离，则将个体5合并到个体4所在的类中，得到一个新的分类结果。

2 仿真实验结果及分析

2.1 参数设置

实验使用Matlab平台，对CEC’2019中22个测试函数进行求解，其中MMF1—MMF12是包含两个优化目标的双目标优化问题，MMF13是包含3个优化目标的三目标优化问题，MMF14—MMF22是超过3个优化目标的超多目标优化问题。

2.2 仿真实验结果

仿真实验中，将所提出的算法（p-MMODE）与5个其他算法进行对比，以验证算法的有效性。其中算法MMODE_CSCD^［13］设计了一种特殊拥挤距离的方法计算决策空间及目标空间拥挤度，并引用基于距离的精英选择机制生成新个体。MO_Ring_PSO_SCD^［18］采用基于索引的环形拓扑结构来诱导稳定的小生境，从而允许识别更多的Pareto最优解，并采用特殊的拥挤距离概念作为决策和目标空间中的密度度量。TriMOEA_TAR^［15］是一种基于双存档和重组策略的多模态多目标进化算法。MO_PSO_MM^［16］是一种新的具有自组织机制的多目标粒子群优化器（SMPSO_MM）。DE_RLFR^［17］是一种基于适应度排序强化学习的差分进化算法（按照原参数）。

针对22个测试函数，每个函数独立运行30次求均值，实验中用4个评价指标以评价算法的有效性，表1给出了度量指标rPSP^［17］的统计结果（均值和方差），表2给出了度量指标rHV^［20］的统计结果（均值和方差），表3给出了度量指标IGDX^［21］的统计结果（均值和方差），表4给出了度量指标IGDF^［21］的统计结果（均值和方差）。

2.3 仿真实验结果分析

2.3.1 rPSP

实验结果如表1所示，p⁃MMODE算法与5个对比算法对22个测试函数进行测试，得到9个最小平均值，得到的最小rPSP指标数多于对比算法。TriMOEA_TAR得到7个最小平均值，这是因为TriMOEA_TAR具有多样性的档案，同时采用了聚类策略来保证目标空间的多样性。MMODE_CSCD得到5个最小平均值，MO_POS_MM得到2个最小平均值，DE_RLFRI得到1 个最小平均值。MO_Ring_PSO_SCD排名表现结果较差，可能是使用不合适特殊拥挤距离的计算方法导致rPSP性能较差。

2.3.2 rHV

实验结果如表2所示，p⁃MMODE算法与5个对比算法对22个测试函数进行测试，得到11个最小平均值，得到的最小的rHV指标数多于对比算法。TriMOEA_TAR在6个测试函数中表现较优，MMODE_CSCD得到5个最小平均值，MO_POS_MM得到3个最小平均值，DE_RLFRI得到1个最小平均值。这些算法都考虑解在目标空间中的分布。rHV可以反映所得PF的收敛性和多样性，受Pareto 前沿中解的分布影响。如果Pareto 前沿中的解分布得较均匀，且尽可能靠近参考点，那么rHV的值会相对较小。分布不均匀或者离参考点较远的解可能导致rHV增大。另一方面，当Pareto前沿收敛到真正的Pareto最优解时，rHV 往往会减小。如果Pareto前沿没有收敛，或者收敛得不好，rHV的值就可能较高。

2.3.3 IGDX

实验结果如表3所示，p⁃MMODE算法与5个对比算法对22个测试函数进行测试，得到10个最小平均值。TriMOEA_TAR中得到6个最小平均值，MMODE_CSCD得到3个最小平均值，MO_POS_MM 得到2个最小平均值，DE_RLFR得到1个最小平均值。IGDX的结果越小则表示每个获得的解都与理想Pareto解的距离相对较小。IGDX表明算法能够在决策空间中所得PS与真实PS的收敛性。如果算法得到强大的全局搜索能力，就能找到Pareto前沿中的多样性解，从而降低整体获得的Pareto前沿中第i个解到最接近理想Pareto解的距离平均值。

2.3.4 IGDF

实验结果如表4所示，p⁃MMODE算法与5个对比算法对22个测试函数进行测试，得到12个最小平均值。MMODE_CSCD得到7个最小平均值，TriMOEA_TAR和DE_RLFRI分别得到2个最小平均值，MO_POS_MM得到1个最小平均值。IGDF的结果好，意味着每个获得的解都与理想Pareto解的距离相对较小，表明在目标空间中得到的PF与真实PF之间的收敛性。

3 结论

为提高解的多样性及收敛性，为决策者提供更多、更好的解，提出了一种基于L_{\mathrm{1}/\mathrm{2}}范数的拥挤度度量及解的合并策略的多模态多目标优化算法。基于L_{\mathrm{1}/\mathrm{2}}范数及自适应权重系数的拥挤度度量，可以有效地表征解空间及目标空间的拥挤度，为算法进行环境选择提供支撑，从而提高Pareto前沿及Pareto解集的多样性和收敛性。在K‑Means聚类进行解自动分类的基础上，设计了解的合并机制，将孤立点合并到距离最近的分类中，可以有效地提高Pareto前沿均匀性。实验结果表明，本文提出的p⁃MMODE能够有效地提高算法的性能指标。

参考文献

[1] 宣贺君， 向勇， 和晓强， 等. 联合火力打击中武器目标分配问题的多目标优化模型及算法［J］. 信阳师范学院学报（自然科学版）， 2019， 32（4）： 664⁃669.

[2] XUAN Hejun， XIANG Yong， HE Xiaoqiang， et al. Multi‑objective optimization model and algorithm for weapon‑target assignment problem in joint fire strike［J］. Journal of Xinyang Normal University （Natural Science Edition）， 2019， 32（4）： 664⁃669.

[3] 姜明富， 肜丽. 多目标拆分优化网络拥塞攻击调度［J］. 信阳师范学院学报（自然科学版）， 2017， 30（2）： 316⁃320.

[4] JIANG Mingfu， RONG Li. Multi objective resolution optimization to solve network congestion attack schedule［J］. Journal of Xinyang Normal University （Natural Science Edition）， 2017， 30（2）： 316⁃320.

[5] 张涛， 张东方， 王凌云， 等. 基于改进小生境粒子群算法的主动配电网优化重构［J］. 信阳师范学院学报（自然科学版）， 2018， 31（3）： 473⁃478.

[6] ZHANG Tao， ZHANG Dongfang， WANG Lingyun， et al. Optimal reconfiguration of the active distribution network based on improved niche multi‑objective particle swarm optimization algorithm［J］. Journal of Xinyang Normal University （Natural Science Edition）， 2018， 31（3）： 473⁃478.

[7] 李明伟， 杨鑫. 基于MOP模型的ITS对城市交通运输效率的优化研究［J］. 信阳师范学院学报（自然科学版）， 2018， 31（4）： 671⁃676.

[8] LI Mingwei， YANG Xin. Research on the efficiency optimization of ITS to urban road transportation based on the MOP model［J］. Journal of Xinyang Normal University （Natural Science Edition）， 2018， 31（4）： 671⁃676.

[9] XIONG Shijie， GONG Wenyin， WANG Kai. An adaptive neighborhood⁃based speciation differential evolution for multimodal optimization［J］. Expert Systems with Applications， 2023， 211： 118571.

[10] RAUF H T， GAO Jiechao， ALMADHOR A， et al. Multi population⁃based chaotic differential evolution for multi‑modal and multi⁃objective optimization problems［J］. Applied Soft Computing， 2023， 132： 109909.

[11] ZHOU Ting， HU Zhongbo， SU Qinghua， et al. A clustering differential evolution algorithm with neighborhood⁃based dual mutation operator for multimodal multiobjective optimization［J］. Expert Systems With Applications， 2023， 216： 119438.

[12] MING Fei， GONG Wenyin， YANG Yueping， et al. Constrained multimodal multi‑objective optimization： Test problem construction and algorithm design［J］. Swarm and Evolutionary Computation， 2023， 76： 101209.

[13] 李占山， 宋志扬， 花昀峤. 一种基于自适应搜索的多模态多目标优化算法［J］. 东北大学学报（自然科学版）， 2023， 44（10）： 1408⁃1415.

[14] LI Zhanshan， SONG Zhiyang， HUA Yunqiao. A multi⁃modal multi⁃objective optimization algorithm based on adaptive search［J］. Journal of Northeastern University （Natural Science）， 2023， 44（10）： 1408⁃1415.

[15] 李浩东， 胡洁， 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用［J］. 计算机科学， 2022， 49（5）： 212⁃220.

[16] LI Haodong， HU Jie， FAN Qinqin. Multimodal multi⁃objective optimization based on parallel zoning search and its application［J］. Computer Science， 2022， 49（5）： 212⁃220.

[17] DEB K， TIWARI S. Omni‑optimizer： A procedure for single and multi‑objective optimization［C］//Evolutionary Multi‑Criterion Optimization， Guanajuato， 2005： 47⁃61.

[18] ZHANG Qingfu， LI Hui. MOEA/D： A multiobjective evolutionary algorithm based on decomposition［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712⁃731.

[19] LIANG Jing， QIAO Kangjia， YUE Caitong， et al. A clustering‑based differential evolution algorithm for solving multimodal multi⁃objective optimization problems［J］. Swarm and Evolutionary Computation， 2021， 60： 100788.

[20] ZHANG Kai， SHEN Chaonan， HE Juanjuan， et al. Knee based multi⁃modal multi⁃objective evolutionary algorithm for decision making［J］. Information Sciences， 2021， 544： 39⁃55.

[21] LIU Yiping， YEN G 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.

[22] ZHAO Hong， TANG Ling， LI Jiarui， et al. Strengthening evolution‑based differential evolution with prediction strategy for multimodal optimization and its application in multi‑robot task allocation［J］. Applied Soft Computing， 2023， 139： 110218.

[23] 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.

[24] YUE Caitong， QU Boyang， LIANG Jing. A multiobjective particle swarm optimizer using ring topology for solving multimodal multiobjective problems［J］. IEEE Transactions on Evolutionary Computation， 2018， 22（5）： 805⁃817.

[25] ZITZLER E， THIELE L， LAUMANNS M， et al. Performance assessment of multiobjective optimizers： An analysis and review［J］. IEEE Transactions on Evolutionary Computation， 2003， 7（2）： 117⁃132.

[26] 马元锋， 李昂儒， 余慧敏， 等. 基于动态拥挤距离的混合多目标免疫优化算法［J］. 计算机科学， 2018， 45（S1）： 63‑68.

[27] MA Yuanfeng， LI Angru， YU Huimin， et al. Dynamic crowding distance⁃based hybrid immune algorithm for multi‑objective optimization problem［J］. Computer Science， 2018， 45（S1）： 63⁃68.

[28] ZHOU Aimin， ZHANG Qingfu， JIN Yaochu. Approximating the set of pareto⁃optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm［J］. IEEE Transactions on Evolutionary Computation， 2009， 13（5）： 1167⁃1189.

基金资助

国家自然科学基金项目(62202366)

国家自然科学基金项目(62362056)

河南省自然科学基金项目(232300420424)

河南省本科高校研究性教学改革研究与实践项目(2022SYJXLX061)

河南省本科高校研究性教学改革研究与实践项目(2023SYJXLX073)

2023年度河南省本科高校研究性教学示范课程（数字逻辑）

信阳师范大学‘南湖学者奖励计划’青年项目

河南省研究生教育改革与质量提升工程项目(YJS2024AL104)