改進遷移算子的BBO算法及其在PID參數中的優化

裴 沛，李彩偉，呂波特

（1. 北京中油瑞飛信息技術有限責任公司，北京100029； 2. 國家工業信息安全發展研究中心，北京100040；3. 北京博華信智科技股份有限公司，北京100029）

（*通信作者電子郵箱licaiwei888@sina.com）

0 引言

進化算法常用于求解顯式和隱式函數的極值。與數值求解方法不同，進化算法無需知曉目標函數是否可微。實際上，進化算法不需要目標函數的相關信息。由于這一特性使它們成為一種解決復雜問題的方法［1］。

生物地理學優化（Biogeography-Based Optimization，BBO）算法［2］是由美國的Simon 基于生態系統中各個種群在不同棲息地之間的遷徙、突變、滅絕的一般規律提出，算法可用于函數求解與全局參數優化。BBO 算法也屬于一種進化算法，因對生物在生態系統中的進化機制進行了模擬，具有計算量較小、算法參數少、收斂速度快等特點［3］。

近年來，BBO 算法中涉及的進化機制也已被大量學者進行了研究，研究結果表明，其他進化算法中存在的搜索能力下降現象，在BBO 算法中也同樣存在［4-6］。為解決這個問題，很多學者對BBO 算法從生物地理學原理出發進行了改進。江岳春等［7］將余弦型遷移模型、差分進化算法的變異策略以及動態非均勻變異算子引入生物地理學優化算法，并將其用于求解風電-水電互補優化運行策略的模型，結果表明經改進的BBO 算法比粒子群算法和遺傳算法尋優能力更強，求解的模型精度更高。張文輝等［8］提出了自適應遷移算子和差分進化變異算子，對BBO 算法進行改進，改進算法在保留了棲息地特征的同時，也改善了棲息地間信息交流以及分享的情況，實驗結果表明改進后的BBO 算法全局優化能力得到了進一步增強。陳道君等［9］的研究表明使用柯西分布比高斯分布更易產生遠離原點的隨機數，將其用于改進變異算子能增強BBO算法的全局搜索能力。魯宇明等［10］提出了二重遷移算子和二重變異算子，使得個體在進化中的進化概率更高，并使改進后的BBO 算法全局尋優能力得到進一步提升。Zhang 等［11］將模糊C均值算法和BBO算法結合，用于圖像分割，得到的混合算法較其他算法更優。文獻［12］基于生物地理學算法，提出一種混合遷移多目標優化算法，并在ZDT測試函數進行驗證，表明算法在收斂性和搜索能力方面更優。

以上基于生物地理學原理的改進提升了算法尋優能力，但也在一定程度上增加了算法的復雜性，收斂精度方面仍有待進一步提升。

為加快算法的收斂，并提高算法的收斂精度，避免算法陷入局部最優，本文提出了一種基于改進遷移算子的生物地理學 （Improved Migration Operator Biogeography-Based Optimization，IMO-BBO）算法。結合“優勝劣汰”的進化思想，將自然環境的變化作為影響因素，對不適宜遷移的個體進行淘汰并重新生成。同時引入多種群概念，促使不同種群之間的物種進行信息交互，能很好地增強算法的全局勘探能力。將本文提出的IMO-BBO算法在13個基準測試函數進行測試，結果表明改進算法在大部分測試函數中的全局探索能力、收斂速度和收斂精度上都有顯著提高。經IMO-BBO 算法整定后的PID（Proportional Integral Differential）控制器也得到了更快的響應速度和更穩定的精度。

1 BBO算法原理

BBO 算法來源于生物地理學理論，如圖1 所示，每個棲息地都有對應的適宜度指數（Habitat Suitability Index，HSI），其中待優化問題中可能存在的解實際由棲息地進行表示，棲息地質量的優劣由HSI 來進行表示。影響HSI 的因素包括降雨情況、空氣濕度、環境溫度、植被多樣性等，各種影響因素通過一個適宜度向量（Suitable Index Variable，SIV）來對棲息地進行描述。

圖1 BBO多個棲息地以及遷移過程Fig. 1 Multiple habitats and migration processes of BBO

