0 引言

实际应用中存在大量多模态优化问题, 传统意义上的多模态优化是指多模态单目标优化(即多峰优化)^[1-5]. 对多模态单目标优化的研究由来已久, 解决此类问题最常用的方法是小生境策略^{[3, 6]}, 该方法使得进化在局部范围内进行, 防止算法过早收敛到某一个区域.

许多优化问题的目标不止一个, 而是有两个或两个以上的待优化目标, 改进其中一个目标可能会造成其他目标的恶化, 这些问题被称作多目标优化问题^[7-12]. 一般情况下, 不可能同时找到所有目标的最优值. 常用于解决多目标优化问题的方法是找到不同目标之间的最优权衡解集. 该解集分布在帕累托前沿上, 为决策者提供更多选择. 由于解的优劣都根据目标值(即在目标空间)进行评估, 决策空间的分布特性没有受到太多关注. 早期研究的多目标优化问题都被默认为单模态多目标优化问题, 即问题只有一个帕累托最优解集.

事实上, 多目标优化中也存在多模态情形, 即在某些多目标优化问题中存在多个全局或局部帕累托最优解集的情况, 这些存在多模态情形的多目标优化问题被称为多模态多目标优化问题^[13-16]. 图 1给出了一个简单的多模态多目标优化实例^[17]. 该实例是特征选择优化问题^[18-19], 有两个待优化目标: 1) 选择特征的个数; 2) 分类错误率. 图 1中虚线表示问题的帕累托前沿, 如图所示, 当选择一个特征时, 有3个不同的选择方案{$ F_1 $}、{$ F_2 $}或{$ F_4 $}. 3种方案的两个目标值都相同, 即选择$ F_1 $、$ F_2 $或$ F_4 $, 选择特征的个数均为1, 错误率均为0.8. 如果选择两个特征, 则选择{$ F_2 $, $ F_3 $}或{$ F_1 $, $ F_4 $}的错误率均为0.4. 该特征选择问题的帕累托最优解集有多种组合(只考虑选择特征个数为1或者2的组合就有$ 2 \times 3 = 6 $种), 即它有多个帕累托前沿, 因此该问题属于多模态多目标优化问题. 在该问题中, 一组帕累托最优解集不能很好地满足决策者的需求. 因为提取$ F_1 $和$ F_4 $需要花费的时间、人力、物力等资源较多, 而$ F_2 $和$ F_3 $都比较容易提取, 如果选择一个特征时算法找到的最优特征是$ F_1 $, 选择两个特征时算法找到的最优特征组合是{$ F_1 $, $ F_4 $}, 则决策者不得不消耗大量的资源去提取$ F_1 $和$ F_4 $. 如果选择一个特征时算法找到的最优特征是$ F_1 $、$ F_2 $或$ F_4 $, 选择两个特征时算法找到的最优特征组合是{$ F_1 $, $ F_4 $}或{$ F_2 $, $ F_3 $}, 则决策者可以选择$ F_2 $(需要一个特征时)或{$ F_2 $, $ F_3 $}(需要两个特征时), 这样既能满足较低的错误率, 又能节约资源. 因为现有多模态多目标优化方法是实数空间的连续优化方法, 所以本文只对连续多模态多目标优化方法进行了综述.

多模态多目标优化方法需要保留多个帕累托解集, 其意义^[3]在于: 1) 多个解集可以满足不同决策者的需求; 2) 多个解集可以揭示问题的潜在特性; 3) 快速由一个解集转化到另一个解集可以帮助解决动态优化问题; 4) 提供多个解集可以提高找到鲁棒解的可能性.

传统多目标优化算法难以找到多个帕累托最优解集, 因为传统多目标优化算法极少利用解集在决策空间的分布特性, 它们侧重于提高目标空间的多样性、延展性和收敛性. 为了找到多个帕累托最优解, 需要设计特殊的搜索机制和环境选择策略.

本文对解决多模态多目标优化问题的相关文献进行分析总结, 介绍多模态多目标优化问题的特点和难点, 分析现有解决方法并总结其各自的优缺点, 介绍关于多模态多目标优化的测试问题和评价指标, 希望能给该领域的研究人员提供参考.

1 相关定义

不失一般性, 最小化多目标优化问题定义如下:

$ \begin{align} &\min\, {{\mathit{\boldsymbol{f}}}} ({{\mathit{\boldsymbol{x}}}} ) = [{f_1}({{\mathit{\boldsymbol{x}}}} ), {f_2}({{\mathit{\boldsymbol{x}}}} ), \ldots , {f_m}({{\mathit{\boldsymbol{x}}}} )].\\ &{\rm \; s.t.}\; {g_i}({{\mathit{\boldsymbol{x}}}} ) \leqslant 0, \; i = 1, 2, \ldots, k;\\ &\; \; \; \; \; \; \; {h_j}({{\mathit{\boldsymbol{x}}}} ) = 0, \; j = 1, 2, \ldots, p. \end{align} $

(1)

