基于混沌迁移的社会学习天牛群算法

郑 源， 付晓刚， 轩艳文

(上海电机学院 电气学院， 上海 201306)

群智能算法是模仿自然界中没有智能的个体或智能度不高的个体，在群体的交互中学到一些简单的规则，然后在群体层面中涌现出比较高级的智能。天牛须算法(Beetle Antennae Search Algorithm, BAS)[1-2]作为一种生物智能算法模拟了自然界中天牛利用天牛须来搜寻食物的过程。相比于粒子群算法(Particle Swarm Optimization, PSO)等群智能优化算法，BAS只需一个个体，参数少易于实现，对于低纬优化函数收敛速度快，质量高。邵良杉等[3]为了改进花朵授粉算法(Flower Pollination Algorithm, FPA)的收敛速度和精度的问题，在FPA的全局寻优阶段引入BAS；陈婷婷等[4]提出基于BAS的PSO，并将其应用于包含完整费用的投资组合模型中，提高了PSO的有效性和稳定性；赵玉强等[5]提出了一种混沌天牛群算法，提高了BAS收敛性和寻优能力。上述文献对BAS都做出了一定的运用和改进。

为了改善BAS的搜索性能，解决其精度低和易陷入局部最优的缺陷，本文将社会学习策略、拉丁超立方抽样(Latin Hypercube Sampling, LHS)、混沌迁移策略、相似度与BAS深度融合。首先用LHS产生初始群体，其次基于相似度采用混沌迁移策略，最后根据社会学习策略更新种群。该算法改进了传统BAS算法在高维问题上精度低、易陷入局部最优的缺点，并保留了BAS参数少、易于实现的优点，极大地提高了全局搜索的能力，降低了收敛的迭代次数。本文选取了4种测试函数，对社会学习天牛群算法(Social Learning Beetle Swarm Algorithm, SLBSA)、天牛群算法(Beetle Swarm Optimization, BSO)和PSO进行仿真测试和比较。结果表明SLBSA具有更好的效果。

1 BAS基本原理

BAS基本原理为天牛在觅食过程中并不知道食物的精确位置，但可通过判断左右须食物味道的强弱来确定自身的飞行方向。如果右须收集到的味道强于左须，天牛下一步就往左飞，反之，天牛往右飞。BAS模型建立的方法如下：

求解D维优化问题时，天牛由质心、左须及右须3个点代替。

天牛的质心、左须和右须之间的关系为

(1)

式中：X为质心在D维度空间中的位置X=(x1,x2,…,xd)；Xr、Xl为右须和左须在空间中的位置；L为两须到质心的距离。

(2)

式中：ranks()是随机函数，规定将右须作为天牛的朝向。

式(2) 算法的迭代过程中，天牛判断左右须的适应度，将适应度强的一边作为更新的方向。

天牛位置的更新方法为

x(t+1)=

(3)

δ(t+1)=λδ(t)

(4)

式中：t为算法的当前迭代次数，即天牛当前移动次数；f(xr(t))为右须的适应度值，同理左须为f(xl(t))；δ(t)为第t次迭代的步长；sign()为符号函数，为下一次移动时候的方向；λ为步长因子，一般取0.95。若右须的适应度值大于左须，sign()取1，天牛往右须方向以步长δ(t)移动，反之，往左须方向移动。

2 改进的BSO

2.1 LHS原理

文献[6]表明群智能算法的收敛性受初始群体分布的影响较大。LHS[7]可从决策空间中选取较均匀、合适数目、具有全区域信息的样本点,有利于保证初始群体的多样性,故本文采用LHS产生初始种群。具体抽样原理如下：

设某一待求概率问题的K个随机变量X1,X2,…,XK中的任意一个累积概率分布函数为

YK=FK(XK)

(5)

设采样次数为N，将YK的纵轴N等分且各随机变量相互独立，xkn为第k个变量的第n次抽样。选取每个区间的中点作为YK的采样值，然后用YK=FK(XK)的反函数来计算xkn，则有

(6)

抽样步骤如下：

(1) 确定决策空间样本的维数为a，以及要从决策空间中抽取样本点的个数b。

(2) 把已知的样本中每一维划分为b个等概率、不重复的区域，从而得到a·b个等量的小区间。

(3) 在a·b个等概率的小区域中，随机选取b个不重复的全排列小区域即可得到对应的样本矩阵A。

(4) 在步骤(3)中随机选取的全排列小区域内进行随机取样，选取随机的一个样本点，从而保证b维数据中，每一维每一个区域中都能选取一个样本，即获得b个样本点。

2.2 基于相似度的混沌迁移策略

