禁忌搜索灰狼优化算法研究

2019-12-11郭玉纯曹小鹏胡元娇

计算机技术与发展 2019年12期

郭玉纯，曹小鹏，胡元娇

(西安邮电大学计算机学院，陕西西安 710121)

0 引言

2014年澳大利亚学者Mirjalili模仿狼群种群围攻、捕获猎物的过程提出了灰狼优化算法(grey-wolf-optimization，GWO)[1-3]。灰狼优化算法具有较好的计算鲁棒性和全局搜索能力，自该算法提出以来，在图像处理、图像分割[4]，无人机三维航路规划[5]，流水车间调度[6]，TSP问题[7]，均值聚类[8]，互联电网负荷频率控制[9]等方面应用广泛。

由于灰狼优化算法中灰狼种群始终向全局最优的前三个解靠近，导致其全局搜索能力较弱，对于一些复杂优化问题，如在解决高维度、多模态复杂函数优化问题时，容易陷入局部最优和出现早熟收敛的现象。针对以上问题，张贾奎等提出了一种基于Tent混沌序列的灰狼算法(TCGWO)[10]，以改善算法的寻优性能；伍铁斌提出一种基于对数函数描述收敛因子的改进GWO算法[11]，以避免算法出现早熟收敛；徐慧等提出了融合杜鹃搜索的灰狼优化算法[12]，在全局搜索能力方面有较为显著的提升，将其应用于特征选择中，有效提高了网络入侵检测的性能。以上文献中提出的更新策略，虽然扩大了搜索空间，但是容易跳过全局最优，收敛速度也会变低。

禁忌搜索通过禁忌表来记录若干次搜索历史，下轮迭代可通过检索禁忌表来避免回到历史搜索。文中通过引入禁忌搜索策略，通过对每次迭代产生的最优解α、优解β、次优解δ个体执行禁忌搜索，从而提高算法的全局搜索能力并在算法收敛后期跳出局部最优解，且收敛速度加快。基于此，提出一种禁忌搜索灰狼优化改进算法(tabu search-grey wolf optimization，TS-GWO)，并通过多组实验验证了该策略对算法寻优性能的改进。

1 算法描述

1.1 灰狼优化算法

灰狼属于犬科动物，也被认为是食物链顶端的捕食者，一般种群中包含5-12头狼，它们拥有十分严格的社会统治等级制度。最高领导地位的头狼被叫作α狼，负责决定捕猎的路线、休息地点、工作时间等；第二层级上的灰狼被称为β狼，β狼是α狼的下级，它的主要工作是帮助α狼进行决策以及领导其余灰狼活动，它也是下一任α狼的最佳候选者；最低等级的灰狼就是ω狼，ω狼必须遵从其他领导阶层的灰狼；剩余灰狼则为δ狼，δ狼遵从α狼和β狼，领导ω狼，这个层次的狼包含了侦察狼，哨兵，经验者，猎手以及看护者等等。

(1)包围猎物。

灰狼包围猎物的数学模型描述如下：

(1)

(2)

(3)

(4)

(2)攻击猎物。

α狼引导β狼、δ狼来进行猎物攻击。为了模拟灰狼捕猎，选取前三个最优解，其余灰狼根据α、β、δ更新自己的位置，式5～式7描述了这一过程。

2.3.2实际产量实际产量是处理1(CK)最低，为205.82公斤/亩。依次居第5位的是处理2为209.23公斤/亩，每亩比CK增加小麦3.41公斤，增产1.66%；居第4位的是处理3为220.09公斤/亩，每亩比CK增加小麦15.08公斤，增产7.33%；居第3位的是处理4为235.83公斤/亩，每亩比对照增加小麦30.01公斤，增产14.58%；居第2位的是处理5为262.78公斤/亩，每亩比CK增加小麦56.96公斤，增产27.67%；居第1位的是处理6为283.55公斤/亩，每亩比CK增加小麦77.73公斤/亩，增产37.77%。

(5)

(6)

(7)

1.2 禁忌搜索算法

