差分遷移和趨優變異的生物地理學優化算法

張新明，康 強，王 霞，程金鳳

1(河南師范大學 計算機與信息工程學院，河南 新鄉 453007)

2(河南省高校計算智能與數據挖掘工程技術研究中心，河南 新鄉 453007)

1 引 言

進化算法是一類模擬自然現象和生物行為的優化算法，主要通過群智能的方法在解空間區域搜索最優解，具有比傳統優化方法更高的搜索效率，常用于處理科學和工程領域中的優化問題.已有的知名進化算法包括粒子群(Particles swarm optimization，PSO)算法[1]，人工蜂群(Artificial bee colony，ABC)算法[2]，差分進化(Differential evolution，DE)算法[3]等，近幾年還不斷有各種新的算法被提出.

生物地理學優化(Biogeography-based optimization，BBO)算法是進化算法之一，于2008年由Simon[4]首次提出，得到眾多學者的青睞，然而，該算法的兩個主要算子(遷移算子和變異算子)都存在著一些缺陷，且算法收斂速度慢，計算復雜度高，從而影響了算法的優化性能和運行速度.

許多學者在改善BBO算法方面進行了大量研究，主要分為以下四個角度：一、分析調整BBO算法的模型和參數，例如，Ma[5]提出了6種不同的遷移模型，分析了各模型下遷入率和遷出率的變化曲線，并在不同的種群數量、問題維度、變異率、最大遷入率和最大遷出率下對6種模型的優化性能進行測試，驗證了余弦遷移模型具有最好的優化性能，該模型后來也被一些其它研究所采用[6,7]；二、改變算法的拓撲結構，例如，Zheng等人[8]提出了3種不同的局部拓撲BBO算法，使算法中的遷移只能在相鄰區域發生，從而降低計算復雜度，并通過實驗驗證了3種局部拓撲BBO算法的優化性能；三、改進算法的更新方式，例如，Guo等人[9]提出了一種回溯BBO算法來克服遷移算子中的缺點，提高算法的優化性能；四、算法之間的混合，例如，Gong等人[10]將DE算法和BBO算法混合生成DE/BBO算法，有效地結合了DE算法的探索能力和BBO算法的開采能力，增強了算法的優化效率.需要注意的是，現代算法改進策略已不限于單從上述某一個角度改進BBO算法，很多研究都會從幾個角度同時對算法進行改進.雖然這些研究一定程度上達到了改善BBO算法的目的，卻無法保證算法的性能最大化，隨著社會發展，現實中要不斷面臨各種復雜的優化問題，對算法的優化性能發出巨大挑戰，目前，BBO算法在優化性能方面依然有著可提升空間及研究意義.

算法的優化性能體現在三個方面，一是尋優能力，即能否搜索到問題的最優解或高精度的解；二是穩定性，即能否經常搜索到滿意解，而非偶然事件；三是收斂速度，即能否用較少的迭代次數完成搜索.此外，在增強算法優化性能的同時還應考慮運行時間的平衡，避免以大量時間消耗為代價而得不償失.為了增強BBO算法的優化性能，降低其運行的時間消耗，提出了一種差分遷移和趨優變異的BBO算法(DGBBO).對BBO算法的遷移算子進行改進，增強全局搜索能力，平衡探索和開采，對BBO算法的變異算子進行改進，加快收斂速度，又從多個角度降低算法的計算復雜度，減少運行時間.在一組常用的基準函數上進行仿真實驗，對比其它state-of-the-art算法，對DGBBO算法的優化性能和運行速度進行了驗證.

2 生物地理學優化算法

在生物地理學理論中，一個種群由若干棲息地組成，棲息地通過生存適應度指數(Habitat Suitability Index，HSI)描述其生存環境的優劣，影響生存適宜度指數的因素稱為生存適宜度指數變量(Suitability Index Variables，SIVs)，其中每一個SIV都是一個獨立變量.

BBO算法是受生物地理學理論啟發而提出的，對于求解式(1)所示的d維全局優化問題，

minf(x)，x∈D

(1)

其中，D為解空間區域，用x=(x1，x2，…xd)表示該優化問題的候選解，f(x)是該候選解對應的目標函數值.

