基于全局最优值的群搜索优化算法

熊聪聪，李俊伟，杨晓艺，王 丹

(天津科技大学人工智能学院，天津300457)

在20世纪60年代早期，人们创造了许多工具来模拟生物的行为，仿生学就此诞生.在这样的前提下，自然界有很多动物群体(蚁群、鸟群等)成为研究者关注的焦点，对动物的群体行为进行数学建模，并在计算机软件上进行模拟仿真实验，群智能(swarm intelligence，SI)算法[1-4]应运而生.其中，比较经典的群智能算法有：Colorni等[3]根据蚂蚁在寻找食物时的行为而提出的蚁群(ant colony optimizer，ACO)算法、Kenndy等[4]根据鸟群在寻找食物时的行为从而提出的粒子群(particle swarm optimizer，PSO)算法、He等[1,5]提出的群搜索优化(group search optimizer，GSO)算法.

He等[1]系统地阐述了群搜索优化算法的基本原理，解释了相关的数学模型，并将其与遗传算法(GA)、快速演化规划(FEP)[6]、快速演化策略(FES)[7]、粒子群(PSO)算法等群智能算法进行了比较和仿真实验，对比讨论该算法中的初始化参数对最终实验结果的影响.

虽然GSO在一些优化问题中显示出了比较显著的优越性，但其仍然存在部分不足之处，例如在处理一些优化问题时出现易陷入局部最优，造成收敛速度较慢、精度较低的问题.因此，许多研究者都提出了相应的改进方法.安晓伟等[8]提出了保留发现者的搜索策略和由加入者执行鱼群算法的搜索策略，通过引入鱼群算法，可以避免种群搜索陷入局部最优.在标准GSO算法的基础上，李丽娟等[9]提出了取消按角度搜索的策略，增加了控制变量随迭代次数减少而变化的概率，在一定程度上解决了标准GSO算法收敛速度慢的缺点.杨文璐等[10]提出了一种基于交叉因子的改进群搜索优化算法，通过将交叉因子和模拟退火算法结合，使得群体中粒子多样性增加，从而避免使GSO算法陷入局部最优值的可能性.景书杰等[11]提出一种群搜索优化算法，该算法通过对发现者搜索方式中加入最大下降方向，把游荡者生成策略改变为基因突变策略，从而提高了标准GSO算法的收敛速度.郝璐萌[12]提出在发现者搜索过程中引入不同的差分变异策略，提高收敛精度.王娟等[13]提出了基于改进Tent混沌映射的种群初始化和基于Levy飞行特征的跟随者更新策略，提高了解决高维复杂问题的收敛速度和求解精度.

针对GSO算法存在的问题，本文提出了一种基于全局最优值的群搜索优化(global optimal valuebased group search optimizer，GGSO)算法，该算法针对在标准群搜索优化算法发现者搜索过程中收敛速度慢，引入全局最优值，从而加速算法收敛速度.选取11组标准测试函数进行测试，并与GSO算法的测试结果比较，GGSO算法整体上相比GSO算法具有更好的收敛速度和精度.

1 群搜索优化算法

群搜索优化(group search optimizer，GSO)算法，根据群居动物搜索食物行为而设计的一种仿真模拟算法.该算法的原型是“发现者–加入者”(producerscrounger，PS)模型.在GSO算法中将研究对象按照在种群中的功能分为3类：搜索资源并共享其信息的发现者、对发现者搜索到的资源进行掠夺的加入者、执行随机搜索的游荡者.群搜索优化算法是基于动物种群之间信息共享和相互合作的特性而建立的一种智能优化算法[1].该算法模仿了动物的视觉搜索机制，在其搜索过程中，适应度值最好的个体作为发现者带头搜索，发现者按照既定的搜索角度和方向寻找更好的资源，加入者跟随发现者进行局部搜索，剩余的个体作为游荡者，根据搜索角度在当前的范围内调整自己的位置.群体中的3类个体相互协同协作完成搜索的任务，从而使所找到的资源为最优.

1.1 发现者

在每次迭代过程中，均选择适应度值最好的个体作为本次迭代过程中的发现者(producer)，发现者在共享资源的同时继续搜索资源.搜索策略是在当前位置沿着3个不同的角度进行扫描搜索，找到3个方向上不同的位置，通过式(4)—式(6)分别在其前方、左方以及右方进行扫描查找.

其中：r1∈R1为服从均值为0、方差为1的正态分布随机数；r2∈ Rn−1为[0，1)间均匀分布的随机数；lmax为搜索的最大距离，并能够通过式(7)计算得到；θmax为搜索的最大角度.

其中Ui和Li分别是取值范围的上界和下界.

如果3个随机位置中某一个要好于当前发现者的位置，就将发现者的位置和角度更新为随机位置中较好的位置和角度；反之，发现者则不改变其当前位置信息，并通过式(8)更新搜索角度，进行下一次迭代.

