基于自適應(yīng)多普勒及動態(tài)鄰域的改進(jìn)BA算法

陳 瑤，陳 思

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

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

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

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

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

1 基本BA算法

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

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

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

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

其中，β∈[0,1] 。

步驟4產(chǎn)生隨機(jī)數(shù)rand1，若隨機(jī)數(shù)則圍繞最優(yōu)解x*的鄰域，通過下式進(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ù)。通過分析這兩個(gè)更新公式可知，在迭代過程中當(dāng)蝙蝠個(gè)體逼近獵物目標(biāo)時(shí)，響度Ai逐漸減小，這使得蝙蝠個(gè)體不易被獵物發(fā)現(xiàn)，同時(shí)脈沖發(fā)射率反而逐漸增大，使得蝙蝠個(gè)體發(fā)出愈加急促的脈沖信號，迅速確定獵物的位置。

步驟6通過函數(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)為觀測者。多普勒效應(yīng)的主要內(nèi)容為：當(dāng)聲源與觀測者之間存在相對運(yùn)動時(shí)，觀測者接收到的頻率會不同于聲源的原始發(fā)射頻率。具體來說，當(dāng)聲源向觀測者移動，接近觀測者時(shí)接收頻率變高，遠(yuǎn)離觀測者接收頻率變低；相同地，當(dāng)觀測者向聲源移動時(shí)也能得到同樣的結(jié)論。多普勒效應(yīng)產(chǎn)生的原理是當(dāng)聲源完成一次全振動就會向外發(fā)出一個(gè)波長的波，聲源的頻率是單位時(shí)間內(nèi)聲源發(fā)出的完全波的個(gè)數(shù)，而觀測者聽到的聲音的音調(diào)，是由觀測者接收到的頻率決定的。當(dāng)聲源和觀測者之間存在相對運(yùn)動時(shí)，觀測者接收到的頻率就會發(fā)生改變。當(dāng)觀測者靠近聲源，在單位時(shí)間內(nèi)，觀測者接收到的完全波的個(gè)數(shù)增多，接收到的頻率增大。當(dāng)觀測者遠(yuǎn)離聲源，觀測者在單位時(shí)間內(nèi)接收到的完全波個(gè)數(shù)減少，接收頻率減小。

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

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

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

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

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

根據(jù)蝙蝠個(gè)體的空間位置，定義優(yōu)選解集。優(yōu)選解集的蝙蝠個(gè)體是通過目標(biāo)測試函數(shù)的適應(yīng)度值來確定的，即在已經(jīng)進(jìn)行的迭代過程找到的解中，適應(yīng)度值最小的解對應(yīng)的個(gè)體標(biāo)記為優(yōu)選解集。不難理解優(yōu)選解集中的蝙蝠個(gè)體比非優(yōu)選解集中的個(gè)體更接近Pareto前沿。動態(tài)鄰域變異策略的中心思想是：在迭代次數(shù)進(jìn)行到1/3 后，對還沒進(jìn)入到優(yōu)選解集的蝙蝠個(gè)體根據(jù)優(yōu)選解集中的個(gè)體計(jì)算出每個(gè)自變量的均值和標(biāo)準(zhǔn)差，用以動態(tài)調(diào)整新鄰域的取值范圍，對未進(jìn)入優(yōu)選解集的個(gè)體實(shí)施變異策略，使這些個(gè)體進(jìn)入新的鄰域進(jìn)行搜索。判斷蝙蝠個(gè)體i是否進(jìn)入過優(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é)公式表示為：

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

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

通過上述自適應(yī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)用動態(tài)鄰域變異策略，對還沒進(jìn)入優(yōu)選解集的蝙蝠個(gè)體進(jìn)行變異操作。

步驟5產(chǎn)生隨機(jī)數(shù)rand1，若隨機(jī)數(shù)則圍繞最優(yōu)解x*的鄰域，通過式（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通過函數(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)定收斂性分析

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

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

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

本節(jié)將從控制系統(tǒng)的相關(guān)理論出發(fā)，解析證明算法穩(wěn)定收斂時(shí)所需參數(shù)設(shè)置條件。算法進(jìn)化過程可視為一個(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)來判斷的，因此上述離散系統(tǒng)穩(wěn)定的充要條件是：

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

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

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

