多目標的混合生物地理學優(yōu)化算法研究

張丹麗，高彥杰

（上海電力大學電子與信息工程學院，上海 200090）

多目標優(yōu)化是指目標函數(shù)在兩個以上且不同目標不能進行比較的問題。在實際生活與科學應用中，多目標優(yōu)化的問題（MOPs）隨處可見。這些目標的優(yōu)化之間有時會相互產(chǎn)生抵觸，致使一個子目標的更新或者修復會導致另一個子目標的性能被破壞。MOPs 解表現(xiàn)為一組折中解，即為Pareto 最優(yōu)解。進化算法（MOEAs）以其搜索的全局解逐漸成為解決MOP 問題的有效工具。

BBO 算法是美國學者Simon 基于生物地理學理論，于2008 年提出的一種群智能優(yōu)化算法[1]。BBO 算法模擬了自然界物種在不同棲息地之間的遷移行為以及棲息地自身生態(tài)環(huán)境的變異現(xiàn)象。棲息地通過遷移信息的互換以及共享，通過變異改變生存環(huán)境，因此，BBO 算法已經(jīng)引起了學術界學者廣泛的興趣，但關于BBO 應用于MOPs 的研究卻很少。

本文提出了一種生物地理學多目標優(yōu)化算法來求解MOPs。在該算法中，將BBO 與NSGA-II[2]結合，采用種群的非支配可行解以及擁擠距離對個體進行綜合評價；然后提出了改進的遷移算子，增強其多樣性，通過與經(jīng)典的NSGA-II、MOEA/D、MOPSO 算法[2-4]進行比較，所得結果表明了所提算法的有效性。

1 多目標進化的概念

以最小化為例的MOPs 可以用表達式（1）寫成以下形式[1]：

式中，x=（x1，...xn）∈X?Rn是n 維的決策變量；X 是n 維的決策空間；y=（y1，...ym）∈Y?Rm是m 維的目標向量；Y是m 維的目標空間；F（x）定義為由決策空間向目標空間映射的函數(shù)。

2 基于生物地理學優(yōu)化的多目標優(yōu)化算法

BBO 算法是通過模擬種群的物種遷移實現(xiàn)一個尋優(yōu)的過程。其中，棲息地（Habitat）為優(yōu)化問題的一些可能解，而棲息地指數(shù)變量（suitability index variable，SIV）則代表的是解變量，棲息地的好壞程度則是適應度指數(shù)（habitat suitability index，HSI）表示的[1]。

由于BBO 算法自身不具有處理MOPs 的能力，本文則建立了針對于BBO 算法的多目標的優(yōu)化模型。首先，對于棲息地適應度指數(shù)進行了重新定義，將它與經(jīng)典的進化的多目標算法NSGA-II[2]框架結合。因為原BBO 的進化策略以及它的改進方法只能適用于單目標優(yōu)化問題，并不能充分滿足多目標優(yōu)化的需求。下面為棲息地適應度指數(shù)的重新定義。

2.1 棲息地適應度指數(shù)的確定機制

在SOPs 中，BBO 中的HSI 則被認為是一個相當于對應優(yōu)化問題的目標函數(shù)。然而，與單目標優(yōu)化不同的地方就是，多目標優(yōu)化不僅包含只有唯一一個解，是使用一組折中解Pareto 的非支配解集來實現(xiàn)平衡每個目標。所以，先前關于HSI 的確定和計算方法不能再廣泛應用于MOBBO 中，我們可以通過個體的Pareto 的支配關系對其HSI 重新進行定義。

本文采用與NSGA-II[2]相同的適應度評價方法，計算個體的適應度。在計算個體的的適應度時，不僅考慮支配它的個體，并用他們之間的距離計算擁擠距離，利用擁擠距離修改每一個個體的適應度。

2.2 遷移算子

在BBO 中，有兩種類型的算子被認為是主要的：一種是變異算子，另一種類型就是遷移算子。文中的遷移算子是BBO 遷移算子的一個推廣。隨著迭代次數(shù)的增加，解Hi比解Hj更合適。解決方案不僅受好的解決方案的影響且受解決方案本身的影響，避免種群陷入局部收斂，增強了種群的多樣性。修改后的遷移公式可以定義為：

其中，Hi是遷入島嶼，Hk是遷出島嶼，Hi（j）是第i 個解的第j 維，上式方程意味著解Hi和Hk改變了解Hi的特征。換句話說，遷移后的新解決方案由兩個組件組成：從自身遷移功能和另一個解決方案。特征從自身以及另一個解決方案遷移。

2.3 變異算子

在BBO 中，變異操作將被隨機生成新的解集去代替。其會影響B(tài)BO 算法的搜索性能，將DE 合并到單目標優(yōu)化問題的遷移過程中。我們的算法在變異過程中加入了DE。該算法在最優(yōu)解附近進行調(diào)整，從而找到非支配解。在MOBBO 中，通過結合DE 對變異算子進行修改，得到新的可行解。根據(jù)下式產(chǎn)生突變個體：