定義1. 生態系統(種群)HN由N個棲息地組成，其中，N為種群數量.

定義2. 棲息地Hi(i=1，2，…，N)的生存適宜度指數變量SIVs=(Hi(SIV1)，Hi(SIV2)，…，Hi(SIVd))，表示所求優化問題的一個候選解.

定義3. 棲息地Hi(i= 1，2，…，N)的生存適宜度指數HSI表示該候選解對應的目標函數值，與該棲息地物種數量Si成正關系.

定義4. 棲息地Hi的遷入率λi是其HSI或物種數量Si的單調遞增函數，遷出率μi是其HSI或物種數量Si的單調遞減函數，通常算法根據圖1所示的線性遷移模型計算遷入率和遷出率，計算分別如式(2)和式(3)所示：

λi=I(1-Si/Smax)

(2)

μi=E(Si/Smax)

(3)

其中，I表示最大遷入率，E表示最大遷出率，Smax表示最大物種數量.

圖1 線性遷移模型Fig.1 Linear migration model

定義5. 遷移操作Ω(λ，μ)是一個概率性運算，棲息地Hi被其它棲息執行特征遷入的概率與其遷入率λi成正比，棲息地HSI對其它執行特征遷出的概率與其遷出率μSI成正比，遷移操作可表示為式(4)所示：

Hi(SIVj)←HSI(SIVj)

(4)

其中，Hi為遷入棲息地，HSI為遷出棲息地，j=1，2，…d.

BBO算法的遷移算子的偽代碼如算法1所示，其中，rand表示均勻分布在(0，1)之間的隨機實數.

算法1. 遷移算子

01 fori= 1 toNdo

02 forj= 1 toddo

03 ifrand<λithen

04 用輪賭選擇法選出遷出棲息地HSI

05 通過式(4)更新Hi(SIVj)

06 end if

07 end for

08 end for

需要注意的是，通過遷移算子更新之后的Hi(SIVj)不能越出解的可行區域D.

定義6. 變異操作M(λ，μ)是一個概率性運算，基于棲息地存在的先驗概率對棲息地生存環境隨機性改變，棲息地Hi的變異率mi計算如式(5)所示：

mi=mmax(1-Pi/Pmax)

(5)

其中，mmax表示最大變異概率；Pi是物種數量概率，其遷入率和遷出率存在的關系如式(6)所示，Pmax= max(Pi)：

(6)

變異算子的偽代碼如算法2所示.

算法2. 變異算子

01 fori=1 toNdo

02 通過式(5)計算變異率mi

03 forj=1 toddo

04 ifrand

05 在取值范圍內用隨機生成的SIV取代Hi(SIVj)

06 end if

07 end for

08 end for

同樣的，通過變異算子更新之后的Hi(SIVj)不能越出解的可行區域D.

定義7. 種群更新操作Ψ(N，d，λ，μ，Ω，M)是將一次優化迭代更新后的所有棲息地組成的新種群用于下一次優化迭代.BBO算法的總流程如算法3所示,其中，MaxDT表示最大迭代次數.

算法3. BBO算法總流程

01 設置相關參數，隨機初始化種群

02 評價每個棲息地的HSI，按HSI由優至劣對種群排序

03 fort= 1 toMaxDTdo

04 計算每個棲息地的遷入率和遷出率，保留精英棲息地

05 通過算法1的遷移算子更新種群

06 通過算法2的變異算子更新種群

07 對每個棲息地進行越界限制

08 評價每個棲息地的HSI，按HSI由優至劣對種群排序，用精英棲息地替換較差的棲息地

09 按HSI由優至劣對每個棲息地排序

10 end for

11 輸出最優解

3 改進的生物地理學優化算法

3.1 算法改進動機

鑒于BBO算法的遷移算子采用式(4)所示的直接取代式遷移操作，雖然提供了一定的局部搜索能力，但遷移方式單一，棲息地間共享的信息少，可搜索位置局限，又由于現代群智能優化算法在改進時，若一味地追求全局搜索或者局部搜索單方面的提升，反而不能解決復雜優化問題，需考慮二者的平衡，整體上提高算法的優化性能，故將兩種差分擾動操作與原遷移操作有機融合，形成差分遷移算子，有效地結合了原遷移操作的局部搜索和差分擾動操作的全局搜索，整體上提升算法的全局搜索能力并平衡了探索和開采.

