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

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

0 引言

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

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

1 MBO算法簡介

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

個體位置更新方法：設(shè)種群個數(shù)為NP，位于Land1的個體數(shù)為NP1(=ceil( p × NP))（記為Subpopulation1），位于Land2的個數(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中個體數(shù)）和NP2=NP-NP1（Land2中個體數(shù)）均取定值。)

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

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

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

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

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

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

2 改進的MBO算法

本文對MBO采用的改進策略如下：

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

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

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

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

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

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

1）種群分配方法。

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

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

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

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

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

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

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

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

Step1：

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

Step2：

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

Step3：

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

Step4：

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

Step5：

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

Step6：

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

Step7：

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

Step8：

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

3 數(shù)值實驗

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

3.1 實驗結(jié)果與分析

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

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

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

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

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

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

要么至少存在一個i ∈I使得

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

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

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

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

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

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

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

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

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

由于ER，GD和SP三個指標總體上刻畫了算法針對多目標優(yōu)化問題的優(yōu)化性能，而且普遍被智能優(yōu)化領(lǐng)域研究者所普遍采用。故本文以ER，GD和SP作為算法求解多目標優(yōu)化問題的優(yōu)化性能評價指標，用ER，GD和SP分別來評價算法所獲得的解中不屬于真正Pareto最優(yōu)解的百分比、解與真實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獨立進行30次實驗測試，得到的實驗測試結(jié)果見表1。

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

表1 三個多目標優(yōu)化問題實驗結(jié)果

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

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

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

實驗中得到的3 種算法分別求解ZDT1、ZDT2和ZDT3時找到的最優(yōu)前沿與真實Pareto前沿擬合程度圖如圖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)前沿與真實Pareto前沿的擬合程度均比另外兩種算法找到的最優(yōu)前沿與真實Pareto前沿的擬合程度要好，說明了MOIMBO求解多目標優(yōu)化問題時的全局搜索能力均比另外兩種算法強。

圖2-3 MOPSO 求解ZDT2

圖3-1 MOPSO 求解ZDT3

圖2-1 MOPSO 求解ZDT2

圖1-3 MOPSO 求解ZDT1

圖1-1 MOPSO 求解ZDT1

4 結(jié)語

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

圖1-2 MOPSO 求解ZDT1

圖2-2 MOPSO 求解ZDT2

圖3-2 MOPSO 求解ZDT3