一種用于求解多目標(biāo)優(yōu)化問題的改進(jìn)MBO算法*

蒙麗萍，姜思佳，韋 量，王 勇

（1.廣西西子科技有限責(zé)任公司，廣西南寧 530009；2.柳州城市職業(yè)學(xué)院，廣西柳州 545036；3.廣西金融職業(yè)技術(shù)學(xué)院，廣西南寧 530007；4.廣西民族大學(xué)人工智能學(xué)院，廣西南寧 530006）

0 引言

近年來，對現(xiàn)有群智能優(yōu)化算法進(jìn)行改進(jìn)，并將其應(yīng)用于求解工程等方面的優(yōu)化問題，已經(jīng)成為國內(nèi)學(xué)者的一個(gè)研究熱點(diǎn)。例如，國內(nèi)研究者針對粒子群算法(PSO)[1]、蟻群算法(ACO)[2]、人工蜂群算法(ABC)[3]、人工魚群算法(AFSA)[4]等現(xiàn)有的群智能算法提出了各種版本的改進(jìn)算法(對PSO的改進(jìn)算法見文獻(xiàn)[5-11]，對ACO的改進(jìn)算法見文獻(xiàn)[12-14]，對ABC的改進(jìn)算法見文獻(xiàn)[15-20]，對AFSA的改進(jìn)算法見文獻(xiàn)[21-23])，并將其應(yīng)用于求解工程等方面的問題。目前，改善現(xiàn)有群智能優(yōu)化算法的性能仍然是智能計(jì)算領(lǐng)域一個(gè)重要的研究方向。

大紅斑蝶優(yōu)化算法(Monarch Butterfly Optimization，MBO)是Wang和Cui等人[24]于2015年提出一種新的群智能隨機(jī)優(yōu)化算法。然而，標(biāo)準(zhǔn)MBO算法在應(yīng)用于求解復(fù)雜函數(shù)優(yōu)化問題時(shí)仍出現(xiàn)早熟收斂現(xiàn)象、存在陷入局部最優(yōu)之不足。針對這一問題，筆者首先提出一種改進(jìn)的MBO算法，然后將其用于求解多目標(biāo)優(yōu)化問題，并通過數(shù)值實(shí)驗(yàn)仿真來檢驗(yàn)本文算法的有效性和可行性。

1 MBO算法簡介

MBO算法將群體搜索空間分成Land1和Land2兩兩不相交的區(qū)域；個(gè)體位置更新有兩種方式：一是個(gè)體產(chǎn)生后代，一是個(gè)體移動導(dǎo)致位置變更。而個(gè)體后代的產(chǎn)生是通過遷徙算子得以實(shí)現(xiàn)。MBO算法中個(gè)體搜索方向由遷徙算子和調(diào)整算子確定。MBO假定：①大紅斑蝶群體僅限于Land1和Land2這兩個(gè)區(qū)域活動。②每一個(gè)體后代均經(jīng)由遷徙算子產(chǎn)生，并規(guī)定：每產(chǎn)生一只新子代，相應(yīng)就會死去一只父代；若新子代優(yōu)于其父代，則以子代替換父代，否則丟棄該子代。③具有最優(yōu)適應(yīng)度值的個(gè)體則保留到下一代，且不對其進(jìn)行任何變化操作。

個(gè)體位置更新方法：設(shè)種群個(gè)數(shù)為NP，位于Land1的個(gè)體數(shù)為NP1(=ceil( p × NP))（記為Subpopulation1），位于Land2的個(gè)數(shù)為NP-NP1=NP2（記為Subpopulation2）。其中ceil(x)為區(qū)間[ x，[ x]+1]中的最小整數(shù)，[ x]為取整函數(shù)，p為NP1與NP之比率。(注：MBO讓p=5/12（遷移率）、NP1=BP×p（Land1中個(gè)體數(shù)）和NP2=NP-NP1（Land2中個(gè)體數(shù)）均取定值。)

1)遷徙算子。MBO 算法表示個(gè)體位置遷移的方程如下：

其中peri為遷徙期（MBO 中，取peri=1.2），rand為[0，1]中的隨機(jī)函數(shù)。當(dāng)r＞p時(shí)，則新產(chǎn)生的個(gè)體（大紅斑蝶）第k維則由式（3）確定：

2)調(diào)整算子。MBO算法中的個(gè)體還可通過如下方法來變更位置：對于個(gè)體j的所有維，若rand≤p，則該個(gè)體按式(4)更新位置：