鑒于BBO算法的變異算子采用算法2第05行所示的隨機方向的變異操作，可能破壞優質解，導致種群退化，故將原變異操作去掉，克服上述缺陷，為彌補變異操作的缺失，將趨優操作融入原變異算子中，提升了算法的收斂能力.鑒于BBO算法一些計算過程繁瑣，故從多個角度降低了算法的計算復雜度.利用算法的已有的局部搜索能力并對全局搜索能力進行提升有利于增強算法的尋優能力，對于算法探索和開采的平衡有利于強化算法的穩定性，對于算法收斂能力的提升有利于加快收斂速度，對于算法計算復雜度的降低有利于降低運行的時間消耗，最終得到具有優秀優化性能且運行時間較少的改進算法.

3.2 差分遷移算子

DE算法是一個知名的進化算法，其優化原理是根據當前種群中個體間的距離和方向信息，通過差分計算引導種群搜索最優解[3].DE算法具有優秀的全局搜索能力，其中起到關鍵作用的差分思想被很多其它改進算法所借鑒.

對于BBO算法的遷移算子，將式(7)和式(8)所示兩種差分擾動操作與原遷移操作有機融合，形成差分遷移算子.

Hi(SIVj)←Hi(SIVj)+α*(Hrn1(SIVj)-Hrn2

(SIVj)+Hrn3(SIVj)-Hrn4(SIVj))

(7)

Hi(SIVj)←Hi(SIVj)+α*(Hbest(SIVj)-

Hi(SIVj)+Hrn1(SIVj)-Hrn2(SIVj))

(8)

其中，α是縮放因子，Hbest當前迭代種群中最優的棲息地，Hrn1、Hrn2、Hrn3和Hrn4是隨機選擇的4個棲息地，滿足rn1、rn2、rn3、rn4、i∈[1，N]且rn1 ≠rn2 ≠rn3 ≠rn4 ≠i.

由式(7)可以看出，差分擾動操作將4個隨機選擇的棲息地同一維SIV通過差分計算得到差分向量，將差分向量賦予權值，加到棲息地Hi的相應SIV上，從而實現對該SIV值的擾動，生成差分SIV.差分擾動可以使棲息地之間共享更多樣化的信息，增加了種群多樣性.式(8)的原理與式(7)類似，兩種不同的差分擾動操作同時使用是為了確保足夠的種群多樣性.

縮放因子α是用來調整差分擾動范圍的參數，兩種差分擾動操作均采用了指數縮放因子，避免縮放因子參數設置步驟，并增加算法的可操作性，其計算如式(9)所示：

α=randβ

(9)

其中，β是指數參數.

除了兩種差分擾動操作外，對于在差分遷移算子中同時融入的原直接取代式的遷移操作不做修改，但對遷出棲息地的選擇，采用了榜樣學習法替換輪賭選擇法[11]，有利于大幅降低算法計算復雜度.

差分遷移算子的偽代碼如算法4所示.

算法4. 差分遷移算子

01 fori=1 toNdo

02 通過式(9)計算縮放因子α

03 forj=1 toddo

04 ifrand<λithen

05 用榜樣學習法選出遷出的棲息地HSI

06 通過式(4)更新Hi(SIVj)

07 else

08 ifrand<0.5 then

09 通過式(7)更新Hi(SIVj)

10 else

11 通過式(8)更新Hi(SIVj)

12 end if

13 end if

14 end for

15 end for

由于差分遷移算子融入了原直接取代式遷移操作，故其具有一定的局部搜索能力，又由于差分擾動操作增加了種群多樣性，故相較于原遷移算子整體上提升了全局搜索能力，兩種能力的結合也使得算法的探索和開采得以平衡.

3.3 趨優變異算子

對于BBO算法的變異算子，去掉了其隨機方向的變異操作，從而克服了可能破壞優質解的缺陷，又融入了式(10)所示的趨優操作彌補變異操作的缺失，形成趨優變異算子.

