引入物種演化的改進生物地理學優(yōu)化算法

摘 要： "針對生物地理學優(yōu)化算法（biogeography-based optimization，BBO）易早熟收斂、陷入局部最優(yōu)的問題，引入物種演化理論提出了改進生物地理學優(yōu)化算法。該算法將所有棲息地按照物種數(shù)量劃分為三種地區(qū)，并建立協(xié)同進化關系，合理地采用區(qū)間入侵、區(qū)內(nèi)合作/競爭策略，滿足多樣性的同時避免了早熟收斂。定義了物種更迭和物種進化兩種變異策略，提出的雙策略協(xié)同變異算子旨在解決變異算子對較優(yōu)解的破壞。通過CEC2017中的八個基準測試函數(shù)與標準BBO及相關改進算法相比，該算法在算法性能、穩(wěn)定性等方面優(yōu)于BBO及其他改進算法，且該算法不易被局部最優(yōu)值所限制。將該算法應用于以最大完工時間為目標的柔性作業(yè)車間調(diào)度問題（flexible Job-Shop scheduling problem，F(xiàn)JSP）以檢驗其實際應用價值，實驗表明，該算法在解決FJSP上具有一定的有效性。

關鍵詞： "生物地理學優(yōu)化算法; 物種演化; 物種更迭; 柔性作業(yè)車間調(diào)度問題

中圖分類號： "TP301.6 """文獻標志碼： A

文章編號： "1001-3695（2022）02-007-0367-07

doi：10.19734/j.issn.1001-3695.2021.08.0316

Improved biogeography-based optimization algorithm "introducing species evolution

Zhang Qiwen， Yang Yongchao

（School of Computer amp; Communication， Lanzhou University of Technology， Lanzhou 730050， China）

Abstract： "In order to solve the problem of premature convergence and falling into local optimum in biogeography-based optimization algorithm， this paper proposed an improved biogeography-based optimization algorithm introducing species evolution（SEBBO）. The algorithm divided all habitats into three regions according to the number of species， established a co-evolution relationship， and reasonably adopted interval invasion and regional cooperation/competition strategies to meet diversity while avoided premature convergence. It defined two mutation strategies of species change and "species development， and designed the dual-strategy cooperative mutation operator to solve the damage of the mutation operator to the better solution. Then， compared with standard BBO and other related improved algorithms on 8 benchmark functions from CEC2017， SEBBO algorithm is superior to BBO and other BBO variants in terms of algorithm performance and stability， and local optimal values is not easily limit the algorithm. Finally， this paper applied the SEBBO algorithm to flexible Job-Shop scheduling with maximum completion time as the goal to test its practical application value. Experiments show that the algorithm has a certain effectiveness in solving FJSP.

Key words： "biogeography-based optimization algorithm; species evolution; species change； FJSP

0 引言

Simon教授［1］在2008年正式提出了生物地理學優(yōu)化算法（biogeography-based optimization，BBO）。由于BBO算法原理簡單且參數(shù)較少，一經(jīng)提出就吸引了眾多國內(nèi)外學者，廣泛應用于各種領域，但因其存在尋優(yōu)速度緩慢、易早熟收斂等劣勢，學者們提出了各種改進的BBO算法防止其早熟收斂。Zhang等人［2］提出了啟發(fā)式交叉策略和指數(shù)動態(tài)隨機差分遷移算子，結(jié)合全局最優(yōu)高斯變異算子并融合對立學習策略，實驗表明，該算法能避免早熟收斂且具有更好的性能和更快的運行速度；張新明等人［3］將變異算子融合到遷移算子中，采用榜樣選擇方案和貪婪保留法將該算法應用于圖像分割，實驗表明，基于高效生物地理學算法的圖像多閾值分割法分割速度快、穩(wěn)定性好；Giri等人［4］通過使用自適應鄰域結(jié)構提高了算法全局搜索能力，遷入棲息地可以通過分享局部最優(yōu)棲息地和全球最優(yōu)棲息地的信息來更新其特征，該改進能夠避免算法過早陷入局部最優(yōu)；Kavah等人［5］在BBO變異算子中引入基于高斯變異、柯西變異、指數(shù)變異的混合變異策略，該策略提高了算法的全局搜索能力，增強了種群的多樣性，避免陷入局部最優(yōu)；Farswan等人［6］將BBO算法的遷移算子和變異算子以及煙花算法（FWA）的爆炸算子結(jié)合在一起，改進算法具有更良好的優(yōu)化性能，滿足多樣性的同時避免過早收斂；Zhao等人［7］提出了兩階段的差分生物地理學優(yōu)化算法，兩階段遷移模型滿足進化早期的種群多樣性并加速進化后期的種群收斂速度，引入高斯變異算子使種群能夠有效地跳出局部最優(yōu)；葛強等人［8］將差分變異算子和自適應微擾動因子結(jié)合形成新的遷移算子，將高斯變異和柯西變異相結(jié)合改進變異算子，實驗表明該算法在收斂速度、尋優(yōu)精度和穩(wěn)定性等方面都有很大程度的提升。

盡管國內(nèi)外學者對BBO算法早熟收斂的問題進行了廣泛的研究，但是大部分改進算法沒有考慮棲息地和棲息地之間的差異及整個棲息地的進化情況，所有棲息地的遷移策略和變異策略都相同，很難突破早熟收斂。本文提出了一種引入物種演化的改進生物地理學優(yōu)化算法（improved biogeography-based optimization algorithm introducing species evolution，SEBBO），采用更加匹配自然遷移規(guī)律的雙曲正切變形遷移率模型和余弦遷移模型，根據(jù)遷移模型的特點將所有棲息地按照物種數(shù)量劃分為三類地區(qū)，通過區(qū)間入侵、區(qū)內(nèi)合作/競爭策略建立協(xié)同進化關系；為了解決變異算子對較優(yōu)解的破壞，提出了一種雙策略協(xié)同變異算子。

1 生物地理學優(yōu)化算法

BBO算法主要的兩個算子就是遷移算子和變異算子。

