高凱歌，鄭向偉

（1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014；2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南250014）

0 引 言

2008年，美國(guó)學(xué)者 Dan Simon在IEEE Transactions on Evolutionary Computation提出了一種新型的基于種群的仿生智能優(yōu)化算法——生物地理學(xué)優(yōu)化算法 （biogeographybased optimizer，BBO）。BBO算法模擬了自然界中生物種群的動(dòng)態(tài)變化，即物種在棲息地上的分布、遷移、繁殖、滅絕的過(guò)程。

由于BBO的遷移算子采用已知的棲息地替換策略，所以新的棲息地的精確度受到限制，導(dǎo)致BBO算法收斂速度慢。另一方面，受到變異策略的影響，BBO容易陷入局部最優(yōu)解，以致難以獲得真正最優(yōu)解。MCBBO算法從新的角度對(duì)BBO算法的兩個(gè)核心算子——遷移算子和變異算子進(jìn)行改進(jìn)，即把中值定理應(yīng)用在遷移算子，把柯西變異應(yīng)用在變異算子中，提出一種基于中值遷移和柯西變異的MCBBO算法。在仿真實(shí)驗(yàn)中，通過(guò)四個(gè)基準(zhǔn)函數(shù)驗(yàn)證了MCBBO算法更有優(yōu)勢(shì)：MCBBO得到的解比BBO、PSO和GA的解更加接近理論最優(yōu)解，而且MCBBO算法的收斂速度更快。

1 BBO算法和相關(guān)研究

1.1 BBO算法

BBO算法思想來(lái)源于生物種群在自然界中的動(dòng)態(tài)變化過(guò)程［1］。大環(huán)境是在一個(gè)小生態(tài)系統(tǒng)中存在多個(gè)棲息地。若是其中某個(gè)棲息地的環(huán)境十分適合生物的生存和繁殖，表示該棲息地有較高的棲息地適宜度指數(shù)；反之，則表示這個(gè)棲息地有較低的適宜度指數(shù)。與棲息地適宜度指數(shù)相關(guān)的因素有許多，每種因素的變化都會(huì)改變棲息地的環(huán)境，進(jìn)而對(duì)該棲息地物種分布和遷移等產(chǎn)生某種程度的影響。概括說(shuō)來(lái)，棲息地適宜度指數(shù)和生物種群數(shù)量的關(guān)系是：具有高適宜度的棲息地相對(duì)來(lái)說(shuō)可以容納較多的物種，具有較低適宜度的棲息地則只能容納較少的物種。所以，棲息地的適宜度和該棲息地的物種數(shù)量成正比。

BBO算法中的術(shù)語(yǔ)和定義包括如下幾個(gè)［2－3］。

（1）生態(tài)系統(tǒng)：數(shù)學(xué)模型中的最大范圍。

（2）棲息地 （Hi，i＝1，2，…，n）：生態(tài)系統(tǒng)中包含若干棲息地，每個(gè)棲息地可被看作一個(gè)相對(duì)獨(dú)立的物種生存區(qū)域。數(shù)學(xué)模型中物種之間的遷移操作是以棲息地為界的。

（3）棲息地適宜度指數(shù) （HSI）：用數(shù)值衡量棲息地是否適合物種的生存和發(fā)展。

（4）適宜度指數(shù)變量 （SIV）：每個(gè)變量都是影響棲息地的一個(gè)因素，采用整數(shù)表示。

（5）適宜度指數(shù)向量 （SIVs）：一個(gè)采用整數(shù)編碼的d－維向量表示整個(gè)優(yōu)化問(wèn)題的一個(gè)可行解。

（6）遷入率 （λ）：棲息地被更改的概率。

（7）遷出率 （μ）：棲息地被作為信息引入源的概率。

（8）變異率 （Pmod）：棲息地發(fā)生變異的概率。

（9）遷移算子：根據(jù)棲息地的遷入率、遷出率以及遷移策略，進(jìn)行遷移操作。

