張丹麗，高彥杰

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

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

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

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

1 多目標(biāo)進(jìn)化的概念

以最小化為例的MOPs 可以用表達(dá)式（1）寫(xiě)成以下形式[1]：

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

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

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

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

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

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

本文采用與NSGA-II[2]相同的適應(yīng)度評(píng)價(jià)方法，計(jì)算個(gè)體的適應(yīng)度。在計(jì)算個(gè)體的的適應(yīng)度時(shí)，不僅考慮支配它的個(gè)體，并用他們之間的距離計(jì)算擁擠距離，利用擁擠距離修改每一個(gè)個(gè)體的適應(yīng)度。

2.2 遷移算子

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

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

2.3 變異算子

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

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

3 MOBBO 的算法描述

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

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

步驟2 利用NSGA-II，計(jì)算每個(gè)個(gè)體的適應(yīng)度H（xi）=（H1（xi），H2（xi），...Hm（xi）），并確定當(dāng)前H 中的非支配個(gè)體。

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

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

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

4仿真實(shí)驗(yàn)與結(jié)果分析

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

4.1 性能評(píng)價(jià)指標(biāo)

本文采用世代距離指標(biāo)評(píng)價(jià)[2]標(biāo)準(zhǔn)來(lái)測(cè)試MOBBO的性能。

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

4.2 結(jié)果分析

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

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

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

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

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

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