基于禁忌搜索的自适应人工鱼群优化算法

陈静静，刘 升

(上海工程技术大学，上海 201620)

0 引 言

人工鱼群算法(artificial fish swarm algorithm，AFSA)[1]是一种智能的仿生优化算法，基于鱼群及其觅食习惯而衍生出来的算法，该算法具有对初值不敏感、鲁棒性高、全局搜索能力强且易与其他方法结合等优点，目前在传感器网络优化[2]、水质参数识别[3]、参数优化[4]以及组合优化[5]等多个工程领域取得了良好效果。 但AFSA算法也存在前期收敛速度快、 后期盲目性强且易陷入局部极值、解精度低等问题。针对上述人工鱼群算法的缺点，目前许多学者提出了改进策略，主要包括三类：自适应策略、变异策略和混合算法策略[6]。自适应策略主要是对参数的调整，例如文献[7-9]自适应调整人工鱼的参数，保证算法前期有较强的全局探索能力，迭代后期有较好的局部寻优能力，但当鱼群寻优停滞不前，很难摆脱局部困境。为了增加鱼群的多样性，降低人工鱼陷入早熟的可能性，文献[10]提出了一种最优解引导的高斯变异机制。人工鱼群算法除了可以从自身方面进行改进外，还可以借助其他算法的优点来弥补自身的不足，文献[11]利用模拟退火较强的局部寻优能力来改善人工鱼群迭代后期盲目搜索、寻优精度低等问题。文献[12]将人工鱼群算法与和声搜索算法进行融合，提出了一种新的混合算法，相比单一算法，混合算法明显提高了寻优精度、降低了算法复杂度，全局搜索能力也有所增强。文献[13-14]提出了人工鱼群算法与粒子群算法结合的混合优化算法，该混合算法综合利用人工鱼群算法较好的全局搜索能力和粒子群算法的局部快速收敛性、易实现性等优点，弥补人工鱼群算法和粒子群算法在后期寻优过程中存在的不足。虽然这些改进算法都不同程度地增强了AFSA的寻优性能，但是随着待优化问题复杂程度和规模的不断扩大，对AFSA及其改进算法寻优能力的要求越来越高。

为了能在一定程度上提升AFSA求解复杂优化问题的能力，该文试图提出一种基于禁忌搜索的自适应人工鱼优化算法(Taboo search based adaptive artificial fish swarm optimization algorithm，TSAFSA)。该算法首先对鱼群行为的视野和步长进行了改进。在迭代寻优过程中，视野和步长按照各自设定的衰减函数进行递减，既提高了算法的全局搜索能力，也降低了算法后期陷入局部极值的概率；为了改善随机行为具有盲目性这一状况，该文引入了更符合鱼群自由游动的levy飞行机制；当AFSA寻优停滞不前时，就以当前最优个体为初始值，建立禁忌区域，产生领域解，帮助鱼群跳出“困境”。最后通过经典测试函数进行验证，实验结果表明TSAFSA算法具有较好的寻优性能。

1 基本AFSA算法

1.1 相关定义

人工鱼群算法是基于动物行为的一种新型仿生优化算法，鱼群密度较大的地方，大多是食物较为充足的水域，以这一点为依据来模拟鱼群觅食、聚群、追尾等行为，以期实现寻优的目的。假设第i条人工鱼可表示为Xi={x1,x2,…,xn}，适应度函数Y=f(x)(食物浓度)，视野范围用Visual表示，Step表示移动步长，δ表示拥挤度因子，最大尝试次数为try-number，鱼群规模为np，人工鱼之间的距离用dij=‖Xj-Xi‖表示，Rand函数为(0,1)范围内的随机数。

1.2 描述行为

1.2.1 觅食行为

设某条人工鱼目前状态为Xi，随机的在其视野范围内选择一条鱼Xj，如式(1)所示。针对求最大值的问题，若Yj≥Yi，则向Xj的方向前进一步，用式(2)所示；否则，继续寻找，如果尝试次数m等于try-number次后，仍未找到较优状态，则随机移动一步。可以用式(3)表示。

Xj=Xi+visual×Rand

(1)

(2)

nextX=Xi+step×Rand

(3)

1.2.2 聚群行为

(4)

1.2.3 追尾行为

(5)

2 基于禁忌搜索的自适应人工鱼群优化算法(TSAFSA)

2.1 自适应视野和步长

在基本AFSA中，视野visual和步长step都是提前设定好的固定值。这是两个非常重要的参数，直接影响了寻优结果的精度。视野较大时，有利于鱼群进行全局的探索，加快寻优速度；较小的视野范围，有利于人工鱼进行局部搜索提高解精度；但是视野过小，不仅影响收敛速度还可能导致算法陷入局部极值。综合考虑上述条件，该文利用分段函数对视野进行了改进，保证了鱼群在不同阶段具有合适的视域，如式(6)所示。

(6)

为了进一步协调算法寻优速度与解精度的之间的平衡，对鱼群的各个行为的步长也进行了改进，如式(7)所示：

