一种自适应寻优的社会蜘蛛优化算法（SA-SSA）

施怡乐，乔之勇,2，白克强，陈 果，刘知贵*

（1.西南科技大学 信息工程学院，绵阳 621000；2.绵阳职业技术学院，绵阳 621000）

0 引言

社会蜘蛛智能优化算法（SSA）于2015年香港大学James等人提出[1]。作为一种新型全局智能优化算法，其思想源于蜘蛛发现食物以后，振动蛛网向同伴发出信息并吸引其他蜘蛛前来觅食的自然现象。社会蜘蛛智能优化算法（SSA）中，蛛网表示待求解问题的解空间，每个蜘蛛表示解空间中的一个可行性解，食物表示解空间中解的适应度。当某一个蜘蛛发现食物以后，将产生与该食物适应度所匹配的振动，并吸引其他蜘蛛前来觅食。该算法具有结构简单、自身参数少的优点，在多元函数问题求解时比传统遗传算法和粒子群算法速度更快、精度更高[2]。目前社会蜘蛛智能优化算法（SSA）被广泛应用于电力调度优化[3]、网络服务器分布[4]、神经网络训练[4]、防洪调度[6]、水纹频率参数优化[7]中。作为一种新型全局智能优化算法，社会蜘蛛智能优化算法（SSA）已成为多个领域中的研究热点[8]。

为进一步提高社会蜘蛛智能优化算法（SSA）寻优能力，有学者提出引入随机交叉策略用于个体蜘蛛的更新，通过快速的个体更新策略提高SSA的搜索速率[9]；采用自适应寻优和偏好随机游动机制，以迭代次数为变量来提高SSA在多峰测试函数中的全局搜索能力和寻优精度[10]；引入分层协作思想将蜘蛛群体划分为两个分工种类，并结合贪婪策略定性移除部分蜘蛛，提高处理高维优化问题的全局搜索能力和寻优精度[11]；在分层协作思想基础上引入差分进化算子，通过优化群体中不同种类蜘蛛的进化方式来提高SSA的全局搜索能力和寻优精度[12]。目前已有一些关于SSA改进算法被提出，但大多改进都没有考虑到振动强度对算法全局搜索能力的影响。

针对上述问题，本文提出了一种自适应策略的社会蜘蛛智能优化算法（self adaption social spider optimization algorithm，SA-SSA）。该算法在蜘蛛振动过程中利用自适应权重，动态调整算法不同迭代时段的收敛速度，并通过最优领域扰动策略来抑制算法早熟。为验证SA-SSA的寻优性能，在6个测试函数中进行了仿真实验，结果表明该算法具有更高的寻优精度和更快的寻优速度。

1 社会蜘蛛优化算法（SSA）

在社会蜘蛛智能优化算法（SSA）中，将优化问题的搜索空间拟化为蛛网，蛛网的每一个位置均代表了优化空间中的一个可行性解，且蛛网还作为信息交流的媒介用于传播振动。在SSA初始化阶段随机生成每一个蜘蛛的位置，并对应产生相应的适应度，依据该适应度产生对应的振动并传播。单个蜘蛛判断自身振动与接收其他蜘蛛振动的大小，产生游走概率，进行随机游走。社会蜘蛛智能优化算法（SSA）主要包括：蜘蛛信息、振动产生以及游走寻优三个环节。

1.1 蜘蛛信息

社会蜘蛛智能优化算法（SSA）中，每个蜘蛛在蛛网上的位置均代表了优化问题中的一个可行性解，其中每一个蜘蛛均携带着如下信息：

图1 社会蜘蛛示意图

1）蜘蛛S所在的位置计为Ps；

2）蜘蛛S所在位置的适应度计为f(Ps)；

4）自上一次改变目标振动后的迭代次数Cs；

5）上次迭代的移动方向w；

6）上次迭代中用于游走的掩码m。其中前两个信息为蜘蛛自身的个体信息，其他的则是引导蜘蛛前往适应度更高位置的信息。

1.2 振动产生

振动产生是SSA的核心环节，也是与其他算法区别开的一个主要特性。在SSA中从蜘蛛个体振动强度和感知群体中其他蜘蛛振动强度两个方面来定义了振动的概念。当蜘蛛S到达某个位置Ps以后将对对应产生在该位置的振动，其强度表示为I(Ps,Ps,t)；除此以外该振动强度也会在振动衰减的基础上被群体中其他蜘蛛感知，同样也能感受到来自其他蜘蛛的振动，其强度表示为I(Ps,Ps,t)（其中i的范围[1，pop-1]，pop表示种群数量）。基于这种种群信息共享的方式，SSA的全局寻优能力得到了增强。

