一种用于求解多目标优化问题的改进MBO算法*

蒙丽萍，姜思佳，韦 量，王 勇

（1.广西西子科技有限责任公司，广西南宁 530009；2.柳州城市职业学院，广西柳州 545036；3.广西金融职业技术学院，广西南宁 530007；4.广西民族大学人工智能学院，广西南宁 530006）

0 引言

近年来，对现有群智能优化算法进行改进，并将其应用于求解工程等方面的优化问题，已经成为国内学者的一个研究热点。例如，国内研究者针对粒子群算法(PSO)[1]、蚁群算法(ACO)[2]、人工蜂群算法(ABC)[3]、人工鱼群算法(AFSA)[4]等现有的群智能算法提出了各种版本的改进算法(对PSO的改进算法见文献[5-11]，对ACO的改进算法见文献[12-14]，对ABC的改进算法见文献[15-20]，对AFSA的改进算法见文献[21-23])，并将其应用于求解工程等方面的问题。目前，改善现有群智能优化算法的性能仍然是智能计算领域一个重要的研究方向。

大红斑蝶优化算法(Monarch Butterfly Optimization，MBO)是Wang和Cui等人[24]于2015年提出一种新的群智能随机优化算法。然而，标准MBO算法在应用于求解复杂函数优化问题时仍出现早熟收敛现象、存在陷入局部最优之不足。针对这一问题，笔者首先提出一种改进的MBO算法，然后将其用于求解多目标优化问题，并通过数值实验仿真来检验本文算法的有效性和可行性。

1 MBO算法简介

MBO算法将群体搜索空间分成Land1和Land2两两不相交的区域；个体位置更新有两种方式：一是个体产生后代，一是个体移动导致位置变更。而个体后代的产生是通过迁徙算子得以实现。MBO算法中个体搜索方向由迁徙算子和调整算子确定。MBO假定：①大红斑蝶群体仅限于Land1和Land2这两个区域活动。②每一个体后代均经由迁徙算子产生，并规定：每产生一只新子代，相应就会死去一只父代；若新子代优于其父代，则以子代替换父代，否则丢弃该子代。③具有最优适应度值的个体则保留到下一代，且不对其进行任何变化操作。

个体位置更新方法：设种群个数为NP，位于Land1的个体数为NP1(=ceil( p × NP))（记为Subpopulation1），位于Land2的个数为NP-NP1=NP2（记为Subpopulation2）。其中ceil(x)为区间[ x，[ x]+1]中的最小整数，[ x]为取整函数，p为NP1与NP之比率。(注：MBO让p=5/12（迁移率）、NP1=BP×p（Land1中个体数）和NP2=NP-NP1（Land2中个体数）均取定值。)

1)迁徙算子。MBO 算法表示个体位置迁移的方程如下：

其中peri为迁徙期（MBO 中，取peri=1.2），rand为[0，1]中的随机函数。当r＞p时，则新产生的个体（大红斑蝶）第k维则由式（3）确定：

2)调整算子。MBO算法中的个体还可通过如下方法来变更位置：对于个体j的所有维，若rand≤p，则该个体按式(4)更新位置：

若rand＞p，则该个体按式(5)变更位置：

其中BAR为调整率（MBO算法置BAR=p），α为权重，dx为j个体的步长。dx和α分别由式(7)和式(8)确定：

其中Smax为全体个体之最大步长，t为当前代数。

2 改进的MBO算法

本文对MBO采用的改进策略如下：

第一，本文算法置迁移率为p=0.2+0.6×rand()，其中rand()为[0，1]上的随机函数，从而NP1=BP×p（Land1中个体数）和NP2=NP-NP1（Land2中个体数）都是随机数。换言之，在Land1和Land2中活动的个体，有些个体可能从Land1进入Land2，有些个体可能从Land2进入Land1，NP1和NP2均为变数。

第二，本文算法让Land1和Land2中的每一个体都有可能产生后代。

第三，设群体至t时刻找到的食物最丰富之处为Gtbest=(gt1，…，gtD)。由于大红斑蝶喜欢飞到食物最丰富之处去觅食，即会有较多的个体飞到Gtbest的周围觅食。针对这一现象，我们用如下式（9）来表达个体飞到Gtbest的周围觅食的方程：

