基于禁忌搜索的蝙蝠算法

2014-04-29罗波袁嵩朱合志

计算机时代 2014年12期

罗波袁嵩朱合志

摘；要：为了克服蝙蝠算法（BA）易陷入局部最优，收敛速度过快等缺点，以基本蝙蝠算法为基础，提出了基于禁忌搜索的蝙蝠算法（TSBA）。TSBA算法将蝙蝠算法和禁忌搜索算法相结合，采用禁忌表以及渴望水平函数的策略，使算法具有更强的全局寻优能力，有效地避免了早熟现象。为了验证该算法的有效性，采用0-1背包问题作为测试内容。实验结果表明，基于禁忌搜索的TSBA蝙蝠算法比基本的蝙蝠算法具有更强的寻优能力和搜索速度。

关键词：蝙蝠算法；禁忌搜索算法；渴望水平函数；禁忌表； 0-1背包问题

中图分类号：TP301.6 ；；；；；文献标志码：A ；；文章编号：1006-8228（2014）12-15-04

Bat algorithm based on tabu search

Luo Bo1，2， Yuan Song1，2， Zhu Hezhi1，2

（1. College of Computer Science and Technology， Wuhan University of Science and Technology， Wuhan， Hubei 430065， China；

2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System）

Abstract： In order to solve disadvantages of the bat algorithm （BA）， such as easy to fall into local optimum and convergence speed is too fast， based on the fundamental bat algorithm， the bat algorithm based on tabu search （TSBA） is put forward. TSBA combines the algorithm and tabu search algorithm. The tabu list and aspiration level function are utilized to give the algorithm as better search ability. The premature phenomenon is efficiently avoided. In order to verify the effectiveness of the algorithm， 0-1 knapsack problem is used to test. The experimental results show that TSBA has better search ability and faster search speedthan the fundamental bat algorithm.

Key words： bat algorithm； tabusearchalgorithm； aspiration level function； tabu list； 0-1 knapsack problem

0 引言

近些年，群智能优化算法[1]逐渐成为求解复杂优化问题的有力工具，在求解复杂优化问题的过程中，都有着不俗的表现，成为了人们越来越关注的研究领域。例如，借鉴生物界的进化规律演化而来的遗传算法[2-3]，受飞鸟集群活动规律得到的粒子群算法[4]，源于蚂蚁在寻找食物发现路径的行为的蚁群算法[5-6]等等，这些群智能优化算法在解决复杂优化问题中都有不错的性能表现。但它们也都存在着算法所得解容易陷入局部优化，求解收敛速度过慢等问题。

蝙蝠算法（Bat Algorithm，BA），是Xin-She Yang在2010年提出的一种元启发式算法[7-8]。蝙蝠算法以微型蝙蝠的回声定位行为为基础，采用不同的脉冲发射频率和响度对复杂优化问题进行求解。在国内，很少学者深入研究蝙蝠算法。目前，该算法已成功应用于工程设计，分类等应用[9-10]。但是，蝙蝠算法依然存在着陷入局部最优、早熟等问题[11]。本文在基本的蝙蝠算法基础上，提出基于禁忌搜索的蝙蝠算法（Bat Algorithm based on Tabu Search，TSBA），融合禁忌搜索算法和蝙蝠算法，引入禁忌表和渴望水平函数；对蝙蝠算法和基于禁忌搜索的蝠算法给出相关介绍，并以0-1背包问题为例对两者作出比较。

1 蝙蝠算法

1.1 自然界中蝙蝠的行为

人们在对蝙蝠的生活习性进行研究的过程中，对蝙蝠有了更深层次的了解，也从蝙蝠的身上模仿学习到许多东西。其中，蝙蝠给人们最大灵感的便是它们身上的声波定位系统，蝙蝠可以通过喉咙发出超声波，然后再依据超声波回应来辨别方向。在黑暗的环境中，蝙蝠能够自如的飞行和捕捉猎物，全部依赖于此。当蝙蝠捕捉猎物时，会不停地产生超声波，如果在超声波行进的途中碰撞到障碍物或者猎物，蝙蝠的耳朵会接受到反射的回声，从而判断障碍物或者猎物的位置以及距离。当蝙蝠越接近猎物时，发出超声波的频率就会越快，而响度会相应地减小，直到靠近猎物时，响度变化到最小。

1.2 蝙蝠算法

1.2.1 蝙蝠的速度改变和位置改变的方式

算法最先需要确定的是蝙蝠的速度更新和位置更新的方式。假设在一个多维空间中，在t时刻，蝙蝠种群中第i只蝙蝠的位置为，速度为，则在t+1时刻的新位置和新速度的更新公式如下：

