应用精英反向学习的飞蛾扑火优化算法

Moth-Flame Optimization Algorithm Using Elite Opposition-Based Learning

摘要: 飞蛾扑火优化算法(MFO)是一个新颖的启发式算法，其主要设计灵感来源于自然界中称为横向定位的导航机制。由于标准飞蛾扑火优化算法容易陷入局部最优、求解精度低，所以借鉴精英反向学习策略，提出一种应用精英反向学习的飞蛾扑火优化算法(EOMFO)。新算法不仅增加了群体的多样性，并且提高了算法的综合性能。通过对7组标准测试函数的实验仿真，结果表明应用精英反向学习的飞蛾扑火优化算法具有更高的收敛精度，从而验证了新算法是有效的和可行的。

Abstract: The Moth-flame Optimization (MFO) algorithm is a novel heuristic algorithm. The main inspiration of this algorithm is the navigation method of moths in nature called transverse orientation. Since the Moth-flame Optimization algorithm is easy to fall into the local optimum and the solution accuracy is low, elite opposition-based learning was utilized to propose the Moth-flame optimization algorithm using elite opposition-based learning (EOMFO). The proposed algorithm not only increases the diversity of the group, but also improves the overall performance of the algorithm. Through the experimental simulation of 7 sets of standard test functions, the results show that the Moth-flame optimization algorithm with elite opposition-based learning has higher convergence precision, which verifies that the new algorithm is effective and feasible.

1. 引言

飞蛾扑火优化算法 [1] [2] [3] [4] (Moth-flame optimization algorithm, MFO)是由Seyedali Mirjalili提出的一种新型启发式优化算法 [5] [6]，该算法的灵感来源于飞蛾以月亮为参照来辨别方向的导航机制。由于距离月亮较远，在夜间的时候飞蛾只需要保持与月亮有个固定的角度飞行即可保证直线移动。当飞蛾迷失方向的时候，只需根据月光来自己调整方位，便能找到正确的方向。而当飞蛾误把人造光当成月光而作螺旋状飞行时，飞蛾最终便会向人造光处收敛。

飞蛾扑火优化算法因其具有诸多优点，因此常被用于求解大规模优化问题 [7]、网络流量预测 [8]、编码信号集设计 [9] 等诸多领域，同时算法在寻优过程中也存在一些不足，如由于种群多样性低导致全局寻优性能较差等。针对飞蛾扑火优化算法存在的一些不足，诸多学者尝试对其进行了改进，并成功应用到了一些工程领域。李伟琨等提出一种多目标飞蛾扑火算法，并将其用在了电力系统无功优化中 [10]；高帅等利用支持向量机(SVM)提出将SVM和MFO相结合的算法(MFO-SVM)，并能够有效预测空气质量指数 [11]；徐慧等提出一种融合粒子群的二进制飞蛾扑火优化算法(BPMFO)，并将其应用于网络入侵检测的特征检测中 [12]；岳龙飞等通过借鉴混沌序列、模拟退火算法和遗传算法提出Tent混沌和模拟退火改进的飞蛾扑火优化算法，新算法增加了种群多样性，然后对当前最优解增加扰动产生新解，最终获得最优解 [13]。

2. 飞蛾扑火优化算法

2.1. 标准MFO算法

在标准MFO算法中，分别用矩阵M和F来表示飞蛾和火焰集合，而OM和OF分别用来存放飞蛾和火焰相对应的适应度值。MFO算法可以用下面的全局最优的三元组表示。

$\text{MFO}=\left(I,P,T\right)$ (1)

函数I产生一个随机飞蛾种群及相应的适应度值。

$I:\varphi \to \left\{M,OM\right\}$ (2)

函数P接受矩阵M，并最终返回更新后的矩阵。

$P:M\to M$ (3)

如果满足终止准则，则函数T为真；如果不满足，则函数T为假。

$T:M\to \left\{\text{true},\text{false}\right\}$ (4)

函数I初始化后，P函数迭代运行直到T函数为真。使用式(5)更新每只飞蛾相对于火焰的位置。

$M_i=S\left(M_i,F_j\right)$ (5)

这里的第i只飞蛾表示为M_i，第j个火焰表示为F_j，S为螺旋函数。

MFO算法中飞蛾的更新机制使用的是对数螺旋函数，其定义如下

