群智能优化算法属于元启发式算法的一类, 该类算法是基于对自然界各类生物捕食或者进化的一种模拟. 通过对这些行为研究, 总结出各类生物的行为规律, 将其模型化, 在相对应的搜索空间内进行搜索, 从而达到找到全局最优的目标^{[ 1- 3]}. 同时, 由于群智能优化算法自身所具有的鲁棒性强, 操作性简单和易于实现的特点, 该类算法也被众多的学者关注研究, 如: 基于群狼捕食的灰狼算法(grey wolf algorithm, GWO)^{[ 4- 6]}、基于座头鲸用汽泡网进行捕食的鲸鱼算法(whale algorithm, WOA)^{[ 7, 8]}, 基于麻雀种群觅食的麻雀搜索算法(sparrow search algorithm, SSA)^{[ 9]}等.

其中SSA是一种较为新颖的群智能优化算法, 在2020年由薛建凯首次提出^{[ 9]}. SSA通过模拟麻雀群体觅食的生物行为, 将麻雀种群分为发现者、加入者和预警者3类不同的子群体, 3个子群体之间按照麻雀觅食的行为规律, 相互合作竞争, 最终寻觅到种群所需要的食物. 相比较于WOA、GWO, SSA具有稳定性更好, 精确度值更高和参数更少的特点. 但在SSA中, 如果麻雀种群的初始位置在搜索空间内分布不均, 易导致最终的寻优效果差; 其次发现者在搜索寻优的过程中, 在搜索前期, 容易因为搜索步长过大, 有可能错过最优解; 在搜索后期, 经过多次的迭代更新, 发现者的搜索步长非常容易造成过小的情况, 此时极易被局部峰值所影响, 将局部峰值当作全局最优, 作为最优解进行输出, 造成算法的精度有所下降; 当发现者进行广泛搜索时, 发现者各个维度的适应度值都在变小; 当发现者发现了天敌时, 会按照正态分布的特征移动到安全位置. 而这两个操作大概率会导致算法在迭代一开始就有向全局最优靠近的趋势, 容易导致算法的收敛结果趋于早熟, 错过最优解, 陷入到局部最优; 同时SSA没有平衡好算法前期的全局搜索和算法后期的局部搜索, 因此在高维复杂问题上, SSA容易收敛过早, 陷入局部最优^{[ 10- 13]}. 为改善上述问题, 本文提出基于多策略融合的麻雀搜索算法(ISSA). 在种群的初始化阶段, 引入高维Sine混沌映射, 提高初始种群的多样性和质量; 在搜索阶段, 引入衰减因子作用在发现者群体, 并通过柯西变异和变化选择策略对每次迭代过程中的最优解进行变异扰动, 从而提高算法局部搜索和跳出局部最优的能力.

1 麻雀搜索算法

假设当前搜索空间D维, 可以将由n只麻雀构成的麻雀种群表示为X_i=[x_i1, x_i2, x_i3, …, x_iD], i=1, 2, 3, …, n. 其中x_{i j}表示种群中第i只麻雀在第j维的位置. 每只麻雀的适应度值表示为F_i=f(X_i), i=1, 2, 3, …, n.

1.1 发现者位置更新

发现者会优先选择适应度值较好的位置, 从而为加入者和整个种群提供食物的位置来源. 数量一般占种群数量的10%–20%, 发现者位置更新公式如下:

$ X_{i, j}^{t + 1} = \left\{ {\begin{array}{*{20}{l}} {X_{i, j}^t \cdot {\text{exp}}\left( {\dfrac{{ - i}}{{\alpha \cdot ite{r_{\max }}}}} \right), \begin{array}{*{20}{c}} {}&{} \end{array}{R_2} \lt ST} \\ {X_{i, j}^t + Q \times L , \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {}&{} \end{array}} \end{array}\qquad{R_2} \geqslant ST} \end{array}} \right. $

(1)

其中, t表示迭代次数, iter_max表示最大迭代次数, α是一个取值[0, 1]之间的随机数.R₂表示警报值, 取值[0, 1]之间.ST表示安全阀值, 阈值设定为[0.5, 1]之间.Q表示服从正态分布的随机数, L表示1×d的单位矩阵.

1.2 加入者位置更新

