陳 瑤，陳 思

1.西京學(xué)院 理學(xué)院，西安710123

2.西北工業(yè)大學(xué) 理學(xué)院，西安710072

隨著計(jì)算智能[1]科學(xué)的發(fā)展，啟發(fā)式算法得到了更深入的研究。啟發(fā)式算法包括傳統(tǒng)啟發(fā)式算法和元啟發(fā)式算法兩個(gè)大類。常見(jiàn)的傳統(tǒng)啟發(fā)式算法有構(gòu)造型方法、局部搜索算法、松弛方法、解空間縮減算法等。在搜索過(guò)程中提出一些要求，然后按照這些要求實(shí)現(xiàn)的啟發(fā)式算法即為元啟發(fā)式算法。因此，元啟發(fā)式算法實(shí)質(zhì)上是啟發(fā)式算法的改進(jìn)，它是隨機(jī)算法與局部搜索算法相結(jié)合的產(chǎn)物。元啟發(fā)式算法的尋優(yōu)過(guò)程是一個(gè)求解迭代的過(guò)程，在這個(gè)過(guò)程中，學(xué)習(xí)策略被用來(lái)獲取和掌握信息，進(jìn)而有效地發(fā)現(xiàn)近似最優(yōu)解。元啟發(fā)式策略的特點(diǎn)在于它屬于通用的啟發(fā)式策略范疇，不需要借助于被求解問(wèn)題的特有條件就能找到最優(yōu)解，已被廣泛應(yīng)用到了各類實(shí)際優(yōu)化問(wèn)題中。大多數(shù)元啟發(fā)式算法從自然界的一些現(xiàn)象中獲取靈感，包括動(dòng)物、植物、自然現(xiàn)象和規(guī)律等。因此，探索元啟發(fā)式算法的本質(zhì)就是如何有效模仿自然界中的最佳特征，并設(shè)計(jì)有效的數(shù)學(xué)運(yùn)算符號(hào)來(lái)表達(dá)這些特征。著名的元啟發(fā)式算法有：遺傳算法[2]（Genetic Algorithm，GA），它是根據(jù)達(dá)爾文的自然選擇理論對(duì)生物進(jìn)化方式進(jìn)行抽象后得到的算法；通過(guò)概括生物進(jìn)化和自然選擇，研究者提出了差分進(jìn)化算法[3]（Differential Evolution Algorithm，DE）；和聲搜索算法[4]（Harmony Search Algorithm，HS）、黑洞優(yōu)化算法[5]（Black-Hole Optimization Algorithm，BH）、小世界優(yōu)化算法[6]（Small-World Optimization Algorithm，SWOA）、水循環(huán)優(yōu)化算法[7]（Water Cycle Algorithm，WCA）等是對(duì)自然現(xiàn)象和自然規(guī)律的模擬；人工蜂群算法[8]（Artificial Bee Colony Algorithm，ABC）、螢火蟲(chóng)算法[9]（Firefly Algorithm，F(xiàn)A）、細(xì)菌覓食算法[10]（Bacterial Foraging Optimization，BFO）、布谷鳥(niǎo)搜索算法[11]（Cuckoo Search Algorithm，CS）、花授粉算法[12]（Flower Pollination Algorithm，F(xiàn)PA）等是模擬大自然中生物的群體搜索、協(xié)作行為，該類群智能優(yōu)化算法能夠?qū)崿F(xiàn)單個(gè)個(gè)體無(wú)法實(shí)現(xiàn)的、基于群體的智能搜索行為，能夠通過(guò)特有的群體協(xié)作、信息交流以及社會(huì)智能等現(xiàn)象達(dá)到搜索最優(yōu)解的目的。

本文研究的蝙蝠算法[13]（Bat Algorithm，BA），是由英國(guó)學(xué)者Yang于2010年提出的一類基于群體智能的元啟發(fā)式優(yōu)化算法。BA 算法自提出以來(lái)，已被廣泛成功地應(yīng)用于各類復(fù)雜的優(yōu)化問(wèn)題中。例如，Chen 等人將改進(jìn)后的BA算法應(yīng)用于多閾值圖像分割問(wèn)題[14]；Dai等人將BA算法應(yīng)用于優(yōu)化反向傳播神經(jīng)網(wǎng)絡(luò)模型的無(wú)線網(wǎng)絡(luò)流量預(yù)測(cè)[15]；Li 等人將BA 算法應(yīng)用于人工勢(shì)場(chǎng)的機(jī)器人路徑規(guī)劃[16]；BA 算法還被應(yīng)用于各類其他系統(tǒng)控制型問(wèn)題，如機(jī)組頻率控制[17]、發(fā)動(dòng)機(jī)空燃比控制[18]等。由于元啟發(fā)式算法本身的特性，決定了這類算法的效率和性能主要取決于探索與開(kāi)發(fā)之間的平衡。其中，探索是指在全局范圍內(nèi)搜索最優(yōu)值，而開(kāi)發(fā)則是在當(dāng)前最佳解決方案附近進(jìn)行更細(xì)致的本地搜索。有研究指出，需要在這兩個(gè)組成部分之間保持良好的平衡才能更好地助力算法實(shí)現(xiàn)全局最優(yōu)。BA 算法也不例外，如何保證蝙蝠個(gè)體在尋優(yōu)過(guò)程中保持良好的平衡性，避免陷入局部最優(yōu)解，仍是眾多學(xué)者研究的熱點(diǎn)問(wèn)題。近年來(lái)，已經(jīng)出現(xiàn)了不少關(guān)于BA算法的改進(jìn)型研究，算法性能得到了提升。通過(guò)對(duì)這些改進(jìn)算法的研究學(xué)習(xí)，對(duì)BA算法的改進(jìn)方式可簡(jiǎn)要?dú)w為以下幾類：（1）借鑒融合其他群智能算法的改進(jìn)思想[19]，與其他算法進(jìn)行有機(jī)結(jié)合，例如將BA算法與差分進(jìn)化算法、粒子濾波算法相結(jié)合[20-21]；（2）與局部尋優(yōu)策略進(jìn)行有機(jī)結(jié)合，優(yōu)化搜索方式，例如基于分組進(jìn)化和混合尋優(yōu)策略改進(jìn)BA算法[22]，將Sobol 序列和間歇Lévy 跳躍機(jī)制[23]引入速度和位置更新過(guò)程中；（3）與各種映射特征有機(jī)結(jié)合，例如結(jié)合非線性系統(tǒng)中的混沌映射[24]對(duì)BA算法的優(yōu)化效率進(jìn)行改善。除此以外，還有從其他方面對(duì)基本BA算法進(jìn)行性能提升，例如有學(xué)者提出了離散的BA算法[25]。