其中: $ m $为待优化目标的数目, $ {{\mathit{\boldsymbol{x}}}} = ({x_1}{, x_2}, \ldots , {x_n}) $为n维决策变量, $ {g_i}({{\mathit{\boldsymbol{x}}}} ) \leqslant 0(i = 1, 2, \ldots, k) $为k个不等式约束, $ {h_j}({{\mathit{\boldsymbol{x}}}} ) = 0(j = 1, 2, \ldots , p) $为p个等式约束. 同时满足上述等式和不等式约束的空间$ {{\mathit{\boldsymbol{R}}}}^n $称为决策空间; 决策空间通过目标函数映射出的空间$ {{\mathit{\boldsymbol{R}}}}^m $称为目标空间.

定义1(支配关系)^[20]   给定一个多目标优化问题min $ \, {{\mathit{\boldsymbol{f}}}}({{\mathit{\boldsymbol{x}}}} ) = [ {{f_1}({{\mathit{\boldsymbol{x}}}} ), {f_2}({{\mathit{\boldsymbol{x}}}} ), \ldots , {f_m}({{\mathit{\boldsymbol{x}}}} )} ] $, 其中m为目标个数. 假设$ {x}_1 $和$ {x}_2 $是该优化问题的两个可行解, 当且仅当$ \forall i = 1, 2, \ldots , m, {f_i}({x}_1 ) \leqslant {f_i}({x}_2)\bigwedge \exists j \in [1, m], {f_j}({x}_1 ) < {f_j}({x}_2 ) $时, 称$ {x}_1 $支配$ {x}_2 $.

如果某个解不被其他任何解支配, 则该解称为非支配解. 所有非支配解组成帕累托最优解集(Pareto optimal set, PS); PS映射到目标空间的集合称为帕累托前沿(Pareto front, PF).

定义2(多模态多目标优化)^[21-22]   如果一个多目标优化问题满足以下两个条件之一, 则称该问题为多模态多目标优化问题:

1) 问题至少有一个局部帕累托最优解;

2) 问题至少有两个等效全局帕累托最优解, 它们对应PF上同一点.

局部帕累托最优解是指不被任何邻域解支配的解; 全局帕累托最优解是指不被可行域内任何解支配的解. 为了直观地展示多模态多目标优化问题的特点, 图 2给出多模态多目标优化问题示意图. 如图 2所示, 左侧是决策空间, 右侧是目标空间, 决策空间两条曲线PS$ _1 $和PS$ _2 $代表两个全局帕累托最优解集, 它们映射到目标空间同一个全局帕累托前沿PF. 决策空间的圆点$ A_1 $和$ A_2 $代表两个解集中的可行解, 它们都映射到目标空间的圆点$ A $. 虽然$ A_1 $和$ A_2 $在决策空间的距离较大, 但是它们在目标空间的距离为零. 这是多模态多目标优化问题的一个特点, 也是求解的难点. 下一节会详细介绍此类问题的难点, 并综述各种求解算法.

2 多模态多目标优化算法

在智能搜索策略中存在两种关键操作: 探索(explore)和开采(exploit). 其中探索能力影响收敛速度, 开采能力影响搜索到解集的多样性. 一般而言, 探索能力越强, 收敛速度越快, 但是容易导致早熟收敛; 开采能力越强, 搜索到解的多样性越好, 但是会减缓收敛速度. 优秀的搜索策略需要权衡两种能力的强弱, 在提高收敛速度的同时保证解的多样性. 在多模态多目标优化中也存在与这两种能力相关的难点.

求解多模态多目标优化问题的难点主要有两个: 1) 在搜索过程中如何提高算法的搜索能力, 使得算法能找到尽可能多的帕累托最优解; 2) 在环境选择中如何保留目标空间距离较小而决策空间距离较大的解, 同时保证决策空间和目标空间的多样性.

难点1)解释: 在解决多模态多目标优化问题时, 许多算法容易过早收敛到某一个区域. 如图 2所示, 算法极易收敛到PS$ _1 $或PS$ _2 $中的某一个邻域, 比如算法已经搜索到PS$ _1 $, 那么它就已经找到了一个完整的PF, 但是决策空间另外一个最优解集PS$ _2 $还未找到, 这极可能造成优良解的丢失. 若要提高算法的搜索能力, 使得算法能找到尽可能多的帕累托最优解, 则应当控制信息传递速度, 防止算法过快收敛到某个局部区域.

难点2)解释: 如图 2所示, 决策空间两个点$ A_1 $和$ A_2 $映射到目标空间同一个点$ A $, 如果算法已经找到点$ A_1 $和$ A' $, 且$ A' $正在逼近$ A_2 $, 则$ A' $点很可能在移动到$ A_2 $前被删除, 造成算法难以同时保留$ A_1 $和$ {A'} $, 因为$ A_1 $和$ {{A'}} $在目标空间的距离$ d_2 $非常小. 但是由图中可以看出, 虽然$ d_2 $非常小, 但是在决策空间的距离$ d_1 $相对较大, 因此若要同时保留$ A_1 $和$ {{A'}} $, 则不能单纯以目标空间拥挤度距离衡量其优劣, 还应考虑决策空间的分布情况.

为了解决以上两大难点, 研究者提出了不同的解决方法, 因为多模态多目标优化问题解的数量较多, 且问题的特性较复杂, 演化算法具有求解此类问题的独特优势, 所以本文只对多模态多目标演化算法进行介绍, 这些方法可以分为提高决策空间多样性的方法和提高搜索能力的方法.

2.1 提高搜索能力的方法

