基于禁忌搜索的蝙蝠算法

羅波 袁嵩 朱合志

摘 ?；要： 為了克服蝙蝠算法（BA）易陷入局部最優(yōu)，收斂速度過快等缺點(diǎn)，以基本蝙蝠算法為基礎(chǔ)，提出了基于禁忌搜索的蝙蝠算法（TSBA）。TSBA算法將蝙蝠算法和禁忌搜索算法相結(jié)合，采用禁忌表以及渴望水平函數(shù)的策略，使算法具有更強(qiáng)的全局尋優(yōu)能力，有效地避免了早熟現(xiàn)象。為了驗(yàn)證該算法的有效性，采用0-1背包問題作為測試內(nèi)容。實(shí)驗(yàn)結(jié)果表明，基于禁忌搜索的TSBA蝙蝠算法比基本的蝙蝠算法具有更強(qiáng)的尋優(yōu)能力和搜索速度。

關(guān)鍵詞： 蝙蝠算法； 禁忌搜索算法； 渴望水平函數(shù)； 禁忌表； 0-1背包問題

中圖分類號：TP301.6 ?； ?； ?； ?； ?；文獻(xiàn)標(biāo)志碼：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 引言

近些年，群智能優(yōu)化算法[1]逐漸成為求解復(fù)雜優(yōu)化問題的有力工具，在求解復(fù)雜優(yōu)化問題的過程中，都有著不俗的表現(xiàn)，成為了人們越來越關(guān)注的研究領(lǐng)域。例如，借鑒生物界的進(jìn)化規(guī)律演化而來的遺傳算法[2-3]，受飛鳥集群活動規(guī)律得到的粒子群算法[4]，源于螞蟻在尋找食物發(fā)現(xiàn)路徑的行為的蟻群算法[5-6]等等，這些群智能優(yōu)化算法在解決復(fù)雜優(yōu)化問題中都有不錯的性能表現(xiàn)。但它們也都存在著算法所得解容易陷入局部優(yōu)化，求解收斂速度過慢等問題。

蝙蝠算法（Bat Algorithm，BA），是Xin-She Yang在2010年提出的一種元啟發(fā)式算法[7-8]。蝙蝠算法以微型蝙蝠的回聲定位行為為基礎(chǔ)，采用不同的脈沖發(fā)射頻率和響度對復(fù)雜優(yōu)化問題進(jìn)行求解。在國內(nèi)，很少學(xué)者深入研究蝙蝠算法。目前，該算法已成功應(yīng)用于工程設(shè)計，分類等應(yīng)用[9-10]。但是，蝙蝠算法依然存在著陷入局部最優(yōu)、早熟等問題[11]。本文在基本的蝙蝠算法基礎(chǔ)上，提出基于禁忌搜索的蝙蝠算法（Bat Algorithm based on Tabu Search，TSBA），融合禁忌搜索算法和蝙蝠算法，引入禁忌表和渴望水平函數(shù)；對蝙蝠算法和基于禁忌搜索的蝠算法給出相關(guān)介紹，并以0-1背包問題為例對兩者作出比較。

1 蝙蝠算法

1.1 自然界中蝙蝠的行為

人們在對蝙蝠的生活習(xí)性進(jìn)行研究的過程中，對蝙蝠有了更深層次的了解，也從蝙蝠的身上模仿學(xué)習(xí)到許多東西。其中，蝙蝠給人們最大靈感的便是它們身上的聲波定位系統(tǒng)，蝙蝠可以通過喉嚨發(fā)出超聲波，然后再依據(jù)超聲波回應(yīng)來辨別方向。在黑暗的環(huán)境中，蝙蝠能夠自如的飛行和捕捉獵物，全部依賴于此。當(dāng)蝙蝠捕捉獵物時，會不停地產(chǎn)生超聲波，如果在超聲波行進(jìn)的途中碰撞到障礙物或者獵物，蝙蝠的耳朵會接受到反射的回聲，從而判斷障礙物或者獵物的位置以及距離。當(dāng)蝙蝠越接近獵物時，發(fā)出超聲波的頻率就會越快，而響度會相應(yīng)地減小，直到靠近獵物時，響度變化到最小。