1）遷移算子

遷移是BBO算法中最為核心的操作，棲息地個體主要通過物種遷移機制來實現(xiàn)與其他棲息地之間的信息交換。遷入率和遷出率 分別用λ k和μ k表示，其計 算公式可參照棲息地的物種遷移模型。如圖1所示，本文針對遷移算子采用文獻［9］提出的雙曲正切變形遷移率模型，該模型匹配自然界物種遷移規(guī)律，作為BBO算法的遷移模型所獲得的最終解優(yōu)于余弦遷移率模型［10］及其他遷移模型的BBO算法，且此遷移模型很適用于本文棲息地動態(tài)劃分機制。

雙曲正切變形遷移率模型公式如下：

λ k= I 2 "－ e（k－n/2）－e（－k+n/2） e（k－n/2）+e（－k+n/2） +1 """"（1）

μ k= E 2 ""e（k－n/2）－e（－k+n/2） e（k－n/2）+e（－k+n/2） +1 """"（2）

其中 ：I=E=1;k為當前棲息地的物種數(shù)量;n為最大物種數(shù)量;e為底數(shù)參數(shù)，本文取值為 1.1。

2）變異算子

BBO算法的物種變異機制是提高棲息地種群中個體多樣性的有效手段，棲息地個體以一定幾率發(fā)生突變，為該個體在搜索空間中尋找最優(yōu)解增加更多的機會，但對于較優(yōu)棲息地個體而言，這種隨機變異無疑大大增加了其突變成較差個體的可能。某一棲息地的突變概率函數(shù)與該棲息地的數(shù)量概率成反比，因此，本文采用余弦遷移模型計算物種數(shù)量的概率，此遷移模型很適用于本文棲息地動態(tài)劃分機制。該模型下物種數(shù)量的概率如圖2所示。

物種數(shù) 量為s的棲息地發(fā)生變異的概率 為

m s=m max（1－P s/P max） ""（3）

其中：P s代表棲息地物種數(shù)量為s的概率;m max為用戶定義突變率的最大值;P max是所有P s中的最大值，即 max （P s） 。

2 SEBBO算法

2.1 動態(tài)劃分棲息地

為了解決單一的遷移算子及變異算子不能完全適用于種群中性能各異的所有棲息地，本文按照棲息地的物種數(shù)量對棲息地進行劃分，將棲息地劃分為三個地區(qū)，即富饒地區(qū)、普通地區(qū)和貧瘠地區(qū)，劃分比例為3∶ 4∶ 3，劃分比例的依據(jù)為所選遷移模型的特點。本文所選遷移模型為雙曲正切變形遷移率模型和余弦遷移模型，雙曲正切遷移模型如圖1所示。當物種數(shù)量較少或較多時，遷移模型的變化率較慢，而當物種數(shù)量到達一定數(shù)目時，遷移模型的變化率加快。余弦遷移模型計算各物種數(shù)量對應的概率，各物種數(shù)量對應的概率如圖2所示（物種數(shù)量為50時棲息地物種數(shù)量對應的概率），結(jié)合突變概率與該棲息地的數(shù)量概率成反比的特點，富饒地區(qū)與貧瘠地區(qū)變異率最大且為常值，普通地區(qū)變異率為變值且越靠近中間數(shù)量變異率越小。區(qū)間入侵策略與區(qū)內(nèi)合作/競爭策略的選取根據(jù)遷入率進行選擇。如圖3所示，雙曲正切遷移模型較緩的變化率使貧瘠地區(qū)棲息地執(zhí)行更多的入侵策略，滿足物種多樣性，使富饒地區(qū)棲息地執(zhí)行更多的區(qū)內(nèi)合作/競爭策略，避免算法迭代前期陷入局部最優(yōu)，而在算法迭代后期區(qū)內(nèi)競爭策略使得越優(yōu)秀的棲息地擾動越小（以兩棲息地遷出率之差為擾動），需注重局部搜索。雙策略協(xié)同變異算子采用余弦遷移模型，結(jié)合突變概率與棲息地物種數(shù)量概率成反比的特點，突變較多發(fā)生在物種數(shù)量較多（富饒地區(qū)）和物種數(shù)量較低（貧瘠地區(qū)）的棲息地，針對不同地區(qū)的棲息地選擇不同的策略協(xié)同進化。

針對貧瘠地區(qū)，遷入率大而遷出率小，較大概率執(zhí)行區(qū)間入侵策略而小概率執(zhí)行區(qū)內(nèi)合作/入侵策略；對于普通地區(qū)，按照遷入率的變化由區(qū)間入侵策略逐漸轉(zhuǎn)向區(qū)內(nèi)合作/競爭策略；特別地，富饒地區(qū)只存在區(qū)內(nèi)合作/競爭策略。

不同數(shù)量的設置對算法性能的影響：若貧瘠地區(qū)棲息地數(shù)量多，富饒地區(qū)數(shù)量較少，則導致算法早熟收斂，易陷入局部最優(yōu)；若富饒地區(qū)棲息地數(shù)目多，貧瘠地區(qū)數(shù)量較少，則導致算法迭代后期多樣性不足。

2.2 區(qū)間入侵策略

區(qū)間入侵策略是指物種數(shù)量高的地區(qū)中棲息地中的物種會去入侵數(shù)量低的地區(qū)中的棲息地。在自然界中，物種入侵能夠有效改善入侵棲息地的物種數(shù)量。物種在一個棲息地入侵另一個棲息地，需要考慮兩個因素，即棲息地適應度和距離。物種遷出棲息地的適應度越高，遷出率越高，入侵能力越強，對被入侵棲息地的影響更大。同時，根據(jù)地理學鄰近效應原理［11］，棲息地更容易被其鄰近棲息地所影響，因此，入侵棲息地的選擇會根據(jù)適應度距離比進行選擇。區(qū)間物種入侵策略公式如下：

Xt+1 i，j=Xt i，j+F 1×（Xt best，j－Xt i，j）+ F 2×（Xt k，j－Xt i，j） ""（4）

