记忆增强的莱维飞行引力搜索算法

2022-03-01刘紫阳庞志华郑韩飞

计算机仿真 2022年1期

刘紫阳，庞志华，陶佩，郑韩飞

(1. 北华航天工业学院计算机学院，河北廊坊 065000；2. 机械科学研究院，北京 100044)

1 引言

引力搜索算法(Gravitational Search Algorithm，GSA)是Esmat Rashedi等人提出的一种基于万有引力定律的群体智能优化算法[1]。该算法将搜索粒子看作在空间中遵循力学定律运行的物体，在万有引力作用下物体间相互吸引而发生位移。GSA认为适应度越大的粒子，其质量也越大，粒子不断向适应度大的粒子逼近，由此得到问题的最优解[2]。

引力搜索算法原理简明、过程简单且对有些问题优化能力明显优于粒子群优化算法(Partiticle Swarm Optimization，PSO)、遗传算法等一些常见的智能优化算法[1]，因此在系统辨识、分类、函数优化等领域得到广泛应用[3～6]。但标准的引力搜索算法种群更新完全依赖于粒子间的相互作用，粒子都朝着质量大的粒子方向移动，迭代后期粒子更新变缓，种群趋于一致，导致算法过早收敛，容易陷入局部最优。

为解决该问题，文献[7]根据迭代过程中粒子的信息熵调整粒子速度更新的比例系数，但比例系数按照区间由指定的三个正态分布产生，缺乏适应性。文献[8]将粒子群优化算法中全局最优和局部最优的概念引入GS以增强算法的记忆性，但同时会削弱算法在初期的全局探索能力。文献[9]通过反向策略增大种群规模，扩大搜索范围，然而该策略是以计算量为代价，且适用范围有限。

本文提出了基于莱维飞行的引力搜索算法(Levy Flights based Gravitational Search Algorithm，LGSA)，将莱维飞行策略应用到种群位置更新过程，使算法在迭代后期仍具有较强的随机性，保持搜索粒子的多样性，增强粒子挣脱大粒子束缚的能力，抑制算法早熟，从而取得更好的寻优性能。

2 记忆增强的莱维飞行LGS算法

2.1 GS算法

引力搜索算法是对遵循万有引力定律的粒子移动过程进行模拟的群体智能优化算法。粒子受到种群中其它粒子的引力而产生加速，从而改变速度和位置。粒子的引力与粒子质量成正比，在引力的作用下，粒子将朝着质量大的粒子方向移动，从而算法收敛。

种群包含N个粒子，第i个粒子的位置为

(1)

在第t次迭代中，粒子j对粒子i的引力为

(2)

式中，Mpi代表粒子i的被动引力质量，Maj代表粒子j的主动引力质量，Rij表示粒子i和j之间的欧式距离，ε是防止分母为0的常数。其中粒子质量

(3)

式中，fiti(t)表示粒子i在第t次迭代时的适应值，对于求最小值问题，best(t)和worst(t)的定义如下

best(t)=minfitj(t)，j∈{1，…，N}

worst(t)=maxfitj(t)，j∈{1，…，N}

(4)

粒子质量通过适应值来衡量，具有较大质量的粒子对应较好的解。

为了赋予算法随机性，粒子i在方向d上受到的合力定义为其它粒子引力的随机加权和

(5)

r是服从[0，1]均匀分布的随机数。

根据力学定律，粒子i在方向d上产生的加速度

(6)

因此，粒子i下次迭代时的速度和位置定义为

(7)

式中，q服从[0，1]均匀分布，引入q以增加搜索过程中的随机性，初始速度v0全部设为0。

为了平衡算法的探索和开发能力，引力搜索算法采用小粒子忽略策略，即随着迭代次数增加，线性地减少参与合力计算的粒子数量，将具有较大质量粒子的引力纳入合力计算，而抛弃那些小质量粒子的引力。因此，式(5)可重新定义为

(8)

引力常数G(t)在迭代开始时进行初始化，然后随迭代增加而减少以调节寻优精度[1]

(9)

GS算法中适应度高的粒子有更大的引力质量，产生更强的引力，其余粒子向大质量粒子移动。惯性质量阻碍粒子运动，因此惯性质量大的粒子移动较慢，但有较好局部开发能力。GSA是一种缺少记忆的算法[1]，每次迭代都会更新所有粒子的位置，而不会考虑其适应度是否较上次有所提高。

2.2 莱维飞行

自然界中，许多动物觅食路径是一个随机或近似随机游走过程，动物对方向的选择隐式取决于可以数学建模的概率[10，11]，而莱维飞行是对这种随机游走过程的模拟[12，13]。莱维飞行的步长满足一个重尾(heavy-tailed)的稳定分布[14]，这种形式的行走呈现出短距离的探索与偶尔较长距离行走相间的特点，如图1所示。Mantegna提出了一种用正态分布产生莱维分布随机数S的方法