Hi(SIVj)←Hbest(SIVcn)，cn=ceil(rand*d)

(10)

由式(10)可以看出，變異棲息地Hi的SIV直接接受當前迭代種群中最優的棲息地Hbest的隨機一個SIV，從而可以向Hbest方向迅速收斂.通常Hbest是當前迭代種群中最接近全局最優解的棲息地，故趨優操作實質是使所有變異棲息地向最優解位置迅速聚集，而采用隨機的SIV可以防止種群中出現大量相似的棲息地，避免算法陷入局部最優.

此外，趨優變異算子采用線性降方法計算棲息地的變異率，如式(11)所示：

mp=mpmax-(mpmax-mpmin)*(t-1)/MaxDT

(11)

其中，mp是變異率，t是當前迭代次數，mpmax和mpmin分別是mp取值的上界和下界.由式(11)可知，隨著迭代次數t線性增加，變異率mp的值逐漸降低.在算法優化過程前期，mp的值較大，更傾向于執行趨優變異算子，較差的棲息地可以向當前迭代種群中最優的棲息地方向迅速收斂；在算法優化過程后期，大量棲息地聚集在某一區域，mp的值較小，執行趨優變異的概率較小，一定程度上避免了優質解被破壞.相較于原變異率計算法方法，線性降方法計算變異率還降低了計算復雜度.

趨優變異算子的偽代碼如算法5所示.

算法5. 趨優變異算子

01 通過式(11)計算變異率mp

02 fori=1 toNdo

03 forj=1 toddo

04 ifrand

05 通過式(10)更新Hi(SIVj)

06 end if

07 end for

08 end for

3.4 DGBBO算法總流程

除上述改進外，還將BBO算法的精英保留策略換成了貪婪選擇法[11]，在保證棲息地HSI總是有效的前提下，將遷入率計算步驟移至算法的迭代循環外[12]，這些改進能夠進一步降低了計算復雜度，最終形成了DGBBO算法.

總的來說，DGBBO算法在BBO算法的基礎上，整體提升了全局搜索能力，平衡了探索和開采，加快了收斂速度，大幅度降低了計算復雜度.DGBBO算法總流程偽代碼如算法6所示.

對比DGBBO算法和BBO算法，它們的相同點在于均采用遷移和變異兩個主要算子更新種群.它們的不同點分為三方面：1.從算法3和算法6的對比中可以看出，總流程上DGBBO算法的棲息地遷入率計算步驟在迭代循環外，采用榜樣學習法選擇遷出棲息地從而不需要計算遷出率，采用貪婪選擇法從而每次迭代需對棲息地排序一次，而BBO算法的遷入遷出率計算步驟均在迭代循環內，采用精英保留機制每次迭代需對所有棲息地排序兩次；2.從算法1和算法4的對比中可以看出，DGBBO算法的差分遷移算子包含三種不同的操作，分別是直接取代式的遷移操作和兩種差分擾動操作，不僅對執行遷入的棲息地進行了更新，還對未執行遷入的棲息地進行了更新，而BBO算法的遷移算子只采用直接取代式的遷移操作更新執行遷入的棲息地，對不執行遷入的棲息地不更新；3.從算法3和算法5的對比中可以看出，DGBBO算法的趨優變異算子其變異率的計算步驟在種群循環外，即每次迭代所有棲息地都使用同一變異率，而BBO算法的變異算子其變異率計算步驟在種群循環內，每個棲息地都擁有各自的變異率且這些變異率各不相同.

表1 基準函數Table 1 Benchmark functions

算法6. DGBBO算法總流程

01 設置相關參數，隨機初始化種群

02 評價每個棲息地的HSI，按HSI由優至劣對種群排序

03 計算每個棲息地的遷入率

04 fort= 1 toMaxDTdo

05 通過算法4的差分遷移算子更新種群

06 通過算法5的趨優變異算子更新種群

07 對每個棲息地進行越界限制

08 評價每個棲息地的HSI，按HSI由優至劣對種群排序，執行貪婪選擇法更新種群

09 end for

10 輸出最優解

4 仿真實驗與分析

