自適應(yīng)多普勒補償與變異選擇的蝙蝠算法*

王永貴，張博雅，呂歡歡

遼寧工程技術(shù)大學 軟件學院，遼寧 葫蘆島125105

1 引言

元啟發(fā)式算法是隨機算法與局部搜索算法相結(jié)合的產(chǎn)物，可以在全局搜索和局部搜索之間取得平衡。元啟發(fā)式算法由適者生存和隨機選擇兩部分組成，適者生存確?？尚薪馐諗康阶顑?yōu)值，而隨機選擇可使搜索方式在局部搜索和全局搜索間相互轉(zhuǎn)換，增加可行解的多樣性，避免陷入局部極值。由于元啟發(fā)式算法可在合理的時間和空間開銷下獲得問題的可行解，不受搜索空間限制條件（如不可微、非凸、多峰）的約束且不需要梯度等其他輔助信息，其作為主流優(yōu)化方法受到廣泛的關(guān)注。近年來，許多學者從自然界中得到啟發(fā)，模仿生物行為或自然現(xiàn)象，以種群為基礎(chǔ)提出了各種新型元啟發(fā)式算法。其中，蝙蝠算法[1]（bat algorithm，BA）是一種基于群體智能的新型元啟發(fā)式算法，它是根據(jù)蝙蝠利用回聲定位搜尋獵物和避開障礙物的特性發(fā)展而來。目前，BA已被廣泛應(yīng)用在風能開發(fā)[2]、模型預(yù)測[3]、無人機路徑規(guī)劃[4]、經(jīng)濟調(diào)度[5]等領(lǐng)域。雖然BA 具有收斂迅速、參數(shù)少、魯棒性強等優(yōu)點，但和其他元啟發(fā)式算法一樣，BA 不可避免地存在易陷入局部最優(yōu)和求解精度不高的缺點。為了克服這些缺點，提高全局探索和局部開發(fā)能力，目前一些學者主要從以下四方面對BA 作出改進。

（1）融合其他進化算法。充分發(fā)揮其他算法的優(yōu)點彌補自身的不足。例如文獻[6]結(jié)合和聲搜索的音調(diào)微調(diào)算子產(chǎn)生變異的蝙蝠個體，根據(jù)精英選擇策略保留能進入下一代的最優(yōu)個體，從而改善對搜索空間的探索。文獻[7]采用差分進化中rand/1/bin、randToBest/1/bin、best/1/bin 和best/2/bin 四種不同的變異策略替換BA 原有的局部搜索模式，增加種群多樣性來提高搜索效率。文獻[8]引入蛙跳算法，考慮個體與群體間的信息交流，加快全局收斂。

（2）利用混沌映射?；煦缡欠蔷€性系統(tǒng)的一個特征，由簡單的確定性系統(tǒng)隨機產(chǎn)生。例如文獻[9]用混沌映射結(jié)合線性函數(shù)替換響度和脈沖發(fā)射率中的隨機數(shù)，研究了11 種不同混沌映射對BA 優(yōu)化效率的影響；文獻[10]通過Logistic 映射對精英個體進行混沌優(yōu)化，有效利用了混沌算法的局部搜索能力，避免BA 過早陷入局部最優(yōu)。

（3）優(yōu)化搜索方式。通過修改頻率和速度方程，進而控制個體的搜索位置。例如文獻[11]簡化了位置方程，去除速度參數(shù)，新位置的產(chǎn)生取決于最優(yōu)解和隨機解，并根據(jù)平均解和最優(yōu)解調(diào)整頻率，提高收斂效率。文獻[12]設(shè)計了最佳覓食策略來指導蝙蝠的移動方向，將歷史最優(yōu)位置替換為由最佳覓食策略產(chǎn)生的位置，并采用隨機擾動策略加強蝙蝠之間的信息共享。文獻[13]根據(jù)輪盤賭選擇機制和概率方法，設(shè)計了四種不同的速度更新策略，加強蝙蝠的自我學習能力。文獻[14]利用迭代局部搜索，當搜索陷入局部最優(yōu)解時，對最優(yōu)解進行適當?shù)碾S機移動，從而突破當前空間獲得新解，逃出局部極值區(qū)域，并引入隨機慣性權(quán)重更新速度方程，在一定程度上繼承歷史速度的影響，穩(wěn)定尋優(yōu)結(jié)果。

（4）模擬生物行為。從生物學角度進一步模仿蝙蝠行為，使算法更符合自然規(guī)律。例如文獻[15]分別設(shè)計了具有機械性能和量子特性的飛行策略，用來模擬蝙蝠在不同棲息地之間的移動，并在機械飛行中引入多普勒效應(yīng)更新個體頻率。文獻[16]對蝙蝠產(chǎn)生兩個不同的飛行方向，一個向著最優(yōu)區(qū)域，另一個向著隨機區(qū)域，通過比較隨機個體與當前個體的優(yōu)劣決定最終的飛行方向，在一定程度上模擬了蝙蝠利用回聲之間的延遲來預(yù)測獵物位置的特性。文獻[17]引入許多動物都存在的Lévy 飛行特征，搜索中經(jīng)過一系列較小步長的移動后，突然轉(zhuǎn)變方向產(chǎn)生一個較大的跳躍，從而拓展搜索空間，有效避免蝙蝠個體被局部極值束縛。