其中： X i是被入侵棲息地；t為迭代次數(shù)；X best是最優(yōu)棲息地，最優(yōu)棲息地會參與每次區(qū)間入侵。對于入侵棲息地X k，計算其與r個預備 入侵棲息地的適應度差和距離差的比值，選擇適應 度距離比最大的預備棲息地作為入侵棲息地，X K= argmax "k∈r "HSI i－ HSI k/|X k，j－X i，j| 。F 1和F 2是［0，1］間的一個系數(shù)，稱為入侵推動力，F(xiàn) 1和F 2的取值與入侵棲息地的適應度成正相關，F(xiàn) 1= fit （X best，j）/（ fit （X best，j）+ fit （X k，j）），F(xiàn) 2=1－F 1 。

2.3 區(qū)內(nèi)合作策略

種間合作是物種種間正相互作用，是生物之間對一方有利而對另一方無害的種間關系［12］。某棲息地的物種與同一地區(qū)更優(yōu)秀棲息地的物種合作改變自身適應度。區(qū)內(nèi)合作策略公式如下：

Xt+1 i，j=α 1Xt i，j+（1－α 1）Xt r1，j ""（5）

其中： X i是當前棲息地;X r1是同一地區(qū)中比自身優(yōu)秀的任意合作棲息地；α 1是［0，1］間的一個系數(shù)，稱為合作強度，α 1的取值與兩物種的適應度有關，α 1越大，說明此棲息地適應度越高，合作貢獻越大，因為適應度的高低與物種遷出率成正相關，所以α 1的取值依賴于遷出率μ i，α 1=μ i/（μ i+μ r1） 。

2.4 區(qū)內(nèi)競爭策略

種間競爭是物種種間負相互作用，一般指生態(tài)需求的物種為爭奪資源或條件而產(chǎn)生的一種直接或間接抑制對方的現(xiàn)象［12］。在競爭中常常是一方取得優(yōu)勢而另一方受抑制甚至被消滅。區(qū)內(nèi)競爭策略根據(jù)達爾文進化論中“優(yōu)勝劣汰，適者生存”提出，區(qū)內(nèi)競爭策略公式如下：

Xt+1 i，j= Xt i，j+α 2×（Xt i，j－Xt r2，j） ""fit （Xt r2，j）lt; fit （Xt i，j）

