求解最优化问题的改进蜘蛛猴算法

姜 爽

(承德石油高等专科学校 数理部，河北 承德 067000)

蜘蛛猴算法(SMO)是2014年由Jagdish Chand Bansal等[1]学者提出的，是一种建立在对蜘蛛猴群觅食行为建模基础上产生的新型解决优化问题的数值优化方法.根据原始SMO算法多种改进算法[2-4]被研发用来解决优化问题.本文设计了S-SMO算法并挑选了优化问题的测试函数进行了实验，表明改进算法的多重评价性能均优于原算法和WSMO算法。

1 基本蜘蛛猴算法

首先程序会产生一个规模为N的蜘蛛猴群.SMOi代表群体中第i个猴子,同时也为D维被优化函数潜在的解。按：SMOij=SMOminj+rand(0,1)×(SMOmaxj-SMOminj)确定其自身位置.我们称第2阶段为本地领导人阶段，在本进程中新位置的产生依靠的是本地领导人和群体成员的反馈所决定即SMOnewij=SMOij+rand(0,1)×(LLkj-SMOij)+rand(-1,1)×(SMOrj-SMOij)，LLk是第k组本地领导人位置向量.当实现了本地领导人阶段，随即开始进行全局领导人进程：SMOnewij=SMOij+rand(0,1)×(GLj-SMOij)+rand(-1,1)×(SMOrj-SMOij)，GLj代表全局领导人位置向量，此时位置的改变依靠的是全局领导人和小组成员的反馈。

接下来展开全局领导人学习进程，判断全局领导人的位置是否得到了改变，如未得到改变则GlobalLimitCount增加1。随后算法开展本地领导人学习阶段，同样地，判断本地领导人位置是否更新，否则LocalLimitCount增加1。在以上两阶段本地领导人位置和全局领导人位置由距离“食物源”最近的个体位置确定。第6阶段为本地领导人决策阶段，若本地领导人位置更新次数未达到已知的LocalLeaderLimit的值，那么该小组的所有成员启动新的公式：SMOnewij=SMOij+rand(0,1)×(GLj-SMOij)+rand(0,1)×(SMOij-LLkj)来改变位置。

最后算法会经历全局领导人决策阶段，此时若全局领导人的位置更新次数未达到已知的GlobalLeaderLimit的值，则猴群会将群体分成更多的组来觅食，重复这样的操作到最大组数后，算法将所有小组合并成为一个组.这样7个阶段的操作被重复后算法会得到其寻优能力范围内的最优解。

2 惯性权重正弦调整的蜘蛛猴算法

增强探索和开发最优解的能力是提高群体智能算法寻优、求解能力的两个重要指标，蜘蛛猴算法作为一种新型算法创造性地平衡了其两种寻优方式.本文在其原始程序运行的基础上在本地领导人阶段及其决策阶段调节蜘蛛猴个体位置变化的频率和周期性即增加了正弦调整[6]的惯性权重，ω=ωmin*(1-sin(t))+rand*ωmax*sin(t)，t=π*iter/maxCycle。该权重调节中，在迭代早期惯性权重ω的值很小，使得每个蜘蛛猴个体在其周围进行局部寻优，可以规避在初期陷入局部最优解从而发展为停滞状态。随着算法的推进，迭代次数在不断地上升则ω的值不断增大，导致猴群个体之间协作程度增大，猴群更侧重全局寻优。后期猴群对最优解进行局部的开发和搜索。这样的设计即对蜘蛛猴群搜索的初期及末期都进行了正弦调整。公式中h的变动规律增加了ω变化的周期性且rand函数的引入为ω的变化增添了随机性.

2.1 本地领导人进程中的权重改进

原算法中本进程中新位置的产生依靠的是本地领导人和群体成员的反馈.根据惯性权重公式的特点，在算法刚开始时，ω的值接近于本文设定的惯性权重的最小值，猴群在其自身附近进行局部寻优从而更能最大化地利用小组成员信息.随着权重增大对解空间进行全局搜索，迭代后期进行局部开发和寻优，调整方式见(1)和(2):

ω=ωmin*(1-sin(t))+rand*ωmax*sin(t)

