-
多目标优化问题在现实生活中非常普遍，这类问题涉及到同时优化两个或者两个以上相互冲突的目标。例如，我们要购买一台电脑，运行速度和小巧轻便是我们所追求的目标，然而体积和运行速度之间是相互冲突的，体积越小也就意味着电脑散热能力越弱，从而影响电脑的运行速度。我们不可能使每个目标同时达到最优状态，只能从所有可能的情况中找到一个相对令我们满意的答案。
针对上述类型的优化问题，已有大量的智能优化算法被提出，这些算法被称为多目标优化算法。典型的多目标优化算法有基于精英策略的非支配排序遗传算法II（NSGA-II）[1]、高强度Pareto进化算法2（SPEA2）[2]、基于分解的多目标进化算法（MOEA/D）[3]、多目标粒子群算法（MOPSO）[4]等。与传统的优化算法相比，这些启发式优化算法能在运行中同时搜索到可能的解，不仅可以找到较优的Pareto前沿，而且能够保证求得的解尽可能均匀地分布在目标空间中。
随着学者对多目标优化问题的深入研究，发现在一些优化问题中存在两个或者两个以上Pareto最优解集对应同一个Pareto前沿，并且存在至少一个局部最优解或两个以上全局最优解，这类问题被称为多模态多目标优化问题[5]。由于这类问题的所有解集都有可能是我们所寻求的解，而在实际应用中部分解的丢失可能造成不必要的困难或经济损失[6]，因此对多模态多目标优化的研究在实际问题优化中具有重要的意义。解决多模态多目标优化问题需要找到Pareto前沿上每个点对应的所有的Pareto解集[7]。由于现有的大多数多目标优化算法未考虑解集在决策空间的多样性，因此不能保证找到所有Pareto最优解[8]。
为了给决策者提供更多的选择机会，一些学者致力于这类具有多峰性质的多目标优化问题的研究。Liang等[9]在MODE算法的基础上加入决策变量预选方案促进决策空间的多样性。Hu等[10]将自组织映射（SOM）和改进的鸽子算法结合提出了MMOPIO算法。Yu等[11]提出了一种多学习回溯搜索算法（MLBSA），用于实际多模态电流电压数据的优化问题。Guo等[12]提出了一种具有自组织机制的多目标粒子群算法求解多模态问题。Lynn等综合粒子群算法的探索与开发能力，提出了异质综合电子学习微粒群优化算法（HCLPSO）[13]，后来又提出集合粒子群优化算法（EPSO）[14]去解决实际多模态的参数优化问题。Qu等[15]使用多个局部最佳粒子信息，提出了基于距离的局部信息粒子群优化算法解决多模态问题。Yan等[16]采用动态拓扑结构和停滞检测策略提出了增强的多模多目标蝙蝠算法（PEN-MOBA）。Fan等[17]提出了一种“物理隔离”的分区搜索方法，通过将搜索空间划分为多个子空间保持决策空间的多样性。Shi等[18]利用调和平均距离法估计决策空间解的全局密度，提出了一种新的基于密度的多模多目标算法。Kalyanbrata等[19]在原有的邻域敏感存档进化多目标优化算法框架的基础上，提出了多模态NAEMO算法。Ji等[20]利用距离信息和目标函数值将多模态多目标优化问题转换为双目标优化问题，然后再进行问题的求解。
如何同时平衡目标空间和决策空间解的分布情况，找出所有的较优解是本文研究的核心内容。
(1)建立空间学习机制。种群能够对种群内每个个体与最佳个体的相对空间位置进行学习监测，从而根据种群分布状态将种群判定为离散态或聚合态中的一种。分别为两种种群分布状态定义不同的搜索寻优策略，使算法前期能够快速发现多个较优解，后期能精确收敛到最优解。
(2)受群体社会行为启发，将整个种群划分为开发者子群与游走者子群。开发者子群里的个体负责引导及开发，可以自学习以及邻里学习；游走者子群里的个体负责跟随及勘探，除了自学习及邻里学习之外，还必须要服从开发者的领导。
(3)引入了情感因子模型，增强个体间的信息交互，防止算法陷入停滞状态，提高算法求解速度。其次采用特殊的非支配排序方法保证算法所求解在决策空间和目标空间的双重多样性。
-
多目标优化问题又称为多标准优化问题[21]。通常一个多目标优化问题（此处以最小化问题为例）可以定义为如下形式：
其中：
${{x}} = ({x_1},{x_2}, \cdots ,{x_n}) \subseteq {{\bf{R}}^n}$ 为搜索空间中的决策向量；${{\varOmega}}$ 为n维的决策空间；${{y}} = \left( {{f_1}(x),{f_2}(x), \cdots ,{f_m}(x)} \right) \subseteq {{Y}}$ 为m维的目标向量，Y为m维的目标空间；$F({{x}})$ 定义了m个由决策空间到目标空间的映射函数。 -
相较于一般的多目标优化问题，多模态特征是指在决策空间中存在两个或者两个以上不同的决策向量值对应于目标空间的同一个值，表示如下：
其中，
${{x}_{1}} = ({a_1},{b_3},...,{m_4})$ 和${{x}_{6}} = ({a_3},{b_1},...,{m_8})$ 两个不同的决策向量都对应于${{y}_{1}}$ 。对于决策者而言，${{x}_{1}}$ 和${{x}_{6}}$ 两个解同等重要，图1示出了不同解的分布。
图 1 解在决策空间和目标空间的分布
Figure 1. Distribution of solutions in decision space and target space
-
文献[22]提到对于优化问题而言，其复杂度由搜索空间和目标空间共同决定，划分搜索空间能有效降低问题的复杂度。受此启发，本文充分挖掘决策空间的信息，建立搜索空间状态学习机制，根据分析学习初始解分布的特征，为后续算法的搜索过程提供引导方向。
定义1 空间距离 对于种群中的任意个体
${{x}_{i}}$ ，假设其在各维度上的坐标为$x_{i1}^{},x_{i2}^{},...,x_{in}^{}$ ，则个体${{x}_{i}}$ 和个体${{x}_{j}}$ 之间的距离$d_{ij}^{}$ 按照式（3）进行计算：
其中：
$i,j \in [1,NP]$ ，表示个体的下标序号，NP为种群的规模，即种群中个体的总数，此处要求$i \ne j$ 且$k \in [1,n]$ ；n为搜索空间维度。对于种群内每一个个体
${{x}_{i}}$ ，根据式（3）分别计算其与种群内其他个体的距离$d_{i1}^{},d_{i2}^{},...,d_{i(i - 1)}^{},d_{i(i + 1)}^{},..., d_{iNP}^{}$ ，则其空间距离$ds_i^{}$ 定义如下：
定义2 种群状态 根据定义1计算出每个个体的空间距离
$ds_i^{}$ 之后，首先对此学习信息的有效性进行判定，如果$d{s_i} \geqslant \delta /NP \times \displaystyle\sum\limits_{j = 1}^{NP} {d{s_j}} $ （其中$\delta _{}^{}$ 表示舍弃系数，一般设定范围为[1.5,3]），则表示该个体离种群进化中心较远，处于种群边缘游离区，基于该个体空间学习到的信息对于整个群体的进化过程将不会起到正向指引作用，因此将舍弃这类个体的位置信息。经过上述取舍过程，对于余下的
$NP_{}^\sim $ 个有效个体，根据整个搜索空间里每个个体与种群进化中心之间的相对距离，定义了两种分布状态，按照如下规则进行判定：(1)若
${\displaystyle\sum\limits _{i=1}^{N{P}^{\sim}}d{s}_{i}}\geqslant 0.5{\rm{Range}} \times NP{\text{或}}i\geqslant 0.5 \times NP$ ，则此时种群处于离散态；(2)若
${\displaystyle\sum\limits _{i=1}^{N{P}^{\sim}}d{s}_{i}} < 0.5{\rm{Range}}\times NP{\text{或}}i < 0.5 \times NP$ ，则此时种群处于聚合态。其中：
${\rm{Range}}$ 为决策空间的范围，即上下界之间的差值；$i$ 为每一次迭代过程中基于特殊拥挤距离排序后个体的序数值。定义3 搜索偏好 根据学习到的群体状态结果，确定算法的搜索偏好。定义3种搜索偏好：开发、收敛、勘探。如图2所示，开发和收敛阶段注重全局解的搜寻，勘探阶段注重局部解的挖掘。
图 2 3种搜索偏好行为
Figure 2. Three search preference behaviors
-
文献[23]提到在较大目标空间内有限的种群规模难以保证找到所有最优解，多个种群以分布式方式共同进化能保持Pareto前沿的多样性。文献[24]指出合理的社会团队等级和有效的团队合作能帮助狼群有效地猎捕食物。因此，本文将整个搜索种群划分为开发个体和游走个体两个子群体。
定义4 支配度
${D_{{\rm{ab}}}}$ 支配度反映${s_{\rm{a}}}$ 和${s_{\rm{b}}}$ 两个解的相对优劣程度，对于最小化问题来说支配度的计算公式如下：
如果式（5）成立，则
${D_{\rm{{ab}}}}$ =1，否则${D_{{\rm{ab}}}}$ =$ - 1$ 。定义5 开发者 开发者具有较高的支配等级，在整个群体中负责引导作用，可以自学习以及邻里学习，代表种群前进的方向。
定义6 游走者 其相应的帕累托支配等级较低，除了自学习及邻里学习之外，还需要学习开发者的优秀信息。
-
定义7 追踪行为 在
$n$ 维搜索解空间里，第$i$ 次迭代过程中，某个追踪个体的位置向量为$(x_{i1}^{\rm{{track}}}, x_{i2}^{\rm{{track}}},..., x_{in}^{\rm{{track}}})$ ，该个体在空间中寻解的速度向量为$(v_{i1}^{\rm{{track}}}, v_{i2}^{\rm{{track}}},...,v_{in}^{\rm{{track}}})$ ，追随的目标个体位置向量为$(x_{i1}^{{\rm{pioneer}}}, x_{i2}^{{\rm{pioneer}}},...,x_{in}^{{\rm{pioneer}}})$ ，其寻解速度向量为$(v_{i1}^{{\rm{pioneer}}},v_{i2}^{{\rm{pioneer}}},..., v_{in}^{{\rm{pioneer}}})$ 。在下一次迭代时，追踪个体的速度向量按照式（6）进行更新。
其中：
$w$ 为权重因子；$c$ 为追踪因子，表征了追踪行为的力度；$r$ 为0和1之间的随机数。文献[25]提到一些具有高影响力的人的行为会影响社会中的其他个体，此外个人的行为也会受到与自己近邻的人的行为影响。在此研究基础之上，结合生物学中的情感行为，本文定义了情感因子模型，帮助提升种群搜索能力。
定义8情感因子
${e_{i,j}}$ 个体${{{x}}_i}$ 在向个体${{{x}}_j}$ 学习过程中，其受到的情感影响因素主要由二者的角色差异、个人能力及相互距离所决定。用
${\lambda _{ri,j}}$ ，${\lambda _{ai,j}}$ 和${\lambda _{di,j}}$ 分别表示角色因子、能力因子及距离因子，3个因子系数均为[0,1]内的随机数，按照以下情感规则计算：(1)由于种群被划分为了两个群体，所谓“近朱者赤近墨者黑”，如果个体
${{{x}}_i}$ 和个体${{{x}}_j}$ 处于同一个种群或者${{{x}}_i}$ 处于游走者子群而${{{x}}_j}$ 处于开发者子群，则二者之间影响力较强，此时${\lambda _{ri,j}} \in [0.5,1]$ ，否则${\lambda _{ri,j}} \in [0,0.5)$ 。(2)具有高支配度的个体对于种群的进化方向起着正向引导作用，根据定义4计算个体
${{{x}}_i}$ 和${{{x}}_j}$ 之间的支配度关系，如果${D_{ji}} = 1$ ，则${\lambda _{ai,j}} \in [0.3,1]$ ，否则${\lambda _{ai,j}} \in [0,0.3)$ 。(3)一个人的行为会受到与自己亲近的人的影响，因此两人距离越近，代表二者之间的感情越深厚，彼此影响的概率较大，因此
${\lambda _{di,j}}$ 可以按照式（7）进行计算：
根据以上3条情感规则，结合3个因子系数，情感因子
${e_{i,{\rm{j}}}}$ 计算如公式（8）所示：
其中：
$e_{ci,j}^{}$ 为角色因子、能力因子及距离因子的乘积，代表3个影响作用的累积效应。情感因子${e_{i,j}}$ 平衡了个体${{{x}}_i}$ 受到个体${{{x}}_j}$ 和整个种群进化方向的影响作用。图3示出了基于情感因子的追踪行为机制。
图 3 情感因子追踪行为机制
Figure 3. Affective factor tracking behavior mechanism
-
令种群中个体总数为
$NP$ ，维度为$n$ 维，搜索范围为$[{x_{{\rm{low}}}},{x_{\rm{upper}}}]$ ，为每个个体${p_i}$ 赋予初始的${{\rm{x}}_i}$ 和${v_i}$ 。将个体按照其支配度进行排序，根据分群公式${N_{\rm{pioneer}}} = {\rm{floor}}(NP * per)$ 选出${N_{\rm{pioneer}}}$ 个个体为开发者群体，剩余的$NP - {N_{\rm{pioneer}}}$ 个为游走者群体。其中：${\rm{floor}}()$ 为向下取整函数；${\rm{per}}$ 为分群阈值系数，实验取值范围为$[0.2,0.5]$ 。此外为开发者群体建立开发者个人最佳存档（$p_{\rm{best}}^{\rm{pioneer}}$ ）与邻里最佳存档（$g_{\rm{best}}^{\rm{pioneer}}$ ），为游走者群体建立游走者个人最佳存档（$p_{\rm{best}}^{\rm{track}}$ ）与邻里最佳存档（$g_{\rm{best}}^{\rm{track}}$ ）。 -
个体在搜索整个决策空间之前，先根据空间状态学习结果判断当前种群的离散程度，当种群处于离散态时，使用离散状态下的游走追踪方式进行整个空间的搜索收敛；当种群处于聚合态时，使用聚合状态下的动态搜索策略进行局部勘探。
-
个体在寻优过程中会受到自身历史信息和附近邻居个体的影响，个体支配程度越高，代表其位置信息拥有量越多，其社会等级越高，不同社会等级的个体将采取不同的学习更新方式。开发者将学习其历史最优位置信息和其优秀邻居个体的位置信息，二者对一个个体产生的速度偏差如式（9）所示：
游走者除了学习其自身历史最优信息之外，还将根据定义8计算情感因子，学习使其情感因子最大的开发者
$x_j^{}$ 的位置信息，二者对该个体产生的速度偏差如式（10）所示：
每个个体的历史和位置更新方式如下：
其中：
$v_{t + 1,i}^{}$ 和$x_{t + 1,i}^{}$ 表示个体$i$ 在$t + 1$ 时刻的速度和位置；$v_{t,i}^{}$ 和$x_{t,i}^{}$ 表示个体$i$ 在$t$ 时刻的速度和位置；$x_{t,{\rm{pbest}}}^{\rm{{pioneer}}}$ 和$x_{t,{\rm{pbest}}}^{{\rm{track}}}$ 分别表示开发者个体和游走者个体的历史最佳位置；$x_{t,{\rm{nbest}}}^{{\rm{pioneer}}}$ 表示开发者的优秀邻居个体位置；${e_{i,j}} \otimes x_{t,i}^{\rm{{pioneer}}}$ 表示游走者追踪的开发者个体位置；$w$ 为权重因子；$\alpha $ 和$\beta $ 服从[0,1]区间内的均匀分布。 -
当群体状态处于聚合态时，个体分布较为集中。为了充分挖掘最优解附近的潜在位置，选取一部分开发者进行动态勘探行为，搜索周围方向最优的一个位置作为自己的移动信息，如果更新后的位置优于当前最优值，则更新最优位置信息，否则退回到前一步的位置。开发者的速度和位置分别按照式（13）和式（14）更新。
其中：
$\mu $ 和$b$ 分别控制勘探间距和勘探范围，二者是[0，1]内的均匀分布函数；$\mu {{\rm{e}}^{ - bt}}$ 随着勘探代数的增加而单调递减；$\theta $ 表示勘探行为的角度，控制开发者在其自身的8个方向上进行局部勘探。 -
首先根据文献[1]中提到的非支配排序排序策略为个体进行排序，然后计算个体在决策空间和目标空间的拥挤距离，根据该距离降序排列所有的个体，排序后的第一个个体就是具有最大距离的非支配解。拥挤距离的计算采用文献[5]中提出的方法。以二维空间为例，将所有个体分级后排序方式如图4所示。
图 4 特殊的排序方式
Figure 4. Special sorting method
(1)对于中间的个体（以3号为例），其决策拥挤度计算如下：
$c{d_{3,x}} = \left| {\dfrac{{{x_{1,4}} - {x_{1,2}}}}{{{x_{1,5}} - {x_{1,1}}}}} \right| + \left| {\dfrac{{{x_{2,4}} - {x_{2,2}}}}{{{x_{2,5}} - {x_{2,1}}}}} \right|$ ；其目标拥挤度计算如下：$c{d_{3,f}} = \left| {\dfrac{{{f_{1,4}} - {f_{1,2}}}}{{{f_{1,5}} - {f_{1,1}}}}} \right| + \left| {\dfrac{{{f_{2,4}} - {f_{2,2}}}}{{{f_{2,5}} - {f_{2,1}}}}} \right|$ ，${x_{i,j}}$ 和${f_{i,j}}$ 为第$j$ 个个体的第$i$ 维度信息。(2)处于边上的个体（以1号为例），其决策拥挤度计算公式如下：
$c{d_{1,x}} = 2\left( {\left| {\dfrac{{{x_{1,1}} - {x_{1,2}}}}{{{x_{1,1}} - {x_{1,5}}}}} \right| + \left| {\dfrac{{{x_{2,1}} - {x_{2,2}}}}{{{x_{2,1}} - {x_{2,5}}}}} \right|} \right)$ ；其目标拥挤度$c{d_{1,f}}$ =1。然后计算个体的特殊拥挤距离（${\rm{scd}}$ ）。当个体的$c{d_{i,x}} \geqslant c{d_{{\rm{avg}},x}}||c{d_{i,{\rm{f}}}} \geqslant c{d_{{\rm{avg}},f}}$ 时，${\rm{sc{d}}_i} = \max (c{d_{i,x}},c{d_{i,{\rm{f}}}})$ ，否则令其${\rm{sc{d}}_i} = \min (c{d_{i,x}},c{d_{i,{\rm{f}}}})$ 。其中$c{d_{{\rm{avg}},x}}$ 是决策空间平均距离，$c{d_{{\rm{avg}},{\rm{f}}}}$ 是目标空间平均距离。 -
基于空间学习和情感追踪的多模多目标群搜索算法（MMO_LTSGSO）的伪代码如下：
输入：种群个体总数NP，维数n，最大迭代次数Tmax
输出：帕累托解集（PS）和帕累托前沿（PF）
begin
（1） 初始化NP个个体，T = 0
（2） 根据分群公式将个体划分为开发者和游走者
（3） 根据式（4）进行支配度排序，将非支配解和最优解分别放入
${p}_{\rm{{best}}}^{\rm{{track}}}{\text{、}}{g}_{\rm{{best}}}^{\rm{{track}}}{\text{、}}{p}_{\rm{{best}}}^{\rm{{pioneer}}}{\text{、}}{g}_{\rm{{best}}}^{\rm{{pioneer}}}$ 中（4） while T < Tmax
（5） 根据式（3）学习空间分布状态：
（6） if 处于离散态
（7） 从
${p}_{\rm{{best}}}^{\rm{{track}}}{\text{、}}{p}_{\rm{{best}}}^{{\rm{pioneer}}}$ 中挑选优秀信息（8） 根据式（7）、（9）、（10）更新开发者的信息
（9） 根据式（6）、（8）~（10）更新游走者信息
（10） else
（11） 从
${g}_{\rm{{best}}}^{{\rm{track}}}{\text{、}}{g}_{\rm{{best}}}^{{\rm{pioneer}}}$ 中挑选优秀信息（12） 根据式（11）、（12）更新个体的信息
（13） 根据3.3节所述的特殊的非支配排序方式更新
${p}_{\rm{{best}}}^{\rm{{track}}}{\text{、}}{g}_{\rm{{best}}}^{\rm{{track}}}{\text{、}}{p}_{\rm{{best}}}^{\rm{{pioneer}}}{\text{、}}{g}_{\rm{{best}}}^{\rm{{pioneer}}}$ ，并移除支配解（14） 将4个外部存档进行交叉学习，获得优秀个体信息更新
${g}_{best}^{\rm{{track}}}{\text{、}}{g}_{best}^{\rm{{pioneer}}}$ （15） 输出PS和PF
end
-
对于一个搜索空间为
$s$ 、优化函数为$f$ 的优化问题$ < s,f > $ ，假设优化算法第$i$ 次寻优的非支配解个数为${n_i}$ ，此时非支配解（优秀解）的集合记作$x(i) = \left\{ {\left. {{x_{i,1}},{x_{i,{\rm{2}}}},...,{x_{i,n}}} \right\}} \right.$ ；第$i + 1$ 次搜寻到的非支配解个数为${n_{i + 1}}$ ，非支配解集合记作$x(i + 1)$ 。定理1 对于任意一个迭代时刻
$i$ 和$i + 1$ ，非支配解的个数都单调并不递减，即$\forall i \leqslant {T_{\max }},{n_{i + 1}} \geqslant {n_i}$ 。证明 搜寻到最优解的个体的支配程度高于其他个体，即该个体较其他个体优秀，算法MMO_LTSGSO在每次搜寻解空间时都会将优秀的个体保存下来，因此在每次迭代过程中优秀的个体不会被后来个体的加入而删除，即假如算法在第
$i$ 次迭代时存档中支配度最高的个体有${n_i}({n_i} \geqslant 0)$ 个，则在下一次迭代时，存档中的优秀个体数目恒满足${n_{i + 1}} \geqslant {n_i}$ 。定理2 MMO_LTSGSO能够收敛到全局最优解，即：
$\mathop {\lim }\limits_{i \to {t_{\max }}} P(f(x(t)) > 0) = 1$ 。证明 当第
$i$ 次迭代时非支配解数为$a$ 的概率为${P_{\rm{a}}}(i) = P(f(x(i)) = a)$ ，由贝叶斯概率公式有：${P_{\rm{a}}}(i + 1) = P(f(x(i + 1)) = a\left| {f(x(i)) = a} \right.) \times P(f(x(i)) = a)+$ $P(f(x(i)) \ne a) \times P(f(x(i + 1)) = a) + P(f(x(i + 1)) \ne a))$ 根据定理1可知：$P(f(x(i + 1)) = a|f(x(i)) \ne a) = 0$ 。可以得到：
又因为算法在搜寻的任意时间里都可能移动到帕累托优秀解的区域内，所以可以得出：
结合上述两式可知：
又因为
${P_{\rm{a}}}(i + 1) \leqslant (1 - \mu ){P_{\rm{a}}}(i)$ ，所以当$i \to \infty $ 时可以得到：$0 \leqslant {P_{\rm{a}}}(i + 1) \leqslant {(1 - \mu )^{i + 1}}{P_{\rm{a}}}(0){\rm{ = 0}}$ 。因此可以得到：$\mathop {\lim }\limits_{i \to \infty } P(f(x(i)) > 0){\rm{ = 1 - }}\mathop {\lim }\limits_{i \to \infty } P(f(x(i)){\rm{ = }}0){\rm{ = 1}}$ 。由上分析可知，MMO_LTSGSO算法最终会以概率1收敛到一个最优的状态。
-
实验环境为带有8个计算节点和1个控制节点的联想深腾6800并行计算集群，计算平台为Matlab R2017b。选择CEC2019多模多目标定义问题中的MMF1~MMF12函数和SYM-PART simple、SYM-PART rotate以及Omni-test(n=3)作为测试函数，表1示出了这些函数相关的多峰性质。文献[6]提出用PSP和Hv这两个主要指标来衡量多模多目标算法的性能，较大的PSP表示算法在决策空间性能较好，较大的Hv表示算法在目标空间中表现较好。本文分别采用1/PSP和1/Hv来衡量各个算法的求解的优劣程度，因此1/PSP和1/Hv的值越小就代表着算法的综合性能越好。各类参数设置如下：种群规模设置为500，外部档案大小设为800，迭代次数设置为50次，4个对比算法的实验参数设定与参考文献中一致。5个算法均在相同运行环境下独立运行15次。
Function Number of PS Overlap in every dimension MMF1 2 no MMF2 2 no MMF3 2 yes MMF4 4 no MMF5 4 no MMF6 4 yes MMF7 2 no MMF8 4 no MMF9 2 no MMF10 2(1 global+1 local) no MMF11 2(1 global+1 local) no MMF12 8(4 global+4 local) yes SYM-PART simple 9 yes SYM-PART rotate 9 yes Omni-test(n=3) 27 yes 表 1 测试函数的多模性质
Table 1. Multimodal features of the test functions
-
由于多模多目标优化问题不同于一般的多目标问题，其具有多个全局最优解或多个局部最优解，为了验证MMO_LTSGSO算法解决多模态多目标优化问题的有效性，首先将MMO_LTSGSO在15个多模测试函数上运行求解，实验结果如图5所示。从图可以看出MMO_LTSGSO算法在MMF1~MMF9以及SYM-PART simple、SYM-PART rotate和Omni-test测试函数上表现很好（如图5(a)~(i)和(m)~(o)所示），能够同时找到多个未重叠或者重叠的帕累托最优前沿PS。由于MMF10~MMF12函数包含上半部分的局部PS和下半部分的全局PS，由图5(j)~(l)可知，MMO_LTSGSO算法所求的解均分布在最优PS附近，除了MMF10函数局部最优有极少量解分布外，基本没有保存局部最优值的信息，说明MMO_LTSGSO算法在能保证搜寻到所有最优PS的同时不易陷入局部最优。
图 5 MMO_LTSGSO在15个测试函数上的求得的PS与真实PS
Figure 5. The obtained PS by MMO_LTSGSO and the true PS on 15 test functions
将MMO_LTSGSO算法与4个多模态多目标优化算法进行对比，验证MMO_LTSGSO算法的性能。4个对比算法分别是MO_Ring_PSO_SCD[5]、DN_NSGAII[6]、MMOEA_GD[18]以及MMOPIO[10]。1/PSP用来评价算法在决策空间求解的多样性，值越小代表算法性能越好。表2示出了每个算法在15个测试函数上的1/PSP的均值和方差。结果表明MMO_LTSGSO算法在MMF3、MMF5、MMF6、MMF12以及SYM_PART_simple、SYM_PART_rotated、Omni_test上表现最好，在其他几个函数上，虽然MMOPIO算法表现相对较好，但是MMO_LTSGSO算法的指标值和其相差并不大。
Test functions 1/PSP（mean±std） MMO_LTSGSO MO_Ring_PSO_SCD DN_NSGAII MMOEA_GD MMOPIO MMF1 0.0411±0.0013 0.0455±0.0019 0.0741±0.0200 0.0436±0.0028 0.0361±0.0018 MMF2 0.0177±0.0059 0.0283±0.0120 0.0577±0.1301 0.011±0.0044 0.0267±0.0065 MMF3 0.0148±0.0020 0.0223±0.0087 0.0477±0.0302 0.022±0.0048 0.0175±0.0054 MMF4 0.0222±0.0022 0.0251±0.0020 0.0554±0.0181 0.0217±0.0011 0.0195±0.0027 MMF5 0.0743±0.0051 0.0810±0.0041 0.1517±0.0198 0.0747±0.0032 0.0745±0.0048 MMF6 0.0658±0.0038 0.0679±0.0043 0.1143±0.0170 0.0660±0.0023 0.0658±0.0060 MMF7 0.0204±0.0008 0.0232±0.0017 0.0366±0.0095 0.0205±0.0021 0.0158±0.0017 MMF8 0.0621±0.0125 0.0598±0.0047 0.1236±0.1415 0.0590±0.0061 0.0743±0.0112 MMF9 0.0054±0.0003 0.0070±0.0004 0.0135±0.0081 0.0056±0.0002 0.0025±0.0001 MMF10 0.1599±1.5610 0.1029±0.0207 0.1030±3.1331 0.1118±0.1020 1.8053±2.2440 MMF11 0.1880±0.5616 0.1884±0.3425 1.4972±0.1490 0.1889±0.4118 1.6055±0.3832 MMF12 0.1428±0.5234 0.1433±0.5050 0.1954±0.6892 0.1731±0.5497 1.6757±0.4923 SYM_PART_simple 0.0777±0.0140 0.1443±0.0371 1.1423±1.3414 0.1248±0.0148 0.0778±0.0073 SYM_PART_rotated 0.0947±0.0190 0.1560±0.0459 2.2009±11.424 0.1351±0.0195 0.2210±0.3609 Omni_test 0.0870±0.0258 0.3086±0.0798 1.2623±0.3609 0.9491±0.0123 0.3950±0.0598 表 2 5个算法在15个多模多目标测试函数上的1/PSP值
Table 2. 1/PSP value of five algorithms on 15 multimodal multi-objective test functions
为了测试算法所求得的解在目标空间的优劣程度及分布性能，计算所有算法在测试函数上的1/Hv值，该值越小表明所求的解在目标空间分布越均匀，算法性能越好，具体结果如表3所示。实验结果表明MMO_LTSGSO算法在MMF3、MMF4、MMF6、MMF8、MMF9、MMF10、MMF11以及SYM_PART_rotated、Omni_test上表现最好，在其
Test functions 1/HV（mean±std） MMO_LTSGSO MO_Ring_PSO_SCD DN_NSGAII MMOEA_GD MMOPIO MMF1 1.1462±0.0002 1.1480±0.0003 1.1481±0.0015 1.1488±0.0035 1.1459±0.0004 MMF2 1.1629±0.0036 1.1707±0.0097 1.1590±0.0273 1.1967±0.0190 1.1686±0.0030 MMF3 1.1630±0.0032 1.1647±0.0060 1.1633±0.0177 1.1678±0.0131 1.1657±0.0044 MMF4 1.8552±0.0012 1.8585±0.0019 1.8567±0.0007 1.8594±0.0081 1.8556±0.0012 MMF5 1.1459±0.0003 1.1476±0.0006 1.1470±0.0013 1.1471±0.0041 1.1455±0.0003 MMF6 1.1461±0.0004 1.1476±0.0012 1.1475±0.0008 1.1462±0.0219 1.1463±0.0005 MMF7 1.1462±0.0004 1.1475±0.0004 1.1480±0.0012 1.1463±0.0011 1.1430±0.0001 MMF8 2.3752±0.0113 2.3889±0.0361 2.3762±0.0032 2.3834±0.0061 2.3756±0.0019 MMF9 0.1032±0.0003 0.1033±0.0003 0.1033±0.0003 0.1035±0.0002 0.1033±0.0009 MMF10 0.0777±0.0007 0.0791±0.0006 0.0778±0.0030 0.0820±0.0034 0.0779±0.0009 MMF11 0.0689±0.0001 0.0690±0.0003 0.0689±0.0014 0.0690±0.0001 0.0671±0.0001 MMF12 0.6360±0.0002 0.6373±0.0011 0.6357±0.0562 0.6596±0.0665 0.6368±0.0003 SYM_PART_simple 0.0601±0.0007 0.0604±0.0006 0.0601±0.0001 0.0591±0.0094 0.0601±0.0001 SYM_PART_rotated 0.0601±0.0001 0.0605±0.0007 0.0601±0.0002 0.0699±0.0091 0.0602±0.0002 Omni_test 0.0189±0.0002 0.0190±0.0001 0.0189±0.0008 0.0288±0.0008 0.0190±0.0004 表 3 5个算法在15个多模多目标测试函数上的1/Hv值
Table 3. 1/Hv value of five algorithms on 15 multimodal multi-objective test functions
余函数上DN_NSGAII及MMOPIO算法的性能相对较优。总体来说，MMO_LTSGSO算法在大部分测试函数上均能获得较优的解。
为了更加直观地突出算法的性能，采用Friedman测试对5个算法进行比较。表4 示出了5个算法在15个测试函数上的综合排名，从表可知MMO_LTSGSO算法在决策空间以及目标空间均表现较好，综合排名最高。图6示出了各个算法在15个测试函数上的具体的1/PSP和1/Hv排名。图6(a)显示，除了MMF1、MMF2、MMF7、MMF8以及MMF10外，MMO_LTSGSO算法表现最好，在以上函数中的排名也在第二、第三浮动。图6(b)显示，MMO_LTSGSO算法在9个测试函数上均排名第一，在5个测试函数上排名第二，仅在SYM_PART_simple表现较差，排名第四。
Indicator 1/PSP 1/Hv Comprehensive MMO_LTSGSO 1.87 1.53 1.7 MO_Ring_PSO_SCD 3.47 3.93 3.7 DN_NSGAII 4.47 2.73 3.6 MMOEA_GD 2.73 4.13 3.43 MMOPIO 2.47 2.67 2.57 表 4 5个优化算法在决策空间和目标空间的平均排名
Table 4. Average ranking of five optimization algorithms on decision space and objective space
图 6 5个算法在15个测试函数上的Friedman排名
Figure 6. Friedman ranks of the optimization comprehensive performance for the five algorithms
-
针对多模多目标优化问题，本文提出了基于空间状态学习机制和迁徙追踪的多模多目标社会群优化算法，对搜索个体进行社会层级划分，明确行为分工，同时算法能够根据对搜索空间的实时状态进行学习，从而判定种群的离散程度，在不同离散度下对个体采用不同的寻优策略加快算法的收敛；通过引入情感因子，平衡算法的局部勘探和全局搜索能力，使一定的个体进行情感追踪移动行为，提高算法求解精度。将本文算法与4个现有算法在15个测试问题上进行实验对比，结果表明MMO_LTSGSO算法能够保存多个最优PS信息且不易陷入局部最优，综合性能较好。本文主要研究的是多模态双目标或三目标的优化问题，接下来我们将进一步对算法进行改进，使之能应用于更为复杂的高维超多目标的优化问题中。
基于空间学习和情感追踪的多模多目标群搜索算法
A Spatial Learning Based SGSO with Emotional Tracking for Multimodal Multi-objective Optimization
-
摘要: 为了解决多模态多目标优化问题，寻找与帕累托最优解等效的所有解，通过在基本的群搜索算法中引入社会行为，提出了一种新颖的基于空间学习机制和情感追踪行为的社会群搜索优化算法（MMO_LTSGSO）。首先，建立空间学习机制，根据学习到的个体自身位置与最佳个体位置的实时信息，对种群分布状态（离散态、聚合态）进行决策。当种群处于离散态时，采用追随和游走的方式增强算法空间探索能力；随着优化过程的进行，个体彼此影响交互，空间距离逐渐减小，此时种群逐渐聚合，采用动态步长的搜索策略更新个体位置，能实时勘探最优解周围的解，加快算法收敛速度。其次，引入了情感因子，使一定的个体沿其偏好方向进行情感追踪移动行为，防止算法陷入停滞状态，提高算法求解精度；采用特殊的拥挤距离计算方式和引导进化策略保证算法在决策空间和目标空间的双重多样性。最后，从理论上证明了该算法的收敛性；使用15个多模态多目标优化测试基准函数验证算法的性能，并将其与现有的几个多模多目标优化算法进行性能对比，实验结果验证了本文算法能够有效求解多模多目标优化问题。Abstract: In order to solve the multimodal multi-objective optimization problem and find all solutions equivalent to the Pareto optimal solution, this paper proposes a novel group search optimization algorithm (MMO_LTSGSO) based on spatial learning mechanism and emotion tracking behavior. Group intelligence calculation method that supports the workflow mode in a complex way. First, establish a spatial learning mechanism and make decisions on the distribution state (discrete state and concentrated state) of the population based on the real-time information of the learned individual's own position and the best individual position. When the population is in a discrete state, random walk is used to enhance the space exploration ability of the algorithm; as the optimization process progresses, individuals interact with each other, and the spatial distance gradually decreases. At this time, the population gradually aggregates, and the dynamic step search is used. The strategy updates individual positions; when the population is in a centralized state, the adaptive local exploration method is used to speed up the algorithm convergence. Second, the algorithm introduces the emotion factor, which enables certain individuals to follow their preferred direction of emotion tracking movement behavior, prevent the algorithm from falling into a stagnation state, and improve the speed of algorithm solving. Then a special non-dominated sorting method and guided evolution strategy are adopted to ensure the dual diversity of the algorithm in decision space and target space. Finally, the convergence of the algorithm is proved theoretically. 15 multimodal multi-objective optimization test benchmark functions are used to verify the performance of the algorithm, and the performance of the algorithm is compared with several existing multimodal multi-objective optimization algorithms. The experiments results verify that the proposed algorithm can effectively solve multimodal multi-objective optimization problems.
-
图 1 解在决策空间和目标空间的分布
Figure 1. Distribution of solutions in decision space and target space
图 5 MMO_LTSGSO在15个测试函数上的求得的PS与真实PS
Figure 5. The obtained PS by MMO_LTSGSO and the true PS on 15 test functions
图 6 5个算法在15个测试函数上的Friedman排名
Figure 6. Friedman ranks of the optimization comprehensive performance for the five algorithms
表 1 测试函数的多模性质
Table 1. Multimodal features of the test functions
Function Number of PS Overlap in every dimension MMF1 2 no MMF2 2 no MMF3 2 yes MMF4 4 no MMF5 4 no MMF6 4 yes MMF7 2 no MMF8 4 no MMF9 2 no MMF10 2(1 global+1 local) no MMF11 2(1 global+1 local) no MMF12 8(4 global+4 local) yes SYM-PART simple 9 yes SYM-PART rotate 9 yes Omni-test(n=3) 27 yes 
下载: 导出CSV
表 2 5个算法在15个多模多目标测试函数上的1/PSP值
Table 2. 1/PSP value of five algorithms on 15 multimodal multi-objective test functions
Test functions 1/PSP（mean±std） MMO_LTSGSO MO_Ring_PSO_SCD DN_NSGAII MMOEA_GD MMOPIO MMF1 0.0411±0.0013 0.0455±0.0019 0.0741±0.0200 0.0436±0.0028 0.0361±0.0018 MMF2 0.0177±0.0059 0.0283±0.0120 0.0577±0.1301 0.011±0.0044 0.0267±0.0065 MMF3 0.0148±0.0020 0.0223±0.0087 0.0477±0.0302 0.022±0.0048 0.0175±0.0054 MMF4 0.0222±0.0022 0.0251±0.0020 0.0554±0.0181 0.0217±0.0011 0.0195±0.0027 MMF5 0.0743±0.0051 0.0810±0.0041 0.1517±0.0198 0.0747±0.0032 0.0745±0.0048 MMF6 0.0658±0.0038 0.0679±0.0043 0.1143±0.0170 0.0660±0.0023 0.0658±0.0060 MMF7 0.0204±0.0008 0.0232±0.0017 0.0366±0.0095 0.0205±0.0021 0.0158±0.0017 MMF8 0.0621±0.0125 0.0598±0.0047 0.1236±0.1415 0.0590±0.0061 0.0743±0.0112 MMF9 0.0054±0.0003 0.0070±0.0004 0.0135±0.0081 0.0056±0.0002 0.0025±0.0001 MMF10 0.1599±1.5610 0.1029±0.0207 0.1030±3.1331 0.1118±0.1020 1.8053±2.2440 MMF11 0.1880±0.5616 0.1884±0.3425 1.4972±0.1490 0.1889±0.4118 1.6055±0.3832 MMF12 0.1428±0.5234 0.1433±0.5050 0.1954±0.6892 0.1731±0.5497 1.6757±0.4923 SYM_PART_simple 0.0777±0.0140 0.1443±0.0371 1.1423±1.3414 0.1248±0.0148 0.0778±0.0073 SYM_PART_rotated 0.0947±0.0190 0.1560±0.0459 2.2009±11.424 0.1351±0.0195 0.2210±0.3609 Omni_test 0.0870±0.0258 0.3086±0.0798 1.2623±0.3609 0.9491±0.0123 0.3950±0.0598
下载: 导出CSV
表 3 5个算法在15个多模多目标测试函数上的1/Hv值
Table 3. 1/Hv value of five algorithms on 15 multimodal multi-objective test functions
Test functions 1/HV（mean±std） MMO_LTSGSO MO_Ring_PSO_SCD DN_NSGAII MMOEA_GD MMOPIO MMF1 1.1462±0.0002 1.1480±0.0003 1.1481±0.0015 1.1488±0.0035 1.1459±0.0004 MMF2 1.1629±0.0036 1.1707±0.0097 1.1590±0.0273 1.1967±0.0190 1.1686±0.0030 MMF3 1.1630±0.0032 1.1647±0.0060 1.1633±0.0177 1.1678±0.0131 1.1657±0.0044 MMF4 1.8552±0.0012 1.8585±0.0019 1.8567±0.0007 1.8594±0.0081 1.8556±0.0012 MMF5 1.1459±0.0003 1.1476±0.0006 1.1470±0.0013 1.1471±0.0041 1.1455±0.0003 MMF6 1.1461±0.0004 1.1476±0.0012 1.1475±0.0008 1.1462±0.0219 1.1463±0.0005 MMF7 1.1462±0.0004 1.1475±0.0004 1.1480±0.0012 1.1463±0.0011 1.1430±0.0001 MMF8 2.3752±0.0113 2.3889±0.0361 2.3762±0.0032 2.3834±0.0061 2.3756±0.0019 MMF9 0.1032±0.0003 0.1033±0.0003 0.1033±0.0003 0.1035±0.0002 0.1033±0.0009 MMF10 0.0777±0.0007 0.0791±0.0006 0.0778±0.0030 0.0820±0.0034 0.0779±0.0009 MMF11 0.0689±0.0001 0.0690±0.0003 0.0689±0.0014 0.0690±0.0001 0.0671±0.0001 MMF12 0.6360±0.0002 0.6373±0.0011 0.6357±0.0562 0.6596±0.0665 0.6368±0.0003 SYM_PART_simple 0.0601±0.0007 0.0604±0.0006 0.0601±0.0001 0.0591±0.0094 0.0601±0.0001 SYM_PART_rotated 0.0601±0.0001 0.0605±0.0007 0.0601±0.0002 0.0699±0.0091 0.0602±0.0002 Omni_test 0.0189±0.0002 0.0190±0.0001 0.0189±0.0008 0.0288±0.0008 0.0190±0.0004
下载: 导出CSV
表 4 5个优化算法在决策空间和目标空间的平均排名
Table 4. Average ranking of five optimization algorithms on decision space and objective space
Indicator 1/PSP 1/Hv Comprehensive MMO_LTSGSO 1.87 1.53 1.7 MO_Ring_PSO_SCD 3.47 3.93 3.7 DN_NSGAII 4.47 2.73 3.6 MMOEA_GD 2.73 4.13 3.43 MMOPIO 2.47 2.67 2.57
下载: 导出CSV
-
[1] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017 [2] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm[C]//Fifth Conference on Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Greece: IEEE, 2001: 95-100. [3] ZHANG Q, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. doi: 10.1109/TEVC.2007.892759 [4] COELLO COELLO C A, LECHUGA M S. MOPSO: A proposal for multiple objective particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation. USA: IEEE, 2002: 1051-1056. [5] YUE C T, QU B Y, LIANG J. A multi-objective particle swarm optimizer using ring topology for solving multimodal multi-objective problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(5): 805-817. doi: 10.1109/TEVC.2017.2754271 [6] LIANG J, YUE C T, QU B Y. Multimodal multi-objective optimization: A preliminary study[C]//2016 IEEE Congress on Evolutionary Computation (CEC). Canada: IEEE, 2016: 2454-2461. [7] KERSCHKE P, GRIMME C. An expedition to multimodal multi-objective optimization landscapes[C]//International Conference on Evolutionary Multi-Criterion Optimization. Germany: Springer, 2017: 329-343. [8] LIU Y, YEN G G, GONG D. A multi-modal multi-objective evolutionary algorithm using two-archive and recombination strategies[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(4): 660-674. doi: 10.1109/TEVC.2018.2879406 [9] LIANG J, XU W W, YUE C T. Multimodal multiobjective optimization with differential evolution[J]. Swarm and Evolutionary Computation, 2019, 44: 1028-1059. doi: 10.1016/j.swevo.2018.10.016 [10] HU Y, WANG J, LIANG J. A self-organizing multimodal multi-objective pigeon-inspired optimization algorithm[J]. Information Sciences, 2019, 62: 1-17. [11] YU K J, LIANG J J, QU B Y. Multiple learning backtracking search algorithm for estimating parameters of photovoltaic models[J]. Applied Energy, 2018, 226: 408-422. doi: 10.1016/j.apenergy.2018.06.010 [12] LIANG J, GUO Q Q, YUE C T. A Self-organizing multi-objective particle swarm optimization algorithm for multimodal multi-objective problems[C]//International Conference on Swarm Intelligence. UK: Springer, 2018: 550-560. [13] LYNN N, SUGANTHAN P N. Heterogeneous comprehensive learning particles warm optimization with enhanced exploration and exploitation[J]. Swarm and Evolutionary Computation, 2015, 24: 11-24. doi: 10.1016/j.swevo.2015.05.002 [14] LYNN N, SUGANTHAN P N. Ensemble particle swarm optimizer[J]. Applied Soft Computing, 2017, 55: 533-548. doi: 10.1016/j.asoc.2017.02.007 [15] QU B Y, SUGANTHAN P N, DAS S. A Distance-based locally informed particle swarm model for multimodal optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(3): 387-402. doi: 10.1109/TEVC.2012.2203138 [16] YAN L, LI G S, JIAO Y C. A performance enhanced niching multi-objective bat algorithm for multimodal multi-objective problems[C]// 2019 IEEE Congress on Evolutionary Computation (CEC). New Zealand: IEEE, 2019: 1275-1282. [17] FAN Q Q, YAN X F. Solving multimodal multiobjective problems through zoning search[C]// IEEE Transactions on Systems, Man, and Cybernetics: Systems. USA: IEEE, 2019: 1-12. [18] SHI R Z, LIN W, LIN Q Z. Multimodal multi-objective optimization using a density-based one-by-one update strategy[C]// 2019 IEEE Congress on Evolutionary Computation (CEC). New Zealand: IEEE, 2019: 295-301. [19] MAITY K, SENGUPTA R, SHA S. MM-NAEMO: Multimodal neighborhood-sensitive archived evolutionary many-objective optimization algorithm[C]//IEEE Congress on Evolutionary Computation. USA: IEEE, 2019: 286-294. [20] JI J Y, YU W J, CHEN W N. Solving multimodal optimization problems through a multiobjective optimization approach[C]//2017 Seventh International Conference on Information Science and Technology (ICIST). Vietnam: IEEE, 2017: 458-463. [21] CHENG R, JIN Y C, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791. doi: 10.1109/TEVC.2016.2519378 [22] FAN Q, LI N, ZHANG Y, et al. Zoning search using a hyper-heuristic algorithm[J]. Science China Information Sciences, 2019, 62(9): 1869-1919. [23] LIU X F, ZHAN Z H, GAO Y, et al. Coevolutionary particle swarm optimization with bottleneck objective learning strategy for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(4): 587-602. doi: 10.1109/TEVC.2018.2875430 [24] FENG X, XU H Y, WANG Y B, et al. The social team building optimization algorithm[J]. Soft Computer, 2019, 23(15): 6533-6554. doi: 10.1007/s00500-018-3303-x [25] MODLMEIER A P, LASKOWSKI K L, Brittingham H A, et al. Adult presence augments juvenile collective foraging in social spiders[J]. Animal Behavior, 2015, 109: 9-14. doi: 10.1016/j.anbehav.2015.07.033 -
点击查看大图
图(6)表(4)
计量
- 文章访问数: 296
- HTML全文浏览量: 260
- PDF下载量: 6
- 被引次数: 0