基于鄰域引力學習的生物地理學優(yōu)化算法

馬 萍，劉思含，孫根云，張愛竹 ，郝艷玲

1.中國石油大學（華東）地球科學與技術學院，山東 青島 266580

2.青島海洋國家實驗室 海洋礦產(chǎn)資源評價與探測技術功能實驗室，山東 青島 266071

3.環(huán)境保護部衛(wèi)星環(huán)境應用中心 國家環(huán)境保護衛(wèi)星遙感重點實驗室，北京 100094

1 引言

生物地理學優(yōu)化算法（Biogeography-Based Optimization，BBO）是Simon[1]于2008年提出的一種新型的元啟發(fā)式算法。該算法受生物地理學啟發(fā)，通過模擬生物物種在棲息地之間的遷移、變異和滅絕實現(xiàn)棲息地之間信息的交流和共享，達到搜尋問題最優(yōu)解的目的[2]。

BBO算法具有操作簡單、參數(shù)少、收斂快速等優(yōu)點[3]，但是該算法在搜索過程中容易發(fā)生早熟收斂而陷入局部最優(yōu)[4]。造成這一現(xiàn)象的直接原因是在遷移操作中，棲息地的更新僅僅通過簡單的解變量替換的方式進行，導致算法開采新解的能力較差[4]；同時，“輪盤賭”策略選擇的遷出棲息地大部分為優(yōu)秀解，使得種群主要向優(yōu)秀棲息地學習，進一步加快了種群多樣性的喪失，致使算法陷入停滯狀態(tài)[5]。為解決這一問題，研究者們提出了多種改進策略。畢曉君等[5]改進了BBO算法的遷移操作，采用動態(tài)方法選取遷出棲息地，并運用一種混合遷移策略指導物種遷移，增強了算法對解的搜索能力；Boussaid等[6]將DE算法與BBO算法相結合，提出了雙階段差分生物地理學優(yōu)化算法，利用DE算法的搜索能力提高了算法的種群多樣性；龔文引等[7]采用了三種變異機制代替BBO算法的隨機變異策略，并利用實數(shù)編碼的形式將算法拓展到了連續(xù)域，有效地提高了BBO算法的全局搜索能力；徐志丹等[8]在BBO算法遷移策略的基礎上提出了擾動遷移算子，增強了群體的多樣性，提高了算法解決MOP的能力。這些改進策略均在一定程度上提高了BBO算法的優(yōu)化性能，但大部分算法忽略了棲息地之間物種遷移的自然規(guī)律，沒有充分考慮棲息地之間的距離和適應度對物種遷移的影響。

為解決上述問題，本文提出了一種基于鄰域引力學習的生物地理學優(yōu)化算法（Neighbor Force Learning Biogeography-Based Optimization，NFBBO）。新算法采用基于鄰域的選擇策略，使遷入棲息地向其鄰域中最鄰近且優(yōu)秀的棲息地學習，充分利用棲息地的鄰域信息，增加種群多樣性。同時采用引力學習的方式對遷入棲息地進行更新，使其解變量的變化受遷出棲息地適應度和距離的共同影響，拓展解空間，提高算法的搜索能力。為了使算法更好地跳出局部最優(yōu)，提出了一種自適應的高斯變異機制，通過10個具有不同特點的測試函數(shù)[9-10]進行對比實驗，結果表明了本文算法的有效性和優(yōu)越性。

2 背景知識

2.1 生物地理學優(yōu)化算法

在自然界中，物種生存在不同的棲息地中，適合物種生存的棲息地具有高的適應度指數(shù)（Habitat Suitability Index，HSI）。影響適應度指數(shù)的因素，如溫度、雨量和植被的多樣性等稱為適應度指數(shù)變量（Suitability Index Variable，SIV）。在BBO算法中，每個棲息地對應一個優(yōu)化問題的候選解其中N是解的個數(shù)，D是解的維度，評價棲息地好壞的適應度指數(shù)對應優(yōu)化問題的適應度函數(shù)。算法中優(yōu)秀的解對應高HSI的棲息地，較差的解對應低HSI的棲息地。根據(jù)生物地理學理論，HSI值高的棲息地適合居住，物種數(shù)較多且趨于飽和，對棲息地空間和資源的競爭激烈，因此接納新物種遷入的能力較差，具有較高的遷出率和較低的遷入率。相反，HSI值低的棲息地，物種數(shù)量少，因此有很大的空間和資源，具備較高的遷入率和較低的遷出率。棲息地之間物種的遷入和遷出提供了不同棲息地之間信息交流的途徑，較差棲息地可以通過接受優(yōu)秀棲息地的物種遷移提高自身的質(zhì)量。棲息地Xi的遷入率λi和遷出率μi，可以由以下公式計算得到：