除此之外，還有學者從其他角度對BA 進行改進。例如文獻[18]使用鄰域搜索和動態(tài)慣性權(quán)重策略，提出了一種改進的二進制蝙蝠算法。文獻[19]通過變異開關(guān)函數(shù)對滿足條件的蝙蝠個體進行變異，保持較高的種群活躍性。文獻[20]引入外部子群和內(nèi)部子群，兩個子群共同演化協(xié)作，分別增強探索與開發(fā)能力。文獻[21]提出均衡負載的初始化策略，針對離散蝙蝠算法設(shè)計了新的搜索算子，最后應(yīng)用于求解柔性作業(yè)車間調(diào)度問題。文獻[22]結(jié)合三種局部搜索策略與和聲搜索機制，使用新的隨機游走法則改善搜索能力，并用于求解無容量設(shè)施選址問題。

以上改進算法雖從不同角度提高BA 的性能，但在高維問題下仍難以準確收斂到理論最優(yōu)值并存在早熟收斂的現(xiàn)象。從直觀來說，算法越符合自然規(guī)律，就越能高效地解決問題，而BA 算法本質(zhì)上是對自然界蝙蝠行為的簡化與抽象，因此對BA 算法的改進仍需進一步研究。本文提出自適應(yīng)多普勒補償與變異選擇的蝙蝠算法（Doppler and mutant bat algorithm，DMBA），該算法首先根據(jù)蝙蝠較自身相對獵物距離的遠近變化，對頻率進行自適應(yīng)多普勒補償，進一步模擬回聲特性，同時利用種群平均速度產(chǎn)生速度偏移，修正飛行方向。其次，提出柯西和高斯變異機制，使最優(yōu)個體在開發(fā)的不同時期自適應(yīng)選擇變異策略，避免陷入局部極值從而精確搜尋最優(yōu)值。最后，通過調(diào)節(jié)響度和脈沖發(fā)射率，使算法前期執(zhí)行全局探索，后期執(zhí)行局部開發(fā)，有效平衡探索和開發(fā)能力。

2 蝙蝠算法與多普勒效應(yīng)

2.1 蝙蝠算法

BA 算法[1]是在理想狀態(tài)下，簡化回聲定位的特征，模擬蝙蝠在捕食飛行中發(fā)出聲波的響度和脈沖發(fā)射率的變化，接收頻率、速度和位置信息搜尋最優(yōu)解。在D維下，記f(x)為目標函數(shù)，分別為第t代中第i只蝙蝠的位置和速度，fi和分別為蝙蝠的頻率和響度，為脈沖發(fā)射率。在完成以上參數(shù)的初始設(shè)置后，算法進入以下4 個迭代過程：

（1）隨機飛行。蝙蝠的空間位置通過下式更新：

其中，fmin和fmax分別是最小和最大頻率值，β∈[0,1]是服從均勻分布的隨機數(shù)，x*代表當前搜尋到的全局最優(yōu)解。

其中，?是隨機向量，?j∈[-1,1],j=1,2,…,D，At是平均響度，rand1是[0,1]內(nèi)服從均勻分布的實數(shù)。

（3）接受新解。通過式（1）或式（2）產(chǎn)生新個體后，如果并且，則接受，其中rand2是[0,1]內(nèi)服從均勻分布的隨機數(shù)。

（4）參數(shù)調(diào)整。當新個體得到改進時，響度和脈沖發(fā)射率才會通過下式更新：

其中，α和γ都是常數(shù)，0 ＜α＜1,γ＞0,當蝙蝠逼近目標時，響度逐漸減小，不易被獵物察覺，而脈沖發(fā)射率逐漸增大，發(fā)出急促的脈沖信號，迅速定位獵物位置。當Ai減小到0 時意味著蝙蝠捕獲到獵物，停止發(fā)聲。

2.2 多普勒效應(yīng)

事實上，蝙蝠能夠通過目標昆蟲翅膀顫動率引起的多普勒效應(yīng)的變化來區(qū)分目標。這里將能夠發(fā)射聲波的物體稱為聲源，能接收聲波的物體稱為觀察者。研究發(fā)現(xiàn)，當聲源與觀察者之間存在相對運動時，觀察者聽到的聲音頻率就會不同于聲源的發(fā)射頻率，這種現(xiàn)象就是多普勒效應(yīng)。假定f為聲源和觀察者之間沒有相對運動時，觀察者聽到的聲音頻率，即聲源的發(fā)射頻率；f′為聲源和觀察者有相對運動時，觀察者聽到的聲音頻率，若觀察者的運動速度為v，聲源的運動速度為u，聲音在空氣中傳播的速度為c時，f′和f存在如下關(guān)系：

當觀察者靠近聲源時，v用“+”號，遠離時用“-”號；當聲源靠近觀察者時，u用“-”號，遠離時用“+”號。由于多普勒效應(yīng)的作用，當觀察者與聲源互相靠近時，接收頻率大于發(fā)射頻率，觀察者與聲源互相遠離時，接收頻率小于發(fā)射頻率。

3 本文算法

3.1 自適應(yīng)多普勒補償

從式（1）可以看出頻率本質(zhì)上控制蝙蝠飛行的速度和位置，蝙蝠和獵物二者相對空氣都在運動，因此聲波的頻率存在多普勒效應(yīng)，而BA 算法的頻率是在一個區(qū)間內(nèi)隨機取值，忽略了這種效應(yīng)。在實際捕食中，蝙蝠本身會對頻率進行多普勒補償，通過調(diào)整頻率獲知獵物的精確位置。在文獻[15]引入的多普勒效應(yīng)中，蝙蝠與獵物向量在各維上差值的大小并不能準確反映二者的位置變化。因為根據(jù)多普勒原理，頻率是隨著觀察者與聲源在某一時刻前后相對位置的變化而改變的。因此為使算法接近實際，本文對頻率自適應(yīng)補償策略的表達式如下：