其中，蜘蛛S自身振动强度I(Ps,Ps,t)是指蜘蛛S在t时刻所产生的振动强度，具体的计算表示如下。

式(1)中，f(Ps)为蜘蛛S所在位置的适应度，C为极小常数用于保证f(Ps)+C＞0。

蜘蛛S感知种群其他蜘蛛的震动强度I(Ps,Ps,t)的具体计算表示如下，在计算I(Ps,Ps,t)之前首先需要分别计算蜘蛛S与其他蜘蛛的距离。这里我们选择采用曼哈顿距离计算方法，定义蜘蛛S与蜘蛛A的距离为D(Ps,PA)。

此时，可表示蜘蛛S感知蜘蛛A产生振动强度为I(Ps,PA,t)。

式(3)中，为蜘蛛种群每个维度的标准差，Ra为振动衰减率。

1.3 游走寻优

社会蜘蛛智能优化算法（SSA）游走寻优方式，不存在全局最优标准来指导种群进化的行为，而是蜘蛛个体依靠自身携带信息和种群共享信息，随迭代采用逐步逼近的方式向全局最优解靠近。

游走寻优的本质是基于概率的一种游走形式，在SSA中规定了每一个蜘蛛均携带一个固定分配的二进制编码表M（该表为pop×dim的矩阵，pop表示种群数量，dim表示待优化问题的维度），在算法初始阶段矩阵中各个元素均为零，在每轮迭代的过程中蜘蛛S具有的概率改变矩阵（其中Cs表示自上一次改变目标振动后的迭代次数）。当M矩阵被判定为改变以后，M中的每个元素均有Pm的概率被改变为1。在随机编码M确定以后，根据M生成蜘蛛S新的目标位置，该目标位置的第i维数值记为具体表示如式(4)所示。

其中a的取值范围为[1，pop]。

式(5)中r和R均为服从[0，1]分布的随机数，o为矩阵中点对点乘运算。

在随机游走环节中为防止蜘蛛超出解空间，得到不可行解，需要对SSA进行约束处理，在SSA中采用reflecting算法进行边界约束，具体表达如下。

式(6)中为搜索空间第i维的上界，为搜索空间第i维的下界。

2 改进型社会蜘蛛优化算法

通过分析发现，传统的社会蜘蛛优化算法（SSA）在全局寻优精度和全局收敛速度方面仍存在一定缺陷。目前SSA的算法改进几乎没有考虑到振动强度对算法寻优的影响，以及算法在全局搜索能力的不足。因此根据标准的蜘蛛种群位置（适应度）更新，引入振动自适应调整函数和最优邻域扰动构成自适应寻优社会蜘蛛优化算法（SA-SSA）。

2.1 振动自适应函数

传统的SSA在振动强度和传递距离确定的情况下，振动传递的衰减由蜘蛛种群每个维度的标准差σ和振动衰减率Ra影响。又因蜘蛛种群每个维度的标准差σ主要由初始化随机决定，因此振动衰减率Ra为主要SSA的主要控制参数。然而通过实验发现，在SSA中以10000倍的跨度调节振动衰减率Ra对传统社会蜘蛛优化算法（SSA）的全局优化能力并无太大改善。通过分析发现，该现象出现的主要原因是由于标准差σ值过于极端且随机性强，变相使得振动衰减率Ra的控制效力不足，造成振动环节随机性较强，SSA的全局优化能力提升受限。

基于上述实验验证和分析，为提升社会蜘蛛优化算法（SSA）的全局优化能力，本文在粒子群优化算法的权重因子思想上，结合迭代规律，引入振动自适应函数。

式(7)中Ra为算法初始化设定的振动衰减率，iter为当前迭代次数，max_iter为初始化设定的最大迭代次数。该函数使得算法在迭代前期增加群体对个体的影响能力，进而增加全局搜索的能力；在迭代后期该影响逐渐减小，以获得更高的寻优精度。综上所述，改进的W-SSA振动传递式如式(8)所示。

2.2 最优邻域扰动