Xt r2，j "fit （Xt r2，j）≥ fit （Xt i，j） """"（6）

其中： X i是競爭棲息地;X r2是在同一地區(qū)中任意選擇的其他競爭棲息地；α 2稱為競爭強度，與兩棲息地遷出率之差相等，α 2越小，競爭越激烈，α 2=μ i－μ r2 。本文以適應度作為物種競爭強弱的指標，適應度越高，越在競爭中占據(jù)主導地位，反之亦然。競爭成功會得到部分自身所沒有 的生態(tài)差異，若是競爭失敗則被淘汰，棲息地被優(yōu)勢棲息地的物種占領。

區(qū)間入侵策略針對適應度不高的貧瘠棲息地和部分普通地區(qū)棲息地，該類地區(qū)的棲息地受最優(yōu)解與較優(yōu)解的指導逐漸向較優(yōu)解靠近，改善自身較低的適應度；區(qū)內(nèi)合作策略針對適應度較高的富饒棲息地及部分普通地區(qū)棲息地且在算法迭代前期較多使用，該策略借鑒了遺傳算法中交叉操作的思想，決定了遺傳算法的全局搜索能力。將其引入到BBO算法中，一方面取得了遷移操作的效果，讓較差的解獲得較優(yōu)解的特征，從而提高自身的質(zhì)量且提高了多樣性；另一方面，算法避免了較優(yōu)的解在遷移過程中出現(xiàn)退化的情況。區(qū)內(nèi)競爭策略針對適應度較高的富饒棲息地及部分普通地區(qū)棲息地，且在算法迭代后期較多使用，若是競爭成功，則添加較小擾動在自身領域內(nèi)進行局部搜索；若競爭失敗，則采用具備較強局部搜索能力的傳統(tǒng)遷移策略。

2.5 雙策略協(xié)同變異算子

單一的隨機變異策略無法兼顧全局搜索和局部搜索，且存在一定缺陷：對于較差棲息地，這種隨機變異有可能使其突變成新的更優(yōu)棲息地，為種群朝最優(yōu)方向進化提供一定機會，但對于較優(yōu)棲息地而言，尤其在算法迭代后期，隨機變異不僅很難開發(fā)出比當前最優(yōu)解優(yōu)秀的棲息地，還容易產(chǎn)生毫無利用價值的較差棲息地，致使算法的進化效率較低。受達爾文進化論的啟發(fā)，本文在基本變異算子的基礎上重新定義了棲息地的變異策略，即雙策略協(xié)同變異算子。

達爾文的進化論認為，一個生物群體在穩(wěn)定的環(huán)境中的進化，一部分不適應的群體被淘汰，另一部分群體朝著更適應環(huán)境的方向進化，即“物競天擇，適者生存”。針對不同物種數(shù)量的棲息地，結(jié)合突變概率與該棲息地的數(shù)量概率成反比的特點，突變多發(fā)生在棲息地物種數(shù)量較少（貧瘠地區(qū)）或者較多（富饒地區(qū)）的情況，針對不同類型棲息地使用不同的變異策略。

a）對于貧瘠地區(qū)的棲息地，此類棲息地自身適應度太差，有一定概率會被自然淘汰，然后重新生成新的種群，因此定義為“物種更迭”，重新生成新的物種來代替。

b）對于富饒地區(qū)的棲息地，其進化是朝著更加適應環(huán)境的方向進行，且不會較多改變自身已有的適應度，定義為“物種進化”。

c）對于普通地區(qū)的棲息地，在算法迭代初期，所有棲息地的適應度較低，其生態(tài)系統(tǒng)十分脆弱，生物群體有很大概率被淘汰，棲息地大概率執(zhí)行“物種更迭”；堅持下來的棲息地，其生態(tài)系統(tǒng)會越來越穩(wěn)定，其物種會朝著更加適應環(huán)境的方向進化，故大概率執(zhí)行“物種進化”。

物種更迭公式如下：

Xt+1 i，j=（ max X（j）－ min X（j））×rand+ min X（j） ""（7）

其中：min X（j）、 max X（j）分別是第j維的最小值和最大值 。

物種進化公式如下：

Xt+1 i，j=Xt i，j+α 3⊕ Levy （β） ""（8）

其中 ：α 3表示步長控制量，選擇初始值步長A=1，使得α 3= A "t "更新飛行步長，t是當前迭代次數(shù)，α 3的值隨著代數(shù)的增加而減少，進行更多的局部搜索；⊕表示點對點乘法； Levy （β）表示服從參數(shù)為β的 Levy 分布，β=1.5 。

萊維飛行［13］具有的較小步長的短距離行走和較大步長的長距離行走，且行走交替，偶爾較大步長的長距離行走防止較小步長短距離行走的聚集，而較小步長的短距離行走在增加種群多樣性的同時也能夠減少對較優(yōu)解的破壞，不會過多破壞尋優(yōu)過程，因此很適用于“物種進化”。

2.6 策略分配的合理性及尋優(yōu)能力的綜合性分析

SEBBO算法針對不同棲息地在不同迭代時期使用不同的策略綜合尋優(yōu)。在算法迭代早期改進遷移算子，區(qū)間入侵策略應用于適應度較低的棲息地，滿足物種多樣性；算法迭代前期較多使用區(qū)內(nèi)合作策略進行全局搜索。雙策略協(xié)同變異算子中物種更迭策略在算法迭代前期較多使用，具備全局搜索性能；物種進化策略保證較優(yōu)棲息地尋找最優(yōu)解的同時不會過多破壞自身已有的適應度。在算法迭代后期，此時算法已經(jīng)收斂，改進遷移算子，區(qū)間入侵策略加快算法的收斂速度，算法迭代后期較多使用區(qū)內(nèi)競爭策略，區(qū)內(nèi)競爭策略具備一定的局部搜索能力。雙策略協(xié)同變異算子中物種更迭策略在迭代后期針對適應度較低的棲息地滿足物種多樣性，隨機變異有可能使其突變成新的更優(yōu)棲息地，為種群朝最優(yōu)方向進化提供一定機會；物種進化策略在算法迭代后期較多使用，該策略采用Levy飛行公式，此公式具備一定的局部搜索能力。

從整體尋優(yōu)角度來看，以上分配機制在算法迭代前期具有全局搜索能力，滿足棲息地的多樣性，避免算法陷入局部最優(yōu)；算法迭代后期在滿足算法的局部搜索能力的同時不會破壞已有較優(yōu)解的適應度，因此，以上分配機制合理。

引入物種演化的改進生物地理學優(yōu)化算法由改進遷移算子和雙策略協(xié)同變異算子兩部分組成，改進遷移算子由區(qū)間入侵策略、區(qū)內(nèi)合作策略、區(qū)內(nèi)競爭策略組成。區(qū)內(nèi)競爭策略在考慮自身適應度的情況下進行局部搜索，雙策略協(xié)同變異算子包含物種更迭策略和物種進化策略兩部分。 從整體尋優(yōu)角度分析，改進遷移算子在算法迭代前期具有全局搜索性能，滿足多樣性的同時避免陷入局部最優(yōu)；而在算法迭代后期，具有局部搜索性能。雙策略協(xié)同變異算子在算法迭代前期多進行全局搜索，滿足多樣性；在算法迭代后期多進行局部搜索。因此，該算法在迭代前期偏向全局搜索，而在迭代后期偏向局部搜索。

2.7 低差異序列初始化種群策略

低差異序列［14］又稱做擬隨機序列，其超均勻分布的特點使得任意長度的子序列能均勻地填充在整個函數(shù)空間，分布均勻的隨機數(shù)意味著更加優(yōu)秀的樣本分布。使用具有超均勻分布特性的低差異序列初始化種群，避免在初始化過程中產(chǎn)生隨機重復的棲息地，使算法性能更優(yōu)、誤差更小、收斂更快。本文使用的低差序列為Halton序列。

3 SEBBO算法的收斂性分析

本文采用馬爾可夫鏈策略來分析SEBBO算法的收斂性。設 X（t）={x 1（t），x 2（t），…，x n（t）}是改進算法代數(shù)為t時的種群，根據(jù)適應度將X（t）分為n個子集，x i（t）（i=1，2，…，n）為其中的一個子集。假設某一迭代次數(shù)最好的目標函數(shù)值為F i，i為當前狀態(tài)，則下一次迭代時向更優(yōu)狀態(tài)k轉(zhuǎn)移，應滿足klt;i；若k=i ，則算法已經(jīng)收斂到全局最優(yōu)。

物種演化中，從一個狀態(tài)i轉(zhuǎn)移到下一個狀態(tài)k的轉(zhuǎn)移概率為p ik，則 有

kgt;i，p ikgt;0 ""（9）

klt;i，p ikgt;0 ""（10）

k=i，p ik=0 ""（11）

式（9）～（11） 證明：設i為某迭代次數(shù)為t時某棲息地狀態(tài)，該狀態(tài)i為該棲息地經(jīng)過若干次改進遷移、改進變異、貪婪選擇操作后的狀態(tài)，也是當前位置最好的狀態(tài)，若當前棲息地執(zhí)行操作，則有三種遷移策略（區(qū)間入侵策略、區(qū)內(nèi)合作策略、區(qū)內(nèi)競爭策略）和兩種變異策略（物種更迭策略和物種進化策略）。一種情況是：在迭代次數(shù)t+1，若當前棲息地執(zhí)行區(qū)間入侵策略、當前棲息地的狀態(tài)更新到更優(yōu)狀態(tài)，則當前棲息地的狀態(tài)將以概率P 1更新到 新狀態(tài)。

P 1=λ（1－p m）p s+λp m（1－p i）p s+λp mp ip s=λp s ""（12）

顯然P 1gt;0，命題得證。其中，p m為突變算子執(zhí)行成功的概率；p i為物種更迭策略執(zhí)行成功的概率，1-p i為物種進化策略執(zhí)行成功的概率；p s為貪婪選擇算子執(zhí)行成功的 概率。

另外一種情況是：在迭代次 數(shù)t+1，若當前棲息地執(zhí)行 區(qū)內(nèi)合作策略或者區(qū)內(nèi)競爭策略：

a）執(zhí)行 區(qū)內(nèi)合作策略，若當前棲息地狀態(tài)可以轉(zhuǎn)移到更優(yōu)狀態(tài)，則當前棲息地的狀態(tài)將以概率P 2更新到新狀 態(tài)。

P 2=（1－λ）（1－p m）p sp r+（1－λ）p m（1－p i）p sp r+

（1－λ）p mp ip sp r=（1－λ）p sp r ""（13）

顯然P 2gt;0，命題得證。p r為［0，1］的隨 機數(shù)。

b）執(zhí)行區(qū)內(nèi)競爭策略，若當前棲息地狀態(tài)可以轉(zhuǎn)移到更優(yōu)狀態(tài)，則當前棲息地的狀態(tài)將以概率 P "3更新到新狀態(tài)。

P 3=（1－λ）（1－p m）p s（1－p r）+（1－λ）p m（1－p i）p s（1－p r）+

（1－λ）p mp ip s（1－p r）=（1－λ）p s（1－p r） ""（14）

顯然 P "3gt;0，命題得證。

綜合式（12）～（14）可得總概率 P 為

P=P 1+P 2+P 3=λp s+（1－λ）p sp r+（1－λ）p s（1－p r）=p s ""（15）

因為引入貪婪選擇算子，所以kgt;i，p ikgt;0；又因為0≤ p s≤1，可知P≥0；如果Pgt;0，命題得證klt;i，p ikgt;0 。在SEBBO 算法中，每次進行新的演化都是對當前棲息 地狀態(tài)i向更好的狀態(tài)更新；如果P=0，說明當前棲息地已經(jīng)達到全局最優(yōu)，即k=i，p ik=0 。

SEBBO算法的進化過程主要由改進的遷移算子和雙策略協(xié)同變異算子以及貪婪選擇算子構成，與迭代次數(shù)不相關，并且考慮到SEBBO算法種群個體的數(shù)目確定，則該算法的進化過程滿足有限齊次馬爾可夫鏈。種群子集 x i（t）（i=1，2，…，n），可等價為有限齊次馬爾可夫鏈上一個狀態(tài)，根據(jù)上述結(jié)論可得，該馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣 P "為

P = "p 11 0 … 0

p 21 p 22 … 0

p n1 p n2 … p nn "= "p 11 0 "S "2 "S "1 """""（16）