盡管這些改進(jìn)BA 算法從各個(gè)角度出發(fā)，提出了各類策略對(duì)基本BA算法進(jìn)行了改進(jìn)，但改進(jìn)算法中蝙蝠個(gè)體的進(jìn)化方式仍較為單一，在高維的復(fù)雜優(yōu)化問(wèn)題中仍然難以準(zhǔn)確收斂到理論最優(yōu)，搜索能力較弱。針對(duì)這些問(wèn)題，本文提出基于自適應(yīng)多普勒學(xué)習(xí)策略及動(dòng)態(tài)鄰域的改進(jìn)BA算法。一方面，引入自適應(yīng)多普勒學(xué)習(xí)策略使BA算法更符合蝙蝠個(gè)體獵捕行為的自然規(guī)律。在實(shí)際的獵捕過(guò)程中蝙蝠個(gè)體是通過(guò)回聲定位系統(tǒng)對(duì)獵物進(jìn)行準(zhǔn)確定位，而基本BA算法實(shí)質(zhì)上是對(duì)獵捕行為的簡(jiǎn)化抽象，并未考慮回聲定位系統(tǒng)中存在的多普勒效應(yīng)，本文對(duì)蝙蝠個(gè)體的頻率進(jìn)行自適應(yīng)多普勒補(bǔ)償，進(jìn)一步模擬回聲定位系統(tǒng)。另一方面，將動(dòng)態(tài)鄰域策略與BA算法有機(jī)結(jié)合，增加蝙蝠個(gè)體尋優(yōu)結(jié)構(gòu)的多樣性，改善算法易陷入局部最優(yōu)的不足。這樣的雙重策略強(qiáng)化了算法在搜索前期執(zhí)行全局范圍的探索，在尋優(yōu)后期進(jìn)行局部的細(xì)致開(kāi)發(fā)。從大量對(duì)比實(shí)驗(yàn)結(jié)果中發(fā)現(xiàn)，改進(jìn)算法能夠有效地平衡算法的探索和開(kāi)發(fā)能力。

1 基本BA算法

蝙蝠算法是在理想狀態(tài)下，模擬蝙蝠群體在夜間捕食的過(guò)程，用數(shù)學(xué)的表達(dá)方法抽象了獵捕過(guò)程的回聲定位系統(tǒng)，簡(jiǎn)化了蝙蝠個(gè)體在捕食飛行中發(fā)出聲波的響度和脈沖發(fā)射率的變化，接收頻率、速度和位置信息用以搜尋最優(yōu)解。蝙蝠群體發(fā)現(xiàn)獵物并避開(kāi)障礙物的捕食過(guò)程與尋找全局最優(yōu)解的情況相似，基于上述原理，英國(guó)學(xué)者Yang研究、設(shè)計(jì)了BA算法，其基本步驟可概述如下。

步驟1初始化基本參數(shù)，蝙蝠種群的大小N，脈沖率ri，響度Ai，最大迭代次數(shù)iter，響度的衰減因子α，脈沖率的增大因子γ,脈沖頻率fi及頻率的范圍[fmin,fmax]。

步驟2初始化蝙蝠個(gè)體的位置信息xi，速度信息vi，其中x*代表迭代過(guò)程中搜尋到的最優(yōu)解。

步驟3通過(guò)以下迭代公式更新脈沖頻率fi、蝙蝠的位置信息xi和速度信息vi，進(jìn)行隨機(jī)飛行搜索，具體的迭代公式如下：

其中，β∈[0,1] 。

步驟4產(chǎn)生隨機(jī)數(shù)rand1，若隨機(jī)數(shù)則圍繞最優(yōu)解x*的鄰域，通過(guò)下式進(jìn)行局部搜索，產(chǎn)生新解：

其中，rand1∈[0,1] 服從均勻分布，ε∈[－1,1] 為隨機(jī)向量，At是蝙蝠個(gè)體的平均響度。

步驟5產(chǎn)生隨機(jī)數(shù)rand2，若隨機(jī)數(shù)rand2＜Ai且f(xnew)＜f(x*)，則接受新解，此時(shí)蝙蝠個(gè)體得到改進(jìn)，按照如下公式更新脈沖頻度ri和響度Ai：

其中，0＜α ＜1，γ ＞0，二者均為常數(shù)。通過(guò)分析這兩個(gè)更新公式可知，在迭代過(guò)程中當(dāng)蝙蝠個(gè)體逼近獵物目標(biāo)時(shí)，響度Ai逐漸減小，這使得蝙蝠個(gè)體不易被獵物發(fā)現(xiàn)，同時(shí)脈沖發(fā)射率反而逐漸增大，使得蝙蝠個(gè)體發(fā)出愈加急促的脈沖信號(hào)，迅速確定獵物的位置。

步驟6通過(guò)函數(shù)適應(yīng)度值排序更新蝙蝠個(gè)體的優(yōu)選解集和最優(yōu)位置。