其中，因為式（4）的頻率和速度是標量，而算法中的頻率是標量，速度是向量，所以用速度的模長代表速度值的大小。,v*表示當前獵物即最優(yōu)個體的速度，代表當前時刻蝙蝠到獵物的距離，代表前一時刻蝙蝠到獵物的距離。該補償策略參照了蝙蝠在上一次迭代中的位置，頻率的自適應(yīng)調(diào)整取決于蝙蝠與獵物間距離的相對變化，具體遠近的程度是根據(jù)蝙蝠在先前迭代中的位置而言的。當蝙蝠向獵物發(fā)射一定頻率的超聲波后，在等待接收獵物反射回的超聲波這一時期內(nèi)，蝙蝠作為觀察者，獵物作為聲源。當蝙蝠與獵物不存在相對運動時，蝙蝠的發(fā)射頻率等于獵物接收的頻率，通常認為入射波的頻率等于反射波的頻率，故此時獵物作為聲源發(fā)射的頻率即為。因此對頻率進行自適應(yīng)調(diào)整的原理在于：如果，則表示當前蝙蝠個體相比前一時刻已遠離了獵物，相當于觀察者逐漸遠離聲源，根據(jù)式（4），二者從前后時刻來說相互遠離，故取“-”號，v*取“+”號。此時蝙蝠接收到較低頻率的超聲波，應(yīng)當放慢飛行速度，圍繞在獵物周圍細細探尋；如果，說明前后時刻二者的距離不變，既沒有遠離也沒有接近，或者在迭代后期蝙蝠已經(jīng)捕獲到獵物，即找到最優(yōu)解，此時應(yīng)保持當前的頻率不再作調(diào)整；如果，則表示當前蝙蝠個體相比前一時刻更加接近獵物，相當于觀察者逐漸接近聲源，根據(jù)式（4），二者從前后時刻來說相互靠近，故取“+”號，v*取“-”號。此時蝙蝠會接收到更高頻率的超聲波，從而加速飛向獵物。之所以考慮先前迭代與當前迭代中蝙蝠和獵物的距離，是因為在每一次迭代中，獵物的位置是變化的，蝙蝠自身的位置也是在變化，當前時刻下二者間距離的遠近是基于前一時刻各自的位置而言的。

另外，頻率和速度共同影響了新解的位置，并且BA 算法中蝙蝠的飛行具有很強的隨機性，影響自身對最優(yōu)解的搜尋。定義式（1）為方式1，文獻[23]指出根據(jù)方式1 產(chǎn)生的新位置會使算法發(fā)散，并證明其收斂區(qū)域為空集。因此，本文對速度產(chǎn)生偏移，結(jié)合補償后的頻率的位置更新方程如下：

其中，w是[0,1]上服從均勻分布的隨機數(shù)，vm表示種群平均速度。定義式（6）為方式2，不同于方式1，方式2 的速度更新策略引入vm作為種群對個體自身速度的影響，并將方式1 的改為，從而修正飛行方向，確保算法產(chǎn)生的新解能在一個封閉區(qū)域內(nèi)收斂，通過特征方程法證明其收斂的過程如3.5 節(jié)所述。

Fig.1 Two ways of generating new position圖1 兩種方式產(chǎn)生新位置

經(jīng)過多普勒補償后的頻率控制了飛行速度的快慢，進而影響個體在搜索空間中的新位置，為直觀描述補償策略指導新解的準確性，將向量空間簡化到二維平面。圖1 表示在t-1 時刻，固定相同位置、速度和獵物x*時，蝙蝠利用兩種方式產(chǎn)生新位置的差異。在方式1 中，蝙蝠的頻率fi沒有經(jīng)過多普勒補償，而是在上下區(qū)間內(nèi)取隨機值，因此頻率可大可小，如圖1（a）所示，沒能修正新速度的模長和方向，最終使新位置遠離獵物x*。在方式2 中，根據(jù)個體與獵物在前后時刻相對遠近的變化，蝙蝠的頻率受到多普勒效應(yīng)的自適應(yīng)調(diào)整。圖1（b）表示當蝙蝠個體遠離獵物時，經(jīng)過補償策略的影響，接收到更低的頻率。較小的頻率作用于交換順序后的位移偏差，最終與速度偏差共同決定新速度，此時的模長小于舊速度的模長，方向比向著獵物x*，圍繞在獵物周圍減速飛行。圖1（c）表示當蝙蝠個體接近獵物時，同樣受到補償策略的影響，此時接收到更高的頻率，結(jié)合速度和位移偏差產(chǎn)生新速度，其模長大于的模長，方向比更加接近x*，從而加速飛向獵物。從圖1（b）和圖1（c）可知，個體在接收到更低或更高頻率時，通過方式2 產(chǎn)生的要比方式1 接近x*，促使蝙蝠努力朝最優(yōu)解的方向飛行。

根據(jù)多普勒效應(yīng)自適應(yīng)補償頻率，調(diào)整飛行速度的大小和方向，盡可能地模擬蝙蝠在捕食中發(fā)生的自然行為，產(chǎn)生更接近獵物的新個體，從而快速定位到全局最優(yōu)區(qū)域，提高全局探索能力。

3.2 變異選擇策略