图1 Levy飞行在二维空间上产生的移动轨迹

(10)

(11)

其中，u～N(0，σ2)，v～N(0，1)。

2.3 LGS算法

LGS算法在种群位置更新过程中加入莱维飞行策略，扩大搜索范围，增加种群多样性，使算法更容易跳出局部最优点。首先，莱维飞行步长因子随迭代次数动态调整，使得算法在迭代初期能充分发挥GSA的全局探索能力，而随着迭代次数增加，莱维飞行随机步长作用逐步凸显，搜索粒子能继续保持多样性，使算法拥有较好局部开发性能的同时兼顾全局搜索性。步长因子定义

(12)

式中，α0为步长因子初始值，t为当前迭代次数，T为预计迭代总次数。步长因子随时间非线性递增，如图2所示。

图2 步长因子随时间变化曲线

其次，莱维飞行随机步长以历史最优粒子位置为指导，使粒子位置更新在随机性的基础上具备指导性。最后，与引力更新不同，莱维更新只对适应度有提高的粒子进行更新。如果粒子加入莱维飞行随机步长后适应度较引力更新后退化，则该粒子只进行引力更新。该策略是为了增强算法对优秀粒子的记忆能力，避免莱维飞行在算法初期对引力搜索全局探索的干扰，确保种群整体朝着适应度更优方向进化。莱维更新方式

(13)

LGS算法流程如图3所示。从图3可以看出，引力更新是一种缺乏记忆的更新方式，即在一次迭代中，无论粒子更新后适应度是否提高都进行位置更新。而莱维更新则只选择加入随机步长后适应度未退化粒子进行莱维更新，其余则保持引力更新位置，以此增强算法对优秀粒子的记忆能力。记忆增强策略可以避免加入莱维飞行随机步长而带来的粒子退化，迫使粒子向更优适应度方向进化。

图3 LGS算法流程图

对于GS算法，随着迭代次数的增加，搜索粒子适应度提高，惯性质量增大，粒子移动变缓，所以算法后期粒子适应度更新进度减弱，局部开发能力增强，但同时容易陷入局部最优。如果仅依靠粒子间的引力作用，粒子难以跳出局部最优的束缚，如图4所示。图中显示的是Schwefel函数(表1函数2)在1000次迭代中适应度变化和算法进化情况，虚线为标准GS算法，实线为LGSA。进化曲线含义为适应度随时间的累计提高次数，即进化次数，纵坐标数值越大说明算进化次数越多。从图4可以看出，在迭代初期，两种算法进化次数接近，随着迭代次数增加，GSA进化化次数快速增长，但适应度却变缓平稳，说明GSA每次更新对函数的优化力度很小，算法陷入局部极小值。而LGSA进化次数变化平缓，但函数进化幅度逐步增加，说明LGSA每次更新都对适应度带来了明显的提高，粒子逐步接近全局最优解。

图4 Schwefel21函数适应度进化和算法进化示意图

3 实验结果与分析

为验证LGS算法的有效性，实验将LGSA与引力搜索算法GSA和具有莱维飞行特性的布谷鸟算法[15，16](Cuckoo Search Algorithm，CSA)在10个常见基准函数上进行测试，基准函数见表1。基准函数包含了5个单峰函数(F1-F5)和5个多峰函数(F6-F10)。

3.1 实验参数

为使算法的比较过程更为公平，CSA参数与文献[10]保持一致，即发现概率Pα=0.25，步长因子α=1。GSA和本文算法参数均与文献[1]保持一致，即式(9)中的G0=100，β=20。本文算法莱维飞行步长因子初始值α0=0.3。三种算法迭代次数均设为设为1000，种群大小为50(与文献[1]一致)。

3.2 实验结果与分析

表2展示了3种算法执行30次的测试结果，包括平均值、最大值、最小值和方差。为保证3种算法的起点一致，3种算法初始解设为相同。从表2可以看出，LGS对大部分函数的平均寻优精度和稳定性上优于GS和CS算法。对于测试函数单峰函数SumSquares、多峰函数Alpine，LGS算法的寻优精度远大于GS和CS算法。

表2 实验结果对比

为直观表示算法寻优过程的区别，图5-图10展示了部分测试函数在一次实验中的适应度进化曲线。可以看出，LGS算法相较于GSA和CSA全局探索能力更强，不易陷入局部最优。在迭代初期LGS和GS算法的适应度基本一致，这是因为步长因子随迭代次数动态调整，算法在迭代初期以引力更新为主，充分发挥GSA的全局探索能力；随着迭代次数增加，引力更新幅度减缓，LSG转向局部开发，而莱维步长因子的增大，导致莱维飞行随机步长作用逐步凸显，搜索粒子能继续保持多样性，使算法拥有较好局部开发性能的同时兼顾全局搜索性，有更大几率跳出局部最优，找到全局最优值。