(7)

若满足觅食行为条件，nextX表示下一较优状态Xj，如果是执行聚群行为，nextX则代表鱼群中心Xc，若条件适合追尾行为，那么nextX即为人工鱼当前视野范围内的最优值Xbest， ‖nextX-Xi‖表示当前鱼Xi与下一状态鱼间的距离，Rand函数是为了防止算法收敛过快，降低其陷入局部极值的风险。在迭代寻优过程，逐渐减少的步长有助于提高算法的寻优的稳定性及寻优精度，但寻优速度可能会受到负面影响。为了提高算法的综合性能，该文对步长的改进不仅加入了衰减因子还在此基础上考虑了鱼间距离，若当前鱼Xi距离下一状态较远，则赋给Xi较大的步长，否则移动较小的步长。这种对步长的改进，不仅有利于人工鱼群跳出局部极值，在对求解精度、寻优稳定性及迭代周期方面也有一定的积极作用。

2.2 对觅食行为的改进

在觅食过程中倘若尝试了try-number次后仍没有合适的新解，则执行具有levy飞行机制的自由游动。在解空间的范围内，若人工鱼经自由游动后依旧没有探寻到合适的下一状态鱼，就随机移动一步，如式(8)所示。将levy飞行机制加入到自由游动算子中，既符合生物觅食的本能行为，也加强了算法的全局搜索能力。

nextX=

(8)

2.3 禁忌搜索算法的融合

禁忌算法又称禁忌搜索算法(Tabu search，TS)，是一种启发式算法，最早由美国工程院士Ferd W.Glover在1986年提出[15]。禁忌搜索算法是一种模拟人的思维的智能算法，即人们在寻找东西时，对搜索过的地方短时不会进行第二次寻找，而是去其他未搜索过地方寻找，若仍然没有结果，可能会再搜索已去过的地方。为了避免陷入局部极值，禁忌搜索加入了一种灵活的“记忆”技术，即记录已执行过的优化过程，并对下一步的搜索方向做出指导，建立禁忌表。表中保存了最近若干次迭代过程中所实现的移动，凡是处于表中的移动，在当前迭代过程中是禁忌进行的，这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解，从而防止了循环，帮助算法摆脱局部最优解，当禁忌对象满足一定禁忌长度之后，将被释放出来重新寻优，为了尽可能不错过产生最优解的“移动”，还采用“特赦准则”的策略[16]。

因AFSA在求解高维且具有多个局部极值点的问题时，容易陷入局部最优。为此，该文将禁忌搜索算法融入到了AFSA中，提出了一种基于禁忌搜索的AFSA算法(Tabu search based artificial fish swarm algorithm，TSAFSA)，当AFSA寻优过程停滞时，以当前最优值作为禁忌搜索的初值，建立禁忌区域，并在禁忌区域内生成一个小规模子群继续寻优，实现跳出局部极值的目的。算法基本思路如下：

首先，设立一个公告板，计算所有人工鱼的食物浓度，将最大的食物浓度值Ymax及其对应的BestX更新至公告板上。将每次AFSA迭代寻优寻得的Ymax与公告板中的数值进行比较，若大于公告板中的数值，则更新公告板，否则公告板中数值保持不变。记录每次迭代寻得的Ymax于BestY中，若BestY中数据连续0.05*maxgen次没有发生变化或者变化非常小时，表明算法陷入了停滞，此时鱼群很难跳出局部极值，这就需要建立禁忌区域来改善这一状况。把当前公告板中数据对应的BestX作为禁忌搜索的初值X0，并记为目前最优解Xbest和当前解Xnow，将其对应的函数值赋给当前解的函数值Ynow和best so far，设立禁忌区域，在禁忌区域内按照levy机制生成邻域解，第i个邻域解的第j维数据可表示为Xnear(i,j)=Xi+levyrand(beta)*w*(ub(j)-lb(j))，其中w是权重，初值为1，按照w=w*0.998进行自适应更新，ub和lb代表X的边界限定值。计算领域解的适应度，将其中最优的作为候选解Xcandidate，对应的函数值为Ycandidate，计算Ycandidate与Ynow的差值β1以及Ycandidate与best so far的差值β2。若候选解没有改进(即β1<0)，就把候选解赋给下一次迭代的当前解，更新禁忌表；若β1>0且β2>0时，就把候选解赋给下一次迭代的当前解Xnow和目前最优解Xbest，并将相应对象加入禁忌表，更改禁忌表中各对象的任期；若β1>0但β2<0，判断Xcandidate是否在禁忌表中：若不在，则把候选解赋给下一次迭代的当前解Xnow，并更新禁忌表；若在，则用当前Xnow重新产生新的邻域解。

2.4 算法描述

TSAFSA具体步骤如下：

(a)初始化TSAFSA鱼群及各参数。

(b)AFSA执行觅食、追尾、聚群、随机行为，视野更新如式(6)，步长更新如式(7)，觅食行为更新如式(8)，进入自适应迭代寻优。