1.2 蝙蝠算法

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

算法最先需要確定的是蝙蝠的速度更新和位置更新的方式。假設(shè)在一個多維空間中，在t時刻，蝙蝠種群中第i只蝙蝠的位置為，速度為，則在t+1時刻的新位置和新速度的更新公式如下：

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

⑵

⑶

公式⑴中的參數(shù)β是由算法事先決定的隨機(jī)變量，并且要求β∈[0，1]。公式⑵中的x*是由算法經(jīng)過比較當(dāng)前種群中所有的蝙蝠位置得到的最優(yōu)蝙蝠位置。蝙蝠種群中的每只蝙蝠會在算法開始時，隨機(jī)地分配一個頻率作為當(dāng)前蝙蝠發(fā)出的頻率，而且隨機(jī)分配的頻率的范圍在[fmin，fmax]中，即fi∈[fmin，fmax]。

當(dāng)蝙蝠進(jìn)行全局搜索后，需要對其中的蝙蝠進(jìn)行一些擾動，實(shí)施蝙蝠的局部搜索。對于局部搜索，蝙蝠的位置是由蝙蝠的原位置根據(jù)一定的擾動得到的。局部搜索的位置更新公式如下：

xnew=xold+εAt ?；⑷

在公式⑷中，xnew代表局部搜索后蝙蝠的新位置，xold則是蝙蝠的原位置，公式中的ε是一個任意數(shù)字，并且ε∈[-1，1]，由算法事先隨機(jī)得到。

1.2.2 響度和脈沖速率的更新

在蝙蝠算法中，每個蝙蝠獨(dú)有的脈沖發(fā)射的響度和頻率是各自不相關(guān)的，并且是隨著算法的進(jìn)行不斷變化的。因?yàn)樵隍疬M(jìn)行捕食的過程中，當(dāng)蝙蝠接近獵物時，脈沖發(fā)射速率提高，而響度會不斷地減小，直到最后響度為0。蝙蝠算法中的響度和脈沖速率的更新公式如下：

⑸

⑹

在公式⑸和公式⑹中，α和γ均為常量，為算法開始時，預(yù)先指定好的參數(shù)，其中算法規(guī)定0<；α<；1，0<；γ。從公式⑸和公式⑹明顯可以看出當(dāng)t→∞時，→0，→，表現(xiàn)為當(dāng)蝙蝠發(fā)現(xiàn)獵物后，蝙蝠就不再會發(fā)出聲音。

1.2.3 蝙蝠算法的偽代碼

根據(jù)上述公式和蝙蝠算法的原理，可以得到如下的蝙蝠算法的偽碼：

對蝙蝠種群中的每一個蝙蝠進(jìn)行相應(yīng)變量的初始化

依次對每個蝙蝠進(jìn)行適應(yīng)值的評價

While（t<；算法規(guī)定的最大的迭代次數(shù)或者算法所得解的誤差在一定的范圍內(nèi)）

for i=1：N

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

if（rand>；ri）

由公式⑷進(jìn)行蝙蝠的局部搜索

end if

蝙蝠不受限制飛行，產(chǎn)生一個新的隨機(jī)解

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

蝙蝠種群接受這個新解

根據(jù)算法中的公式⑸和公式⑹，減小響度Ai，增大頻率ri

end if

end for

更新當(dāng)前最優(yōu)蝙蝠X*的位置和速度，以及相應(yīng)的參數(shù)

end while

算法流程如圖1所示。

[初始化蝙蝠種群][評價每個蝙蝠，找出最佳蝙蝠個體][通過調(diào)整頻率，調(diào)整速度和位置][rand>；ri] [由最佳解集中的解

擾動形成局部解][通過隨意飛行產(chǎn)生新解][評估新位置][新位置由于先前位置并且

rand<；Ai] [接受新解][更新響度和頻率][更新最優(yōu)蝙蝠和相應(yīng)的參數(shù)][T<；迭代次數(shù)或者誤差在

范圍內(nèi)] [輸出結(jié)果][原位置不變][是] [否][是] [否] [是] [否]