禁忌搜索算法(tabu search，TS)是1986年由美国科罗拉多大学教授Fred Glover提出的一种启发式随机搜索算法[13]。禁忌搜索算法的核心就是禁忌表的建立，从过去的搜索历史中总结经验和获取知识，避免重新回到原来的搜索历史中，通过禁忌表中记录过往搜索移动，对于禁忌表中的移动，在以后的若干次迭代中是被禁止的，以免回到原来的解。这种做法，有利于在搜索陷入局部最优的时候，重新回到局部最优点，可以跳出局部最优，进行下一轮迭代搜索。其次，当候选解高于以往任何一个最优解，可特赦。禁忌搜索算法的基本流程如下：

Step1:初始化。初始解作为当前解、候选解，禁忌表为空；

Step2:在当前解的邻域选取满足不受禁忌的候选集，选取候选集中适应度值最高的一个解作为最优候选解，替换当前解；

Step3:若最优候选解的适应度值高于最优解，则替换最优解；

Step4:更新禁忌表，将最优候选解加入禁忌表，替换最早进入禁忌表的解；

Step5:判断是否满足算法停止条件，即满足收敛条件或者到达最大迭代次数，如果满足，则输出最优解，如不满足，继续返回Step2。

禁忌搜索对初始解的要求很高，如果初始解过差，会降低收敛速度，并且容易进行无效搜索。

2 基于禁忌搜索的灰狼优化算法改进

GWO算法在每一次迭代均根据灰狼首领的位置来更新所有种群个体位置，然后再计算所有种群个体的适应度值，选取最优的三个作为α、β、δ进行位置更新以及下一次迭代，直至满足收敛条件或者达到最大迭代次数。算法每次迭代不断接近最优解，在算法初期具有较快的收敛速度，在迭代后期若灰狼首领陷入了局部最优，则其余种群个体根据精英位置更新自己位置，均围绕在局部最优点附近，也无法脱离局部最优。因此算法在迭代后期存在全局搜索能力差的缺点，容易陷入局部最优，收敛速度变慢。而禁忌搜索算法会标记已经得到的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程，从而获得更多的搜索区域，避免迂回搜索，进而跳出局部最优解。

为增强人工灰狼跳出局部最优解的能力，迫使狼群在不断逼近猎物的过程中，能随机地跳出局部最优，采取算法混合策略来进行算法优化，利用算法间的优势进行互补来弥补单一算法的不足，进而提升算法性能。灰狼种群根据狼群首领的位置来更新个体位置，对当前灰狼首领进行局部搜索，当其陷入局部最优时，引入禁忌表策略，对搜索历史进行记录，在后若干次的行动中禁止再回到该解位置。基于此文中提出一种基于禁忌搜索的灰狼优化改进算法，该策略主要是选取当前最优的三个解α、β、δ作为初始解进行局部的禁忌搜索，随机选取初始解邻域内的点作为候选解，进行禁忌搜索，每迭代一轮则判断是否优于当前最优解，若优于则更新最优解，并将该解加入禁忌表，否则只更新禁忌表，下一轮迭代开始前，首先判断当前候选解是否在禁忌表中，若存在，则跳过此次迭代。此时可以有效防止灰狼优化算法陷入局部最优，禁忌搜索完成后，根据选取的头狼位置更新种群个体位置，进行下一轮灰狼算法迭代。

TS-GWO算法的流程如下：

Step1:种群初始化，设定最大迭代次数、维度、解空间上下限等；

Step2:计算每个种群个体的适应度值，从中选取最优的三个解作为第一代α,β,δ；

Step4:以α,β,δ的位置通过式1、式2计算X1,X2,X3，通过式7计算每个灰狼的位置；

Step5:计算每个灰狼的适应度值，选取前三作为α,β,δ，以α,β,δ为当前解；

Step6:在当前解的设定邻域里随机选取候选解集合；

Step7:判断当前候选解是否存在于禁忌表中，若存在则跳过此次迭代；

Step8:计算候选解的适应度值，若当前候选解的适应度值高于最优解，则替换最优解；

Step9:更新禁忌表，将最优候选解加入禁忌表，替换最早进入禁忌表的解；

Step10:判断当前解是否满足禁忌搜索收敛条件即达到最大禁忌迭代次数或达到收敛条件，若满足则跳转至Step11，否则跳转至Step6；

Step11:判断是否达到灰狼优化算法最大迭代次数，若满足则跳转至Step12，否则跳转至Step3进行下一次迭代；