（10）變異算子：根據(jù)棲息地的變異率以及變異策略，進(jìn)行變異操作。

1.2 相關(guān)研究

已有不少針對(duì)BBO研究和改進(jìn)。文獻(xiàn) ［4］提出一類(lèi)基于物種遷移優(yōu)化的進(jìn)化算法，比較分析了SMO與其他智能算法的優(yōu)缺點(diǎn)，其仿真實(shí)驗(yàn)結(jié)果表明這類(lèi)算法是有價(jià)值的。文獻(xiàn) ［5］提出了BBO算法優(yōu)化過(guò)程中可以采用4種遷移模型，并分別測(cè)試了這4中遷移模型的性能。文獻(xiàn)［6］提出6種生物遷移模式，測(cè)試得到采用新遷移策略的BBO算法的性能得到了提高。文獻(xiàn) ［7］給出一種結(jié)合精英策略的BBO算法，實(shí)驗(yàn)結(jié)果表明對(duì)于該算法的適用問(wèn)題來(lái)說(shuō)，結(jié)合精英策略的BBO算法性能是有明顯改進(jìn)的。文獻(xiàn)［8］將進(jìn)化策略應(yīng)用于BBO算法，并采用一種新的遷移拒絕方法。文獻(xiàn) ［9］利用DE算法的差分進(jìn)化算子改進(jìn)BBO算法的遷移算子，基準(zhǔn)函數(shù)的測(cè)試結(jié)果表明改進(jìn)后的算法性能同時(shí)優(yōu)于DE算法和BBO算法。文獻(xiàn) ［10］引入對(duì)立學(xué)習(xí)機(jī)制 （OBL），提出了OBBO算法，仿真實(shí)驗(yàn)結(jié)果表明OBBO比BBO表現(xiàn)的更優(yōu)秀。

總體而言，BBO算法在算法的收斂速度和擺脫局部最優(yōu)的能力仍然不夠理想。

2 基于中值定理和柯西變異的生物地理學(xué)優(yōu)化算法

2.1 基于中值定理的遷移算子

BBO算法通過(guò)遷移算子來(lái)實(shí)現(xiàn)棲息地之間的信息共享，進(jìn)而更新棲息地得到更大更豐富的解集合，以便優(yōu)化過(guò)程結(jié)束后得到更優(yōu)解。考慮到使用中值定理可以擴(kuò)大信息源的范圍，信息源就不會(huì)僅局限于某個(gè)已存在的解，這樣理論上得到更優(yōu)解的可能性就大了。下面在三維立體空間中說(shuō)明中值定理擴(kuò)大引入信息源的原理。

將解的形式定義為 （x，y，z）。假設(shè)A：（x1，y1，z1）已確定要進(jìn)行遷移操作，B：（x2，y2，z2）則是信息的來(lái)源。若是在進(jìn)行遷移操作時(shí)，僅簡(jiǎn)單的用B：（x2，y2，z2）中的變量依概率替換掉A：（x1，y1，z1）中的變量，顯然得到的解集只有8個(gè)元素?，F(xiàn)在使用 ［0，1］之間的3個(gè)隨機(jī)實(shí)數(shù)：α1，α2，α3，分別作為3個(gè)對(duì)應(yīng)變量的系數(shù)。依概率用α1x1＋（1－α1）x2，α2y1＋ （1－α2）y2，α3z1＋ （1－α3）z2分別替換A：（x1，y1，z1）中的變量x1，y1，z1。這樣，信息的來(lái)源就不僅局限在有限的幾個(gè)變量，而是有無(wú)數(shù)種可能。

2.2 基于柯西分布的變異算子

突變是指生物的生存環(huán)境在短時(shí)間內(nèi)發(fā)生了急劇的變化，如由瘟疫疾病、自然災(zāi)害等原因?qū)е聴⒌丨h(huán)境發(fā)生徹底改變。突變操作豐富了解集合，提高了找到更優(yōu)解的可能性。在原有變異算子的基礎(chǔ)上提出一種新的、基于柯西隨機(jī)數(shù)的變異算子，即在進(jìn)行變異操作時(shí)得到的隨機(jī)數(shù)是服從柯西分布的。