BA 算法根據(jù)式（2）進行局部搜索，然而響度隨著迭代逐漸遞減到0，對最優(yōu)個體的擾動步長也逐漸減小，由于缺乏有效的變異機制，最終使種群在前期容易陷入局部極值。為此，已有很多方法對種群實行變異，例如使用和聲[6]或差分[7]等算子能有效避免局部極值的吸引，增加種群多樣性。從另一角度來說，這些算子可能會額外增加算法的負擔。差分算子涉及突變、交叉和選擇操作，和聲算子涉及微調(diào)擾動和隨機選擇操作，可能會在一定程度上增加計算量，并且其各自參數(shù)如交叉概率和微調(diào)概率取值的不同，也可能會影響最終結(jié)果。因此為使算法易于操作并具有通用性，本文利用柯西和高斯分布的特性，在局部搜索中對最優(yōu)個體提出柯西變異和高斯變異兩種變異機制。圖2 給出了標準柯西分布和標準高斯分布密度函數(shù)曲線的差異?？梢钥闯?，兩種分布的密度函數(shù)相似，但從垂直方向上看，柯西分布在中心值附近的峰值小于高斯分布，在兩端的峰值高于高斯分布；從水平方向上看，柯西分布越接近水平軸的兩端，曲線下降越緩慢，而高斯分布的曲線趨近水平軸的兩端。

Fig.2 Probability density of Cauchy and Gaussian圖2 標準柯西與高斯概率密度

（1）柯西變異。由于柯西分布具有較高的兩翼概率特性，它比高斯分布更容易產(chǎn)生具有更寬分布范圍和遠離原點的隨機數(shù)。在局部搜索的前期，對最優(yōu)個體進行柯西擾動，使蝙蝠個體能以大幅度的步長在最優(yōu)區(qū)域附近探尋，拓展搜索空間，增大逃離局部極值的概率。本文根據(jù)標準柯西密度函數(shù)的特性，對最優(yōu)個體構(gòu)造柯西變異的方程如下：

其中，r是(0,1)上服從均勻分布的隨機數(shù)，t是當前迭代次數(shù)，Tmax是最大迭代次數(shù)，C(1,0)是服從標準柯西分布的隨機變量。

（2）高斯變異。由于高斯分布在中心值附近產(chǎn)生隨機數(shù)的概率較高，在局部搜索的后期對最優(yōu)個體進行高斯變異，使蝙蝠個體在最優(yōu)值附近以小幅度的步長游走，對最優(yōu)區(qū)域進行精細搜尋，準確尋找全局最優(yōu)值。本文根據(jù)標準高斯密度函數(shù)的特性，對最優(yōu)個體構(gòu)造高斯變異的方程如下：

其中，r是(0,1)上服從均勻分布的隨機數(shù)，N(0,1)是服從標準高斯分布的隨機變量。

式（7）、式（8）中的1-t/Tmax是在[0,1]內(nèi)的單調(diào)遞減函數(shù)，在開發(fā)初期，t值較小，因此1-t/Tmax取值較大，當其大于在[0,1]內(nèi)隨機產(chǎn)生的數(shù)r時，算法對蝙蝠群的當前最優(yōu)位置按照式（7）進行柯西變異擾動。在開發(fā)前期，柯西變異產(chǎn)生的較大變異步長能避免種群聚集在最優(yōu)值附近，降低陷入局部極值的風險。隨著迭代推進到開發(fā)的后期，t值增大，因此1-t/Tmax的取值逐漸變小，當其小于隨機數(shù)r時，算法對最優(yōu)位置按照式（8）進行高斯變異擾動。在開發(fā)后期，高斯變異產(chǎn)生的較小變異步長能使種群保持對最優(yōu)解附近區(qū)域的空間開采能力，從而實行深度搜尋。兩種變異機制互相協(xié)作配合，在開發(fā)階段促使蝙蝠個體依據(jù)迭代的推進自適應(yīng)選擇變異策略，提高算法的整體收斂速度和尋優(yōu)精度。

3.3 平衡探索與開發(fā)

3.3.1 響度和脈沖發(fā)射率更新策略

在DMBA 算法中，為了有效平衡算法的探索和開發(fā)能力，利用個體的脈沖發(fā)射率控制算法是執(zhí)行全局探索還是局部開發(fā)，利用響度進一步?jīng)Q定是否接收具有更優(yōu)適應(yīng)度的新解，因此本文對響度和脈沖發(fā)射率提出如下更新策略：

其中，Amax和Amin分別是響度的最大值和最小值，rmax和rmin分別是脈沖發(fā)射率的最大值和最小值，tmax是最大迭代次數(shù)。

3.3.2 參數(shù)取值范圍分析

根據(jù)式（9）當t′=tmax/2 時（tmax?1），此時(rmax+rmin)/2，為實現(xiàn)探索到開發(fā)的轉(zhuǎn)換，且和rand1都在[0,1]內(nèi)，rand1服從均勻分布，應(yīng)落到區(qū)間中點附近內(nèi)，在t＞t′時提高發(fā)生轉(zhuǎn)換的概率，即，解得0.8-rmax≤rmin≤1.2-rmax。而在初期要保證探索，rmax應(yīng)取較大的值，即rmax∈[0.8,1.0]，此時對應(yīng)的rmin∈[0,0.2]。對于響度，在成立的同時也要滿足成立，獲得改進的新解才能進入到下一代。根據(jù)式（9）遞減到Amin，賦予其較大的值使成立即可，因為若過小，即使新解獲得了改進，也不能被保留到下一次迭代，故取，即Amax=1，Amin=0.8。