式中，I和E分別為最大遷入率和遷出率；si為棲息地Xi的物種數(shù)量；smax為每個棲息地可容納的最大物種數(shù)量。

BBO算法通過遷移操作實現(xiàn)棲息地的更新。對于棲息地Xi的第d維解變量，如果滿足遷入條件，則按照下列方式進行遷移操作：（1）通過“輪盤賭”策略選取滿足條件的遷出棲息地Xi；（2）用遷出棲息地對應維度的解變量代替原有棲息地的解變量。BBO算法通過這種解變量替換的方式，使較差棲息地共享優(yōu)秀棲息地的解分量而得到進化。

為了增強種群多樣性，使算法跳出局部最優(yōu)，BBO算法在執(zhí)行完遷移操作之后，設置了一個變異操作，棲息地的變異概率為：

其中，mmax為初始變異率；Pi為各個棲息地的物種數(shù)量概率；Pmax為所有物種數(shù)量概率的最大值。

變異操作中，對于棲息地Xi的第d維解變量，若隨機產(chǎn)生的[0，1]之間的隨機數(shù)小于其變異率mi，則采用隨機變異策略隨機產(chǎn)生一個新的解分量代替原解分量。變異算子可以使棲息地的一個或多個解分量發(fā)生變化，增加種群的多樣性。BBO算法的詳細流程介紹見文獻[1]。

2.2 萬有引力定律

作為宇宙中四種基本相互作用力之一的萬有引力，由Newton于1687年提出[11]。在牛頓萬有引力定律中，宇宙空間中任意兩個物體之間都相互吸引，且引力的大小與它們質(zhì)量的乘積成正比，與它們之間距離的平方成反比[11]，即：

其中，G為萬有引力常數(shù)；M1和M2分別為兩個物體的質(zhì)量；R12為兩個物體之間的距離。根據(jù)牛頓第二定律，物體1在物體2的萬有引力作用下產(chǎn)生的運動加速度為：

從式（4）中可以看出，萬有引力定律反應了物體質(zhì)量和距離對引力影響的規(guī)律：在同等距離下，質(zhì)量大的物體吸引力更大；在質(zhì)量相等的情況下，距離越近的物體受到的引力越大。萬有引力定律的這一特性，和自然界中物種遷移規(guī)律有著相同之處，即物種的遷移與棲息地之間距離的遠近和適應度值有關。因此，本文將引力定律應用到BBO算法中，構建新的棲息地更新策略，提高算法的搜索能力。

3 生物地理學優(yōu)化算法

在自然界中，棲息地適應度的提高是通過物種遷移實現(xiàn)的[1]。物種在不同棲息地之間進行遷移時，需要同時考慮兩個因素：棲息地適應度和距離。低適應度的棲息地通過接受高適應度棲息地的物種遷移提高自身的質(zhì)量。物種遷出棲息地的適應度越高，其物種間的競爭也就越激烈，導致遷出的物種對環(huán)境的適應能力更強，對遷入棲息地的影響更大。同時，根據(jù)地理學鄰近效應原理[12]，棲息地更容易受到鄰近棲息地的影響。這主要是因為物種會選擇距離較近的棲息地進行遷移，遷移距離越遠，物種被獵殺的風險也就越高，距離越近，物種保留得越好[13]。因此，在兩個遷出棲息地適應度相同的情況下，遷移距離近的影響大。特別地，當棲息地距離較遠時，即使是高適應度的遷出棲息地，對遷入棲息地的影響也較小。棲息地之間的這種相互關系與引力規(guī)律非常類似，因而可以利用引力定律來描述不同物種遷移對棲息地的影響。

原始BBO算法的遷移操作忽略了上述棲息地之間復雜的遷移關系，通過“輪盤賭”的策略選擇遷出棲息地，并對滿足遷入條件的棲息地通過解變量替換的形式進行更新[1]。“輪盤賭”策略雖可有效地選取較優(yōu)的棲息地作為遷出棲息地，但是該選擇方式具有一定的隨機性，忽視了棲息地之間距離和適應度對物種遷移的影響。解向量替換的更新方式使得遷入棲息地完全被動地接收遷出棲息地的信息，導致搜索空間不再產(chǎn)生新的變量，僅僅是當前所有解變量的組合，棲息地之間迅速趨于相似，種群多樣性降低[4-5]。為了增加算法的種群多樣性，跳出局部最優(yōu)，BBO算法采用隨機變異策略對棲息地進行變異操作。但是這種變異方式忽略了種群的狀態(tài)信息，對新解的搜索能力較差，特別是在迭代后期，當種群候選解和最優(yōu)解較為接近時，隨機變異不僅很難勘探出較優(yōu)解，還容易產(chǎn)生很多較差解，造成計算資源的浪費[5]。