$S\left(M_i,F_j\right)=D_i\cdot {\text{e}}^{bt}\cdot \cos \left(2\pi t\right)+F_j$ (6)

第i个飞蛾与第j个火焰的距离在这里用D_i表示，b为常数，t为 $\left[-\text{1},\text{1}\right]$ 之间的随机数。

D 由式(7)计算求得

$D_i=\left|F_j-M_i\right|$ (7)

飞蛾的移动路径使用式(6)来进行模拟，并且还可以把飞蛾相的下一个位置确定下来。在式(6)中，参数t表示的是飞蛾在下个位置与火焰的远近程度(t = −1表示为飞蛾最接近火焰，而t = 1表示为距离火焰最远)。在式(6)中需要飞蛾向火焰处移动，而这使得MFO算法极易陷入局部最优的停滞中。于是，使用式(6)来更新每个飞蛾的位置。在每次迭代更新火焰列表后，火焰根据其适应度值来排序。然后飞蛾更新其相对于相应火焰的位置。第一只飞蛾总是更新相对于最优火焰的位置，而最后那个飞蛾更新列表中最差火焰的位置。

对于飞蛾在位置更新的时候可能降低了对于解的开采，使用一种火焰数量的自适应机制，使用式(8)表示

$flameno=round\left(N-l\ast \frac{N-1}{T}\right)$ (8)

这里的l表示为当前的迭代次数，火焰数量的最大值为N，而算法的最大迭代次数表示为T。

式(8)表明在迭代初始步骤中存在数量为N的火焰。然而，在迭代的后期飞蛾仅使用最好的火焰更新它们的位置。飞蛾数量上的逐渐减少平衡了在搜索空间里的探测与开采。

标准MFO算法流程描述如下：

Step 1：初始化飞蛾种群M、螺旋线等相关参数；

Step 2：随机生成飞蛾位置，由飞蛾种群排序得到火焰F及其适应度值OF，迭代开始；

Step 3：由式(8)求出飞蛾数量，去掉不好的飞蛾及火焰；

Step 4：由式(7)求出飞蛾及对应火焰的距离D_i；

Step 5：将Step 4求得结果与式(6)结合，求每只飞蛾更新之后的值；

Step 6：由新的飞蛾种群M计算出对应OM；

Step 7：若满足结束条件，则停止迭代；若不满足，跳转到Step2继续执行。

2.2. 反向学习

反向学习(Opposition-Based Learning, OBL)是学者Tizhoosh在2005年提出的计算智能领域的一个新概念 [14]，该方法已经被证实可以有效提高智能优化算法的搜索能力。反向学习表示为在当前个体所在区间上产生反向解个体，然后把产生的反向个体和当前群体放在一起参与择优选择，选择优秀的个体进入后序的迭代中，另外从概率论的方面也说明了反向解有高于50%的概率远离问题的最优解 [15]。下面给出反向解的定义。

定义1：反向解(Opposite Solution, OS) [16]。如在 $\left[a,b\right]$ 上有实数 x， x的反向数用 $x^{\prime }=a+b-x$ 表示。若有个N维点 $p=\left(x_1,x_2,\cdots ,x_i,\cdots ,x_N\right)$ 在R域上， $x_i\in \left[a_i,b_i\right]$， 表示p的反向点， ${x^{\prime }}_i=k\ast \left(a_i+b_i\right)-x_i$，k为[0,1] 区间上服从均匀分布的随机数。若适应度函数的可行解为x，其反向解为 $x^{\prime }$，当 $f\left(x\right)>f\left(x^{\prime }\right)$ 时，则用 $x^{\prime }$ 代替x。

2.3. 精英反向学习

在标准MFO算法中引入反向解，使得算法的搜索范围较之以前扩大了很多。为有效提高算法的收敛速度，先求出当前解的反向解，再根据适应度值找出原解适应度值大于反向解适应度值的个体，并将其组成精英群体，然后在精英群体中生成新搜索空间，求出原解适应度值小于反向解适应度值个体的反向解。在算法找到最优解的时候，也必然会找到最优解所在的区域，然后在精英群体定义的区间上生成反向解，从而搜索到最优解处 [17]。