步驟7重復(fù)操作步驟3～步驟6，直到符合結(jié)束條件時(shí)輸出全局最優(yōu)，尋優(yōu)結(jié)束。

2 改進(jìn)BA算法

2.1 自適應(yīng)多普勒策略

多普勒效應(yīng)是由澳大利亞物理學(xué)家及數(shù)學(xué)家Doppler提出的，該理論中定義能夠發(fā)出聲波的目標(biāo)為聲源，能夠接收聲波的目標(biāo)為觀測(cè)者。多普勒效應(yīng)的主要內(nèi)容為：當(dāng)聲源與觀測(cè)者之間存在相對(duì)運(yùn)動(dòng)時(shí)，觀測(cè)者接收到的頻率會(huì)不同于聲源的原始發(fā)射頻率。具體來(lái)說(shuō)，當(dāng)聲源向觀測(cè)者移動(dòng)，接近觀測(cè)者時(shí)接收頻率變高，遠(yuǎn)離觀測(cè)者接收頻率變低；相同地，當(dāng)觀測(cè)者向聲源移動(dòng)時(shí)也能得到同樣的結(jié)論。多普勒效應(yīng)產(chǎn)生的原理是當(dāng)聲源完成一次全振動(dòng)就會(huì)向外發(fā)出一個(gè)波長(zhǎng)的波，聲源的頻率是單位時(shí)間內(nèi)聲源發(fā)出的完全波的個(gè)數(shù)，而觀測(cè)者聽(tīng)到的聲音的音調(diào)，是由觀測(cè)者接收到的頻率決定的。當(dāng)聲源和觀測(cè)者之間存在相對(duì)運(yùn)動(dòng)時(shí)，觀測(cè)者接收到的頻率就會(huì)發(fā)生改變。當(dāng)觀測(cè)者靠近聲源，在單位時(shí)間內(nèi)，觀測(cè)者接收到的完全波的個(gè)數(shù)增多，接收到的頻率增大。當(dāng)觀測(cè)者遠(yuǎn)離聲源，觀測(cè)者在單位時(shí)間內(nèi)接收到的完全波個(gè)數(shù)減少，接收頻率減小。

在實(shí)際捕獵活動(dòng)中，蝙蝠個(gè)體和被獵捕的對(duì)象之間存在著相對(duì)運(yùn)動(dòng)，即存在多普勒效應(yīng)。然而，基本BA算法是在理想條件下簡(jiǎn)化了蝙蝠捕獵時(shí)的回聲定位過(guò)程，頻率f的取值被簡(jiǎn)化地設(shè)置為一個(gè)區(qū)間內(nèi)的隨機(jī)值，并未考慮實(shí)際存在的多普勒效應(yīng)，這與蝙蝠實(shí)際捕獵活動(dòng)存在一定差異，使得算法在一定程度上減弱了蝙蝠個(gè)體的尋優(yōu)能力。為了接近實(shí)際捕獵過(guò)程，提升算法尋優(yōu)性能，本文對(duì)頻率參數(shù)進(jìn)行自適應(yīng)多普勒策略補(bǔ)償，數(shù)學(xué)表達(dá)式為：

在捕獵過(guò)程中，蝙蝠個(gè)體是觀測(cè)者，獵物為聲源，改進(jìn)策略對(duì)頻率進(jìn)行自適應(yīng)調(diào)整的原理在于：如果意味著相比于前一時(shí)刻，蝙蝠個(gè)體遠(yuǎn)離了獵物，根據(jù)自適應(yīng)的頻率公式，蝙蝠接收到的頻率變低，飛行速度隨之變緩，蝙蝠個(gè)體在獵物附近展開(kāi)細(xì)致搜索；如果意味著前后時(shí)刻蝙蝠個(gè)體和獵物之間的距離沒(méi)有發(fā)生變化，根據(jù)改進(jìn)的頻率公式，此時(shí)頻率保持當(dāng)前值繼續(xù)搜索；如果意味著相比于前一時(shí)刻，蝙蝠個(gè)體接近了獵物，根據(jù)頻率公式，蝙蝠接收到的頻率變高，加速飛向獵物，完成獵捕，即找到最優(yōu)解。通過(guò)分析頻率參數(shù)的調(diào)整公式，不難發(fā)現(xiàn)，這一改進(jìn)策略通過(guò)實(shí)時(shí)地調(diào)整頻率進(jìn)而控制蝙蝠個(gè)體的飛行速度。具體來(lái)說(shuō)，當(dāng)蝙蝠個(gè)體遠(yuǎn)離獵物時(shí)，根據(jù)多普勒補(bǔ)償策略降低頻率，由式（2）可得：減小的頻率使得該公式中的位置偏差減小，進(jìn)而使得下一次迭代時(shí)的飛行速度降低，有利于蝙蝠個(gè)體圍繞在獵物附近開(kāi)始減速飛行搜索；同樣地，當(dāng)蝙蝠個(gè)體靠近獵物時(shí)，根據(jù)多普勒補(bǔ)償策略加大頻率取值，位置偏差增大，使得下一次迭代的速度增加，加速向獵物靠近。

