基于t分布變異的蝙蝠算法

常 青，賀興時

（西安工程大學理學院，陜西西安 710048）

基于t分布變異的蝙蝠算法

常 青，賀興時

（西安工程大學理學院，陜西西安 710048）

為了進一步提高BA算法的性能，提出一種基于t分布變異的蝙蝠算法（TMBA）.該算法通過對最優(yōu)的蝙蝠個體進行高斯變異，對非最優(yōu)蝙蝠個體進行自適應t分布變異，使得算法在進化初期具有良好的全局探索性，而在進化后期具有較優(yōu)的局部開發(fā)性.通過選取6個典型函數(shù)對BA、ABA和TMBA進行對比實驗，結果表明TMBA優(yōu)于BA、ABA.

蝙蝠算法；t分布變異；高斯變異

0 引 言

蝙蝠算法是基于微蝙蝠回聲定位行為提出的一種元啟發(fā)式算法，并已廣泛地應用于復雜優(yōu)化問題.蝙蝠算法（Bat Algorithm，BA）［1］是2010年由Yang提出的一種基于種群隨機尋優(yōu)的全局優(yōu)化算法.由于該算法模型簡單，收斂速度快，已廣泛應用于多目標優(yōu)化［2］、工程優(yōu)化［3］等問題中.為了進一步提高算法的性能，國內(nèi)許多學者對蝙蝠算法進行了改進.文獻［4］開發(fā)了一種混合蝙蝠乍法，使用差分進化作為蝙蝠算法局部搜索的一部分，改進了該算法.文獻［5］將蝙蝠算法與和聲搜索結合，產(chǎn)生了用于函數(shù)基準數(shù)值優(yōu)化的混合蝙蝠算法.文獻［6］將模擬退火的思想引入到蝙蝠優(yōu)化算法中.這些改進算法在不同程度上提高了算法的性能.但是，針對高維目標函數(shù)的改進方法，目前成果較少.

本文針對BA易早熟，對高維函數(shù)尋優(yōu)精度低等缺陷，在分析原有算法優(yōu)化機理的基礎上，提出一種基于自適應t分布變異的蝙蝠算法，在優(yōu)化過程中，對最優(yōu)的蝙蝠個體進行高斯變異，對非最優(yōu)蝙蝠個體進行自適應t分布變異，使算法有效擺脫局部極值的束縛，同時提高了該算法的收斂速度和解的精度.

1 蝙蝠算法和變異策略

1.1 蝙蝠算法

蝙蝠算法是在理想的狀態(tài)下，利用蝙蝠在覓食時所發(fā)出的脈沖的頻率、音強、脈沖發(fā)射頻度的變化而模擬設計出的一種群智能算法.為模擬蝙蝠的回聲定位特征，理想化的假設如下［7］：

（a）所有蝙蝠利用回聲定位感應距離，并能夠判斷獵物和障礙物之間的差異.

（b）蝙蝠是以速度Vi、位置Xi和固定頻率f（或波長λ）隨機飛行的，并用可變化的波長λ（或頻率f）和脈沖音強A來搜索獵物，它們會根據(jù)獵物的接近程度調整其發(fā)出的脈沖頻率.

（c）雖然音強在不同形式下變化不同，在這里假設音強從一個很大的（正數(shù)）A變化到最小值Amin.

基于以上規(guī)則，蝙蝠算法的基本步驟可以概括如下：

Step1：參數(shù)初始化，最大迭代次數(shù)maxgen，蝙蝠種群規(guī)模sizepop，蝙蝠的位置Xi，搜索脈沖頻率范圍［fmin，fmax］，脈沖音強A，脈沖頻度r；

Step2：種群迭代，按式（1）分別對蝙蝠的頻率fi，速度vi，位置Xi進行更新；

其中，β∈［0，1］是一個服從均勻分布的隨機向量.x＊表示當前全局最優(yōu)解，它是通過比較所有n只蝙蝠搜索到的解而得到的.另外，依據(jù)問題需要搜索的范圍大小，令fmin＝0，fmax＝O（1）.初始時，每只蝙蝠隨機賦給一個頻率，這個頻率服從［fmin，fmax］間的均勻分布.

Step3：如果rand＞r，選擇最優(yōu)蝙蝠個體，通過隨機游走法則在最優(yōu)蝙蝠個體附近形成局部新解，如式（2）所示，

