智能优化算法：蛾群优化算法

摘要：蛾群算法 (Moth Swarm Algorithm, MSA）是 Al-Attar AliMohamed 于2016年提出的新兴元启发式智能优化算法，它模拟自然界蛾群在夜间朝月光飞行的行为。蛾群算法具有结构简单，参数较少，求解精度高以及鲁棒性强等优点。

1.算法原理

蛾群算法（Moth Swarm Algorithm , MSA）是 2016 年由 Al-Attar Ali Mohamed 提出，受到飞蛾趋光性以及飞行方式的启发而设计的一种元启发式算法。与大多数群智能算法不同的是，在蛾群算法模型中，将整个蛾群划分为不同作用类型的飞蛾，更真实地体现了群体的合作行为，在一定程度上平衡了算法探测和开采能力。

在蛾群算法中，光源位置代表优化问题的可能解，光源的发光强度代表问题解的适应度值。MSA 算法中蛾群由三部分组成，分别为探路蛾，勘探蛾以及观察蛾。
探路蛾：这部分蛾以一定的方式在优化空间中来发现新的区域。这部分蛾的主要任务是找到最好的位置作为光源来引导飞蛾主体的移动。
勘探蛾：这部分蛾在围绕着被探路蛾标记出的最好光源附近以对数螺旋线的方式来移动。
观察蛾：这部分蛾直接移动到被勘探蛾标记出的最亮光源处。

1.1 初始化蛾群

在蛾群初始化阶段，假设在 $d$ 维搜索空间中，种群数目为 $n$ ，随机生成的( $n*d$ ) 只蛾（初始候选解）将遵循以下的数学公式：
$x_{i,j}=rand*(x_j^{max}-x_j^{min}) + x_j^{min} \tag{1}$
其中 $x_j^{max}$ 和 $x_j^{min}$ 分别代表算法的上界和下界。

1.2 探路蛾阶段

在探路蛾阶段，蛾群以轮盘赌的方式选择若干只蛾作为下一阶段的指导蛾，位置更新公式如下：

探路蛾阶段：提出的多样性交叉点，交叉操作的策略可以扩大种群的多样性。首先，对第 $t$ 代的个体在 $j$ 维中服从以下分布：
$\sigma_j^t = \frac{\sqrt{\sum_{i=1}^{n_p}(x_{ij}^t -\overline x_j^{t})/n_p}}{\overline x_j^{t}}\tag{2}$
式中， $\overline x_j^{t} = \sum_{i=1}^{n_p}x_{ij}^p/n_p$ ,领头蛾的数目为 $n_p$ ，变量因子 $u^t$ 为度量领头蛾是否进行变异机制，服从以下的分布：
$u^t = \sum_{j=1}^d\sigma_j^t/d\tag{3}$
当组成探路蛾群的蛾分散的时候将纳入 $c_p$ 种群进行变异操作，服从以下的公式:
$j\in c_p ,if\, \sigma_j^t\leq u^t \tag{4}$
蛾群的交叉率随着迭代的进行在动态的变化。对 $n_c\in n_p$ 的交叉机制中，本算法提出的子矢 $\vec v_p = [v_{p1},v_{p2},...,v_{pn_c}]$ 是用扰乱所选择的主矢量 $\vec x_p=[x_{p1},x_{p2},...,x_{pn_c}]$ 生成的，公式如下:
$\vec v_p^t = \vec x^t_{r1}+L_{p1}^t.(\vec x^t_{r2} - \vec x^t_{r3}) + L_{p2}^t.(\vec x^t_{r4} - \vec x^t_{r5}),r1\neq r2\ne r3 \ne r4\ne r5\ne p\in \{1,2,...,n_p\}\tag{5}$
其中 $L_i\sim step \bigoplus Levy(\alpha)\sim 0.01\frac{u}{|y|^{1/\alpha}},u\sim N(0,\sigma_u^2),y\sim N(0,\sigma_y^2)$
$\sigma_u = \{\frac{\Gamma(1+\beta)sin(\pi \beta/2)}{\Gamma[(1+\beta)/2]\beta2^{(\beta-1)/2}}\},\sigma_y = 1$
为了获得较好的飞行路径，每只探路蛾通过和变异过后的子矢量进行交互操作来更新自身的位置。完整的飞行路径 $V_{pj}$ 可以定义如下：
$V_{pj}^t=\begin{cases}v_{pj}^t,if\,j\in c_p\\x_{pj}^t,else\end{cases}\tag{6}$
轮盘赌选择机制
在以上迭代之后，每一代的适应度值将会重新计算并与探路蛾的适应度值进行比较。适应度值较好的蛾将继续保留到下一次迭代的过程中，用于求解极小值的过程表示如下:
$\vec{x^{t+1}_p}=\begin{cases}\vec{x_p^t},if\,f(\vec{V_p^t}\geq f(\vec{x_p^t}))\\ \vec{v_p^t},else \end{cases}\tag{7}$
$P_p$ 则用于评价光的强度 $fit_p$ ，两者的关系表达如下：
$P_p = \frac{fit_p}{\sum_{p=1}^{n_p}fit_p}\tag{8}$
目标函数的适应度值 $f_p$ 则表示光的强度，用于求解极小值的问题中，表述如下：
$fit_p = \begin{cases}\frac{1}{1+f_p} ,if \,f_p\geq0\\1+f_p,else \end{cases} \tag{9}$

1.3 勘探蛾阶段

勘探蛾感受到光的强度次于探路蛾， $f_n$ 为探路蛾的数量，其随着迭代次数 $T$ 的增加而减少。其公式为：
$n_f = round((n-n_p))\tag{10}$
在探路蛾搜索完成之后，将光源强度的信息传递给勘探蛾，勘探蛾紧随着更新自身的位置。每只勘探蛾 $x_i$ 将绕着人工光源 $x_p$ （轮盘赌机制选择的探路蛾）做螺旋盘旋。勘探蛾更新位置的公式如下:
$x_i^{t+1}=|x_i^t-x_p^t|.e^{\theta}.cos(2\pi\theta)+x_p^t,p\in\{1,2,...,n_p\},i\in\{n_p+1,n_p+2,...,n_f\}\tag{11}$
上式中， $θ$ 为螺旋形状常数定义飞蛾盘旋的形状，其取值范围为[r,1]之间的随机数， $r=-1-t/T$ 。在本算法中，每只蛾的分类是随着迭代次数的变化而变化的。因此，每只蛾找到光源强度比较好的位置时，将有可能变换为探路蛾。也就是说，在这个阶段会产生新的光源。

1.4 观察蛾阶段

在算法优化的过程中，随着勘探蛾数量的减少，观察蛾将会增多 $(n_o = n-n_f-n_p)$ 在优化中，该机制可以提高算法的收敛速度。在这个阶段将观察蛾的数量分为两部分，一部分为高斯游走方式更新位置(12)，另一部分加入即时记忆的联想学习机制进行位置更新(13)分别如下:
$x_i^{t+1}=x_o^t+\xi_1 +(\xi_2*gbest^t-\xi_3*x_i^t),i\in(1,2,...,n_G)\tag{12}$

$\xi_1\sim random(size(d))\bigoplus N(best_g^t,\frac{logt}{t}*(x_i^t - best_g^t))$

式中， $\xi_1$ 为高斯分布中随机生成的种群数量， $best_g^t$ 为本阶段中最好的蛾群的位置（包括探路蛾和勘探蛾）， $\xi_2$ , $\xi_3$ 为[0,1]之间的随机数。
$x_i^{t+1}=x_i^t+0.001.G[x_i^t - x_i^{min},x_i^{max}-x_i^t]+(1-g/G).r_1.(best_p^t-x_i^t)+(2g/G.r_2.(best_g^t-x_i^t))\tag{13}$
式中 $i\in\{1,2,...,n_A\}$ ， $2g/G$ 为社会因子， $1-g/G$ 为认知因子， $r_1$ 和 $r_2$ 为[0,1]之间的随机数， $best_p$ 是基于一定概率随机选出来的光源的位置。

算法步骤：

Step 1: 初始化基本控制参数：群体规模 n ，最大迭代次数 iterMax ；
Step 2: 初始化蛾群种群：按照公式（1），初始化蛾群个体在搜索空间位置；
Step 3: 根据目标函数计算适应度值，开始算法迭代过程；
Step 4: 根据探路蛾阶段位置更新公式（ 2-9 ）进行探路蛾的位置更新，目标函数计算探路蛾个体的适应度值，与初始种群适应度值作比较，选择较优的个体作为光源，引导蛾群主体的移动；
Step 5: 在勘探蛾阶段随着迭代次数增加，勘探蛾数目减少。勘探蛾绕探路蛾阶段找到的光源做按公式（11）对数螺旋线飞行，计算目标函数适应度值，如果适应度值优于光源位置的适应度值，勘探蛾将转化为探路蛾；
Step 6: 随着勘探蛾数目的减少，观察蛾的数目增多。观察蛾阶段观察蛾以高斯游走计算公式（12）和学习机制计算公式（13）来更新位置，将更新的位置根据目标函数计算适应度函数值，与勘探蛾阶段计算的适应度值作比较，较优的观察蛾转化为勘探蛾，较差的作为探路蛾；
Step 7: 用满足算法的终止条件（达到最大迭代次数），则转到 Step 7，否则进入 Step3 继续进入下一代搜索；
Step 8: 输出最优的蛾个体以及适应度值。

2.实验结果

在这里插入图片描述

3.参考文献

[1]Al-Attar Ali Mohamed,Yahia S. Mohamed,Ahmed A.M. El-Gaafary,Ashraf M. Hemeida. Optimal power flow using moth swarm algorithm[J]. Electric Power Systems Research,2017,142{5}:

[1]杨晓. 蛾群算法及其应用研究[D].广西民族大学,2018.

4.Matlab

上述代码，见个人资料

智能优化算法：蛾群优化算法

智能优化算法：蛾群优化算法

1.算法原理

1.1 初始化蛾群

1.2 探路蛾阶段

1.3 勘探蛾阶段

1.4 观察蛾阶段

2.实验结果

3.参考文献

4.Matlab

推荐阅读更多精彩内容