改进多目标帝王蝶算法

冯礼杰 符强 陈嘉豪

DOI：10.16644/j.cnki.cn33-1094/tp.2021.11.012

摘要： 帝王蝶优化算法结构简单，能够较好的完成寻优搜索要求，但在多目标问题上，算法的精度和非支配解的分布性较差。针对以上不足之处，本文提出一种改进型多目标帝王蝶算法（Improved multi-objective monarch butterfly algorithm，IMOMBO），对非支配解进行拥挤度排序，所有非支配解个体都以当前最优个体为中心点映射镜像点，并朝向镜像点奔袭，以此增加个体在Pareto前沿上的收敛性和算法精度。在算法迭代后期，对部分较优个体进行Logistic混沌映射，以改善个体在 Pareto 前沿上的分布性。随机选用ZDT和DTLZ测试函数集中的函数进行算法性能验证，实验结果证明，本算法可以很好地保证非支配解个体的收敛特性和分布特性。

关键词： 群智能; 多目标; 帝王蝶优化算法; 非支配解排序; Logistic混沌映射

中图分类号：TP301.6          文献标识码：A     文章编号：1006-8228（2021）11-44-05

Improved multi-objective monarch butterfly algorithm

Feng Lijie， Fu Qiang， Chen Jiahao

（School of Information Engineering， School of Science and Technology， Ningbo University， Cixi， Zhejiang 315300， China）

Abstract： The monarch butterfly optimization algorithm is simple in structure and can better fulfill the optimization search requirements， but for multi-objective problems， the accuracy of the algorithm and the distribution of non-dominated solutions are poor. To solve the above short comings， an improved multi-objective monarch butterfly algorithm （IMOBO） is proposed in this paper to sort the crowding degree of the non-dominant solutions. All the individuals of the non-dominated solution map the mirror point with the current optimal individual as the center point and run toward the mirror point， so as to increase the convergence of the individuals on the Pareto front and the algorithm's accuracy. Logistic chaotic mapping is carried out for some of the better individuals at the later stage of the algorithm iteration， to improve the distribution of individuals on the Pareto front. The functions in the ZDT and DTLZ test function sets are randomly selected to verify the performance of the algorithm. The experimental results show that the algorithm can well guarantee the convergence characteristics and distribution characteristics of the non-dominated solution individuals.

Key words： swarm intelligence; multi-objective; monarch butterfly optimization algorithm; non-dominated solution sorting; Logistic chaotic map

0 引言

由多個目标组成且目标之间相互冲突和影响的问题被称为多目标问题[1]。而且在多目标问题的求解上，很难像解决单目标问题一样去寻找函数的最优解，因此寻找能够均衡所有目标的解成为求解多目标问题的目的。求解多目标问题时，经过一系列运算取舍最终会得到一组非劣解，而这组非劣解被称为Pareto最优解集[2]。最开始在寻求Pareto最优解集是通过赋予权重，将一个多目标的问题直接转化成一个单目标的问题来对其进行求解，但这种方法存在权重分配的主观性，并且结果的优劣也无法客观的判断。但在实际生产生活中，经常需要针对一个多目标问题去拿出多种有效的方案，以供决策者进行权衡选择得出最好的解决方案。因此，高效、合理的多目标优化算法在解决多目标的问题上是必不可少的。在已知的多目标优化算法中最为典型的就是多目标粒子群算法[3]（MOPSO），该算法通过合并Pareto-占优的概念来选出非劣解，并采用外部储存库来存储，以此不断迭代最终得出Pareto最优解集。而多目标遗传算法[4]（NSGA-II）也是目前具有代表性的多目标优化算法，NSGA-II采用非优超排序机制提升算法逼近Pareto最优前沿的能力，同时采用了排挤机制保证了非劣解集的分布性。此外，帝王蝶优化算法[5][6]也凭借其优秀的收敛性和寻优能力脱颖而出，但在多目标问题的解决上，算法稳定性和非支配解的分布性较差，由此，本文提出了一种改进多目标帝王蝶算法以解决算法本身在求解多目标问题上的不足。

1 帝王蝶优化算法