其中，ε∈［－1，1］是一個隨機數(shù)，At＝＜Ati＞是所有蝙蝠在同一個時間段的平均音量.

Step4：通過隨機飛行產(chǎn)生一個新解；

Step5：如果rand＜A，并且蝙蝠的適應值得到改善，則接收這個新解.按式（3）增大ri減小Ai；

其中，α和γ為常量.

Step6：按照適應值大小蝙蝠群體進行排列，找到當前最優(yōu)蝙蝠所處空間位置及其適應值.

Step7：迭代尋優(yōu)，返回Step2，直到滿足終止條件為止.

Step8：終止算法，輸出最優(yōu)蝙蝠個體的適應值及位置.

1.2 變異策略

學生t分布又簡稱為t分布.威廉·戈塞于1908年首先推導發(fā)表，t分布含有參數(shù)自由度n，而它的曲線形態(tài)與n大小有關，自由度n越小，t分布曲線愈平坦，曲線中間愈低，曲線雙側尾部翹得愈高；當自由度n＝1時，t分布曲線為柯西分布曲線.即t（n＝1）＝C（0，1），其中C（0，1）為柯西分布；自由度n愈大，t分布曲線愈接近正態(tài)分布曲線，當自由度n→∞時，t分布曲線近似為高斯分布曲線.即t（n→∞）→N（0，1），其中N（0，1）為高斯分布.也就是說標準高斯分布和柯西分布是t分布的兩個特例.柯西分布、正態(tài)分布、t分布的密度，從圖1可以看出，柯西分布尾部曲線呈現(xiàn)長而平坦的形態(tài)，正態(tài)分布的尾部曲線呈現(xiàn)出短而陡的形態(tài).柯西變異比高斯變異有更大的可能性產(chǎn)生遠離親代的下一代點［8］.

圖1 柯西分布、正態(tài)分布、t分布的概率密度函數(shù)曲線Fig.1 Curves of probability density function for cauchy Gaussian and t distribution

本文對蝙蝠個體X優(yōu)＝（xi1，xi2，…，xid），采取自適應t分布的變異策略，具體定義如下：X′＝X優(yōu)＋X優(yōu)?ε.（4）其中，ε和Xi是同階的隨機矩陣，每個元素εi～t（Iteration），?表示點乘.式（4）表示在當前蝙蝠個體空間位置Xi的基礎上增加了t分布隨機干擾項Xi?ε，充分利用當前種群的信息進行變異.自適應t分布變異策略使用算法的迭代次數(shù)Iteration作為t分布的自由度參數(shù).算法在運行初期Iteration值較小，t分布變異近似于柯西分布變異，具有良好的全局探索性，有助于算法跳出局部最優(yōu)點，避免過早收斂；算法運行中期，t分布變異介于柯西分布變異和高斯變異之間；算法在運行后期，Iteration值較大，t分布變異近似于高斯分布變異，具有較優(yōu)的局部開發(fā)性，有助于算法提高解的質量，加快收斂速度.因此本文提出的基于自適應t分布變異的蝙蝠算法（TMBA）優(yōu)勢在于，基于t分布的變異策略將高斯分布和柯西分布兩者變異的優(yōu)勢結合起來，從而提高了算法的全局探索和局部開發(fā)能力，使蝙蝠算法能夠跳出局部最優(yōu)點的束縛，收斂于全局極值點，同時也提高了收斂速度.鑒于高斯分布具有良好的局部開發(fā)能力，為提高算法解的質量，還需做的一項工作是，在最優(yōu)蝙蝠個體上加上一個服從高斯分布的隨機擾動項.對最優(yōu)蝙蝠個體X優(yōu)＝（x1，x2，…，xd）進行高斯變異定義如下：

其中，Φ和X優(yōu)是同階的隨機矩陣；每個元素ηi～t（Iteration）；?表示點乘.

2 改進的蝙蝠算法