要解决多模态多目标优化问题, 需要提高算法的搜索能力, 使算法能求得尽可能多的帕累托最优解.下面介绍通过提高搜索能力解决多模态多目标优化问题的算法.

DN-NSGAII^[13]在选取父代时, 采用决策空间小生境的方法, 使种群在不同小生境内搜索不同的帕累托最优解, 提高算法的搜索能力. 该算法的优点是促使种群在决策空间多个区域并行进化, 防止过早收敛到某一个区域; 缺点是只使用了决策空间拥挤度距离, 没有考虑目标空间的分布情况, 造成算法得到的帕累托前沿多样性较差, 另一个缺点是引入了小生境参数.

为避免引入小生境参数, MO_Ring_PSO_SCD^[14]以环形拓扑结构约束种群信息的传递速度, 使种群在搜索过程中逐渐形成稳定的小生境, 防止算法过早收敛到某一个区域, 使其能够找到更多的帕累托最优解. 此外, 该算法使用特殊拥挤距离(SCD)兼顾决策和目标空间的多样性, 克服了DN-NSGAII的缺点. 该算法的优点是: 在不引入任何小生境参数的前提下, 促使决策空间形成稳定的小生境, 增强算法的搜索能力, 改善环境选择机制, 同时提高决策空间和目标空间的多样性. 此外, 在选取父代时, 采用二元锦标赛方法, 只有决策空间距离相近的粒子才进行相互竞争, 这种机制可以防止算法过早收敛到某一个区域, 缺点是在某些PS形状复杂的问题上性能不好, 种群的分布不够均匀.

MO_Ring_CSO_SCD^[23]也采用环形拓扑结构和特殊拥挤度距离提高算法的搜索能力并改善解的多样性, 由于competitive swarm optimization(CSO)适用于大规模优化问题, 该算法在低维问题上优越性不明显.

为了进一步提高解集在决策空间的多样性, MMODE^[24]采用预选解机制, 选择非支配排序和拥挤度排序较好的解作为父本产生子代. 在产生子代过程中, 如果子代超出边界, 不是直接将它们舍去或将它们直接放在边界上, 而是采用特殊的边界处理机制, 使得出界的子代也有机会继续进化, 这种机制有效地提高了算法的搜索能力. 该算法的优点是充分利用已有资源搜索决策空间, 防止出现粒子在边界聚集的现象; 缺点是求得的解集在目标空间的分布性欠佳.

MO_PSO_MM^[25]和MMOPIO^[26]都采用自组织映射方法将原始决策空间转化到映射空间, 根据粒子在映射空间的分布确定其邻域关系, 使种群在映射空间邻域内进化, 提高算法的搜索能力. 这两种算法的优点是可以将高维决策空间映射到一维或二维空间, 便于可视化粒子的邻域关系; 缺点是映射机理不清晰, 随机性较大.

使用存档机制, 充分挖掘种群在决策空间的信息, 也是求解多模态多目标优化的一种有效方法. TriMOEA-TA & R^[22]首先通过决策变量分析技术检测出与收敛相关的决策变量, 并使用收敛性存档优化这些变量, 提高目标空间的收敛性. 为了提高多样性, 本文采用多样性存档, 旨在维持目标空间和剩余决策子空间的多样性(即从总搜索空间中移除收敛相关决策子空间). 最后, 通过重新组合选出两种存档中的优秀解, 构建具有良好整体性能的最终解集. 该算法的优点是使用两个外部存档, 分别负责改善多样性和收敛性, 且兼顾决策空间和目标空间的多样性; 缺点是当不同帕累托最优解之间的距离相差较大时, 算法性能下降, 且在产生参考向量时引入了新的参数.

DNEA-L^[27]通过改进DNEA^[28]得到, 它使用多前沿存档存储多个帕累托前沿, 在提高算法性能的同时保留全局最优和局部最优解的能力, 环境选择中采用double-sharing的适应度分享函数值作为筛选指标, 同时改善决策空间和目标空间的多样性. 该算法的优点是能够同时保留全局和局部最优解集, 得到决策空间和目标空间分布性较好的解; 缺点是引入了多个参数, 如适应度值分享半径, 需要保留非支配前沿的个数.

MOEA/D-AD^[29]将多模态多目标优化问题分解成多个子问题, 每个子问题由一个或几个个体进行寻优, 提高了解集在决策空间的多样性. 该方法的优点是可以保留目标空间距离小但决策空间距离大的解; 缺点是引入了确定邻域大小的参数.

强化学习或机器学习与进化算法结合是求解多模态多目标优化问题的另一途径. DE-RLFR^[30]将强化学习机制融入差分进化算法解决多模态多目标优化问题. 首先根据个体的适应度值划分不同的等级, 不同等级有不同的进化方法, 根据进化后子代与父代等级高低设置奖励级别. 该方法的优点是进化过程向邻近最优等级逐步进行, 保证了收敛的稳定性; 缺点是引入了等级划分参数, 且在高目标优化中奖励情况较复杂. SS-MOPSO^[31]采用自组织Speciation策略将种群分成不同的子种群, 不同种群之间不存在重叠, 促使算法找到更多帕累托解. MMO-Clustering-PSO^[32]通过聚类将整个种群分成多个子种群, 子种群内的粒子根据自己的全局最优更新位置和速度, 不同种群之间使用环形拓扑结构进行信息传递. 该方法的优点是搜索能力较强, 能找到较多的帕累托最优解; 缺点在于不同问题中聚类数目难以设定, 且参数对算法性能影响较大.