為驗證DGBBO算法的優化性能和運行速度，在一組常用基準函數上進行了仿真實驗，這些基準函數如表1所示.所有實驗均在操作系統為 Windows 7、CPU為主頻3.10GHz和內存為4GB的PC上進行的，編程語言采用MATLAB R2014a.

4.1 DGBBO算法自身對比實驗

第一組實驗用DGBBO算法與其變體算法進行對比，這些變體算法包括：DRBBO算法，即差分遷移和原始變異的BBO算法；EGBBO算法，即榜樣選擇法的原始遷移和趨優變異的BBO算法；RGBBO算法，即輪賭選擇法的原始遷移和趨優變異的BBO算法.

4種算法分別在50維f1-f15和200維f16上進行了測試.為公平起見，統一設置每種算法的種群數量N= 20，最大迭代次數MaxDT=4000，最大遷入和遷出率分別為I=1，E=1，變異率mp的取值上限和下限分別為mpmax=0.03，mpmin=0.001，指數參數β=4.為避免偶然事件，4種算法在每個基準函數上分別獨立運行50次，取統計得到平均值(Mean)、標準差值(Std)和運行時間(Time/s，s表示單位為“秒”)用于對比.4種算法的結果對比如表2所示，其中，加粗的為最優結果.

對比DGBBO算法和DRBBO算法可以看出，擁有差分遷移算子的DGBBO算法獲得平均值和標準差值總是更優，且在一些基準函數上優勢巨大，運行時間上兩者沒有明顯差距.對比DGBBO算法和EGBBO算法可以看出，擁有趨優變異算子的DGBBO算法獲得的平均值和標準差值總是更優，且在一些基準函數上優勢巨大，但運行時間更長.對比EGBBO算法和RGBBO算法可以看出，兩種算法獲得的平均值和標準差值都不理想，但在運行時間上，EGBBO算法優勢明顯.總的來說，DGBBO算法獲得的的平均值和標準差值總是4種算法中最優的，EGBBO算法的運行時間總是4種算法中最短的.

表2 DGBBO算法與其變體算法的對比Table 2 Comparisons among DGBBO and its variants

4種算法在16個函數上的收斂曲線對比如圖2所示，其中，橫坐標是迭代次數，縱坐標是平均優化結果.從圖2可以看出，除了DGBBO算法外，其它算法都出現了過早收斂，在f6、f8、f9和f10上，DGBBO算法用了很少的迭代次數便搜索到了函數最優解，特別是在f6上，幾乎看不到DGBBO算法的收斂曲線，其快速的收斂速度得以體現.

第一組實驗的結果對比表明，榜樣學習法對于算法優化性能影響不明顯，但對降低算法運行時間有明顯作用，差分遷移算子和趨優變異算子對增強算法的優化性能，加快算法的收斂速度作用明顯，雖然差分遷移算子的使用增加了算法的運行時間，但綜合考慮優化性能和運行時間的平衡，DGBBO算法的結果是最可取的，從而也證明了本研究對BBO算法的這3項改進都是不可或缺的.

4.2 DGBBO算法與同類算法對比實驗

第二組實驗用DGBBO與state-of-the-art同類進行對比，由于BBO算法適用于離散型優化問題，在連續型優化問題上性能較差，而本文實驗仿真的是連續型優化問題，故沒有用BBO算法作為對比算法，而使用在連續型優化問題上表現更優的BBO改進及混合算法用于對比.

圖2 DGBBO與其變體算法的收斂曲線Fig.2 Convergence curve of DGBBO and its variants

首先，用DGBBO算法對比LBBO算法[13].選取LBBO算法進行對比是因為該算法具有很強的競爭性.

2種算法分別在不同維度的16個基準函數上進行實驗，它們的最大迭代次數MaxDT動態調整以適應不同維度的優化問題，為公平起見，它們種群數量統一設置為N= 20，DGBBO算法的其它參數不變，LBBO的其它參數設置同其相應參考文獻，2種算法在每個基準函數上獨立運行50次,對比結果如表3所示.