其中αmax∈R1为最大的搜索转换角度.

发现者如果在α次迭代后无法找到更好的资源时，通过式(9)回到0°位置.

其中α∈R1为实验人员自行确定的常数.

1.2 加入者

随机选择剩余个体的80%作为加入者(scrounger)，加入者一直跟随共享由发现者搜索到的位置资源信息，如果加入者找到比当前发现者更好的资源时，在下一次迭代中按照式(10)加入者会转换为发现者角色进行搜索.

其中r3∈Rn为服从[0，1)均匀分布的随机数.

1.3 游荡者

剩余个体作为游荡者(ranger)在搜索空间中随机分布并且进行资源搜索.在第k次迭代中，游荡者通过式(8)产生随机角度，并通过式(11)得出随机距离li，通过式(12)更新位置.

通过3种角色个体间的相互合作，更新种群信息，最终收敛得到种群中的最优个体.但是为了在搜索资源时更加方便，所以在一定程度上限制了个体的搜索界限，如果某个个体在搜索时跳出该搜索界限，会判断其是否越界，并让该个体返回到之前的搜索位置.

1.4 GSO算法整体框架

标准GSO算法流程图如图1所示.

图1 标准GSO算法流程图Fig. 1 Standard GSO algorithm flow chart

标准GSO算法(算法1)如下：

1. 输入：随机向量Xi.

2. 输出：当前最优个体位置信息.

3. 初始化种群中所有个体的角度和位置信息.

4. 计算种群个体的适应度值fvalue.

5. WHILE(iter＜MaxIter).

6. 选取发现者，按照式(4)—式(9)执行发现者操作.7. 选择剩余成员80%作为加入者，按照式(10)执行加入者操作.

8. 选择剩余成员20%作为游荡者，按照公式(11)和公式(12)执行游荡者操作.

9. 计算种群的适应度值fvalue.

10. END WHILE.

1.5 GSO参数选择

2 改进的群搜索优化算法

为了提升算法在搜索空间内的资源寻优能力，提出一种基于全局最优值的群搜索优化(global optimal value-based group search optimizer，GGSO)算法.该算法以标准GSO算法的PS模型为基础，并在搜索时加入全局最优值作为发现者，提高了算法的搜索性能和收敛精度.在该算法中，先求得所有群体的适应度值，然后得到其中的最优值，在发现者的搜索过程中，加入全局最优值.在不断的迭代过程中，每一次迭代加入全局最优值以后，使得全局最优值有机会参与到发现者的搜索过程中，进而使算法可以跳出局部最优值，提升算法收敛精度，从而提高算法的全局搜索能力.

2.1 GGSO算法的实现过程

(1)在前期时，算法采用标准GSO算法流程进行进化和迭代.

(2)保存所有成员适应度值的最小值，即在迭代开始之前保存某个成员i当前位置及其适应度作为全局最优值fbestval.

(3)在发现者搜索过程中，每一轮迭代在发现者适应度值中都加入之前保存的全局最优值fbestval.

(4)与此同时，发现者、加入者和游荡者均按照GSO算法的搜索方式进行搜索.

2.2 GGSO算法伪代码

GGSO算法伪代码(算法2)如下：

1. 输入：随机向量Xi.

2. 输出：当前最优个体位置信息.

3. BEGIN.

4. 随机初始化种群种个体的位置和角度信息.

5. 计算种群个体的适应度值fvalue.

6. 选取适应度值最好的点作为发现者.

7. WHILE(迭代是否满足).

8. 将全局最优值加入发现者群体.

9. 选择发现者，由式(4)—式(9)执行发现者操作.

10. 选择剩余成员80%作为加入者，由式(10)执行加入者策略.

11. 选择剩余成员20%作为游荡者，由式(11)和式(12)执行游荡者策略.

12. 再次计算种群的适应度值fvalue，得到当前最优适应度值.

13. END WHILE.

全局最优值即在优化问题的全值域范围内得到的最优值.局部最优值即在优化问题的解在一定范围或者区域内的最优值，或者优化问题在一定的限制条件内最优值.从图2即可明显看出两者的区别.

图2 局部最优值与全局最优值示意图Fig. 2 Diagram of local optimum and global optimum

其中：B ⊂S⊆Rn，S为函数的搜索空间，则称为f (X)的局部最小值点，f ()为局部最小值.

如果存在 X*∈S，使得对∀X∈S，存在

其中 S⊆Rn为函数的搜索空间，则称 X*为f (X)的全局最优值点，f (X*)为其全局最优值.

2.3 全局最优策略