以上方法通过提高搜索能力防止算法陷入局部区域, 对解决多模态多目标优化问题有很大帮助. 然而, 只有搜索机制是不够的, 还需要有较好的环境选择机制来提高决策空间的多样性, 保留决策空间距离大但目标空间距离小的解, 进而更好地解决多模态多目标优化问题.

2.2 提高决策空间多样性的方法

上述提高搜索能力的方法可以使算法找到更多的帕累托解, 此外, 多模态多目标优化问题需要特殊的环境选择方法才能使目标空间距离相近而决策空间距离较远的帕累托最优解(如图 2中$ A_1 $和$ A_2 $)都被保留下来. 以下是提高决策空间多样性的相关工作.

Deb等^[15]提出了Omni-optimizer算法, 在该算法的环境选择机制中, 根据非支配排序、决策空间拥挤度距离和目标空间拥挤度距离3个指标对个体进行排序. 其中非支配排序方法如图 3所示, 帕累托最前沿的点集为第1前沿, 帕累托次前沿的点集为第2前沿, 以此类推. 决策空间拥挤度距离的计算如图 4所示. 以二维决策空间问题为例, 计算拥挤度距离在$ x_1 $方向的分量时, 首先根据$ x_1 $的值由小到大排序, 粒子的拥挤度距离等于该粒子前后邻居相应决策变量的差值. 边界粒子(图 4中第5个点)的拥挤度距离等于它与最近邻居相应决策变量差值的二倍. 目标空间拥挤度距离计算方式与决策空间类似, 只有边界点的处理不同, 决策空间边界点拥挤度距离为与最近邻居差值的二倍, 而目标空间边界点拥挤度距离取无穷大. 最后根据条件选择两个空间的拥挤距离之一分配给对应粒子. 条件选择后的拥挤度距离能反映粒子决策空间和目标空间邻域的拥挤度, 进而同时保证决策空间和目标空间的多样性. 之后, 许多方法(如MO_Ring_PSO_SCD^[14]、MO_PSO_MM^[25]等)都采用了兼顾决策和目标空间拥挤度距离的环境选择机制.

Liang等^[13]提出一种决策空间小生境策略, 能在环境选择中帮助保留更多帕累托最优解. 该策略首先根据非支配关系将种群分成不同的帕累托前沿, 然后依据Omni-optimizer中决策空间拥挤度距离将同一个前沿内的粒子进行排序. Yan等^[33]提出PEN-MOBA算法, 在决策空间引入小生境策略, 增加了局部最优外部存档以提高决策空间的多样性, 但是这两种选择机制均没有考虑目标空间的分布情况.

为了兼顾决策空间和目标空间的分布情况, Yue等^[14]提出一种特殊拥挤度距离. 在环境选择中, 首先根据非支配关系排列出不同的前沿, 同一前沿中的粒子再根据特殊拥挤度距离由大到小排序, 特殊拥挤度距离计算如下:

$ \begin{align} {\rm SCD}_i = \begin{cases} {\rm max} ({\rm CD}{_{i, x}}, {\rm CD}{_{i, f}}), \\ \; \; \; \; {\rm CD}{_{i, x}} > {\rm CD}{_{{\rm avg}, x}}\; {\rm or}\; {\rm CD}{_{i, f}} > {\rm CD}{_{{\rm avg}, f}};\\ {\rm min} ({\rm CD}{_{i, x}}, \; {\rm CD}{_{i, f}}), \; {\rm otherwise}. \end{cases} \end{align} $

(2)

