基于微分進化的混合生物地理學約束優化算法

徐以坤，余 洋，米增強，趙 彤

（華北電力大學 新能源電力系統國家重點實驗室，河北 保定071003）

0 引 言

BBO 算法［1］模擬生物種群在棲息地間的遷徙機制，來實現種群信息的共享，從而達到尋優的目的。BBO 算法結構簡單，控制參數少，收斂速度快，具有出色的信息利用能力，已被成功地應用于多個工程領域［2－4］。

然而，由于搜索能力和利用能力沒有得到有效的平衡，BBO 算法容易陷入局部最優解而發生 “早熟”現象。為了提升BBO 算法的全局優化能力，加快收斂速度，相關的研究人員提出了許多改進方案［5－7］。這些改進方案均在一定程度上平衡了BBO的搜索能力和利用能力，提升了BBO 的全局優化能力，但已有的改進生物地理學優化算法大多應用于無約束優化，用于解決約束優化的改進BBO算法很少。

本文研究工作的創新點主要體現在以下兩方面：第一，融合BBO 的利用能力和DE 的搜索能力，提出了一種混合生物地理學優化算法BBO－DE；第二，在提出的改進算法中引入了基于可行性的約束處理機制，將BBO 算法推廣至約束優化領域。

1 BBO 算法

BBO 算法通過模擬生物物種在不同棲息地間移動和分布的情況來尋找最優解，在這一算法中，每一個棲息地對應問題的一個可能解，居住適應度指標 （habitat suitability index，HSI）用來衡量棲息地適宜居住的程度，與棲息地所能支撐的物種數成正相關，對應于其它進化算法中評價解優劣的適應度函數，影響棲息地居住性的變量稱為適應度變量（suitability index variables，SIVs），對應解的元素變量。

在BBO 算法中，每個棲息地都需要經過遷徙和變異兩個算子，逐步向最優解進化。遷徙算子模擬了生物地理學的遷徙機制，以實現種群中不同個體間的信息交互。在遷徙算子中，棲息地的每一個SIV 都會被概率性地共享。高HSI的棲息地具有低遷入率和高遷出率，其SIV 傾向于遷入其它棲息地，被其它棲息地共享；低HSI的棲息地具有高的遷入率和低的遷出率，傾向于接受來自高HSI棲息地的SIV，以改善自身居住適應性。

目前，相關研究人員已提出了多種遷徙數學模型，本文在此僅介紹基本的線性遷徙數學模型。為便于說明，本文假定種群中有NP 個棲息地，棲息地用D 維向量表示，Xij表示第i個棲息地Xi的第j 維適應度變量，I和E 分別為可能的最大遷入率和最大遷出率，Si為棲息地Xi的物種數，Smax為棲息地可能容納的最大物種數。線性遷徙數學模型中Xi的遷入率λi和遷出率μi 可按如下公式進行計算

遷徙算子的具體機制如下：對于每一個棲息地Xi的每一維適應度變量Xij，依據該棲息地遷入率λi來確定其是否需要進行遷徙操作，即隨機產生 （0，1）之間的一個數值，將其與遷入率λi進行比較，若其小于遷入率λi，那么Xij為待遷入適應度變量。然后，在其余棲息地中，依據各自遷出概率μ的大小利用輪盤賭選出需要遷出變量的棲息地，用選出棲息地第j維變量替代Xij。

BBO 算法的變異算子模擬了突發狀況使得棲息地物種數量急劇變化的情況，以增加種群的多樣性。每個棲息地Xi的變異率mi取決于這一棲息地的先驗存在概率Pi，具體計算如下

式中：mmax——最大變異率，Pmax——所有棲息地先驗存在概率的最大值。變異算子的具體機制如下：對于每一棲息地Xi的每一個適應度變量Xij，依據變異率mi確定其是否需要進行變異操作，即隨機產生的 （0，1）之間的數值若小于變異概率mi，則在相應給定的邊界范圍內隨機產生一個適應度變量替代Xij。

2 BBO－DE算法

從上述關于BBO 算法的描述中可以看到，在遷徙操作中，優秀棲息地將自身適應度變量與其它棲息地進行共享，以提升其它棲息地的適應度水平，從而使得種群中已有的信息獲得了較好的利用，但是在整個遷徙過程中并沒有新的適應度變量產生，可以說，遷徙算子為最大程度地利用已有的種群信息，犧牲了種群多樣性；變異算子使用給定邊界內隨機產生的適應度變量替代個體中已有的變量，只能在一定程度上增加種群多樣性，搜索新的區域。所以生物地理學優化算法的利用能力強，而其搜索能力相對較弱，兩者之間不能有效平衡。