為了確定rmin∈[0,0.2]和rmax∈[0.8,1.0]的最優(yōu)參數(shù)值，需要分析在Amax=1，Amin=0.8 時，rmax和rmin分別取不同的值對算法尋優(yōu)性能的影響。本文DMBA算法給出來自標準函數(shù)[24]的Schwefel 2.22（記為f1）和Quartic（記為f2）在100 維下，當rmax和rmin取不同值時求得的平均適應(yīng)值fit 和標準差std 的比較結(jié)果，如表1所示。其中虛擬蝙蝠的數(shù)目為40，最大迭代次數(shù)為500，每個函數(shù)獨立運行50 次。Schwefel 2.22 函數(shù)和Quartic 函數(shù)分別為單峰和多峰函數(shù)，其全局最優(yōu)值均是0，因此算法求解結(jié)果的平均適應(yīng)值越接近0，說明求解精度越高，標準差越小，收斂結(jié)果越穩(wěn)定。

從表1 中可以看出，參數(shù)rmax和rmin的取值即共有9 種組合，整體來說，算法在各組合下的尋優(yōu)效果相似。其中在[0,0.8]下，算法的尋優(yōu)效果最好，另外[0.1,0.8]和[0.2,0.8]下的平均適應(yīng)值和標準差在整體上的尋優(yōu)效果更優(yōu)于其他6 種組合。的范圍在[0,0.8]、[0.1,0.8]和[0.2,0.8]內(nèi)時，算法的尋優(yōu)性能均具有優(yōu)勢，因此通過上述分析，本文DMBA 算法脈沖發(fā)射率的范圍取[0,0.8]，響度的范圍取[0.8,1.0]。

Table 1 Comparison of performance in value range of 表1 取值范圍對算法尋優(yōu)性能的對比

Table 1 Comparison of performance in value range of 表1 取值范圍對算法尋優(yōu)性能的對比

3.4 算法流程

本文DMBA 算法的執(zhí)行流程如圖3 所示。

Fig.3 Procedure of DMBA圖3 DMBA 算法流程

步驟1初始化參數(shù)，包括蝙蝠個體數(shù)、變量維數(shù)、最大迭代次數(shù)、目標函數(shù)F(x)等。

步驟2產(chǎn)生初始種群，根據(jù)F(x)計算每只蝙蝠的適應(yīng)度值，并記錄最優(yōu)個體x*。

步驟3遍歷所有個體，依據(jù)式（5）和式（6）更新頻率、速度和位置信息，產(chǎn)生新個體xnew。

步驟4生成隨機數(shù)R1，若R1＞ri，則按照式（7）或式（8）選擇變異機制，將變異個體賦值給xnew。

步驟5生成隨機數(shù)R2，若R2＜Ai&F(xnew)＜F(xi)，則將xi替換為xnew，然后按照式（9）更新A和r。

步驟6對所有蝙蝠個體的適應(yīng)值排序，更新當前最優(yōu)解x*。

步驟7判斷迭代次數(shù)是否達到最大次數(shù)或者能否求出滿足精度要求的解，若是則輸出最優(yōu)解x*及對應(yīng)的適應(yīng)度，退出；否則重復步驟3～步驟7。

相對于上級的協(xié)調(diào)作用，采油廠是各項勘探開發(fā)行為運行的主體。各勘探、開發(fā)項目的經(jīng)理及具體組成人員都來自于采油廠。直接掌握著各項目的投資及成本運行、進度運行、質(zhì)量運行、各相關(guān)方關(guān)系運行等。

3.5 全局收斂性分析

根據(jù)式（6），即利用方式2 產(chǎn)生新解體現(xiàn)了算法的全局搜索能力，本文對此進行收斂性分析。盡管和是多維變量，但各維度下分量間均是相互獨立的，故可以簡化到一維進行分析[23]。為簡化計算，假設(shè)在某一時刻下，個體頻率記為常數(shù)e，種群最優(yōu)解位置和平均速度不變，分別記為常數(shù)g和m。

定義1對于DMBA 算法，當采用方式2 產(chǎn)生新解時，極限在一個封閉區(qū)域內(nèi)收斂。

證明由式（6）可得個體位置遞推公式：

這是一個二階常系數(shù)非齊次差分方程，利用特征方程法求其通解，對應(yīng)特征方程如下：

記Δ=(1+w-e)2-4w，仿照二階常系數(shù)齊次微分方程，分別求出通解。先由初始化時的x0、v0根據(jù)式（6）計算x1和x2：

（1）Δ＞0 時，，此時xt=C0+，C0為特解，C1、C2為待定系數(shù)，通過x0、x1、x2求出C0=x0-C1-C2，，。

由于t=0,1,…，故當t→+∞時，若要保證xt極限存在，由洛必達法則可知收斂條件是|λ1,2|＜1，解得-3 ＜w-e＜1，2w-e+2 ＞0，e＞0。

（2）Δ=0 時，λ=λ1=λ2=，此時xt=C0+(C1+C2t)λt，求出C0=x0-C1，C1=，。

當t→+∞時，xt收斂的條件是|λ|＜1，解此不等式得-3 ＜w-e＜1。

當t→+∞時，xt收斂的條件是0 ＜w＜1。

經(jīng)過上述分析可以得到如下結(jié)論：

當Δ＞0 時，收斂區(qū)域為(1+w-e)2-4w＞0,2w-e+2 ＞0 和e＞0 所圍成的區(qū)域。

當Δ=0 時，收斂區(qū)域為(1+w-e)2-4w=0 和-3 ＜w-e＜1 所圍成的區(qū)域。

當Δ＜0 時，收斂區(qū)域為(1+w-e)2-4w＜0 和0 ＜w＜1 所圍成的區(qū)域。