基于以上分析，本文提出一種基于鄰域引力學習的遷移算子。在該算子中，對滿足遷入條件的棲息地采用“適應度距離比”的方法從其鄰域中選擇遷出棲息地。同時，采用引力學習的方式對遷入棲息地進行更新，不同物種遷移的影響與距離和適應度有關。在此基礎上，為了彌補BBO算法隨機變異策略的不足，引入一種自適應的高斯變異策略，利用當前種群的信息進行隨機擾動，并根據(jù)進化過程調(diào)整變異強度，使算法能夠自適應地跳出局部最優(yōu)，尋找更優(yōu)解。

3.1 NFBBO遷移策略

其中，棲息地Xi的r個鄰域是根據(jù)適應度值排序之后，依順序在Xi的兩邊選取r/2個棲息地組成。這樣，遷入棲息地就可以向其鄰域中最鄰近且優(yōu)秀的棲息地學習。在選擇出合適的遷出棲息地之后，采用引力學習的策略對遷入棲息地進行更新：

其中，rand為[0，1]之間的隨機數(shù)；M(Xk)為棲息地Xk的質(zhì)量，計算公式為：

式（7）中A是空間尺度因子，隨著當前解空間的擴大或縮小而增減，計算公式為：

其中，Xd(u)和Xd(l)分別是當前種群的第d維解變量的最大值和最小值。

NFBBO遷移算子的具體步驟如算法1所示。

算法1 NFBBO遷移算子

1.按照適應度值對棲息地進行排序，并劃分鄰域

2.計算所有粒子的遷入率λ和遷出率μ

4. For d=1 to D do

5. If rand(0,1)＜λi

6. 按照式（6）從Xi的r個鄰域選擇遷出棲息地Xdk

7. 按照式（7）更新Xdi

8. End If

9. End for

10.End for

中外運-敦豪國際航空快件有限公司近日在其北京總部舉行媒體發(fā)布會，宣布其珠?？诎墩铰涑刹⑼度胧褂?，成為落戶珠?？诎秶H快遞監(jiān)管中心的首家國際快遞公司。此外，DHL正式宣布將持續(xù)加大在中國的戰(zhàn)略投資，對外公開了今年以來的一系列投資舉措。DHL稱，借助港珠澳大橋帶來的高效物流通道，DHL珠?？诎兜慕⒋蠓嵘榻靼兜貐^(qū)國際物流的快遞效率。隨著2018年10月24日港珠澳大橋正式通車，由珠?？诎肚尻P的國際快遞轉(zhuǎn)運至其香港轉(zhuǎn)運中心（DHL全球三大轉(zhuǎn)運中心之一）的時間將從原來的4小時縮短為45分鐘，大大提升了轉(zhuǎn)運時效。而這對于專業(yè)做國際限時快遞服務的DHL來說，尤為重要。

與BBO算法遷移算子不同，NFBBO算法中采用了鄰域選擇策略確定遷出棲息地，充分利用了每個棲息地鄰域粒子的距離和適應度信息，有效避免了“輪盤賭”策略大概率選擇高適應度棲息地所造成的早熟收斂問題，增加了算法的種群多樣性，并且適應度信息的運用保證了算法搜索精度。同時，引力學習的更新策略直接源于基本的萬有引力定律，使得遷入棲息地的改變受物種遷移距離和適應度的綜合影響，產(chǎn)生了新的解變量，拓展了解空間；空間尺度因子的引入，可以根據(jù)種群的收斂狀態(tài)調(diào)節(jié)引力的大小，提高了算法的搜索能力。

3.2 自適應的高斯變異機制

為了使算法跳出局部最優(yōu)，BBO算法采用了隨機變異策略。但是該變異策略忽略了種群在不同進化過程中的狀態(tài)差異，搜索新解的能力較差[5]。為了使算法更好地搜索到全局最優(yōu)解，在迭代初期，應使種群更大程度地遍布整個搜索空間，較快地定位最優(yōu)解的范圍；在迭代后期使種群聚集在最優(yōu)值的鄰域范圍內(nèi)，進行更精細的搜索[8]。

基于這一點，本文提出一種自適應的高斯變異機制。與隨機變異不同，高斯變異是在原解的周圍產(chǎn)生一個服從高斯分布的隨機擾動[14]，公式為：