圖1 ?；基本蝙蝠算法流程圖

2 基于禁忌搜索的改進(jìn)蝙蝠算法

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

在算法進(jìn)行的搜索過程中，將近期的搜索過程放入算法事先建好的禁忌表（Tabu List）中，這是禁忌搜索算法中非常重要的基本思想，也是禁忌搜索算法的本質(zhì)。

禁忌搜索算法的具體思路如下：以領(lǐng)域優(yōu)先選擇作為禁忌搜索算法的基本搜索方法，使得算法過程中出現(xiàn)的劣解能夠被算法接受，因?yàn)殡S著算法迭代的進(jìn)行，即便是在當(dāng)前迭代過程為劣解，卻很有可能具有尋找算法全局最優(yōu)解的潛力。算法接受劣解雖然避免了陷入局部最優(yōu)，但同時有算法進(jìn)入循環(huán)的可能。為了避免算法進(jìn)入循環(huán)，在禁忌表中添加近期被算法所接受的移動，并且這些移動在一段時間內(nèi)的算法迭代過程中禁止再次出現(xiàn)。隨著算法迭代的進(jìn)行，在禁忌表中的被禁忌對象會不斷地更新、輪換，算法后期進(jìn)入禁忌表中的移動會代替算法前期進(jìn)入的移動。

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

2.2.1 禁忌表

禁忌表是禁忌搜索算法中最不可或缺的一部分，同時也是最能夠體現(xiàn)禁忌搜索算法本質(zhì)核心的重要部分。防止算法在搜索過程中出現(xiàn)循環(huán)是禁忌表最大的作用。在基本的蝙蝠算法中，我們向其中加入的禁忌表。這樣使得蝙蝠在一段時間內(nèi)，不會重復(fù)地停留在同一個地方，使得算法更趨于全局的搜索。

⑴ 禁忌對象

禁忌對象，指的就是算法中不能夠重復(fù)出現(xiàn)的對象。不同的算法中，對禁忌對象的選擇十分多變，既可以將禁忌對象設(shè)置為最近算法中被選擇的個體，也可以將禁忌對象設(shè)置為算法中個體的狀態(tài)、或者這些狀態(tài)的變化以及對個體進(jìn)行評價的適應(yīng)值。在不同的情況下，需要根據(jù)算法的要求進(jìn)行不同的選擇，以使算法更加簡單。在基于禁忌搜索的蝙蝠算法中，采用比較簡單的做法，將每只蝙蝠自身的狀態(tài)作為禁忌表的禁忌對象。也就是說，每個蝙蝠所在的位置為禁忌表中的元素，判斷是否將該蝙蝠加入禁忌表是根據(jù)它的位置來決定的。以算法中每只蝙蝠的位置作為禁忌對象，這樣的選擇使得禁忌表更加靈活、簡單，算法中對禁忌表的操作更加容易。

⑵ 禁忌長度

當(dāng)算法中的個體由于重復(fù)進(jìn)入算法迭代過程中，會進(jìn)入禁忌表，成為被禁忌的對象。進(jìn)入禁忌表的對象想要從禁忌表中釋放出來，必須經(jīng)過一定的算法迭代次數(shù)。也就是說，在一段迭代時間內(nèi)，如果禁忌表中存在某個被禁忌的操作，那么算法以后將不會允許相同的操作發(fā)生。因此，算法中禁忌長度越小的禁忌表，算法所需要計算的時間越少以及禁忌對象在禁忌表中所需要的存儲空間也越少。但是禁忌表的長度過小，容易陷入循環(huán)，又會成為算法的缺點(diǎn)。在基于禁忌搜索的蝙蝠算法中，算法規(guī)定禁忌表的長度不變，為事先設(shè)置好的參數(shù)。通常簡單規(guī)定禁忌表的長度不變，為t，t=，N為問題的規(guī)模。在該算法中使用固定長度的禁忌表，使得算法更加簡單，同時在對禁忌表中的禁忌對象進(jìn)行查詢時，固定長度的禁忌表更為快速，這顯得尤為重要。

2.2.2 渴望水平函數(shù)