帝王蝶是地球上唯一具有迁徙性蝴蝶，他们每年都会进行迁徙，并在迁徙过程中进行繁殖。而帝王蝶优化算法是通过模仿自然界中帝王蝶族群随着季节气候变化而进行的迁移行为，研究出来的群体智能优化算法。该算法将整个帝王蝶种群划分为两个种群，称为种群1和种群2，种群1的个体进行迁徙实现更新，种群2则在种群内部进行随机游走，以获得更优个体，这两种行为在算法中描述为迁移算子和调整算子。算法的具体细节由下文展开。

假设问题对应于一个d维解空间，初始化产生一个个体数量为N的帝王蝶种群[P=（X1，X2，...，XN）]，第i个帝王蝶个体的位置可以表示为[Xi=（Xi，1，Xi，2，...，Xi，d）T]，由此可知，每个帝王蝶个体都有其对应目标问题的一个潜在解，其中迁移算子和调整算子描述如下：

设[NP1]和[NP2]分别为两个种群的个体数量，即[NP1=ceil（par*N），NP2=NP-NP1]。其中par为种群1个体的占比，函数ceil表示向上取整，迁移算子的数学模型描述如下：

其中，[i=1，2，...，NP1]，t表示当前迭代次数，[xr1]和[xr2]分别代表帝王蝶个体r1和r2的位置，这两个个体分别随机取自两个种群，标量[r=rand*peri]，其中的rand是一个随机数且[rand∈0，1];peri则代表的是帝王蝶个体的迁移周期。

在调整算子中，若[rand≤par]，则种群2中个体按式⑵更新;否则，个体将按式⑶更新。

其中，i=1，2，...，[NP2].[xbest]表示全局最优个体的位置。

其中，[xr3]表示从种群2中随机选择的一个帝王蝶的位置。

在此基础上，若rand[>]BAR，则对[xt+1i，k]进一步更新为：

其中，[α]是权重因子，由[α=1/t2]计算所得。[dx]表示帝王蝶个体[xi]的莱维飞行步长，由Levy函数计算。而BAR表示调整率。

2 改进多目标帝王蝶算法

多目标帝王蝶算法个体的更新是通过个体之间的维度替换，在迭代后期维度的多样性会降低并导致算法的分布性变差，而且很容易陷入局部最优。根据算法本身的不足在此提出以下三种优化策略去提升算法非支配解的分布性、收敛性以及算法的稳定性。

2.1 非支配解排序

为了保证能够更好的划分种群1和种群2，引入了非支配解排序算法[7].

首先，非支配排序涉及到的概念有如下两点。

⑴ 对于两个向量x和y，当且仅当

称之为x支配y，用[x?y]表示，否则，这称这两个向量互不支配。

⑵ 对于一个解[x∈X]，当且仅当

则称该解x为Pareto最优，而Pareto解集即Pareto最优解的集合，定义如下：

一个包含Pareto解集目标函数值的集合称为Pareto前沿，表示为：

因此在多目标帝王蝶算法中，非支配排序算法对所有个体都需要进行以下四步操作：

⑴ 判断是否被种群中其余个体支配;

⑵ 计算该个体在种群中的拥挤度[8]大小;

⑶ 对所有非支配个体进行拥挤度排序;

⑷ 将排序后的结果存入外部储存库中。

2.2 基于镜像映射的奔袭策略

由于帝王蝶优化算法在整个生命周期中的精英策略存在缺陷，如后期种群迁徙和游走的步长随机性过大导致种群出现退化，从而导致算法稳定性较差。本文提出了一种基于镜像映射的奔袭策略，以此降低帝王蝶个体在算法迭代过程中的退化率。该策略的思想是让非支配解个体朝着当前最优个体进行奔袭，如果新个体拥有更好的精度，则淘汰其余精度较差的个体，以此避免种群的大规模退化。

选取任意一个非支配解个体[xi]和当前最优个体[xbest]，[xi]以[xbest]为中心点，将其每个维度进行镜像映射得到镜像点[x‘i]，镜像点[x‘i]是个体[xi]奔袭过程中的最远位置，设置镜像点的目的是防止奔袭步长过大，其中计算公式如式⑽所示：