另外，頻率參數(shù)和蝙蝠個(gè)體的速度信息共同作用并影響了蝙蝠在搜索空間中新產(chǎn)生的位置信息。根據(jù)多普勒效應(yīng)基本原理，聲源和觀察者之間產(chǎn)生相對(duì)運(yùn)動(dòng)的現(xiàn)象，頻率會(huì)隨之發(fā)生變化。本文的這一改進(jìn)策略正是緊扣該原理，以兩次迭代中蝙蝠與獵物間的距離在前后時(shí)刻的相對(duì)變化為判斷準(zhǔn)則，能夠準(zhǔn)確反映蝙蝠與獵物間的位置變化，對(duì)頻率參數(shù)進(jìn)行自適應(yīng)調(diào)整。當(dāng)即蝙蝠個(gè)體遠(yuǎn)離獵物時(shí)，通過(guò)自適應(yīng)補(bǔ)償策略使得蝙蝠個(gè)體獲得更低的頻率參數(shù)，更低的頻率參數(shù)作用于速度更新公式對(duì)蝙蝠的飛行速度進(jìn)行控制，產(chǎn)生模長(zhǎng)更小的速度，新的速度進(jìn)而作用于位置更新公式使蝙蝠獲得模長(zhǎng)更小的位置信息。這時(shí)蝙蝠個(gè)體相對(duì)于前一時(shí)刻會(huì)減速并圍繞在獵物周圍飛行，也就是說(shuō)自適應(yīng)多普勒補(bǔ)償策略指導(dǎo)了新的位置信息的準(zhǔn)確性。相似地，當(dāng)自適應(yīng)多普勒補(bǔ)償策略會(huì)助力蝙蝠個(gè)體加速向獵物接近。該改進(jìn)策略正是以此方式影響蝙蝠個(gè)體在整個(gè)搜索空間中的位置，進(jìn)一步模擬蝙蝠在捕食中發(fā)生的自然行為，彌補(bǔ)了基本BA 算法中被忽略卻實(shí)際存在的多普勒效應(yīng)，對(duì)新解產(chǎn)生準(zhǔn)確的指導(dǎo)性作用，使蝙蝠個(gè)體產(chǎn)生更接近最優(yōu)位置的新解，從而快速定位到全局最優(yōu)區(qū)域，提高算法的全局探索能力。

2.2 動(dòng)態(tài)鄰域策略

從BA 算法運(yùn)行過(guò)程來(lái)看，在算法初始階段隨機(jī)化蝙蝠個(gè)體位置后，蝙蝠隨機(jī)分散到各個(gè)區(qū)域，聚集度很低。在經(jīng)歷一系列迭代過(guò)程后，隨著迭代次數(shù)增加，蝙蝠個(gè)體開(kāi)始向某一個(gè)或者多個(gè)位置聚集，聚集度增大，算法趨于收斂。如果在這個(gè)過(guò)程中，有蝙蝠個(gè)體在經(jīng)歷很長(zhǎng)時(shí)間的迭代過(guò)程后仍然沒(méi)有搜索到最優(yōu)解集，那么這樣的個(gè)體很可能就陷入了局部極值點(diǎn)無(wú)法跳出，無(wú)法繼續(xù)進(jìn)行搜索，這時(shí)就需要變異策略來(lái)引導(dǎo)這樣的個(gè)體跳出局部極值點(diǎn)，擴(kuò)大搜索范圍，以期進(jìn)行更大范圍的全局搜索行為，從而進(jìn)入最優(yōu)解的鄰域。因此，本文提出動(dòng)態(tài)鄰域的變異策略，用以引導(dǎo)陷入局部極值的蝙蝠個(gè)體擺脫極值，加快收斂速度。

根據(jù)蝙蝠個(gè)體的空間位置，定義優(yōu)選解集。優(yōu)選解集的蝙蝠個(gè)體是通過(guò)目標(biāo)測(cè)試函數(shù)的適應(yīng)度值來(lái)確定的，即在已經(jīng)進(jìn)行的迭代過(guò)程找到的解中，適應(yīng)度值最小的解對(duì)應(yīng)的個(gè)體標(biāo)記為優(yōu)選解集。不難理解優(yōu)選解集中的蝙蝠個(gè)體比非優(yōu)選解集中的個(gè)體更接近Pareto前沿。動(dòng)態(tài)鄰域變異策略的中心思想是：在迭代次數(shù)進(jìn)行到1/3 后，對(duì)還沒(méi)進(jìn)入到優(yōu)選解集的蝙蝠個(gè)體根據(jù)優(yōu)選解集中的個(gè)體計(jì)算出每個(gè)自變量的均值和標(biāo)準(zhǔn)差，用以動(dòng)態(tài)調(diào)整新鄰域的取值范圍，對(duì)未進(jìn)入優(yōu)選解集的個(gè)體實(shí)施變異策略，使這些個(gè)體進(jìn)入新的鄰域進(jìn)行搜索。判斷蝙蝠個(gè)體i是否進(jìn)入過(guò)優(yōu)選解集的依據(jù)是：首先根據(jù)適應(yīng)度值的計(jì)算找到該個(gè)體的最優(yōu)位置，然后判斷該最優(yōu)位置是否在優(yōu)選解集中解的可接受鄰域內(nèi)，如果在該鄰域內(nèi)，則不用進(jìn)行位置信息的變異操作；如果不在，則用下面的式（8）、（9）進(jìn)行變異操作。

設(shè)第i個(gè)蝙蝠個(gè)體的自變量的取值范圍是在第t次迭代時(shí)最優(yōu)解集的蝙蝠個(gè)體自變量的均值是，標(biāo)準(zhǔn)差是σi(t)，變異算子作用于蝙蝠個(gè)體的位置信息，變異后的位置信息用數(shù)學(xué)公式表示為：

通過(guò)分析這兩部分改進(jìn)策略，不難發(fā)現(xiàn)：經(jīng)過(guò)自適應(yīng)多普勒補(bǔ)償策略改進(jìn)的頻率參數(shù)控制了蝙蝠的飛行速度，進(jìn)而影響了新解的產(chǎn)生，正是以此方式影響蝙蝠個(gè)體在整個(gè)搜索空間中的位置，彌補(bǔ)了標(biāo)準(zhǔn)蝙蝠算法中被忽略卻實(shí)際存在的多普勒效應(yīng)，對(duì)新解產(chǎn)生準(zhǔn)確的指導(dǎo)性作用，使算法快速定位到全局最優(yōu)區(qū)域，提高全局探索能力。同時(shí)，動(dòng)態(tài)鄰域變異機(jī)制增加了解的多樣性，并使得算法在局部搜索環(huán)節(jié)獲得了更小范圍的搜索空間，有益于加強(qiáng)算法的局部搜索能力。