綜合上面三種情況，DMBA 算法的收斂區(qū)域為2w-e+2 ＞0,-3 ＜w-e＜1,0 ＜w＜1和e＞0 所圍成的區(qū)域，此時定義1 得證。 □

3.6 運算復雜性分析

下面將本文提出的改進蝙蝠算法DMBA 和標準BA 算法的運算復雜度進行分析和對比。

設(shè)第i次迭代中算法獲得的最優(yōu)解為1,2,…,M)，M為最大迭代次數(shù)。令ε為收斂閾值，若在第m次(m≤M)迭代中，，則認為滿足收斂精度要求，終止迭代，否則繼續(xù)迭代直到M次結(jié)束，記m為終止迭代次數(shù)。標準BA 算法和DMBA算法每一次迭代中的虛擬蝙蝠數(shù)量不變，均記為Pb，每只虛擬個體每一次迭代需要的運行時間為Ti(i=1,2,…,m)。設(shè)BA 算法的終止迭代次數(shù)為m1，則其時間復雜度為O(m1PbTi)；設(shè)DMBA 算法的終止迭代次數(shù)為m2，則其時間復雜度為O(m2PbTi)，故兩者運行時間性能的差異主要決定于迭代次數(shù)m上，即語句執(zhí)行次數(shù)。由3.1 節(jié)分析可知，對于每一次迭代下的每一只虛擬蝙蝠，BA 算法中個體位置的更新具有很強的隨機性，致使新位置逐漸偏離最優(yōu)解，而DMBA 算法受自適應(yīng)多普勒補償?shù)淖饔茫痔剿髦袀€體的新位置逐漸向最優(yōu)解靠攏，即在相同迭代次數(shù)下，DMBA 算法的運行結(jié)果會比BA 算法更加接近理論結(jié)果，比BA 算法先滿足閾值要求，提前終止迭代，故m1＞m2（4.2 節(jié)實驗表明，整體上減少運行時間。DMBA 算法相比標準BA 算法新改變的計算式如式（5）、式（9）均為常數(shù)級計算，式（7）或式（8）本質(zhì)上與BA 算法的式（2）具有相同的計算結(jié)構(gòu)，均為向量求和運算，對時間復雜度帶來的增量遠遠小于語句執(zhí)行次數(shù)帶來的減量，可以忽略。因此DMBA 算法的時間復雜度O(m2PbTi)小于BA 算法的時間復雜度O(m1PbTi)，而增加的計算部分使得新解在搜索空間中的分布更加合理，解的適應(yīng)性更好。

在空間復雜度方面，本文DMBA 算法比標準BA算法在每次迭代中增加了常數(shù)量級的中間變量如式（5）中的，式（6）中的vm等，以及與之相關(guān)的臨時變量的存儲，但整體上DMBA 算法的終止迭代次數(shù)遠小于BA 算法的終止迭代次數(shù)，語句執(zhí)行次數(shù)的降低減少了存儲的中間變量和臨時變量，因此空間復雜度相比BA 算法有所降低。

本文算法屬于元啟發(fā)式算法，這一類算法不能保證獲得理論最優(yōu)解，而是獲得接近理論值的近似解。對于許多優(yōu)化問題，使用確定性算法雖能獲得理論最優(yōu)解，但計算復雜（例如計算梯度等信息），運行時間很長，以致時間復雜度的代價極大，有時需要保存很多的變量，導致空間復雜度也較大。而隨著問題復雜性的增加，求解工程實際問題往往并不需要得到理論最優(yōu)解，只需要一個能逼近理論值的近似解就能解決問題，故元啟發(fā)式算法比確定性算法更加適用。因此通過設(shè)置一定的滿足條件如收斂閾值，使算法在獲得一個符合實際需求的近似解的同時，能夠提前終止迭代，避免往后不必要的運算，從而縮短運行時間，減少存儲空間。

3.7 綜合分析

4 實驗與結(jié)果分析

4.1 測試函數(shù)

本文選取12 個標準函數(shù)[24]，大部分函數(shù)存在很多局部極值，故準確找到理論最優(yōu)值具有一定難度，適合充分考察算法的尋優(yōu)能力。如表2 所示，在所有測試函數(shù)中，f1～f6為單峰函數(shù)，主要用于測試算法的尋優(yōu)精度和收斂速度；f7～f12為多峰函數(shù)，主要用于測試算法的全局搜索和跳出局部極值避免早熟收斂的能力。本文的所有測試均在Intel Core i5-4200M，2.5 GHz，8 GB 內(nèi)存的PC Windows 7 機器上進行，編寫的程序在Matlab R2016a上實現(xiàn)。

Table 2 Benchmark functions表2 標準測試函數(shù)

4.2 數(shù)值結(jié)果及分析

為了評價DMBA 算法在高維度下的尋優(yōu)性能，本文除了選取BA 算法[1]，還選取近兩年的NBA（novel bat algorithm）算 法[15]、dBA（directional bat algorithm）算法[16]和UGBA（uniform mutant and Gaussian mutant bat algorithm）算法[19]進行比較。

實驗中所有算法的蝙蝠個數(shù)設(shè)置為40，最大迭代次數(shù)Tmax為500，各算法的具體參數(shù)設(shè)置如表3 所示。為了更清晰地表達算法尋優(yōu)效果，設(shè)置誤差值e=1.0E-100,當?shù)趖次迭代的結(jié)果時，可認為其達到全局最優(yōu)值f(x*)（-1.0、0 或0.9），此時終止迭代，并記錄迭代次數(shù)和運行時間，否則繼續(xù)迭代直到Tmax時結(jié)束迭代。