由于柯西分布函數(shù)的概率分布特性：在水平方向上越接近水平軸，變化得越緩慢。因此柯西分布可以看作是無(wú)限的，它產(chǎn)生一個(gè)遠(yuǎn)離原點(diǎn)的隨機(jī)數(shù)的概率高于正態(tài)分布，所以產(chǎn)生的隨機(jī)數(shù)有更大的分布范圍。這意味著在優(yōu)化過(guò)程中陷入局部極值后，利用柯西變異更有可能跳出局部極值。

對(duì)確定發(fā)生變異的棲息地Hi的狀態(tài)：Xi＝ （xi，1，xi，2，……，xi，d）做 柯 西 變 異， 定 義 是：Xi＇ ＝ Xi ＋Xi＇＊Cauchy（0，1）。其 中，Cauchy （0，1）是 標(biāo) 準(zhǔn) 柯西分布。

2.3 MCBBO算法

MCBBO算法具體步驟如下：

步驟1 初始化算法參數(shù)。包括最大物種容納數(shù)量Smax、遷移率Pmod、最大遷入率Imax、最大遷出率Emax和最大變異率Mmax。

步驟2 初始化一組棲息地向量。每個(gè)向量都是問(wèn)題的一個(gè)可行解。

步驟3 根據(jù)映射關(guān)系f：SIVs—＞HSI，將每一個(gè)棲息地向量對(duì)應(yīng)的SIVs映射到HSI。并判斷是否滿(mǎn)足程序終止條件，若滿(mǎn)足則輸出最優(yōu)解，退出程序，否則繼續(xù)步驟4。

步驟4 對(duì)于每一個(gè)棲息地，計(jì)算其遷入率和遷出率，根據(jù)結(jié)合中值定理的遷移算子修改棲息地，進(jìn)行相關(guān)計(jì)算。

具體遷移過(guò)程為：①設(shè)定棲息地的全局遷移率Pmod，范圍是 ［0，1］。由全局遷移率Pmod決定棲息地是否進(jìn)行遷移操作，即，信息的引入。例如，我們?cè)O(shè)Pmod＝1，說(shuō)明每個(gè)棲息地都會(huì)被更新。若設(shè)Pmod＝0.5，說(shuō)明棲息地有一半的概率會(huì)被更改。②循環(huán)判斷每個(gè)棲息地是否被選中做遷移操作。若第i個(gè)棲息地Hi被選中，利用Hi的遷入率λi判斷決定Hi的棲息地向量SIVs每個(gè)變量是否發(fā)生更改。λi是 ［0，1］之間的實(shí)數(shù)，由公式λk＝Imax＊（1－k／Smax）［1］求得。③循環(huán)判斷棲息地Hi的每個(gè)變量是否被選中做遷移操作。若棲息地Hi的第k個(gè)變量Hi，k已被選中，根據(jù)所有其它棲息地Hi（i?。絡(luò)）的遷出率μj，利用輪盤(pán)選擇法或其它方法以決定是引入了哪個(gè)棲息地的信息。假如，得到是第j個(gè)棲息地Hj。遷出率μ是由公式μk＝Ek／Smax得到。至此，可以確定被引入信息的來(lái)源。④為了擴(kuò)大解的范圍，在確定了信息的來(lái)源之后，不再是用源的對(duì)應(yīng)變量替換發(fā)生遷入的變量 （即Hj，k替換Hi，k），而是結(jié)合α系數(shù)－中值定理，用α1x1＋（1－α1）x2，α2y1＋（1－α2）y2，α3z1＋（1－α3）z2分別替換相應(yīng)變量。

步驟5 根據(jù)柯西變異算子更新棲息地，并進(jìn)行相關(guān)計(jì)算。

