基于中值遷移和柯西變異的生物地理學算法

高凱歌，鄭向偉

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

0 引 言

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

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

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

1.1 BBO算法

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

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

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

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

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

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

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

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

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

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

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

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

1.2 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

2.3 MCBBO算法

MCBBO算法具體步驟如下：

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

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

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

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

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

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

具體變異過程為：①設定棲息地最大變異概率Mmax。例如，Mmax＝0.005，說明所有的可行解發(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］可以得到此時 Hi的變異概率mi。由mi決定Hi是否發(fā)生變異操作。③假設Hi已被選中發(fā)生變異操作。采用柯西變異算子，即用Xi′＝Xi＋Xi＊Cauchy（0，1）來替換隨機得到的棲息地向量Xi″。

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

3 仿真實驗

3.1 實驗準備

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

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

3.2 實驗結(jié)果

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

3.3 結(jié)果分析

由表1可知，經(jīng)過100次Monte Carlo實驗的驗證，在求四個測試函數(shù)的極小值、平均極小值和最大極小值的算法性能上，MCBBO優(yōu)于PSO和GA。同時，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)勢。所以，采用MCBBO算法求解4種測試函數(shù)，相較于其它算法更加接近理論上的最優(yōu)極值。

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

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

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

4 結(jié)束語

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

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

［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）. ［張建科.生物地理學優(yōu)化算法研究 ［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）.［王存睿，王楠楠，段曉東，等.生物地理學優(yōu)化算法綜述 ［J］.計算機科學，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）.［馬海平，陳子棟，潘張鑫.一類基于物種遷移優(yōu)化的進化算法 ［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.