基于禁忌搜索的蝙蝠算法

羅波 袁嵩 朱合志

摘 ?；要： 為了克服蝙蝠算法（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 渴望水平函數

在一些特殊的情況下，不管禁忌表中是否存在這個對象，這個禁忌對象都會被算法作為可行解，并且算法會更新迭代過程中的最優解，所謂的渴望水平函數，就是指的這個特定的條件。在基于禁忌搜索的蝙蝠算法中，采用基于適配值得準則來設定渴望水平函數。若當前蝙蝠的適配值優于最優蝙蝠的適配值，則無論這個蝙蝠是否處于禁忌表中，都會被算法接受作為可行解?？释胶瘮档膶崿F，使得算法的搜索性更趨于全局搜索，更利于找到問題的最優解。

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

[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] 李煜，馬良.新型全局優化蝙蝠算法[J].計算機科學，2013.40（9）：

225-229