改進多目標帝王蝶算法

馮禮杰 符強 陳嘉豪

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

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

關鍵詞： 群智能; 多目標; 帝王蝶優化算法; 非支配解排序; Logistic混沌映射

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：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 引言

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

1 帝王蝶優化算法

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

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

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

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

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

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

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

在此基礎上，若rand[>]BAR，則對[xt+1i，k]進一步更新為：

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

2 改進多目標帝王蝶算法

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

2.1 非支配解排序

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

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

⑴ 對于兩個向量x和y，當且僅當

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

⑵ 對于一個解[x∈X]，當且僅當

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

一個包含Pareto解集目標函數值的集合稱為Pareto前沿，表示為：

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

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

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

⑶ 對所有非支配個體進行擁擠度排序;

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

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

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

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

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

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

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

2.3 Logistic混沌映射

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

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

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

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

2.4 IMOMBO算法流程

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

Step 2 在多目標優化問題的解空間中隨機初始化帝王蝶種群;

Step 3 評估每個個體的適應度值;

Step 4 應用非支配解排序對當前帝王蝶種群排序，淘汰擁擠度較差的多余個體，并將非支配解存入外部儲存庫;

Step 5 判斷是否達到最大迭代次數，若未滿足，則當前迭代次數t=t+1;

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

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

Step 8 種群2使用調整算子更新;

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

Step 10 當前迭代次數[t>MaxGen ]*0.5時，對非支配解中擁擠度值最優個體進行Logistic混沌映射;

Step 11 合并所有種群，轉 Step 3;

3 仿真實驗結果與分析

3.1 仿真實驗初始參數設置

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

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

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

3.2 仿真實驗結果比較與分析

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

3.3 各算法在測試函數中的Pareto前沿

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

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

4 結束語

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

參考文獻（References）：

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

[2] 裴勝玉，周永權.基于Pareto最優解集的多目標粒子群優化算法[J].計算機工程與科學，2010.32（11）：85-88

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

[4] 陳小慶，侯中喜，郭良民等.基于NSGA-Ⅱ的改進多目標遺傳算法[J].計算機應用，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] 馮艷紅，楊娟，賀毅朝等.差分進化帝王蝶優化算法求解折扣{0-1背包問題[J].電子學報，2018.46（6）：1343-1350

[7] 李小林，王靜，張元孜，黃世國.準確度優先的多目標帝王蝶優化定量構效特征選擇方法[J].小型微型計算機系統，2021.5：1-5

[8] 魏武，郭燕.基于擁擠距離的動態粒子群多目標優化算法[J].計算機工程與設計，2011.32（4）：1422-1425

[9] 朱雅敏，薛鵬祥.一種基于Logistic混沌映射的骨干粒子群改進算法[J].西安文理學院學報：自然科學版， 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] 胡涵，李振宇.多目標進化算法性能評價指標綜述[J].軟件導刊，2019.203（9）：7-10