·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 optimiza￾tion 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 卷