2.3 改進(jìn)BA算法的操作步驟

通過(guò)上述自適應(yīng)多普勒策略及動(dòng)態(tài)鄰域策略改進(jìn)后的SDDNBA算法，操作流程可表示為以下步驟：

步驟1初始化種群及基本參數(shù)設(shè)置，種群規(guī)模N=20，最大迭代次數(shù)iter=500，脈沖率響度并初始化蝙蝠個(gè)體的位置信息及速度信息。

步驟2按照基本BA 算法的更新公式迭代產(chǎn)生位置信息，并根據(jù)適應(yīng)度值排序生成優(yōu)選解集，確定全局最優(yōu)。

步驟3根據(jù)改進(jìn)后的更新公式（將原始隨機(jī)頻率更換為自適應(yīng)多普勒策略的改進(jìn)方式）更新蝙蝠個(gè)體的位置和速度，迭代尋優(yōu)。

步驟4在迭代次數(shù)進(jìn)行到1/3 時(shí)，運(yùn)用動(dòng)態(tài)鄰域變異策略，對(duì)還沒(méi)進(jìn)入優(yōu)選解集的蝙蝠個(gè)體進(jìn)行變異操作。

步驟5產(chǎn)生隨機(jī)數(shù)rand1，若隨機(jī)數(shù)則圍繞最優(yōu)解x*的鄰域，通過(guò)式（4）進(jìn)行局部搜索產(chǎn)生新解。

步驟6產(chǎn)生隨機(jī)數(shù)rand2，若隨機(jī)數(shù)rand2＜Ai且f(xnew)＜f(x*)，則接受新解，此時(shí)蝙蝠個(gè)體得到改進(jìn)，更新脈沖率ri和響度Ai。

步驟7通過(guò)函數(shù)適應(yīng)度值排序更新蝙蝠個(gè)體的優(yōu)選解集和最優(yōu)位置。

步驟8重復(fù)操作步驟3～步驟7，直到符合結(jié)束條件，即達(dá)到最大迭代次數(shù)或?qū)?yōu)精度達(dá)到設(shè)定的tolerance=10－7，然后輸出全局最優(yōu)，尋優(yōu)結(jié)束。

3 SDDNBA算法的理論性分析

3.1 穩(wěn)定收斂性分析

對(duì)本文提出的SDDNBA算法進(jìn)行收斂性和穩(wěn)定性的分析。根據(jù)前文的分析，SDDNBA算法的迭代公式為：

通過(guò)遞歸整理，得到位置信息的二階差分方程為：

其中，x*·f*為系統(tǒng)的外部輸入，不影響整個(gè)線性時(shí)變系統(tǒng)的穩(wěn)定收斂性。

本節(jié)將從控制系統(tǒng)的相關(guān)理論出發(fā)，解析證明算法穩(wěn)定收斂時(shí)所需參數(shù)設(shè)置條件。算法進(jìn)化過(guò)程可視為一個(gè)離散的系統(tǒng)，依據(jù)Jury 穩(wěn)定判據(jù)，設(shè)n階離散系統(tǒng)的特征方程為：

利用其系數(shù)構(gòu)造(2n－3)(n ＋1)列Jury矩陣，有：

離散線性系統(tǒng)的穩(wěn)定性通常是以特征根是否位于z平面的單位圓內(nèi)來(lái)判斷的，因此上述離散系統(tǒng)穩(wěn)定的充要條件是：

定理1SDDNBA算法穩(wěn)定收斂的充要條件是：

證明對(duì)式（11）位置信息的二階差分方程等號(hào)兩端同時(shí)取數(shù)學(xué)期望后得：

其中，K=E(x*·f*)。

特征方程為：

則其特征根為：

易知其通解可表示為：

其中，C1、C2為系數(shù)，C為常數(shù)項(xiàng)。

對(duì)于SDDNBA 算法的二階線性定常離散系統(tǒng)，即當(dāng)n=2 時(shí)，判斷其特征根的模是否在單位圓范圍內(nèi)，依據(jù)Jury判據(jù)中離散系統(tǒng)穩(wěn)定的充要條件對(duì)SDDNBA算法對(duì)應(yīng)的條件進(jìn)行判斷，則該系統(tǒng)穩(wěn)定的充要條件是：

顯然，第三條是滿足的。

因此，可得SDDNBA 算法對(duì)應(yīng)的離散系統(tǒng)穩(wěn)定收斂的充要條件為：

經(jīng)過(guò)簡(jiǎn)化可得該系統(tǒng)穩(wěn)定收斂的充要條件為：0＜f*＜3。

3.2 運(yùn)算復(fù)雜性分析

下面對(duì)本文提出的SDDNBA 算法與基本BA 算法進(jìn)行運(yùn)算復(fù)雜度的對(duì)比分析。