fi=fmin+（fmax-fmin）β ；⑴

⑵

⑶

公式⑴中的参数β是由算法事先决定的随机变量，并且要求β∈[0，1]。公式⑵中的x*是由算法经过比较当前种群中所有的蝙蝠位置得到的最优蝙蝠位置。蝙蝠种群中的每只蝙蝠会在算法开始时，随机地分配一个频率作为当前蝙蝠发出的频率，而且随机分配的频率的范围在[fmin，fmax]中，即fi∈[fmin，fmax]。

当蝙蝠进行全局搜索后，需要对其中的蝙蝠进行一些扰动，实施蝙蝠的局部搜索。对于局部搜索，蝙蝠的位置是由蝙蝠的原位置根据一定的扰动得到的。局部搜索的位置更新公式如下：

xnew=xold+εAt ；⑷

在公式⑷中，xnew代表局部搜索后蝙蝠的新位置，xold则是蝙蝠的原位置，公式中的ε是一个任意数字，并且ε∈[-1，1]，由算法事先随机得到。

1.2.2 响度和脉冲速率的更新

在蝙蝠算法中，每个蝙蝠独有的脉冲发射的响度和频率是各自不相关的，并且是随着算法的进行不断变化的。因为在蝙蝠进行捕食的过程中，当蝙蝠接近猎物时，脉冲发射速率提高，而响度会不断地减小，直到最后响度为0。蝙蝠算法中的响度和脉冲速率的更新公式如下：

⑸

⑹

在公式⑸和公式⑹中，α和γ均为常量，为算法开始时，预先指定好的参数，其中算法规定0<；α<；1，0<；γ。从公式⑸和公式⑹明显可以看出当t→∞时，→0，→，表现为当蝙蝠发现猎物后，蝙蝠就不再会发出声音。

1.2.3 蝙蝠算法的伪代码

根据上述公式和蝙蝠算法的原理，可以得到如下的蝙蝠算法的伪码：

对蝙蝠种群中的每一个蝙蝠进行相应变量的初始化

依次对每个蝙蝠进行适应值的评价

While（t<；算法规定的最大的迭代次数或者算法所得解的误差在一定的范围内）

for i=1：N

由公式⑵改变蝙蝠的速度，由公式⑶改变蝙蝠的位置

if（rand>；ri）

由公式⑷进行蝙蝠的局部搜索

end if

蝙蝠不受限制飞行，产生一个新的随机解

if（rand<；Ai&；f（xi）<；f（x*））

蝙蝠种群接受这个新解

根据算法中的公式⑸和公式⑹，减小响度Ai，增大频率ri

end if

end for

更新当前最优蝙蝠X*的位置和速度，以及相应的参数

end while

算法流程如图1所示。

[初始化蝙蝠种群][评价每个蝙蝠，找出最佳蝙蝠个体][通过调整频率，调整速度和位置][rand>；ri] [由最佳解集中的解

扰动形成局部解][通过随意飞行产生新解][评估新位置][新位置由于先前位置并且

rand<；Ai] [接受新解][更新响度和频率][更新最优蝙蝠和相应的参数][T<；迭代次数或者误差在

范围内] [输出结果][原位置不变][是] [否][是] [否] [是] [否]

图1 ；基本蝙蝠算法流程图

2 基于禁忌搜索的改进蝙蝠算法

2.1 禁忌搜索算法的基本思想

在算法进行的搜索过程中，将近期的搜索过程放入算法事先建好的禁忌表（Tabu List）中，这是禁忌搜索算法中非常重要的基本思想，也是禁忌搜索算法的本质。

禁忌搜索算法的具体思路如下：以领域优先选择作为禁忌搜索算法的基本搜索方法，使得算法过程中出现的劣解能够被算法接受，因为随着算法迭代的进行，即便是在当前迭代过程为劣解，却很有可能具有寻找算法全局最优解的潜力。算法接受劣解虽然避免了陷入局部最优，但同时有算法进入循环的可能。为了避免算法进入循环，在禁忌表中添加近期被算法所接受的移动，并且这些移动在一段时间内的算法迭代过程中禁止再次出现。随着算法迭代的进行，在禁忌表中的被禁忌对象会不断地更新、轮换，算法后期进入禁忌表中的移动会代替算法前期进入的移动。

2.2 基于禁忌搜索算法的蝙蝠算法

2.2.1 禁忌表

