·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 op￾timization 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 中解个数的比值，也称为解的覆盖率；IG￾Dx 表示决策空间中的反向世代距离[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 卷