設(shè)算法的最大迭代次數(shù)為T(mén)max，算法終止條件閾值為α（本文設(shè)定尋優(yōu)精度達(dá)到tolerance=10－7），如果在第t次迭代中尋優(yōu)精度達(dá)到α，則停止搜索，否則繼續(xù)進(jìn)行尋優(yōu)迭代，記tend為終止迭代次數(shù)?；綛A 算法和SDDNBA算法在每一次的迭代過(guò)程中蝙蝠個(gè)體的數(shù)量是等量的，記為N；每個(gè)蝙蝠個(gè)體進(jìn)行一次迭代所需要的時(shí)間記為t*；基本BA算法和SDDNBA算法的最終迭代次數(shù)分別記為t1、t2，則其時(shí)間復(fù)雜度分別為O(t1tend)和O(t2tend)，由此可得兩種算法運(yùn)行時(shí)間的差異主要由各自的迭代次數(shù)所決定?；綛A算法的頻率參數(shù)在[0,1]范圍內(nèi)隨機(jī)取值，致使蝙蝠個(gè)體的位置信息具有很強(qiáng)的隨機(jī)性，這在算法前期不利于快速搜索整個(gè)解空間，在算法后期也不利于局部精確搜索。而SDDNBA算法受自適應(yīng)多普勒補(bǔ)償策略和變異引導(dǎo)機(jī)制的作用，在全局搜索中有助于蝙蝠個(gè)體的新位置快速向最優(yōu)解靠近，在后期局部搜索時(shí)引導(dǎo)蝙蝠個(gè)體縮小范圍，在相同迭代次數(shù)下，SDDNBA算法會(huì)比基本BA算法先滿足終止迭代條件，提前終止迭代，有t1＞t2，因此SDDNBA算法的運(yùn)算復(fù)雜度低于基本BA算法。

綜上所述，SDDNBA 算法通過(guò)自適應(yīng)多普勒補(bǔ)償策略自適應(yīng)地調(diào)整飛行速度，并影響產(chǎn)生更靠近最佳位置且適應(yīng)度值更優(yōu)的新解，這是在算法前期指導(dǎo)性能更佳的全局搜索；基于動(dòng)態(tài)鄰域的引導(dǎo)變異機(jī)制使得算法在迭代的適當(dāng)時(shí)期，引導(dǎo)尋優(yōu)方向不佳的蝙蝠個(gè)體進(jìn)行變異，增強(qiáng)對(duì)最優(yōu)值附近的局部搜索能力。這兩部分策略協(xié)同作用，提高了算法的收斂速度和收斂精度。下面，將通過(guò)數(shù)值對(duì)比實(shí)驗(yàn)進(jìn)一步驗(yàn)證改進(jìn)算法的優(yōu)越性。

4 對(duì)比實(shí)驗(yàn)及分析

由上一節(jié)的分析，SDDNBA 算法在上述參數(shù)設(shè)置下是穩(wěn)定收斂的，接下來(lái)對(duì)算法進(jìn)行一系列仿真對(duì)比實(shí)驗(yàn)，以測(cè)試本文提出的SDDNBA 算法的性能。其中包括10 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，并且為了檢驗(yàn)SDDNBA 算法解決實(shí)際優(yōu)化問(wèn)題的能力，將其應(yīng)用于經(jīng)典的螺旋壓縮彈簧設(shè)計(jì)問(wèn)題，用以進(jìn)一步驗(yàn)證其求解實(shí)際問(wèn)題的能力。

4.1 基于標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真測(cè)試

本文選取10 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，其中包括單峰和多峰函數(shù)，測(cè)試函數(shù)大部分存在很多局部極值點(diǎn)，想要找到理論的最優(yōu)值有一定難度，因此能很好地考察改進(jìn)算法的尋優(yōu)性能，具體表達(dá)式如表1所示。所有仿真實(shí)驗(yàn)均在Intel Core i5-1035G1 CPU＠1.00 GHz 1.19 GHz，16 GB內(nèi)存的PC Windows 10機(jī)器上運(yùn)用Matlab 2016a進(jìn)行測(cè)試。為了對(duì)比驗(yàn)證SDDNBA 算法的有效性，除了基本BA 算法以外，還與文獻(xiàn)[26]提出的NDBA 算法進(jìn)行對(duì)比實(shí)驗(yàn)。為了實(shí)驗(yàn)的可比性與公正性，這3個(gè)關(guān)于BA 算法的基本參數(shù)設(shè)置保持一致，最大迭代次數(shù)iter=500,種群規(guī)模N=20,r=0.1,A=0.9。

表1 測(cè)試函數(shù)Table 1 Test benchmarks

這3 個(gè)對(duì)比算法對(duì)每個(gè)目標(biāo)函數(shù)獨(dú)立運(yùn)行測(cè)試30次，盡可能地減小算法初始化對(duì)算法性能的影響。記錄每個(gè)測(cè)試的最優(yōu)值，通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的比較分析來(lái)評(píng)估每種算法的性能。表2 記錄了每個(gè)測(cè)試的全局最小值（Min）、最大值（Max）和平均值（Mean）3 個(gè)指標(biāo)的最優(yōu)取值，實(shí)驗(yàn)中最好的結(jié)果加粗顯示。SDDNBA 算法在除了G6、G5、G7 的最大值指標(biāo)以外的測(cè)試結(jié)果中均取得了最好的結(jié)果，NDBA 算法在G6 中取得了更好的結(jié)果。從這些仿真實(shí)驗(yàn)數(shù)據(jù)中不難看出，SDDNBA 算法的尋優(yōu)性能明顯優(yōu)于NDBA算法和BA算法。

表2 SDDNBA算法與同類型算法的仿真實(shí)驗(yàn)對(duì)比結(jié)果(D=30)Table 2 Comparison results of SDDNBA and same type of algorithms(D=30)

此外，本文給出3種同類型算法在D=30 維時(shí)求解標(biāo)準(zhǔn)測(cè)試函數(shù)迭代過(guò)程中的收斂曲線，如圖1～圖10 所示。在這些收斂曲線圖中，橫軸和縱軸分別表示迭代次數(shù)和適應(yīng)度值，黑色、藍(lán)色和紅色虛線分別表示BA 算法、NDBA 算法和SDDNBA 算法的收斂曲線。可以清楚地看到，除測(cè)試函數(shù)G6 以外，SDDNBA 算法的收斂性能均優(yōu)于其他兩種算法。無(wú)論是求解單峰函數(shù)還是多峰函數(shù)，SDDNBA算法的收斂精度更高，從收斂曲線圖中可以看出SDDNBA 算法在測(cè)試函數(shù)G1、G2、G3、G4、G5、G7、G8、G10 中的收斂精度都最高，并且在G1、G2、G7、G9 中當(dāng)?shù)螖?shù)不到150 次時(shí)就已經(jīng)收斂。分析圖2、圖3、圖5、圖8、圖10，由于基本BA 算法的搜索機(jī)制的隨機(jī)性太強(qiáng)，易陷入局部極值，造成尋優(yōu)性能較差，所得解的適應(yīng)度值不佳。