基于自適應t分布變異的蝙蝠算法的思想是為了利用柯西分布的全局探索性和高斯分布的局部開發(fā)性，提出一種基于t分布的變異策略［9］.當蝙蝠個體陷入局部最優(yōu)點時，對當前蝙蝠種群中最優(yōu)蝙蝠個體采取高斯變異策略，將高斯變異后的蝙蝠個體與全局最優(yōu)蝙蝠個體的適應值進行比較，取二者最優(yōu)值替代全局最優(yōu)值，對其他蝙蝠個體采取t分布變異策略.這樣一方面增加了蝙蝠種群的多樣性，有利于算法跳出局部最優(yōu)點；另一方面增強了算法的全局搜索和局部開發(fā)的性能，提高了解的質量和算法的收斂速度.在算法迭代過程中，當全局最優(yōu)值在連續(xù)兩次迭代過程中沒有改變或者變化很小，小于η時，看作蝙蝠算法尋優(yōu)停滯，啟動高斯變異策略和t分布變異策略.算法主要步驟如下：

（a）產(chǎn)生初始化群體.在控制變量可行域內(nèi)隨機生成n個蝙蝠個體，形成初始蝙蝠種群.隨機初始化蝙蝠的位置、速度、頻率、脈沖頻度和脈沖音強.參數(shù)beststep表示最優(yōu)蝙蝠個體連續(xù)不變的次數(shù)，初始置為0；

（b）評價種群.對當前種群中的每個蝙蝠個體進行評價，找到當前全局最優(yōu)值.

（c）更新種群.在種群迭代過程中，按式（1）分別對蝙蝠的頻率fi，速度vi，空間位置Xi進行更新.

（d）生成隨機數(shù)rand.如果rand＞r，選擇最優(yōu)蝙蝠個體，通過隨機游走法則得到局部新解，如式（2）所示.

（e）評價種群.對當前種群中的每個個體進行評價，若某個個體優(yōu)于全局最優(yōu)蝙蝠個體，則全局最優(yōu)蝙蝠個體更新為該個體.并置beststep為0.

（f）變異條件判斷.判斷beststep是否已達到預置的連續(xù)不變化次數(shù)的最大閾值maxstep，或連續(xù)兩次迭代變化很小（＜η）.若是，執(zhí)行第（g）步；否則轉到第（h）步執(zhí)行.

（g）變異操作：1.對當前種群中最優(yōu)蝙蝠個體進行高斯變異，對其他蝙蝠個體進行t分布變異；2.對新形成的蝙蝠種群計算各蝙蝠的函數(shù)適應值，并與全局最優(yōu)值進行比較，如果優(yōu)于全局最優(yōu)值，則以自身替換；3.beststep置為0.

（h）終止條件判斷：判斷是否已達到預置的最大迭代次數(shù)Maxgen或判斷最優(yōu)解是否達到了滿意的誤差界內(nèi)，若不滿足，則beststep加1更新，轉到第（c）步執(zhí)行，進行下一步蝙蝠優(yōu)化過程；否則轉到第（i）步執(zhí)行.（i）算法終止，輸出最優(yōu)解.TMBA算法流程如圖2所示.

3 仿真實驗

3.1 基準測試函數(shù)

在本次實驗中，為了研究TMBA的有效性，選取了6個典型的基準測試函數(shù)，其中，Sphere，Zakharov，Sum Squaares為單模態(tài)函數(shù)，Ackley，Griewangk，Rastrigin為多模態(tài)函數(shù)，各個函數(shù)的搜索空間、全局最優(yōu)值和函數(shù)解析式見表1.

3.2 結果與討論

為了研究TMBA算法的性能，驗證該算法的有效性，本文采用BA、ABA［10］和TMBA 3種算法進行實驗對比分析.本文仿真實驗均在Matlab 7.11.0（R2010b）環(huán)境下運行.具體參數(shù)設置為：種群數(shù)50，當維數(shù)為10，50維時，迭代次數(shù)分別為1 000次，2 000次.最小頻率值為0，最大頻率值設為2，最大脈沖音強A為0.25，脈沖頻度r為0.5.

3.2.1 BA，ABA和TMBA尋優(yōu)結果對比 為了防止算法的偶然性，分別對3種算法獨立運行30次，運行結果見表2.其中，平均值反映了算法達到最大迭代次數(shù)時解的質量；標準差體現(xiàn)了算法的收斂穩(wěn)定性.