(1)

SMOnewij=ω×SMOij+rand(0,1)×(LLkj-SMOij)+rand(-1,1)×(SMOrj-SMOij)

(2)

该式中，t=π*iter/maxcycle。其中ωmax代表惯性权重的最大值，ωmin为最小值，iter表示当前迭代次数，maxcycle是运行次数最大值.

2.2 本地领导人决策进程中的权重改进

当扰动率较大时算法会利用全局领导人和本地领导人的综合反馈对每个个体的位置进行确定，此时我们为该阶段个体位置增加同样的惯性权重：

SMOnewij=ω×SMOij+rand(0,1)×(GLj-SMOij)+rand(0,1)×(SMOij-LLkj)

(3)

3 数值实验

3.1 实验设置

猴群群体规模N设定为50，最大迭代次数M为2 000次,猴群可以被划分的最大组数：DP=N/10。ωmax=0.8,ωmin=0.4,GlobalLeaderLimit=N,LocalLeaderLimit=N×D。扰动率：Hiter+1=Hiter+0.4/maxCycle,H1=0.1。

3.2 改进算法有效性测试

为了检测S-SMO算法对最优化问题求解的效果，分别将SMO算法和S-SMO算法用于求解表1中的待优化函数其理论最优解均为“0”。先后对处于低维和高维的函数求解30次，实验数据见表2和表3。

当被优化问题处于低维度时，我们可以观察到此两种算法都能取得比较好的效果，其中f1-f3为单峰待优化函数，S-SMO算法对其优化的能力高于SMO算法，寻优均值的精度均提升了1个数量单位，标准差降低了1个单位。原算法对f4函数平均值的精度与S-SMO算法相比低了8个数量单位，对f6函数优化性能更不理想。S-SMO算法对表中f4-f6多峰函数的求解都能达到最优解“0”，且稳定性指标即标准差为“0”。而对f5函数的求解虽未达到理论最小值“0”，但是平均值精度较SMO算法提升了12个数量单位，标准差为“0”，表现了优异的稳定性。

当被优化问题处于高维度时，SMO算法对函数的优化能力下降，但是S-SMO算法仍然保持着优异的求解性能和稳定性。求解f1-f3单峰函数时，在最优值、最差值

表1 本文选择的测试函数

表2 两种算法有效性对比(D=30)

表3 两种算法有效性对比(D=100)

和均值3个指标上其精度均提高了1个数量单位，在稳定性角度标准差降低了1个单位.对于处于高维度的f4-f6函数，S-SMO算法的30次求解仍能得到最优值，且求解性能稳定.S-SMO算法对f5函数的优化虽然没有达到理论最优解“0”，但得出的平均值精度提高了 15 个单位，且标准差为“0”具有很好的稳定性。

3.3 算法效率测试

为了更加形象地展示SMO、S-SMO和WSMO算法对各个函数不同的求解效果，比较算法在收敛速率、最少迭代数量等效率上的差异.当函数处于30维时，利用软件仿真出3个算法在各个函数上的收敛图像。

如图1～图6所示，S-SMO算法最有能力寻找到最优解，在6个问题上的求解均优于其他两种算法，且达到目标精度的迭代次数大大少于SMO算法和WSMO算法，搜索速度最快.通过观察图像可以发现WSMO算法改善了原始SMO算法极易陷入局部最优的情况，但是仍存在被短暂地困在局部最优附近的情形，例如WSMO算法在f1函数的200-400代，f2函数的200代周围，f4函数的500～600代均暂时性地停留在局部最优解，S-SMO算法对停留于局部最优情况的改善更加明显,与此同时可以迅速地捕捉到最优解。S-SMO算法仅需要少量的迭代就可以符合规定精度的要求.在时耗角度由于迭代的减少从而会压缩处理问题的运行时间，收敛速度即效率得到了提高。

5 结束语

蜘蛛猴算法作为一种新开发的群体智能算法在处理优化问题时表现着非常优异的性能，本文设计的S-SMO算法在探索原始SMO算法的原理上对其运行机制方面做出了改进，并在选取的标准函数上进行检测结果显示有效性，效率都高于原算法。