其中: SCD$ _i $为第$ i $个粒子的特殊拥挤度距离, CD$ _{i, x} $为第$ i $个粒子在决策空间的拥挤度距离, CD$ _{i, f} $为第$ i $个粒子在目标空间的拥挤度距离, CD$ _{{\rm avg}, x} $为决策空间的平均拥挤度距离, CD$ _{{\rm avg}, f} $为目标空间的平均拥挤度距离. 由式(2)可见, 当第$ i $个粒子的决策空间或目标空间拥挤度距离大于平均水平时, SCD取较大的一个, 否则取较小的一个. 图 2中$ A_1 $和$ {{A'}} $的特殊拥挤度距离取决策空间的值, 因此在环境选择中二者被同时保留的可能性增大. 环境选择中使用非支配关系和特殊拥挤度距离排序可以提高决策空间和目标空间的多样性. 文献[24-26]也采用了这种环境选择机制, 均取得了较好的效果.

将多样性指标嵌入目标函数是改善种群多样性的一种有效方法. Liu等^[27]设计了double-sharing函数, 该函数将决策空间和目标空间适应度值分享后组合到一个函数中, 并将组合后的函数值用于环境选择标准, 以达到同时改善决策空间和目标空间多样性的目的.

大部分小生境方法都基于欧氏距离确定邻域关系, 但在较高维空间欧氏距离确定的邻域会出现偏差. Shi等^[34]提出了MMOEA-GD算法, 该算法在决策空间使用谐波平均距离(harmonic average distance)衡量种群在决策空间的邻域关系, 只允许粒子与决策空间邻域内的个体进行信息交互, 从而提高种群在决策空间的多样性.

也有学者使用聚类方法辅助改善种群的多样性. Liu等^[22]提出了一种基于小生境的清除策略, 该策略首先根据一组分布均匀的参考向量把种群进行聚类, 以改善目标空间的均匀性和延展性, 对每个子类采用小生境方法促进决策空间的多样性. Maity等^[35]提出了MM-NAEMO算法, 它由NAEMO改进而来, 改进后的环境选择中使用了基于混合高斯模型的聚类算法, 先将种群聚成不同的子类, 然后在每个子类中挑选优秀个体, 以改善种群的多样性.

上述算法的信息总结见表 1. 表中给出了各种算法的基本框架和有效机制. 这些算法的代码可以在多模态多目标优化问题相关研究主页下载(http://www5.zzu.edu.cn/cilab/MMO.htm).

2.3 典型算法举例

第2.1和2.2节从提高算法搜索能力和改善决策空间多样性两个方面对相关工作进行了介绍, 为了说明求解此类问题的整体流程, 本节给出典型算法的求解过程.

使用环形拓扑结构和特殊拥挤距离的多目标粒子群优化算法(MO_Ring_PSO_SCD)^[14]是求解多模态多目标优化问题的典型算法, 算法同时具有提高搜索能力以及改善决策空间多样性机制, 因此选择它来说明求解多模态多目标优化问题的整体流程.

MO_Ring_PSO_SCD的整体流程如算法1所示. 首先初始化种群P、个体最优存档PBA和邻域最优存档NBA (1~6行); 然后根据非支配关系和特殊拥挤距离对PBA和NBA中的个体进行优劣排序(第11行、12行), 按照非支配排序由前到后, 特殊拥挤距离由大到小进行排序; 选择排序后PBA和NBA中的第1个个体作为当前个体的个体最优和邻域最优, 并根据粒子群优化算法个体位置和速度的更新公式对当前粒子进行更新(14~19行); 将更新后的粒子放入个体最优存档, 删除存档中被更新后个体所支配的所有个体(21行); 使用当前个体最优存档、前一个体最优存档以及后一个体最优存档组合成暂时邻域最优存档(temp_NBA{i}), 从暂时邻域最优存档中选出所有非支配个体作为更新后的邻域最优存档(24~33行); 循环上述更新过程直至满足停止迭代条件; 最后输出NBA中的非支配解集.

算法1    MO_Ring_PSO_SCD.

1 //初始化种群P

2 evaluation(P)

3 //初始化个体最优和邻域最优存档

4 $ {\rm PBA} = P $

5 $ {\rm NBA} = {\rm PBA} $

6 while generation $ < $ maxgenerations do

7 for $ i = 1 $: particlenumber

8 //对PBA和NBA中的个体进行排序

9 sorted_PBA{i} = non-dominated_scd_sort (PBA{i})

10 sorted_NBA{i} $ = $

     non $ - $ dominated_scd_sort(NBA{i})

11 //选择pbest和nbest

12 pbest$ _i\; \leftarrow $ sorted_PBA{i}中的第1个

13 nbest$ _i\; \leftarrow $ sorted_NBA{i}中的第1个

14 //更新种群P

15 $ P_i(t+1) = P_i(t) +v_i(t + 1) $

16 $ v_i(t + 1) = Wv_i(t) + C_1r_1({\rm pbest}_i - P_i(t) )+ $

                        $ C_2r_2({\rm nbest}_i - P_i(t)) $

17 evaluation$ (P_i(t+1)) $

18 //更新PBA

19 将$ P_i(t+1) $放入PBA$ \{i\} $并删除被$ P_i(t+1) $支配的个体

20 end for

21更新NBA

22 for $ i = 1 $: particlenumber

23 if $ i = 1 $

24 temp_NBA$ \{i\} = $

$ [ {\rm PBA} \{ {\rm particlenumber} \}, {\rm PBA} \{1\}, {\rm PBA}] $

25 else if $ i = {\rm particlenumber} $

26 temp_NBA{i}=

    $ [ {\rm PBA}\{ {\rm particlenumber} -1\} $,

    $ {\rm PBA}\{ {\rm particlenumber} \}, {\rm PBA}\{1\}] $

27 else

28 temp_NBA$ \{i\} = $

    $ [{\rm PBA}\{i-1\}, {\rm PBA}\{i\}, {\rm PBA}\{{i}+1\}] $

29 end if

30 NBA$ \{{i}\} = {\rm non-dominated\; particles\; in} $

                      temp_NBA{i}

31 end for

32 end while

33 输出: NBA中的非支配解集.

经过分析发现, $ {\rm MO_Ring_PSO_SCD} $算法针对多模态多目标优化问题的有效处理机制有两个: 1) 使用环形拓扑结构; 2) 使用特殊拥挤距离. 环形拓扑结构将整个种群分成多个小生境, 不同小生境之间不存在直接竞争, 大大提高了算法找到多个最优解的能力; 特殊拥挤距离兼顾决策空间和目标空间拥挤距离, 使得算法能够保留目标空间拥挤距离小但决策空间拥挤距离大的解. 关于两种机制的具体描述及有效性验证参见文献[14].

通过对各种多模态多目标进化算法进行分析总结发现, 此类算法的一般框架如图 5所示, 它与一般进化优化算法的总体流程一致. 首先, 初始化一个种群, 种群中不同个体根据环境变化或其他个体分享的信息不断调整进化方向; 然后, 根据预定义的算子对种群进行筛选, 如此迭代式地对个体进行调整筛选, 直至满足预设的终止条件. 多模态多目标优化方法的独特之处在于: 进化过程中需加入限制信息传递范围的策略, 防止种群过早收敛到局部区域; 在筛选过程中需要兼顾决策和目标空间的多样性, 使得多模态解能在环境选择中生存下来.

3 测试函数和评价指标

为了公平、公开、合理地比较不同多模态多目标优化算法, 学者们提出不同的测试函数集和能够衡量算法性能优劣的评价指标来评价算法的性能.

3.1 测试函数

标准测试函数集可以用来公平测试不同算法的性能, 因为测试问题的各项信息都已知, 所以可以避免实际问题中不确定因素造成的影响, 这对相关领域的研究具有促进作用. 因此, 多模态多目标优化也需要标准测试函数, 这些函数与普通多目标测试函数不同, 它们具有多个全局或局部PS.

Deb^[36]最早提到了多目标优化问题中的多模态情形, 并给出了Omni-test测试函数, 该函数决策变量的维度和等效PS的个数都可扩展, 但是目标空间的维度不可扩展. Rudolph等^[37]提出了SYM-PART测试函数, 且在函数中加入了旋转和扭曲操作, 使不同决策变量之间存在相关性. Preuss等^[38]提出了TWO-ON-ONE测试函数, 用于分析传统进化多目标优化算法在多模态多目标优化问题上的性能. Ishibuchi等^[39]提出了Polygon-based problem, 用于在决策空间直观地显示种群的多样性, 但是这些函数决策变量的维度是固定的. 随后, Ishibuchi等^[40]和Masuda等^[41]提出了决策变量具有可扩展性的多模态多目标测试函数. 此外, Liang等^[13]通过平移和对称操作复制多个PS设计了两个多模态多目标测试函数, 函数较为简单. 随后, Yue等^[14]设计了6个较为复杂的测试函数, 函数具有不同形状的PS和PF, 但是决策空间和目标空间的维度不可扩展, 性质较单一. Liang等^[24]设计了PF和PS形状复杂的测试函数, 但是函数决策空间和目标空间的维度仍然不可扩展. Liu等^[22]设计了决策空间和目标空间都可扩展的测试函数MMMOP, 但是函数没有局部和全局PS共存的情况. Yue等^[21]设计了较为复杂的多模态多目标测试问题MMF suite, 包括局部PS和全局PS共存、形状复杂的PS和PF、决策变量个数和目标个数可调等特征, 并给出了多模态多目标测试函数的设计方法和设计框架, 函数的可扩展性较好.

多模态多目标测试函数期望具有的性质包括: 1) 同时具有局部和全局PS; 2) PS的个数可调节; 3) PS的形状不同; 4) PS和PF已知; 5) 决策变量和目标个数可调. 一般而言, 同时具有局部和全局PS的问题比只有全局PS的问题难以解决, 因为局部PS是陷阱, 搜索能力较弱的算法容易陷入局部PS. 另外, 决策空间的维度越高, 搜索空间越大, 问题的求解难度越大; 目标的个数越多, 算法的收敛力度越小, 问题求解难度也会越大. 测试函数集既要包括简单的测试函数, 又要包括复杂的测试函数, 这样才能评价不同算法的优劣. 为了方便研究者进行选择, 表 2对文献中已有多模态多目标优化测试函数的性质进行了总结. 其中: $ \surd $表示测试函数集有满足对应性质的函数, $ \times $表示没有满足对应性质的函数, $ \surd/\times $表示既有满足对应性质的函数也有不满足对应性质的函数. 如MMF suite中既有决策变量个数可调的也有不可调的函数, 因此对应“决策变量个数是否可调”的性质为$ \surd/\times $. 表中所列Omni-test、SYM-PART和TWO- ON-ONE测试函数是单个测试函数, 因为早期文献中对多模态多目标优化的研究较少, 所以测试函数性质单一; 后面几行所列测试函数均为测试函数集, 每个集合包含多个测试函数, 它们的性质也有所差异. 如果研究者需要测试算法求解超多目标(3个以上)多模态优化问题的性能, 则建议选择Polygon-based problem^[39]或MMMOP^[22], 因为这两个测试函数集包含目标个数大于3的测试函数, 且它们的PS几何形状为区域块, 这种测试函数的决策空间只有二维, PS是多边形内部区域, 通过观察算法求得解对多边形的覆盖情况即可了解算法的性能, 所以这些函数可以实现超多目标优化的可视化. 如果研究者需要测试算法求解具有不同形状PF问题的性能, 则建议选择MMF suite, 因为该测试函数集包含多种集合形状的PF, 且测试函数的其他性质也较为丰富.

