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

常 青，賀興時(shí)

（西安工程大學(xué)理學(xué)院，陜西西安 710048）

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

常 青，賀興時(shí)

（西安工程大學(xué)理學(xué)院，陜西西安 710048）

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

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

0 引 言

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

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

1 蝙蝠算法和變異策略

1.1 蝙蝠算法

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

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

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

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

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

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

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

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

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

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

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

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

其中，α和γ為常量.

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

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

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

1.2 變異策略

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

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

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

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

2 改進(jìn)的蝙蝠算法

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

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

（b）評價(jià)種群.對當(dāng)前種群中的每個(gè)蝙蝠個(gè)體進(jìn)行評價(jià)，找到當(dāng)前全局最優(yōu)值.

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 基準(zhǔn)測試函數(shù)

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

3.2 結(jié)果與討論

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

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

從表2的結(jié)果可以看出，不管對于單模態(tài)函數(shù)，還是多模態(tài)函數(shù)，低維函數(shù)還是高維函數(shù)，基于t分布變異的TMBA算法在解的質(zhì)量上都明顯高于基本BA算法和自適應(yīng)變異的ABA算法.TMBA算法解的標(biāo)準(zhǔn)差要小于其他兩個(gè)算法解的標(biāo)準(zhǔn)差，可見TMBA算法更具有穩(wěn)定性.雖然，各個(gè)算法在同一基準(zhǔn)函數(shù)下，隨著維數(shù)的增加，解的質(zhì)量有所下降，但這是合理的，因?yàn)榻獾乃阉骺臻g隨著問題維數(shù)的增加呈指數(shù)形式增加.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

蝙蝠算法是一類新型的搜索全局最優(yōu)解的隨機(jī)優(yōu)化技術(shù).本文提出的基于t分布變異的蝙蝠算法，由于引入t分布變異策略增加了種群的多樣性，有利于算法跳出局部最小值的束縛，因此加快蝙蝠算法的收斂速度，提高了解的質(zhì)量.由仿真實(shí)驗(yàn)結(jié)果可以看出，該算法的性能在不同程度上優(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］ 賀興時(shí)，丁文靜，楊新社.基于模擬退火高斯擾動(dòng)的蝙蝠優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，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］ 王波.基于自適應(yīng)t分布混合變異的人工魚群算法［J］.計(jì)算機(jī)工程與科學(xué)，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］ 盛孟龍，賀興時(shí)，王慧敏.一種改進(jìn)的自適應(yīng)變異蝙蝠算法［J］.計(jì)算機(jī)技術(shù)與發(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］.計(jì)算機(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

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目（2014JM1006，2014KRM28－01）；陜西省教育廳專項(xiàng)科研計(jì)劃項(xiàng)目（14JK1282）

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