本文提出的更新策略的基本思想是考虑在迭代过程中一直向最优个体靠近，但无法在种群中占据支配地位的天牛，这些天牛在算法满足终止条件时无法达到最优值，不利于天牛群在寻优过程中维持多样性、跳出局部最优。类比生物群体在觅食过程中，最优天牛为最先找到食物的天牛，而非最优的其他天牛，后找到资源，导致资源已经大部分被最优个体取走，所以对多次迭代后靠近最优个体的天牛根据天牛相似度[8]S(i,j)对天牛群进行混沌迁移[9]操作。

相似度S(i,j)定义如下：

S(i,j)=

(7)

式中：d(i,j)为个体j与i的欧氏距离，i为第t代适应度最大的天牛；dmin为与i相距最近个体的欧氏距离；dmax为与i相距最远天牛的欧氏距离。

相似度函数为

(8)

式中：pj(t)为0～1的随机数。

相似度计数为

(9)

混沌序列[10]具有内随机性、遍历性和规律性等特点，看似混乱却有着精致的内在结构。本文提出了基于相似度的动态混沌迁移算法，引入进化过程中，Logistic映射混沌模型程序为

(10)

式中：d为对应的维度；δ为迁移参数，当混沌序列的长度S大于种群数N的20%左右时效果较好，所以δ取0.2；σ为控制参数，取(3.56，4)时系统进入混沌状态。

赋D个0～1的混沌初值，根据迭代式(11)可得混沌序列G={x1,x2,…,xs}，然后对所有相似度值sh取1的天牛进行混沌迁移操作，即

xi=xi(bu-bl)+bl，i=1,2,…,s

(11)

式中：bu、bl分别为上边界和下边界。

2.3 社会学习策略

社会学习策略就是种群中适应度差的个体向多个适应度优于自己的个体学习。由于BAS个体搜索范围有限，并且在处理高维、复杂问题时难以搜寻到最优解，而社会学习粒子群算法[11-13](Social Learning Particle Swarm Optimization, SLPSO)，在有限计算次数上拥有更好的性能，尤其是在解决高维、复杂问题上拥有更显著的优势。本文在天牛须算法基础上提出了SLBSA，种群中个体j的t到t+1代迭代过程为

xjd(t+1)=

(12)

社会学习策略中天牛的速度更新规则为

(13)

式中：k(Pk>Pj)为个体j在大于它适应度的个体中随机选择的学习对象，并且个体j在每个维度上选择的学习对象k并不是固定的，都是随机的。天牛i可以向当前优于它的多个个体学习，使其能够获得更多的信息。xkd(t)为个体k在第t代的d维上的位置(1≤d≤D)；D为决策空间维数；xm(t)为天牛群位置在d维上的均值；ε为影响因子用来控制xm(t)的社会影响力，本文取0.01；r1～r3为个体j在[0,1]之间的随机数。

概率函数为

(14)

式中：N为种群数；i为个体j在适应度排序后在种群中的排位。

社会学习策略步骤如下，流程见图1。

(1) 对t代种群P(t)进行适应度评价，计算其大小。

(2) 由坏到好，按适应度值对种群排序。

(3) 由适应度值最坏的天牛开始，其每一个维度都独立且随机地向优于自身的天牛学习，通过社会学习得到第t+1代种群P(t+1)。

图1 社会学习策略流程图

2.4 算法步骤

SLBSA的流程如下，具体流程见图2。

图2 SLBSA算法流程图

(1) 初始化算法参数，设置天牛群规模为N，质心与触须的距离为L，学习因子为ε，迭代步长为δ(0)，控制参数为σ，迁移参数为δ，步长因子为λ，最大迭代次数为imax。

(2) 采用LHS产生规模为N的初始群体P(0)，并计算初始种群的适应度值。

(3) 计算最优天牛i与其他天牛的相似度，根据式(7)～(9)计算相似度计数。

(4) 根据式(10)判断是否需要进行混沌迁移操作，如果需要转步骤(5)，反之转步骤(6)。

(5) 对相似度函数取1的天牛通过式(10)进行混沌迁移操作，计算迁移后的天牛的适应度值。

(6) 计算当前天牛群在d维上的均值xm，然后根据天牛的适应度值进行排序，通过式(12)、(13)从最坏的天牛开始随机向由于自身的个体学习，并更新速度与位置。

(7) 对超出范围的天牛进行越界处理，计算更新后的天牛群的适应度值。

(8) 检验是否满足迭代终止条件，若是，输出全局最优解及对应的位置，否则跳转步骤(3)。

3 数值实验

3.1 测试函数及参数设定