若rand＞p，則該個(gè)體按式(5)變更位置：

其中BAR為調(diào)整率（MBO算法置BAR=p），α為權(quán)重，dx為j個(gè)體的步長。dx和α分別由式(7)和式(8)確定：

其中Smax為全體個(gè)體之最大步長，t為當(dāng)前代數(shù)。

2 改進(jìn)的MBO算法

本文對MBO采用的改進(jìn)策略如下：

第一，本文算法置遷移率為p=0.2+0.6×rand()，其中rand()為[0，1]上的隨機(jī)函數(shù)，從而NP1=BP×p（Land1中個(gè)體數(shù)）和NP2=NP-NP1（Land2中個(gè)體數(shù)）都是隨機(jī)數(shù)。換言之，在Land1和Land2中活動的個(gè)體，有些個(gè)體可能從Land1進(jìn)入Land2，有些個(gè)體可能從Land2進(jìn)入Land1，NP1和NP2均為變數(shù)。

第二，本文算法讓Land1和Land2中的每一個(gè)體都有可能產(chǎn)生后代。

第三，設(shè)群體至t時(shí)刻找到的食物最豐富之處為Gtbest=(gt1，…，gtD)。由于大紅斑蝶喜歡飛到食物最豐富之處去覓食，即會有較多的個(gè)體飛到Gtbest的周圍覓食。針對這一現(xiàn)象，我們用如下式（9）來表達(dá)個(gè)體飛到Gtbest的周圍覓食的方程：

第四，本文針對MBO中的式(5)，考慮個(gè)體在飛行運(yùn)動中受到風(fēng)力的影響，對其作如下改進(jìn)：若rand ＞p，則

其中r3表示t時(shí)刻從NP2(即在Land2中活動的大紅斑蝶群體)中隨機(jī)選出的某一個(gè)體，即r3∈{1，…，NP2}，ε(t)=(0.5-rand())× s(t)，s(t)=1/(1+exp(-4t))，rand()為[0，1]上的隨機(jī)函數(shù)。

設(shè)種群至t時(shí)找到的最優(yōu)位置為Gbtest=(g1t，…，gDt)，i個(gè)體的位置為xti=(xti，1，…，xti，D)，NP為種群規(guī)模，i=1，…，NP。

1）種群分配方法。

對于第t代，先求適應(yīng)度值f (xti)，i=1，…，NP。然后將全部個(gè)體按f (xti)(i=1，…，NP)的優(yōu)劣排序（即最優(yōu)者位列第1，次優(yōu)者位列第2，依次類推）。記i個(gè)體位列第sti，本文稱

為 i 個(gè)體的遷移決策因子（Migration decision factor）。mig_Dti確定i個(gè)體下一步的遷移地。

最后將種群個(gè)體隨機(jī)分配到Land1或Land2中(依據(jù)遷移 率 p=0.2+0.6×rand())。分 配 方 法 如 下 ：若mig_Dti＜ p，則i個(gè)體飛入Land2中（個(gè)體數(shù)為NP2）。否則，飛入Land1中（個(gè)體數(shù)為NP1）。

2）實(shí)現(xiàn)方法和步驟。

·在Land1中活動的NP1只個(gè)體，均按公式（1）變更位置。

·在Land2中活動的NP2只個(gè)體，按如下方法變更位置：先求出i個(gè)體的排位sti。其次利用式（11）計(jì)算mig_Dti。最后按如下方法選擇運(yùn)動方程：任取隨機(jī)數(shù)rand ∈[0，1]，若mig_則選擇式（9）確定位置；mig_Dti≤ rand，則選擇式（10）確定位置 ；若 mig_Dti＞rand，則該個(gè)體要重新初始化。

實(shí)現(xiàn)步驟如下：

Input：目標(biāo)函數(shù)f (X )、群體規(guī)模NP、最大迭代次數(shù)max Gen。

Step1：

Set t=1，隨機(jī)初始化群體X1i([i=1，…，NP])，計(jì)算f (X1i)，令Gtbest為群體當(dāng)前最優(yōu)位置。

Step2：

按“種群分配方法”將種群分配到區(qū)域Land1或區(qū)域Land2中。

Step3：

Land1中的個(gè)體按公式（1）確定位置。

Step4：