眾所周知，DE算法是一種性能優異的全局優化算法，其控制參數少，收斂速度快，穩健性高，搜索能力出眾。變異算子是DE算法中極為重要的一項操作，可以說，DE算法卓越的搜索能力主要歸功于變異算子。在變異算子中，利用不同個體變量之間的加權差值對隨機選擇的母本個體進行擾動，以產生相應的變異個體。在此我們僅簡要介紹幾種應用較為廣泛的變異策略［8，9］。

其中，r1－r5為 ［1，NP］內互不相同的隨機整數，F 為變異參數，Yi表示DE 進化策略得到的變異個體，Yij表示變異個體Yi的第j維變量。

本文引入微分進化算法的變異算子與生物地理學優化算法進行混合，提出一種基于DE 的混合生物地理學優化算法 （BBO－DE），以平衡算法的搜索能力和利用能力，提升BBO 全局優化能力。在BBO－DE，種群中的所有個體依照基本生物地理學優化算法進行更新，另外，最差的30%個體還需按照rand／1，rand to best／1和rand／2這3種變異策略進行進化。最差的一部分個體依據微分進化變異策略更新，可以探索新的區域，增加種群多樣性，使算法快速跳出局部最優解，提升算法的搜索能力，加快收斂速度；基于DE變異策略所得到的優秀個體可以在遷徙策略中將自身適應度變量與其它個體共享，提升整個種群的適應度水平。

為了解決約束優化問題，將Deb提出的基于可行性的約束處理機制引入改進算法，這一約束處理機制不需要額外的控制參數，原理簡單，應用方便，具體如下［10］：①可行個體優于不可行個體；②對于兩個可行個體，適應度小的個體較優；③對于兩個不可行個體，約束違反度小的個體較優。

若進化過程中產生的新變量違反邊界約束，在給定邊界范圍內隨機產生的一個變量來替代它，以保持種群進化始終在給定的邊界范圍內進行。改進算法BBO－DE 的偽代碼如圖1所示，其中Ci為母本個體按照基本BBO 進化策略所得到的新個體，TempCi為最差的部分個體依據微分進化變異策略所得到新個體。

圖1 BBO－DE算法流程

3 仿真實驗與結果分析

為了驗證改進算法的有效性和先進性，在該部分進行了一系列仿真實驗，并將BBO－DE算法與基本BBO 算法和DE算法進行比較，兩種基本算法同樣采用Deb提出的基于可行性的約束處理機制解決約束優化問題。為驗證算法性能，選取了8個典型標準測試函數，關于測函數的詳細信息可以從文獻 ［11］中得到。從目標函數類型，約束函數類型，約束函數個數，解的維度等方面來說，這些測試函數相互之間各不相同，表1給出了測試函數的主要特征［8］。

3.1 參數設置

BBO－DE的參數設置如下：種群規模NP＝100，最大遷入概率I＝1，最大遷出概率E＝1，最大變異概率mmax＝0.005，F＝0.8，G01、G02、G04 最大迭代次數分別為300、750、150，G06－G09 的最大迭代次數分別為200、1200、50、600，G12的最大迭代次數為50。

表1 測試函數的主要特征

基本DE算法采用rand／1變異策略。為了保證比較的公正性，對于相同參數，基本BBO 算法和DE算法與BBODE算法保持一致，基本BBO 的其余參數設置與文獻 ［1］相同，DE算法的交叉參數CR＝0.8。根據改進算法的流程可知，BBO－DE每次迭代需要評價適應度函數和約束函數190次，而基本BBO 與DE 每次迭代執行適應度函數和約束函數評價100次，基本BBO 與DE 迭代次數的設置應保證參與比較的3 種算法適應度函數評價次數 （number of fitness function evaluations，NFFEs）一致。

由于算法可能存在波動性，對每個測試函數獨立運行30次。所有實驗均以Matlab 7.0 為平臺進行，實驗結果將從以下兩方面進行分析：

（1）基于30次獨立運行所得的優化結果的統計特征值（最優值、平均值及最差值），比較3種算法的優化能力。

（2）通過平均進化曲線比較算法的收斂速率。

3.2 算法性能