禁忌表是禁忌搜索算法中最不可或缺的一部分，同时也是最能够体现禁忌搜索算法本质核心的重要部分。防止算法在搜索过程中出现循环是禁忌表最大的作用。在基本的蝙蝠算法中，我们向其中加入的禁忌表。这样使得蝙蝠在一段时间内，不会重复地停留在同一个地方，使得算法更趋于全局的搜索。

⑴ 禁忌对象

禁忌对象，指的就是算法中不能够重复出现的对象。不同的算法中，对禁忌对象的选择十分多变，既可以将禁忌对象设置为最近算法中被选择的个体，也可以将禁忌对象设置为算法中个体的状态、或者这些状态的变化以及对个体进行评价的适应值。在不同的情况下，需要根据算法的要求进行不同的选择，以使算法更加简单。在基于禁忌搜索的蝙蝠算法中，采用比较简单的做法，将每只蝙蝠自身的状态作为禁忌表的禁忌对象。也就是说，每个蝙蝠所在的位置为禁忌表中的元素，判断是否将该蝙蝠加入禁忌表是根据它的位置来决定的。以算法中每只蝙蝠的位置作为禁忌对象，这样的选择使得禁忌表更加灵活、简单，算法中对禁忌表的操作更加容易。

⑵ 禁忌长度

当算法中的个体由于重复进入算法迭代过程中，会进入禁忌表，成为被禁忌的对象。进入禁忌表的对象想要从禁忌表中释放出来，必须经过一定的算法迭代次数。也就是说，在一段迭代时间内，如果禁忌表中存在某个被禁忌的操作，那么算法以后将不会允许相同的操作发生。因此，算法中禁忌长度越小的禁忌表，算法所需要计算的时间越少以及禁忌对象在禁忌表中所需要的存储空间也越少。但是禁忌表的长度过小，容易陷入循环，又会成为算法的缺点。在基于禁忌搜索的蝙蝠算法中，算法规定禁忌表的长度不变，为事先设置好的参数。通常简单规定禁忌表的长度不变，为t，t=，N为问题的规模。在该算法中使用固定长度的禁忌表，使得算法更加简单，同时在对禁忌表中的禁忌对象进行查询时，固定长度的禁忌表更为快速，这显得尤为重要。

2.2.2 渴望水平函数

在一些特殊的情况下，不管禁忌表中是否存在这个对象，这个禁忌对象都会被算法作为可行解，并且算法会更新迭代过程中的最优解，所谓的渴望水平函数，就是指的这个特定的条件。在基于禁忌搜索的蝙蝠算法中，采用基于适配值得准则来设定渴望水平函数。若当前蝙蝠的适配值优于最优蝙蝠的适配值，则无论这个蝙蝠是否处于禁忌表中，都会被算法接受作为可行解。渴望水平函数的实现，使得算法的搜索性更趋于全局搜索，更利于找到问题的最优解。

2.2.3 停止规则

在TSBA算法中，共有两种停止规则。一种是事先规定算法迭代的最大次数。一旦算法的迭代次数到达规定次数，算法自动停止。这种方法简单容易。第二种是以得到满意解为停止条件。在算法得到最优解，或者得到的解与最优解在一定的误差内，就结束算法。

2.2.4 基于禁忌搜索的蝙蝠算法

基于禁忌搜索的蝙蝠算法流程图如图2所示。

[初始化禁忌表][初始化蝙蝠种群] [评价每个蝙蝠，找出最佳蝙蝠个体][通过调整频率，调整速度和位置][rand>；ri] [由最佳解集中的解

扰动形成局部解][通过随意飞行产生新解][评估新位置][新位置由于先前位置并且

rand<；Ai] [接受新解][更新响度和频率][更新最优蝙蝠和相应的参数][T<；迭代次数或者误差在

范围内] [输出结果][原位置不变][是] [否][是] [否][是否禁忌表中] [满足渴望水平函数] [否][接受最优蝙蝠新解][将解加入禁忌表] [否][是] [是] [否] [是]

图2 ；基于禁忌搜索的蝙蝠算法流程图

通过将上述禁忌表、渴望水平函数以及停止规则加入蝙蝠算法中，提出了基于禁忌搜索的蝙蝠算法。以蝙蝠的位置作为禁忌对象，以蝙蝠的适配值作为渴望水平函数，以最大迭代次数和误差范围作为算法停止条件。TSBA算法的伪代码如下：

对蝙蝠种群中的每一个蝙蝠进行相应变量的初始化

依次对每个蝙蝠进行适应值的评价

初始化禁忌表

While（t<；算法规定的最大的迭代次数或者算法所得解的误差在

一定的范围内）

for i=1：N