具體變異過(guò)程為：①設(shè)定棲息地最大變異概率Mmax。例如，Mmax＝0.005，說(shuō)明所有的可行解發(fā)生突變的最大概率為0.005。②根據(jù)棲息地Hi的適宜度向量SIVs，可以得到該棲息地的相關(guān)數(shù)據(jù)，包括種群數(shù)量si。根據(jù)公式

可得到棲息地Hi種群數(shù)量為si的概s率P（si）。根據(jù)公式mi＝Mmax＊（1－P（si）／Pmax）［1］可以得到此時(shí) Hi的變異概率mi。由mi決定Hi是否發(fā)生變異操作。③假設(shè)Hi已被選中發(fā)生變異操作。采用柯西變異算子，即用Xi′＝Xi＋Xi＊Cauchy（0，1）來(lái)替換隨機(jī)得到的棲息地向量Xi″。

步驟6 轉(zhuǎn)至步驟3進(jìn)行下一次迭代過(guò)程。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)準(zhǔn)備

仿真實(shí)驗(yàn)部分對(duì)4種仿生智能優(yōu)化算法：MCBBO、基本BBO、PSO和GA進(jìn)行比較，通過(guò)4個(gè)代表性的測(cè)試函數(shù)驗(yàn)證MCBBO算法的性能。為了提高實(shí)驗(yàn)結(jié)果的可靠性，選取了在函數(shù)極值個(gè)數(shù)、極值點(diǎn)分布方面有代表性的4個(gè)函數(shù)作為測(cè)試函數(shù)：Sphere、Rosenbrock、Fletcher、Griewank四個(gè)函數(shù)，分別記為1—4號(hào)函數(shù)。

算法相關(guān)參數(shù)設(shè)置。種群大小，n＝20；解向量維度，d＝20；遷移率，Pmod＝1；最大突變概率，Mmax＝0.005；一次實(shí)驗(yàn)中算法迭代次數(shù)，Generation＝50。

3.2 實(shí)驗(yàn)結(jié)果

在Matlab7.6中完成仿真實(shí)驗(yàn)。表1是進(jìn)行100次Monte Carlo實(shí)驗(yàn)得到的結(jié)果，包括極小值、平均值、最大極小值。最小值代表了算法的最優(yōu)性能，平均值量化了算法的平均性能，最大極小值則是反映了算法求極小值的最壞性能。其中加粗顯示的數(shù)據(jù)是比較4種優(yōu)化算法結(jié)果得到的最優(yōu)解。圖1和圖2分別是得到每種算法基于Fletcher函數(shù)和Griewank函數(shù)，得到平均極小值的優(yōu)化過(guò)程曲線。

3.3 結(jié)果分析

由表1可知，經(jīng)過(guò)100次Monte Carlo實(shí)驗(yàn)的驗(yàn)證，在求四個(gè)測(cè)試函數(shù)的極小值、平均極小值和最大極小值的算法性能上，MCBBO優(yōu)于PSO和GA。同時(shí)，MCBBO算法在求函數(shù)Sphere、Rosenbrock和Griewank的極小值，求函數(shù)Sphere、Rosenbrock和Griewank的平均極小值，求函數(shù)Rosenbrock、Fletcher和Griewank的最大極小值上優(yōu)于基本BBO算法?；綛BO算法只在求Fletcher函數(shù)的極小值，求Fletcher函數(shù)的平均極小值，求Sphere函數(shù)的最大極小值上略有優(yōu)勢(shì)。所以，采用MCBBO算法求解4種測(cè)試函數(shù)，相較于其它算法更加接近理論上的最優(yōu)極值。

表1 算法極值 （A：algorithm V：value F：function）

由圖1和圖2可知，MCBBO算法的收斂過(guò)程曲線比其它算法的收斂過(guò)程更穩(wěn)定，收斂速度也更快。

以上兩點(diǎn)結(jié)論表明，將中值定理應(yīng)用到遷移算子，將柯西變異應(yīng)用到變異算子確實(shí)在一定程度上提高了BBO算法的性能，所以MCBBO算法是有效的。