3.2 评价指标

评价指标可以将不同算法的性能量化, 在算法评估和对比中起着非常重要的作用. 常用的多目标算法的评价指标包括inverted generational distance (IGD^[42])、HyperVolume(HV^[43])等, 它们只能衡量种群在目标空间的分布情况, 对于多模态多目标优化问题而言, 即使目标空间的分布性能良好, 决策空间的性质也可能很差. 因此需要新的评价指标对不同的多模态多目标算法进行评价.

多模态多目标优化算法评价指标需要具有以下性质: 1) 能反映决策空间的多样性、收敛性、覆盖率; 2) 能反映目标空间的多样性、收敛性、覆盖率; 3) 有合理的量化范围; 4) 能用来比较不同算法解决多模态多目标优化问题的能力. 设计具有这些性质的指标具有很多挑战, 所设计的指标需要兼顾多个方面, 只考虑某一个指标不能准确地反应算法的性能. 如图 6所示, 圆点表示算法得到的解集, 虚线和实线代表问题的两个PS. 图 6(a)中算法得到的解集具有很好的多样性, 但是圆点还没有逼近实线或者虚线, 因此收敛性差; 图 6(b)圆点逼近了实线或者虚线, 但是聚成了簇, 多样性差; 图 6(c)算法得到的解集具有良好的多样性和收敛性, 但是并没有覆盖整个PS, 而是覆盖了$ \rm{PS}_1 $的一部分和$ \rm{PS}_2 $的另外一部分, 虽然这两部分可以组成一个相对完整的PF, 但事实上算法并没有找到一个完整的PS; 图 6(d)给出了理想情况下, 算法得到解集的分布情况. 由图 6可知, 同时衡量解集在决策空间和目标空间的分布性、多样性、收敛性和覆盖率是比较困难的.