特征方程為：

則其特征根為：

易知其通解可表示為：

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

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

顯然，第三條是滿足的。

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

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

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

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

設(shè)算法的最大迭代次數(shù)為Tmax，算法終止條件閾值為α（本文設(shè)定尋優(yōu)精度達(dá)到tolerance=10－7），如果在第t次迭代中尋優(yōu)精度達(dá)到α，則停止搜索，否則繼續(xù)進(jìn)行尋優(yōu)迭代，記tend為終止迭代次數(shù)?；綛A 算法和SDDNBA算法在每一次的迭代過程中蝙蝠個(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算法會比基本BA算法先滿足終止迭代條件，提前終止迭代，有t1＞t2，因此SDDNBA算法的運(yùn)算復(fù)雜度低于基本BA算法。

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

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

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

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

本文選取10 個(gè)標(biāo)準(zhǔn)測試函數(shù)，其中包括單峰和多峰函數(shù)，測試函數(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)行測試。為了對比驗(yàn)證SDDNBA 算法的有效性，除了基本BA 算法以外，還與文獻(xiàn)[26]提出的NDBA 算法進(jìn)行對比實(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 測試函數(shù)Table 1 Test benchmarks

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

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

此外，本文給出3種同類型算法在D=30 維時(shí)求解標(biāo)準(zhǔn)測試函數(shù)迭代過程中的收斂曲線，如圖1～圖10 所示。在這些收斂曲線圖中，橫軸和縱軸分別表示迭代次數(shù)和適應(yīng)度值，黑色、藍(lán)色和紅色虛線分別表示BA 算法、NDBA 算法和SDDNBA 算法的收斂曲線?？梢郧宄乜吹?，除測試函數(shù)G6 以外，SDDNBA 算法的收斂性能均優(yōu)于其他兩種算法。無論是求解單峰函數(shù)還是多峰函數(shù)，SDDNBA算法的收斂精度更高，從收斂曲線圖中可以看出SDDNBA 算法在測試函數(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 測試函數(shù)迭代收斂曲線Fig.1 Iterative convergence curve of G1

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

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

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

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

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

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

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

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

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

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

為了進(jìn)一步研究SDDNBA算法在高維度復(fù)雜問題上的求解性能，本文將其與5種算法進(jìn)行了高維度性能測試對比實(shí)驗(yàn)，分別是基本BA算法、NDBA算法、UGBA算法[27]、PSO算法和FPA算法。所有算法的最大迭代次數(shù)均設(shè)置為Tmax=500，表3 列出了每種算法的具體參數(shù)設(shè)置。6 種算法針對G1～G10 這10 個(gè)標(biāo)準(zhǔn)測試函數(shù)分別進(jìn)行100 維和500 維的高維度測試實(shí)驗(yàn)，每種算法在每個(gè)維度下各自獨(dú)立運(yùn)行30 次，通過計(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í)的對比實(shí)驗(yàn)結(jié)果Table 4 Performance comparison of 6 algorithms with 100 dimensions

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

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

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

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

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

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

在本節(jié)中，SDDNBA 算法被應(yīng)用于求解螺旋壓縮彈簧的優(yōu)化設(shè)計(jì)問題，進(jìn)一步測試SDDNBA 算法求解實(shí)際應(yīng)用問題的能力。螺旋壓縮彈簧的優(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）來考察算法的優(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)化類型的測試，相比前兩部分?jǐn)?shù)值仿真實(shí)驗(yàn)更具實(shí)際利用價(jià)值。從表6 的不同優(yōu)化算法求解螺旋壓縮彈簧設(shè)計(jì)問題的實(shí)驗(yàn)結(jié)果中可以清楚地看到，SDDNBA 算法對螺旋壓縮彈簧取得了最優(yōu)的設(shè)計(jì)結(jié)果，其目標(biāo)函數(shù)的最優(yōu)值均優(yōu)于BA、GA、PSO、ABFA算法，在優(yōu)化精度方面顯示出明顯的優(yōu)越性。

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

5 結(jié)論

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