物種的遷移主要與HSI 有關。較優的HSI 表示棲息地物種多樣性較好；較差的HSI表示物種多樣性受到限制。當HSI較優時，表明棲息地物種數目趨向于飽和，接近棲息地最大容量，會存在較多的物種遷出的現象。而當HSI 保持較差水平時，又會有較多的物種遷入此棲息地［13］。同時，BBO算法對棲息地中可能發生的突發事件進行模擬，使物種的一部分特性發生改變，即令棲息地的物種產生一定程度的突變。各個棲息地間，BBO 算法利用遷移和變異操作［14］增強了物種間的信息交互，使得物種多樣性得到了一定程度的提升。

2 改進的BBO算法

本文受文獻［15］中生物寄生“優勝劣汰”進化思想的啟發，考慮了自然環境等因素對個體遷移過程的影響，提出一種改進的BBO 算法。本文對遷移算子進行了改進，將個體的遷移距離作為影響因素，使不適宜遷移的個體越容易被新個體替換。同時為豐富種群的物種多樣性，進一步加快算法的收斂速度，引入雙種群概念。

2.1 遷移算子的改進

不同棲息地間物種遷移主要有周期性和非周期性之分，周期性主要與繁殖、食物、氣候變化等因素有關，非周期性主要由自然災害引起，與生存條件的惡化有關。

當棲息地Xi中的個體遷移至其他棲息地Xj時，其遷移距離d(Xi，Xj)由式（3）的歐氏距離公式得到。

其中:xi，1為第i個棲息地的第1個個體，n為種群數量大小。

根據棲息地之間的遷移距離進行排序，得到從Xi遷移至不同棲息地的距離系數Wi，遷移距離越遠距離系數大，遷移距離越近系數越小。

當遷移距離增大，個體遷移至目的地所需能量和時間更多，受自然環境等影響而被其他個體替代的可能性越高；當遷移距離越小，個體在遷移過程中只需用更少的能量和更短的時間，因此被替換的可能性相應越小。

另一方面，考慮到優質解本身更有可能是全局最優解，為避免遷移過程中造成優質解的退化，對優質解增加保護措施。個體遷移過程中，被替換的概率按以下公式計算得到:

其中:Pi，j為從棲息地i遷移至棲息地j的個體替換率；wi為遷移過程中的距離系數，wmax為距離系數最大值，與種群數量有關；HSIi為第i個棲息地的適應度值，HSImax為所有棲息地中適應度的最大值。

算法迭代過程中，在保持原先群體大小和開發能力不變的情況下，進一步提高算法對可行解區域的探索能力。本文引入差分進化策略產生新個體，可在一定程度上保證群體的多樣性。新個體生成方式如式（6）所示:

其中:xbest，k為當前最優解的第k個個體，xr1，k、xr2，k、xr3，k、xr4，k為隨機選擇的4個不同個體。

由式（6）可知，新個體的信息由最優解和兩個差分公式計算得到。而且縮放系數F可以對探索和開發能力進行平衡。當F=0時，新個體直接獲取最優個體的信息，提高了算法的開發能力。當F增大時，新個體從其他個體獲取的信息逐步增加，使算法在探索可行解的能力上增強，但相對地會弱化最優解的開發能力。為平衡對局部和全局的搜索能力，本文選取F=0.5。

2.2 多種群協同策略

多種群［16］是將多個種群按照不同或相同的初始環境和約束條件，各自獨立進化，是一種保持種群多樣性的有效方法。多種群策略在其他算法中得到了大量研究和使用［17-20］，但鮮有在BBO算法中使用的報道。

多個種群進化過程迭代到一定次數時，按一定條件對種群間的個體信息進行交流和協作。因各個種群在進化時具有獨立性，能較好地保證種群多樣性。同時不同種群間優秀個體的信息參與信息交換可以提高收斂速度。

常見的協作算子有長方體交叉算子、離散交叉算子、兩點交叉算子、算術交叉算子等［21］。本文采用雙種群的協同策略，選擇算術交叉算子為協作算子。種群間的交叉概率由概率pc決定，若滿足rand(0，1)＜pc，則執行協作算子操作；否則不執行協作算子。