計(jì)算Land1中每一個(gè)體在新位置的適應(yīng)度值，并與當(dāng)前群體最優(yōu)位置進(jìn)行比較，判斷是否需要更新當(dāng)前群體最優(yōu)位置。

Step5：

對于Land2中i個(gè)體，利用式（11）求出mig_Dti；然后取一個(gè)隨機(jī)數(shù)rand ∈[0，1]，若mig_（9）確定其下一步的位置；若其按公式(10)確定其下一步的位置；若mig_Dti＞ rand，則其將重新初始化。

Step6：

計(jì)算Land2中每一個(gè)體在新位置的適應(yīng)度值，并與當(dāng)前群體最優(yōu)位置進(jìn)行比較，判斷是否需要更新當(dāng)前群體最優(yōu)位置。

Step7：

將Land1中和Land2中個(gè)體合并，組成新的群體規(guī)模為NP的種群。

Step8：

若滿足算法終止條件，則輸出最優(yōu)位置及相對應(yīng)的目標(biāo)值，算法終止；否則，轉(zhuǎn)向Step2。

3 數(shù)值實(shí)驗(yàn)

利用數(shù)值實(shí)驗(yàn)與仿真來檢驗(yàn)本文算法的優(yōu)化性能。我們將本文算法與MBO[24]、標(biāo)準(zhǔn)PSO[1]作數(shù)值優(yōu)化實(shí)驗(yàn)對比與分析。在數(shù)值仿真實(shí)驗(yàn)中，我們分別選取了3個(gè)多目標(biāo)優(yōu)化問題，用來測試這三種算法各自的函數(shù)優(yōu)化性能。這3個(gè)多目標(biāo)優(yōu)化問題分別如下：

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

本文將IMBO、MBO和PSO應(yīng)用于求解多目標(biāo)優(yōu)化問題時(shí)，分別記為MOIMBO、MOMBO和MOPSO。

關(guān)于多目標(biāo)優(yōu)化問題，需要介紹以下幾個(gè)基本概念。

多目標(biāo)優(yōu)化問題（MOP）：設(shè)X=(x1，…，xn)為決策變量，滿足

約束條件。設(shè)有r個(gè)目標(biāo)，且這r個(gè)優(yōu)化目標(biāo)是相互沖突的，優(yōu)化目標(biāo)可表示為

尋找X*=(x*1，…，x*n)，使f (X*)在滿足約束（12）和（13）的同時(shí)達(dá)到最優(yōu)。

Pareto最優(yōu)狀態(tài)：點(diǎn)x→*∈ Ω（Ω為決策變量空間）是Pareto最優(yōu)需要滿足下面兩個(gè)條件中任一個(gè)，即任意x→∈Ω，x→*∈ Ω是Pareto最優(yōu)，要么

要么至少存在一個(gè)i ∈I使得

Pareto 支 配 ：向 量 u→=(u1，…，uk)支 配 向 量 v→=(v1，…，vk)表示為u→ -? v→，當(dāng)且僅當(dāng)

Pareto最優(yōu)集：對于多目標(biāo)優(yōu)化問題f→(X )，Pareto最優(yōu)集P*定義為

Pareto最優(yōu)前沿：對于多目標(biāo)優(yōu)化問題f→(X )和Pareto最優(yōu)集P*，最優(yōu)前沿PF*定義為

·ER（誤差比）：該指標(biāo)用來描述算法產(chǎn)生的非劣解中，不屬于真實(shí)Pareto前沿的解所占的百分比：

其中n為所獲得的非劣解個(gè)數(shù)，若解i屬于Pareto最優(yōu)解集，則ei=0；否則，ei=1。

ER值越小，屬于Pareto最優(yōu)解集的非劣解所占比例就越高。ER=0表示所有非劣解都位于真實(shí)的Pareto前沿上。

·GD：該指標(biāo)用來表示算法所獲得的非劣解與問題的真實(shí)Pareto前沿之間的距離：

其中disti表示第i個(gè)非劣解與真實(shí)Pareto前沿之間的最短距離。

·SP：該指標(biāo)表示非劣解在目標(biāo)空間上的分布范圍。計(jì)算方法如下：

由于ER，GD和SP三個(gè)指標(biāo)總體上刻畫了算法針對多目標(biāo)優(yōu)化問題的優(yōu)化性能，而且普遍被智能優(yōu)化領(lǐng)域研究者所普遍采用。故本文以ER，GD和SP作為算法求解多目標(biāo)優(yōu)化問題的優(yōu)化性能評價(jià)指標(biāo)，用ER，GD和SP分別來評價(jià)算法所獲得的解中不屬于真正Pareto最優(yōu)解的百分比、解與真實(shí)Pareto前沿之間的距離和解的分布范圍。