其中，ub，lb为目标函数解空间的上限和下限。个体[xi]在第j维时到最优个体[xbest]距离与最优个体[xbest]到解空间边界的比值等于镜像点个体[x'i]到最优个体[xbest]距离与最优个体[xbest]到解空间边界的比值。

个体[xi]在[xi]、[xbest]、[x'i]三点之间来回奔袭寻找非劣解，奔袭结束后得到子代个体[xnew]，其中奔袭的步长都由随机数公式决定，如式⑾所示：

其中，m是[x'i，j]与[xi，j]的乘积，而n是[x'i，j]与[xi，j]差的绝对值，max和min是[x'i，j]、[xi，j]中的最大值与最小值，[β]是一个正态分布的衰减系数，randn是一个符合正态分布的随机数，随着randn值增大，[xnew]游走之后的最终结果会无限趋近最优个体[xbest]。

2.3 Logistic混沌映射

為了提高算法在迭代后期个体在Pareto前沿上的分布性，采取对拥挤度最优个体进行Logistic混沌映射[9]，使最优个体在Pareto前沿上游走。其表达式为：

其中，[zi∈0，1]是第i个混沌变量，[zit]是[zi]经过t次迭代后的值。[μ]是混沌映射中的控制参数，且[μ∈0，4]。当 μ 的取值趋近于4时，系统在其映射下处于混沌状态。当[zi∈0，1]且[zi?]{0.25，0.50，0.75} 时将产生混沌现象，其中0.25，0.5，0.75这三个点是映射空间[0，1]中的断点，在映射时需要跳过。

当[xi∈ai，bi]要映射到[zi∈0，1]可用公式⒀中表达式：

然后利用公式⒁将[zi]映射回[xi]：

2.4 IMOMBO算法流程

Step 1 初始化必要参数，令初始代数[t =0]，设置最大迭代次数[MaxGen]，种群总个数为N，令种群1个数为[NP1]，种群2个数为[NP2]。

Step 2 在多目标优化问题的解空间中随机初始化帝王蝶种群;

Step 3 评估每个个体的适应度值;

Step 4 应用非支配解排序对当前帝王蝶种群排序，淘汰拥挤度较差的多余个体，并将非支配解存入外部储存库;

Step 5 判断是否达到最大迭代次数，若未满足，则当前迭代次数t=t+1;

Step 6 将种群中拥挤度值较优的NP1个个体组成种群1，余下的NP2个个体形成种群2;

Step 7 种群1使用迁徙算子更新﹔

Step 8 种群2使用调整算子更新;

Step 9 使用基于镜像映射的奔袭策略更新非支配解个体;

Step 10 当前迭代次数[t>MaxGen ]*0.5时，对非支配解中拥挤度值最优个体进行Logistic混沌映射;

Step 11 合并所有种群，转 Step 3;

3 仿真实验结果与分析

3.1 仿真实验初始参数设置

本文选取多目标粒子群算法[3]（MOPSO），带精英策略的非支配排序的遗传算法[4]（NSGA-II），以及本文的改进多目标帝王蝶算法（IMOMBO）进行对比实验，将所有算法的种群个数定为100，迭代次数为100代。测试函数的目标数设为2，每个个体的维度设置为10维。

本文算法参数设置：帝王蝶调整率为5/12，迁移周期为1.2，以及种群1个体的占比率为5/12;其余对比算法的参数设置均来源于引用文献。

在本次实验中，随机选用ZDT测试函数集[10]和DTLZ测试函数集[11]中8个测试函数进行验证。为了避免出现实验偶然性带来的偏差，测试的算法在每个测试函数上都进行10次独立实验。实验采用算法的GD[12]、IGD[12]、Spacing[12]三个值做比较，其中GD[12]用于检验算法的收敛能力，GD值越小，表明算法的收敛性能越好。IGD[12]是综合评价指标，同时反映了种群的收敛性和分布性，IGD值越小，说明算法的综合性能越好。Spacing[12]是检测算法在优化过程中均匀性的能力，Spacing值越小，算法的非支配解分布的越均匀。

3.2 仿真实验结果比较与分析

实验结果如下列各表所示，表1中IMOMBO的GD值远小于对比算法的GD值，说明本算法在运算过程中拥有更强的收敛性，能够得到比其余算法更为精确的解方案。表2的数据显示，本算法的IGD值优于对比算法，说明其综合性能相较于对比算法更优秀。表3中IMOMBO的Spacing值也是最小的，说明算法在非支配解的分布性上同样具有优势。在以下列出的8个测试函数中，IMOMBO算法的各项数值对比其余算法表现更为稳定，说明了本文提出的改进策略，能够很好的保证算法的稳定性。

3.3 各算法在测试函数中的Pareto前沿

为了进一步展示IMOMBO算法非支配解的分布性与收敛性，本文列出IMOMBO算法、MOPSO算法和NSGA-II算法在8个测试函数中的Pareto前沿，如图1所示。

从图像可以看出，本文的改进算法对于非支配解的分布性与收敛性都有不错的表现。本算法在8个测试函数中能保证每一个非支配解都位于测试函数Pareto前沿之上，且分布均匀。对比于MOPSO算法和NSGA-II算法，收敛性和分布性也更强。在测试函数DTLZ3、DTLZ7中，由于MOPSO的Pareto前沿较差，故没有参与对比。

4 结束语

本文提出了一种改进的多目标帝王蝶算法，改进方法包括了非支配解排序、基于镜像映射的奔袭策略和Logistic混沌映射，并且与多目标粒子群算法、带精英策略的非支配排序的遗传算法，进行了算法性能的对比实验，实验结果表明本算法的各项改进策略可以很好地保证个体的收敛特性和分布特征，同时，各项数值也表现出算法具有优秀的稳定性。这表明了本算法对于多目标问题的求解又迈出了一步，接下来还可以对一些生产生活中的实际问题做进一步的研究及优化。

参考文献（References）：

[1] 肖晓伟，肖迪，林锦国等.多目标优化问题的研究概述[J].计算机应用研究，2011.28（3）：805-808，827

[2] 裴胜玉，周永权.基于Pareto最优解集的多目标粒子群优化算法[J].计算机工程与科学，2010.32（11）：85-88

[3] Yanmin L，  Ben N，  Qingzhen Z， et al. Particle swarm optimizer simulation research of multi-objective optimization problems多目标优化问题的粒子群算法仿真研究[J].计算机应用研究，2011.28（2）：458-460

[4] 陳小庆，侯中喜，郭良民等.基于NSGA-Ⅱ的改进多目标遗传算法[J].计算机应用，2006.26（10）：2453-2456

[5] Gai-Ge Wang，Suash Deb，Xinchao Zhao，Zhihua Cui. A

new monarch butterfly optimization with an improved crossover operator[J].Operational Research，2018.18（3）.

[6] 冯艳红，杨娟，贺毅朝等.差分进化帝王蝶优化算法求解折扣{0-1背包问题[J].电子学报，2018.46（6）：1343-1350

[7] 李小林，王静，张元孜，黄世国.准确度优先的多目标帝王蝶优化定量构效特征选择方法[J].小型微型计算机系统，2021.5：1-5

[8] 魏武，郭燕.基于拥挤距离的动态粒子群多目标优化算法[J].计算机工程与设计，2011.32（4）：1422-1425

[9] 朱雅敏，薛鹏祥.一种基于Logistic混沌映射的骨干粒子群改进算法[J].西安文理学院学报：自然科学版， 2016.19：1-4

[10] Zitzler E，Deb K，Thiele L.Comparison of Multiobjective Evolutionary Algorithms：Empirical Results[J].Evolutionary Computation，2000.8（2）：173-195

[11] Deb K. Scalable test problems for evolutionary multiobejctive optimization[J]. Evolutionary Multiobjective Optimization： Theoretical Advances and Applications，2005.

[12] 胡涵，李振宇.多目标进化算法性能评价指标综述[J].软件导刊，2019.203（9）：7-10