在IMO-BBO 算法中，當使用算術交叉算子對種群1 中的個體Xi進行操作，需從種群2 中選擇當前HSI 最小的個體Xj，即適應度最佳的個體，按以下公式計算得到新的個體:

其中:r為交叉因子，X′i和X″i分別表示計算得到的新個體。若新個體比原個體Xi具有更好的適應度，則將原個體進行更新。當在種群2應用協作算子時，則選取種群2的各個個體與種群1 的最優個體執行協作算子操作，以生成新的個體。通過將種群中的個體與其他種群的適應度最佳的個體進行信息交互產生的兩個新個體，能更好地豐富種群多樣性，促進種群的進化。

2.3 算法基本流程

IMO-BBO算法的算法流程如圖2所示。

圖2 改進BBO算法流程Fig. 2 Flow chart of improved BBO algorithm

具體步驟如下:

1）設定IMO-BBO相關參數，初始化種群數量、迭代次數、棲息地的突變率、棲息地的適宜度向量SIV。

2）分別設定種群1 和種群2 的參數，初始化交叉概率pc、交叉因子r。

3）計算棲息地中物種的遷入遷出概率。

4）執行改進的遷移操作、變異操作。

5）當種群1 和種群2 分別將此次迭代步驟的3）～4）都執行完畢，執行協作算子。結合各個種群的交叉因子r，計算得到新的個體，若新個體的HSI 值更小，則將原個體更新為新個體。

6）判斷是否滿足終止條件，若不滿足，則繼續執行步驟7；否則輸出計算結果，并退出。

7）分別更新種群中的精英個體，并使用精英個體替換掉種群中適應度最差的n個個體，并重復執行步驟3）～6）。

雖經協作算子進行個體信息交互后的個體不一定最優，但是這樣的個體為種群提供了更多可能性，與BBO 算法的變異操作相比，在尋找最優解方面有效性更高，從而提高了對求解問題的收斂速度。

3 改進算法在PID參數優化中應用

在工業的過程控制領域，PID 控制策略在控制系統中所占的比例超過90%，而所配置PID 參數會直接影響到系統運行的性能和穩定性，因此獲取一組合適的PID 參數非常關鍵。隨著群智能算法等人工智能算法的迅速發展，很多新的參數優化方法也被用于PID 控制器參數的整定。其中，文獻［22］根據種群內相似度調整變異算子，提出一種自適應變異的差分進化算法，并成功應用于PID 參數整定優化。本文中的改進BBO 算法也屬于群智能優化算法的一種，由于其收斂精度高、尋優性能穩定的特點，能很好地對PID 控制器的參數進行尋優。

PID控制器的公式可以由式（9）表示:

其中:u(t)為系統的輸出，e(t)為系統輸入與輸出的誤差。并由比例增益系數Kp，積分時間Ti，微分時間常數Td組成控制器的參數。為方便分析和計算，將式（9）替換為如下形式:

其中有Ki=Kp/Ti，Kd=KpTd。Ki為積分增益系數，Kd為微分增益系數。

動態性能指標有上升時間、調節時間、峰值時間、超調量、穩態誤差等，但這些指標相互矛盾，無法同時滿足。為評價系統優化過程中的性能，需要選擇另一類型的性能指標進行評價。常見的性能指標有時間絕對偏差積分（Integral Time Absolute Error，ITAE）、絕 對 誤 差 積 分（ Integral Absolute Error，IAE）、時間誤差平方積分（Integral Time Square Error，ITSE）、平方誤差積分（Integral Square Error，ISE）等。

改進后的IMO-BBO算法PID參數優化目標是在給定的尋優控件中，尋找到一組適宜的Kp、Ki、Kd，使得系統的性能指標達到最好。本文選用ITAE 作為評價PID 算法性能的指標，表達式如式（11）所示:

4 仿真實驗

實驗中采用表1 中的13 個基準測試函數進行測試，測試函數在可分解性、多峰、作用域等性質上各有不同。實驗所用計算機配置為:Intel i5-3210M，2.5 GHz 雙核處理器，Windows 7操作系統，所有算法均采用Matlab 2015b實現。