为了解决上述挑战, 研究者提出了不同种类的评价指标. Rudolph等^[37]设计了covered sets(CS)和set population spread(SPS)衡量多模态多目标优化算法的性能. CS表示帕累托子集被覆盖的数目, CS越大表明算法求得的解集覆盖帕累托子集的数量越多. SPS表示接近每个帕累托子集的种群数量的标准差, SPS越大表明算法求得的解集多样性越好. 但是, 随机均匀初始化的种群这两个指标值都比较好, 因此这两个指标不能准确地反映算法的性能. Zhou等^[44]将IGD^[42]用于决策空间(IGDX), 衡量算法求得的PS与真实PS之间的接近程度, IGDX的计算方法如下.

令$ {P^*} $代表沿真实PS均匀分布的点集(参考点), $ O $代表算法求得的解集, IGDX计算如下:

$ \begin{align} {\rm IGDX}(O, {P^*}) = \dfrac{{ \sum\limits_{v \in {P^*}} {d(v, O)} }}{{| {{P^*}} |}}. \end{align} $

(3)

其中: $ d(v, O) $为$ v $和$ O $中所有点之间欧氏距离的最小值, $ | {{P^*}} | $为参考点的数目. 如果参考点集能够很好地表示真实PS, 则IGDX就能较好地衡量决策空间的收敛性和多样性. IGDX的值越小, 表明算法求得的解集和参考点集越接近. 但是只用IGDX指标衡量算法性能存在一种缺陷, 当算法求得的解也在真实PS上, 但是没有与参考点接近或重合时, IGDX的值便不能反映求解此问题的情况. 为了更合理地比较不同多模态多目标优化算法的性能, Yue等^[14]将CR与IGDX相结合, 设计了新的衡量指标PSP. 但是PSP的最优值为无穷大, 根据指标值无法判断算法求得解集与最优解集的差距, 于是Yue等^[21]将PSP改成$ {1}/{{\rm PSP}} $, 这样评价指标$ {1}/{{\rm PSP}} $的最优值变为零, 指标值越接近零表明算法性能越好. $ {1}/{{\rm PSP}} $的计算方法如下所示, 它既能反映算法求得解集对真实PS的覆盖率, 又能反映它们之间的接近程度:

$ \begin{align} \dfrac{1}{{\rm PSP}} = \dfrac{{\rm IGDX}}{{\rm CR}}, \end{align} $

(4)

其中CR为算法求得的解集对真实解集的覆盖率. $ {1}/{{\rm PSP}} $越小表明算法求得的解集与真实解集越接近, 且算法求得的解集对真实解的覆盖率越大. $ {1}/{{\rm PSP}} $也只能反映决策空间的性质, 为了综合评价算法的性能, 需要搭配目标空间衡量指标(如HV^[43])对算法进行综合评价.

为了同时评价解集在决策空间和目标空间的性质, Liu等^[22]提出了评价指标IGDM, 该指标可以衡量解集在决策空间和目标空间的收敛性和多样性. 令$ {F^*}:\{ {f_1^*, f_2^*, \ldots , f_q^*} \} $为PF上均匀分布的参考点, $ q $为参考点的个数; $ A:\{ {{a_1}, {a_2}, \ldots, {a_q}} \} $, $ {a_i}(i = 1, 2, \ldots, q ) $为目标值是$ f_i^* $的帕累托最优解的个数; $ {X^*}:\{ x_{1, 1}^*, x_{1, 2}^*, \ldots, x_{1, a_1}^*, x_{2, 1}^*, \ldots, x_{q, {a_q}}^* \} $代表与$ {F^*} $和$ A $对应的帕累托最优解集; P为算法求得的解集. IGDM定义如下:

$ \begin{align} &{\rm IGDM}( {P, {F^*}, {X^*}} ) = \\ & \dfrac{{ \sum\limits_{f_i^* \in {F^*}} { \sum\limits_{j = 1, 2, \ldots , {x_p}} {d( {f_i^*, x_{i, j}^*, P} )} } }}{{| {{X^*}} |}}. \end{align} $