个体蜘蛛经过迭代进行位置更新时，一般以当前迭代的最强振动为方向进行有目的的随机游走。但目标函数以及群体蜘蛛的位置均为未知，且个体振动与个体接收振动的量化均存人为经验的判断，因此在算法寻优时不可避免的会出现算法早熟，陷入局部最优的问题。为规避该问题，本文提出在SSA中引入最优领域扰动，在当前最优位置产生随机扰动，增加个体蜘蛛对附近空间的搜索能力，最优领域扰动如下。

式(9)中rand1、rand2为[0，1]之间的均匀产生的随机数；为上一次迭代所处最佳位置的蜘蛛S，经过最优领域扰动以后新位置。对于蜘蛛S新生成的领域位置采用贪婪机制判断是否保留。

2.3 SA-SSA算法流程

SA-SSA综合考虑了算法的收敛速度、全局和局部搜索能力。引入振动自适应函数用于提升算法收敛速度和全局搜索能力，引入最优领域扰动并结合贪婪机制增加最优个体的局部搜索能力，具体算法流程如表1所示。

表1 SA-SSA算法流程表

2.4 算法复杂度分析

对于算法复杂度的分析，主要从时间复杂度和空间复杂度两个方面展开。

在社会蜘蛛优化算法（SSA）中，设算法中鲸鱼的规模为N，最大迭代次数为I，问题维度为D，于是可以得到社会蜘蛛优化算法（SSA）的时间复杂度为O（N×I×D）。而SA-SSA是在原SSA基础上引入了两种改进策略，从算法流程可以看出，在加入振动自适应函数以后并未增加算法的循环次数，而加入最优邻域扰动也仅仅是只给算法外围增加了一次遍历种群的循环，增加了O（N×I）的运算量。对于整个算法的时间复杂度而言，增加O（N×I）的运算量并不会对整个算法造成太大的计算负担，总体来说SA-SSA相较SSA在时间复杂度方面几乎持平。

空间复杂度则是用来评判一个算法对内存空间的需求。本文所述的空间复杂度主要由蜘蛛种群的规模决定，而SA-SSA和SSA均采用相同的种群规模，因此两种算法具有相同的空间复杂度O（N×D）。

3 仿真与分析

3.1 测试函数及性能指标

为测试SA-SSA算法的寻优能力，选择了6个标准测试函数，其函数特性如表所示。算法寻优精度为实际寻得最优解与理论最优解之间的误差绝对值，本文采用两个评价指标：寻优精度的平均值（Ave）和标准差（Std），其计算式分别如式(11)、式(12)所示。

3.2 优化算法性能分析

将W-SSA算法在6个标准测试函数上进行性能测试，并将其与蝙蝠优化算法（BA）、人工鱼群算法（AFA）以及传统社会蜘蛛算法（SSA）进行对比。算法参数设置相同：种群规模为30、最大迭代次数500。算法均分为10和30两组优化问题维度分别测试20次，得到优化结果的平均精度及其标准差如表3、表4所示，其中黑色粗体为较优结果。

算法主要参数设置如表3所示，算法收敛精度对比如表4所示。

表3 算法参数设置表

表4 算法收敛精度对比表

由表2可以看出改进以后的SA-SSA在f1～f6的6个测试函数中其寻优精度均优于传其他三种全局优化算法。特别是在f1、f2、f3以及f6四个测试函数中，SA-SSA的寻优精度具有极佳的表现。

表2 标准测试函数表

为进一步验证SA-SSA算法在寻优速度方面的表现，对收敛精度较好的SSA和SA-SSA在上述6个标准测试函数下的求解收敛曲线进行了对比，如图2所示。

图2 算法收敛速度对比图

从图中可以看出，SA-SSA算法在上述6个标准测试函数的收敛速度均明显高于标准SSA。综上所述，改进后的SA-SSA算法在求解复杂函数最优解时，比标准的SSA以及其他群智能优化算法具有更高的寻优精度，在收敛速度方面也相较于标准SSA更快。

4 结语

社会蜘蛛优化算法（SSA）是一种具有仿生寻优的智能优化算法，已被广泛的应用于多个领域中，但该算法在全局寻优精度和收敛速度方面仍存在一定的缺陷。本文分析了标准SSA算法的寻优过程。根据标准的蜘蛛种群位置（适应度）更新，引入振动自适应调整函数和最优邻域扰动构成自适应寻优社会蜘蛛优化算法（SA-SSA），提升整个算法的全局搜索能力。通过标准测试函数测试，SASSA算法相较于BA、AFA以及SSA在寻优精度和收敛速度两方面均更优。证明了本文所提出的两种改进策略对于SSA算法的有效性。