其中，函數f6、f8、f10、f11、f12、f13都是單峰函數，在搜索作用域中有且僅有一個局部極小值。函數f1、f2、f3、f4、f5、f7、f9是多峰函數，在進行搜索的作用域中有大量局部極小值。其中，f1、f3、f7的局部最優點數量與函數維數呈正相關，為指數關系增長。大量的局部極小值會使尋優難度增大。

表1 基本測試函數特性Tab. 1 Features of benchmark functions

4.1 IMO-BBO中改進算子貢獻度分析

為分析本文中引入的改進遷移算子和雙種群策略算子對原BBO 算法的貢獻程度，對這兩個算子進行實驗驗證。這里將基于改進遷移算子的BBO 算法簡稱為“模型1”，將基于雙種群策略算子的BBO算法簡稱為“模型2”。

BBO 算法部分的初始化參數設置一致:棲息地數量為50，迭代的最大次數均為50次，個體變異率為0.05，最大遷入率和最大遷出率均為1。其中，模型2的交叉概率為0.1，交叉因子為0.3。選用蒙特卡羅方法對以上問題進行模擬實驗，分別進行50輪實驗，得到的結果如表2所示。

表2 是對不同維度、不同性質的測試函數、不同優化算法進行實驗所得到的最小HSI 結果，HSI 越小表示尋優結果越佳。表中d= 1 表示測試函數為一維函數，d= 20 為維數為20的高維函數。

表2 不同測試條件下的尋優結果Tab. 2 Optimization results under different test conditions

從表2 中可以看出:在對低維的一維函數進行最小值尋優時，相比于BBO 算法，模型1 和模型2 不論是在單峰和多峰函數上都表現出了很強的搜索能力，在函數f2和f9上找到了更優的解；在對維數為20 的高維函數進行測試時，13 個測試函數中，有11 個得到的結果比BBO 算法更好。因為模型1 中的改進算子通過差分進化策略生成新的個體，使最優解的局部勘探能力得到了加強，模型2 中的協作算子通過種群間的信息交互，豐富了種群的多樣性，使其具有更強的全局搜索能力。

4.2 IMO-BBO與其他算法的對比

為評估改進后IMO-BBO 算法在最優解搜索能力、最優解精度、動態穩定性，將本文提出的IMO-BBO 算法與基于協方差遷移算子和混合差分策略的BBO（Covariance Matrix based Migration BBO hybrid with Differential Evolution，CMM-DE/BBO）算法［23］和BBO 算法進行比較。BBO 算法部分的初始化參數與上文一致。其中，IMO-BBO 算法的交叉概率為0.1，交叉因子為0.3。

選用蒙特卡羅方法對以上問題進行模擬實驗，且分別用不同的優化算法對表1 中的13 個測試函數進行50 輪實驗，得到的結果如表3所示。其中，表3是各算法對不同維度和不同測試函數進行優化后得到的最小HSI 值和平均HSI 值，表中對適應度值更小的結果進行加粗。

由表3 中得到的最小HSI 值部分看出:在函數維度為1時，相比于其他算法，改進后的IMO-BBO 算法在單峰函數和多峰函數的測試中對最優解有更強搜索能力，且在多峰函數f2，f9上得到了更小的HSI；在函數維數為20 時，IMO-BBO 算法在12 個測試函數上得到了比其他算法更好的結果。說明IMO-BBO 算法有尋優能力更強、收斂精度更高的特點，在問題求解精度方面有了更有效的提高。同時在數值優化方面，該算法是一種行之有效參數尋優算法。

同時，因IMO-BBO 算法需對遷移距離、雙種群的尋優以及種群間的協作進行計算，總的時間復雜度相比BBO 算法更高，這與改進算法對局部和全局尋優能力進行平衡有關。為評價IMO-BBO 算法的穩定性，避免單次優化結果不準確，將幾種算法分別進行了50 次蒙特卡羅實驗，并分別記錄了各算法每次運行結束后的HSI 值，得到表3 中各算法的平均HSI。可以看出，在低維函數和高維函數的尋優能力上，CMM-DE/BBO算法與IMO-BBO算法實力相當，但IMO-BBO算法在更多的測試函數中表現更佳，經50 次模擬實驗得到了HSI 最優的結果最多，在尋優能力上具有更優良的性能?？偟膩碚f，IMO-BBO 算法在大部分的測試函數中有更理想的結果，同時能保證較穩定的全局尋優能力。