從表3可以看出，大多數情況下，DGBBO算法比LBBO算法獲得了更優的平均值和標準差值，在一些基準函數上，DGBBO算法的優勢巨大.例如，在 100維f1上，DGBBO算法的平均值和標準差值精度分別達到1e-162和1e-162，而LBBO算法只分別達到1e-27和1e-26.在運行時間的對比中，DGBBO算法的運行時間總是比LBBO算法更少.

其次，用DGBBO算法與BBOFWA算法[14]、POLBBO算法[15]和PRBBO算法[16]進行對比.這三種算法都是近幾年提出的BBO改進及混合算法，具有很強的競爭性.

對比算法的結果分別取自其相應的參考文獻，由于不同文獻對算法的測試函數集不同，故只選取4種算法在相同維度的相同基準函數上獲得的結果進行對比，為使對比結果可靠，DGBBO算法的最大函數評價次數(MNFE)總是小于對比算法.4種算法的結果對比如表4所示，其中，NA表示原文獻未提供該數據.

從表4可以看出，在MNFE更少的前提下，DGBBO算法在14個基準函數中獲得了11次最優或與其它算法并列最優的平均值及10次最優或與其它算法并列最優的標準差值.在f7和f12上，雖然DGBBO算法獲得的結果不如POLBBO算法和PRBBO算法，但差距很小.在f14上，DGBBO算法與PLOBBO算法和PRBBO算法獲得了相同的平均值，在標準差值上略微不如另外兩種算法.在f5上，DGBBO算法的結果較POLBBO算法和PRBBO算法差距較大，但是另外兩種算法的MNFE約是DGBBO算法的10倍.

第二組實驗結果表明，DGBBO算法與state-of-the-art同類算法相比，其結果是很可取的.

4.3 DGBBO算法與其它類算法對比實驗

第三組實驗用DGBBO算法與state-of-the-art其它類算法進行對比，選取的對比算法有SLPSO算法[17]、DELLU算法[18]和ILABC算法[19]，選取這些算法對比是因為它們包含了近年來提出的ABC改進算法、PSO改進算法和DE改進算法，具有很強競爭性，在同類算法中又具有一定代表性.

表4 DGBBO算法與同類算法的對比(d=30)Table 4 Comparisons among DGBBO and the same types of algorithms(d=30)

對比算法的結果分別取自其相應的參考文獻，只選取4種算法在相同維度的相同基準函數上獲得的結果進行對比，DGBBO算法的MNFE總是小于或近似等于其它算法.4種算法的結果對比如表5所示.

從表5可以看出，DGBBO算法在所有情況下獲得的平均值都是最優或者與其它算法并列最優的，其標準差值雖然在f13、f14和f16上不如其它算法，但在MNFE遠小于其它算法的前提下也達到了很高的精度.

第三組實驗結果表明，DGBBO算法與state-of-the-art其它類算法相比，其結果依然是很可取的.

4.4 DGBBO算法實驗結果討論

以表3結果為例，對DGBBO算法進行討論.觀察DGBBO算法獲得的平均值可以發現，不論在30維、50維還是100維基準函數上，其在多數情況下都獲得了高精度的結果，例如，在f1和f3上，DGBBO算法的結果精度達到了三位數，在f6、f8、f9和f10上，DGBBO算法搜索到了函數最優解，相比之下，LBBO算法的結果精度則不理想，從而證明了DGBBO算法的尋優能力顯著，在多數優化問題上能夠搜索到優化問題的最優解或高精度解.

當基準函數維度的增加時，問題的復雜度進一步增加，通常一個算法在處理更高維度的優化問題時，其解的精度會有所下降.橫向觀察DGBBO算法在不同維度的同一基準函數的結果發現，除了f5外，DGBBO算法在所有基準函數上的結果精度都沒有明顯下降，由于測試更高維基準函數時增加了最大迭代次數，所以在f1、f2、f3、f4、f6、f8、f9，f10、f13、f14、f15和f16上，DGBBO算法的結果保留了高精度或得到了更高的精度，相比之下，LBBO算法在多數情況下的結果精度有所下降，從而再次證明DGBBO算法的尋優能力顯著，還證明了其具有較強的穩定性，在面對不同復雜度的優化問題時能夠保持較好的尋優能力.表3中DGBBO算法獲得的標準差值同樣體現出了其較強的穩定性.

