馮禮杰 符強 陳嘉豪

DOI：10.16644/j.cnki.cn33-1094/tp.2021.11.012

摘要： 帝王蝶優(yōu)化算法結(jié)構(gòu)簡單，能夠較好的完成尋優(yōu)搜索要求，但在多目標(biāo)問題上，算法的精度和非支配解的分布性較差。針對以上不足之處，本文提出一種改進(jìn)型多目標(biāo)帝王蝶算法（Improved multi-objective monarch butterfly algorithm，IMOMBO），對非支配解進(jìn)行擁擠度排序，所有非支配解個體都以當(dāng)前最優(yōu)個體為中心點映射鏡像點，并朝向鏡像點奔襲，以此增加個體在Pareto前沿上的收斂性和算法精度。在算法迭代后期，對部分較優(yōu)個體進(jìn)行Logistic混沌映射，以改善個體在 Pareto 前沿上的分布性。隨機選用ZDT和DTLZ測試函數(shù)集中的函數(shù)進(jìn)行算法性能驗證，實驗結(jié)果證明，本算法可以很好地保證非支配解個體的收斂特性和分布特性。

關(guān)鍵詞： 群智能; 多目標(biāo); 帝王蝶優(yōu)化算法; 非支配解排序; Logistic混沌映射

中圖分類號：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2021）11-44-05

Improved multi-objective monarch butterfly algorithm

Feng Lijie， Fu Qiang， Chen Jiahao

（School of Information Engineering， School of Science and Technology， Ningbo University， Cixi， Zhejiang 315300， China）

Abstract： The monarch butterfly optimization algorithm is simple in structure and can better fulfill the optimization search requirements， but for multi-objective problems， the accuracy of the algorithm and the distribution of non-dominated solutions are poor. To solve the above short comings， an improved multi-objective monarch butterfly algorithm （IMOBO） is proposed in this paper to sort the crowding degree of the non-dominant solutions. All the individuals of the non-dominated solution map the mirror point with the current optimal individual as the center point and run toward the mirror point， so as to increase the convergence of the individuals on the Pareto front and the algorithm's accuracy. Logistic chaotic mapping is carried out for some of the better individuals at the later stage of the algorithm iteration， to improve the distribution of individuals on the Pareto front. The functions in the ZDT and DTLZ test function sets are randomly selected to verify the performance of the algorithm. The experimental results show that the algorithm can well guarantee the convergence characteristics and distribution characteristics of the non-dominated solution individuals.

Key words： swarm intelligence; multi-objective; monarch butterfly optimization algorithm; non-dominated solution sorting; Logistic chaotic map

0 引言

由多個目標(biāo)組成且目標(biāo)之間相互沖突和影響的問題被稱為多目標(biāo)問題[1]。而且在多目標(biāo)問題的求解上，很難像解決單目標(biāo)問題一樣去尋找函數(shù)的最優(yōu)解，因此尋找能夠均衡所有目標(biāo)的解成為求解多目標(biāo)問題的目的。求解多目標(biāo)問題時，經(jīng)過一系列運算取舍最終會得到一組非劣解，而這組非劣解被稱為Pareto最優(yōu)解集[2]。最開始在尋求Pareto最優(yōu)解集是通過賦予權(quán)重，將一個多目標(biāo)的問題直接轉(zhuǎn)化成一個單目標(biāo)的問題來對其進(jìn)行求解，但這種方法存在權(quán)重分配的主觀性，并且結(jié)果的優(yōu)劣也無法客觀的判斷。但在實際生產(chǎn)生活中，經(jīng)常需要針對一個多目標(biāo)問題去拿出多種有效的方案，以供決策者進(jìn)行權(quán)衡選擇得出最好的解決方案。因此，高效、合理的多目標(biāo)優(yōu)化算法在解決多目標(biāo)的問題上是必不可少的。在已知的多目標(biāo)優(yōu)化算法中最為典型的就是多目標(biāo)粒子群算法[3]（MOPSO），該算法通過合并Pareto-占優(yōu)的概念來選出非劣解，并采用外部儲存庫來存儲，以此不斷迭代最終得出Pareto最優(yōu)解集。而多目標(biāo)遺傳算法[4]（NSGA-II）也是目前具有代表性的多目標(biāo)優(yōu)化算法，NSGA-II采用非優(yōu)超排序機制提升算法逼近Pareto最優(yōu)前沿的能力，同時采用了排擠機制保證了非劣解集的分布性。此外，帝王蝶優(yōu)化算法[5][6]也憑借其優(yōu)秀的收斂性和尋優(yōu)能力脫穎而出，但在多目標(biāo)問題的解決上，算法穩(wěn)定性和非支配解的分布性較差，由此，本文提出了一種改進(jìn)多目標(biāo)帝王蝶算法以解決算法本身在求解多目標(biāo)問題上的不足。