表3 蒙特卡羅尋優HSI最小值與平均值Tab. 3 Minimum and average HSI values of Monte Carlo optimization

圖3 分別展示了IMO-BBO 算法、CMM-DE/BBO 算法和BBO 算法（以下簡稱為“3 種BBO 算法”）對Sphere 函數尋找函數極小值時HSI 隨迭代次數的變化情況。其中，上文模擬實驗使用的初始化參數，依舊作為3 種BBO 算法的初始化參數。

圖3 三種BBO算法在Shpere函數中尋優情況Fig. 3 Optimization results on Sphere function of three BBO algorithms

從圖3 的三種BBO 算法優化Sphere 函數的HSI 變化情況可以看出，在前15 次迭代中，3 種BBO 算法收斂速度相當，其中IMO-BBO 算法的收斂速度更快。圖4 中包含了從第25 次至50 次迭代放大后的HSI變化情況，可以看出IMO-BBO 算法相較于其他2種算法得到的HSI值更小。

由上述結果可知，相比于其他兩種尋優算法，改進后的IMO-BBO 算法具有更好的最優值搜索能力。主要在于對算法做了以下改進:1）對遷移操作的改進，使算法能在最優解附近做進一步搜索，提升了局部搜索能力。2）雙種群獨立進化后，使用協作算子產生新解，使得算法的全局搜索范圍加大，增強了算法對最優解的探索能力。

圖4 三種BBO算法在Sphere函數中尋優情況（放大）Fig. 4 Optimization result of Sphere with three BBO algorithms（magnified）

4.3 PID控制器參數整定測試

為表明改進的IMO-BBO 算法在全局最優能力和搜索穩定性的特性，本文將算法應用于PID 參數的整定。選擇的被控對象為直流電機，被控對象的數學模型如下所示:

選用IMO-BBO 算法、CMM-DE/BBO 算法、BBO 算法進行比較，算法的適應度指標HSI如式（11）所示。其中，種群數量為50，變異率為0.05，最大迭代次數為50 次。圖5 是兩種方法尋優過程中適應度指標函數。

圖5 PID優化過程中的適應度變化曲線Fig. 5 Fitness change curve of PID optimization process

圖5 是PID 參數優化過程中HSI 變化情況。PID 整定后的階躍響應曲線如圖6 所示。從中可以看出，另外兩種BBO算法和原BBO 算法相比，收斂速度更快。從圖6 和表4 可以看出，同樣經過50 次迭代，本文提出的IMO-BBO 算法確實能得到更好的可行解。

圖6 優化后的PID階躍響應曲線Fig. 6 Optimized PID step response curve

由圖5 看出優化過程中，適應度指標HSI 更小時，獲得的PID 控制器控制效果更佳。同時，IMO-BBO 使得PID 控制的動態性能指標得到了改善，特別是ITAE 和適應度指標函數，雖然超調量稍微比CMM-DE/BBO 算法大，但上升時間和調節時間更小。

表4 不同算法在參數整定的系統動態響應性能Tab. 4 System dynamic response performance of different algorithms in PID parameter tuning

5 結語

本文針對BBO 算法在迭代后期搜索動力不足、收斂精度不高的問題，提出了一種改進遷移算子的生物地理學算法。結合“優勝劣汰”的進化思想，通過模擬自然環境因素對物種遷移過程的影響，對不適宜遷移的個體進行選擇性的替換。并引入多種群概念，在保證兩個種群并行獨立進化的同時，通過協作算子令兩個種群間產生信息交互，使改進后的算法有更高的求解精度和更快的收斂速度。為驗證新算法的尋優能力，用13 個常用基準測試函數，在單峰、多峰、高維情況下分別與BBO、CMM-DE/BBO 算法進行了比較，數值實驗結果表明，在收斂速度以及對最優解的搜尋能力上，本文所提出的IMO-BBO 算法在測試函數上的表現優于其他幾種算法。將改進后的IMO-BBO 算法用于PID 控制器參數整定，得到整定后的PID 參數，仿真結果表明該方法優化后的控制器能有更好的控制性能，也進一步驗證了改進后IMO-BBO 算法的優越性能。