第四，本文针对MBO中的式(5)，考虑个体在飞行运动中受到风力的影响，对其作如下改进：若rand ＞p，则

其中r3表示t时刻从NP2(即在Land2中活动的大红斑蝶群体)中随机选出的某一个体，即r3∈{1，…，NP2}，ε(t)=(0.5-rand())× s(t)，s(t)=1/(1+exp(-4t))，rand()为[0，1]上的随机函数。

设种群至t时找到的最优位置为Gbtest=(g1t，…，gDt)，i个体的位置为xti=(xti，1，…，xti，D)，NP为种群规模，i=1，…，NP。

1）种群分配方法。

对于第t代，先求适应度值f (xti)，i=1，…，NP。然后将全部个体按f (xti)(i=1，…，NP)的优劣排序（即最优者位列第1，次优者位列第2，依次类推）。记i个体位列第sti，本文称

为 i 个体的迁移决策因子（Migration decision factor）。mig_Dti确定i个体下一步的迁移地。

最后将种群个体随机分配到Land1或Land2中(依据迁移 率 p=0.2+0.6×rand())。分 配 方 法 如 下 ：若mig_Dti＜ p，则i个体飞入Land2中（个体数为NP2）。否则，飞入Land1中（个体数为NP1）。

2）实现方法和步骤。

·在Land1中活动的NP1只个体，均按公式（1）变更位置。

·在Land2中活动的NP2只个体，按如下方法变更位置：先求出i个体的排位sti。其次利用式（11）计算mig_Dti。最后按如下方法选择运动方程：任取随机数rand ∈[0，1]，若mig_则选择式（9）确定位置；mig_Dti≤ rand，则选择式（10）确定位置 ；若 mig_Dti＞rand，则该个体要重新初始化。

实现步骤如下：

Input：目标函数f (X )、群体规模NP、最大迭代次数max Gen。

Step1：

Set t=1，随机初始化群体X1i([i=1，…，NP])，计算f (X1i)，令Gtbest为群体当前最优位置。

Step2：

按“种群分配方法”将种群分配到区域Land1或区域Land2中。

Step3：

Land1中的个体按公式（1）确定位置。

Step4：

计算Land1中每一个体在新位置的适应度值，并与当前群体最优位置进行比较，判断是否需要更新当前群体最优位置。

Step5：

对于Land2中i个体，利用式（11）求出mig_Dti；然后取一个随机数rand ∈[0，1]，若mig_（9）确定其下一步的位置；若其按公式(10)确定其下一步的位置；若mig_Dti＞ rand，则其将重新初始化。

Step6：

计算Land2中每一个体在新位置的适应度值，并与当前群体最优位置进行比较，判断是否需要更新当前群体最优位置。

Step7：

将Land1中和Land2中个体合并，组成新的群体规模为NP的种群。

Step8：

若满足算法终止条件，则输出最优位置及相对应的目标值，算法终止；否则，转向Step2。

3 数值实验

利用数值实验与仿真来检验本文算法的优化性能。我们将本文算法与MBO[24]、标准PSO[1]作数值优化实验对比与分析。在数值仿真实验中，我们分别选取了3个多目标优化问题，用来测试这三种算法各自的函数优化性能。这3个多目标优化问题分别如下：

3.1 实验结果与分析

本文将IMBO、MBO和PSO应用于求解多目标优化问题时，分别记为MOIMBO、MOMBO和MOPSO。

关于多目标优化问题，需要介绍以下几个基本概念。

多目标优化问题（MOP）：设X=(x1，…，xn)为决策变量，满足

约束条件。设有r个目标，且这r个优化目标是相互冲突的，优化目标可表示为

寻找X*=(x*1，…，x*n)，使f (X*)在满足约束（12）和（13）的同时达到最优。

Pareto最优状态：点x→*∈ Ω（Ω为决策变量空间）是Pareto最优需要满足下面两个条件中任一个，即任意x→∈Ω，x→*∈ Ω是Pareto最优，要么

要么至少存在一个i ∈I使得

Pareto 支 配 ：向 量 u→=(u1，…，uk)支 配 向 量 v→=(v1，…，vk)表示为u→ -≺ v→，当且仅当

Pareto最优集：对于多目标优化问题f→(X )，Pareto最优集P*定义为