對于DGBBO算法的收斂速度已在圖2的收斂曲線對比中進行討論，本節不再重復論述.

綜上所述，DGBBO算法在尋優能力、穩定性和收斂速度上表現優良，其優秀的優化性能得以體現.

4.5 DGBBO算法計算復雜度分析

在相同的運行環境下，影響算法運行時間的因素主要有二，一是最大函數評價次數，這是由于算法在優化過程中，對候選解的函數評價過程最為耗時；二是算法自身流程的復雜程度.本文在運行時間的對比實驗中，設置所有算法具有相同的種群數量和最大迭代次數，使它們的MNFE近似相等，故DGBBO算法運行速度快的原因不在于MNFE，而是由于在流程設計中從多個角度降低了計算復雜度.

參照BBO算法，對DGBBO算法的計算復雜度進行對比分析.對于算法的總流程，DGBBO算法將棲息地遷入率計算移至迭代循環外，又因為在交叉遷移中采用榜樣學習法選擇遷出棲息地，不需要棲息地的遷出率，因此在整個算法優化過程中，只需要對所有棲息地的遷入率計算1次，其計算次數為N，而BBO算法每次迭代都需要對所有棲息地的遷入率和遷出率進行計算，其計算次數為2*N*MaxDT，故DGBBO算法大幅降低了計算復雜度.BBO算法每次迭代都采用的是精英保留策略更新種群，需對所有棲息地排序2次，若以簡單排序方法為例，其計算次數為N2，而DGBBO算法采用貪婪選擇法更新種群，每次迭代只需對所有棲息地排序一次，其計算次數為N2/2，再次降低計算復雜度.遷移算子的對比中，雖然DGBBO算法的差分遷移算子較BBO算法的原遷移算子多出一些判斷步驟，但沒有增加額外的循環步驟，BBO算法采用輪賭選擇法選擇遷出棲息地，其計算次數大于1小于N，平均計算次數為(1+N)/2，而DGBBO算法采用的榜樣學習法選擇遷出棲息地，其計算次數為1，整體上DGBBO算法降低了計算復雜度.在變異算子的對比中，DGBBO算法采用線性降方法計算變異，每次迭代只需要對變異率計算1次，而BBO算法每次迭代需要對每個棲息地都計算變異率，計算次數為N，且變異率計算需要先計算棲息地物種數量概率，其計算量較大，故DGBBO算法進一步大幅降低計算復雜度.

表5 DGBBO算法與其它類算法的對比(d=30)Table 5 Comparisons among DGBBO and the other types of algorithms(d=30)

綜上所述，DGBBO算法在BBO算法的基礎上，從多個角度降低計算復雜度，從而達到了減少了算法運行時間的目的，表3中算法的運行時間對比也驗證了該結論.

4.6 實驗總結

為驗證DGBBO算法的優化性能和運行速度，在一組常用基準函數上進行大量仿真實驗.實驗結果證明了DGBBO算法中3項主要的改進都是不可或缺的，又通過與state-of-the-art同類型及不同類型算法的結果進行對比、討論及分析，表明了DGBBO算法尋優能力顯著，穩定性強，收斂速度快，運行時間少，驗證了其優秀的優化性能.

5 結束語

為了增強BBO算法的優化性能，降低其運行的時間消耗，根據算法改進動機，提出了一種差分遷移和趨優變異的生物地理學優化算法(DGBBO).將兩種差分擾動操作與BBO算法的遷移操作有機融合，形成差分遷移算子，提升全局搜索能力并平衡探索和開采；將趨優操作融入到BBO算法的變異算子中，替換原變異操作，形成趨優變異算子，克服了原變異算子存在的缺陷，加快收斂速度；又從多個角度降低算法的計算復雜度.在一組常用基準函數上進行了仿真實驗，與其它state-of-the-art算法進行對比，驗證了DGBBO算法優秀的優化性能.下一步研究會將算法用于工程領域，處理現實中更為復雜優化問題[20].

：

[1] Liu Y，Mu C，Kou W，et al.Modified particle swarm optimization-based multilevel thresholding for image segmentation [J].Soft Computing，2015，19(5)：1311-1327.