Hi（j）=Hi（j）+c1*（Hbest（j）-Hi（j））+c1*（Hr1（j）-Hr2（j）），（3）其中Hi（j）為突變個體，c1為突變比例因子，其值通常設置為0.5。Hr1，Hr2是隨機選取的兩個解，Hbest（j）是當前迭代的最佳解決方案。這種突變方案傾向于增加種群間的多樣性。它作為一個微調(diào)單元，有助于實現(xiàn)全局最優(yōu)解。

3 MOBBO 的算法描述

基于生物地理學多目標優(yōu)化算法（MOBBO）主要特點是通過生物遷移機制算子、變異機制算子和NSGA-II等機制來實現(xiàn)對不同種群的環(huán)境和優(yōu)化生態(tài)更新。改進的一種遷移機制算子可以使得優(yōu)秀的生物個體信息經(jīng)過獲取后能夠得到實時共享，增強收斂性；同時采用了變異機制算子，可以進一步提高和大大改進對于群體的多樣性，并極大可能地產(chǎn)生更優(yōu)秀的個體；本文提出的MOBBO 算法具體步驟如下所示。

步驟1 初始化I、E、α、c1、c2這些參數(shù)。隨機的生成N個個體，則其初始種群為H={xi，i=1，2，...N}。

步驟2 利用NSGA-II，計算每個個體的適應度H（xi）=（H1（xi），H2（xi），...Hm（xi）），并確定當前H 中的非支配個體。

步驟3 判斷是否滿足終止條件。若滿足終止條件，則轉到步驟6，否則繼續(xù)步驟4。

步驟4 根據(jù)遷入率λi和遷出率μi，按式（2）和（3）對個體進行遷移和變異操作，產(chǎn)生新的種群H'。

步驟5 合并H 和H'作為父代種群H，轉到步驟2。步驟6 輸出非支配種群Hn。

4仿真實驗與結果分析

為了對本文所提出的MOBBO 算法對于如何解決MOPs 的有效性問題進行了驗證，將其結果與NSGA-II、MOEA/D、MOPSO 這三種類型的MOEAs 在兩個目標ZDT和三個目標DTLZ 的測試問題上的結果進行了實驗分析對比。MOBBO 與其他三種算法的初始種群規(guī)模設置為100。MOBBO 中I=E=1，α=0.9，c1=c2=0.5。其余三種算法設置參考文獻[2-4]。

4.1 性能評價指標

本文采用世代距離指標評價[2]標準來測試MOBBO的性能。

其中，nPF為近似Pareto 前沿的解的數(shù)目；di為近似Pareto前沿上第i 個解到理想Pareto 前沿之間的最小歐式距離。GD 越小，表明近似Pareto 前沿解集越逼近理想Pareto 前沿面，算法收斂性越好[2]。

4.2 結果分析

圖1 中（a）～（d）給出了MOBBO 算法對ZDT1-ZDT4系列測試函數(shù)的理想Pareto 解的近似；圖中（e）、（f）給出了對DTLZ1-DTLZ2 系列測試函數(shù)的理想Pareto 解的近似?？梢愿又庇^地看出該算法求解多目標的性能。該算法對于ZDT1-ZDT4 均能從分布上收斂到真正的Pareto前沿，且它的分布性和收斂性良好，對于DTLZ 系列的兩個被用來進行測試的函數(shù)，該算法中MOBBO 解集盡管它們都能在實踐中收斂并達到真正的Pareto 前沿，但其中的分布性相對比較差。

圖1 MOBBO 對ZDT 和DTLZ 系列測試函數(shù)所得Pareto 前沿

表1 4 種算法分別用于測試函數(shù)ZDT 和DTLZ 下的GD 指標

表1 給出MOBBO 及3 種算法進行ZDT 和DTLZ 測試函數(shù)的實驗結果，包括平均值（含在括號外）和標準差（含在括號內(nèi)）。由表1 可以看出算法MOBBO 與3 種經(jīng)典算法相比，MOBBO 具有一定的優(yōu)勢。

5 結束語

鑒于目前多目標優(yōu)化算法所存在的求解復雜多目標優(yōu)化問題時存在的收斂性較差等問題。本文提出了一種生物地理學優(yōu)化算法MOBBO。首先，該算法將BBO 本身的機制與NSGA-II 模型相結合，構建了一個適用于BBO的MOEAs 模型。其次，改進BBO 的遷移機制算子應用于群體的進化，增強了種群的多樣性；最后，提出一種經(jīng)過改進的變異算子，防止種群陷入局部收斂。通過在ZDT和DTLZ 測試函數(shù)上進行的仿真實踐結果表明，本文所研究的MOBBO 算法相比于現(xiàn)有的多種MOEAs 還是具有一定競爭性的，并且能夠有效地求解復雜的多目標優(yōu)化問題。