從表2的結果可以看出，不管對于單模態(tài)函數(shù)，還是多模態(tài)函數(shù)，低維函數(shù)還是高維函數(shù)，基于t分布變異的TMBA算法在解的質量上都明顯高于基本BA算法和自適應變異的ABA算法.TMBA算法解的標準差要小于其他兩個算法解的標準差，可見TMBA算法更具有穩(wěn)定性.雖然，各個算法在同一基準函數(shù)下，隨著維數(shù)的增加，解的質量有所下降，但這是合理的，因為解的搜索空間隨著問題維數(shù)的增加呈指數(shù)形式增加.

圖2 TMBA算法流程圖Fig.2 Flow chart of TMBA algorithm

表1 基準測試函數(shù)Table 1 Test fnctions

表2 BA、ABA、TMBA對6個基準函數(shù)的尋優(yōu)結果Table 2 The optimization result of BA，ABA，and IBA for six functions

3.2.2 BA、ABA和TMBA進化曲線對比 為了進一步測試TMBA算法的性能，在相同的條件下，對表1所示的基準函數(shù)進行仿真模擬，對各算法的進化曲線進行對比，結果如圖3～8所示.進化曲線的橫軸表示進化的迭代次數(shù)，縱軸表示目標函數(shù)的適應度值.

Sphere函數(shù)是簡單的單峰函數(shù)，除了唯一的全局最小解，沒有局部最小解，是許多單峰函數(shù)以及一般優(yōu)化函數(shù)的代表，對于此類函數(shù)，大部分算法都能得到一個較好的結果.因此要做的工作是，在高維情況下，改進的算法要盡可能的提高解的精度.函數(shù)Sphere進化曲線如圖3所示.由圖3可以看出，TMBA算法下，測試函數(shù)迭代曲線下降速度很快，解的質量明顯高于BA和ABA兩種算法.解的精度至少提高了20個數(shù)量級.Zakharov函數(shù)除了唯一的全局最小解，沒有局部最小解.函數(shù)Zakharov進化曲線如圖4所示.從圖4可以看出，TMBA的解的質量要高于BA和ABA解的質量.

圖3 函數(shù)Sphere進化曲線Fig.3 Convergence curve of function for Sphere

圖4 函數(shù)Zakharov進化曲線Fig.4 Convergence curve of function for Zakharov

圖5 函數(shù)Sum squares進化曲線Fig.5 Convergence curve of function for Sum squares

圖6 函數(shù)Ackley進化曲線Fig.6 Convergerce curve of function for Ackley

對于Sum squares函數(shù)來說，BA和ABA的蝙蝠個體容易陷入局部最優(yōu)點且不易跳出.函數(shù)Sum squares進化曲線如圖5所示.從圖5可以看出，TMBA可以在搜索范圍內(nèi)快速搜索，得到一個精度較高的解.

Ackley函數(shù)是多模態(tài)函數(shù)，有少數(shù)的局部最小值，它的特征是幾乎平坦的區(qū)域由于余弦波的影響而起伏不平.為避免算法陷入局部最優(yōu)，就要增大問題的搜索區(qū)域.基于t分布變異的TMBA算法利用變異增加了種群的多樣性，搜索的區(qū)域也就更大，在高維的情況下，該函數(shù)是測試算法是否收斂的最好工具.函數(shù)Ackley進化曲線如圖6所示.從圖6可以看出，TMBA以較快的速度收斂于一個精度更高的解.解的精度至少提高了10個數(shù)量級.

圖7 函數(shù)Griewangk進化曲線Fig.7 Convergence curve of functionfor Griewangk

圖8 函數(shù)Rastrigin進化曲線Fig.8 Convergence curve of functionfor Rastrigin

Griewangk函數(shù)是典型的非線性多模態(tài)函數(shù)，有無數(shù)個局部最優(yōu)解.函數(shù)Griewangk進化曲線如圖7所示.從圖7可以看出，在高維的情況下，TMBA在迭代初期就表現(xiàn)出良好的性能，并以較快的速度收斂于一個精度較高的解.而且TMBA能達到Griewangk函數(shù)的理論最優(yōu)值0.Rastrigin函數(shù)是多模態(tài)函數(shù)，有數(shù)個局部最優(yōu)解.函數(shù)Rastrigin進化曲線如圖8所示.從圖8可以看出，TMBA算法解的精度更高.

4 結束語

蝙蝠算法是一類新型的搜索全局最優(yōu)解的隨機優(yōu)化技術.本文提出的基于t分布變異的蝙蝠算法，由于引入t分布變異策略增加了種群的多樣性，有利于算法跳出局部最小值的束縛，因此加快蝙蝠算法的收斂速度，提高了解的質量.由仿真實驗結果可以看出，該算法的性能在不同程度上優(yōu)于其他優(yōu)化算法.