式中，Gaussian(0 ,σ)是服從均值為0方差為σ的高斯分布隨機變量。受文獻[15]啟發(fā)，文中方差σ隨著迭代次數(shù)逐漸遞減：

其中，itermax是算法的最大迭代次數(shù)；t是算法的當前迭代次數(shù)。在迭代初期，σ值較大，高斯變異可以產(chǎn)生較大的擾動步長，增大算法的搜索范圍；而在迭代后期，σ變小，產(chǎn)生的擾動步長較小，主要在當前候選解的局部范圍進行精細搜索。同時，變異步長的計算利用了棲息地信息，因此，高斯變異機制可以根據(jù)不同棲息地在不同進化過程中的狀態(tài)自適應地產(chǎn)生變異粒子，更加高效地搜索新解，跳出局部最優(yōu)。

自適應的高斯變異的步驟如算法2所示。

算法2自適應的高斯變異

1.計算所有粒子的變異率m

2.For i=1 to N do

3. For d=1 to D do

4. If mi＞rand

6. End if

7. End for

8.End for

3.3 NFBBO算法流程

基于鄰域引力學習的生物地理學優(yōu)化算法的流程如圖1所示。

圖1 NFBBO算法流程圖

4 實驗結果與分析

4.1 測試函數(shù)

為驗證算法的有效性，本文采用10個具有不同特點的測試函數(shù)進行函數(shù)優(yōu)化實驗。測試函數(shù)的維度D均為30，其表達式、搜索空間S以及真值o如表1所示。其中F1～F2為經(jīng)典測試函數(shù)中的單峰函數(shù)[9]，只有一個最優(yōu)值，可以檢驗算法的收斂特性[5]；F3～F5為經(jīng)典測試函數(shù)中的多峰函數(shù)[9]，含有多個局部極小值，反映了算法跳出局部最優(yōu)，逼近全局最優(yōu)解的能力[5]；F6～F10為CEC2015旋轉(zhuǎn)平移測試函數(shù)[10]，其全局最優(yōu)點不再位于搜索空間的中心，且函數(shù)變量之間彼此不相關，用來檢驗算法解決復雜優(yōu)化問題的能力。

4.2 參數(shù)設置

本文采用基本的BBO[1]算法以及目前改進效果較好的 PBBO[16]算法、DBBO[6]算法和 RCBBO[7]算法作為對比算法。為了保證對比實驗的公平性，所有算法的終止條件均設置為最大適應度計算數(shù)，F(xiàn)Esmax=50 000，種群大小為N=50。同時為了發(fā)揮各個對比算法最優(yōu)的性能，算法的其他參數(shù)都按照原文獻經(jīng)過測試后的參數(shù)進行設定。NFBBO算法中最大遷入率E=1，最大遷出率I=1,初始變異率mmax=0.1,鄰域大小

表1 測試函數(shù)

對每個優(yōu)化函數(shù)，每個算法獨立運行30次，取運行結果的平均值Mean、標準差Std、運行時間runtime[10]進行比較。此外，本文采用Wilcoxon秩和檢驗法[17]對不同算法進行非參統(tǒng)計檢驗，置信度α=0.05。非參檢驗的實驗結果由“h”表示，其中“+”表示測試結果本文算法顯著占優(yōu)，；“-”表示測試結果其他算法顯著占優(yōu)；“=”表示測試結果不顯著，即本文算法與其他算法所得的結果無顯著性差異。

4.3 實驗結果及分析

實驗結果如表2所示，可以看出，NFBBO算法在所有函數(shù)上獲得的Mean值都是最小的，要明顯優(yōu)于其他4種對比算法，充分表現(xiàn)了本文算法在搜索能力和搜索精度上的優(yōu)越性。這主要是因為NFBBO算法遷移操作中的鄰域選擇策略充分利用了棲息地的鄰域信息，增加了種群的多樣性；引力學習的更新方式拓展了解空間，提高了搜索能力，其中空間因子的使用還可以調(diào)節(jié)搜索的步長，更好地找到全局最優(yōu)解的范圍，并在后期進行精細的搜索。對于含有多個局部極小值的多峰函數(shù)F3和F5，NFBBO算法的優(yōu)化效果更為顯著，是唯一一個搜索到真值的算法，而其他算法在這兩個函數(shù)上的優(yōu)化效果都較差。這表明NFBBO使得種群能夠有效地跳出局部最優(yōu)，收斂到全局最優(yōu)。在處理復雜的CEC2015測試函數(shù)時，5種算法所得到的平均最優(yōu)值結果都不太理想，這主要是因為旋轉(zhuǎn)平移函數(shù)本身比較復雜，函數(shù)變量之間不相關，且真值不在函數(shù)的搜索空間中心處，加大了全局最優(yōu)解的搜索難度。同時，BBO算法本身不具備旋轉(zhuǎn)不變特性，因此基于BBO改進的策略在CEC2015函數(shù)上效果較差。即便如此，相比較于其他4種對比算法，NFBBO算法的處理效果仍然是最優(yōu)的。這些實驗結果都證明了本文算法在處理不同特點的函數(shù)優(yōu)化問題時的優(yōu)越性。同時從表2中各個算法的“Std”值可以看出，NFBBO算法具有較好的穩(wěn)定性。除了函數(shù)F7和F10，NFBBO算法的標準差在其他8個測試函數(shù)的結果中都是最小的，且效果突出。