4 結(jié)束語(yǔ)

本文通過(guò)將中值定理應(yīng)用到BBO算法的遷移算子、將柯西變異應(yīng)用到變異算子，改進(jìn)基本BBO算法，提出MCBBO算法。MCBBO算法希望把遷移算子結(jié)合中值定理從而擴(kuò)大引入信息的來(lái)源，將變異算子結(jié)合柯西變異以達(dá)到即使在優(yōu)化過(guò)程中一時(shí)陷入局部最優(yōu)也能盡快跳出局部最優(yōu)目的。在Matlab7.6中通過(guò)4個(gè)測(cè)試函數(shù)進(jìn)行的仿真實(shí)驗(yàn)結(jié)果顯示，與基本BBO、PSO、GA相比較，無(wú)論在獲得最優(yōu)極值和多次Monte Carlo實(shí)驗(yàn)得到的平均值與理論上最優(yōu)極值的相近程度上，還是算法的收斂速度上，MCBBO算法都更有效。

目前，MCBBO算法還有待進(jìn)一步研究完善。包括，在實(shí)現(xiàn)上是受某些條件限制，選擇采用的遷移模型是最簡(jiǎn)單、最利于實(shí)驗(yàn)實(shí)現(xiàn)的線性模型；對(duì)一些參數(shù)值的設(shè)定只是確定它在某個(gè)合理有效的范圍內(nèi)，并不能保證這里所設(shè)定的參數(shù)數(shù)值能最大限度的發(fā)揮算法優(yōu)勢(shì)。

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

［2］ZHANG Jianke.Research on optimization algorithm for biogeography ［J］.Computer Engineering and Design，2011，32 （7）：2497－2500 （in Chinese）. ［張建科.生物地理學(xué)優(yōu)化算法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32 （7）：2497－2500.］

［3］WANG Cunrui，WANG Nannan，DUAN Xiaodong，et al.Survey of biogeography－based optimization ［J］.Computer Science，2010，37 （7）：34－38 （in Chinese）.［王存睿，王楠楠，段曉東，等.生物地理學(xué)優(yōu)化算法綜述 ［J］.計(jì)算機(jī)科學(xué)，2010，37 （7）：34－38.］

［4］MA Haiping，CHEN Zidong，PAN Zhangxin.A kind of evolutionary algorithm optimization based on the migration of species［J］.Control and Decision，2009，24 （11）：1620－1624 （in Chinese）.［馬海平，陳子棟，潘張?chǎng)?一類(lèi)基于物種遷移優(yōu)化的進(jìn)化算法 ［J］.控制與決策，2009，24 （11）：1620－1624.］

［5］MA Haiping，CHEN Xiaolei.Equilibrium species counts and migration model tradeoffs for biogeography－based optimization［C］／／Shanghai，P.R.China：48th IEEE Conference on Decision and Control，2009：3306－3310.

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

［7］Dan Simon，Mehmet Ergezer，Dawei Du.Population distributions in biogeography－based optimization algorithms with elitism ［C］／／San Antonio，TX，USA：Proceedings of the IEEE International Conference on Systems Man and Cybernetics，2009：991－996.

［8］DU Dawei，DAN Simon，Mehmet Ergezer.Biogeography－based optimization combined with evolutionary strategy and immigration refusal ［OL］. ［2012－06－03］.http：／／embeddedlab.csuohio.edu／BBO／BBO＿Papers／mbbo.pdf.

［9］GONG Wenyin，CAI Zhihua，Charles X Ling.DE／BBO：A hybrid differential evolution with biogeography－based optimization for global numerical optimization ［OL］.［2012－06－03］http：／／embedded lab.csuohio.edu／BBO／BBO＿Papers／Gong2.pdf.

［10］Ergezer M，Simon D，DU Dawei.Oppositional biogeographybased optimization ［C］／／San Antonio，Texas，USA：IEEE International Conference on Systems Man and Cybernetics，2009：1009－1014.