［1］ YANG X S.A new metaheuristic bat－inspired algorithm［M］.Nature Inspired Cooperative Strate－gies for Optimization.Bristol：Lunivers Press，2010：97－104.

［2］ YANG X S.Bat algorithm for multiobjective optimization［J］.Int J Bio－Inspired Computation，2011，3（5）：267－274.

［3］ YANG X S，GANDOMI A H.Bat algorithm：A novel approach for global engineering optimization［J］.Engineering Computation，2012，29（5）：267－289.

［4］ FISTER J I，F(xiàn)ISTER D，YANG X S.A hybrid bat algorithm［J］.Elektrotehniski Vestnik，2013，80（112）：1－7.

［5］ WANG G G，GUO L H.A novel hybrid bat algorithm with harmony search for global numerical optimization［J］.Journal of Applied Mathematics，2013，65（20）：1－21.

［6］ 賀興時，丁文靜，楊新社.基于模擬退火高斯擾動的蝙蝠優(yōu)化算法［J］.計算機應用研究，2014，31（2）：392－397.

HE Xingshi，DING Wenjing，YANG Xinshe.Bat algorithm based on simulated annealing and gaussian perturbations［J］.Application Research of Computers，2014，31（2）：392－397.

［7］ LIU Y，LIN G G，YAO X.Evolutionary programming made faster［J］.IEEE Transactons on Evolutionary Computation，1999，3（2）：82－102.

［8］ FARITHA B A，CHANDRASEKAR C.An optimized approach of modified bat algorithm to record deduplication［J］.International Journal of Computer Applications，2012，62（1）：10－15.

［9］ 王波.基于自適應t分布混合變異的人工魚群算法［J］.計算機工程與科學，2013，35（4）：120－124.

WANG Bo.Artificial fish－school algorithm based on adaptive t distribution mixed mutation［J］.Computer Engineering＆Science.2013，35（4）：120－124.

［10］ 盛孟龍，賀興時，王慧敏.一種改進的自適應變異蝙蝠算法［J］.計算機技術與發(fā)展，2014，24（10）：131－135.

SHENG Menglong，HE Xingshi，WANG Huimin.An improved algorithm for adaptive mutation bat［J］.Computer Technology and Development，2014，24（10）：131－135.

［11］ 劉佳，劉麗娜，李靖，等.基于模擬退火算法的人工魚群優(yōu)化研究［J］.計算機仿真，2011，28（10）：185－198.

LIU Jia，LIU Lina，LI Jing，et al.Research of improved artificial fish swarm algorithm based on simulated annealing algorithm［J］.Computer Simulation，2011，28（10）：185－198.

［12］ UI KABIR Md Was，MOHAMMAD S A.Bat algorithm with self－adaptive mutation：A comparative study on numerical optimization problems［J］.International Journal of Computer Applications，2014，100（10）：7－13.

編輯：校對：田 莉

Bat algorithm based on t distribution mutation

CHANG Qing，HE Xingshi

（School of Science，Xi′an Polytechnic University，Xi′an 710048，China）

In order to improve the performance of algorithm，a Bat algorithm based on t distribution mutation（TMBA）is presented.This improved algorithm executes the Gauss mutation on the excellent bat and executes the adaptivet distribution mutation on the nonexcellent bat.The proposed algorithm shows good exploitative properties at the early evolution and more explorative at later evolution process.It uses BA，ABA and TMBA to carry out numerical experiments for 6test benchmarks.The simulation results show that the proposed TMBA is superior to BA and ABA.

Bat algorithm；t distribution mutation；Gauss mutation

TP 18；TP 301.6

A

1674－649X（2015）05－0647－07

10.13338／j.issn.1674－649x.2015.05.023

2015－01－22

陜西省自然科學基礎研究計劃項目（2014JM1006，2014KRM28－01）；陜西省教育廳專項科研計劃項目（14JK1282）

賀興時（1960—），男，陜西省富平縣人，西安工程大學教授，研究方向為智能優(yōu)化算法、數(shù)理統(tǒng)計、數(shù)據(jù)挖掘等.E－mail：xingshi－h(huán)e＠163.com