1 帝王蝶優(yōu)化算法

帝王蝶是地球上唯一具有遷徙性蝴蝶，他們每年都會進(jìn)行遷徙，并在遷徙過程中進(jìn)行繁殖。而帝王蝶優(yōu)化算法是通過模仿自然界中帝王蝶族群隨著季節(jié)氣候變化而進(jìn)行的遷移行為，研究出來的群體智能優(yōu)化算法。該算法將整個帝王蝶種群劃分為兩個種群，稱為種群1和種群2，種群1的個體進(jìn)行遷徙實現(xiàn)更新，種群2則在種群內(nèi)部進(jìn)行隨機游走，以獲得更優(yōu)個體，這兩種行為在算法中描述為遷移算子和調(diào)整算子。算法的具體細(xì)節(jié)由下文展開。

假設(shè)問題對應(yīng)于一個d維解空間，初始化產(chǎn)生一個個體數(shù)量為N的帝王蝶種群[P=（X1，X2，...，XN）]，第i個帝王蝶個體的位置可以表示為[Xi=（Xi，1，Xi，2，...，Xi，d）T]，由此可知，每個帝王蝶個體都有其對應(yīng)目標(biāo)問題的一個潛在解，其中遷移算子和調(diào)整算子描述如下：

設(shè)[NP1]和[NP2]分別為兩個種群的個體數(shù)量，即[NP1=ceil（par*N），NP2=NP-NP1]。其中par為種群1個體的占比，函數(shù)ceil表示向上取整，遷移算子的數(shù)學(xué)模型描述如下：

其中，[i=1，2，...，NP1]，t表示當(dāng)前迭代次數(shù)，[xr1]和[xr2]分別代表帝王蝶個體r1和r2的位置，這兩個個體分別隨機取自兩個種群，標(biāo)量[r=rand*peri]，其中的rand是一個隨機數(shù)且[rand∈0，1];peri則代表的是帝王蝶個體的遷移周期。

在調(diào)整算子中，若[rand≤par]，則種群2中個體按式⑵更新;否則，個體將按式⑶更新。

其中，i=1，2，...，[NP2].[xbest]表示全局最優(yōu)個體的位置。

其中，[xr3]表示從種群2中隨機選擇的一個帝王蝶的位置。

在此基礎(chǔ)上，若rand[>]BAR，則對[xt+1i，k]進(jìn)一步更新為：

其中，[α]是權(quán)重因子，由[α=1/t2]計算所得。[dx]表示帝王蝶個體[xi]的萊維飛行步長，由Levy函數(shù)計算。而BAR表示調(diào)整率。

2 改進(jìn)多目標(biāo)帝王蝶算法

多目標(biāo)帝王蝶算法個體的更新是通過個體之間的維度替換，在迭代后期維度的多樣性會降低并導(dǎo)致算法的分布性變差，而且很容易陷入局部最優(yōu)。根據(jù)算法本身的不足在此提出以下三種優(yōu)化策略去提升算法非支配解的分布性、收斂性以及算法的穩(wěn)定性。

2.1 非支配解排序

為了保證能夠更好的劃分種群1和種群2，引入了非支配解排序算法[7].

首先，非支配排序涉及到的概念有如下兩點。