對于算法的搜索效率和收斂速度可以從實驗結果表2的runtime和收斂特性曲線中得出。由表2可知，NEBBO算法的運算時間在所有單峰函數(shù)和多峰函數(shù)上都是最小的，驗證了NEBBO高效的運算速度。尤其是在具有一個局部極值的單峰函數(shù)F2上，NEBBO的運算速度明顯優(yōu)于其他對比算法。圖2給出了5種算法對部分測試函數(shù)的收斂特性曲線，圖中分別采用了5種不同的線型表示不同的對比算法。從圖2中可以看出，NFBBO算法具有優(yōu)良的收斂性能。對于經(jīng)典的單峰和多峰函數(shù)F1、F2和F5，NFBBO算法在演化的初始階段收斂速度就明顯快于其他4種對比算法，表現(xiàn)出其優(yōu)越的搜索能力，能迅速找到優(yōu)秀解所在的區(qū)域。同時，在收斂曲線中，NFBBO算法搜索到的最優(yōu)值也是最小的，具有較高的收斂精度。但是對一些復雜的CEC2015測試函數(shù)，算法的收斂速度有所變慢。對函數(shù)F6，在演化初期，NFBBO算法收斂曲線的下降速度要慢于PBBO和DBBO，但是隨著迭代的進行，NFBBO算法的收斂速度明顯加快，且達到最好的收斂精度。同樣在函數(shù)F8的演化過程中，初期階段NFBBO算法收斂速度要慢于其他算法，隨后曲線下降速度加快，當其他4種對比算法的收斂曲線不再變化，陷入局部最優(yōu)時，NFBBO算法的收斂曲線能夠繼續(xù)下降且收斂到了最好的結果。與以上CEC2015測試函數(shù)不同，對F10，NFBBO算法表現(xiàn)出了明顯的收斂性能優(yōu)勢，在整個演化過程中，NFBBO算法的收斂速度均是最快的且達到了最好的收斂精度?；谝陨戏治?，可以得出NFBBO算法具有較快的收斂速度，在處理復雜的函數(shù)問題時，能夠很好地跳出局部最優(yōu)，拓展新的搜索區(qū)域，找到更加優(yōu)秀的解集。

表2 5種算法在不同測試函數(shù)上的性能對比

表2統(tǒng)計了對比算法之間的非參檢驗結果。從結果中可以看到，除函數(shù)F6、F7和F8，其他函數(shù)的非參檢驗結果均為“+”，即與其他對比算法相比，NFBBO算法具有顯著的優(yōu)越性。對函數(shù)F6和F7，NFBBO算法要顯著優(yōu)于BBO和RCBBO，與PBBO、DBBO算法無顯著性差異。對函數(shù)F8，與PBBO算法無顯著差異，但是要顯著優(yōu)于其他函數(shù)。從整個非參檢驗的結果可以得出，NFBBO算法與其他優(yōu)化算法相比具有顯著的優(yōu)越性。

5 結束語

BBO算法具有較快的收斂速度，但其搜索能力較差，容易發(fā)生早熟收斂，陷入局部最優(yōu)。為了克服這一缺點，本文提出一種基于鄰域引力學習的遷移算子，該算子采用鄰域選擇策略確定遷出棲息地，并利用引力學習的方式對棲息地進行更新，增加了種群多樣性，提高了算法的搜索能力。同時引入了自適應高斯變異機制，充分利用了當前解的信息，使算法能夠自適應地跳出局部最優(yōu)。從實驗結果中可以得出，NFBBO算法不僅收斂速度較其他算法快，而且可以更大程度上逼近全局最優(yōu)解，在收斂速度和收斂精度上較標準BBO算法有較大提高。

圖2 BBO、PBBO、DBBO、RCBBO與NFBBO在部分測試函數(shù)上的收斂曲線圖