定义2 精英反向解(Elite Opposite Solution, EOS) [16] [18]。在N维空间中，当前群体的精英个体 $X_{best}=\left(x_1,x_2,\cdots ,x_i,\cdots ,x_N\right)$ 的反向解可表示为 ${X^{\prime }}_{best}=\left({x^{\prime }}_1,{x^{\prime }}_2,\cdots ,{x^{\prime }}_i,\cdots ,{x^{\prime }}_N\right)$，可定义成 ${x^{\prime }}_i=k\ast \left(a_i+b_i\right)-x_i$，其中的 $x_i\in \left[a_i,b_i\right]$， $k\in \left[0,1\right]$ 为服从均匀分布的随机数，利用k可以产生精英个体的多个反向解，可以有效提高算法的开采能力。

2.4. 应用精英反向学习的飞蛾扑火优化算法

在标准MFO算法中，作为种群领导者的最优飞蛾如果陷入局部最优中去的话，将导致算法提前进入早熟，而使得算法搜索停滞。而对飞蛾进行反向学习之后，这种现象将在很大程度上得到规避。此外，在带有盲目性的反向学习中加入精英策略，不仅扩大了算法的搜索区域，有效减少盲目搜索带来的时间浪费，而且加快了算法的收敛速度。使得算法在每次迭代时，将一些精英个体进行反向学习，然后把生成的精英个体的反向种群放入其中参与竞争，这样做不仅可以保障算法具有较强的局部搜索能力，另外在性能上也有了较大的提升。

EOMFO算法流程描述如下：

Step 1：使用精英反向学习策略初始化飞蛾种群M、螺旋线等相关参数(选取策略概率p = 0.7)；

Step 2：随机生成飞蛾位置，由飞蛾种群排序得到火焰F及其适应度值OF ，迭代开始；

Step 3：由式(8)求出飞蛾数量，去掉不好的飞蛾及火焰；

Step 4：由式(7)求出飞蛾及对应火焰的距离D_i；

Step 5：将Step 4求得结果与式(6)结合，求每只飞蛾更新之后的值；

Step 6：由新的飞蛾种群M计算出对应 OM；

Step 7：若满足结束条件，则停止迭代；若不满足时，跳转到Step2继续执行。

3. 仿真实验

3.1. 实验环境与参数设置

为了验证新算法EOMFO的有效性，文章选取了7个测试函数。实验中算法参数设置为：种群规模为30个个体，最大迭代次数为1000次，函数维数设置为30维，最终测试结果采用独立运行30次最优值的平均值。

3.2. 测试函数

在这次仿真实验中共选取7个基准测试函数，其中包含有4个单峰函数( $f_1~f_4$)和3个多峰函数( $f_5~f_7$)。单峰函数因其只有一个全局最优值，可以对算法的开采能力进行测试，多峰函数具有较多的局部最优值，可以考验算法跳出局部最有停滞的能力。实验中用到的7个测试函数如下：

1) Sphere函数

$f_1\left(x\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_i^2}$， $-100\le x_i\le 100\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值0。

2) Schwefel’s 2.22函数

$f_2\left(x\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}\left|x_i\right|}+{\displaystyle \underset{i=1}{\overset{n}{\prod }}\left|x_i\right|}$， $-10\le x_i\le 10\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值0。

3) Step函数

$f_3\left(x\right)={\displaystyle {\sum }_{i=1}^n{\left(\lfloor x_i+0.5\rfloor \right)}^2}$， $-100\le x_i\le 100\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值0。

4) Quartic函数

$f_4\left(x\right)={\displaystyle {\sum }_{i=1}^{n}i{x}_i^4+random\left(0,1\right)}$， $-1.28\le x_i\le 1.28\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值 0。

5) Ackley函数

$f_5\left(x\right)=-20\exp \left(-0.2\sqrt{\frac{1}{n}{\displaystyle {\sum }_{i=1}^n{x}_i^2}}\right)-\exp \left(\frac{1}{n}{\displaystyle {\sum }_{i=1}^n\cos \left(2\pi x_i\right)}\right)+20+e$，

$-32\le x_i\le 32\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值0。

6) Griewangk函数

$f_6=\frac{1}{4000}{\displaystyle {\sum }_{i=1}^n{x}_i^2}-{\displaystyle {\prod }_{i=1}^n\cos \left(\frac{x_i}{\sqrt{i}}\right)}+1$， $-600\le x_i\le 600\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值0。

7) Penalized 1函数

