基于混合策略改进的社会群体优化算法

张小萍 谭 欢

(1.广西大学 计算机与电子信息学院，南宁 530004；2.中国移动通信集团广西有限公司，南宁 530022)

元启发式算法可以直观有效地解决科学和工程研究领域的许多实际问题。粒子群优化算法、遗传优化算法和蚁群优化算法都是非常经典的元启发式算法。近年来又出现了许多新兴的元启发式算法，如乌鸦优化算法[1]、蝴蝶优化算法[2]和樽海鞘群优化算法[3]等，这些算法被广泛应用于光伏阵列MPPT研究[4]、冷热电联供微网日前优化调度[5]和应急救援供给点选择[6]等方面。

社会群体优化算法(SGO)是2016年提出的一种新颖的元启发式算法[7]。SGO算法将个体获取知识的方式分为提高阶段和获取阶段。在提高阶段，群体中每个个体的知识都是在最优个体的帮助下得到提高；在获取阶段，每个个体的知识是通过和其他个体进行交流或在最优个体的帮助下来获取。虽然SGO算法的收敛速度较快，但与其他元启发式算法类似，存在迭代后期种群多样性不足而易陷入局部最优的问题。刘亚军等人提出多子群的社会群体优化算法(MPSGO)[8]，采用多子群学习方法，对个体学习方法进行改进，既提高了群体的多样性，又保证了子群个体的充分进化。

针对SGO算法易陷入局部最优的问题，本次研究提出一个基于混合策略改进的社会群体优化算法(HSGO)。

1 社会群体优化算法

Satapathy等人提出的SGO算法一种新颖的元启发式算法，操作简单、易于实现，在一些实际问题的优化中取得了良好的效果。在SGO算法中，每个个体都被赋予一定的知识，具有解决某些问题的能力。通过最好的个体在群体中传播知识以及个体之间的相互交流来提高整个群体的知识水平。SGO算法分为初始化、提高和获取等3个阶段。

1.1 初始化阶段

初始化个体如式(1)所示：

Xi=Lb+(Ub-Lb)rand(1，m)

(1)

式中：m是变量的维度；Ub和Lb分别是变量的上限和下限；rand(1，m)是0～1的m维向量；Xi是种群中的第i个个体，i=1，2，…，n，n是种群个体总数。

1.2 提高阶段

在提高阶段，所有个体都向最优个体学习。假设最优个体是gb，则提高阶段的学习策略如式(2)所示：

Xnewij=cXij+r1(gbj-Xij)

(2)

式中：c是自我反省参数，取值为0～1，一般取0.2；r1是0～1的随机数；gbj是最优个体的第j维变量，j=1,2,…,m；Xij和Xnewij分别表示第i个个体更新前后的第j维变量。

1.3 获取阶段

在获取阶段，个体除了向最优个体学习，还与其他个体进行随机交流学习。获取阶段的学习策略如式(3)所示：

(3)

式中：r2和r3为0～1的随机数；f(Xi)和f(Xk)分别表示Xi和Xk的适应度。

2 基于混合策略改进的社会群体优化算法

2.1 随机搅动变量

在提高阶段，新个体的生成仅仅依赖于r1，(gbj-Xij)在迭代中相对不变。为了扩大搜索范围、增加种群多样性，受蝴蝶优化算法的启发，本次研究增加随机搅动变量r。假设r是0～1的随机数，则提高阶段的学习策略如式(4)所示:

Xnewij=cXij+r1(r2gbj-Xij)

(4)

加入随机搅动变量可以在寻优前期提升算法的全局搜索能力，在寻优后期增加种群多样性，以避免陷入局部最优。

2.2 基于精英个体的逐维改进

与其他个体相比，精英个体与全局最优解的亲和度相对较大，因此通过精英个体求得问题最优解的可能性也较大。为了提高算法的收敛速度，在每次迭代中利用精英个体对当前最优解进行改进。利用精英个体对当前全局最优解进行逐维改进，可以避免高维函数之间相互干扰，从而提高解的质量。精英个体逐维改进全局最优解的步骤如下:

Step 1将Xi按其适应度值从小到大的顺序进行排列，X1为当前最优解，前1/3个个体是精英个体。

Step 2从第2～n/3个中选择一个随机整数k，令temp=X1，fbest=f(temp)。

Step 3每次使用Xk的1个维度变量来取代temp的相应维度变量，计算出temp的适应度值，如果f(temp)

Step 4X1=temp，将逐维改进后的temp赋值给X1，则X1为改进后的全局最优解。

2.3 HSGO算法的具体步骤

Step 1初始化系统参数，利用式(1)随机初始化种群。

Step 2计算种群中个体的适应度值，记录全局最优解。

Step 3在提高阶段，使用式(4)更新个体位置。

Step 4在获取阶段，使用式(3)进行个体间交流学习，更新个体位置。

Step 5利用精英个体逐维改进全局最优解。

Step 6判断是否满足迭代停止条件，若满足则输出最优解，算法停止；否则返回Step 2。

3 仿真实验结果分析

为了测试HSGO算法的性能，选用8个不同的基准测试函数(f1，f2,…，f8)，测试算法的有效性。其中，f1—f4是单峰值函数，f5—f8是多峰值函数，如表1所示。

表1 基准测试函数

采用Matlab R2020b分别对面向全局搜索的自适应领导者樽海鞘群算法(ALSSA)[9]、具有自适应步长的柯西变异乌鸦算法(CMCSA)[10]、SGO、MPSGO与HSGO算法进行仿真实验。仿真实验环境为Windows7 64 bit系统，内存为8 GiB，CPU为Intel(R)Xeon双核2.4 GHz。为了测试的公平性，所有算法的种群个体数都为50，最大迭代次数为500次，每个算法独立测试30次，计算各个算法在不同基准测试函数中的最小值、平均值和方差，计算结果如表2所示。

表2 5种算法的仿真实验结果

由表2可知，HSGO算法在f1、f2、f3、f4和f8中方差都为0，且其平均值是所有算法中并列最小的，达到理论最优解。HSGO算法在f5中的平均值与MPSGO算法相同，是所有算法中最小的，只有方差略大于MPSGO算法。HSGO算法在f6中的平均值是所有算法中最小的。HSGO算法在f7中平均值和方差也是所有算法中最小的，达到理论最优解。综上所述，HSGO算法的求解精度和稳定性总体优于其他4种算法。

为了更加直观地观察算法的收敛精度和速度，绘制了4个多峰值函数(f5—f8)的平均收敛曲线(见图1—图4)。f1—f4是单峰值函数，相对简单，其收敛曲线不再赘述。

由图1—图4可知，HSGO算法和MPSGO算法在f5和f6中表现非常优越，有较快的收敛速度，且收敛精度较高。在f7中，只有CMCSA算法的收敛速度较慢，其他4种算法都能很快收敛到最优解域。在f8中，CMCSA算法的收敛速度最快，HSGO算法次之，且只有这2种算法搜索到了理论最优解。因此，HSGO算法在收敛速度和求解精度上都比其他4种算法好。

图1 f5的平均收敛曲线

图2 f6的平均收敛曲线

图3 f7的平均收敛曲线

图4 f8的平均收敛曲线

4 结 语

本次研究基于SGO算法提出HSGO算法。使用随机搅动策略改进提高阶段的学习方法，扩大算法的搜索范围，以避免陷入局部最优。利用精英个体逐维改进全局最优解，以加快算法的收敛速度和求解精度。根据8个基准测试函数的仿真实验结果可知，HSGO算法在求解精度和收敛速度上均优于ALSSA、CMCSA、SGO和MPSGO等4种算法。