Pareto最优前沿：对于多目标优化问题f→(X )和Pareto最优集P*，最优前沿PF*定义为

·ER（误差比）：该指标用来描述算法产生的非劣解中，不属于真实Pareto前沿的解所占的百分比：

其中n为所获得的非劣解个数，若解i属于Pareto最优解集，则ei=0；否则，ei=1。

ER值越小，属于Pareto最优解集的非劣解所占比例就越高。ER=0表示所有非劣解都位于真实的Pareto前沿上。

·GD：该指标用来表示算法所获得的非劣解与问题的真实Pareto前沿之间的距离：

其中disti表示第i个非劣解与真实Pareto前沿之间的最短距离。

·SP：该指标表示非劣解在目标空间上的分布范围。计算方法如下：

由于ER，GD和SP三个指标总体上刻画了算法针对多目标优化问题的优化性能，而且普遍被智能优化领域研究者所普遍采用。故本文以ER，GD和SP作为算法求解多目标优化问题的优化性能评价指标，用ER，GD和SP分别来评价算法所获得的解中不属于真正Pareto最优解的百分比、解与真实Pareto前沿之间的距离和解的分布范围。

对于MOIMBO，MOMBO和MOPSO，均采用外部档案库及自适应网格法来接受和更新Pareto最优解。三种算法的种群规模都是50，最大迭代次数均为1000次，外部档案库大小均为100，搜索空间都是30维；MOIMBO 与IMBO的其他参数设置相同，MOMBO及MOPSO也分别与MBO及PSO的其他参数设置相同。

利用三种算法分别对ZDT1，ZDT2和ZDT3独立进行30次实验测试，得到的实验测试结果见表1。

根据表1实验数据对比三种算法的优化性能。

表1 三个多目标优化问题实验结果

首先，分析三种算法求解ZDT1时：从ER和GD上看，MOIMBO在最优值、最差值、平均值和标准差指标上均比MOMBO和MOPSO的好。从SP上看，MOIMBO在最优值、平均值和标准差指标上均比MOMBO和MOPSO的优或相同；MOIMBO 在最差值指标上略差于MOMBO，但比MOPSO的优。

其次，分析三种算法求解ZDT2时：从ER和SP上看，MOIMBO在最优值、最差值、平均值和标准差指标上均比MOMBO和MOPSO的好。从GD上看，MOIMBO在最差值、平均值和标准差指标上均比MOMBO和MOPSO的优或相同；MOIMBO 在最优值指标上略差于MOMBO，但比MOPSO的优。

再次，分析三种算法求解ZDT3时：从ER和SP上看，MOIMBO在最优值、最差值、平均值和标准差指标上均比MOMBO和MOPSO的好。从GD上看，MOIMBO在最优值、最差值和平均值指标上均比MOMBO和MOPSO的优；在标准差指标上，MOMBO 和MOPSO 略优于MOIMBO。

实验中得到的3 种算法分别求解ZDT1、ZDT2和ZDT3时找到的最优前沿与真实Pareto前沿拟合程度图如图1-1至图1-3、图2-1至图2-3、图3-1至图3-3所示。

图3-3 MOPSO 求解ZDT3

从图1-1至图1-3、图2-1至图2-3、图3-1至图3-3上看，MOIMBO找到的最优前沿与真实Pareto前沿的拟合程度均比另外两种算法找到的最优前沿与真实Pareto前沿的拟合程度要好，说明了MOIMBO求解多目标优化问题时的全局搜索能力均比另外两种算法强。

图2-3 MOPSO 求解ZDT2

图3-1 MOPSO 求解ZDT3

图2-1 MOPSO 求解ZDT2

图1-3 MOPSO 求解ZDT1

图1-1 MOPSO 求解ZDT1

4 结语

本文提出一种新的可用于求解多目标优化问题的MOIMBO算法，并利用多目标优化问题来检验本文算法的优化性能。数值实验仿真结果表明：MOIMBO在求解多目标优化问题时的全局搜索能力均比MOPSO和MOMBO的强，说明本文提出的MOIMBO在用于求解多目标问题时是有效的和可行的。

图1-2 MOPSO 求解ZDT1

图2-2 MOPSO 求解ZDT2

图3-2 MOPSO 求解ZDT3