在一些特殊的情況下，不管禁忌表中是否存在這個對象，這個禁忌對象都會被算法作為可行解，并且算法會更新迭代過程中的最優(yōu)解，所謂的渴望水平函數(shù)，就是指的這個特定的條件。在基于禁忌搜索的蝙蝠算法中，采用基于適配值得準(zhǔn)則來設(shè)定渴望水平函數(shù)。若當(dāng)前蝙蝠的適配值優(yōu)于最優(yōu)蝙蝠的適配值，則無論這個蝙蝠是否處于禁忌表中，都會被算法接受作為可行解。渴望水平函數(shù)的實(shí)現(xiàn)，使得算法的搜索性更趨于全局搜索，更利于找到問題的最優(yōu)解。

2.2.3 停止規(guī)則

在TSBA算法中，共有兩種停止規(guī)則。一種是事先規(guī)定算法迭代的最大次數(shù)。一旦算法的迭代次數(shù)到達(dá)規(guī)定次數(shù)，算法自動停止。這種方法簡單容易。第二種是以得到滿意解為停止條件。在算法得到最優(yōu)解，或者得到的解與最優(yōu)解在一定的誤差內(nèi)，就結(jié)束算法。

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

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

[初始化禁忌表][初始化蝙蝠種群] [評價每個蝙蝠，找出最佳蝙蝠個體][通過調(diào)整頻率，調(diào)整速度和位置][rand>；ri] [由最佳解集中的解

擾動形成局部解][通過隨意飛行產(chǎn)生新解][評估新位置][新位置由于先前位置并且

rand<；Ai] [接受新解][更新響度和頻率][更新最優(yōu)蝙蝠和相應(yīng)的參數(shù)][T<；迭代次數(shù)或者誤差在

范圍內(nèi)] [輸出結(jié)果][原位置不變][是] [否][是] [否][是否禁忌表中] [滿足渴望水平函數(shù)] [否][接受最優(yōu)蝙蝠新解][將解加入禁忌表] [否][是] [是] [否] [是]

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

通過將上述禁忌表、渴望水平函數(shù)以及停止規(guī)則加入蝙蝠算法中，提出了基于禁忌搜索的蝙蝠算法。以蝙蝠的位置作為禁忌對象，以蝙蝠的適配值作為渴望水平函數(shù)，以最大迭代次數(shù)和誤差范圍作為算法停止條件。TSBA算法的偽代碼如下：

對蝙蝠種群中的每一個蝙蝠進(jìn)行相應(yīng)變量的初始化

依次對每個蝙蝠進(jìn)行適應(yīng)值的評價

初始化禁忌表

While（t<；算法規(guī)定的最大的迭代次數(shù) 或者 算法所得解的誤差在

一定的范圍內(nèi)）

for i=1：N

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

if（rand>；ri）

由公式⑷進(jìn)行蝙蝠的局部搜索

end if

蝙蝠不受限制飛行，產(chǎn)生一個新的隨機(jī)解

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

蝙蝠種群接受這個新解

根據(jù)算法中的公式⑸和公式⑹，減小響度Ai，增大頻率ri

end if

end for

求出當(dāng)前蝙蝠種群中候選解

if（整個禁忌表中不包含這個候選解）

該候選解作為算法的可行解，同時加入禁忌表

else

if（滿足破禁的要求）

將該解從禁忌表中釋放，算法接受該候選解

else

放棄該解，重新獲得解

end if

更新最優(yōu)蝙蝠的相應(yīng)的參數(shù)

end while

2 實(shí)驗(yàn)測試

背包問題：共有N個物品，對于每個物品而言，物品i的重量和價值分別用wi和vi來表示（i=1，2，3…N）。如何選擇物品裝入背包，使它們裝入特定容量的背包中時，物品價值總和最大。用0和1組成的編碼序列s=x1x2…xi來表示物品組合，為0表示不選擇物品i，為1表示選擇物品i。則0-1背包問題的數(shù)學(xué)模型可以描述為：

⑺

⑻

背包問題用懲罰函數(shù)進(jìn)行函數(shù)的約束：

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

其中M表示一個很大的正數(shù)。

