基于微分進(jìn)化的混合生物地理學(xué)約束優(yōu)化算法

徐以坤，余 洋，米增強(qiáng)，趙 彤

（華北電力大學(xué) 新能源電力系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，河北 保定071003）

0 引 言

BBO 算法［1］模擬生物種群在棲息地間的遷徙機(jī)制，來實(shí)現(xiàn)種群信息的共享，從而達(dá)到尋優(yōu)的目的。BBO 算法結(jié)構(gòu)簡(jiǎn)單，控制參數(shù)少，收斂速度快，具有出色的信息利用能力，已被成功地應(yīng)用于多個(gè)工程領(lǐng)域［2－4］。

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

本文研究工作的創(chuàng)新點(diǎn)主要體現(xiàn)在以下兩方面：第一，融合BBO 的利用能力和DE 的搜索能力，提出了一種混合生物地理學(xué)優(yōu)化算法BBO－DE；第二，在提出的改進(jìn)算法中引入了基于可行性的約束處理機(jī)制，將BBO 算法推廣至約束優(yōu)化領(lǐng)域。

1 BBO 算法

BBO 算法通過模擬生物物種在不同棲息地間移動(dòng)和分布的情況來尋找最優(yōu)解，在這一算法中，每一個(gè)棲息地對(duì)應(yīng)問題的一個(gè)可能解，居住適應(yīng)度指標(biāo) （habitat suitability index，HSI）用來衡量棲息地適宜居住的程度，與棲息地所能支撐的物種數(shù)成正相關(guān)，對(duì)應(yīng)于其它進(jìn)化算法中評(píng)價(jià)解優(yōu)劣的適應(yīng)度函數(shù)，影響棲息地居住性的變量稱為適應(yīng)度變量（suitability index variables，SIVs），對(duì)應(yīng)解的元素變量。

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

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

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

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

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

2 BBO－DE算法

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

眾所周知，DE算法是一種性能優(yōu)異的全局優(yōu)化算法，其控制參數(shù)少，收斂速度快，穩(wěn)健性高，搜索能力出眾。變異算子是DE算法中極為重要的一項(xiàng)操作，可以說，DE算法卓越的搜索能力主要?dú)w功于變異算子。在變異算子中，利用不同個(gè)體變量之間的加權(quán)差值對(duì)隨機(jī)選擇的母本個(gè)體進(jìn)行擾動(dòng)，以產(chǎn)生相應(yīng)的變異個(gè)體。在此我們僅簡(jiǎn)要介紹幾種應(yīng)用較為廣泛的變異策略［8，9］。

其中，r1－r5為 ［1，NP］內(nèi)互不相同的隨機(jī)整數(shù)，F(xiàn) 為變異參數(shù)，Yi表示DE 進(jìn)化策略得到的變異個(gè)體，Yij表示變異個(gè)體Yi的第j維變量。

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

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

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

圖1 BBO－DE算法流程

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1 參數(shù)設(shè)置

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

表1 測(cè)試函數(shù)的主要特征

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

由于算法可能存在波動(dòng)性，對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次。所有實(shí)驗(yàn)均以Matlab 7.0 為平臺(tái)進(jìn)行，實(shí)驗(yàn)結(jié)果將從以下兩方面進(jìn)行分析：

（1）基于30次獨(dú)立運(yùn)行所得的優(yōu)化結(jié)果的統(tǒng)計(jì)特征值（最優(yōu)值、平均值及最差值），比較3種算法的優(yōu)化能力。

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

3.2 算法性能

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

表2 BBO－DE、BBO 和DE在測(cè)試函數(shù)上的優(yōu)化結(jié)果

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

3.3 實(shí)驗(yàn)結(jié)果分析

從以上實(shí)驗(yàn)結(jié)果可以看出：

（1）改進(jìn)算法能夠在選定的8個(gè)測(cè)試函數(shù)上能夠得到全局最優(yōu)解 （或非常接近全局最優(yōu)解），而且具有較高的穩(wěn)定性，這說明BBO－DE 是一種能夠較好解決約束優(yōu)化的改進(jìn)生物地理學(xué)優(yōu)化算法，為將BBO 推廣至約束優(yōu)化領(lǐng)域提供了一種方法。

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

4 結(jié)束語

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

為驗(yàn)證改進(jìn)算法性能，將BBO－DE 應(yīng)用于選定的8個(gè)測(cè)試函數(shù)，實(shí)驗(yàn)結(jié)果表明BBO－DE 在選定的測(cè)試函數(shù)上能夠得到全局最優(yōu)解 （或者接近全局最優(yōu)解）具有而且較高的穩(wěn)定性。與基本BBO 和DE 相比，BBO－DE 算法在最終解的質(zhì)量上和收斂速度上具有明顯優(yōu)勢(shì)。因此，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）. ［胡寬，常新龍，宋筆鋒，等.求解含等式約束優(yōu)化問題的遺傳算法 ［J］.上海交通大學(xué)學(xué)報(bào)，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.