⑴ 對于兩個向量x和y，當(dāng)且僅當(dāng)

稱之為x支配y，用[x?y]表示，否則，這稱這兩個向量互不支配。

⑵ 對于一個解[x∈X]，當(dāng)且僅當(dāng)

則稱該解x為Pareto最優(yōu)，而Pareto解集即Pareto最優(yōu)解的集合，定義如下：

一個包含Pareto解集目標(biāo)函數(shù)值的集合稱為Pareto前沿，表示為：

因此在多目標(biāo)帝王蝶算法中，非支配排序算法對所有個體都需要進(jìn)行以下四步操作：

⑴ 判斷是否被種群中其余個體支配;

⑵ 計算該個體在種群中的擁擠度[8]大小;

⑶ 對所有非支配個體進(jìn)行擁擠度排序;

⑷ 將排序后的結(jié)果存入外部儲存庫中。

2.2 基于鏡像映射的奔襲策略

由于帝王蝶優(yōu)化算法在整個生命周期中的精英策略存在缺陷，如后期種群遷徙和游走的步長隨機性過大導(dǎo)致種群出現(xiàn)退化，從而導(dǎo)致算法穩(wěn)定性較差。本文提出了一種基于鏡像映射的奔襲策略，以此降低帝王蝶個體在算法迭代過程中的退化率。該策略的思想是讓非支配解個體朝著當(dāng)前最優(yōu)個體進(jìn)行奔襲，如果新個體擁有更好的精度，則淘汰其余精度較差的個體，以此避免種群的大規(guī)模退化。

選取任意一個非支配解個體[xi]和當(dāng)前最優(yōu)個體[xbest]，[xi]以[xbest]為中心點，將其每個維度進(jìn)行鏡像映射得到鏡像點[x‘i]，鏡像點[x‘i]是個體[xi]奔襲過程中的最遠(yuǎn)位置，設(shè)置鏡像點的目的是防止奔襲步長過大，其中計算公式如式⑽所示：