$\begin{array}{l}{f}_7\left(x\right)=\frac{\pi }{n}\left\{10\sin \left(\pi y_1\right)+{\displaystyle {\sum }_{i=1}^{n-1}{\left(y_1-1\right)}^2}\left[1+10{\sin }^2\left(\pi y_{i+1}\right)\right]+{\left(y_n-1\right)}^2\right\}\\ +{\displaystyle {\sum }_{i=1}^{n}u\left(x_i,10,100,4\right)}\\ y_i=1+\frac{x_i+1}{4};u\left(x_i,a,k,m\right)=\{\begin{array}{l}k{\left(x_i-a\right)}^m{x}_i>a\\ 0-a<x_i<a\\ k{\left(-x_i-a\right)}^m{x}_i<-a\end{array}\end{array}$， $-50\le x_i\le 50\left(i=1,2,\cdots ,n;n=30\right)$，在 $\left(0,0,\cdots ,0\right)$ 处取得全局最小值0。

3.3. 实验结果

实验结果如表1所示。

Table 1. Comparison of experimental results between MFO and EOMFO

表1. MFO与EOMFO实验结果比较

从表1可知，单峰函数方面，对于函数 $f_1$，EOMFO的最优值精确度达到 $e^{-8}$，平均值方面其求解精度比标准MFO提高了5个数量级，并且方差较小，说明新算法对于 $f_1$ 的求解具有一定的稳定性。对于函数 $f_2$，EOMFO的最优值精确度达到 $e^{-4}$，平均值和方差均达到了 $e^{-2}$，说明新算法对于 $f_2$ 的求解具有较好的稳定性。对于函数 $f_3$，EOMFO的最优值、最差值、平均值虽没有取得理想的成绩，但相较于标准MFO还是提高了3个数量级。对于函数 $f_4$，EOMFO在最优值和方差方面的精确度达到 $e^{-2}$，说明新算法对其的寻优过程中具有良好的稳定性；另外，在平均值和最差值方面，新算法EOMFO的求解精度与标准MFO相比提高了3个数量级。

多峰函数方面，对于函数 $f_5$，EOMFO在平均值方面比标准MFO只有少量的提升，但在最优值方面却达到了 $e^{-4}$，比标准MFO提高了5个数量级。对于函数 $f_6$，EOMFO的最优值精度达到了 $e^{-8}$，比标准MFO提高了9个数量级，其平均求解精度也达到了 $e^{-2}$。对于函数 $f_7$，EOMFO的最优值精度为 $e^{-1}$，虽没有取得很好的求解精度，但与标准MFO相比，也提高了7个数量级；另外，在最优值和方差方面，EOMFO所求值均比原算法提高了8个数量级。由前面的比较结果可知，与标准MFO算法相比，EOMFO算法搜索最优值的能力更好，求解的最优值也更接近理论最优值。

为了更好的对比标准MFO算法和EOMFO算法的性能，选取了4个函数的收敛曲线图，如图1~4所示。

Figure 1. Curve of fitness for f₁

图1. f₁的适应度曲线

Figure 2. Curve of fitness for f₃

图2. f₃的适应度曲线

Figure 3. Curve of fitness for f₅

图3. f₅的适应度曲线

Figure 4. Curve of fitness for f₆

图4. f₆的适应度曲线

从以上4幅图可以看到EOMFO算法的收敛速度明显要高于标准MFO算法，且求解精度也有一定的提升。标准MFO算法在迭代一定的次数后便陷入局部最优而很难跳出，而EOMFO算法由于针对精英个体执行反向学习，使其具有比标准MFO算法更好的跳出局部最优的能力，从而能够更快的向理论最优值收敛，并且随着迭代次数的增长，所求结果的精度有进一步提升的可能。

4. 结束语

标准飞蛾扑火优化算法是一种近几年提出的新型算法，文中将精英反向学习加入到标准的飞蛾扑火优化算法当中。改进后的新算法EOMFO对于避免陷入局部最优具有一定的作用，可以更快地收敛到全局最优值，并且对于提高算法寻优速度和精度方面有很好的作用。从文中选取的7个函数优化的结果可知，EOMFO算法不仅提高了进化速度，并且取得了更精确的函数值，说明EOMFO算法是可行的，并且是优于标准的MFO算法的。另外，EOMFO算法在收敛速度等方面有不足，还需进一步研究。

基金项目

广西高校中青年教师基础能力提升项目(No. 2018KY0701, 2019KY0874)，广西科技厅基地和人才专项(No. AD16450003)。