-
摘要: 图像描述(Image captioning)是一个融合了计算机视觉和自然语言处理这两个领域的研究方向, 本文为图像描述设计了一种新颖的显著性特征提取机制(Salient feature extraction mechanism, SFEM), 能够在语言模型预测每一个单词之前快速地向语言模型提供最有价值的视觉特征来指导单词预测, 有效解决了现有方法对视觉特征选择不准确以及时间性能不理想的问题. SFEM包含全局显著性特征提取器和即时显著性特征提取器这两个部分: 全局显著性特征提取器能够从多个局部视觉向量中提取出显著性视觉特征, 并整合这些特征到全局显著性视觉向量中; 即时显著性特征提取器能够根据语言模型的需要, 从全局显著性视觉向量中提取出预测每一个单词所需的显著性视觉特征. 本文在MS COCO (Microsoft common objects in context)数据集上对SFEM进行了评估, 实验结果表明SFEM能够显著提升基准模型 (baseline)生成图像描述的准确性, 并且SFEM在生成图像描述的准确性方面明显优于广泛使用的空间注意力模型, 在时间性能上也大幅领先空间注意力模型.Abstract: Image captioning is a research direction that combines computer vision and natural language processing. In this paper, a novel saliency feature extraction mechanism (SFEM) is designed to solve several key problems existing in current methods. It can quickly provide the most valuable visual features to the language model before which predict word. And it effectively solves the problems that the existing methods are inaccurate in selecting visual features and time-consuming. SFEM consists of global salient feature extractor and instant salient feature extractor: global salient Feature extractor extracts salient visual features from multiple local visual vectors and integrate these features into a global salient visual vector; the instant salient feature extractor can extract the saliency visual features required at each moment from the global saliency visual vector according to the needs of the language model. We evaluated SFEM on the MS COCO (Microsoft common objects in context) dataset. Experiments show that our SFEM can significantly improve the accuracy of baseline in caption generating. And SFEM is significantly better than the widely used spatial attention model in both the accuracy of generating caption and time performance.
-
Key words:
- Image captioning /
- salient feature extract /
- language model /
- encoder /
- decoder
-
在多数实际问题和工程应用中, 决策者需要同时使多个目标在决策空间内尽可能得到最佳优化, 即多目标优化问题(Multi-objective optimization problems, MOPs)[1]. 在MOPs中, 使算法快速有效地收敛在Pareto最优解集中并使得到的非支配解在Pareto前沿中保持均匀分布是衡量多目标优化算法性能的重要指标之一, 即算法的收敛性和多样性. 过度强调算法的收敛性会导致粒子聚集, 陷入局部最优; 过度增强算法多样性会导致算法收敛速度慢, 影响最终非支配解集的收敛性[2]. 因此, 平衡算法的收敛性和多样性是研究MOPs的重要课题之一[3-5].
粒子群优化算法因为易于实现和计算效率高等特点, 在单目标优化问题上得到广泛应用. 当粒子群优化应用于多目标优化问题时, 即多目标粒子群优化(Multi-objective particle swarm optimization, MOPSO). 由于MOPs中没有真正意义上的最优解, 所以MOPSO算法的全局最优粒子gbest和个体最优粒子pbst需要采取特定的策略进行选取, 并且由于MOPSO算法较快的收敛速度, 在算法学习过程中, 易使所得到的非支配解集迅速丧失多样性[6].
为解决上述问题, 学者们相继提出了一些改进的MOPSO算法. Coello等[7]提出一种基于自适应网格的多目标粒子群优化算法, 采用自适应网格技术对外部存档进行维护, 指导粒子更新, 并对粒子以及粒子的飞行区域实施变异. 虽然算法相比于传统多目标进化算法在MOPs问题上表现出一定优势, 但在解决多局部前沿的复杂MOPs问题时存在困难, 且非支配解多样性较差. Raquel等[8]提出一种基于拥挤距离的MOPSO (An effective use of crowding distance in MOPSO, cdMOPSO)算法, 采用目标空间的拥挤距离评估非支配解的密集程度, 并据此来选取全局最优粒子和保持外部存档中解的分布性, 但算法仍存在收敛性不足的问题. 为解决这个问题, Yen等[9]提出一种动态多子群的多目标粒子群优化算法, 算法将种群分为多个子群, 通过动态调整子群大小从种群角度平衡算法的探索能力和开发能力, 实验结果表明算法性能得到改善.
与上述通过支配关系确定搜索机制的MOPSO算法不同, Peng等[10]基于分解的多目标进化算法 (Multi-objective evolutionary algorithm based on decomposition, MOEA/D)的分解框架, 将MOPs分解为多个单目标优化问题, 用粒子群优化的搜索方法替代遗传算子, 从而提出一种MOPSO算法, 虽然其维护了一个外部存档存储各单目标优化问题的全局最优粒子, 但并未对粒子群优化的搜索机制进行优化, 算法综合性能不足. Martinez等[11]提出一种多目标粒子群优化器, 算法提出了一种重新初始化策略来保持群的多样性, 当粒子存在超过一定代数时将会重新初始化, 以此来提高种群多样性和避免陷入局部极值, 但由于用分解替换了占优关系, 算法在求解一些复杂MOPs时, 不能覆盖整个Pareto前沿. 为解决这个问题, Dai等[12]提出一种基于分解的多目标粒子群优化算法, 根据一系列预先定义的方向向量将整个目标空间分解为一系列子空间, 并让每个子空间都有至少一个解来维护解集的多样性, 进一步提升MOPSO算法解决MOPs的能力.
学者们还提出了其他改进方法提升MOPSO算法的性能. Hu等[13]提出一种基于平行单元坐标系的自适应多目标粒子群优化(Adaptive MOPSO based on parallel cell coordinate, pccsAMOPSO)算法, 将目标空间的Pareto前沿变换为平行单元坐标形式的二维网格, 采用种群的熵作为反馈信息, 设计具有自适应调节探索和开发过程的进化策略, 使算法的收敛性和多样性都得到了提升. Kumar等[14]提出一种自学习的多目标粒子群优化算法, 在粒子速度和位置更新上采用4种运算方式, 不同方式对应不同的学习来源, 独立提高每个粒子搜索的有效性. 但目前多数改进的MOPSO算法仅依靠一种搜索策略更新粒子的位置和速度, 没有考虑不同性能粒子的搜索情况, 在求解复杂多目标问题时, 算法收敛性和多样性不足.
为解决上述问题, 进一步提升MOPSO算法的性能, 本文提出一种基于种群分区的多策略自适应多目标粒子群优化(Multi-strategy adaptive multi-objective particle swarm optimization based on swarm partition, spmsAMOPSO)算法. 对MOPSO算法的改进在于: 1)提出一种基于种群分区的多策略全局最优粒子选取方法, 并基于种群分区思想, 提出一种多策略的变异方法, 提升粒子探索和开发能力; 2)为提升个体最优粒子选取的可靠性, 提出一种带有记忆区间的个体最优粒子选取方法; 3)根据算法环境, 自适应调整粒子探索和开发过程, 并采用双性能测度的融合指标维护外部存档, 平衡算法的收敛性和多样性. 实验结果表明, 相比一些其他多目标优化算法, 本文算法在收敛性和多样性上具有一定优势.
1. 多目标优化问题和粒子群优化算法
1.1 多目标优化问题
多目标优化问题的数学模型可描述为:
$$ \min y({\boldsymbol{x}}) = ({{f}_{1}}({\boldsymbol{x}}),{{f}_{2}}({\boldsymbol{x}}),\cdots,{{f}_{M}}({\boldsymbol{x}})), {\boldsymbol{x}}\in {{\Omega }^{n}} $$ (1) 式中,
${\boldsymbol{x}} = (x_{1},x_{2},\cdots,x_{n})$ 为问题的决策变量;$ \Omega^{n} $ 为决策变量可行解空间;$y:{\Omega^{n}}\to {{{\bf{R}}}^{M}}$ 是决策空间到目标空间的映射;$ M $ 为目标空间维数.有关求解MOPs的Pareto最优定义如下[14]:
1) Pareto支配: 对任意的
$ {{\boldsymbol{x}}_{a}},{{\boldsymbol{x}}_{b}}\in {{\Omega }^{n}} $ , 是问题的两个可行解. 式中,${\boldsymbol{x}}_{a} = ({x_{a,1}},{x_{a,2}},\cdots,{x_{a,n}}),$ ${\boldsymbol{x}}_{b} = ({x_{b,1}},{x_{b,2}},\cdots,{x_{b,n}}),$ 当且仅当:$$ \left\{\begin{aligned} &\forall i\in [1,M],\;\;\;\;\;\;\;{{f}_{i}}({{\boldsymbol{x}}_{a}})\le {{f}_{i}}({{\boldsymbol{x}}_{b}})\\ &\wedge \exists j\in [1,M],\;\;{{f}_{j}}({{\boldsymbol{x}}_{a}})<{{f}_{j}}({{\boldsymbol{x}}_{b}}) \end{aligned}\right.$$ (2) 则称
$ {\boldsymbol{x}}_{a} $ 支配$ {\boldsymbol{x}}_{b} $ (记为$ {{\boldsymbol{x}}_{a}}\prec {{\boldsymbol{x}}_{b}} $ ).2) Pareto最优解: 对任意的
$ {\boldsymbol{x}}'\in\Omega^{n} $ 为问题的可行解, 当且仅当:$$ \neg \exists {\boldsymbol{x}}\in \Omega ^{n},\;\;{\boldsymbol{x}}\prec {\boldsymbol{x}}' $$ (3) 则称
$ {\boldsymbol{x}}' $ 为Pareto最优解.3) Pareto最优解集: 对给定的MOPs, Pareto最优解集定义为:
$$ P^{*} = \{{\boldsymbol{x}}\in \Omega ^{n}|\neg \exists {\boldsymbol{x}}'\in \Omega ^{n} ,{\boldsymbol{x}}'\prec {\boldsymbol{x}}\} $$ (4) 4) Pareto前沿: 由
$ P^{*} $ 的定义, Pareto前沿(Pareto front, PF)可定义为:$$ PF = \{y = (f_{1}({\boldsymbol{x}}),f_{2}({\boldsymbol{x}}),\cdots,f_{M}({\boldsymbol{x}}))|{\boldsymbol{x}}\in P^{*}\} $$ (5) 1.2 标准粒子群算法
粒子群算法是由Kennedy等[15]提出的一种基于种群搜索的进化计算技术. 种群中粒子
$ i $ 的速度${\boldsymbol{v}}_{i}$ 和位置${\boldsymbol{x}}_{i}$ 的更新方法分别为:$$ \begin{split} v_{i,d}^{t+1} =\;& w_{p}^{t}v_{i,d}^{t}+c_{1}^{t}rand_{1}\left(pbest_{i,d}^{t}-x_{i,d}^{t}\right)+\\ &c_{2}^{t}rand_{2}\left(gbest_{i,d}^{t}-x_{i,d}^{t}\right) \end{split} $$ (6) $$ x_{i,d}^{t+1} = x_{i,d}^{t}+v_{i,d}^{t+1} $$ (7) 式中,
$d = 1,2,\cdots,D$ ,$ D $ 为问题的决策空间维数;$ v_{i,d}^{t} $ 和$ x_{i,d}^{t} $ 分别为$ t $ 时刻粒子$ i $ 第$ d $ 维变量的速度和位置;$ pbest_{i,d}^{t} $ 和$ gbest_{i,d}^{t} $ 分别为$ t $ 时刻粒子$ i $ 的个体最优粒子和全局最优粒子的第$ d $ 维变量;$ w_{p}^{t} $ 为$ t $ 时刻算法惯性权重,$ c_{1}^{t} $ 和$ c_{2}^{t} $ 为$ t $ 时刻算法学习因子,$ rand_{1} $ 和$ rand_{2} $ 为[0, 1]区间上均匀分布的随机数.2. 基于种群分区的多策略自适应多目标粒子群优化算法
MOPSO算法因其特殊的搜索机制和快速的收敛速度, 需要对算法的参数调整、全局最优粒子选取、个体最优粒子选取、外部存档维护以及粒子变异操作等部分制定策略以引导粒子搜索[7]. 本文在全局最优粒子选取和变异操作部分, 提出一种基于种群分区的多策略改进方法, 并提出一种带有记忆区间的个体最优粒子选取方法, 结合自适应参数调整以及使用融合指标的外部存档维护策略, 进一步提升MOPSO算法性能. 本文spmsAMOPSO算法的整体结构如图1所示, 通过算法的参数调整、最优粒子选取、变异以及外部存档维护等部分之间的协同, 共同指导粒子寻优过程, 提升算法综合性能.
2.1 自适应调整惯性权重和学习因子
对于MOPSO算法, 由于算法迭代过程中, 其环境是实时变化的, 为提升粒子探索和开发能力, 本文根据算法环境变化调整惯性权重
$ w_{p} $ 以及学习因子$ c_{1} $ 和$ c_{2} $ , 达到算法参数精细化调控的目的.当算法搜索到的非支配解需要加入外部存档时, 计算其对外部存档中解的支配程度, 得到粒子的收敛性贡献[16]:
$$ Cv({\boldsymbol{x}}_{n,i},rep) = \mathop {\max }\limits_{{\boldsymbol{x}}_{r}\in rep} \rho({{\boldsymbol{x}}_{n,i}},{\boldsymbol{x}}_{r}) $$ (8) 式中,
$ {\boldsymbol{x}}_{n,i} $ 为算法寻优所得到的第$ i $ 个非劣解;$ {\boldsymbol{x}}_{r} $ 为外部存档中存储的非支配解;$ rep $ 为算法外部存档;$ \rho({{\boldsymbol{x}}_{n,i}},{\boldsymbol{x}}_{r}) $ 为$ {\boldsymbol{x}}_{n,i} $ 对$ {\boldsymbol{x}}_{r} $ 的支配程度, 计算方法如下:$$ \rho ({{\boldsymbol{x}}_{n,i}},{\boldsymbol{x}}_{r}) = \left\{ \begin{aligned} &\dfrac{1}{M}\displaystyle\sum_{j = 1}^{M}{\dfrac{|f_{j}({\boldsymbol{x}}_{n,i}) - f_{j}({\boldsymbol{x}}_{r})|}{(f_{j,\max } - f_{j,\min })}},\;{\boldsymbol{x}}_{n,i}\prec {\boldsymbol{x}}_{r} \\ &0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{其他}\qquad\; \end{aligned} \right.$$ (9) 式中,
$ M $ 为目标个数;$f_{j,{\rm{max}}}$ 和$f_{j,{\rm{min}}}$ 分别为外部存档中非支配解在第$ j $ 个目标上的最大值和最小值. 若$ t $ 时刻算法搜索到$ n_{p} $ 个非支配解, 则算法的环境检测参数$ Ap $ 定义为:$$ Ap^{t} = \mathop {\max }\limits_{i = 1,2,\cdots,{n_p}} {\mkern 1mu} Cv({{\boldsymbol{x}}_{n,i}},rep) $$ (10) 粒子对外部档案的收敛性贡献反映算法当前的收敛状态, 当
$ Ap $ 较大时, 种群处于探索阶段, 应保持其全局搜索能力, 随着$ Ap $ 逐渐减小, 种群逐渐达到收敛, 应加强局部搜索, 当$ Ap $ 趋于0时, 表明种群达到收敛稳定状态.由文献[17]可知, 较小的惯性权重
$ w_{p} $ 和学习因子$ c_{1} $ 以及较大的学习因子$ c_{2} $ 有利于算法收敛, 较大的$ w_{p} $ 和$ c_{1} $ 以及较小的$ c_{2} $ 有利于增强算法多样性. 为避免参数调整影响算法搜索连贯性, 本文采用增量式参数调节方法:$$ {\boldsymbol{\xi}}^{t} = \left\{ {\begin{array}{*{20}{l}} {\begin{array}{*{20}{l}} {{\boldsymbol{\xi}}^{t-1}},\\ {{\boldsymbol{\xi}}^{t-1}+{\boldsymbol{\gamma}} \Delta Ap},\\ {{\boldsymbol{\xi}}^{t-1}-{\boldsymbol{\gamma}} \Delta Ap}, \end{array}}&{\begin{array}{*{20}{l}} {\Delta Ap = 0 }\\ {\Delta Ap>0 }\\ {\Delta Ap<0 } \end{array}} \end{array}} \right. $$ (11) 式中,
$ {\boldsymbol{\xi}}^{t} = [w_{p}^{t},c_{1}^{t},c_{2}^{t}]^{\rm{T}} $ , 由$ t $ 时刻$ w_{p} $ 、$ c_{1} $ 和$ c_{2} $ 的值构成;$ {\boldsymbol{\gamma}} = [\lambda_{w_{p}},\lambda_{c_{1}},-\lambda_{c_{2}}]^{\rm{T}} $ , 由$ w_{p} $ 、$ c_{1} $ 和$ c_{2} $ 的增量步长因子构成;$ \Delta Ap $ 为收敛性贡献增量, 计算方法为$\Delta Ap{ \;=\; }A{{p}^{t}}-A{{p}^{t-1}}$ ; 设置$ w_{p} $ 的上下限分别为0.9和0.4,$ c_{1} $ 和$ c_{2} $ 的变化范围均为区间[0.5, 2.5][18].2.2 基于种群分区的多策略全局最优粒子选取
全局最优粒子
$(gbest)$ 选取是影响MOPSO算法收敛性和多样性的重要问题. 本文采用不同的评价指标分别选取促进算法收敛的全局最优粒子$(c{\text{-}} gbest)$ 和增强算法多样性全局最优粒子$(d{\text{-}}gbest),$ 并根据粒子性能将种群划分为多个区域, 对不同区域粒子制定不同的$ gbest $ 选取策略.2.2.1 c-gbest和d-gbest的选取方法
为保证算法的收敛性, 在算法寻优过程中选取外部存档中收敛程度最好的粒子做为算法的c-gbest.
本文采用粒子的平均排名和全局损害作为粒子的收敛性评价指标.
粒子平均排名(Average ranking, AR)的计算方法为:
$$ AR({{\boldsymbol{x}}_{i}}) = \displaystyle\sum\limits_{m = 1}^{M}{{{r}_{m}}({{\boldsymbol{x}}_{i}})} $$ (12) 式中,
$ r_{m}({\boldsymbol{x}}_{i}) $ 为粒子$ i $ 在第$ m $ 个目标变量上的排名;$ M $ 为目标个数.粒子全局损害(Global detriment, GD)的计算方法如下:
$$ GD({{{\boldsymbol{x}}}_{i}}) = \sum\limits_{{{{\boldsymbol{x}}}_{i}}\ne {{{\boldsymbol{x}}}_{j}}}{\sum\limits_{m = 1}^{M}{\max ({{f}_{m}}({{{{\boldsymbol{x}}}}_{i}})-{{f}_{m}}({{\boldsymbol{x}}_{j}}),0)}} $$ (13) 式中,
$ f_{m}({\boldsymbol{x}}_{i}) $ 为粒子$ i $ 在第$ m $ 个目标上的适应度值;$ GD({\boldsymbol{x}}_{i}) $ 表示粒子$ i $ 比其他粒子在目标上的劣势.由于通过AR指标选取最优粒子时容易使粒子聚集在Pareto前沿的边缘, 而GD指标容易排除Pareto前沿中的端点粒子[6]. 将上述两个指标结合, 改善评价方式缺陷:
$$ FR({{\boldsymbol{x}}_{i}}) = {{\eta }_{1}}AR({{\boldsymbol{x}}_{i}})+{{\eta }_{2}}GD({{\boldsymbol{x}}_{i}}) $$ (14) 式中,
$ \eta_{1} $ 和$ \eta_{2} $ 为区间[0, 1]之间的常数, 用于确定指标AR和GD的权重, 其取值分别为:$ \eta_{1} = 0.4 $ 、$ \eta_{2} = 0.6 $ , 具体讨论分析见第3.2.1节. Fusion ranking (FR)指标有利于目标解的序列和个体之间的相对信息结合, 从而更全面地评估解空间内个体的收敛程度. 由式(12) ~ (14)计算外部存档中各粒子的融合排序FR指标, 选取FR指标最小的粒子作为算法的c-gbest.为保证非支配解集的多样性, 在算法寻优过程中应引导粒子向外部存档中非支配解较为稀疏的区域飞行, 本文采用粒子的拥挤距离作为算法多样性全局最优粒子(d-gbest)的选取标准.
粒子
$ i $ 与粒子$ j $ 之间的欧氏距离为:$$ dis({{\boldsymbol{x}}_{i}},{{\boldsymbol{x}}_{j}}) = {\sqrt{{\displaystyle\sum\limits_{m = 1}^{M}({{f}_{m}}({{\boldsymbol{x}}_{i}})-{{f}_{m}}({{\boldsymbol{x}}_{j}}))^{2}}}} $$ (15) 为避免个别极端粒子影响粒子密度估计, 本文采用局部距离作为粒子的密度评价指标, 取粒子
$ i $ 距离最近的$ S $ 个粒子之间距离的平均值作为粒子$ i $ 的拥挤距离, 即:$$ {{d}_{s}}({{\boldsymbol{x}}_{i}}) = rank(dis({{\boldsymbol{x}}_{i}})) $$ (16) $$ LD({{\boldsymbol{x}}_{i}}) = \dfrac{1}{S}\displaystyle\sum\limits_{s = 1}^{S}{{{d}_{s}}({{\boldsymbol{x}}_{i}})} $$ (17) 局部拥挤距离(Locality crowding distance, LD)为反映粒子分布情况的指标, 粒子的LD指标越大, 表明粒子分布越稀疏. 根据式(15) ~ (17)计算外部存档中各粒子的LD指标, 选取LD指标最大的粒子作为算法的d-gbest.
2.2.2 种群分区及各区域粒子的
${\boldsymbol{ gbest}}$ 选取方法为增强粒子探索和开发能力, 并根据算法环境自适应调整种群探索和开发过程, 扩大粒子搜索区域的同时保持算法收敛性和多样性的平衡. 本文通过粒子收敛程度将种群中粒子划分为3个区域, 根据不同区域粒子的特征, 提出一种多策略的
$ gbest $ 选取方法.根据种群中各粒子的FR指标大小, 得到每个粒子基于指标FR的种群内排名:
$$ FR{{s}^{t}} = rank(FR(po{{p}^{t}})) $$ (18) 根据每个粒子的群内排名FRs, 确定各粒子的所属区域:
$$ region({{x}_{i}}) = \left\{ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{l}} {{\rm{I}}\;{\text{区}}},\\ {{\rm{II}}\;{\text{区}}},\\ {{\rm{III}}\;{\text{区}}}, \end{array}}&{\begin{array}{*{20}{l}} {FRs({{\boldsymbol{x}}_{i}})<\alpha}\\ {\alpha \leq FRs({{\boldsymbol{x}}_{i}})<\beta}\\ {FRs({{\boldsymbol{x}}_{i}})\geq \beta} \end{array}} \end{array}} \right. $$ (19) 式中,
$ \alpha $ 和$ \beta $ 均为正常数, 通过确定$ \alpha $ 和$ \beta $ 的值, 将种群划分为3个区域, 分区参数选取分别为:$ \alpha = 0.2N $ ,$ \beta = 0.8N $ ,$ N $ 为种群粒子个数, 分区参数的取值对算法影响分析见第3.2.2节. 图2给出了种群各区域粒子的划分情况.根据各区域内粒子的不同特征, 制定一种多策略的
$ gbest $ 选取方案:1)对于I区粒子, 其在种群中具有较好的收敛性, 为保持算法搜索到非支配解的多样性, 使I区粒子选取
$ d{\text{-}}gbest $ 作为全局最优粒子指导其飞行.2)对于II区粒子, 为平衡算法的收敛性和多样性, 使种群能够探索更多区域, 使II区粒子根据算法环境进行全局最优粒子的选取, 由第2.1节中的粒子收敛贡献度对算法当前环境进行估计, 根据算法环境确定粒子选取c-gbest或d-gbest作为
$ gbest $ 的概率:$$ gbest_{i}^{t} = \left\{ {\begin{array}{*{20}{l}} {c{\text{-}}gbest^{t}},&{rand<Ap^{t}}\\ {d{\text{-}}gbest^{t}},&{其他} \end{array}} \right. $$ (20) 由式(20)使II区粒子能够根据算法当前环境进行自适应探索和开发. 当Ap较大时, 为保证算法收敛性, 使粒子有较大概率选取c-gbest作为gbest指导其飞行; 当Ap逐渐减小时, 为增强算法的多样性, 应使粒子有较大概率选取d-gbest作为gbest.
3)对于III区粒子, 由于其在种群中性能较差, 对种群中的其他粒子的飞行没有太大贡献, 为提升粒子的开发能力, 保证算法收敛性, 使III区粒子选取c-gbest作为全局最佳粒子指导其飞行.
通过上述多策略的gbest选取方法, 使算法能够根据不同区域的粒子性能和算法环境, 选取c-gbest或d-gbest作为全局最优粒子, 有效提升算法的收敛性和多样性, 增强粒子探索和开发能力.
2.3 基于种群分区的多策略高斯变异
由于MOPSO算法具有快速的收敛过程, 算法易发生早熟收敛, 过早结束搜索过程, 陷入局部最优. 为解决这个问题, 在粒子位置更新时, 对部分粒子加入扰动, 使算法跳出局部最优, 扩大粒子搜索区域[19]. 基于种群分区, 针对不同区域粒子的性能, 提出一种多策略的变异方法:
1)若粒子
$ i $ 位于I区, 表明粒子$ i $ 距离真实Pareto前沿较近, 为避免种群产生退化, 保留种群中的精英个体, 粒子$ i $ 不进行变异操作;2)若粒子
$ i $ 位于II区, 则其具有较好的性能, 可以通过较少的迭代次数飞行至真实Pareto前沿附近; 若$ \delta <{{p}_{m}} $ , 将粒子$ i $ 向d-gbest方向进行变异, 增强算法多样性. 变异方法如下:$$ \begin{split} x_{i,d} =\;& x_{i,d}+\delta (x_{\max ,d}-x_{\min ,d})(d{\text{-}}gbest_{d}-x_{i,d})\times\\ &\exp \left(-\left(\dfrac{d{\text{-}}gbest_{d}-x_{i,d}}{\sigma }\right)^{2}\right) \\[-15pt] \end{split} $$ (21) 3)若粒子i位于III区, 则粒子性能较差, 距离真实Pareto前沿较远, 优先考虑增强粒子的收敛性; 若
$ \delta <(1-p_{m}) $ , 将粒子i向c-gbest方向进行变异:$$ \begin{split} x_{i,d} =\;& x_{i,d}+\delta (x_{\max ,d}-x_{\min ,d})(c{\text{-}}gbest_{d}-x_{i,d})\times\\ &\exp \left(-\left(\frac{c{\text{-}}gbest_{d}-x_{i,d}}{\sigma }\right)^{2}\right)\\[-15pt] \end{split} $$ (22) 式中,
$ \delta $ 为区间[0, 1]之间的随机数;$ d $ 为区间[1,$ D $ ]之间的随机整数,$ D $ 为问题的决策空间维数;$x_{{\rm{max}},d}$ 和$x_{{\rm{min}},d}$ 分别为$ d $ 维决策空间上的最大值和最小值;$ p_{m} $ 为粒子变异因子, 取值为${{p}_{m}} = 0.25+ (t/2T)$ ;$ \sigma $ 为高斯函数方差, 根据算法迭代次数更新:$ \sigma = \sigma _{0}^{2}\exp (-(t/T)) $ ; 方差$ \sigma $ 控制变异范围, 随迭代次数增加, 使粒子的变异范围越来越小, 保证算法迭代后期粒子的开发能力.上述变异方法具有以下2个优点: 1)算法能够根据粒子位置进行不同程度的变异, 使算法跳出局部最优的同时避免对粒子搜索产生太大干扰, 保持算法搜索连贯性. 2)根据不同区域粒子的性能差异, 制定不同的变异策略, 扩大粒子的搜索区域, 增强粒子的探索和开发能力.
2.4 带有记忆区间的个体最优粒子选取方法
合理选择个体最优粒子(pbest)有助于提高种群对局部空间的开发能力. 多数MOPSO算法均采用一个外部库来存储粒子的
$ pbest $ , 当粒子位置$ x_{i} $ 受${\boldsymbol{pbest}}_{i}$ 支配时,${\boldsymbol{pbest}}_{i}$ 保持, 当${\boldsymbol{x}}_{i}$ 支配${\boldsymbol{pbes}}t_{i}$ 时, 将${\boldsymbol{pbest}}_{i}$ 更新为粒子当前位置${\boldsymbol{x}}_{i}$ , 两者无支配关系时, 采用随机方法进行选取. 这种方法虽然计算简单, 但当${\boldsymbol{x}}_{i}$ 与${\boldsymbol{pbest}}_{i}$ 无支配关系时, 选取的$ pbest $ 不能有效指导粒子的飞行方向, 易导致算法停滞[20].基于上述问题, 本文提出一种带有记忆区间的
$ pbest $ 选取方法, 在算法迭代过程中, 每个粒子具有一个外部存储库, 存储粒子最近几次迭代所经过的位置, 形成记忆区间:$$ {\boldsymbol{Me}}_{i}^{t} = [{\boldsymbol{x}}_{i}^{t-u},{\boldsymbol{x}}_{i}^{t-u+1},\cdots,{\boldsymbol{x}}_{i}^{t-1},{\boldsymbol{x}}_{i}^{t}] $$ (23) 式中,
$ {\boldsymbol{x}}_{i}^{t} $ 为粒子$ i $ 第$ t $ 次迭代时的位置;$ u $ 为粒子的记忆区间长度.根据第2.2.1节中粒子的融合排序方法, 计算记忆区间中各位置的FR指标, 选取FR指标最小的位置作为粒子
$ i $ 下一次迭代时的$ pbest $ :$$ {\boldsymbol{pbest}}_{i}^{t+1} = \mathop {\min }\limits_{i = 1,2,\cdots,n} {\mkern 1mu} (FR({\boldsymbol{Me}}_{i}^{t})) $$ (24) 当记忆区间饱和时, 需要制定策略对记忆区间进行维护, 图3以2个粒子为例, 给出了粒子的记忆区间更新过程.
由图3可以看出, 粒子记忆区间更新存在两种情况: 1)若存储位置达到记忆区间最大值, 则将记忆中最早一次迭代时的位置遗忘, 即
$ {\boldsymbol{x}}_{i}^{t-u} $ . 2)若$ {\boldsymbol{x}}_{i}^{t-u} $ 为最优的粒子位置, 则按时间顺序向后, 将相邻的一个位置遗忘. 即:$$ {\boldsymbol{Me}}_{i}^{t+1} = \left\{ {\begin{array}{*{20}{l}} & \left[{\boldsymbol{x}}_{i}^{t-u},{\boldsymbol{x}}_{i}^{t-u+2},\cdots,{\boldsymbol{x}}_{i}^{t}\right],& {\boldsymbol{pbest}}_{i}^{t+1} = {\boldsymbol{x}}_{i}^{t-u}\\ & \left[{\boldsymbol{x}}_{i}^{t-u+1},{\boldsymbol{x}}_{i}^{t-u+2},\cdots,{\boldsymbol{x}}_{i}^{t}\right],& 其他 \end{array}} \right.$$ (25) 2.5 基于双性能测度融合指标的外部存档维护
算法在迭代过程中将非支配解存入外部存档中, 随着算法迭代次数增加, 非支配解个数随之增加, 当达到外部存档的最大容量时, 需要对外部存档进行维护. 多数MOPSO算法在进行外部存档维护时, 采用粒子的分布性能指标作为判断粒子性能的标准, 将密度最大的粒子进行删除. 这种方法虽然能够保持外部档案中非支配解的多样性, 但可能会删除外部存档中收敛性较好的非支配解, 导致种群产生退化, 影响粒子开发能力[21]. 因此, 在进行外部存档维护时不应将粒子密度作为外部存档维护的唯一性能指标, 还应考虑到粒子的收敛性.
根据粒子的收敛性指标
$ FR $ 和粒子的分布性指标$ LD $ , 采用融合的评价指标判断外部存档中粒子的综合性能:$$ CR({{x}_{i}}) = \dfrac{FR({{\boldsymbol{x}}_{i}})}{LD({{\boldsymbol{x}}_{i}})} $$ (26) 由式(12)和式(14)可知, 粒子FR指标越小, 粒子收敛性越好, LD指标越大, 粒子分布性越好. 由式(26)可以看出, 粒子的综合排序(Comprehensive ranking, CR)指标不仅能够反映粒子的收敛程度而且包含了粒子的分布情况, 粒子的CR指标越小, 表明粒子的综合性能越好. 因此, 当算法搜索到的非支配解个数超过外部存档的最大容量时, 将外部存档中CR指标较大的粒子删除.
3. 实验分析
3.1 性能评价指标
为有效评价算法的收敛性和多样性, 本文采用反世代距离(Inverted generational distance, IGD)、间隔指标(Spacing, SP)、出错比率(Error ratio, ER) 和计算时间, 分别对算法性能进行评价.
1) IGD: IGD是度量真实Pareto前沿与算法获得的近似Pareto前沿之间的距离指标[13]. IGD值越小, 表明算法获得的近似Pareto前沿的收敛性和多样性越好, 越接近真实Pareto前沿, 其计算方法为:
$$ IGD(PF,PF^*) = \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^{n}{\min dis(P{{F}_{i}},PF^*)} $$ (27) 式中,
$ PF $ 为多目标算法所求得的Pareto前沿;$ PF^* $ 为真实Pareto前沿的一组采样点;$ n $ 为Pareto前沿中非支配解个数.2) SP: 用于度量每个解到其他解最小距离的标准差, 是衡量一个范围内邻近解差异的重要指标[22]. SP值越小, 表明解集分布越均匀, 其计算方法为:
$$ SP = \sqrt{\frac{1}{n-1}\sum\limits_{i = 1}^{n}{{{(\bar{d}-{{d}_{i}})}^{2}}}} $$ (28) 式中,
$ d_{i} $ 为第$ i $ 个非支配解与其他解之间最小的欧氏距离;$ \bar{d} $ 为所有$ d_{i} $ 的平均值.3) ER: 用来说明最优解的百分比[7]. ER越小, 所得非支配解在真实Pareto前沿中占比越高, 其计算方法为:
$$ ER = \dfrac{1}{n}\sum\limits_{i = 1}^{n}{{{e}_{i}}} $$ (29) 式中,
$ e_{i} $ 取值方法为: 若第$ i $ 个非支配解在真实Pareto前沿中, 则$ e_{i} = 0 $ , 否则$ e_{i} = 1 $ .4)计算时间
$ t $ : 计算时间是多目标优化算法的重要性能评价指标之一[23], 相同实验平台下算法的计算时间能够表征各算法的计算复杂度.3.2 参数取值和分析
本节通过本文算法在不同参数取值方案下对ZDT3和DTLZ2测试函数的实验, 说明参数的取值方法. 实验基本参数设置: 种群粒子数量为100, 外部存档最大容量为200, 粒子记忆区间长度为
$ u = 5 $ , 粒子拥挤距离中$ S = 4 $ , 变异策略中高斯函数的方差初始值$ \sigma_{0} = 0.8 $ .3.2.1 融合收敛性指标
${\boldsymbol{FR}}$ 的权重${\boldsymbol{\eta_{1} }}$ 和${\boldsymbol{\eta_{2}}}$ 由式(14)所描述的融合收敛性指标
$ FR $ 的权重$ \eta_{1} $ 和$ \eta_{2} $ 的取值对粒子的收敛性评价产生影响, 进而影响算法性能, 合适的$ \eta_{1} $ 和$ \eta_{2} $ 取值能够有效对粒子进行分区, 提升算法开发能力. 本节通过多种参数取值下的实验, 说明$ \eta_{1} $ 和$ \eta_{2} $ 的取值原因. 选取7种参数取值方案:Case 1:
$\eta_{1} = 0.2,$ $\eta_{2} = 0.8;$ Case 2:
$\eta_{1} = 0.3,$ $\eta_{2} = 0.7;$ Case 3:
$\eta_{1} = 0.4,$ $\eta_{2} = 0.6;$ Case 4:
$\eta_{1} = 0.5,$ $\eta_{2} = 0.5;$ Case 5:
$\eta_{1}= 0.6,$ $\eta_{2} = 0.4;$ Case 6:
$ \eta_{1} = 0.7 ,$ $ \eta_{2} = 0.3; $ Case 7:
$ \eta_{1} = 0.8 ,$ $ \eta_{2} = 0.2 .$ 分别对两目标问题ZDT3和三目标问题DTLZ2进行实验, 测试ZDT3问题时, 每20次迭代进行一次IGD指标评价, 测试DTLZ2问题时, 每30次迭代进行一次IGD指标评价, 实验结果如图4所示.
图 4$\eta_{1}$ 和$\eta_{2}$ 的不同取值方案下IGD指标变化Fig. 4 IGD metric changes of different$\eta_{1}$ and$\eta_{2}$ value schemes由图4可以看出, 在7种参数取值方案中, 算法在Case 3 ~ Case 5的取值方案下, 性能较好, 即
$ \eta_{1} $ 和$ \eta_{2} $ 的取值大小接近时, 算法能够获得良好的性能. 这是由于粒子平均排名AR和粒子全局损害GD的计算方法造成的. 粒子收敛性融合指标FR由AR和GD的加权和构成, 种群中粒子个数为100时, 粒子的AR指标略大于GD指标, 当$ \eta_{1} $ 的取值远大于$ \eta_{2} $ 时,$ GD $ 指标在粒子收敛性评价中几乎被忽略, 即$ FR\approx AR $ . 粒子的收敛性评价将由AR主导, 导致粒子收敛性评价不全面, 算法性能下降, 反之亦然. 为保证本文算法性能, 本文中$ \eta_{1} $ 和$ \eta_{2} $ 的取值分别为0.4和0.6.3.2.2 分区参数
${\boldsymbol{\alpha}}$ 和${\boldsymbol{ \beta }}$ 第2.2.2节通过分区参数
$ \alpha $ 和$ \beta $ 将种群划分为3个区域, I区和III区最优粒子的选取可以保证算法基本的收敛性和多样性, II区粒子能够根据算法当前环境进行自适应最优粒子的选取, 提升粒子的探索和开发能力. 因此,$ \alpha $ 和$ \beta $ 的取值将影响算法的收敛速度和综合性能. 图5给出本文算法解决ZDT3和DTLZ2问题时, 3种$ \alpha $ 和$ \beta $ 取值方案下IGD指标下降趋势, 取值方案分别为: Case 1:$\alpha = 0.1N,\;\beta = 0.9N$ ; Case 2:$\alpha = 0.2N,\;\beta = 0.8N$ ; Case 3:$ \alpha = 0.3N,\beta = 0.7N $ . 式中$ N $ 为粒子总个数.
图 5 不同分区参数取值方案下IGD指标变化Fig. 5 IGD metric changes of different partition parameter value schemes由图5可以看出, 当
$ \alpha $ 和$ \beta $ 的取值使II区粒子数量较多时, 算法收敛速度较慢, 当II区粒子数量较少时算法收敛速度较快. 由ZDT3测试问题的Case 3可以看出, 当II区粒子数量较少时, 算法的IGD指标下降陡峭, 并且算法迭代过程中IGD指标下降无明显波动, 表明算法在搜索过程中由于II区粒子数量不足, 导致粒子的探索能力不足; 由DTLZ2测试问题可以看出, 随着II区粒子的增多, 算法获得的最终IGD指标逐渐减小, 算法的综合性能逐渐提升.为避免算法收敛速度过快, 保证种群中粒子的探索和开发能力, 应使II区粒子保持较高数量. 通过大量实验验证,
$ \alpha $ 和$ \beta $ 的取值使I区、II区和III区粒子数分别约为粒子总数的1/5、3/5和1/5, 能够使算法保持合适的收敛速度并获得良好的综合性能.3.3 实验结果及比较分析
为验证本文算法的有效性, 分别对两目标问题(ZDT系列函数)和三目标问题(DTLZ系列函数)进行实验测试, 并设置8种多目标算法进行对比实验, 对比算法包括: 基于聚类的多目标粒子群优化算法(MOPSO based on clustering, clusterMOPSO)[23]、cdMOPSO[8]、pccsAMOPSO[13]、非支配排序遗传算法(Nondominated sorting genetic algorithm II, NSGA-II)[24]、增强Pareto进化算法(Strength Pareto evolutionary algorithm, SPEA2)[25]、MOEA/D[26]、基于竞争机制的多目标粒子群优化算法(Competitive mechanism based MOPSO, CMOPSO)[27]和嵌入基于分解归档方法的SPEA2算法(Decomposition-based archiving approach embedded in SPEA2, SPEA2 + DA-A)[28]算法. 各算法对测试问题的最大评价次数均为1000次, 实验结果均为各算法在同一测试问题上独立运行30次的统计结果. 算法运行环境均为Inter Core i5-5257U 2.70 GHz CPU, 8 GB内存, Windows10操作系统, Matlab 2016b. 各对比算法参数设置均与原文献保持一致.
表1 ~ 6分别给出了包括本文spmsAMOPSO算法在内的多种多目标优化算法在12个测试问题上的IGD、SP以及ER性能指标的平均值和标准差. 表7给出了几种算法计算所需的时间, 其中粗体数据为各评价指标下所得的最优结果.
表 1 本文算法与其他多目标粒子群算法的IGD评价指标对比Table 1 Results of IGD metric of the proposed algorithm and MOPSOs测试函数 spmsAMOPSO clusterMOPSO[23] cdMOPSO[8] pccsAMOPSO[13] CMOPSO[27] 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 ZDT1 ${\bf{2.34\times 10^{-3}}}$ ${\bf{5.46\times 10^{-6}}}$ $1.25\times 10^{-2}$ $1.78\times 10^{-3}$ $4.24\times 10^{-3}$ $2.58\times 10^{-4}$ $3.83\times 10^{-3}$ $2.67\times 10^{-4}$ $3.82\times 10^{-3}$ $2.15\times 10^{-5}$ ZDT2 ${\bf{1.98\times 10^{-3}}}$ ${\bf{6.18\times 10^{-6}}}$ $1.78\times10^{-2}$ $5.09\times 10^{-3}$ $4.28\times 10^{-3}$ $1.14\times 10^{-4}$ $3.81\times 10^{-3}$ $5.81\times 10^{-5}$ $3.86\times 10^{-3}$ $2.83\times 10^{-5}$ ZDT3 ${\bf{8.83\times 10^{-4}}}$ ${\bf{1.02\times 10^{-5}}}$ $1.05\times 10^{-1}$ $7.05\times 10^{-2}$ $3.06\times 10^{-3}$ $7.13\times 10^{-5}$ $4.91\times 10^{-3}$ $6.56\times 10^{-4}$ $4.50\times 10^{-3}$ $2.83\times 10^{-5}$ ZDT4 ${\bf{2.32\times 10^{-3}}}$ ${\bf{3.96\times 10^{-6}}}$ $3.99\times 10^{0} $ $2.61\times 10^{0} $ $5.91\times 10^{-1}$ $4.52\times 10^{-1}$ $5.79\times 10^{-3}$ $2.98\times 10^{-4}$ $3.70\times 10^{-2}$ $4.59\times 10^{-2}$ ZDT6 ${\bf{1.60\times 10^{-3}}}$ ${\bf{5.20\times 10^{-7}}}$ $4.39\times 10^{-1}$ $2.37\times 10^{-2}$ $2.99\times 10^{-3}$ $1.54\times 10^{-4}$ $4.68\times 10^{-3}$ $7.67\times 10^{-4}$ $3.09\times 10^{-3}$ $2.61\times 10^{-5}$ DTLZ1 ${\bf{1.23\times 10^{-2}}}$ $1.23\times 10^{-3}$ $4.15\times 10^{1} $ $2.29\times 10^{1} $ $2.75\times 10^{1}$ $9.34\times 10^{0}$ $1.36\times 10^{-1}$ $1.12\times 10^{-1}$ $4.44\times 10^{-2}$ $7.83\times 10^{-2}$ DTLZ2 ${\bf{3.62\times 10^{-3}}}$ $8.56\times 10^{-5}$ $1.26\times 10^{-1}$ $1.68\times 10^{-2}$ $1.02\times 10^{-1}$ $1.34\times 10^{-2}$ $6.14\times 10^{-2}$ $1.89\times 10^{-3}$ $4.40\times 10^{-3}$ ${\bf{3.61\times 10^{-5}}}$ DTLZ3 ${\bf{3.28\times 10^{-3}}}$ ${\bf{9.62\times 10^{-5}}}$ $4.76\times 10^{1}$ $2.87\times 10^{1}$ $4.46\times 10^{1}$ $1.02\times 10^{1}$ $2.19\times 10^{-1}$ $1.85\times 10^{-1}$ $4.24\times 10^{-3}$ $1.71\times 10^{-4}$ DTLZ4 $7.58\times 10^{-3}$ $3.45\times 10^{-3}$ $2.28\times 10^{-1}$ $8.45\times 10^{-2}$ $1.02\times 10^{-1}$ $3.66\times 10^{-2}$ $ {\bf{4.21\times 10^{-3} }} $ $3.37\times 10^{-3}$ $4.41\times 10^{-3}$ $7.58\times 10^{-5}$ DTLZ5 $9.76\times 10^{-3}$ $6.42\times 10^{-4}$ $1.62\times 10^{-4}$ $2.48\times 10^{-3}$ $6.05\times 10^{-3}$ $7.29\times 10^{-4}$ $1.18\times 10^{-2}$ $2.48\times 10^{-3}$ ${\bf{4.40\times 10^{-3}}}$ $5.66\times 10^{-5}$ DTLZ6 ${\bf{3.62\times 10^{-3}}}$ $3.47\times 10^{-5}$ $7.38\times 10^{-2}$ $1.55\times 10^{-1}$ $5.23\times 10^{-3}$ $3.90\times 10^{-4}$ $5.04\times 10^{-3}$ $2.27\times 10^{-4}$ $4.09\times 10^{-3}$ ${\bf{1.83\times 10^{-5}}}$ DTLZ7 ${\bf{4.23\times 10^{-3}}}$ $1.37\times 10^{-4}$ $4.02\times 10^{-2}$ $2.06\times 10^{-3}$ $5.78\times 10^{-2}$ $8.49\times 10^{-3}$ $4.27\times 10^{-2}$ $9.51\times 10^{-4}$ $4.43\times 10^{-3}$ ${\bf{4.01\times 10^{-5}}}$ 表 2 本文算法与其他多目标进化算法的IGD评价指标对比Table 2 Results of IGD metric of the proposed algorithm and multi-objective genetic algorithms测试函数 spmsAMOPSO NSGA-II[24] SPEA2[25] MOEA/D[26] SPEA2 + DAA[28] 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 ZDT1 ${\bf{2.34\times 10^{-3}}}$ ${\bf{5.46\times 10^{-6}}}$ $5.74\times 10^{-3}$ $3.39\times 10^{-4}$ $4.15\times 10^{-3}$ $1.77\times 10^{-4}$ $4.03\times 10^{-3}$ $5.59\times 10^{-5}$ $3.92\times 10^{-3}$ $5.05\times 10^{-5}$ ZDT2 ${\bf{1.98\times 10^{-3}}}$ ${\bf{6.18\times 10^{-6}}}$ $5.36\times 10^{-3}$ $2.02\times 10^{-4}$ $4.17\times 10^{-3}$ $2.56\times 10^{-4}$ $3.85\times 10^{-3}$ $4.34\times 10^{-5}$ $4.02\times 10^{-3}$ $1.07\times 10^{-4}$ ZDT3 ${\bf{8.83\times 10^{-4}}}$ ${\bf{1.02\times 10^{-5}}}$ $5.83\times 10^{-3}$ $2.02\times 10^{-4}$ $3.16\times 10^{-3}$ $5.96\times 10^{-3}$ $8.42\times 10^{-2}$ $7.02\times 10^{-3}$ $8.46\times 10^{-3}$ $9.45\times 10^{-3}$ ZDT4 ${\bf{2.32\times 10^{-3}}}$ ${\bf{3.96\times 10^{-6}}}$ $2.53\times 10^{1}$ $7.21\times 10^{0}$ $2.49\times 10^{1}$ $7.25\times 10^{-5}$ $4.86\times 10^{-3}$ $8.41\times 10^{-4}$ — — ZDT6 ${\bf{1.60\times 10^{-3}}}$ ${\bf{5.20\times 10^{-7}}}$ $1.65\times 10^{0}$ $9.80\times 10^{-1}$ $5.32\times 10^{-3}$ $2.65\times 10^{-8}$ $3.99\times 10^{-3}$ $6.02\times 10^{-5}$ — — DTLZ1 ${\bf{1.23\times 10^{-2}}}$ $1.23\times 10^{-3}$ $1.41\times 10^{1}$ $6.65\times 10^{0}$ $3.77\times 10^{1}$ ${\bf{1.45\times 10^{-4}}}$ $6.04\times 10^{-1}$ $2.89\times 10^{-1}$ $1.51\times 10^{-2}$ $1.48\times 10^{-3}$ DTLZ2 ${\bf{3.62\times 10^{-3}}}$ $8.56\times 10^{-5}$ $1.06\times 10^{-1}$ $8.38\times 10^{-3}$ $8.22\times 10^{-2}$ $2.83\times 10^{-7}$ $6.24\times 10^{-1}$ $6.44\times 10^{-5}$ $3.81\times 10^{-2}$ $3.03\times 10^{-4}$ DTLZ3 ${\bf{3.28\times 10^{-3}}}$ ${\bf{9.62\times 10^{-5}}}$ $1.64\times 10^{1}$ $7.56\times 10^{0}$ $4.87\times 10^{1}$ $0.00\times 10^{0}$ $6.52\times 10^{-1}$ $2.59\times 10^{-1}$ — — DTLZ4 $7.58\times 10^{-3}$ $3.45\times 10^{-3}$ $7.30\times 10^{-2}$ $5.09\times 10^{-2}$ $7.29\times 10^{-2}$ $1.42\times 10^{-7}$ $2.70\times 10^{-1}$ $6.83\times 10^{-3}$ — — DTLZ5 $9.76\times 10^{-3}$ $6.42\times 10^{-4}$ $8.05\times 10^{-3}$ $1.63\times 10^{-3}$ $1.41\times 10^{-2}$ $3.54\times 10^{-5}$ $5.94\times 10^{-1}$ ${\bf{8.43\times 10^{-8}}}$ — — DTLZ6 ${\bf{3.62\times 10^{-3}}}$ $3.47\times 10^{-5}$ $1.47\times 10^{0}$ $6.09\times 10^{-1}$ $2.49\times 10^{-1}$ $5.67\times 10^{-5}$ $6.17\times 10^{-1}$ $1.01\times 10^{-4}$ — — DTLZ7 ${\bf{4.23\times 10^{-3}}}$ $1.37\times 10^{-4}$ $6.14\times 10^{-1}$ $1.29\times 10^{-3}$ $6.24\times 10^{-2}$ $9.50\times 10^{-3}$ $6.57\times 10^{-1}$ $9.87\times 10^{-4}$ $3.69\times 10^{-2}$ $5.02\times 10^{-4}$ 表 3 本文算法与其他多目标粒子群算法的SP评价指标对比Table 3 Results of SP metric of the proposed algorithm and MOPSOs测试函数 spmsAMOPSO clusterMOPSO[23] cdMOPSO[8] pccsAMOPSO[13] 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 ZDT1 ${\bf{4.09\times 10^{-3}}}$ ${\bf{5.57\times 10^{-5}}}$ $7.25\times 10^{-2}$ $6.17\times 10^{-4}$ $8.56\times 10^{-2}$ $1.43\times 10^{-2}$ $1.33\times 10^{-2}$ $5.42\times 10^{-3}$ ZDT2 ${\bf{3.19\times 10^{-3}}}$ ${\bf{5.58\times 10^{-5}}}$ $1.77\times 10^{-2}$ $1.95\times 10^{-3}$ $1.91\times 10^{-2}$ $6.42\times 10^{-4}$ $1.06\times 10^{-2}$ $4.63\times 10^{-3}$ ZDT3 ${\bf{4.35\times 10^{-3}}}$ ${\bf{4.54\times 10^{-5}}}$ $7.78\times 10^{-2}$ $4.36\times 10^{-2}$ $5.97\times 10^{-1}$ $2.25\times 10^{-1}$ $1.25\times 10^{-1}$ $6.48\times 10^{-2}$ ZDT4 ${\bf{3.84\times 10^{-3}}}$ ${\bf{9.84\times 10^{-5}}}$ $9.19\times 10^{-3}$ $1.32\times 10^{-3}$ $8.49\times 10^{-3}$ $5.85\times 10^{-4}$ $1.09\times 10^{-2}$ $2.78\times 10^{-3}$ ZDT6 ${\bf{3.11\times 10^{-3}}}$ ${\bf{3.91\times 10^{-5}}}$ $2.69\times 10^{-2}$ $1.67\times 10^{-2}$ $9.83\times 10^{-3}$ $4.65\times 10^{-4}$ $1.10\times 10^{-2}$ $5.89\times 10^{-3}$ DTLZ1 ${\bf{2.24\times 10^{-2}}}$ ${\bf{3.36\times 10^{-4}}}$ $9.32\times 10^{-2}$ $1.74\times 10^{-2}$ $4.12\times 10^{-2}$ $5.64\times 10^{-3}$ $5.79\times 10^{0}$ $4.83\times 10^{-1}$ DTLZ2 ${\bf{3.60\times 10^{-2}}}$ ${\bf{1.74\times 10^{-4}}}$ $7.06\times 10^{-2}$ $3.42\times 10^{-3}$ $6.91\times 10^{-2}$ $4.03\times 10^{-3}$ $6.08\times 10^{-2}$ $2.54\times 10^{-3}$ DTLZ3 ${\bf{4.12\times 10^{-2}}}$ $2.33\times 10^{-3}$ $7.93\times 10^{-1}$ $2.06\times 10^{-2}$ $5.88\times 10^{-2}$ $3.96\times 10^{-3}$ $6.09\times 10^{-1}$ ${\bf{7.45\times 10^{-4}}}$ DTLZ4 ${\bf{3.80\times 10^{-2}}}$ ${\bf{8.63\times 10^{-4}}}$ $6.81\times 10^{-1}$ $9.94\times 10^{-3}$ $4.76\times 10^{-2}$ $2.84\times 10^{-3}$ $5.97\times 10^{-1}$ $6.33\times 10^{-2}$ DTLZ5 $7.52\times 10^{-2}$ $5.83\times 10^{-3}$ $8.93\times 10^{-2}$ $7.52\times 10^{-3}$ ${\bf{2.42\times 10^{-2}}}$ $6.22\times 10^{-3}$ $1.02\times 10^{-1}$ $3.74\times 10^{-2}$ DTLZ6 ${\bf{3.47\times 10^{-2}}}$ $2.14\times 10^{-3}$ $6.80\times 10^{-2}$ $1.83\times 10^{-2}$ $4.65\times 10^{-2}$ $2.73\times 10^{-3}$ $5.86\times 10^{-2}$ ${\bf{1.26\times 10^{-4}}}$ DTLZ7 ${\bf{9.47\times 10^{-2}}}$ $4.81\times 10^{-2}$ $3.90\times 10^{-1}$ $1.29\times 10^{-2}$ $5.97\times 10^{-1}$ $2.13\times 10^{-1}$ $1.08\times 10^{-1}$ $3.14\times 10^{-2}$ 表 4 本文算法与其他多目标进化算法的SP评价指标对比Table 4 Results of SP metric of the proposed algorithm and multi-objective genetic algorithms测试函数 spmsAMOPSO NSGA-II[24] SPEA2[25] MOEA/D[26] 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 ZDT1 ${\bf{4.09\times 10^{-3}}}$ ${\bf{5.57\times 10^{-5}}}$ $5.83\times 10^{-2}$ $9.39\times 10^{-3}$ $3.73\times 10^{-2}$ $2.67\times 10^{-3}$ $4.85\times 10^{-3}$ $7.19\times 10^{-4}$ ZDT2 ${\bf{3.19\times 10^{-3}}}$ ${\bf{5.58\times 10^{-5}}}$ $7.24\times 10^{-3}$ $7.41\times 10^{-3}$ $1.09\times 10^{-2}$ $1.04\times 10^{-3}$ $4.36\times 10^{-3}$ $7.41\times 10^{-4}$ ZDT3 ${\bf{4.35\times 10^{-3}}}$ ${\bf{4.54\times 10^{-5}}}$ $9.22\times 10^{-2}$ $8.42\times 10^{-3}$ $6.07\times 10^{-1}$ $1.03\times 10^{0}$ $1.02\times 10^{-1}$ $9.33\times 10^{-3}$ ZDT4 ${\bf{3.84\times 10^{-3}}}$ ${\bf{9.84\times 10^{-5}}}$ $2.83\times 10^{-2}$ $6.13\times 10^{-3}$ $4.06\times 10^{-2}$ $1.59\times 10^{-2}$ $7.52\times 10^{-3}$ $6.93\times 10^{-4}$ ZDT6 ${\bf{3.11\times 10^{-3}}}$ ${\bf{3.91\times 10^{-5}}}$ $3.43\times 10^{-2}$ $4.33\times 10^{-3}$ $4.72\times 10^{-2}$ $7.74\times 10^{-3}$ $1.88\times 10^{-2}$ $5.52\times 10^{-3}$ DTLZ1 ${\bf{2.24\times 10^{-2}}}$ ${\bf{3.36\times 10^{-4}}}$ $7.21\times 10^{-1}$ $6.34\times 10^{-2}$ $2.92\times 10^{-1}$ $3.62\times 10^{-2}$ $9.83\times 10^{-1}$ $2.33\times 10^{-1}$ DTLZ2 ${\bf{3.60\times 10^{-2}}}$ ${\bf{1.74\times 10^{-4}}}$ $4.67\times 10^{-2}$ $7.71\times 10^{-3}$ $5.38\times 10^{-2}$ $3.42\times 10^{-3}$ $8.14\times 10^{-2}$ $8.49\times 10^{-3}$ DTLZ3 ${\bf{4.12\times 10^{-2}}}$ $2.33\times 10^{-3}$ $8.26\times 10^{-2}$ $2.09\times 10^{-3}$ $6.34\times 10^{-2}$ $5.12\times 10^{-3}$ $1.79\times 10^{-1}$ $3.36\times 10^{-2}$ DTLZ4 ${\bf{3.80\times 10^{-2}}}$ ${\bf{8.63\times 10^{-4}}}$ $7.14\times 10^{-2}$ $1.97\times 10^{-3}$ $4.38\times 10^{-2}$ $6.54\times 10^{-3}$ $9.25\times 10^{-2}$ $5.61\times 10^{-3}$ DTLZ5 $7.52\times 10^{-2}$ $5.83\times 10^{-3}$ $6.37\times 10^{-2}$ ${\bf{1.74\times 10^{-3}}}$ $3.15\times 10^{-2}$ $5.31\times 10^{-3}$ $8.02\times 10^{-2}$ $4.39\times 10^{-3}$ DTLZ6 ${\bf{3.47\times 10^{-2}}}$ $2.14\times 10^{-3}$ $7.03\times 10^{-2}$ $1.56\times 10^{-3}$ $5.11\times 10^{-2}$ $4.89\times 10^{-3}$ $3.93\times 10^{-2}$ $3.31\times 10^{-3}$ DTLZ7 ${\bf{9.47\times 10^{-2}}}$ $4.81\times 10^{-2}$ $4.19\times 10^{-1}$ $7.96\times 10^{-3}$ $2.96\times 10^{-1}$ ${\bf{5.29\times 10^{-3}}}$ $1.85\times 10^{-1}$ $7.93\times 10^{-2}$ 表 5 本文算法与其他多目标粒子群算法的ER评价指标对比Table 5 Results of ER metric of the proposed algorithm and MOPSOs测试函数 spmsAMOPSO clusterMOPSO[23] cdMOPSO[8] pccsAMOPSO[13] 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 ZDT1 ${\bf{6.73\times 10^{-4}}}$ ${\bf{1.34\times 10^{-4}}}$ $1.06\times 10^{-2}$ $1.00\times 10^{-2}$ $9.90\times 10^{-2}$ $1.25\times 10^{-3}$ $8.12\times 10^{-3}$ $1.43\times 10^{-2}$ ZDT2 ${\bf{3.75\times 10^{-3}}}$ ${\bf{1.17\times 10^{-5}}}$ $4.92\times 10^{-1}$ $8.72\times 10^{-2}$ $1.30\times 10^{0}$ $1.21\times 10^{-1}$ $9.00\times 10^{-3}$ $2.36\times 10^{-3}$ ZDT3 ${\bf{8.95\times 10^{-3}}}$ ${\bf{1.37\times 10^{-3}}}$ $2.66\times 10^{-1}$ $9.30\times 10^{-2}$ $2.89\times 10^{-1}$ $7.24\times 10^{-2}$ $2.60\times 10^{-2}$ $8.32\times 10^{-3}$ ZDT4 $2.70\times 10^{-2}$ $8.35\times 10^{-3}$ $4.42\times 10^{-1}$ $1.02\times 10^{-1}$ $9.34\times 10^{-2}$ $6.83\times 10^{-2}$ ${\bf{2.37\times 10^{-2}}}$ ${\bf{4.74\times 10^{-3}}}$ ZDT6 ${\bf{1.60\times 10^{-3}}}$ $1.24\times 10^{-2}$ $2.98\times 10^{-2}$ $7.43\times 10^{-3}$ $6.77\times 10^{-3}$ $3.43\times 10^{-3}$ $1.10\times 10^{-2}$ ${\bf{4.64\times 10^{-4}}}$ DTLZ1 $6.81\times 10^{-2}$ ${\bf{4.24\times 10^{-3}}}$ ${\bf{4.83\times 10^{-2}}}$ $6.52\times 10^{-3}$ $6.22\times 10^{-1}$ $3.81\times 10^{-2}$ $9.90\times 10^{0}$ $7.13\times 10^{-1}$ DTLZ2 ${\bf{4.74\times 10^{-1}}}$ ${\bf{3.52\times 10^{-3}}}$ $1.19\times 10^{0}$ $7.62\times 10^{-1}$ $8.32\times 10^{-1}$ $3.53\times 10^{-2}$ $9.10\times 10^{-1}$ $5.31\times 10^{-2}$ DTLZ3 ${\bf{8.15\times 10^{-2}}}$ $2.47\times 10^{-2}$ $4.07\times 10^{-1}$ $5.26\times 10^{-2}$ $7.21\times 10^{-1}$ $2.12\times 10^{-2}$ $9.53\times 10^{-2}$ $3.64\times 10^{-2}$ DTLZ4 $8.02\times 10^{-2}$ ${\bf{1.14\times 10^{-3}}}$ $8.24\times 10^{-2}$ $3.01\times 10^{-3}$ $2.42\times 10^{-1}$ $9.71\times 10^{-2}$ $6.33\times 10^{-1}$ $3.60\times 10^{-2}$ DTLZ5 ${\bf{1.43\times 10^{-2}}}$ $3.90\times 10^{-3}$ $4.81\times 10^{-1}$ $5.32\times 10^{-2}$ $1.99\times 10^{-1}$ $9.73\times 10^{-2}$ $2.72\times 10^{-2}$ $4.74\times 10^{-3}$ DTLZ6 $1.73\times 10^{-1}$ $5.69\times 10^{-2}$ ${\bf{4.62\times 10^{-2}}}$ ${\bf{6.39\times 10^{-3}}}$ $3.48\times 10^{-1}$ $2.15\times 10^{-3}$ $1.92\times 10^{-1}$ $8.13\times 10^{-2}$ DTLZ7 ${\bf{2.18\times 10^{-1}}}$ ${\bf{7.64\times 10^{-2}}}$ $4.77\times 10^{-1}$ $5.07\times 10^{-1}$ $5.89\times 10^{-1}$ $4.33\times 10^{-1}$ $3.16\times 10^{-1}$ $9.57\times 10^{-2}$ 表 6 本文算法与其他多目标进化算法的ER评价指标对比Table 6 Results of ER metric of the proposed algorithm and multi-objective genetic algorithms测试函数 spmsAMOPSO NSGA-II[24] SPEA2[25] MOEA/D[26] 平均值 标准差 平均值 标准差 平均值 标准差 平均值 标准差 ZDT1 ${\bf{6.73\times 10^{-4}}}$ ${\bf{1.34\times 10^{-4}}}$ $8.06\times 10^{-3}$ $5.82\times 10^{-3}$ $3.00\times 10^{-3}$ $6.75\times 10^{-3}$ $7.65\times 10^{-2}$ $2.44\times 10^{-3}$ ZDT2 ${\bf{3.75\times 10^{-3}}}$ ${\bf{1.17\times 10^{-5}}}$ $5.74\times 10^{-1}$ $3.41\times 10^{-2}$ $9.11\times 10^{-1}$ $4.68\times 10^{-2}$ $6.53\times 10^{-1}$ $2.78\times 10^{-2}$ ZDT3 ${\bf{8.95\times 10^{-3}}}$ ${\bf{1.37\times 10^{-3}}}$ $2.09\times 10^{-2}$ $4.12\times 10^{-2}$ $1.49\times 10^{-1}$ $6.92\times 10^{-2}$ $4.87\times 10^{-2}$ $6.47\times 10^{-3}$ ZDT4 $2.70\times 10^{-2}$ $8.35\times 10^{-3}$ $3.49\times 10^{-2}$ $7.66\times 10^{-3}$ $8.45\times 10^{-2}$ $2.93\times 10^{-2}$ $7.60\times 10^{-1}$ $5.36\times 10^{-2}$ ZDT6 ${\bf{1.60\times 10^{-3}}}$ $1.24\times 10^{-2}$ $9.93\times 10^{-3}$ $7.64\times 10^{-4}$ $8.02\times 10^{-3}$ $3.24\times 10^{-3}$ $1.73\times 10^{-2}$ $2.12\times 10^{-3}$ DTLZ1 $6.81\times 10^{-2}$ ${\bf{4.24\times 10^{-3}}}$ $2.80\times 10^{-1}$ $1.55\times 10^{-2}$ $8.31\times 10^{-2}$ $4.85\times 10^{-3}$ $4.64\times 10^{-1}$ $3.06\times 10^{-2}$ DTLZ2 ${\bf{4.74\times 10^{-1}}}$ ${\bf{3.52\times 10^{-3}}}$ $7.06\times 10^{-1}$ $5.44\times 10^{-2}$ $9.47\times 10^{-1}$ $2.13\times 10^{-1}$ $2.59\times 10^{0}$ $7.42\times 10^{-1}$ DTLZ3 ${\bf{8.15\times 10^{-2}}}$ $2.47\times 10^{-2}$ $8.60\times 10^{-1}$ $3.75\times 10^{-2}$ $9.83\times 10^{-1}$ $3.41\times 10^{-2}$ $2.17\times 10^{-1}$ ${\bf{4.54\times 10^{-3}}}$ DTLZ4 $8.02\times 10^{-2}$ ${\bf{1.14\times 10^{-3}}}$ $4.85\times 10^{-1}$ $4.21\times 10^{-2}$ ${\bf{6.13\times 10^{-2}}}$ $1.90\times 10^{-3}$ $1.36\times 10^{-1}$ $6.29\times 10^{-2}$ DTLZ5 ${\bf{1.43\times 10^{-2}}}$ $3.90\times 10^{-3}$ $9.43\times 10^{-2}$ $4.16\times 10^{-3}$ $8.32\times 10^{-2}$ ${\bf{2.73\times 10^{-3}}}$ $v1.03\times 10^{-1}$ $6.51\times 10^{-2}$ DTLZ6 $1.73\times 10^{-1}$ $5.69\times 10^{-2}$ $5.84\times 10^{-2}$ $7.91\times 10^{-3}$ $4.36\times 10^{-1}$ $2.26\times 10^{-2}$ $2.53\times 10^{-1}$ $9.06\times 10^{-2}$ DTLZ7 ${\bf{2.18\times 10^{-1}}}$ ${\bf{7.64\times 10^{-2}}}$ $4.34\times 10^{-1}$ $2.64\times 10^{-1}$ $3.92\times 10^{-1}$ $8.70\times 10^{-2}$ $3.76\times 10^{-1}$ $2.92\times 10^{-1}$ 表 7 不同算法对多目标测试问题的运行时间 (s)Table 7 Computational time of different algorithms for multi-objective test problems (s)函数 spmsAMOPSO clusterMOPSO[23] cdMOPSO[8] pccsAMOPSO[13] NSGA-II[24] SPEA2[25] MOEA/D[26] ZDT1 105.26 108.87 ${\bf{101.72}}$ 121.95 129.17 135.23 152.45 ZDT2 ${\bf{104.72}}$ 114.95 112.74 108.34 133.15 126.65 139.13 ZDT3 ${\bf{111.23}}$ 136.38 135.81 124.57 132.40 137.98 135.02 ZDT4 ${\bf{115.17}}$ 132.09 129.69 122.19 125.67 130.61 147.61 ZDT6 ${\bf{122.48}}$ 131.62 124.23 126.62 133.52 128.74 149.55 DTLZ1 ${\bf{210.77}}$ 230.82 226.47 219.83 248.13 232.47 280.73 DTLZ2 218.93 233.49 ${\bf{212.73}}$ 215.63 250.26 238.69 289.36 DTLZ3 ${\bf{212.61}}$ 228.34 217.51 218.26 250.98 242.81 281.75 DTLZ4 218.34 230.25 220.98 ${\bf{216.44}}$ 247.37 241.33 276.84 DTLZ5 ${\bf{219.15}}$ 234.16 228.21 221.92 255.91 250.62 286.17 DTLZ6 ${\bf{216.37}}$ 236.59 225.40 225.73 245.69 247.97 288.33 DTLZ7 ${\bf{215.42}}$ 243.52 224.64 232.41 246.38 238.11 295.42 由表1 ~ 2可以看出, 本文算法在12个测试问题的结果中, 获得10次IGD指标的最优平均值和6次标准差最优值. 虽然在DTLZ4测试问题中本文算法的IGD指标略逊于pccsAMOPSO算法(其结果为最优值, 本文算法结果为次优值), 但优于其中5种多目标算法. 这是由于本文算法在进行最优粒子选取时采用分区策略, 将部分性能相似的粒子划分为一个区域, 对一个区域的粒子实现一种搜索引导策略, 而pccsAMOPSO算法在进行全局最优粒子选取时, 对种群中粒子逐个进行选取, 而本文算法根据粒子当前性能进行分区所获得的分区较为模糊, 在对复杂多目标问题进行优化时, 综合性能表现稍显不足. 但本文算法通过种群分区策略, 提出一种新的变异方法, 并结合带有记忆区间的个体最优粒子选取和融合指标的外部存档维护等方法, 使本文算法最终仍具有良好的性能. 在DTLZ5测试问题中本文算法性能相较于CMOPSO算法和cdMOPSO算法具有一些劣势(综合性能上CMOPSO算法最优, cdMOPSO算法次优), 但优于其余6种多目标优化算法. 对其余测试问题中, 本文算法均取得IGD指标的最优值, 各算法在12个测试问题中的IGD最优值个数表明, 本文算法在综合性能上优于其他8种多目标优化算法.
由表3和表4可以得到, 本文算法在12个测试问题的结果中, 获得11次SP指标的最优平均值和7次标准差最优值. 在DTLZ5测试问题中, 本文算法的SP指标略逊于cdMOPSO和NSGA-II算法(cdMOPSO和NSGA-II算法分别获得最优值和次优值), 但优于pccsAMOPSO、clusterMOPSO、MOEA/D和SPEA2等4种多目标优化算法, 在其余测试问题中, 本文算法的SP指标均取得最优值. 实验结果表明, 相比于其余多目标优化算法, 本文算法获得的Pareto前沿中非支配解分布均匀, 算法具有良好的多样性.
SP指标的实验结果表明, 本文算法获得的非支配解集具有良好的多样性, 这是由于本文算法通过对算法环境的检查自适应地调整了算法惯性权重和学习因子, 并采用种群分区策略, 对种群中收敛性较好的粒子制定特殊的搜索引导策略和变异方法, 提升粒子的探索效率, 有效增强算法多样性.
由表5 ~ 6可以看出, 在12个测试问题的结果中, 本文算法共获得8次ER评价指标的最优值, 在求解ZDT4、DTLZ1和DTLZ4测试问题时取得次优值(MOEA/D、clusterMOPSO和SPEA2算法分别取得最优值). 在DTLZ6测试问题中, 本文算法的ER指标略逊于clusterMOPSO和NSGA-II算法, 这是由于本文算法在最优粒子选取, 变异以及外部存档维护等方面均采用不同的策略对算法的收敛性和多样性进行平衡, 即牺牲了粒子的部分局部开发能力换取粒子的全局开发能力, 使算法取得相较于其他算法更好的多样性, 因此在部分复杂多目标优化问题中收敛性略显不足. 但相比于cdMOPSO等其余4种多目标优化算法, 本文算法在收敛性上仍然具有一定优势. 综合各算法的ER评价指标实验结果, 本文spmsAMOPSO算法获得的非支配解集能够较好地逼近真实Pareto前沿, 相比于其他几种多目标优化算法, 具有良好的收敛性.
ER指标的实验结果表明, 本文算法相较于其他几种多目标优化算法具有更好的收敛性, 这是由于本文算法通过在最优粒子选取和变异中加入种群分区, 对种群中性能较差的粒子实行特殊的寻优策略, 增强劣势粒子的利用率, 有效提升算法收敛性; 在个体最优粒子选取中, 加入粒子的记忆机制, 提升个体最优粒子选取的可靠性, 增强个体最优粒子对粒子收敛过程的指导作用.
由表7可以看出, 本文算法在求解多数测试问题时具均有较好的实时性, 仅在ZDT1和DTLZ2问题时劣于cdMOPSO算法, 在DTLZ4问题时略逊于pccsAMOPSO. 虽然本文算法采用了分区机制和粒子记忆区间, 增加了算法的计算复杂度, 但有效的种群划分使粒子的全局最优粒子选取以及变异更有效率, 并且个体最优粒子的可靠选取使粒子能够更快收敛至Pareto前沿附近, 使算法运行时间相较其他同类型优化算法更短.
为详细说明各算法所得非支配解集的收敛性和多样性, 图6 ~ 8分别给出了6种算法在求解ZDT3、DTLZ2和DTLZ7测试问题时的非支配解集和真实Pareto前沿. 由实验结果可以看出, 在三种测试问题中, cdMOPSO、pccsAMOPSO、NSGA-II、SPEA2和MOEA/D等多目标优化算法均不同程度的出现了收敛性和多样性不足的问题. 同样是在DTLZ2测试问题中, cdMOPSO、NSGA-II和SPEA2算法均表现出收敛性不足的缺点, 虽然pccsAMOPSO和MOEA/D算法具有较好的收敛性, 但算法多样性较差, 而本文spmsAMOPSO算法得到的Pareto前沿中, 非支配解不仅较好地收敛在真实Pareto前沿附近, 而且具有良好的分布性, 算法在收敛性和多样性上均有较好表现.
图 6 不同多目标优化算法对ZDT3函数的Pareto前沿Fig. 6 Pareto front of ZDT3 function of different multi-objective optimization algorithms
图 7 不同多目标优化算法对DTLZ2函数的Pareto前沿Fig. 7 Pareto front of DTLZ2 function of different multi-objective optimization algorithms
图 8 不同多目标优化算法对DTLZ7函数的Pareto前沿Fig. 8 Pareto front of DTLZ7 function of different multi-objective optimization algorithms为直观展示各算法多次实验数据的分布情况, 图9分别给出了7种多目标优化算法在测试ZDT3、DTLZ2和DTLZ7问题时IGD、SP以及ER指标的箱形图, 其中横轴坐标1 ~ 7分别代表spmsAMOPSO、clusterMOPSO、 cdMOPSO、pccsAMOPSO、NSGA-II、SPEA2和MOEA/D算法. 由图9可以看出, 本文算法在求解ZDT3、DTLZ2和DTLZ7测试问题时, IGD、SP以及ER指标相较于其他6种多目标优化算法均具有较大优势, 并且本文算法的多次测试结果数据无明显偏态, 出现的异常数据较少, 各项性能指标的中值和最大偏差均优于其他多目标优化算法. 实验结果表明, 本文算法不仅具有良好的综合性能, 并且测试结果稳定.
图 9 7种多目标优化算法在测试ZDT3、DTLZ2和DTLZ7问题时IGD、SP以及ER指标的箱形图Fig. 9 Box plots of IGD, SP and ER metric on ZDT3, DTLZ2 and DTLZ7 problems of multi-objective optimization algorithms综合实验结果表明, 本文算法得到的非支配解集能够有效地收敛在真实Pareto前沿, 并具有良好的分布性. 这是由于本文算法通过对种群进行分区, 制定多策略的搜索引导方案, 有效平衡了算法的收敛性和多样性, 提升了粒子的探索和开发能力及寻优效率, 并且使算法具有较好综合性能的同时降低了算法的计算复杂度.
4. 结束语
本文提出了一种基于种群分区的多策略自适应多目标粒子群优化算法. 算法通过基于种群分区的多策略改进, 确定算法的全局最优粒子选取和变异方法, 将粒子性能与算法寻优过程结合, 提升种群中各个粒子的搜索效率; 提出带有记忆区间的个体最优粒子选取方法, 提升个体最优粒子选取的可靠性, 避免因个体最优粒子不能有效指导粒子的飞行, 使算法停滞, 陷入局部最优; 采用双性能测度指标的外部存档维护策略, 能够有效保持外部存档中非支配解良好的分布性, 避免进行外部存档维护时, 删除收敛性较好的粒子, 导致种群产生退化, 影响粒子开发能力. 为验证算法有效性, 采用ZDT和DTLZ系列测试函数进行仿真实验, 并与其他几种多目标优化算法进行对比, 通过各算法对同一测试问题的IGD、SP、ER以及计算时间等评价指标的实验结果, 分别说明本文算法的收敛性, 多样性和实时性. 综合实验结果表明, 本文算法具有较显著的收敛性和多样性优势, 且具有良好的实时性.
-
图 5 即时显著性特征随预测单词的变化
Fig. 5 The change of instant salient features with predicted words
表 1
$\bar{D_{t}}$ 值最高的20个单词Table 1 The top-20 words with
$\bar{D_{t}}$ value单词 $\overline{D}_{t}$ 单词 $\overline{D}_{t}$ 单词 $\overline{D}_{t}$ hood 0.0592 ducks 0.0565 doughnut 0.0546 cats 0.0589 pug 0.0564 baby 0.0546 teddy 0.0576 rug 0.0561 bird 0.0545 little 0.0573 hummingbird 0.0556 pen 0.0543 duck 0.0571 pasta 0.0549 motorcycle 0.0543 bananas 0.0569 horse 0.0547 colorful 0.0542 seagull 0.0565 panda 0.0546 — — 
下载: 导出CSV
表 2 Encoder-Decoder + SFEM在MS COCO数据集上的表现(%)
Table 2 The performance of Encoder-Decoder + SFEM on MS COCO dataset (%)
下载: 导出CSV
表 3 Up-Down + SFEM在MS COCO数据集上的表现(%)
Table 3 The performance of Up-Down + SFEM on MS COCO dataset (%)
下载: 导出CSV
表 4 本模型和空间注意力模型的时间性能对比(帧/s)
Table 4 Time performance comparison between our model and the spatial attention model (frame/s)
下载: 导出CSV
表 5 各个模块单次执行平均花费时间(s)
Table 5 The average time spent by each module in a single execution (s)
下载: 导出CSV
表 7 组合模型在MS COCO数据集上的表现(%)
Table 7 Performance of the combined model on MS COCO dataset (%)
下载: 导出CSV
-
[1] Kulkarni G, Premraj V, Ordonez V, Dhar S, Li S M, Choi Y, et al. BabyTalk: Understanding and generating simple image descriptions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(12): 2891-2903 doi: 10.1109/TPAMI.2012.162 [2] Mao J H, Xu W, Yang Y, Wang J, Yuille A L. Deep captioning with multimodal recurrent neural networks (m-RNN). In: Proceedings of the 3rd International Conference on Learning Representations. San Diego, USA: ICLR, 2015. [3] 汤鹏杰, 王瀚漓, 许恺晟. LSTM逐层多目标优化及多层概率融合的图像描述. 自动化学报, 2018, 44(7): 1237-1249Tang Peng-Jie, Wang Han-Li, Xu Kai-Sheng. Multi-objective layer-wise optimization and multi-level probability fusion for image description generation using LSTM. Acta Automatica Sinica, 2018, 44(7): 1237-1249 [4] Cho K, Van Merriënboer B, Gulcehre C, Bahdanau D, Bougares F, Schwenk H, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation [Online], available: https://arxiv.org/pdf/1406.1078v3.pdf, September 3, 2014 [5] Bahdanau D, Cho K, Bengio Y. Neural machine translation by jointly learning to align and translate. In: Proceedings of the 3rd International Conference on Learning Representations. San Diego, USA: ICLR, 2015. [6] Sutskever I, Vinyals O, Le Q V. Sequence to sequence learning with neural networks. In: Proceedings of the 27th International Conference on Neural Information Processing Systems. Montreal, Canada: NIPS, 2014. [7] Vinyals O, Toshev A, Bengio S, Erhan D. Show and tell: A neural image caption generator. In: Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Boston, USA: IEEE, 2015. 3156−3164 [8] 张雪松, 庄严, 闫飞, 王伟. 基于迁移学习的类别级物体识别与检测研究与进展. 自动化学报, 2019, 45(7): 1224-1243Zhang Xue-Song, Zhuang Yan, Yan Fei, Wang Wei. Status and development of transfer learning based category-level object recognition and detection. Acta Automatica Sinica, 2019, 45(7): 1224-1243 [9] You Q Z, Jin H L, Wang Z W, Fang C, Luo J B. Image captioning with semantic attention. In: Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Las Vegas, USA: IEEE, 2016. 4651−4659 [10] Hochreiter S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735-1780 doi: 10.1162/neco.1997.9.8.1735 [11] Jia X, Gavves E, Fernando B, Tuytelaars T. Guiding the long-short term memory model for image caption generation. In: Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV). Santiago, Chile: IEEE, 2015. 2407−2415 [12] Wu Q, Shen C H, Liu L Q, Dick A, Van Den Hengel A. What value do explicit high level concepts have in vision to language problems? In: Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Las Vegas, USA: IEEE, 2016. 203−212 [13] Yang Z L, Yuan Y, Wu Y X, Cohen W W, Salakhutdinov R R. Review networks for caption generation. In: Proceedings of the 30th International Conference on Neural Information Processing Systems. Barcelona, Spain: NIPS, 2016. [14] 奚雪峰, 周国栋. 面向自然语言处理的深度学习研究. 自动化学报, 2016, 42(10): 1445-1465Xi Xue-Feng, Zhou Guo-Dong. A survey on deep learning for natural language processing. Acta Automatica Sinica, 2016, 42(10): 1445-1465 [15] 侯丽微, 胡珀, 曹雯琳. 主题关键词信息融合的中文生成式自动摘要研究. 自动化学报, 2019, 45(3): 530-539Hou Li-Wei, Hu Po, Cao Wen-Lin. Automatic Chinese abstractive summarization with topical keywords fusion. Acta Automatica Sinica, 2019, 45(3): 530-539 [16] Xu K, Ba J, Kiros R, Cho K, Courville A, Salakhudinov R, et al. Show, attend and tell: Neural image caption generation with visual attention. In: Proceedings of the 32nd International Conference on Machine Learning. Lille, France: JMLR.org, 2015. 2048−2057 [17] Lu J S, Xiong C M, Parikh D, Socher R. Knowing when to look: Adaptive attention via a visual sentinel for image captioning. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Honolulu, USA: IEEE, 2017. 3242−3250 [18] Chen L, Zhang H W, Xiao J, Nie L Q, Shao J, Liu W, et al. SCA-CNN: Spatial and channel-wise attention in convolutional networks for image captioning. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Honolulu, USA: IEEE, 2017. 6298−6306 [19] Chen X P, Ma L, Jiang W H, Yao J, Liu W. Regularizing RNNs for caption generation by reconstructing the past with the present. In: Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City, USA: IEEE, 2018. 7995−8003 [20] Anderson P, He X D, Buehler C, Teney D, Johnson M, Gould S, et al. Bottom-up and top-down attention for image captioning and visual question answering. In: Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City, USA: IEEE, 2018. 6077−6086 [21] Lu J S, Yang J W, Batra D, Parikh D. Neural baby talk. In: Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City, USA: IEEE, 2018. 7219−7228 [22] Lin T Y, Maire M, Belongie S, Hays J, Perona P, Ramanan D, et al. Microsoft COCO: Common objects in context. In: Proceedings of the 13th European Conference on Computer Vision. Zurich, Switzerland: Springer, 2014. 740−755 [23] Karpathy A, L F F. Deep visual-semantic alignments for generating image descriptions. In: Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Boston, USA: IEEE, 2015. 3128−3137 [24] Papineni K, Roukos S, Ward T, Zhu W J. BLEU: A method for automatic evaluation of machine translation. In: Proceedings of the 40th Annual Meeting on Association for Computational Linguistics. Philadelphia, USA: ACL, 2002. 311−318 [25] Banerjee S, Lavie A. METEOR: An automatic metric for MT evaluation with improved correlation with human judgments. In: Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization. Ann Arbor, USA: ACL, 2005. 65−72 [26] Vedantam R, Zitnick C L, Parikh D. CIDEr: Consensus-based image description evaluation. In: Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Boston, USA: IEEE, 2015. 4566−4575 [27] Lin C Y. ROUGE: A package for automatic evaluation of summaries. In: Proceedings of the Workshop on Text Summarization Branches Out, Post-Conference Workshop of ACL 2004. Barcelona, Spain: Association for Computational Linguistics, 2004. [28] Anderson P, Fernando B, Johnson M, Gould S. SPICE: Semantic propositional image caption evaluation. In: Proceedings of the 14th European Conference on Computer Vision. Amsterdam, the Netherlands: Springer, 2016. [29] Ren S Q, He K M, Girshick R, Sun J. Faster R-CNN: Towards real-time object detection with region proposal networks. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. Montreal, Canada: NIPS, 2015. 91−99 [30] Krishna R, Zhu Y K, Groth O, Johnson J, Hata K, Kravitz J, et al. Visual genome: Connecting language and vision using crowdsourced dense image annotations. International Journal of Computer Vision, 2017, 123(1): 32-73 doi: 10.1007/s11263-016-0981-7 [31] Rennie S J, Marcheret E, Mroueh Y, Ross J, Goel V. Self-critical sequence training for image captioning. In: Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Honolulu, USA: IEEE, 2017. 1179−1195 期刊类型引用(20)
1. 陈亮. 中压配电网多目标故障自动识别方法研究. 信息技术. 2025(02): 92-96+103 . 
百度学术2. 任旭阳，卜旭辉，尹艳玲，刘静滑. 基于多策略多目标差分进化算法的风光储系统协调优化调度. 系统仿真学报. 2025(02): 450-461 . 百度学术3. 李建林，梁忠豪，赵文鼎，梁策，袁晓冬. 基于权重计算的光储耦合制氢系统模型预测优化控制. 热力发电. 2024(02): 59-67 . 百度学术4. 冯旭刚，樊嵘，赵宇翔. 双目标区域化PSO热风炉均压滑模控制. 重庆工商大学学报(自然科学版). 2024(03): 81-88 . 百度学术5. 庞松岭，范凯迪，窦洁，陈超. 基于PSO的电动汽车规模化充电接入配电网柔性负荷多目标优化控制. 汽车技术. 2024(06): 1-8 . 百度学术6. 韩红桂，王玉爽，刘峥，孙浩源，乔俊飞. 知识和数据驱动的污水处理反硝化脱氮过程协同优化控制. 自动化学报. 2024(06): 1221-1233 . 本站查看7. 江锐，张薇. 最佳节点找寻下传感节点优化部署覆盖仿真. 计算机仿真. 2024(06): 512-515+535 . 百度学术8. 黄樊晶，吴盘龙，李星秀，赵若涵，何山. 考虑执行能力约束的多机协同目标分配AEPSO算法. 宇航学报. 2024(06): 948-957 . 百度学术9. 常大亮，史海波，刘昶. 具有紧时、高能耗特征的混合流水车间多目标调度优化问题. 中国机械工程. 2024(07): 1269-1278 . 百度学术10. 王梓歌，葛利跃，陈震，张聪炫，王子旭，舒铭奕. 联合深度超参数卷积和交叉关联注意力的大位移光流估计. 自动化学报. 2024(08): 1631-1645 . 本站查看11. 杜睿山，井远光，孟令东，张豪鹏. 基于改进多目标粒子群算法的储气库注气优化. 山东大学学报(工学版). 2024(04): 42-50 . 百度学术12. 陈飞，徐佳宁，尹兴隆，施辉选，张维. 基于场景概率约束的电网侧储能电站调度方法. 自动化与仪器仪表. 2024(09): 51-55 . 百度学术13. 辛保娟，陈荣荣. 基于等压差原理的耙式真空干燥机改造设计. 机械设计与制造工程. 2024(12): 117-120 . 百度学术14. 张心茹，季伟东，岳玉麒，殷曾祥. 基于三支决策的多目标优化自然计算策略研究. 智能计算机与应用. 2023(02): 134-138 . 百度学术15. 朱娟娟，段奕琳，闫群民，李召. 基于BAS-IMOPSO算法的风电系统储能优化配置. 电力工程技术. 2023(02): 180-187 . 百度学术16. 王旭，季伟东，周国辉，杨佳慧. 基于多指标精英个体博弈机制的多目标优化算法. 系统仿真学报. 2023(03): 494-514 . 百度学术17. 张章，张丽洁，李光毅，李津. 基于大数据与双向耦合的区域综合能源系统协同优化模型. 微型电脑应用. 2023(10): 76-79 . 百度学术18. 邢海燕，刘超，徐成，陈玉环，王松弘泽. 基于粒子群优化模糊C焊缝等级磁记忆定量识别模型. 吉林大学学报(工学版). 2022(03): 525-532 . 百度学术19. 赵朝辉，王志昊. 多约束条件下某智能飞行器质心平衡优化. 农业装备与车辆工程. 2022(04): 123-128 . 百度学术20. 冯茜，李擎，全威，裴轩墨. 多目标粒子群优化算法研究综述. 工程科学学报. 2021(06): 745-753 . 百度学术其他类型引用(18)
-
下载:
计量
- 文章访问数: 1046
- HTML全文浏览量: 639
- PDF下载量: 294
- 被引次数: 38