(5)

其中

$ \begin{align*} &d( {f_i^*, x_{i, j}^*, P} )\! = \! \begin{cases} d_{\max }, \; P_{i, j} = \varnothing; \\ \min \{ {{d_{\max }}, {\rm ed}( {f_i^*, {P_{i, j}}} )} \}, \; {\rm otherwise}. \end{cases}\\ &{P_{i, j}} = \{ {{x_k}:j = \arg\mathop {\min }\limits_{l = 1, 2, \ldots, {a_i}}{\rm ed}( x_{i, l}^*, {x_k} ), \; {x_k} \in P} \}. \end{align*} $

$ {\rm ed}( {f_i^*, {P_{i, j}}} ) $为$ F^* $与$ P_{i, j} $间的最小欧氏距离; ed$ ( x_{i, l}^*, {x_k} ) $为$ x_l^* $与$ x_k $之间的最小欧氏距离; $ {d_{\max }} $为预定义的参数, 一般设置为1.

虽然已经有一些多模态多目标优化算法的评价指标, 但是大部分都需要已知问题的PS和PF, 并根据它们选取参考点或参考向量. 在实际问题中PS和PF是未知的, 算法性能难以评价. 因此, 多模态多目标优化中, 在PS和PF未知的情况下, 如何设计合理的性能指标是未来研究的一个方向.

4 应用领域及未来研究方向 4.1 应用领域

多模态多目标优化具有广泛的应用领域, 如桥梁优化问题^[45]、饮食设计问题^[37]、空间任务设计问题^[46]、化工生产优化问题^[47]、火箭发动机任务设计问题^[48]、功能性脑成像问题^[49]、路径规划问题^[14]、特征选择问题^[17]、建筑选址问题^[39]等. 上述领域的多目标优化问题具有典型的多模态特性, 且不同的解集具有不同的实际意义. 例如, 某个路径规划问题以路程最短和红绿灯个数最少为优化目标, 存在路程和红绿灯个数都相同的多条路径, 但是它们途经的公共设施可能大有区别, 如果使用多模态多目标优化算法找到多个符合要求的路径, 则不同的司机可以根据自己对公共设施的偏好选择不同的路径. 由于多模态多目标优化的发展仍处于初级阶段, 虽然许多问题属于多模态多目标优化问题, 但是技术人员并未采用多模态多目标优化算法解决这些问题, 需要开发出高效稳定的算法, 为决策者提供更多选择, 也为节约能源、减少污染、降低成本做出贡献.

4.2 未来研究方向

多模态多目标优化领域未来研究包括以下几个方向:

1) 如何同时找到全局和局部帕累托最优解集是多模态多目标优化中的未来研究方向之一. 通过本文的分析可知, 根据全局和局部最优解集的情况, 多模态多目标优化问题可分为两类: 第1类问题只具有全局帕累托最优解集, 第2类问题既有全局帕累托最优解集又有局部帕累托最优解集. 现有的多模态多目标优化算法大多数用来解决第1类问题, 对于第2类问题的解决效果不佳. 因此, 如何搜索到第2类问题的全局和局部最优解集是值得研究的方向.

2) 决策空间收敛性和多样性不平衡问题^[50]是多模态多目标优化领域新的挑战. 在决策空间收敛性和多样性不平衡问题中, 有些帕累托最优解集极易搜索到, 但有些解集则极难找到, 因为不同解集附近的适应度地形不同, 如果某个解集所在的盆区较大, 则搜索此解集的难度较小, 如果某个解集所在的盆区较狭窄或较崎岖, 则搜索此解集的难度会较大. 如何处理多模态多目标优化中收敛性和多样性不平衡问题也是未来的研究方向之一.

3) 多模态多目标优化问题最终解的选择也是待解决的难题. 一个帕累托最优解集包含多个可行解, 多个帕累托解集包含的可行解数目大大增加, 而在一个实际应用的具体情况下, 必须从这些解中挑选出一个使用, 不同决策者在不同情况下会挑选不同的解, 因此最终解的选择是未来研究的难题.

4) 离散多模态多目标优化问题也是未来研究的方向之一^[51]. 特征选择、路径规划、车间流水线调度中存在大量的多模态多目标优化问题, 它们都属于离散组合优化问题. 本文介绍的算法均是连续优化算法, 不能直接用来求解离散优化问题, 如何解决离散多模态多目标优化中编码难题及进化导向问题是未来需要研究的方向.

除了上述方向以外, 在该领域还有许多待研究的问题, 包括: 动态、高维、高目标多模态优化问题研究^[52-53]; 多模态多目标优化中高维可视化技术研究; 多模态多目标优化收敛性分析等理论研究.

5 总结与展望

本文对多模态多目标优化领域的相关工作进行了分析总结, 从提高算法搜索能力和提高决策空间多样性两个方面介绍了相关算法, 阐述了解决多模态多目标优化问题的困难和挑战. 提高算法搜索能力(即增强探索能力), 提高决策空间多样性(即增强开采能力), 这两方面能力的权衡是解决多模态多目标优化问题的关键. 多模态多目标优化是进化计算领域相对新的研究方向, 它具有广阔的应用前景, 该方向还有许多未解决的问题值得研究者深入研究.