虽然GSO算法在部分问题的解决上有优越的表现，但其仍然面临在发现者搜索效果不为显著的问题.受到“适者生存”的规律启发，优秀的个体较为容易生存.因此，将全局最优策略应用到GSO算法的发现者个体选择中.算法3详细描述了该操作.

算法3：根据适应度值对种群中最优个体进行记录.

1. 输入：每轮迭代中的最小适应度值.

2. 输出：所有迭代中的最小适应度值位置信息.

3. BEGIN.

4. WHILE(Iter＜MaxIter).

5. 得到迭代中的最小适应度值fvalue及其位置信息.

6. Min(fvalue)→index.

7. END WHILE.

8. 根据index更新发现者群体信息.

9. END.

在该策略中虽然体现出了与粒子群算法较为相似之处，粒子群算法初始化得到随机粒子群，然后再通过迭代找到最优解.在之后的每次迭代中，其中的粒子通过查找局部最优值和全局最优值更新其本身的位置.当初始化粒子群后，得到其适应度值并找到全局最优值.但是，上述算法3中提到的策略与粒子群算法不同之处在于，在得到每次迭代中的最优值之后将其记录下来，最终将所有最优值均作为发现者群体进行搜索，对发现者种群产生影响，进而可以进一步得到其全局最优值.

在对具体优化问题求解时，主要思路就是找到当前空间内的局部最优值，或者说通过迭代计算找到目标函数的解，直到找到两个解没有变化为止，此时即为该目标函数的局部最优值.如果目标函数及其约束条件均为凸函数，通过算法找到的解即为全局最优值.如果目标函数不是凸函数，通过算法找到的最优值，有可能是全局最优值，也有可能为局部最优值.

3 实验仿真与结果分析

3.1 国际标准测试函数

测试过程中选取了11个国际标准函数(见表1)，主要分为两大类，单峰函数f1—f6和多峰函数f7—f11.

表1 11个测试函数Tab. 1 Eleven benchmark functions

3.2 实验环境与参数设置

实验所用到的环境为：操作系统Win10，软件Matlab2017a，运行内存8GB.实验中算法所用到的参数与初始GSO算法参数均保持一致，种群规模设置为48，种群个体维数设置为30，最大迭代次数设置为5000次，测试函数运行次数设置为50次.

3.3 实验结果及算法比较分析

通过对比标准GSO算法和GGSO算法在11个国际标准测试函数上的平均值和标准差(表2)，评价两种算法的性能.其中，平均值和标准差是同一个标准测试函数上运行50次的实验平均结果的统计.同时，黑色加粗字体表示两个算法在同一个测试函数上所取得的平均值的最优值.

表2 两种算法在11个测试函数上的比较结果Tab. 2 Compared results of the two algorithms on 11 benchmark functions

由表2可知：对于单峰函数(f1—f6)，GGSO算法收敛进度与GSO算法相差不大，f1、f2、f3、f4、f6在GGSO算法上得到的最优值优于标准GSO上的最优值，但其离散程度比标准GSO的离散程度要高.对于多峰函数(f7—f11)，除f7外，其余4个测试函数在GGSO算法上的表现均优于在标准GSO算法上的表现，且其离散程度表现不一，f9、f11的离散程度低于在标准GSO上的离散程度.在11个标准测试函数上，有9个标准测试函数在GGSO算法上的表现优于在标准GSO算法上的表现，仅有1个标准测试函数结果的精度稍逊于标准GSO算法，另有1个测试函数在两个算法上表现一致.总体表明，GGSO算法性能优于标准GSO算法.

为了更好地展示测试改进的算法在测试函数上的表现，实验中测试了迭代次数从500到5000次的表现，以测试函数f6和f11的结果对比为例，结果如图3和图4所示.从图3中可看出，改进的群搜索优化算法在测试函数f6上在3000次迭代之前得到的平均适应度均优于标准GSO算法，在3500次迭代后收敛速度明显优于标准GSO算法的收敛速度，且得到更好的平均适应度.由图4可知，虽然GGSO算法的收敛速度与标准GSO算法中收敛速度一致，但是可以得到比标准GSO算法更好的平均适应度.

图3 测试函数f6结果对比Fig. 3 Comparison of benchmark function f6 results

图4 测试函数f11结果对比Fig. 4 Comparison of benchmark function f11 results

4 结 论

在标准GSO算法基础上，通过对算法中发现者的搜索策略进行改进，以达到提高算法的收敛速度和精度的效果.针对标准GSO算法未考虑全局最优值的影响，通过在发现者搜索过程中加入全局最优值，一定程度增加了种群的多样性，算法的收敛速度和精度相比之前有所提高，避免了发现者在搜索时陷入局部最优.实验结果表明，标准GSO算法的不足之处在GGSO算法上有一定的改进和弥补.未来工作尚需在发现者和加入者搜索过程中加入更多优化策略，把改进过的群搜索优化算法具体应用实现.