(c)判断BestY中的数据是否满足2.3所示条件，若满足，就将此时公告板中的bestX作为禁忌搜索的初值，建立禁忌区域和禁忌表，进入禁忌搜索程序。若不满足，直接跳到(d)。

(d)输出TSAFSA寻得的最优解及其对应目标函数值。

图1 TSAFSA算法流程

3 实验仿真与实验结果

3.1 仿真实验环境

该仿真测试环境：操作系统为Windows10，CPU为Intel(R)Core(TM)i7-8565U，主频1.99 GHz,内存为8 GB，仿真软件为Matlab2018b。

3.2 实验参数初始化设置

该文对基本人工鱼群(AFSA)、基于禁忌搜索的自适应人工鱼(TSAFSA)和基于量子遗传算法(GQA)三种算法的函数寻优结果进行了对比。统一设置所有算法的共有参数，visualmin=0.1，stepmin=0.02，maxgen=200，try-number=50，δ=0.618,禁忌搜索中的候选集个数为Ca=6，禁忌长度L为5到11之间的随机整数。

3.3 测试函数

为了验证TSAFSA的性能，该文选择以下3个典型的测试函数进行了对比实验分析。

F2：f(x,y)=xsin(4πx)+ysin(20πy)，该非线性函数在给定范围内分布着许多局部极值，在寻优过程中易陷入局部区域或在各局部极值间震荡；

F3：f(x,y)=cos(x)cos(y)e[-((x-π)2+(y-π)2)]，在[-2π,2π]的范围内取得全局极大值1。

3.4 实验结果及分析

该文选取AFSA、TSAFSA和量子遗传算法(GQA)三种算法对函数F1、F2及F3进行求解，为了减少随机性对实验结果的影响，算法在每个函数上运行30次，记录其最优值、最差值、平均值和标准差，如表1所示。

表1 各个测试函数的实验结果

由表1可知，TSAFSA在这三个测试函数寻优过程中，都可以找到或接近最优值，寻优性能和稳定性均较优；AFSA在对函数F2寻优时，未搜索到全局最优值，其他寻优性能参数也较差；虽然GQA能全部找到三个函数的全局最大值，但其寻优稳定性和精度较差。以上结果表明TSAFSA的寻优性能优于AFSA、GQA。

3.5 对比其他参考文献的改进算法

为了进一步验证该算法的寻优性能，将该算法与其他参考文献中的算法进行相关的对比实验。

F6[8]:f(x,y)=-(1+(x+y+1)2×(19-14x+3x2-14y+6xy+3y2))×(30+(2x-3y)2)×(18-32x+12x2+48y-36xy+27y2)，变量x,y的范围为[-2，2]，全局极大值为-3；

函数F4的公共参数为：种群规模np=20，人工鱼的感知范围visual=0.1，step=0.008，拥挤因子δ=0.2函数F5的公共参数为种群规模np=20，人工鱼的感知范围visual=10，step=0.1，拥挤因子δ=0.2函数F4-F5寻优对比结果如表2所示。函数F6的公共参数为种群规模np=50，初始视野visual=5，迭代次数为200。其中GSO-Powell为利用Powell方法局部优化的人工萤火虫算法，实验结果如表3所示。函数F7的公共参数设置为：种群规模np=40，感知范围visual=3.5，尝试次数try-number=10，拥挤因子δ=1，最大迭代次数maxgen=1 000实验结果如表4所示。

表2 函数F4-F5的对比实验结果

表3 函数F6的对比实验结果

表4 函数F7的对比试验结果

由表2可得，在对函数F4、F5的寻优过程中，TSAFSA不仅寻优精度高，而且搜索速度快。对函数F6的寻优结果如表3所示，分析实验结果可知，TSAFSA算法的最优值、最差值和平均值均优于算法AFSA、GSO和GSO-Powell；TSAFSA算法的最优值虽然没有文献[8]精确，但其他寻优参数均优于文献[8]，整体性能较文献[8]好一些。表4反映出，针对函数F7的寻优，TSAFSA搜索到的最优解较文献[8]和文献[9]更加精确。由此可见，该改进算法的寻优性能在一定程度上确实有了提高。

4 结束语

针对基本人工鱼群算法存在的缺点及对复杂函数寻优困难等问题，提出了基于禁忌搜索的自适应人工鱼优化算法。TSAFSA算法首先对视野和步长方面的参数进行了改进，随着迭代过程的进行，自适应地调整视野和步长，不仅加快了寻优速度同时也提高了解精度；其次，随机行为有利于鱼群跳出局部极值，但由于其盲目性，也有引起解退化的风险，为了改善这一状况，加入了具有levy飞行机制的自由游动算子；随后，当寻优过程停滞不前时，引入了禁忌搜索的思想，将鱼群寻得的最优值赋值给禁忌搜索的初始值，设立禁忌区域，在禁忌区域内生成小种群继续寻优，明显提高了人工鱼群的寻优精度。最后，通过7个标准测试函数对各个算法的性能进行检测，仿真结果证明了TSAFSA算法的确具有较好的寻优性能。