Step12:输出最优解。

3 实验设计与仿真分析

3.1 测试函数与对比算法

为了验证TS-GWO算法的性能，选取了八个测试函数进行实验仿真，并与原始PSO[14]、GWO算法进行比较，表1给出了测试函数的基本信息。文中采用平台MATLAB 2016 ra进行实验。为了更好地评价算法的寻优能力以及收敛精度，采用每组测试函数50次独立执行的结果，通过最优适应度(best fitness，BF)、平均适应度值(mean best fitness，MBF)以及标准差(standard deviation，SD)[15]统计学指标对算法进行评价。

其中函数F1-F5为单峰基准函数，在定义区间内存在全局最优值，使用智能优化算法可寻找全局最优解；函数F6-F8为多峰基准函数，在定义区间内含有多个局部最优解，在算法迭代过程中，容易陷入局部最优以及产生局部震荡，可用来测试算法避免早熟收敛和脱离局部最优的能力以及对其余空间的搜索能力。

选择TS-GWO与GWO、PSO算法对上述8个基准测试函数进行实验，参数设置如下:种群规模N=50，最大迭代次数t=1 000，维度dim=30，禁忌搜索的禁忌迭代次数TS-t=200，禁忌表长度为6-13之间的随机数，邻域集合大小为5。PSO参数设置如下:c1=2、c2=2、w=1.0。

表1 测试函数

续表1

3.2 实验结果分析

表2给出了八种测试函数的寻优结果的对比数据，其中SAGWO为文献[15]提出的具有自适应搜索策略的灰狼优化算法，表中该算法的数据来源为该文献。

由表2对比测试结果BF与MBF可知，TS-GWO的寻优结果均优于原始GWO与SAGWO，且TS-GWO与GWO的寻优结果远远高于PSO，其中测试函数F1～F5最优解TS-GWO比GWO更接近全局最小值，收敛精度更高，表明TS-GWO对单峰基准函数有着更高的收敛精度；测试函数F6～F8最优解TS-GWO比GWO更接近全局最小值，表明TS-GWO对多峰基准函数寻优能力更佳。对比指标SD，TS-GWO在稳定性上要高于GWO、SAGWO和PSO。对比三项指标可得，TS-GWO在寻优能力上比GWO、SAGWO和PSO要好，八组测试函数，F1～F6、F8寻优结果TS-GWO均优于GWO与SAGWO，函数F7TS-GWO、SAGWO与GWO均到达最优值点。

表2 测试结果对比

为了进一步对比三种算法脱离局部最优的能力，给出了八组测试函数下的TS-GWO，GWO，PSO的50次实验执行平均最优适应度值曲线，如图1所示。

(a)F1寻优迭代曲线

(b)F2寻优迭代曲线

(c)F3寻优迭代曲线

(d)F4寻优迭代曲线

(e)F5寻优迭代曲线

(f)F6寻优迭代曲线

(g)F7寻优迭代曲线

(h)F8寻优迭代曲线

首先，通过图(a)-(h)，可看出PSO对测试函数的寻优能力最弱，收敛精度最低，且易陷入局部最优；从图(a)-(d)可得，函数F1，F2，F3，F4中原始GWO已趋于平缓，即陷入了局部最优，此时TS-GWO仍然继续收敛，同时，两算法虽然前期收敛速度相似，但迭代多次以后，TS-GWO性能与GWO相比，收敛速度加快，收敛精度也要高于原始GWO；从图(g)可得，函数F7实验结果TS-GWO与GWO相似，收敛速度以及最终收敛精度相差无几，但TS-GWO收敛速度更快；从图(h)可得，函数F8前期迭代寻优性能相似，但在250代以后，GWO陷入局部最优，此时TS-GWO经过数次迭代，跳出局部最优继续收敛；通过图(e)、图(f)对比函数F5,F6的迭代曲线，GWO多次陷入局部最优，TS-GWO均有能力在这种情况下跳出局部最优，达到了更高的收敛精度。

从以上实验结果以及寻优迭代曲线可以得到，TS-GWO在处理单峰函数寻优以及多峰函数脱离局部最优的能力上，比GWO都有明显改善，同时具有优越的稳定性。