Table 3 Algorithm parameter setting表3 算法參數(shù)設(shè)置

5 種算法針對12 個標準函數(shù)分別在100 維、500維和1 000 維上獨立運行50 次后，通過計算平均尋優(yōu)值mean、標準差std、平均終止迭代數(shù)iter 和平均運行時間time（s）考察算法性能。實驗中最好的結(jié)果用粗體顯示，Inf 表示正無窮，NaN 表示由Inf 參與運算得到的非數(shù)。

根據(jù)表4～表6，從收斂精度上分析可知，DMBA算法在不同維數(shù)下的尋優(yōu)效果具有明顯的優(yōu)勢，其他4 種算法的求解精度整體上隨著維數(shù)的增加而降低。對于單峰函數(shù)f1～f6，隨著維數(shù)的增加，DMBA算法均達到收斂閾值從而獲得了理論最優(yōu)值和標準差；UGBA 和NBA 算法均在f1獲得了理論最優(yōu)值和標準差。對于f2，UGBA 算法在100 維度下獲得了理論最優(yōu)值和標準差，但在500 維和1 000 維上其求解精度降低。對于f5和f6，BA、dBA 和NBA 算法的尋優(yōu)結(jié)果逐漸偏離理論值，精度上的偏差在高維度下進一步擴大，在1 000 維下的平均適應(yīng)值均是正無窮；NBA 算法在500 維和1 000 維下同樣不能得出確切的運算結(jié)果。對于多峰函數(shù)f7～f12，在不同維數(shù)下，DMBA 算法在除f9外的函數(shù)上均達到收斂閾值從而求解到理論最優(yōu)值和標準差；UGBA 算法在f8上均能求解到理論最優(yōu)值，在100 維下求解f10獲得了理論最優(yōu)值；對于f8、f9和f10，BA、dBA 和NBA算法的求解精度隨著維度的升高明顯下降，與理論值的偏離程度增大。

從收斂快慢上分析可知，DMBA 算法收斂到閾值所需的終止迭代次數(shù)最少，對于f1、f2、f7、f8、f10和f12，其終止迭代數(shù)iter近似等于最大迭代數(shù)Tmax的1/25 ；對于f3、f4和f6，其所需的iter 近似等于Tmax的1/6 ；對于f5和f11，iter 近似等于Tmax的1/3，有效減少了迭代過程，縮短算法重復執(zhí)行的時間。另外，UGBA 算法在f1和f8上獲得理論最優(yōu)值時的終止迭代數(shù)稍高于DMBA 算法，NBA 算法在f1上的終止迭代數(shù)要高于DMBA 和UGBA 算法，其在500維和1 000 維下的iter 約占Tmax的1/2。BA 和dBA 算法對所有函數(shù)沒能求解到收斂閾值，因此直到Tmax時終止迭代。

整體而言，BA 算法的求解精度與理論值有較大的偏差，在除f12外的函數(shù)上的尋優(yōu)效果偏低。dBA、NBA 和UGBA 算法的求解結(jié)果優(yōu)于BA 算法，這3 種算法在不同函數(shù)下的尋優(yōu)性能又互有優(yōu)劣，在大部分函數(shù)上的尋優(yōu)結(jié)果沒能達到收斂閾值，其獲得的平均尋優(yōu)值和標準差隨著維數(shù)的增加而明顯降低。DMBA 算法在除f9以外的函數(shù)上均能快速求解到收斂閾值，并且不受維度變化的影響。因此隨著維數(shù)的增加，在100 維、500 維和1 000 維的測試函數(shù)上，DMBA 算法表現(xiàn)出比BA、dBA、NBA 和UGBA 算法更強的全局收斂能力，證明了DMBA 算法求解高維復雜函數(shù)的有效性。

Table 4 Performance comparison of 5 algorithms in dealing with 100 dimensional test functions表4 5 種算法求解100 維測試函數(shù)的性能比較

Table 5 Performance comparison of 5 algorithms in dealing with 500 dimensional test functions表5 5 種算法求解500 維測試函數(shù)的性能比較

Table 6 Performance comparison of 5 algorithms in dealing with 1000 dimensional test functions表6 5 種算法求解1 000 維測試函數(shù)的性能比較

為了進一步分析DMBA 算法在高維度下的尋優(yōu)性能，本文給出5 種算法在100 維度下求解標準函數(shù)的收斂曲線，衡量算法的收斂性能，如圖4～圖15 所示。由于不同算法的收斂結(jié)果存在較大差異，對f2～f7和f9～f12函數(shù)曲線圖的縱坐標作取對數(shù)處理，曲線在某一點處消失說明在該時期的適應(yīng)值滿足收斂閾值，獲得理論最優(yōu)值，從而終止迭代。

Fig.4 Convergence curve of f1function圖4 f1函數(shù)收斂曲線

Fig.5 Convergence curve of f2function圖5 f2函數(shù)收斂曲線

Fig.6 Convergence curve of f3function圖6 f3函數(shù)收斂曲線

Fig.7 Convergence curve of f4function圖7 f4函數(shù)收斂曲線

Fig.8 Convergence curve of f5function圖8 f5函數(shù)收斂曲線

Fig.9 Convergence curve of f6function圖9 f6函數(shù)收斂曲線

Fig.10 Convergence curve of f7function圖10 f7函數(shù)收斂曲線

Fig.11 Convergence curve of f8function圖11 f8函數(shù)收斂曲線

Fig.12 Convergence curve of f9function圖12 f9函數(shù)收斂曲線

