现实世界中许多问题都有两个或多个相互冲突的目标须要优化，这类问题被称为多目标优化问题．而多模态多目标优化(MMO)[1]问题是指对于目标空间中的同一个帕累托前沿(PF)，决策空间中至少存在两个等价的帕累托最优解集(PS)的一类特殊的多目标优化问题．求解多模态多目标优化问题须要同时考虑到问题的多目标特性和多模态特性，多模态多目标优化要求尽可能多地在决策空间中找到多个等价帕累托最优解集，并且保证在目标空间中具有良好的帕累托前沿分布．多模态多目标优化在一次运行后，提供多个最优解，可以为决策者提供决策依据．已有研究者提出了多种改进智能优化算法求解多模态多目标优化问题．Liang等[1]提出一种基于决策空间的小生境非支配排序遗传算法(DN-NSGAⅡ)，实验结果表明该算法能够尽可能多地找到多个等价帕累托最优解集，但其求解高维多模态多目标优化问题的性能不佳．Liang等[2]提出一种自组织多目标粒子群优化算法(SMPSO-MM)，该算法中的自组织映射网络能找到种群的分布结构，并在决策空间中建立邻域；精英学习策略避免早熟收敛，增强全局搜索能力；实验结果表明该算法能很好地求解多模态多目标优化问题，但因其自组织映射网络机制导致时间开销过大．头脑风暴优化(BSO)算法中的k-均值聚类是求解多模态优化问题的一种常见小生境机制[3]，能帮助定位并维持多个最优解．传统头脑风暴优化算法没有结合多目标优化问题特性对获得的解进行环境选择，不能求解多模态多目标优化问题．本研究提出了一种基于分区搜索和非支配特殊拥挤距离排序的差分头脑风暴优化算法(ZS-DEBSO-SCD)求解多模态多目标优化问题．在该算法中，分区搜索将搜索空间分为多个子空间，降低搜索难度并维持种群多样性，能帮助定位多个等价帕累托最优解．传统头脑风暴优化算法自带的k-均值聚类是常见的小生境机制，能够很好地求解多模态问题．以差分变异算子替代头脑风暴优化算法新个体生成算子以增强种群的多样性，帮助定位多个等价最优解．非支配特殊拥挤距离排序能兼顾决策空间和目标空间的多样性，并作为环境选择算子筛选最优解．为了验证所提算法的有效性，本研究选取5种求解多模态多目标问题的智能算法，与本文所提出算法在13个测试函数上进行比较与实验．实验结果表明所提出算法能够尽可能多地在决策空间找到多个等价帕累托最优解集，并且能保证在目标空间中具有良好的帕累托前沿分布．1 相关工作1.1　多目标优化问题不失一般性，最小化多目标优化问题[4-5]的数学形式可表示为min  f(x)={f1(x),f2(x),…,fm(x)}；（1）s.t.  gi(x)≤0      (i=1,2,…,k)；hj(x)=0      (j=1,2,…,p)，式中：x为n维决策向量，x=x1,x2,…,xn；f为m维目标向量；gi(x)≤0(i=1,2,…,k)为不等式约束；hj(x)=0(j=1,2,…,p)为等式约束．决策向量x的所有可能取值组成的n维空间称为决策空间．目标向量f的所有可能取值组成的m维空间称为目标空间．假设x和y是一个最小化多目标优化问题的两个可行解，∀i=1,2,…,m,fi(x)≤fi(y)且∃ j∈{1,2,…,m},fj(x)fj(y)，则称x帕累托支配y．若一个可行解不被其他任何解支配，则这个解被称为非支配解．决策空间中所有非支配解构成的集合称为帕累托最优解集．帕累托最优解集映射到目标空间中目标向量的集合称为帕累托前沿．1.2　多模态多目标优化问题及评价指标1.2.1　多模态多目标优化问题多模态多目标优化问题[1]是在多目标优化问题的基础上，对于目标空间中帕累托前沿上的同一点，决策空间中至少存在两个等价的帕累托最优解的一类问题．也就是说在多模态多目标优化问题中，目标空间中的同一个帕累托前沿，决策空间中至少存在两个等价的帕累托最优解集．如图1所示，左边坐标系代表决策空间，右边坐标系代表目标空间．两个等价的帕累托最优解集对应于目标空间的同一个帕累托前沿．多模态多目标优化问题要求尽可能多地在决策空间找到所有等价的帕累托最优解集，并且在目标空间有良好的帕累托前沿分布．10.13245/j.hust.240449.F001图1多模态多目标优化问题1.2.2　评价指标本研究选取帕累托解集近似(PSP)[6]和目标空间中的反向世代距离(IGDF)[7]作为多模态多目标优化问题的性能评价指标．帕累托解集近似(PSP)是用于衡量决策空间中算法性能的评价指标，而反向世代距离(IGDF)用于评估算法在目标空间中的性能．a. 帕累托解集近似的定义PSP=CR/IGDX; (2)IGDX(PS,PS*)=∑v∈PS*d(v,PS)/PS*；(3)CR=∏l=1nδl1/(2n)；(4)δl=1     (Vlmax=Vlmin),0     (vlmin≥Vlmax||vlmax≤Vlmin),    {[min(vlmax,Vlmax)-max(vlmin,Vlmin)]/(Vlmax-Vlmin)}2      (其他), (5)式中：CR为决策空间中获得的帕累托最优解集和真实的帕累托最优解集之间的覆盖率；IGDX为决策空间的反向世代距离；PS为获得的帕累托最优解集；PS*为真实的帕累托最优解集；d(v,PS)为v到PS中所有点之间的最小欧式距离；PS*为PS*中解的数量；n为决策空间的维度；Vlmax和Vlmin分别为PS*中第l个变量的最大值和最小值；vlmax和vlmin分别为PS中第l个变量的最大值和最小值．帕累托解集近似不但能反映获得的帕累托最优解集的收敛程度，而且能反映获得的帕累托最优解集和真实的帕累托最优解集之间的相似程度．帕累托解集近似越大，算法的性能越好．b. 反向世代距离的定义IGDF(PF,PF*)=∑v∈PF*d(v,PF)/PF*，(6)式中：PF为获得的帕累托前沿；PF*为真实的帕累托前沿；d(v,PF)为v到PF中所有点之间的最小欧式距离；PF*为PF*中解的数量．IGDF(PF,PF*)反映了帕累托前沿在目标空间中的分布情况，IGDF(PF,PF*)越小，则算法的性能越好．1.3　差分头脑风暴算法1.3.1　差分进化算法差分进化(DE)[8]算法是一种简单却非常有效的群体智能优化算法，主要包括种群初始化、变异、交叉和选择四个步骤．在变异步骤中有几种不同的突变策略，例如DE/rand/1，DE/best/1，DE/best/2，DE/rand/2．DE/rand/2算子全局搜索能力强，能帮助找到多个等价解．因此本研究选择DE/rand/2差分变异算子，其公式为xi=xr1+F[(xr2-xr3)+(xr4-xr5)]，(7)式中：xi为新生成的个体；xr1为被添加扰动的某个基础个体；xr2，xr3，xr4和xr5为从父代种群中随机挑选的个体；F为变异因子，用于缩放差分向量，通常设置为0.5．1.3.2　差分头脑风暴算法头脑风暴优化算法[9]是模拟人类解决问题时头脑风暴过程的群体智能算法．头脑风暴优化算法生成新个体来源于一个聚类或两个聚类，差分头脑风暴优化算法用DE/rand/2差分变异算子替代头脑风暴优化算法新个体生成算子以增强种群的多样性，帮助定位多个等价最优解．若新个体生成来源于一个聚类，则xr1为该聚类中心个体；若新个体生成来源于两个聚类，则xr1生成公式为xr1=Rxc1+(1-R)xc2，(8)式中：xc1为选中的一个聚类的中心个体；xc2为选中的另一个聚类的中心个体；R为0~1之间的随机数，在此设置为0.5．2 算法设计2.1　分区搜索分区搜索(ZS)[10]将一个多模态多目标优化问题在搜索空间中划分为多个子空间，有助于定位多个等价帕累托最优解，同时降低了搜索难度．分区搜索能提高决策空间中的种群多样性，更好地找到多个等价解，兼顾到多模态多目标优化问题的多模态特性．搜索空间分割步骤：对一个D维多模态多目标优化问题，随机选取决策空间中的h(1≤h≤D)个变量，每个选中的变量分割成q(q1)段．最终，整个搜索空间被划分为qh个子空间．2.2　非支配特殊拥挤距离排序非支配特殊拥挤距离排序用于寻找各个聚类中心和输出最终找到的帕累托最优解．特殊拥挤距离(SCD)[6]是基于Omni-optimizer[11]算法中拥挤距离(CD)的改进．原拥挤距离仅考虑到决策空间中的拥挤距离，而特殊拥挤距离同时考虑到决策空间和目标空间的拥挤距离，能兼顾决策空间和目标空间的多样性．特殊拥挤距离的计算公式为SiCD=max(Ci,xD,Ci,fD)   (Ci,xDCavg,xD或Ci,fDCavg,fD);min(Ci,xD,Ci,fD)    (其他), (9)式中：SiCD为第i个个体的特殊拥挤距离；Ci,xD为第i个个体在决策空间中的拥挤距离；Ci,fD为第i个个体在目标空间中的拥挤距离；Cavg,xD为决策空间中的平均拥挤距离；Cavg,fD为目标空间中的平均拥挤距离．当第i个粒子决策空间或目标空间拥挤距离大于平均拥挤距离时，其特殊拥挤距离取较大的一个，否则取较小的一个．非支配特殊拥挤距离排序将帕累托支配关系和特殊拥挤距离结合起来，用于环境选择筛选出较优个体．非支配特殊拥挤距离排序的具体执行步骤如下．步骤1 根据非支配排序[2]算法，将种群中的所有个体划分为不同等级的帕累托前沿．等级越低，个体越优．步骤2 计算同一个支配等级中所有个体的特殊拥挤距离．根据计算得到的特殊拥挤距离的大小，将同一个支配等级中所有个体按特殊拥挤距离降序排序．对于同一个支配等级的个体，特殊拥挤距离越大，排名越高．非支配特殊拥挤距离排序后，排名第一的个体是特殊拥挤距离最大的非支配个体．2.3　基于特殊拥挤距离的差分头脑风暴优化算法基于非支配特殊拥挤距离排序的差分头脑风暴优化算法(DEBSO-SCD)中k-均值聚类能同时定位多个等价帕累托最优解，兼顾到多模态多目标优化问题的多模态特性；非支配特殊拥挤距离排序作为环境选择算子筛选最优解，兼顾到多模态多目标优化问题的多目标特性；用DE/rand/2差分变异算子替代头脑风暴优化算法新个体生成算子能增强种群多样性，帮助在全局范围内找到多个最优解．DEBSO-SCD算法的流程如图2所示，具体执行步骤如下．10.13245/j.hust.240449.F002图2DEBSO-SCD算法流程图步骤1 初始化种群Pt并评估种群，初始化档案集Archive用于保存最优解；设置种群规模PopuSize、聚类数目ClusterNum和档案集容量MAX_Archive．步骤2 在决策空间中用k-均值聚类将种群分为ClusterNum个聚类．步骤3 对每个聚类进行非支配特殊拥挤距离排序，每个聚类中心为聚类进行非支配特殊拥挤距离排序之后的第一个个体，并将每个聚类中心存储到Archive中．步骤4 根据式(7)生成新个体，保留新生成个体和种群原来位置个体中的非支配解进入新一代种群中．若两个解互不支配，则随机保留一个解到新一代种群中．步骤5 将上一代种群和当前生成的新一代种群合并，对合并后的种群进行非支配特殊拥挤距离排序，保留前PopuSize个个体作为新一代种群．步骤6 若没有超出最大迭代次数，则重复执行步骤2～5；若超出最大迭代次数，对档案集Archive进行非支配特殊拥挤距离排序，将排序后Archive中的性能占优的MAX_Archive个个体作为结果输出．2.4　算法框架本研究提出的算法同时考虑到多模态多目标优化问题的多模态特性和多目标特性，也同时考虑到决策空间和目标空间的多样性．在所提算法中，首先用分区搜索进行搜索空间划分，能降低问题的复杂性并维持种群多样性；然后用DEBSO-SCD优化算法在各个子空间找到最优解；最后用非支配排序算法筛选最优解．所提算法中的分区搜索和k-均值聚类能找到并维持多个帕累托最优解，兼顾到多模态多目标优化问题的多模态特性；非支配特殊拥挤距离排序能同时考虑到决策空间和目标空间的多样性，考虑到多模态多目标优化问题的多目标特性．ZS-DEBSO-SCD算法的具体执行步骤如下．步骤1 初始化种群P和划分的子空间数目n，根据分区搜索对决策空间进行分割，得到多个子空间．步骤2 在各个子空间用DEBSO-SCD算法进行搜索．步骤3 将每个子空间找到的帕累托最优解集合并，每个子空间找到的帕累托前沿合并．步骤4 对合并后的帕累托最优解集和帕累托前沿进行非支配排序，将所有的非支配解作为最终结果输出．3 实验结果与分析3.1　测试函数本研究选择13个测试函数[6]验证所提算法的性能，如表1所示，其中第四列为同一个帕累托前沿的等价帕累托最优解集的数量，第五列为多个等价帕累托最优解集是否重叠．同一个帕累托前沿的等价帕累托最优解集数量越多，多模态多目标优化问题越难．多个等价帕累托最优解集重叠，求解的问题也越难．10.13245/j.hust.240449.T001表113个多模态多目标优化问题的测试函数测试函数目标向量维度决策向量维度帕累托最优解集数量是否重叠MMF1222否MMF2222否MMF3222是MMF4224否MMF5224否MMF6224是MMF7222否MMF8224否SYM_PART_simple229是SYM_PART_rotated229是Omni_test(n=3)2327是Omni_test(n=4)2472是Omni_test(n=5)25360是3.2　实验设置为了验证所提出的ZS-DEBSO-SCD算法性能，选取5种多模态多目标优化算法进行比较．这5种算法分别为：DN-NSGAⅡ[1]，SMPSO-MM[2]，MO-RING-PSO-SCD[6]，SS-MOPSO[12]，ZS-MO-RING-PSO-SCD[10]．所有比较算法的实验参数设置与原文献一致．实验中参数设置如下：a. 种群规模设置为800；b. 聚类数目设置为20；c. 划分子空间的数目设置为4；d. 最大迭代次数设置为200；e. 档案集容量设置为800．3.3　实验结果分析所提算法在13个测试函数上与其他5种算法进行比较．本研究选取帕累托解集近似和目标空间中的反向世代距离两种性能评价指标来比较不同算法的性能．帕累托解集近似用于衡量决策空间中的算法性能，而目标空间中的反向世代距离用于评估算法在目标空间中的性能．较大的帕累托解集近似和较小的目标空间中的反向世代距离意味着算法在决策空间和目标空间中都有不错的性能．所提出算法与其他5种算法比较所得的帕累托解集近似平均值和标准差如表2所示，可以看出ZS-DEBSO-SCD算法在MMF2，MMF3，SYM_PART_rotated，Omni_test(n=3)，Omni_test(n=4)，Omni_test(n=5)等11个测试函数上结果均好于其他5种算法．ZS-MO-RING-PSO-SCD算法在MMF1和MMF5测试函数上获得最好的实验结果．ZS-DEBSO-SCD中的搜索空间划分和差分变异算子能维持种群多样性并降低搜索难度，k-均值聚类考虑到多模态多目标优化问题的多模态特性，能帮助定位并维护多个最优解．ZS-DEBSO-SCD中的非支配特殊拥挤距离同时兼顾目标空间和决策空间的多样性，作为环境选择算子筛选最优解，兼顾到多模态多目标优化问题的多目标特性．ZS-DEBSO-SCD同时考虑多模态多目标优化问题的多模态特性和多目标特性，因此能找到更多高质量的解．10.13245/j.hust.240449.T002表2不同算法获得的帕累托解集近似平均值和标准差测试函数ZS-DEBSO- SCDDN-NSGAⅡMO-RING-PSO-SCDSMPSO-MMZS-MO-RING-PSO-SCDSS-MOPSOMMF1110.80±8.8742.09±4.2267.123.5382.34±3.36129.10±9.2161.26±0.36MMF21 343.83±122.3667.81±30.93103.99±18.85132.96±20.31208.09±4.07174.91±16.70MMF3899.61±79.5878.77±35.63140.81±16.26158.19±16.05188.14±26.11190.92±25.58MMF4256.67±9.1538.85±9.89113.96±5.26135.39±5.19215.39±15.48106.88±7.73MMF547.32±3.5314.78±1.8133.21±1.1039.22±1.0558.14±3.3432.10±1.83MMF657.97±1.2017.71±1.7536.07±1.4641.44±1.1155.85±0.9732.07±0.58MMF7186.55±6.7399.73±14.09108.9±3.21139.02±4.69185.16±0.8072.36±5.72MMF8131.70±7.3515.88±5.5347.96±1.5053.70±3.6188.78±4.7439.31±9.81SYM_PART_simple43.82±4.720.40±0.1321.67±1.5337.47±3.5434.88±0.5343.26±3.22SYM_PART_rotated100.96±7.574.48±4.7718.32±1.3014.46±0.9229.72±0.3132.41±1.12Omni_test(n=3)57.99±4.511.08±0.157.70±1.584.88±1.3212.50±3.81×10-214.50±0.80Omni_test(n=4)1.05±9.33×10-20.44±7.30×10-20.94±5.11×10-20.84±4.87×10-20.90±6.75×10-20.99±1.53×10-2Omni_test(n=5)0.56±1.13×10-20.27±8.05×10-20.49±1.72×10-20.46±1.41×10-20.50±1.27×10-20.51±1.13×10-2ZS-DEBSO-SCD与其他5种算法比较所得的目标空间中的反向世代距离平均值和标准差如表3所示，与其他5种算法相比，在MMF2，MMF3，SYM_PART_simple和Omni_test(n=3)等7个测试函数上ZS-DEBSO-SCD获得的目标空间中的反向世代距离值最小．ZS-MO-RING-PSO-SCD在MMF1和MMF5等4个测试函数上获得的目标空间中的反向世代距离值最小．SMPSO-MM在Omni_test(n=4)和Omni_test(n=5)测试函数上获得最小的目标空间中的反向世代距离值．在13个测试函数上，6种算法获得的目标空间中的反向世代距离值与其他算法获得的目标空间中的反向世代距离值差异不显著．事实上，所有算法的目标空间中的反向世代距离值都非常接近，是因为所有算法都考虑了目标空间中的分布情况．10.13245/j.hust.240449.T003表3不同算法获得的目标空间中的反向世代距离平均值和标准差测试函数ZS-DEBSO-SCDDN-NSGAⅡMO-RING-PSO-SCDSMPSO-MMZS-MO-RING-PSO-SCDSS-MOPSOMMF11.81×10-3±3.35×10-58.42×10-4±8.66×10-59.84×10-4±6.05×10-57.13×10-4±2.07×10-55.11×10-4±3.83×10-51.22×10-3±1.36×10-5MMF24.33×10-4±4.68×10-51.48×10-3±3.33×10-35.04×10-3±4.91×10-43.79×10-3±2.70×10-42.56×10-3±2.26×10-43.01×10-3±1.38×10-4MMF34.88×10-4±3.89×10-57.41×10-4±1.39×10-43.78×10-3±2.21×10-43.13×10-3±1.70×10-42.72×10-3±3.58×10-42.77×10-3±1.89×10-4MMF43.21×10-4±9.31×10-67.92×10-4±6.19×10-59.06×10-4±4.61×10-56.65×10-4±3.35×10-54.13×10-4±4.85×10-51.11×10-3±1.02×10-4MMF52.17×10-3±1.72×10-48.06×10-4±3.80×10-59.50×10-4±3.69×10-57.26×10-4±2.31×10-54.98×10-4±4.24×10-51.11×10-3±7.63×10-5MMF61.56×10-3±1.71×10-48.07×10-4±3.87×10-59.17×10-4±2.96×10-56.72×10-4±2.22×10-54.39×10-4±1.76×10-51.19×10-3±7.66×10-5MMF76.63×10-4±9.03×10-59.97×10-4±4.06×10-59.01×10-4±3.17×10-56.77×10-4±2.14×10-54.14×10-4±6.31×10-52.39×10-3±2.31×10-4MMF83.63×10-4±1.70×10-58.95×10-4±5.45×10-51.28×10-3±4.26×10-59.72×10-4±3.97×10-56.31×10-4±2.33×10-51.01×10-3±2.63×10-5SYM_PART_simple1.15×10-3±1.55×10-43.18×10-3±5.27×10-49.64×10-3±1.48×10-35.12×10-3±7.36×10-46.22×10-3±5.11×10-44.56×10-3±5.24×10-4SYM_PART_rotated1.13×10-3±1.65×10-43.93×10-3±5.37×10-41.16×10-2±1.72×10-31.38×10-2±1.63×10-37.41×10-3±5.32×10-44.42×10-3±2.61×10-5Omni_test(n=3)1.15×10-3±1.27×10-52.93×10-3±1.05×10-41.72×10-2±1.16×10-39.78×10-1±1.76×10-30.98±6.31×10-40.99±1.00×10-3Omni_test(n=4)1.99±1.26×10-31.99±6.72×10-41.93±8.10×10-31.91±1.01×10-21.95±8.20×10-31.96±2.58×10-3Omni_test(n=5)2.93±7.72×10-32.99±1.04×10-32.83±1.94×10-22.76±2.20×10-22.87±2.48×10-22.91±3.12×10-3ZS-DEBSO-SCD与其他5种算法在测试函数Omni_test(n=3)上所获得的帕累托最优解集和帕累托前沿分别如图3和图4所示．ZS-DEBSO-SCD与其他5种算法找到的帕累托前沿结果无显著区别，这是因为所有的算法都考虑了目标空间的分布．ZS-DEBSO-SCD获得的等价帕累托最优解集数量多于其他算法获得的帕累托最优解集的数量．ZS-DEBSO-SCD获得的帕累托最优解集也优于其他算法获得的帕累托最优解集．此外，DN-NSGAⅡ，MO-RING-PSO-SCD和SMPSO-MM获得的等价帕累托最优解集较少．10.13245/j.hust.240449.F003图3在Omni_test(n=3)测试函数上，不同算法获得的帕累托最优解集10.13245/j.hust.240449.F004图4在Omni_test(n=3)测试函数上，不同算法获得的帕累托前沿在Omni_test(n=3)测试函数上，与其他5种算法相比，ZS-DEBSO-SCD获得的帕累托最优解集更全，尽可能多地获得了等价帕累托最优解集．ZS-DEBSO-SCD中的分区搜索和k-均值聚类帮助定位多个最优解，特殊拥挤距离兼顾决策空间和目标空间的多样性，能同时考虑到多模态多目标问题的多模态特性和多目标特性，因此能获得更多高质量的多个等价最优解．4 结语为了求解多模态多目标优化问题，本研究提出了一种基于分区搜索和非支配特殊拥挤距离排序的差分头脑风暴优化算法(ZS-DEBSO-SCD)．首先用分区搜索将搜索空间划分为多个子空间以降低搜索难度，然后在每个子空间用DEBSO-SCD算法求解，最终用非支配排序筛选最优解．为验证所提出算法的有效性，选择13个测试函数与其他5种求解多模态多目标优化问题的智能算法进行比较与实验．结果表明所提出算法能够尽可能多地在决策空间找到多个等价帕累托最优解集，并且能保证在目标空间中具有良好的帕累托前沿分布．本研究提出的算法能求解多模态多目标问题，在所选择的大多数测试问题上，性能优于其他5种算法，说明ZS-DEBSO-SCD算法同时考虑到多模态多目标优化问题的多模态特性和多目标特性．然而随着多模态多目标问题的不断进展，具有高维特征和具有不规则的帕累托前沿的多模态多目标问题将会增加问题的求解难度，下一步将从算法和问题两个方面改进多模态多目标优化问题的求解性能．