圖1 G1 測(cè)試函數(shù)迭代收斂曲線Fig.1 Iterative convergence curve of G1

圖2 G2 測(cè)試函數(shù)迭代收斂曲線Fig.2 Iterative convergence curve of G2

圖3 G3 測(cè)試函數(shù)迭代收斂曲線Fig.3 Iterative convergence curve of G3

圖4 G4 測(cè)試函數(shù)迭代收斂曲線Fig.4 Iterative convergence curve of G4

圖5 G5 測(cè)試函數(shù)迭代收斂曲線Fig.5 Iterative convergence curve of G5

圖6 G6 測(cè)試函數(shù)迭代收斂曲線Fig.6 Iterative convergence curve of G6

圖7 G7 測(cè)試函數(shù)迭代收斂曲線Fig.7 Iterative convergence curve of G7

圖8 G8 測(cè)試函數(shù)迭代收斂曲線Fig.8 Iterative convergence curve of G8

圖9 G9 測(cè)試函數(shù)迭代收斂曲線Fig.9 Iterative convergence curve of G9

圖10 G10 測(cè)試函數(shù)迭代收斂曲線Fig.10 Iterative convergence curve of G10

通過(guò)這部分低維數(shù)設(shè)置下算法在單峰和多峰測(cè)試函數(shù)上的求解結(jié)果不難看出，SDDNBA 算法在處理維數(shù)較低的數(shù)據(jù)時(shí)具有明顯更佳的尋優(yōu)性能。相比其他兩種算法，在整個(gè)求解過(guò)程中表現(xiàn)出了更好的求解性能，尤其是在尋優(yōu)精度上具有很好的改進(jìn)效果。

為了進(jìn)一步研究SDDNBA算法在高維度復(fù)雜問(wèn)題上的求解性能，本文將其與5種算法進(jìn)行了高維度性能測(cè)試對(duì)比實(shí)驗(yàn)，分別是基本BA算法、NDBA算法、UGBA算法[27]、PSO算法和FPA算法。所有算法的最大迭代次數(shù)均設(shè)置為T(mén)max=500，表3 列出了每種算法的具體參數(shù)設(shè)置。6 種算法針對(duì)G1～G10 這10 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)分別進(jìn)行100 維和500 維的高維度測(cè)試實(shí)驗(yàn)，每種算法在每個(gè)維度下各自獨(dú)立運(yùn)行30 次，通過(guò)計(jì)算出平均最佳值（Mean）、平均終止迭代次數(shù)（iter）這兩個(gè)指標(biāo)考察算法在高維度前提下的尋優(yōu)性能。實(shí)驗(yàn)結(jié)果如表4 和表5所示，其中最佳值加粗標(biāo)記。

表3 相關(guān)參數(shù)設(shè)置Table 3 Related parameters setting

表4 6種算法在100維時(shí)的對(duì)比實(shí)驗(yàn)結(jié)果Table 4 Performance comparison of 6 algorithms with 100 dimensions

表5 6種算法在500維時(shí)的對(duì)比實(shí)驗(yàn)結(jié)果Table 5 Performance comparison of 6 algorithms with 500 dimensions

根據(jù)表4和表5可以看出，本文所提出的SDDNBA算法能夠有效地解決高維問(wèn)題，而其他5種算法的求解精度都隨著維數(shù)的增加而降低。在D=100 維的數(shù)值實(shí)驗(yàn)中，對(duì)于3個(gè)測(cè)試函數(shù)(G6、G9 和G10)UGBA算法的適應(yīng)度值較優(yōu)，但與SDDNBA 算法所得的適應(yīng)度值并沒(méi)有太大區(qū)別。在其余7 個(gè)測(cè)試函數(shù)中，本文提出的SDDNBA 算法均取得了更優(yōu)的結(jié)果。在D=500 維的數(shù)值實(shí)驗(yàn)中，SDDNBA算法獲得了8個(gè)測(cè)試函數(shù)的最佳收斂精度。此外，就迭代次數(shù)而言，SDDNBA算法在不同維度上的所有測(cè)試函數(shù)中均表現(xiàn)更佳。在D=100 維時(shí)，對(duì)于測(cè)試函數(shù)G1 和G7，SDDNBA算法的終止迭代次數(shù)“iter”小于最大迭代次數(shù)“Tmax”的7.2%，而對(duì)于G2、G4、G5、G6 和G8，SDDNBA 算法所需的迭代次數(shù)最大的也不到“Tmax”的40%。在D=500 維時(shí)，對(duì)于測(cè)試函數(shù)G1、G7、G9，SDDNBA算法的終止迭代次數(shù)“iter”小于最大迭代次數(shù)“Tmax”的19.2%，而對(duì)于測(cè)試函數(shù)G2、G4、G5、G6 和G8，SDDNBA 算法所需的迭代次數(shù)最大的也不到“Tmax”的46%。同時(shí)，對(duì)于所有測(cè)試函數(shù)，SDDNBA算法所需的終止迭代次數(shù)都是最少的。