加入者是除发现者以外的个体. 加入者利用发现者从而获取食物, 因此加入者自身的适应度值较低. 而且加入者总会跟随着适应度值最高的发现者, 从而获取食物, 甚至会与发现者争夺食物. 加入者位置更新公式如下:

$ X_{i, j}^{t + 1} = \left\{ {\begin{array}{*{20}{c}} {Q \cdot \exp \left( {\dfrac{{X_{{\rm{worst}}}^t - X_{i, j}^t}}{{{i^2}}}} \right) , \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {}&{} \end{array}\quad\;{\text{if}}}&{{{i}} \gt \dfrac{{{n}}}{2}} \end{array}} \\ {X_P^{t + 1} + \left| {X_{i, j}^t - X_P^{t + 1}} \right| \cdot {A^ + } \cdot L , \begin{array}{*{20}{c}} {}&{} \end{array}{\rm{otherwise}}} \end{array}} \right. $

(2)

其中, X_worst表示当前麻雀个体所处的位置是最差位置. L表示1×d的矩阵, 该矩阵中的全部元素都为1. A表示的是1×d的矩阵, 其中的元素只有1或是−1, A⁺=A^T(AA^T)⁻¹.X_P表示当前麻雀所处位置是最好位置.

1.3 预警者位置更新

预警者则是相对整个种群而言, 负责种群的警戒作用, 位置更新公式如下:

$ X_{i, j}^{{{t}} + 1} = \left\{ {\begin{array}{*{20}{l}} {X_{{\text{best}}}^{{t}} + \beta \cdot \left| {X_{i, j}^t - X_{{\rm{best}}}^t} \right| , \begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} \quad{{\rm{if}}}&{{f_i} \gt {f_g}} \end{array}} \end{array}} \\ {X_{i, j}^t + K \cdot \begin{array}{*{20}{c}} {\left( {\dfrac{{\left| {X_{i, j}^t - X_{{\rm{worst}}}^t} \right|}}{{\left( {{f_i} - {f_w}} \right) + \varepsilon }}} \right)} , &{\begin{array}{*{20}{c}} {{\rm{if}}}&{{f_i} = {f_g}} \end{array}} \end{array}} \end{array}} \right. $

(3)

其中, X_best表示当前全局最优位置, β是控制麻雀个体移动的步长系数, 是服从正态分布的随机数.K是一个随机数, 控制麻雀个体移动的距离和方向, 取值[−1, 1]之间.f_g和f_w分别表示当前全局最优的适应度值和当前全局最差的适应度值. $ \varepsilon $ 是非常小的值, 避免分母出现0.

2 基于多策略融合的麻雀搜索算法 2.1 高维Sine映射

Sine映射属于折叠次数无限的映射模型, 根据三角正弦函数变形而来^{[ 14]}. Sine混沌映射表达式如下:

$ \left\{\begin{array}{l} {{X}}_{{n}+1}=\alpha \text{sin}\left(\pi {{X}}_{{n}}\right) , \begin{array}{cc}& \end{array}{n}=0\text{, }1\text{, }\cdots \text{, }N\\ {Y}_{{i}, {j}}={L}_{j}+\left(1+{X}_{i, j}\cdot \dfrac{{U}_{j}-{L}_{j}}{2}\right)\end{array}\right. $

(4)

其中, X_n表示混沌序列, 范围在[−1, 1].U_j和L_j表示当前第i只麻雀个体在第j维的搜索空间的上下限.α是系统参数, α越接近1, 混沌效果越好.

但低维混沌系统的随机性不如高维混沌系统, 同时会让处于混沌状态的参数空间变得狭隘, 造成种群在搜索空间内分布不均. 因此引入高维Sine混沌映射^{[ 15]}, 其系统方程表达式如下:

$ \left\{ {\begin{array}{*{20}{l}} {{{{d}}_{{{i}} + 1}} = {{{\rm{sin}}}}\left( {\mu \cdot \pi \cdot {{{d}}_{{i}}}} \right)} \\ {{{{e}}_{{{i}} + 1}} = {{{\rm{sin}}}}\left( {\mu \cdot \pi \cdot {{{e}}_{{i}}}} \right)} \\ {{{{w}}_{{{i}} + 1}} = {{{d}}_{{{i}} + 1}} + {{{e}}_{{{i}} + 1}}{\text{ mod }}1} \end{array}} \right. $

(5)

其中, μ是Sine混沌映射中的控制参数. d_i和e_i分别是两组由Sine混沌映射产生的混沌序列, W_i+1是迭代混沌序列. 如 图1所示, 图1(a)是Sine映射的散点图, 图1(b)是高维Sine映射的散点图. 可以明显看出Sine映射形成的散点在一定区域内分布不均, 高维Sine混沌映射相较于Sine混沌映射具有更好的混沌特性, 个体可以相对更加均匀分布在搜索空间中.

2.2 自适应衰减因子机制

麻雀搜索算法的搜索阶段共分为发现者阶段、加入者阶段、预警者阶段3个步骤. 步骤1, 更新发现者位置, 当发现者位置更新完后, 筛选出当前阶段的最优和最差个体. 加入者会根据式(2)进行位置更新: 适应度值较差的加入者会远离最差个体; 适应度值较好的加入者会靠近最优个体. 当加入者位置更新完后, 再次进行筛选, 选出新的最优和最差个体, 此时预警者根据式(3)再次进行位置更新: 如果麻雀个体的适应度值优于此时新的最优个体, 那么根据当前新的最优个体的位置进行更新, 反之则根据最差个体的位置进行更新. 因此在步骤1中, 发现者的位置更新, 会影响到后续步骤2和步骤3中的加入者和预警者的位置更新, 从而影响到最优值的寻找^{[ 16]}.

图2中红圈表示第1步骤的发现者位置更新, 对后续第2步骤的加入者位置更新和第3步骤的预警者位置更新有着重要的作用.

衰减因子^{[ 17]}其本质是一个非线性的, 随着迭代次数增加而递减的函数, 其表达式如下:

$ M\left({t}\right)={\text{e}}^{-30\left({ \frac{1}{T}}\right)}, \begin{array}{cc}& M\in \left[0.3\text{, }0.7\right]\end{array} $

(6)

其中, t是当前迭代次数, T是最大迭代次数. 受其指数形式影响, 在搜索前期, 麻雀个体受衰减因子M影响, 搜索步长较大, 在搜索空间内可以进行全面搜索, 充分发挥算法前期的全局搜索能力; 在搜索后期, 随着衰减因子M值的递减, 麻雀个体的搜索步长逐渐变小, 搜索精度提升.

引入自适应衰减因子作用于发现者. 添加了衰减因子后的发现者位置更新公式表达式如下:

$ X_{{{i}}, j}^{{{t}} + 1} = \left\{ {\begin{array}{*{20}{l}} {M(t)\left[ {X_{i, j}^{t + 1} \cdot \exp \left( {\dfrac{{ - \mathop {{i}}\nolimits^2 }}{{\alpha \cdot ite{r_{\max }}}}} \right)} \right], {R_2} \lt ST} \\ {X_{i, j}^t + M\left( t \right)\left[ {Q \times L} \right], \begin{array}{*{20}{c}} {}&{} \end{array}\qquad{R_2} \geqslant ST} \end{array}} \right. $

(7)

根据式(7)添加衰减因子后, 发现者在迭代前期的搜索能力变强, 在搜索空间内进行充分移动, 更好进行全局的搜索, 充分发挥算法前期的全局搜索能力; 迭代后期, 随着衰减因子M的变小, 发现者的搜索步长逐渐变小, 可以更好地进行局部搜索, 提高算法寻优的精度, 从而找到全局最优解.

2.3 柯西变异和变化选择策略

柯西变异基于柯西分布, 柯西分布在原点两侧的峰值比高斯分布小, 且逼近0的过程较为平缓, 速度慢, 扰动能力更佳.

标准柯西分布概率密度函数表达式如下:

$ F\left({x}\right)=\frac{1}{\pi }\cdot \frac{1}{{{a+x}}^{2}}\text{, }{x}\in \left(-\infty \text{, }+\infty \right) $

(8)

根据式(9)引入柯西变异作用在每次迭代的最优解x_best, 通过对最优解进行变异扰动产生新解x_new, 比较x_best和x_new的适应度值优劣, 较优一方作为新的最优解, 继续参与搜索优化, 柯西变异表达式如下:

$ {{{x}}_{{\text{new}}}} = {{{x}}_{{\text{best}}}}\left( {1 + \tan \left( {\pi \left( {{{u}} - \frac{1}{2}} \right)} \right)} \right) $

(9)

通过对最优解进行扰动变异得出新解, 虽然弥补了算法陷入局部极值的缺陷, 提高了局部开发的能力, 但如果对变异不加以调节和约束, 对每次迭代的最优解都进行扰动, 会掩盖算法本身的搜索特点. 因此本文引入变化选择策略^{[ 18- 22]}, 用来调节柯西变异算子的使用范围, 表达式如下:

$ {P_{{{{\rm{dy}}}}}} = {P_1} - \left( {{P_2} \times \left( {ite{r_{\max }} - iter} \right)/ite{r_{\max }}} \right) $

(10)

$ \left\{ \begin{array}{*{20}{l}} { x_{\rm{new}} = x_{\rm{best}} \left( 1+ tan \left( \pi \left(u - \dfrac{1}{2}\right)\right) \right), \; {\rm{if}} {P_{{\rm{dy}}}} \gt {P_{{\rm{rd}}}}}\\ { x_{\rm{new}} = x_{\rm{best}} } , \qquad\qquad\qquad\qquad\;\; {\rm{if}} \; {P_{{\rm{dy}}}} \leqslant {P_{{\rm{rd}}}} \end{array} \right. $

(11)

其中, P_dy是变化选择概率, P_rd是[0, 1]之间的随机数. 经过反复测试可知当P₁、P₂分别取0.5和0.1时, 效果最佳. 在算法前期, 变化选择概率P_dy数值较小, 对最优解进行变异扰动的概率较低, 从而实现小范围扰动, 使得算法在搜索前期可以发挥ISSA的本身的搜索特点, 同时小概率的变异扰动也可以间接补充算法前期的搜索能力; 而在算法后期, 算法易陷入到局部极值, 此时变化选择概率P_dy数值较大, 进行变异扰动的概率较高, 从而实现大范围扰动, 提高了算法跳出局部最优的能力.

2.4 ISSA算法流程

Step 1. 设置参数.种群中麻雀的数量共有n只, 最大迭代次数T, 发现者比例α, 加入者比例(1–α), 预警者比例γ, 种群的警戒阈值R₂等.

Step 2. 利用式(6)高维Sine混沌映射对麻雀种群进行初始化.

Step 3. 计算当前各个麻雀适应度值, 将麻雀从优到劣进行排列.

Step 4. 根据α比例大小来选取适应度值较优的麻雀作为发现者, 按式(8)引入衰减因子进行位置更新.

Step 5. 其余个体作为加入者, 按照式(2)进行位置更新.

Step 6. 麻雀种群中随机选取γ比例大小的个体作为预警者, 按照式(3)进行更新.

Step 7. 当次迭代完成之后, 计算每个麻雀个体的适应度值, 更新最优位置x_best和最差位置x_worst的适应度值.

Step 8. 计算P_rd和P_dy, 如果P_rd小于P_dy对最优位置进行柯西变异得出新解x_new, 比较x_best和x_new, 较优一方作为新的最有位置; 如果P_rd大于P_dy, 不执行变异操作.

Step 9. 判断当前循环迭代是否达到最大迭代次数, 如果是, 循环结束, 输出最优值; 如果不是, 返回Step 4.

3 仿真实验与结果分析 3.1 实验环境和平台

实验环境的参数如下.

(1)电脑操作系统: Windows 10.

(2)编译工具: Matlab 2021b.

3.2 测试函数

为验证ISSA性能, 随机抽取6个benchmark标准测试函数, 选择多策略融合的麻雀搜索算法(ISSA)与麻雀搜索算法(SSA)、灰狼算法(GWO)和鲸鱼算法(WOA)进行比较. 测试函数中F₁、F₂、F₃、F₄是高维单峰函数, 在其所考虑的区间范围内只有一个严格的峰值, 可以测试算法求取最优值的性能; F₅是高维多峰函数, 有多个局部峰值, 测试算法对于复杂问题是否具有足够的能力来解决; F₆的最优值所在区域比较狭窄, 可以用来检测算法的局部搜索的能力. 如 表1所示.

3.3 算法参数设置

为实现算法对比实验的公平性和有效性, 将算法的最大迭代次数统一设定为500次, 发现者占比α为0.2, 预警者占比γ为0.2.

为减少运行次数较少所带来的结果偏差, 在实验中我们对每个标准测试函数分别运行30次, 分别取各标准测试函数的最差值, 最优值, 均值和方差. 平均值可以反映算法寻找最优值的精度, 方差可以反映算法的稳定性. 测试结果如 表2所示.

3.4 数据分析

从 表2的对比实验数据可以看出, 在F₁, F₂, F₃, F₄中, 相比于SSA, WOA和GWO, ISSA无论是最优值, 最差值, 平均值还是方差, ISSA均有较为显著的优化提升; 而在F₅多峰多维测试函数上, 虽然相比于WOA而言, ISSA的寻优能力较为不足, 但跟SSA相比, 还是有很大的提升, 寻优结果会更加逼近函数理论上的最优值−12569.5; 在F₆函数中, ISSA算法的4项测试标准的数值也是优于其余的3个优化算法, 可以说明ISSA算法在测试函数搜索区间狭隘的情况下, 也具有一定优势.

为更直观准确地描述ISSA的优势, 本文根据适应度值和算法的迭代次数, 绘制了测试函数的函数收敛曲线图, 如 图3. 结合 表2的实验对比数据和 图3的测试函数收敛曲线图, 可以明显看出, ISSA相比于其他3种对比算法, ISSA的寻优精度和收敛效果都得到了显著提升. 其中F₁是单峰多维函数, 函数平面较为平缓, 比较考验算法的收敛能力. 结合F₁的收敛曲线和 表2中F₁的实验对比数据, 可以明显看到, 在搜索前期, 到迭代第100次的过程中, ISSA比SSA的精度更高, 稳定性更好, 而在搜索后期, SSA的收敛曲线逐渐趋于平稳, 搜索能力下降, 而ISSA的收敛曲线依旧较为陡峭, 证明在搜索后期, ISSA的搜索寻优能力依旧保持, ISSA的寻优精度和收敛效果得到了很大的提升. 在F₂中, 结合 表2中F₂的实验对比数据, 在搜索前期, ISSA的寻优精度和稳定性依旧比SSA要好, 而且在迭代第400次的时候, SSA的收敛曲线已经趋于平缓, 搜索能力下降, 局部开发的能力不足; 而ISSA在这个时候的收敛曲线依旧相对比较陡峭, 说明在搜索后期, ISSA的搜索能力和局部开发的能力比SSA更好. 在F₃中也是, ISSA无论是寻优精度还是收敛效果相较于SSA都有了显著的提升. 在F₄中, 迭代第250次到第400次的时候, 收敛曲线较为陡峭, 说明在搜索后期ISSA的跳出局部最优的能力相较于SSA有了提升, 而且到迭代第400次的时候, ISSA还能继续向下收敛, 说明ISSA的寻优的高精度, 且收敛效果好. 在F₅中, 结合 表2中F₅的实验对比数据可知, 虽然相比于WOA和SSA, ISSA在搜素前期优化提升的幅度不大, 但在迭代到第100次的时候, ISSA的收敛曲线更加向下的收敛于一个值, 说明ISSA在高维复杂问题上寻优精度更高. 在F₆中, 到迭代第100次的时候, ISSA就已经搜寻到了一个较优的适应度值, 收敛效果好, 寻优的精度高.

4 结束与展望

本文对于SSA容易陷入局部最优和搜索后期精确度较低等问题, 通过使用高维Sine映射对种群进行初始化, 提高了种群的多样性; 引入衰减因子作用在发现者的位置更新, 平衡了全局搜索和局部寻优的能力; 并且通过对最优解采取变异扰动策略, 提高了算法跳出局部最优的能力, 最终提出了ISSA. 通过实验证明ISSA可以有效地弥补SSA的不足. ISSA的不足之处在于优化措施较为粗糙, 且对高维多峰函数的优化提升并没有高维单峰函数优化提升的明显. 接下来的研究方向和研究工作是在保持对高维单峰函数的明显的优化提升的前提下, 提高对高维多峰函数的优化效果. 此外, 结合基于SSA提出的ISSA, 求解优化问题如最优路径规划或是无人机定位等问题, 这些也是有价值的研究探索方向.