對于MOIMBO，MOMBO和MOPSO，均采用外部檔案庫及自適應(yīng)網(wǎng)格法來接受和更新Pareto最優(yōu)解。三種算法的種群規(guī)模都是50，最大迭代次數(shù)均為1000次，外部檔案庫大小均為100，搜索空間都是30維；MOIMBO 與IMBO的其他參數(shù)設(shè)置相同，MOMBO及MOPSO也分別與MBO及PSO的其他參數(shù)設(shè)置相同。

利用三種算法分別對ZDT1，ZDT2和ZDT3獨(dú)立進(jìn)行30次實(shí)驗(yàn)測試，得到的實(shí)驗(yàn)測試結(jié)果見表1。

根據(jù)表1實(shí)驗(yàn)數(shù)據(jù)對比三種算法的優(yōu)化性能。

表1 三個(gè)多目標(biāo)優(yōu)化問題實(shí)驗(yàn)結(jié)果

首先，分析三種算法求解ZDT1時(shí)：從ER和GD上看，MOIMBO在最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差指標(biāo)上均比MOMBO和MOPSO的好。從SP上看，MOIMBO在最優(yōu)值、平均值和標(biāo)準(zhǔn)差指標(biāo)上均比MOMBO和MOPSO的優(yōu)或相同；MOIMBO 在最差值指標(biāo)上略差于MOMBO，但比MOPSO的優(yōu)。

其次，分析三種算法求解ZDT2時(shí)：從ER和SP上看，MOIMBO在最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差指標(biāo)上均比MOMBO和MOPSO的好。從GD上看，MOIMBO在最差值、平均值和標(biāo)準(zhǔn)差指標(biāo)上均比MOMBO和MOPSO的優(yōu)或相同；MOIMBO 在最優(yōu)值指標(biāo)上略差于MOMBO，但比MOPSO的優(yōu)。

再次，分析三種算法求解ZDT3時(shí)：從ER和SP上看，MOIMBO在最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差指標(biāo)上均比MOMBO和MOPSO的好。從GD上看，MOIMBO在最優(yōu)值、最差值和平均值指標(biāo)上均比MOMBO和MOPSO的優(yōu)；在標(biāo)準(zhǔn)差指標(biāo)上，MOMBO 和MOPSO 略優(yōu)于MOIMBO。

實(shí)驗(yàn)中得到的3 種算法分別求解ZDT1、ZDT2和ZDT3時(shí)找到的最優(yōu)前沿與真實(shí)Pareto前沿?cái)M合程度圖如圖1-1至圖1-3、圖2-1至圖2-3、圖3-1至圖3-3所示。

圖3-3 MOPSO 求解ZDT3

從圖1-1至圖1-3、圖2-1至圖2-3、圖3-1至圖3-3上看，MOIMBO找到的最優(yōu)前沿與真實(shí)Pareto前沿的擬合程度均比另外兩種算法找到的最優(yōu)前沿與真實(shí)Pareto前沿的擬合程度要好，說明了MOIMBO求解多目標(biāo)優(yōu)化問題時(shí)的全局搜索能力均比另外兩種算法強(qiáng)。

圖2-3 MOPSO 求解ZDT2

圖3-1 MOPSO 求解ZDT3

圖2-1 MOPSO 求解ZDT2

圖1-3 MOPSO 求解ZDT1

圖1-1 MOPSO 求解ZDT1

4 結(jié)語

本文提出一種新的可用于求解多目標(biāo)優(yōu)化問題的MOIMBO算法，并利用多目標(biāo)優(yōu)化問題來檢驗(yàn)本文算法的優(yōu)化性能。數(shù)值實(shí)驗(yàn)仿真結(jié)果表明：MOIMBO在求解多目標(biāo)優(yōu)化問題時(shí)的全局搜索能力均比MOPSO和MOMBO的強(qiáng)，說明本文提出的MOIMBO在用于求解多目標(biāo)問題時(shí)是有效的和可行的。

圖1-2 MOPSO 求解ZDT1

圖2-2 MOPSO 求解ZDT2

圖3-2 MOPSO 求解ZDT3