由公式⑵改变蝙蝠的速度，由公式⑶改变蝙蝠的位置

if（rand>；ri）

由公式⑷进行蝙蝠的局部搜索

end if

蝙蝠不受限制飞行，产生一个新的随机解

if（rand<；Ai&；f（xi）<；f（x*））

蝙蝠种群接受这个新解

根据算法中的公式⑸和公式⑹，减小响度Ai，增大频率ri

end if

end for

求出当前蝙蝠种群中候选解

if（整个禁忌表中不包含这个候选解）

该候选解作为算法的可行解，同时加入禁忌表

else

if（满足破禁的要求）

将该解从禁忌表中释放，算法接受该候选解

else

放弃该解，重新获得解

end if

更新最优蝙蝠的相应的参数

end while

2 实验测试

背包问题：共有N个物品，对于每个物品而言，物品i的重量和价值分别用wi和vi来表示（i=1，2，3…N）。如何选择物品装入背包，使它们装入特定容量的背包中时，物品价值总和最大。用0和1组成的编码序列s=x1x2…xi来表示物品组合，为0表示不选择物品i，为1表示选择物品i。则0-1背包问题的数学模型可以描述为：

⑺

⑻

背包问题用惩罚函数进行函数的约束：

Max f（s）=-M×max[0，（-C）] ；⑼

其中M表示一个很大的正数。

算法的参数设置为：频率下界fmin=0，频率上界fmax=1，α= 0.95，γ=0.9。初始响度A∈[0，1]初始脉冲发射频度R∈[0， 0.5]。

例1 全部物件个数D=10，背包最大重量限制C=269，各个物件价值p=[55，10，47，5，4，50，8，61，85，87]，各个物件重量w=[95，4，60，32，23，72，80，62，65，46]，最优值为295。

例2 全部物体个数D=20，背包最大重量限制C=878，各个物件价值p=[44，46，90，72，91，40，75，35，8，54，78，40，77，15，61，17，75，29，75，63]，各个物体重量w=[92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，7048，14，58]，最优值1024。

“最小值”指算法寻优成功代数中的最小数，“平均数”指各个寻优代数的平均数，“成功率”指算法寻优成功的概率，“时间”为至少有一次寻优成功时50次寻优消耗的总时间，F代表算法寻优失败分别运行50次，两者对比如表1。

表1 ；TSBA与BA算法运行结果比较

从表1可以看出，在算法寻优的最小值和平均数上面，TSBA的最小值以及平均数明显小于BA的最小值和平均数，这说明TSBA的收敛速度高于BA算法。在成功率方面，TSBA的成功率为100%，优于BA算法的成功率。并且时间上，TSBA明显小于BA算法的时间。基于禁忌搜索的蝙蝠算法加入禁忌表和渴望水平函数后，上一次算法迭代的结果会进入禁忌表中，以保证下一次不会出现，算法可以接受劣解，这样使得算法具有更强的全局搜索能力。同时，满足渴望水平函数的解，可以从禁忌表中解禁出来，保证最优解能够被算法寻找出，增强了算法的寻优能力和稳定性。这些表明基于禁忌搜索的蝙蝠算法在收敛速度和精度上优于基本的蝙蝠算法。

3 结束语

本文将禁忌搜索算法中的禁忌表和渴望水平函数加入到基本的蝙蝠算法中，不仅使得蝙蝠进化的过程速度加快，也让算法接受劣解的能力得到提高，从而使得算法的收敛速度有了很大的提升，并且算法不容易陷入局部优化中，更易于进入全局搜索，利于全局最优解的探寻，具有更好的寻优能力和可行性。但基于生物的原理，算法中α和γ参数的设置没有明确的规定，所以寻找到使算法具有更好的收敛速度和稳定性的参数设置，是今后需要进一步研究的内容。

参考文献：

[1] 汪定伟.智能优化算法[M].高等教育出版社，2007.

[2] 朱钰，韩昌佩.一种种群自适应收敛的快速遗传算法[J].计算机科学，

2012.39（10）：214-217

[3] 韩丽霞.求解多目标优化问题的新遗传算法[J].计算机科学，2013.40

（6）：64-66

[4] 陈久梅，龚英.求解两级定位一路径问题的粒子群算法[J].计算机应

用，2013.33（8）：2261-2264

[5] 叶仕通，万智萍.一种基于改进全局信息素更新效率的蚁群算法及仿

真[J].计算机应用与软件，2014.31（1）：176-179

[6] 刘文.一种定向式挖掘的连续域蚁群算法[J].计算机科学，2013.40

（12）：292-294