Fig.13 Convergence curve of f10function圖13 f10函數(shù)收斂曲線

Fig.14 Convergence curve of f11function圖14 f11函數(shù)收斂曲線

Fig.15 Convergence curve of f12function圖15 f12函數(shù)收斂曲線

分析圖4～圖15，由于BA 算法的搜索算子具有很強的隨機性，新解的位置大幅偏離全局最優(yōu)，造成新解的適應(yīng)值較差，開發(fā)中對最優(yōu)值的擾動越來越小，易產(chǎn)生聚集現(xiàn)象而陷入局部極值，從f2～f7和f9～f12可以看出，BA 算法的尋優(yōu)曲線處于停滯狀態(tài)，基本上停止尋優(yōu)無法跳出局部極值的束縛，尋優(yōu)質(zhì)量較差。dBA 算法產(chǎn)生新解具有選擇性，利用在搜索空間中隨機選擇的一個較優(yōu)解的信息指導其進入下一步的搜索，否則向最優(yōu)解靠攏。但這種選擇機制忽略了速度對位置的影響，在一定程度上降低了解的多樣性，開發(fā)中采用線性遞減的擾動策略，同樣會使新解聚集在局部極值附近，在高維度下易造成早熟收斂的現(xiàn)象，因此dBA 算法的收斂曲線較平緩。NBA 算法一方面通過量子行為拓展個體的搜索范圍，提高了種群的多樣性；另一方面結(jié)合多普勒效應(yīng)指導其產(chǎn)生新解，該策略沒有利用個體與最優(yōu)解在空間位置上距離的遠近信息，不能有效地調(diào)整新解的位置，因而在單峰函數(shù)上的尋優(yōu)效果較為有效，在部分復雜多峰函數(shù)如f10～f12上的求解效果較弱，但整體上的尋優(yōu)性能優(yōu)于BA 和dBA 算法。對于f1，NBA 算法在迭代50 次左右時獲得理論最優(yōu)值；對于f2，NBA 算法在迭代300 次左右時獲得理論最優(yōu)值；對于f3、f4、f7和f9，NBA 算法的收斂曲線的下降幅度明顯優(yōu)于BA 和dBA 算法。UGBA 算法引入變異開關(guān)函數(shù)，使所有個體在任何時期都有機會發(fā)生變異，突破了傳統(tǒng)的只在算法后期對最優(yōu)解進行變異的界限，具有較高的種群多樣性，但忽略了對全局搜索算子的改進，依靠強大的變異機制產(chǎn)生僅次于DMBA 算法的收斂性能。對于f1和f8，UGBA 算法在迭代25 次左右時獲得理論最優(yōu)值；對于f2和f10，UGBA 算法在迭代100 次左右時獲得理論最優(yōu)值。DMBA 算法先根據(jù)距離的變化自適應(yīng)補償頻率，并結(jié)合速度偏移機制產(chǎn)生更靠近最優(yōu)解的新解；其次在局部搜索中引入的柯西和高斯變異策略，在最優(yōu)區(qū)域分別進行大步長和小步長的精細探尋，擺脫局部極值的束縛，最終迅速收斂，提前終止迭代。從圖4～圖15 可明顯看出，不管是求解單峰函數(shù)還是多峰函數(shù)，DMBA 算法都具有更快的收斂速度和更高的收斂精度，在大部分函數(shù)上的收斂曲線更陡峭，下降幅度更明顯。對于f1、f2、f7、f8、f10和f12，DMBA算法均在迭代50 次內(nèi)收斂到理論最優(yōu)值；對于f3、f4和f6，DMBA 算法在迭代100 次左右時收斂到理論值；對于f5和f11，DMBA 算法在迭代150 次左右時收斂到理論值。

綜上所述，實驗表明對于高維度多極值的單峰和多峰函數(shù)，DMBA 算法相比其他4 種算法在求解精度和速度上均具有良好的尋優(yōu)效果，體現(xiàn)了DMBA算法有效地平衡全局探索和局部開發(fā)的能力，驗證了DMBA 算法求解高維復雜函數(shù)的優(yōu)勢。

5 結(jié)論

針對基本蝙蝠算法在求解高維單目標優(yōu)化問題時，存在尋優(yōu)精度低和難以擺脫局部極值束縛的問題，本文提出一種自適應(yīng)多普勒補償與變異選擇的蝙蝠算法。首先，為了準確模擬蝙蝠受到的多普勒效應(yīng)，根據(jù)蝙蝠個體距離最優(yōu)個體相對遠近的變化自適應(yīng)補償頻率，并結(jié)合平均速度對個體速度產(chǎn)生的偏差，共同修正飛行方向，產(chǎn)生更靠近最優(yōu)個體的新個體。其次，為有效解決種群前期易陷入局部極值的問題，對最優(yōu)個體提出柯西和高斯變異策略，先利用柯西變異產(chǎn)生較大的步長，提高擺脫局部極值束縛的概率，后利用高斯變異產(chǎn)生較小的步長，精細搜索最優(yōu)區(qū)域。最后，利用合理范圍內(nèi)的響度和脈沖發(fā)射率，調(diào)控算法前期執(zhí)行全局探索，后期執(zhí)行局部開發(fā)，并提高接受較優(yōu)新解的概率，平衡探索和開發(fā)能力。從理論上分析了本文算法收斂的可行性和運算的復雜性，利用12 個標準函數(shù)在不同維度下進行仿真實驗，結(jié)果表明與最近文獻的算法相比，本文算法在求解高維度優(yōu)化問題時能有效提高收斂精度和速度。