其中：

S "2=（p 21，p 31，…，p n1） T "（17）

S "1= "p 22 … 0

p n2 … p nn """""（18）

由式（17）（18）可以發(fā)現(xiàn)S 2≠0，S 1≠0。由于馬爾可夫轉(zhuǎn)移矩陣中每一行的概率之和是１，則p 11=1≠0。由此可以得出馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣 P 滿足可歸約隨機矩陣［15］，則 有

P ∞ =lim "t→∞ ""p 11 0 "S "2 "S "1 "t =

lim "t→∞ ""pt 11 0 ∑ t-1 i=1 "S i 1 S "2pt-i 11 "S t 1 ""=lim "t→∞ ""p∞ 11 0 "S ∞ 2 0 "t """（19）

由于馬爾可夫轉(zhuǎn)移矩陣中每一行的概率相加是1，則式（19）中 p∞ 11=1，且 S ∞ 1=0，同時必有 S ∞ 2=（1，1，…，1） T，則

P ∞= "1 0 … 0

1 0 … 0

1 0 … 0 """""（20）

可見，當?shù)螖?shù)t→∞時，概率p∞ i1=1（i=1，2，…，n），即無論初始狀態(tài)如何，最后都能以概率1收斂到 全局最優(yōu)解上，則SEBBO算法具有全局收斂性。

4 SEBBO實現(xiàn)流程

本文將雙曲正切變形遷移率模型、改進的遷移算子、雙策略協(xié)同變異算子及低差異序列初始化種群策略合理地結(jié)合在一起，并引入了貪婪選擇算子提出了一種引入物種演化的改進生物地理學優(yōu)化算法（SEBBO），該算法的步驟如下：

a）低差異序列初始種群，設置相關參數(shù)，物種數(shù)量 n，當前迭代次數(shù)t，最大迭代次數(shù)t max ;

b）評價每個棲息地的HSI，根據(jù)HSI由優(yōu)至劣排序種群，且更新各個棲息地的物種數(shù)量;

c）根據(jù)雙曲正切變形遷移率模型及余弦遷移模型計算遷入率、遷出率及變異率;

d）若當前 棲息地的遷入率大于隨機數(shù)，則執(zhí)行區(qū)間入侵策略，否則，執(zhí)行區(qū)內(nèi)合作/區(qū)內(nèi)競爭策略（隨機數(shù)大于t/t max，執(zhí)行區(qū)內(nèi)合作策略，否則執(zhí)行區(qū)內(nèi)競爭 策略）;

e）若當前棲息地的變異率大于隨機數(shù)，則執(zhí)行雙策 略協(xié)同變異算子（若物種數(shù)量小于0.3n或隨機數(shù)大于等于t/t max執(zhí)行物種更迭策略；若物種數(shù)量大于0.7n或隨機數(shù)小于等于t/t max執(zhí)行物種進化策略 ）;

f）評價每個棲息地更新后的HSI并執(zhí)行貪婪選擇算法;

g）根據(jù)HSI由優(yōu)至劣排序種群，且更新各個棲息地的物種數(shù)量;

h）判斷是否達到算法停止條件，如果是，輸出最終結(jié)果，否則，返回步驟c）。

5 數(shù)值實驗及結(jié)果分析

本文采用CEC2017［16］標準測試集中的八個函數(shù)測試集測試SEBBO算法的性能。函數(shù)分為四類： f 1是單峰函數(shù)，f 2和f 3是簡單多模函數(shù)，f 4和f 5是混合函數(shù)，f 6～f 8是組合函 數(shù)，具體如表1所示。每個函數(shù)包含10、30維。算法在每個基準函數(shù)上執(zhí)行30次;為了進行公平比較，將函數(shù)的最大評價次數(shù)設置為1 000，將小于1E-8的誤差值和標準偏差視為零。

所有算法均使用MATLAB R2014a編程語言重新實現(xiàn)，并 在2.5 GHz Intel CoreTM i5-7300 CPU 8 GB RAM的64位OS的 PC上運行。

為了驗證SEBBO算法的性能，將SEBBO與BBO算法［1］、混合生物地理學優(yōu)化算法（blended biogeography-based optimization，BBBO） ［17］、基于拉普拉斯的生物地理學的優(yōu)化算法（Laplacian biogeography-based optimization，LXBBO［18］）、基于生物地理學優(yōu)化的混合差分進化算法（hybrid differential evolution with biogeography-based，DE/BBO） ［19］、兩階段差分生物地理學優(yōu)化算法（two-stage differential biogeography-based optimization，TDBBO） ［7］、差分遷移和趨優(yōu)變異的生物地理學優(yōu)化算法（biogeography-based optimization with differential migration and global-best mutation，DGBBO） ［20］ 以及微擾動差分生物地理學優(yōu)化算法（differential biogeography optimization algorithm based on micro-perturbation and mixed variation，MDEBBO） ［8］進行對比實驗。各算法的參數(shù)設置如表2所示。

為了更直觀地觀察對比各個算法的收斂速度、收斂精度以及算法跳出局部最優(yōu)的能力，圖4給出了SEBBO和基本BBO算法以及六種改進BBO算法在函數(shù) f 3、f 4和f 8上的 收斂曲線圖，其中橫軸表示迭代次數(shù)，縱軸表示適應度值。

從圖4可知，除圖4（e）外，無論在10維還是30維，SEBBO算法的表現(xiàn)最好。 f "3為簡單多模函數(shù)，圖4（a）（ D =10）和圖4（d）（ D=30）分別表示各算法在函數(shù)f 3不同 維度下的表現(xiàn)，分析可知SEBBO算法在簡單多模函數(shù)收斂精度更高，且不易陷入局部最優(yōu)，當其他對比算法陷入局部最優(yōu)狀態(tài)時，SEBBO算法依舊在收斂，且收斂至最大迭代次數(shù)。 f "4為混合函數(shù)，圖4（b）（ D =10）和圖4（e）（ D =30）分別表示各算法在混合函數(shù)不同維度下的表現(xiàn)，分析圖4（b）可知，SEBBO算法收斂速度更快，收斂精度更高；分析圖4（e）可知，除LXBBO外，BBO算法及其他改進BBO算法的表現(xiàn)都很優(yōu)秀，收斂速度快且結(jié)果接近理論最優(yōu)值。 f "8為組合函數(shù)，圖4（c）（ D =10）和圖4（f）（ D =30）分別表示各算法在函數(shù) f "8不同維度下的表現(xiàn)，分析圖4（c）（f）可知，SEBBO算法在組合函數(shù)的收斂速度更快，收斂精度更高，且SEBBO算法不易被局部最優(yōu)值所限制。綜上所述，相較于BBO算法及其改進算法，SEBBO算法收斂速度更快，收斂精度更高，跳出局部最優(yōu)的能力更強。

表3、4為各算法對八個測試函數(shù)的優(yōu)化結(jié)果。表中以平均數(shù)值和方差作為評價項，平均數(shù)值越小，則優(yōu)化效果越好。通過表3和4中粗體標志出的結(jié)果可以看出，在10維和30維度下，除了單峰函數(shù)，其他不論對于簡單多模函數(shù)、混合函數(shù)還是組合函數(shù)，SEBBO均能夠取得較好的優(yōu)化效果。為了進一步測試SEBBO與其他算法之間的顯著差異，使用Wilcoxon對各算法進行驗證，表5給出了在SEBBO和BBO及其變體之間應用Wilcoxon檢驗對不同維度函數(shù)的統(tǒng)計分析結(jié)果。其中 “n/w/t/l”分別表示在n 個函數(shù)上SEBBO算法取得了 w次性能更優(yōu)，t次性能相同，l次性能 更差。從表5可以看出，在10維、30維的情況下，SEBBO提供的 R+值高于R-。在α=0.05和α= 0.1的情況下，除TDBBO算法外，SEBBO算法在8個測試函數(shù)上的性能明顯優(yōu)于其他BBO算法的變體，然而實驗表明SEBBO算法在單峰函數(shù)的表現(xiàn)差強人意。總體來說，SEBBO算法在簡單多模函數(shù)和混合函數(shù)以及組合函數(shù)中所表現(xiàn)出的效果明顯優(yōu)于基本BBO算法和其他BBO算法變體，可以得出結(jié)論，SEBBO是一種有效的改進算法。

6 實際應用及結(jié)果分析

為了驗證改進算法的實際應用價值，將其應用于柔性作業(yè)車間調(diào)度問題（FJSP）［21］。FJSP每道加工工序的加工機器是不確定的，每個工件的每道工序可在多個不同機器之間進行選擇，且不同機器所對應的加工時間不同。由于它的這一柔性特征使問題更加貼近實際應用，已在鋼鐵制造、化學工業(yè)、汽車制造等領域廣泛使用。

6.1 問題描述

假設一個 車間有m臺加工機器和n個工件，每個 工件有若干不等的工序待加工，工序的加工按照一定的順序進行，每個工序的加工過程都可以在許多不同的機器上進行，且所需加工時間不同。FJSP 的優(yōu)化目標是為每個工序分配適當?shù)臋C器，并對每臺機器上的工序加工順序進行排序，以期實現(xiàn)給定目標最優(yōu)。

本文以車間最大完工時間最小化為目標所建立的混合0-1整數(shù)規(guī)劃模型如下：

minC max =max（ C ij ）

（21）

其中： C max表示工件的最大完工時間；C ij表示工件i的第j道工序的 完成時間。

對于該問題，考慮以下假設條件：a）工件和機器零時刻均為可用狀態(tài)；b）同一時刻同臺機器只可加工一道工序；c）工序加工是不可被中斷的；d）各工件加工優(yōu)先級相同；e）不同工件的工序之間相互獨立，同一工件的工序之間具有先后加工的確定關系。

6.2 編碼與解碼

根據(jù)FJSP的特點，每個個體的編碼分為機器編碼和工序編碼兩部分，兩部分組成一個染色體作為一個可行解決方案。

a）編碼方式。假 設某車間包含m個工件，每個工件有n個加工工序，則個體位置向量的總長度為2mn，位置向量的各值在［-m，m ］取值。

b）解碼方式。當個體位置向調(diào)度方案轉(zhuǎn)換時，機器分配根據(jù)文獻［22］中所用的方法，使用式（22）將個體位置向量轉(zhuǎn)換為工序可選分配機器集的編號。

u（j）= round（ "1 2λ （x（j）+τ）（s（j）－1）+1） ""（22）

其中：u（j）表示個體j所分配機器在對應的工序可選分配機器集的序號（1≤j≤l）；τ表示工件數(shù)；x（j）表示個體j的位置向量值；s（j）表示個體j對應工序可選分配機器數(shù)；l表 示總工序數(shù)。

在個體位置向量向調(diào)度方案轉(zhuǎn)換時，工序排序部分采用文獻［23］中的排列順序規(guī)則ROV（ranked order value）。首先，將每個個體的位置向量值按照升序進行排序，排序的次序便是 ROV值，按照ROV值所對應的次序?qū)ο蛄恐档某跏脊ば蚓幪栠M行排序，得到工序排序。

6.3 實驗仿真及分析

為了驗證所提算法在解決FJSP上的有效性，本文選取了部分Kacem和Brandimarte的基準算例［21］進行仿真，算例中工件數(shù)為4～20不等，機器數(shù)為5～15不等。將實驗所得結(jié)果分別與改進貓群優(yōu)化算法（improved cat swarm optimization，ICSO） ［24］、啟發(fā)式算法（heuristic algorithm，HA） ［25］、多目標進化算法（multi-objective evolutionary optimization，MEO） ［21］及混合鯨魚優(yōu)化算法（improved whale optimization algorithm，IWOA） ［26］中的實驗結(jié)果對比，對比結(jié)果如表6、7所示，其中 n表示工件個數(shù)，m 表示機器數(shù)量，粗體表示同算例中算法結(jié)果的最優(yōu)值。在算例測試中，為了更好地發(fā)揮SEBBO的性能，參數(shù)設置為以下條件：種群數(shù)量為100，最大迭代次數(shù)800次，每個算例獨立運行10次。

由表6、7可以看出，SEBBO算法在小規(guī)模Kacem算例下均能取得對比文獻中的最優(yōu)值，在Brandimarte這樣的大中型算例中，在MK1、MK3、MK4、MK7及MK8算例測試中均獲得了當前的最優(yōu)值，在MK2、MK5及MK6中效果不太理想，但相差不大。值得一提的是，該算法在MK1和MK7中尋找到新的最優(yōu)值，如圖5所示。從表6、7的結(jié)果總體來看，SEBBO算法應用于FJSP時效果良好。

7 結(jié)束語

本文提出了一種引入物種演化的改進生物地理學優(yōu)化算法，旨在解決生物地理學優(yōu)化算法易發(fā)生早熟收斂、陷入局部最優(yōu)及變異算子破壞較優(yōu)解的問題。該算法考慮棲息地和棲息地之間的差異及整個棲息地的進化情況，將所有棲息地按照物種數(shù)量進行動態(tài)劃分，根據(jù)不同迭代次數(shù)針對不同類型棲息地選擇不同的策略進行協(xié)同進化。在基本變異策略的基礎上提出了一種雙策略協(xié)同變異算子，采用物種更迭和物種進化兩種變異策略滿足多樣性，同時能夠減少對較優(yōu)解的破壞。實驗表明，該算法在收斂速度、收斂精度和穩(wěn)定性等方面都有明顯的優(yōu)勢，且本算法不易被局部最優(yōu)值所限制。最后，將改進算法應用于柔性作業(yè)車間調(diào)度，證明了所提算法在解決 FJSP上的有效性。

參考文獻：

[1] "Simon D. Biogeography-based optimization［J］. IEEE Trans on Evolutionary Computation ，2008， 12 （6）：702-713.

［2] Zhang Xinming， Wang Doudou， Fu Zihao， "et al . Novel biogeography-based optimization algorithm with hybrid migration and global-best Gaussian mutation［J］. Applied Mathematical Modelling ，2020， 86 （10）：74-91.

［3] 張新明，涂強，尹欣欣.混合遷移的高效BBO算法及其在圖像分割中的應用［J］.計算機科學與探索，2016， 10 （10）：1459-1468.（Zhang Xinming， Tu Qiang， Yin Xinxin. Efficient BBO algorithm based on hybrid migration and its application to image segmentation［J］. Journal of Frontiers of Computer Science amp; Technology ，2016， 10 （10）：1459-1468.）

［4] Giri P K， De S S， Dehuri S. Adaptive neighborhood for locally and globally tuned biogeography-based optimization algorithm［J］. Journal of King Saud University-Computer amp; Information Sciences ，2021， 33 （4）：453-467.

［5] Kavah M， Khishe M， Mosvai M R. Design and implementation of a neighborhood search biogeography-based optimization trainer for classifying sonar dataset using multi-layer perceptron neural network［J］. Analog Integrated Circuits and Signal Processing ，2019， 100 （8）：405-428.

［6] Farswan P， Bansal J C. Fireworks inspired biogeography-based optimization［J］. Soft Computing ，2019， 23 （11）：7091-7115.

［7] "Zhao Fuqing， Qin Shuo， Zhang Yi， "et al . A two-stage differential bio- geography-based optimization algorithm and its performance analysis［J］. Expert Systems with Applications ，2019， 115 （1）：329-345.

［8] 葛強，李玉晶，喬保軍，等.微擾動和混合變異的差分生物地理學優(yōu)化算法［J］.計算機工程與設計，2021， 42 （2）：432-441.（Ge "Qiang， Li Yujing， Qiao Baojun， "et al . Differential biogeography optimization algorithm based on micro-perturbation and mixed variation［J］. Computer Engineering and Design ，2021， 42 （2）：432-441.）

［9] 王雅萍，張正軍，顏子寒，等.基于改進的遷移率模型的生物地理學優(yōu)化算法［J］.計算機應用，2019， 39 （9）：2511-2516.（Wang Yaping， Zhang Zhengjun， Yan Zihan， "et al . Biogeography-based optimization algorithms based on improved migration rate models［J］. Journal of Computer Applications ，2019， 39 （9）：2511-2516.）

［10] 馬海平，李雪，林東升.生物地理學優(yōu)化算法的遷移率模型分析［J］.東南大學學報，2009， 39 （S1）：16-21.（Ma Haiping， Li Xue， Lin Dongshen. Analysis of migration rate models for biogeography-based optimization［J］. Journal of Southeast University ，2009， 39 （S1）：16-21.）

［11] 尚玉昌.動物行為研究的新進展（十）：棲息地選擇［J］.自然雜志，2014， 36 （3）：182-185.（Shang Yuchang. New advance on study of animal behavior（X）：habitat selection［J］. Chinese Journal of Nature ，2014， 36 （3）：182-185.）

［12] 王忍忍.種間相互作用與種間功能特征差異、譜系距離關系的檢驗——以天童喬木幼苗實驗為例［D］.上海：華東師范大學，2018.（Wang Renren. Experimental test on the relationship between tree seedling interaction and interspecific functional trait difference and phylogenetic distance in Tiantong region［D］.Shanghai：East China Normal University，2018.）

［13] ""Zhang Qiwen， Hu Songqi. Hybrid quantum particle swarm algorithm based on levy flights［J］. Journal of Computer ，2020， 31 （3）：58-71.

［14] 涂蘭桂.基于低差異序列的搜索算法及其在SNP關聯(lián)分析中的應用［D］.西安：西安電子科技大學，2013.（Tu Langui. An algorithm based on low discrepancy sequence and its application on SNP association analysis［D］.Xi’an：Xidian University，2013.）

［15] "黃光球，劉權宸，陸秋琴.集合種群生物地理學優(yōu)化算法［J］.系統(tǒng)仿真學報，2014， 26 （6）：1217-1224.（Huang Guangqiu， Liu Quanchen， Lu Qiuqin. Metapopulation biogeography-inspired optimization［J］. Journal of System Simulation ，2014， 26 （6）：1217-1224.）

［16] "Awad N H， Ali M Z， Suganthan P N. Problem definitions and evalua- tion criteria for the CEC 2017 special session and competition on single objective real-parameter numerical optimization［R］.Singapore：Nanyang Technological University，2016.

［17] Ma Haiping， Simon D. Blended biogeography-based optimization for constrained optimization［J］. Engineering Applications of Artificial Intelligence ，2011， 24 （3）：517-525.

［18] Garg V， Deep K. Performance of Laplacian biogeography-based optimization algorithm on CEC 2014 continuous optimization benchmarks and camera calibration problem［J］. Swarm and Evolutionary Computation ，2016， 27 （4）：132-144.

［19] Gong Wenyi， Cai Zhihua， 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.

［20] 張新明，康強，王霞，等.差分遷移和趨優(yōu)變異的生物地理學優(yōu)化 算法［J］.小型微型計算機系統(tǒng)，2018， 39 （6）：1168-1177.（Zhang Xinming， Kang Qiang， Wang Xia， "et al . Biogeography-based optimization with differential migration and global-best mutation［J］. Journal of Chinese Computer Systems ，2018， 39 （6）：1168-1177.）

［21] Kacem I， Hammadi S， Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems［J］. IEEE Trans on Systems， Man， and Cybernetics， Part C： Applications and Reviews ，2002， 32 （1）：1-13.

［22] Yuan Yuan， Xu Hua， Yang Jiadong. A hybrid harmony search algorithm for the flexible Job-Shop scheduling problem［J］. Applied Soft Computing ，2013， 13 （7）：3259-3272.

［23] 談超，李小平.雙目標無等待流水線調(diào)度的加權混合算法［J］.計算機科學，2008， 35 （11）：199-202，213.（Tan Chao， Li Xiaoping. Weighed hybrid heuristics for bi-objective no-wait flow shops problem［J］. Computer Science ，2008， 35 （11）：199-202，213.）

［24] 姜天華.貓群優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題［J］.計算機工程與應用，2018， 54 （23）：259-263，270.（Jiang Tianhua. Cat swarm optimization for solving flexible Job-Shop scheduling problem［J］. Computer Engineering and Applications ，2018， 54 （23）：259-263，270.）

［25] Ziaee M. A heuristic algorithm for solving flexible job shop scheduling problem［J］. International Journal of Advanced Manufacturing Technology ，2014， 71 （3）：519-528.

［26] 張斯琪，倪靜.混合鯨魚算法在柔性作業(yè)車間系統(tǒng)中的應用［J］.系統(tǒng)科學學報，2020， 28 （1）：131-136.（Zhang Siqi，Ni Jing. Application of hybrid whale algorithm in flexible Job-Shop system［J］. Chinese Journal of Systems Science ，2020， 28 （1）：131-136.