为了评估SLBSA的性能，引入了4个标准测试函数对SLBSA和BAS进行测试和对比。采用2种单模态函数f1～f2对SLBSA的收敛性进行检验；2种多模态函数f3～f4对算法的群体多样性、全局搜索能力和逃离局部最优能力进行考察。天牛群的初始种群大小为300，所有函数维度为20，迭代次数为100次，所有函数的运行次数为50次，优化目标取10-3。基本测试函数的相关参数见表1。

表1 测试函数

3.2 测试结果分析

测试结果对比包括寻优成功率(Rate)、最佳适应度值(Best)、最差适应度值(Worst)、平均适应度值(Mean)，如表2所示。

表2 测试结果对比

对于测试函数f1～f4，SLBSA收敛精度都高于 PSO和BSO，说明改进策略能够提高收敛的精度和局部搜索能力，对于Shpere、Rosenbrock和Griewank函数，SLBSA达到目标适应度值1.0×10-3的成功率分别为100%、84%和86%，都明显高于PSO和BSO，且找到最优值的概率较大。对于相对复杂的单模态测试函数Rosenbrock，由于种群间的信息量不够，BSO和PSO的寻优成功率只有0%和12%，但是SLBSA加入了混沌迁移策略和社会学习策略增加了种群间的信息交流，寻优成功率为84%，明显高于BSO和PSO，所以SLBSA的寻优稳定性更好，并且寻优精度更高，每次寻优的结果相差较小。但是对于Rastigrin测试函数而言，3个算法的寻优成功率都很低，算法在Rastigrin类的测试函数上的收敛精度不佳，因为Rastigrin测试函数是一个典型的非线性多峰函数，它具有大规模的搜索区间和局部最小值，当导致优化算法寻找到满足设定的寻优精度的全局最小值较难。但SLBSA在收敛精度和平均值上相比PSO和BSO都有提高，说明SLBSA相对而言性能更好。以上4种函数的测试结果如图3～6所示。

由图3和图4的单模态函数测试结果可见，SLBSA收敛速度和收敛精度优于PSO和BSO。由于SLBSA在产生初始种群时采用了HLS，所以SLBSA具有多样性更好的初始种群，在迭代的初期收敛速度都优于PSO和BSO。SLBSA在种群更新过程中利用基于相似度的混沌迁移策略，当相似度计数达到能产生较好混沌序列时，对相似度计数为1 的个体进行混沌迁移操作，即保证天牛群在迭代过程中既能保证产生较好的混沌个体维持种群的多样性，也避免了每次迭代都进行混沌迁移操作，降低了一定的计算量。社会学习策略保证了天牛群在更新时充分的信息交换，随机向优于自己的多个个体学习，使天牛群能搜索更广阔的空间，避免陷入局部最优，随着迭代的进行，天牛的步长逐渐减小，天牛群能进行更精细地搜索，收敛精度更高，算法的寻优性更好。

图3 Shpere函数测试结果

图4 Rosenbrock函数测试结果

图5 Griewank函数测试结果

图6 Rastigrin函数测试结果

由图5和图6的多模态函数测试结果可见，SLBSA在前期和后期的收敛速度以及最后的收敛精度都优于PSO和BSO，但在Rastigrin函数上，SLBSA的收敛速度要劣于PSO，由于多模态的Rastigrin函数相对复杂，采用LHS产生初始种群使天牛群相对分散，所以在中期收敛速度可能会略微弱于随机产生初始种群的PSO和BSO，但在迭代后期体现了混沌迁移和社会学习策略在收敛精度和速度上的优势，PSO和BSO分别在50代和40代左右才开始收敛，而SLBSA在30代左右就开始收敛。总之，SLBSA的收敛速度和跳出局部最优的能力都优于PSO和BSO。

4 结 论

针对天牛须算法寻优时收敛速度慢，容易陷入局部最优的问题，提出了SLBSA来提高算法的有效性，采用LHS保证初始种群的多样性。在天牛群位置更新过程中加入基于相似度的混沌迁移策略，在加入扰动的同时还保留了最优个体，防止了种群的早熟也保证了收敛速度；社会学习策略增加了个体间的信息交流，保证了在寻优过程中对更广的空间进行探索，在算法后期有更大的概率跳出局部最优。实验结果证明了SLBSA的各方面能力都优于PSO和BSO。在以后的工作中，将会考虑到初始种群数为N的SLBSA在每次迭代过程中评价函数的使用次数至少为3N的问题，采用代理模型[14-15]的方法减少评价函数的使用次数，使算法能够运用到评价昂贵的实际工程问题中。