為了進(jìn)一步驗(yàn)證SDDNBA 算法的穩(wěn)定魯棒性，將SDDNBA算法與前文數(shù)值對(duì)比實(shí)驗(yàn)中表現(xiàn)最佳的UGBA算法進(jìn)行了穩(wěn)定魯棒性分析。分別在維數(shù)設(shè)置為100維和500維時(shí)，對(duì)10個(gè)測(cè)試函數(shù)下所需的迭代次數(shù)進(jìn)行了統(tǒng)計(jì)，如圖11 所示，其中橫軸代表10 個(gè)測(cè)試函數(shù)，縱軸代表達(dá)到收斂狀態(tài)時(shí)所需的迭代次數(shù)。從圖中可以清楚地看到，隨著維數(shù)從100 維大幅度增加至500 維，SDDNBA算法所需迭代次數(shù)并未像UGBA算法那樣出現(xiàn)大范圍浮動(dòng)，兩種維數(shù)設(shè)置下SDDNBA 算法達(dá)到收斂所需的迭代次數(shù)幾乎不受維數(shù)變化的影響，進(jìn)而直觀說(shuō)明了SDDNBA算法優(yōu)秀的穩(wěn)定魯棒性。

圖11 SDDNBA和UGBA算法高維度時(shí)收斂迭代次數(shù)對(duì)比Fig.11 Comparison of number of iterations of SDDNBA and UGBA algorithms

綜上所述，通過(guò)大量對(duì)比實(shí)驗(yàn)的數(shù)據(jù)可以得出，隨著維數(shù)設(shè)置的不斷增加，測(cè)試函數(shù)復(fù)雜性隨之加大，但SDDNBA算法幾乎在所有測(cè)試函數(shù)上仍能迅速收斂到最佳值，基本不受數(shù)據(jù)維度變化的影響。隨著維數(shù)的增加，在100 維和500 維時(shí)SDDNBA 算法均顯示出比其他算法更強(qiáng)的收斂能力。這些對(duì)比實(shí)驗(yàn)結(jié)果表明了SDDNBA算法在處理高維復(fù)雜數(shù)據(jù)時(shí)依舊具有顯著的優(yōu)勢(shì)。

4.2 基于螺旋壓縮彈簧優(yōu)化設(shè)計(jì)的應(yīng)用測(cè)試

在本節(jié)中，SDDNBA 算法被應(yīng)用于求解螺旋壓縮彈簧的優(yōu)化設(shè)計(jì)問(wèn)題，進(jìn)一步測(cè)試SDDNBA 算法求解實(shí)際應(yīng)用問(wèn)題的能力。螺旋壓縮彈簧的優(yōu)化設(shè)計(jì)，是以彈簧的質(zhì)量最小為優(yōu)化目標(biāo)，建立平均線圈直徑D(x1)、導(dǎo)線直徑d(x2)和有效線圈數(shù)N(x3)三維設(shè)計(jì)變量，同時(shí)受到最小撓度、剪切應(yīng)力、工作頻率、直徑和其他設(shè)計(jì)變量的約束。壓縮彈簧優(yōu)化設(shè)計(jì)的目標(biāo)函數(shù)數(shù)學(xué)表達(dá)式如下所示：

其中，0.25 ≤x1≤1.3，0.05 ≤x2≤1.3，2 ≤x3≤15。

實(shí)驗(yàn)配置與之前相同，是在Windows 10 操作系統(tǒng)上使用具有16 GB RAM的計(jì)算機(jī)并運(yùn)用Matlab 2016a實(shí)現(xiàn)的。本文將基于SDDNBA算法的壓縮彈簧設(shè)計(jì)方法與其他6 種不同的方法進(jìn)行了比較，這6 種方法分別是基于BA、MBA[28]、GA、PSO、ABFA[29]、WCA 的優(yōu)化設(shè)計(jì)方法。每種算法各自獨(dú)立運(yùn)行30 次，記錄最小化目標(biāo)函數(shù)的結(jié)果，并計(jì)算這些結(jié)果的最優(yōu)值（Best）、平均值（Mean）、最差值（Worst）、標(biāo)準(zhǔn)差（Std）來(lái)考察算法的優(yōu)化性能，實(shí)驗(yàn)結(jié)果如表6所示，其中最佳值加粗標(biāo)記。

表6 不同算法優(yōu)化設(shè)計(jì)的結(jié)果統(tǒng)計(jì)Table 6 Statistical results of different algorithms on optimal design

這部分應(yīng)用是典型的約束優(yōu)化類型的測(cè)試，相比前兩部分?jǐn)?shù)值仿真實(shí)驗(yàn)更具實(shí)際利用價(jià)值。從表6 的不同優(yōu)化算法求解螺旋壓縮彈簧設(shè)計(jì)問(wèn)題的實(shí)驗(yàn)結(jié)果中可以清楚地看到，SDDNBA 算法對(duì)螺旋壓縮彈簧取得了最優(yōu)的設(shè)計(jì)結(jié)果，其目標(biāo)函數(shù)的最優(yōu)值均優(yōu)于BA、GA、PSO、ABFA算法，在優(yōu)化精度方面顯示出明顯的優(yōu)越性。

顯然，本文提出的SDDNBA 算法引入了有利于全局勘探和局部開(kāi)采的操作策略來(lái)改進(jìn)基本算法，優(yōu)化性能更佳。

5 結(jié)論

針對(duì)基本BA 算法在算法后期尋優(yōu)精度低、易陷入局部極值的不足，本文提出了一種基于自適應(yīng)多普勒策略和動(dòng)態(tài)鄰域策略的新型改進(jìn)BA 算法（SDDNBA）。經(jīng)過(guò)10 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的對(duì)比實(shí)驗(yàn)以及螺旋壓縮彈簧優(yōu)化設(shè)計(jì)問(wèn)題的實(shí)際應(yīng)用的雙重實(shí)驗(yàn)，結(jié)果表明SDDNBA 算法優(yōu)于基本BA 算法和對(duì)比實(shí)驗(yàn)中的其他元啟發(fā)式算法。這些對(duì)比結(jié)果清楚地顯示了SDDNBA算法的有效性，以及更高的收斂速度和穩(wěn)定魯棒性。