[2] Kiran M S，Hakli H，Gunduz M，et al.Artificial bee colony algorithm with variable search strategy for continuous optimization [J].Information Sciences，2015，300：140-157.

[3] Storn R，Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces [J].Journal of Global Optimization，1997，11(4)：341-359.

[4] Simon D.Biogeography-based optimization [J].IEEE Transactions on Evolutionary Computation，2008，12(6)：702-713.

[5] Ma H.An analysis of the equilibrium of migration models for biogeography-based optimization [J].Information Sciences，2010，180(18)：3444-3464.

[6] Feng Q，Liu S，Zhang J，et al.Biogeography-based optimization with improved migration operator and self-adaptive clear duplicate operator [J].Applied Intelligence，2014，41(2)：563-581.

[7] Guo W，Wang L，Ge S S，et al.Drift analysis of mutation operations for biogeography-based optimization [J].Soft Computing，2015，19(7)：1-12.

[8] Zheng Y J，Ling H F，Wu X B，et al.Localized biogeography-based optimization [J].Soft Computing，2014，18(11)：2323-2334.

[9] Guo W，Chen M，Wang L，et al.Backtracking biogeography-based optimization for numerical optimization and mechanical design problems [J].Applied Intelligence，2016，44(4)：894-903.

[10] Gong W Y，Cai Z H，Ling C X.DE/BBO：a hybrid differential evolution with biogeography-based optimization for global numerical optimization [J].Soft Computing，2010，15(4)：645-665.

[11] Zhang Xin-ming，Yin Xin-xin，Tu Qiang.High-dimensional multilevel thresholding based on BBO with dynamic migration and salt & pepper mutation [J].Optics and Precision Engineering，2015，23(10)：2943-2951.

[12] Zhang Xin-ming，Tu Qiang，Yin Xin-xin.Efficient BBO algorithm based on Hybrid migration and its application in image segmentation [J].Journal of Frontiers of Computer Science and Technology，2016，10(10)：1459-1468.

[13] Simon D，Omran M G H，Clerc M.Linearized biogeography-based optimization with re-initialization and local search [J].Information Sciences，2014，267：140-157.

[14] Zhang B，Zhang M X，Zheng Y J.A hybrid biogeography-based optimization and fireworks algorithm [C].IEEE Congress on Evolutionary Computation (CEC)，2014：3200-3206.

[15] Xiong G，Shi D，Duan X.Enhancing the performance of biogeography-based optimization using polyphyletic migration operator and orthogonal learning [J].Computers & Operations Research，2014，41(1)：125-139.

[16] Feng Q，Liu S，Zhang J，et al.Improved biogeography-based optimization with random ring topology and Powell′s method [J].Applied Mathematical Modelling，2016，41：630-649.

[17] Cheng R，Jin Y.A social learning particle swarm optimization algorithm for scalable optimization [J].Information Sciences，2015，291(6)：43-60.

[18] Zhou Xiao-gen，Zhang Gui-jun，Hao Xiao-hu，et al.Differential evolution algorithm based on local lipschitz underestimate supporting hyperplanes [J].Chinese Journal of Computers，2016，39(12)：2631-2651.

[19] Gao W F，Huang L L，Liu S Y，et al.Artificial bee colony algorithm based on information learning [J].IEEE Transactions on Cybernetics，2015，45(12)：2827-2839.

[20] Xu X，Shi X W.Multi-objective based spectral unmixing for hyperspectral images [J].Isprs Journal of Photogrammetry & Remote Sensing，2017，124：54-69.

附中文參考文獻：

[11] 張新明，尹欣欣，涂 強.動態遷移和椒鹽變異融合生物地理學優化算法的高維多閾值分割 [J].光學精密工程，2015，23(10)：2943-2951.

[12] 張新明，涂 強，尹欣欣.混合遷移的高效BBO算法及其在圖像分割中的應用 [J].計算機科學與探索，2016，10(10)：1459-1468.

[18] 周曉根，張貴軍，郝小虎，等.一種基于局部Lipschitz下界估計支撐面的差分進化算法 [J].計算機學報，2016，39(12)：2631-2651.