算法的參數(shù)設(shè)置為：頻率下界fmin=0，頻率上界fmax=1，α= 0.95，γ=0.9。初始響度A∈[0，1]初始脈沖發(fā)射頻度R∈[0， 0.5]。

例1 全部物件個數(shù)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]，最優(yōu)值為295。

例2 全部物體個數(shù)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]，最優(yōu)值1024。

“最小值”指算法尋優(yōu)成功代數(shù)中的最小數(shù)，“平均數(shù)”指各個尋優(yōu)代數(shù)的平均數(shù)，“成功率”指算法尋優(yōu)成功的概率，“時間”為至少有一次尋優(yōu)成功時50次尋優(yōu)消耗的總時間，F(xiàn)代表算法尋優(yōu)失敗分別運(yùn)行50次，兩者對比如表1。

表1 ?；TSBA與BA算法運(yùn)行結(jié)果比較

從表1可以看出，在算法尋優(yōu)的最小值和平均數(shù)上面，TSBA的最小值以及平均數(shù)明顯小于BA的最小值和平均數(shù)，這說明TSBA的收斂速度高于BA算法。在成功率方面，TSBA的成功率為100%，優(yōu)于BA算法的成功率。并且時間上，TSBA明顯小于BA算法的時間?；诮伤阉鞯尿鹚惴尤虢杀砗涂释胶瘮?shù)后，上一次算法迭代的結(jié)果會進(jìn)入禁忌表中，以保證下一次不會出現(xiàn)，算法可以接受劣解，這樣使得算法具有更強(qiáng)的全局搜索能力。同時，滿足渴望水平函數(shù)的解，可以從禁忌表中解禁出來，保證最優(yōu)解能夠被算法尋找出，增強(qiáng)了算法的尋優(yōu)能力和穩(wěn)定性。這些表明基于禁忌搜索的蝙蝠算法在收斂速度和精度上優(yōu)于基本的蝙蝠算法。

3 結(jié)束語

本文將禁忌搜索算法中的禁忌表和渴望水平函數(shù)加入到基本的蝙蝠算法中，不僅使得蝙蝠進(jìn)化的過程速度加快，也讓算法接受劣解的能力得到提高，從而使得算法的收斂速度有了很大的提升，并且算法不容易陷入局部優(yōu)化中，更易于進(jìn)入全局搜索，利于全局最優(yōu)解的探尋，具有更好的尋優(yōu)能力和可行性。但基于生物的原理，算法中α和γ參數(shù)的設(shè)置沒有明確的規(guī)定，所以尋找到使算法具有更好的收斂速度和穩(wěn)定性的參數(shù)設(shè)置，是今后需要進(jìn)一步研究的內(nèi)容。

參考文獻(xiàn)：

[1] 汪定偉.智能優(yōu)化算法[M].高等教育出版社，2007.

[2] 朱鈺，韓昌佩.一種種群自適應(yīng)收斂的快速遺傳算法[J].計算機(jī)科學(xué)，

2012.39（10）：214-217

[3] 韓麗霞.求解多目標(biāo)優(yōu)化問題的新遺傳算法[J].計算機(jī)科學(xué)，2013.40

（6）：64-66

[4] 陳久梅，龔英.求解兩級定位一路徑問題的粒子群算法[J].計算機(jī)應(yīng)

用，2013.33（8）：2261-2264

[5] 葉仕通，萬智萍.一種基于改進(jìn)全局信息素更新效率的蟻群算法及仿

真[J].計算機(jī)應(yīng)用與軟件，2014.31（1）：176-179

[6] 劉文.一種定向式挖掘的連續(xù)域蟻群算法[J].計算機(jī)科學(xué)，2013.40

（12）：292-294

[7] Xin-She Yang，SiamakTalatahari. Bat algorithm for constrained

optimization tasks[M]. Neural Comput&； Applic，2013.22：1239-1255

[8] Xin-She Yang. Bat algorithm for multi-objectiveoptimization[J].

Int. J. Bio-Inspired Computation，2011.3（5）：267-274

[9] 李煜，馬良.新型全局優(yōu)化蝙蝠算法[J].計算機(jī)科學(xué)，2013.40（9）：

225-229