其中，ub，lb為目標(biāo)函數(shù)解空間的上限和下限。個體[xi]在第j維時到最優(yōu)個體[xbest]距離與最優(yōu)個體[xbest]到解空間邊界的比值等于鏡像點個體[x'i]到最優(yōu)個體[xbest]距離與最優(yōu)個體[xbest]到解空間邊界的比值。

個體[xi]在[xi]、[xbest]、[x'i]三點之間來回奔襲尋找非劣解，奔襲結(jié)束后得到子代個體[xnew]，其中奔襲的步長都由隨機數(shù)公式?jīng)Q定，如式⑾所示：

其中，m是[x'i，j]與[xi，j]的乘積，而n是[x'i，j]與[xi，j]差的絕對值，max和min是[x'i，j]、[xi，j]中的最大值與最小值，[β]是一個正態(tài)分布的衰減系數(shù)，randn是一個符合正態(tài)分布的隨機數(shù)，隨著randn值增大，[xnew]游走之后的最終結(jié)果會無限趨近最優(yōu)個體[xbest]。

2.3 Logistic混沌映射

為了提高算法在迭代后期個體在Pareto前沿上的分布性，采取對擁擠度最優(yōu)個體進(jìn)行Logistic混沌映射[9]，使最優(yōu)個體在Pareto前沿上游走。其表達(dá)式為：

其中，[zi∈0，1]是第i個混沌變量，[zit]是[zi]經(jīng)過t次迭代后的值。[μ]是混沌映射中的控制參數(shù)，且[μ∈0，4]。當(dāng) μ 的取值趨近于4時，系統(tǒng)在其映射下處于混沌狀態(tài)。當(dāng)[zi∈0，1]且[zi?]{0.25，0.50，0.75} 時將產(chǎn)生混沌現(xiàn)象，其中0.25，0.5，0.75這三個點是映射空間[0，1]中的斷點，在映射時需要跳過。

當(dāng)[xi∈ai，bi]要映射到[zi∈0，1]可用公式⒀中表達(dá)式：

然后利用公式⒁將[zi]映射回[xi]：

2.4 IMOMBO算法流程

Step 1 初始化必要參數(shù)，令初始代數(shù)[t =0]，設(shè)置最大迭代次數(shù)[MaxGen]，種群總個數(shù)為N，令種群1個數(shù)為[NP1]，種群2個數(shù)為[NP2]。

Step 2 在多目標(biāo)優(yōu)化問題的解空間中隨機初始化帝王蝶種群;

Step 3 評估每個個體的適應(yīng)度值;

Step 4 應(yīng)用非支配解排序?qū)Ξ?dāng)前帝王蝶種群排序，淘汰擁擠度較差的多余個體，并將非支配解存入外部儲存庫;

Step 5 判斷是否達(dá)到最大迭代次數(shù)，若未滿足，則當(dāng)前迭代次數(shù)t=t+1;

Step 6 將種群中擁擠度值較優(yōu)的NP1個個體組成種群1，余下的NP2個個體形成種群2;

Step 7 種群1使用遷徙算子更新﹔

Step 8 種群2使用調(diào)整算子更新;

Step 9 使用基于鏡像映射的奔襲策略更新非支配解個體;

Step 10 當(dāng)前迭代次數(shù)[t>MaxGen ]*0.5時，對非支配解中擁擠度值最優(yōu)個體進(jìn)行Logistic混沌映射;

Step 11 合并所有種群，轉(zhuǎn) Step 3;

3 仿真實驗結(jié)果與分析

3.1 仿真實驗初始參數(shù)設(shè)置

本文選取多目標(biāo)粒子群算法[3]（MOPSO），帶精英策略的非支配排序的遺傳算法[4]（NSGA-II），以及本文的改進(jìn)多目標(biāo)帝王蝶算法（IMOMBO）進(jìn)行對比實驗，將所有算法的種群個數(shù)定為100，迭代次數(shù)為100代。測試函數(shù)的目標(biāo)數(shù)設(shè)為2，每個個體的維度設(shè)置為10維。

本文算法參數(shù)設(shè)置：帝王蝶調(diào)整率為5/12，遷移周期為1.2，以及種群1個體的占比率為5/12;其余對比算法的參數(shù)設(shè)置均來源于引用文獻(xiàn)。

在本次實驗中，隨機選用ZDT測試函數(shù)集[10]和DTLZ測試函數(shù)集[11]中8個測試函數(shù)進(jìn)行驗證。為了避免出現(xiàn)實驗偶然性帶來的偏差，測試的算法在每個測試函數(shù)上都進(jìn)行10次獨立實驗。實驗采用算法的GD[12]、IGD[12]、Spacing[12]三個值做比較，其中GD[12]用于檢驗算法的收斂能力，GD值越小，表明算法的收斂性能越好。IGD[12]是綜合評價指標(biāo)，同時反映了種群的收斂性和分布性，IGD值越小，說明算法的綜合性能越好。Spacing[12]是檢測算法在優(yōu)化過程中均勻性的能力，Spacing值越小，算法的非支配解分布的越均勻。

3.2 仿真實驗結(jié)果比較與分析

實驗結(jié)果如下列各表所示，表1中IMOMBO的GD值遠(yuǎn)小于對比算法的GD值，說明本算法在運算過程中擁有更強的收斂性，能夠得到比其余算法更為精確的解方案。表2的數(shù)據(jù)顯示，本算法的IGD值優(yōu)于對比算法，說明其綜合性能相較于對比算法更優(yōu)秀。表3中IMOMBO的Spacing值也是最小的，說明算法在非支配解的分布性上同樣具有優(yōu)勢。在以下列出的8個測試函數(shù)中，IMOMBO算法的各項數(shù)值對比其余算法表現(xiàn)更為穩(wěn)定，說明了本文提出的改進(jìn)策略，能夠很好的保證算法的穩(wěn)定性。

3.3 各算法在測試函數(shù)中的Pareto前沿

為了進(jìn)一步展示IMOMBO算法非支配解的分布性與收斂性，本文列出IMOMBO算法、MOPSO算法和NSGA-II算法在8個測試函數(shù)中的Pareto前沿，如圖1所示。

從圖像可以看出，本文的改進(jìn)算法對于非支配解的分布性與收斂性都有不錯的表現(xiàn)。本算法在8個測試函數(shù)中能保證每一個非支配解都位于測試函數(shù)Pareto前沿之上，且分布均勻。對比于MOPSO算法和NSGA-II算法，收斂性和分布性也更強。在測試函數(shù)DTLZ3、DTLZ7中，由于MOPSO的Pareto前沿較差，故沒有參與對比。

4 結(jié)束語

本文提出了一種改進(jìn)的多目標(biāo)帝王蝶算法，改進(jìn)方法包括了非支配解排序、基于鏡像映射的奔襲策略和Logistic混沌映射，并且與多目標(biāo)粒子群算法、帶精英策略的非支配排序的遺傳算法，進(jìn)行了算法性能的對比實驗，實驗結(jié)果表明本算法的各項改進(jìn)策略可以很好地保證個體的收斂特性和分布特征，同時，各項數(shù)值也表現(xiàn)出算法具有優(yōu)秀的穩(wěn)定性。這表明了本算法對于多目標(biāo)問題的求解又邁出了一步，接下來還可以對一些生產(chǎn)生活中的實際問題做進(jìn)一步的研究及優(yōu)化。

參考文獻(xiàn)（References）：

[1] 肖曉偉，肖迪，林錦國等.多目標(biāo)優(yōu)化問題的研究概述[J].計算機應(yīng)用研究，2011.28（3）：805-808，827

[2] 裴勝玉，周永權(quán).基于Pareto最優(yōu)解集的多目標(biāo)粒子群優(yōu)化算法[J].計算機工程與科學(xué)，2010.32（11）：85-88

[3] Yanmin L，? Ben N，? Qingzhen Z， et al. Particle swarm optimizer simulation research of multi-objective optimization problems多目標(biāo)優(yōu)化問題的粒子群算法仿真研究[J].計算機應(yīng)用研究，2011.28（2）：458-460

[4] 陳小慶，侯中喜，郭良民等.基于NSGA-Ⅱ的改進(jìn)多目標(biāo)遺傳算法[J].計算機應(yīng)用，2006.26（10）：2453-2456

[5] Gai-Ge Wang，Suash Deb，Xinchao Zhao，Zhihua Cui. A

new monarch butterfly optimization with an improved crossover operator[J].Operational Research，2018.18（3）.

[6] 馮艷紅，楊娟，賀毅朝等.差分進(jìn)化帝王蝶優(yōu)化算法求解折扣{0-1背包問題[J].電子學(xué)報，2018.46（6）：1343-1350

[7] 李小林，王靜，張元孜，黃世國.準(zhǔn)確度優(yōu)先的多目標(biāo)帝王蝶優(yōu)化定量構(gòu)效特征選擇方法[J].小型微型計算機系統(tǒng)，2021.5：1-5

[8] 魏武，郭燕.基于擁擠距離的動態(tài)粒子群多目標(biāo)優(yōu)化算法[J].計算機工程與設(shè)計，2011.32（4）：1422-1425

[9] 朱雅敏，薛鵬祥.一種基于Logistic混沌映射的骨干粒子群改進(jìn)算法[J].西安文理學(xué)院學(xué)報：自然科學(xué)版， 2016.19：1-4

[10] Zitzler E，Deb K，Thiele L.Comparison of Multiobjective Evolutionary Algorithms：Empirical Results[J].Evolutionary Computation，2000.8（2）：173-195

[11] Deb K. Scalable test problems for evolutionary multiobejctive optimization[J]. Evolutionary Multiobjective Optimization： Theoretical Advances and Applications，2005.

[12] 胡涵，李振宇.多目標(biāo)進(jìn)化算法性能評價指標(biāo)綜述[J].軟件導(dǎo)刊，2019.203（9）：7-10