表2給出了3種算法在測試函數上優化結果的統計特征值，表中黑體數值表示3種算法所得優化結果中的最優值。從表2 可以看出：對于6 個測試函數 （G01，G04，G06，G08，G09及G12），BBO－DE 在30 次獨立運行中均能收斂至全局最優解，對于測試函數G02，BBO－DE所得最優值與已知最優解非常接近，對于測試函數G07，BBO－DE在一定次數的運行中能夠收斂至全局最優解，優化結果的平均值和最差值接近全局最優解。與基本BBO 算法相比，BBO－DE在選定的8 個測試函數上具有明顯優勢；除測試函數G06和G08，BBO－DE 在選定的測試函數上明顯優于DE算法，在G06和G08上，BBO－DE和DE 優化結果的統計特征值相同。

表2 BBO－DE、BBO 和DE在測試函數上的優化結果

圖2為算法BBO－DE，基本BBO 和DE 的平均收斂特性，從圖中可以看出：①基本BBO 算法在進化初期具有較快的收斂速度，但在進化中后期，算法易陷入局部最優解，這說明BBO 雖有較強的利用能力，但缺乏相應的搜索能力與之平衡；②相對基本算法BBO 和DE，BBO－DE算法能夠輕松跳出局部最優解，以更快的速度收斂至全局最優解。

3.3 實驗結果分析

從以上實驗結果可以看出：

（1）改進算法能夠在選定的8個測試函數上能夠得到全局最優解 （或非常接近全局最優解），而且具有較高的穩定性，這說明BBO－DE 是一種能夠較好解決約束優化的改進生物地理學優化算法，為將BBO 推廣至約束優化領域提供了一種方法。

（2）在解的質量和收斂速度兩方面，BBO－DE 算法明顯優于基本BBO 和DE，這說明算法BBO－DE 采用的混合策略能夠合理地將BBO 算法的利用能力和DE 算法的搜索能力結合起來，實現算法利用能力與搜索能力的平衡，提升全局優化能力。

4 結束語

本文提出了一種基于DE 的混合生物地理學優化算法BBO－DE，該算法將BBO 的利用能力與DE的搜索能力相結合，以平衡BBO 算法的利用能力和搜索能力，提升BBO算法的全局優化能力。而且，本文還將Deb提出的基于可行性的約束處理機制引入到改進算法之中，將BBO 算法拓展至約束優化領域。

為驗證改進算法性能，將BBO－DE 應用于選定的8個測試函數，實驗結果表明BBO－DE 在選定的測試函數上能夠得到全局最優解 （或者接近全局最優解）具有而且較高的穩定性。與基本BBO 和DE 相比，BBO－DE 算法在最終解的質量上和收斂速度上具有明顯優勢。因此，BBO－DE是一種高效、可行的約束處理算法。

圖2 算法BBO－DE、BBO 和DE的平均收斂特性

［1］Simon D.Biogeography－based optimization ［J］.IEEE Transactions on Evolutionary Computation，2008，12 （6）：702－713.

［2］Kaur K，Rattan M，Patterh MS.Biogeography－based optimisation of cognitive radio system ［J］.International Journal of Electronics，2014，101 （1）：24－36.

［3］Xiong G，Shi D，Duan X.Multi－strategy ensemble biogeography－based optimization for economic dispatch problems ［J］.Applied Energy，2013，111：801－811.

［4］Wang L，Xu Y.An effective hybrid biogeography－based optimization algorithm for parameter estimation of chaotic systems［J］.Expert Systems with Applications，2011，38 （12）：15103－15109.

［5］Ma H.An analysis of the equilibrium of migration models for biogeography－based optimization ［J］.Information Sciences，2010，180 （18）：3444－3464.

［6］Li X，Yin M.Multi－operator based biogeography based optimization with mutation for global numerical optimization ［J］.Computers ＆ Mathematics with Applications，2012，64 （9）：2833－2844.

［7］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：125－139.

［8］Liu H，Cai Z，Wang Y.Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization ［J］.Applied Soft Computing，2010，10 （2）：629－640.

［9］Gong W，Cai Z，Ling CX.DE／BBO：A hybrid differential evolution with biogeography－based optimization for global numerical optimization ［J］.Soft Computing，2010，15 （4）：645－665.

［10］HU Kuan，CHANG Xinlong，SONG Bifeng，et al.Genetic algorithm to solve optimization problem with equality constrains［J］.Journal of Shanghai Jiaotong University，2011，45 （7）：966－969 （in Chinese）. ［胡寬，常新龍，宋筆鋒，等.求解含等式約束優化問題的遺傳算法 ［J］.上海交通大學學報，2011，45 （7）：966－969.］

［11］Boussad I，Chatterjee A，Siarry P，et al.Biogeographybased optimization for constrained optimization problems［J］.Computers ＆ Operations Research，2012，39 （12）：3293－3304.