隨機(jī)擾動(dòng)不同種群變異策略的多目標(biāo)進(jìn)化算法

摘要：為了提高多目標(biāo)優(yōu)化問(wèn)題非支配解集的收斂性和多樣性，解決算法后期易陷入局部最優(yōu)的問(wèn)題，根據(jù)不同差分進(jìn)化策略特點(diǎn)，添加隨機(jī)擾動(dòng)，基于改進(jìn)切比雪夫機(jī)制提出了一種自適應(yīng)差分進(jìn)化策略的分解多目標(biāo)進(jìn)化算法（MOEA/D-ADE-levy）。首先，使用混合水平正交實(shí)驗(yàn)產(chǎn)生均勻權(quán)重向量并應(yīng)用于改進(jìn)切比雪夫機(jī)制分解子問(wèn)題得到均勻分布的初始種群；其次，將種群分為優(yōu)秀個(gè)體、中間個(gè)體和較差個(gè)體，對(duì)不同個(gè)體采用不同的變異策略，對(duì)變異因子F和交叉概率CR采用自適應(yīng)機(jī)制，提高非支配解集的收斂性和多樣性；最后，對(duì)陷入局部最優(yōu)的解集增加Lévy隨機(jī)擾動(dòng)，增大其全局搜索的能力，跳出局部最優(yōu)。采用DTLZ測(cè)試函數(shù)驗(yàn)證算法有效性，將所提算法與NSGA2、NSGA3、MOEA/D、MOEA/D-DE等常用算法進(jìn)行比較，使用GD和IGD評(píng)價(jià)指標(biāo)對(duì)算法進(jìn)行多樣性和收斂性分析，實(shí)驗(yàn)結(jié)果表明，該算法在收斂性和多樣性方面得到了改進(jìn)與提高，能得到更優(yōu)的Pareto解集。

關(guān)鍵詞：混合水平正交；切比雪夫；自適應(yīng)差分；局部最優(yōu)；收斂性；多樣性

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）04-023-1092-07

doi：10.19734/j.issn.1001-3695.2021.08.0371

Multi-objective evolutionary algorithm with random disturbance of different population mutation strategies

Hao Qinxiaa，b，Wang Lianliana

（a.School of Communication amp; Information Engineering，b.School of Safety Science amp; Engineering，Xi’an University of Science amp; Technology，Xi’an 710054，China）

Abstract：In order to improve the convergence and diversity of the non-dominated solution set of multi-objective optimization problems，and solve the problem that the algorithm is easy to fall into the local optimum in the later stage，according to the characteristics of different differential evolution strategies，this paper added random disturbances，and proposed a decomposition multi-objective evolution algorithm with adaptive differential evolution strategy based on the improved Chebyshev mechanism（MOEA/D-ADE-levy）.Firstly，it used the mixed-level orthogonal experiment to generate uniform weight vectors and applied to improve the Chebyshev mechanism to decompose the sub-problems to obtain a uniformly distributed initial population.Secondly，it divided the population into excellent individuals，intermediate individuals and poor individuals，and used different indivi-duals.The mutation strategy used an adaptive mechanism for the mutation factor F and the crossover probability CR to improve the convergence and diversity of the non-dominated solution set.Finally，it added the Lévy random perturbation to the solution set that fell into the local optimum to increase its global search ability，and jumped out of the local optimum.The DTLZ test function was used to verify the effectiveness of the algorithm.And the proposed algorithm was compared with common algorithms such as NSGA2，NSGA3，MOEA/D，MOEA/D-DE，etc..And the diversity and convergence analysis of the algorithm was performed using GD and IGD evaluation indicators.The results show that the algorithm has been improved and improved in terms of convergence and diversity，and can obtain a better Pareto solution set.

Key words：hybrid level orthogonality；Chebyshev；adaptive difference；local optimum；convergence；diversity

0引言

在現(xiàn)實(shí)生活和生產(chǎn)中，通常需要對(duì)多個(gè)問(wèn)題同時(shí)進(jìn)行優(yōu)化，將每個(gè)需要優(yōu)化的問(wèn)題稱為一個(gè)目標(biāo)，當(dāng)目標(biāo)維數(shù)超過(guò)三維時(shí)，稱為高維多目標(biāo)問(wèn)題。高維多目標(biāo)問(wèn)題通常難以解決，到目前為止，尚未找到能夠有效解決高維多目標(biāo)問(wèn)題的方法，專家學(xué)者們使用最多的就是對(duì)多目標(biāo)問(wèn)題進(jìn)行優(yōu)化。目前，多目標(biāo)進(jìn)化算法是使用最為廣泛的一種解決多目標(biāo)問(wèn)題的方法。常用的多目標(biāo)進(jìn)化算法有：a） 基于支配關(guān)系的優(yōu)化算法［1，2］，主要是利用目標(biāo)函數(shù)的優(yōu)劣來(lái)區(qū)分優(yōu)劣解，通過(guò)設(shè)計(jì)新的支配關(guān)系來(lái)促進(jìn)種群的收斂，但是基于支配的優(yōu)化算法需要預(yù)先設(shè)置合適的參數(shù)；b）通過(guò)降維的思想［3］，把高維多目標(biāo)問(wèn)題降為低維多目標(biāo)問(wèn)題，通過(guò)分析目標(biāo)之間的冗余關(guān)系，消除冗余目標(biāo)，但是這種方法并不適用于所有的多目標(biāo)問(wèn)題（MOP）；c）基于指標(biāo)的方法［4～6］，該方法將MOP問(wèn)題轉(zhuǎn)換為優(yōu)化指標(biāo)函數(shù)的單目標(biāo)問(wèn)題，但是對(duì)于指標(biāo)的求解仍需要指標(biāo)去判定收斂性和多樣性，使算法的復(fù)雜度增加；d）基于偏好的方法［7，8］，根據(jù)決策者對(duì)問(wèn)題賦予的重要度排序進(jìn)行處理，使得搜索過(guò)程按照指定偏好進(jìn)行，但是這種方法需要預(yù)先指定偏好，增加了算法的難度；e）基于分解的思想［9～11］，將MOP問(wèn)題轉(zhuǎn)換為多個(gè)單目標(biāo)問(wèn)題的求解，避免使用Pareto支配的缺陷，降低高維多目標(biāo)問(wèn)題的求解難度。

基于分解的多目標(biāo)進(jìn)化算法（MOEA/D）已被廣泛用于處理MOP，文獻(xiàn)[10]于2019年使用三種索引選擇方法，兩種變異策略和五種邊界處理方法，選擇出合適的MOEA/D-DE算子的配置用于處理MOP［10］；文獻(xiàn)[11]提出一種多目標(biāo)遺傳算法DEA-MOEA/D，將分解法和數(shù)據(jù)包絡(luò)法結(jié)合，采用差分算子作為進(jìn)化算子，并與其他基礎(chǔ)算法比較驗(yàn)證了該算法在處理MOP問(wèn)題上的優(yōu)越性；文獻(xiàn)［12］提出將MOEA＼D算法與最流行的直接搜索方法Nelder和Mead方法相結(jié)合，將MOEA＼D的全局搜索特性與數(shù)學(xué)規(guī)劃技術(shù)的開發(fā)能力結(jié)合起來(lái)。由于MOEA＼D算法提出了許多修改版本， 一些方法旨在通過(guò)利用MOEA/D框架中使用的各種標(biāo)度函數(shù)的優(yōu)點(diǎn)來(lái)獲得更好的性能，沒(méi)有考慮到算法的搜索性能，本文針對(duì)MOEA＼D框架利用正交匹配算法產(chǎn)生均勻權(quán)重，使用改進(jìn)的切比雪夫公式對(duì)MOP問(wèn)題進(jìn)行分解，將種群分為優(yōu)秀個(gè)體、中間個(gè)體和較差個(gè)體，對(duì)不同個(gè)體采用不同的變異策略，對(duì)變異因子F和交叉概率CR采用自適應(yīng)機(jī)制。

1算法描述

MOEA/D算法已被證明在收斂性與多樣性上具有先進(jìn)性，但卻具有易陷入局部最優(yōu)的問(wèn)題［10～12］，為保證算法在收斂性與多樣性平衡的基礎(chǔ)上，提出MOEA/D-ADE-levy算法。針對(duì)高維多目標(biāo)問(wèn)題種群規(guī)模大，MOEA/D算法產(chǎn)生的權(quán)重不均勻問(wèn)題，利用混合正交水平實(shí)驗(yàn)產(chǎn)生的值具有均勻分散、齊整可比的特點(diǎn)得到均勻分布的權(quán)重向量［13，14］；將產(chǎn)生的權(quán)重向量引入改進(jìn)的切比雪夫分解方法將MOP問(wèn)題分解為一系列子問(wèn)題；接著針對(duì)子代產(chǎn)生方式收斂性和多樣性不平衡的問(wèn)題，將子代分為優(yōu)秀個(gè)體、中間個(gè)體和較差個(gè)體，對(duì)于不同個(gè)體分別采用不同的交叉變異方法生成子代，對(duì)于優(yōu)秀個(gè)體加強(qiáng)其局部搜索的能力，對(duì)中間個(gè)體采取種群自適應(yīng)進(jìn)化策略，根據(jù)種群進(jìn)化次數(shù)，結(jié)合鄰居節(jié)點(diǎn)信息自適應(yīng)調(diào)整進(jìn)化策略，對(duì)較差個(gè)體提高個(gè)體的全局搜索能力和探索能力，加快向最優(yōu)解收斂，保證算法收斂性與多樣性的平衡；然后結(jié)合Lévy飛行大跳躍、長(zhǎng)拖尾特性［15］，對(duì)陷入局部最優(yōu)的個(gè)體使用Lévy擾動(dòng)增大其全局搜索能力，跳出局部最優(yōu)；最后利用改進(jìn)切比雪夫函數(shù)作為排序標(biāo)準(zhǔn)來(lái)進(jìn)行個(gè)體選擇，得到收斂性和多樣性［11，12］較好的Pareto最優(yōu)解。MOEA/D-ADE-levy算法的整體流程如圖1所示。

1.1產(chǎn)生權(quán)重

在現(xiàn)實(shí)生活中，決策者的偏好信息通常是未知的，MOEA/D算法首先產(chǎn)生一組均勻分布的權(quán)重向量，得到能夠均勻分布于Pareto前沿的解。對(duì)于種群規(guī)模為N，目標(biāo)維數(shù)為m的MOP，λ1，λ2，…，λN為MOEA/D產(chǎn)生的N個(gè)均勻分布的權(quán)重向量，對(duì)于權(quán)重向量λi=（λi1，λi2，…，λim）中的任意分量從（0，1/H，2/H，…，H/H）中不重復(fù)取值，N由式（1）得到。

N=Cm-1H+m-1（1）

從式中可以看出，隨著目標(biāo)維數(shù)的增加，N的數(shù)目將持續(xù)增大，表1給出了在不同（H，m）的情況下N的變化情況。

從表1中可以看出，隨著（H，m）的增大，N呈指數(shù)級(jí)增長(zhǎng)，MOEA/D算法產(chǎn)生均勻權(quán)重的方法并不適用于高維多目標(biāo)問(wèn)題，正交水平實(shí)驗(yàn)是從全面實(shí)驗(yàn)中挑選部分具有代表性的點(diǎn)進(jìn)行實(shí)驗(yàn)，而且這些點(diǎn)具有均勻分散和齊整可比的特點(diǎn)，因此采用正交實(shí)驗(yàn)法產(chǎn)生初始種群可以獲得均勻分布的初始點(diǎn)［13］，本文采用混合水平正交法［14］產(chǎn)生均勻權(quán)重λ，其算法流程如算法1所示。

算法1混合水平正交

輸入：種群規(guī)模N；目標(biāo)數(shù)目m；正交指數(shù)J1，J2；混合水平正交表的劃分水平Q1，Q2；水平正交表的劃分水平Q。

輸出：N個(gè)均勻分布的權(quán)重向量。

1for （k=1，k≤J，k++）

2j=（Qk-1）/（Q-1）+1j=（Qk-1）/（Q-1）+1

3for （i=1，i≤Qj，i++）

4ai，j=i-1QJ-k mod Qai，j=i-1QJ-k mod Q

5end

6end

7for （k=2，k≤J，k++）

8j=（Qk-1）/（Q-1）+1j=（Qk-1）/（Q-1）+1

9for （s=1，s≤j-1，s++）

10for （t=1，t≤Q-1，t++）

11 aj+（s-1）（Q-1）+t=（as×t+aj） mod Q

12 end

13end

14end

15ai，j=ai，j+1，i∈［1：M］∧j∈［1：N］ai，j=ai，j+1，i∈［1：M］∧j∈［1：N］

16構(gòu)造等水平正交表LM1（Q1N1）=（ai，j）M1×N1和LM2（Q2N2）=（bi，j）M2×N2

17 for （k=0，klt;M1，k++）

18for （i=0，klt;M2，i++）

19 c（k-1）M2+i=［ak，bi］

20 輸出混合水平正交矩陣c（i，j）M*（N1+N2）

21 對(duì)混合水平正交表均勻采樣，得到N個(gè)均勻分布的權(quán)重向量

在算法1 中，首先構(gòu)造等水平正交表LM1（Q1N1）=（ai，j）M1×N1、LM2（Q2N2）=（bi，j）M2×N2，其中M=M1×M2，M1=Q1J1，M2=Q2J2，Q1J1-1Q1≥N1

Q2J2-1Q2≥N2，然后通過(guò)迭代得到混合水平正交矩陣（ci，j）M×（N1+N2），最終得到N個(gè)均勻分布的權(quán)重向量λ。本文J1、J2取值分別為1、2。

1.2目標(biāo)分解

MOEA＼D算法將MOP問(wèn)題分解為一系列子問(wèn)題，每一個(gè)子問(wèn)題的最優(yōu)解對(duì)應(yīng)原MOP問(wèn)題的一個(gè)Pareto最優(yōu)解，常用的分解方法有：a）加權(quán)和方法，該方法求解簡(jiǎn)單，但是對(duì)于多目標(biāo)問(wèn)題為非凸的情況下難以找到最優(yōu)解；b）邊界相交法，雖然能夠找到均勻的Pareto解集合，但它需要處理等式約束，需要預(yù)先設(shè)定懲罰系數(shù)θ值；c）切比雪夫法，該方法雖然能夠解決非凸問(wèn)題，但是在均勻分布的權(quán)重向量下，Tchebycheff分解方案下子問(wèn)題的最優(yōu)解不是很均勻［16］。本文使用改進(jìn)的Tchebycheff分解方法［17］，公式如下：

min gte（x|λ，z*）=max1lt;jlt;n{|fj（x）-z*j|λj}=max1lt;jlt;n{fj（x）-z*jλj}

subject tox∈Ω（2）

對(duì)于直線[f1（x）-z*1]/λ1=[f2（x）-z*2]/λ2=…=[fm（x）-z*m]/λm，在理想條件下，與PF有一個(gè)交點(diǎn)，這個(gè)交點(diǎn)為Pareto最優(yōu)解。改進(jìn)的Tchebycheff分解方法不僅能夠解決非凸問(wèn)題，而且可以得到均勻分布的解。

1.3子代生成

子代的生成策略對(duì)算法的搜索有重要影響，進(jìn)化算法在求解高維多峰復(fù)雜函數(shù)最優(yōu)化問(wèn)題時(shí)存在易陷入局部最優(yōu)、早熟收斂、后期收斂速度慢等問(wèn)題［18］，導(dǎo)致在大規(guī)模、高度非線性、實(shí)時(shí)性要求較高的實(shí)際工程應(yīng)用中求解困難。因此，提出一種MOEA/D-ADE-levy算法，首先將種群中所有個(gè)體分為優(yōu)秀個(gè)體、中間個(gè)體和較差個(gè)體，其優(yōu)秀個(gè)體和較差個(gè)體分別來(lái)自當(dāng)前大小為NP的群體中的頂部和底部100p%的個(gè)體，本文經(jīng)實(shí)驗(yàn)驗(yàn)證，當(dāng)三種個(gè)體的比例為1/4、1/2、1/4時(shí)，算法性能表現(xiàn)最優(yōu)，對(duì)三種個(gè)體分別執(zhí)行不同的選擇算子，對(duì)優(yōu)秀個(gè)體應(yīng)盡量保留個(gè)體內(nèi)的優(yōu)良基因，加強(qiáng)其局部搜索的能力，對(duì)中間個(gè)體采取種群自適應(yīng)進(jìn)化策略，根據(jù)種群進(jìn)化次數(shù)，結(jié)合鄰居節(jié)點(diǎn)信息自適應(yīng)調(diào)整進(jìn)化策略，對(duì)較差個(gè)體應(yīng)提高個(gè)體的全局搜索能力和探索能力，加快向最優(yōu)解收斂，其次提出使用時(shí)代距離（GD）判斷種群是否陷入局部最優(yōu)，對(duì)陷入局部最優(yōu)的解加入Lévy隨機(jī)擾動(dòng)，增加算法的全局搜索能力，避免種群陷入局部最優(yōu)；最終通過(guò)改進(jìn)切比雪夫進(jìn)行適應(yīng)度排序選出最優(yōu)Pareto解集，其詳細(xì)流程如算法2所示。

算法2MOEA/D-ADE-levy

輸入：多目標(biāo)優(yōu)化問(wèn)題；算法終止條件；種群大小N；初始權(quán)重向量：λ每一個(gè)鄰域中權(quán)重向量的個(gè)數(shù)T。

輸出：最優(yōu)解。

1 計(jì)算任意兩個(gè)權(quán)重之間的歐氏距離，并查找與每個(gè)權(quán)重向量相近的T個(gè)權(quán)重向量，B（i）={i1，…，iT}，i=1，2，…，n，λi1，…，λiT為λi的T個(gè)相近權(quán)重向量

2 在可行空間中隨機(jī)產(chǎn)生初始種群{x1，x2，…，xn}

3 初始化z={z1，z2，…，zm}，zi=min{fi（x1），fi（x2），…，fi（xN）}

4 設(shè)置EP為空

5 for i=1，…，N，do

6 將種群分為優(yōu)秀個(gè)體xbest，中間個(gè)體xmiddle和較差個(gè)體xworst

7 ifx∈ xbest

8Vi，t+1=xr1，t+F（xbest，t-xr2，t）

9 ifx∈ xmiddle

10 Vi，t+1=xr1，t+F×（xlbest，t-xlworst，t）+F×（xr2，t-xr3，t）

11 else

12Vi，t+1=xr1，t+F（xr2，t-xr3，t）

13變異：對(duì)Vi，t+1應(yīng)用基于測(cè)試問(wèn)題的修復(fù)和改進(jìn)啟發(fā)產(chǎn)生Ui，t+1

14 for each j=1，2，…，m，if zilt;fj（Ui，t+1） end for

15 更新鄰域解

16 計(jì)算相鄰兩代種群的世代距離

17if GDlt;0.01

18使用Lévy隨機(jī)擾動(dòng)，V′i（t）=Vi（t）+l⊕Levy（λ）

19if zilt;fj（V′i（t）） end for

20更新鄰域解

21 更新EP，從EP中移除所有被F（y）支配的向量，如果EP中的所有向量都不被F（y）支配，則把F（y）加入到EP中

22 終止條件：停止并輸出EP，否則轉(zhuǎn)5

通過(guò)上述子代產(chǎn)生方法，進(jìn)化過(guò)程中每一代種群中個(gè)體的變異方式都得到有針對(duì)性的調(diào)整，更適應(yīng)個(gè)體自身的進(jìn)化需求，避免盲目搜索所導(dǎo)致的計(jì)算量大、收斂速度慢等缺陷，因而加快了種群的整體收斂速度，達(dá)到種群收斂性與多樣性的平衡。

對(duì)于優(yōu)秀個(gè)體，因保留其優(yōu)良基因，加強(qiáng)其局部搜索能力，采用如下公式產(chǎn)生子代個(gè)體：

Vi，t+1=xr1，t+F（xbest，t-xr2，t），

Ui，t+1=Vi，t+1rand（j）≤CR

xi，tothers（3）

其中：xr1，t、xr2，t為隨機(jī)選擇的子代基向量；xbest，t是第t代種群中最優(yōu)的個(gè)體；F為縮放因子；CR為交叉概率。縮放因子F決定了變異操作中差分矢量對(duì)基向量的擾動(dòng)程度，F(xiàn)取值較小時(shí)，群體差異度減小，使得種群可以在其局部范圍內(nèi)快速搜索到最優(yōu)值，交叉概率因子CR控制交叉操作生成的實(shí)驗(yàn)個(gè)體中變異個(gè)體所占分量的比例，即實(shí)驗(yàn)個(gè)體中哪些分量由變異向量貢獻(xiàn)，哪些分量由目標(biāo)向量貢獻(xiàn)，當(dāng)CR較大時(shí)，實(shí)驗(yàn)個(gè)體中變異個(gè)體所占的比例較大，有利于局部搜索和加速收斂速度，因此本文對(duì)于優(yōu)秀個(gè)體的F設(shè)置為0.9，CR設(shè)置為0.1。

對(duì)于中間個(gè)體，說(shuō)明個(gè)體i的適應(yīng)度值處于種群平均水平，此時(shí)，應(yīng)根據(jù)進(jìn)化代數(shù)，自適應(yīng)調(diào)整F和CR的值，并根據(jù)鄰居節(jié)點(diǎn)信息，調(diào)整進(jìn)化策略，其產(chǎn)生子代的公式為

vi，t+1=xr1，t+F×（xlbest，t-xlworst，t）+F×（xr2，t-xr3，t）

Ui，t+1=Vi，t+1rand（j）≤CR

xi，tothers（4）

其中：xr1，t、xr2，t、xr3，t為隨機(jī)選擇的子代基向量；xlbest，t、xlworst，t分別為鄰域范圍內(nèi)最優(yōu)和最差的個(gè)體，目標(biāo)向量是由每一代相鄰的M個(gè)體中的最好和最壞的個(gè)體衍生而來(lái)的。確保算法避免最壞的個(gè)體，并引導(dǎo)搜索過(guò)程在搜索空間內(nèi)有前途的區(qū)域，提高了其局部開發(fā)的能力。此外，通過(guò)使用局部極值代替全局極值，確保了該算法避免了局部最優(yōu)的過(guò)早收斂，因?yàn)樗梢苑乐顾袀€(gè)體受到相同極值的影響，并增加全局干擾。在進(jìn)化過(guò)程的早期階段，合適的新個(gè)體（即那些比當(dāng)前個(gè)體的適應(yīng)性更好的個(gè)體）的數(shù)量較大。在此期間，F(xiàn)應(yīng)該很大，以確保保留更好的染色體。這將增強(qiáng)全局搜索的能力。在演化過(guò)程的后期應(yīng)該降低F，以提高收斂速度。因此，F(xiàn)應(yīng)設(shè)置如下：

F=Fmaxif1-Gm0.1+Gm-Ggt;Fmax

Fminif1-Gm0.1+Gm-Glt;Fmin

e1-Gm0.1+Gm-Gothers，

F∈［0.1，0.9］（5）

當(dāng)CR較大時(shí)，雖然這有利于提高收斂速度，但它可能會(huì)降低算法的穩(wěn)定性。另一方面，一個(gè)小的CR值可能會(huì)降低探索和打開新的搜索空間的能力，在進(jìn)化過(guò)程前期，CR設(shè)置較小，保證種群的多樣性，后期CR較大，加快收斂速度。

CR=（1-e1-Gm0.1+Gm-G）×（CRmax-CRmin）+CRmin（6）

對(duì)于較差個(gè)體，應(yīng)增強(qiáng)其全局搜索的能力，保證種群多樣性，采用式（7）產(chǎn)生子代個(gè)體。

Vi，t+1=xr1，t+F（xr2，t-xr3，t），

Ui，t+1=Vi，t+1rand（j）≤CR

xi，tothers（7）

其中：xr1，t，xr2，t，xr3，t為隨機(jī)選擇的子代基向量。當(dāng)F取值較大時(shí)，加到基點(diǎn)向量上的隨機(jī)擾動(dòng)幅度較大，種群多樣性下降緩慢，保證了種群多樣性，當(dāng)CR較小時(shí)，實(shí)驗(yàn)個(gè)體中變異個(gè)體所占的比例較小，而父代目標(biāo)個(gè)體所占比例較大，有利于保持種群的多樣性和全局搜索，因此，本文設(shè)置較差個(gè)體的F為0.9，CR為0.1。考慮到變異后的個(gè)體會(huì)陷入局部最優(yōu)的問(wèn)題，一些學(xué)者通過(guò)定義種群中相鄰兩代的世代距離來(lái)判斷當(dāng)前種群是否陷入局部最優(yōu)［18～20］，從而決定是否執(zhí)行某種操作避免局部最優(yōu)問(wèn)題。相鄰兩代的距離在一定程度上反映了算法的當(dāng)前搜索能力，距離越小，算法的搜索能力越弱，世代距離的計(jì)算公式為

GD（t）=1NP∑NPi=1S（（xi（t）-xi（t-1））2（8）

本文經(jīng)實(shí)驗(yàn)驗(yàn)證當(dāng)世代距離小于0.01時(shí)，種群陷入局部最優(yōu)，使用Lévy隨機(jī)擾動(dòng)跳出當(dāng)前局部最優(yōu)解，萊維飛行是一個(gè)服從Lévy分布的隨機(jī)移動(dòng)過(guò)程，由于在大量小跳躍中存在間歇不連續(xù)的大跳躍行為，而且跳躍長(zhǎng)度具有長(zhǎng)拖尾分布的特性［15］。通過(guò)引入萊維飛行可以大大增加全局搜索能力，有利于逃出局部最優(yōu)，當(dāng)種群陷入局部最優(yōu)時(shí)對(duì)當(dāng)前解增加Lévy隨機(jī)擾動(dòng)。

x′i（t）=xi（t）+l⊕Levy（λ）（9）

l=0.01（xi（t）-xb（t））（10）

其中：Xi（t）表示第t代的第i個(gè)解；⊕表示點(diǎn)乘；l表示控制步長(zhǎng)的權(quán)重，xb為當(dāng)前最優(yōu)解；萊維飛行Levy（λ）滿足

Levy（λ）=μ|v|1β（11）

其中：β=2/3；u，v服從正態(tài)分布；u～N（0，δ2u），v～N（0，δ2v）。

δμ={Γ（β+1）sin（πβ/2）|Γ（β+1）/2|*2（β-1）/2β}1/β

δv=1（12）

其中：Γ是標(biāo)準(zhǔn)Gamma函數(shù)。

以中間個(gè)體的搜索過(guò)程為例，如圖2所示，在進(jìn)化過(guò)程前期，種群隨著進(jìn)化代數(shù)搜索到xlbest最優(yōu)點(diǎn)，陷入局部最優(yōu)，此時(shí)對(duì)當(dāng)前解加入隨機(jī)Lévy擾動(dòng)得到x′lbest，圍繞x′lbest進(jìn)行搜索，找到最優(yōu)點(diǎn)xbest。

1.4算法復(fù)雜度分析

本文算法的計(jì)算成本來(lái)自于自適應(yīng)差分進(jìn)化算法中的子代產(chǎn)生和個(gè)體選擇，時(shí)間復(fù)雜度計(jì)算包括種群劃分和切比雪夫排序，M為目標(biāo)維數(shù)，N為種群規(guī)模，T為鄰域規(guī)模。切比雪夫排序時(shí)間復(fù)雜度為O（MNT），種群劃分的復(fù)雜度為O（N），因此MOEA/D-ADE-levy算法的時(shí)間復(fù)雜度為O（N）+O（MNT）；將該算法與NSGA2、NSGA3、RVEA、MOEA/D、MOEA/D-DE算法進(jìn)行時(shí)間復(fù)雜度比較，NSGA2和NSGA3算法均采用非支配排序，時(shí)間復(fù)雜度為O（MN2）［21］；RVEA算法采用精英保留策略，時(shí)間復(fù)雜度為O（MN2）［22］；MOEA/D和MOEA/D-DE算法的時(shí)間復(fù)雜度主要由切比雪夫排序產(chǎn)生為O（MNT），因?yàn)猷徲蛞?guī)模T遠(yuǎn)小于N，故MOEA/D-ADE-levy算法的時(shí)間復(fù)雜度低于SGA2、NSGA3、RVEA算法，相比于MOEA/D、MOEA/D-DE算法，其時(shí)間復(fù)雜度略高。

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

多目標(biāo)進(jìn)化算法根據(jù)性能評(píng)價(jià)指標(biāo)衡量Pareto解集優(yōu)劣，收斂性指標(biāo)衡量了解集與參考解的貼近程度，多樣性指標(biāo)衡量、了解集分布的均勻程度和求解極端值的能力，為了檢驗(yàn)MOEA/D-ADE-levy算法的性能，本實(shí)驗(yàn)使用NSGA2、NSGA3、RVEA、MOEA/D、MOEA/D-DE算法分別與MOEA/D-ADE-levy算法進(jìn)行收斂性和多樣性的分析，實(shí)驗(yàn)數(shù)據(jù)集使用DTLZ［17］，評(píng)價(jià)方法選擇了世代距離（generational distance，GD）和反轉(zhuǎn)世代距離（inverted generational distance，IGD）。將收斂性和綜合性作為評(píng)價(jià)標(biāo)準(zhǔn)，GD檢驗(yàn)算法在優(yōu)化過(guò)程中種群收斂的能力，表示解集中的每個(gè)點(diǎn)到參考集中的點(diǎn)的平均最小距離，GD值越小說(shuō)明收斂性越好。IGD計(jì)算的是參考點(diǎn)到相距最近解的平均距離，距離所有解都較遠(yuǎn)的參考點(diǎn)具有較大的IGD值，因此在反映解集收斂性的同時(shí)也能反映解集的多樣性。

2.1測(cè)試函數(shù)

DTLZ［17］是用于評(píng)價(jià)高維MOEA性能最廣泛的測(cè)試集之一，目標(biāo)個(gè)數(shù)可以任意設(shè)置，并且具有線性、凸凹面、多峰性、退化性，以及連續(xù)非連續(xù)性等特征［21］，因而實(shí)驗(yàn)采用DTLZ［17］進(jìn)行算法對(duì)比和性能分析。在測(cè)試集中，一個(gè)給定的M目標(biāo)測(cè)試中，每一個(gè)目標(biāo)函數(shù)的決策變量為n=m+r-1。測(cè)試問(wèn)題劃分為4、5、8、10、15目標(biāo)時(shí)，即m∈{4，5，8，10，15}，對(duì)于DTLZ1設(shè)r=5，DTLZ2～6設(shè)r=10，DTLZ7設(shè)r=20。為保證算法的公正性，按照參考文獻(xiàn)［21］對(duì)實(shí)驗(yàn)參數(shù)進(jìn)行設(shè)置。

2.2結(jié)果對(duì)比分析

表2中，對(duì)于每一個(gè)具體的數(shù)據(jù)值，在所有算法中如果是最佳的就以字體加粗表示，而次優(yōu)的數(shù)據(jù)值加下劃線表示，后續(xù)相關(guān)的表格也用相同的方法進(jìn)行表示。當(dāng)測(cè)試函數(shù)為DTLZ1時(shí)，MOEA/D-ADE-levy有最小的GD值，表明其收斂性最優(yōu)；在測(cè)試函數(shù)DTLZ2上，在4、10維上GD值僅次于最優(yōu)值，在其他維度上均為最優(yōu)；在測(cè)試函數(shù)DTLZ3中，僅在維度為5時(shí)表現(xiàn)稍差，在其他維度上均獲得最小的GD值；在測(cè)試函數(shù)DTLZ4和DTLZ5中，本算法在4、8維上的GD值僅次于最優(yōu)值，在其他維度上均為最優(yōu)；在測(cè)試函數(shù)為DTLZ6時(shí)，本算法僅在維度為15維時(shí)得到次優(yōu)GD值，表現(xiàn)稍差；在測(cè)試函數(shù)DTLZ7中，本算法在4維上得到次優(yōu)GD值，在其他維度上均最優(yōu)。在35項(xiàng)數(shù)據(jù)對(duì)比中，本算法有22項(xiàng)值表現(xiàn)為最優(yōu)，5項(xiàng)值表現(xiàn)為次優(yōu)。

表3中，當(dāng)測(cè)試函數(shù)為DTLZ1、DTLZ5和DTLZ6時(shí)，MOEA/D-ADE-levy在各個(gè)維度上均有最小的IGD值，表明其多樣性最好；當(dāng)測(cè)試函數(shù)為DTLZ2和DTLZ3時(shí)，算法分別在5、10維上獲得次優(yōu)值，在其他維度上均有最小IGD值；當(dāng)測(cè)試函數(shù)為DTLZ4時(shí)，在5、10、15維上得到次優(yōu)IGD值，在8維上得到最優(yōu)值；當(dāng)測(cè)試函數(shù)為DTLZ7時(shí)，算法僅在4維上表現(xiàn)最優(yōu)，其性能稍差。在35項(xiàng)數(shù)據(jù)對(duì)比中，本算法有25項(xiàng)值表現(xiàn)為最優(yōu)，6項(xiàng)值表現(xiàn)為次優(yōu)。

為了更加直觀地比較各算法之間的性能，將NSGA2、NSGA3、RVEA算法同R2-MOEA/D在4、5、8、10、15維下，測(cè)試函數(shù)為DTLZ（1～7），進(jìn)行對(duì)比，其GD值比較如圖3所示。

從圖3可以看出，MOEA/D-ADE-levy算法在DTLZ1～7中其GD值增長(zhǎng)緩慢，且均能得到較小的GD值，其他幾種算法在不同測(cè)試函數(shù)中其GD值增長(zhǎng)浮動(dòng)較大；NSGA2算法在DTLZ1～7中，其GD值增加最快，性能較差；NSGA3算法和RVEA算法在測(cè)試函數(shù)DTLZ5、6上GD值變化快，性能差；MOEAD-DE算法在測(cè)試函數(shù)為DTLZ7時(shí)性能略差于MOEA/D-ADE-levy算法；MOEA/D算法其GD值高于本文算法；本文算法在測(cè)試函數(shù)DTLZ1～7上其GD值隨著維度的變化而變化緩慢，其GD值在同一維度下的同一測(cè)試函數(shù)上低于其他五個(gè)算法，即MOEA/D-ADE-levy算法的收斂性能優(yōu)于其他五個(gè)算法。

從圖4中可以看出，MOEA/D-ADE-levy算法在DTLZ1～6上其IGD值增長(zhǎng)緩慢，其他幾種算法在不同測(cè)試函數(shù)中其GD值增長(zhǎng)浮動(dòng)較大NSGA2算法在DTLZ1～7中，其IGD值增加最快，性能較差；N其他幾種算法在測(cè)試函數(shù)DTLZ4～7中，其IGD值變化起伏大，性能較差，本文算法在測(cè)試函數(shù)為DTLZ7時(shí)性能稍差，這是由于DTLZ7測(cè)試函數(shù)具有混合、不連續(xù)、多模態(tài)等特性，本文算法在測(cè)試函數(shù)DTLZ1～6上其IGD值隨著維度的變化變化緩慢，其IGD值在同一維度下的同一測(cè)試函數(shù)上低于其他五個(gè)算法，因此本文算法在連續(xù)，多模態(tài)情況下優(yōu)于其他算法，即MOEA/D-ADE-levy算法的收斂性能優(yōu)于其他五個(gè)算法。

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

本文針對(duì)傳統(tǒng)MOEA/D算法存在收斂性和多樣性不平衡，且在算法后期容易陷入局部最優(yōu)的問(wèn)題，提出了一種MOEA/D-ADE-levy算法。該算法首先通過(guò)正交水平混合矩陣和改進(jìn)切比雪夫產(chǎn)生均與分布的權(quán)重向量和初始種群，對(duì)于收斂性和多樣性不平衡問(wèn)題，提出自適應(yīng)選擇DE進(jìn)化算子，將種群分為優(yōu)秀個(gè)體、中間個(gè)體和較差個(gè)體，對(duì)三種個(gè)體進(jìn)行不同的DE進(jìn)化算子選擇，最后對(duì)陷入局部最優(yōu)的種群加入Lévy隨機(jī)擾動(dòng)，增加其全局搜索的能力，使當(dāng)前種群跳出局部最優(yōu)。通過(guò)該算法可以得到：

a）將MOEA/D-ADE-levy算法于NSGA2、NSGA3、RVEA、MOEA/D、MOEA/D-DE算法在測(cè)試函數(shù)為DTLZ1～7上進(jìn)行收斂性和多樣性的比較，MOEA/D-ADE-levy算法在相同維度上同其他算法相比有更小的GD、IGD值，表明該算法的收斂性和多樣性優(yōu)于其他幾個(gè)算法；b）MOEA/D-ADE-levy算法將種群分為不同個(gè)體自適應(yīng)選擇算子，提高了算法收斂性和多樣性的平衡，算法后期加入Lévy擾動(dòng)，能夠使算法跳出局部最優(yōu)。

參考文獻(xiàn)：

［1］申曉寧，孫毅，薛云勇.采用放松支配關(guān)系的高維多目標(biāo)微分進(jìn)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2018，54（18）：161-167.（Shen Xiao-ning，Sun Yi，Xue Yunyong.High-dimensional multi-objective differential evolution algorithm using relaxed dominance relations［J］.Computer Engineering and Applications，2018，54（18）：161-167.）

［2］Fan Zhun，Li Wenji，Cai Xinye，et al.An improved epsilon constraint-handling method in MOEA/D for CMOPs with large infeasible regions［J］.Soft Computing，2019，23（23）：12491-12510.

［3］吳天緯，安斯光，孫崎嶇，等.改進(jìn)聚合樹的高維多目標(biāo)降維優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2020，56（21）：47-53.（Wu Tianwei，An Siguang，Sun Qiyu，et al.Improved aggregation tree based high-dimensio-nal multi-objective dimensionality reduction optimization algorithm［J］.Computer Engineering and Applications，2020，56（21）：47-53.）

［4］劉建昌，李飛，王洪海，等.進(jìn)化高維多目標(biāo)優(yōu)化算法研究綜述［J］.控制與決策，2018，33（5）：879-887.（Liu Jianchang，Li Fei，Wang Honghai，et al.Research review of evolutionary high-dimensio-nal multi-objective optimization algorithms［J］.Control and Decision，2018，33（5）：879-887.）

［5］張景成，戴光明.基于指標(biāo)的多目標(biāo)進(jìn)化算法研究［J］.計(jì)算機(jī)工程，2009，35（23）：187-189，193.（Zhang Jingcheng，Dai Guangming.Research on multi-objective evolutionary algorithm based on index［J］.Computer Engineering，2009，35（23）：187-189，193.）

［6］Liu Yuanchao，Liu Jianchang，Li Tianjun，et al.An R2 indicator and weight vector-based evolutionary algorithm for multi-objective optimization［J］.Soft Computing，2020，24（7）：5079-5100.

［7］余進(jìn)，何正友，錢清泉.基于偏好信息的多目標(biāo)微粒群優(yōu)化算法研究［J］.控制與決策，2009，24（1）：66-70.（Yu Jin，He Zhengyou，Qian Qingquan.Research on multi-objective particle swarm optimization algorithm based on preference information［J］.Control and Decision，2009，24（1）：66-70.）

［8］Scheepers C，Engelbrecht A P，Cleghorn C W.Multi-guide particle swarm optimization for multi-objective optimization：empirical and stability analysis［J］.Swarm Intelligence，2019，13（3）：245-276.

［9］譚瑋，邱啟倉(cāng)，俞維，等.一種基于鄰域改進(jìn)的分解多目標(biāo)進(jìn)化算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2020，41（12）：81-87.（Tan Wei，Qiu Qicang，Yu Wei，et al.A decomposition multi-objective evolutio-nary algorithm based on neighborhood improvement［J］.Small Microcomputer System，2020，41（12）：81-87.）

［10］Tanabe R，Ishibuchi H.Review and analysis of three components of the differential evolution mutation operator in MOEA/D-DE［J］.Soft Computing，2019，23（23）：12843-12857.

［11］Zhou Zhongbao，Liu Xianghui，Xiao Helu，et al.A DEA-based MOEA/D algorithm for portfolio optimization［J］.Cluster Computing，2019，22（6）：14477-14486.

［12］Zapotecas M S，Coello C C A.A proposal to hybridize multi-objective evolutionary algorithms with non-gradient mathematical programming techniques［C］//Proc of International Conference on Parallel Problem Solving from Nature.Berlin：Springer，2008：837-846.

［13］謝承旺，余偉偉，閉應(yīng)洲，等.一種基于分解和協(xié)同的高維多目標(biāo)進(jìn)化算法［J］.軟件學(xué)報(bào)，2020，31（2）：356-373.（Xie Chengwang，Yu Weiwei，Hui Yingzhou，et al.A high-dimensional multi-objective evolutionary algorithm based on decomposition and collaboration［J］.Journal of Software，2020，31（2）：356-373.）

［14］謝承旺，肖馳，丁立新，等.HMOFA：一種混合型多目標(biāo)螢火蟲算法［J］.軟件學(xué)報(bào)，2018，29（4）：1143-1162.（Xie Chengwang，Xiao Chi，Ding Lixin，et al.HMOFA：a hybrid multi-object firefly algorithm［J］.Journal of Software，2018，29（4）：1143-1162.）

［15］李志軍.基于Sobol序列和間歇Lévy跳躍的改進(jìn)蝙蝠算法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2021，51（8）：313-320.（Li Zhijun.Improved bat algorithm based on Sobol sequence and intermittent Lévy jump［J］.Mathematics in Practice and Knowledge，2021，51（8）：313-320.）

［16］Liu Hailin，Wang Yuping，Cheung Y M.A multi-objective evolutionary algorithm using min-max strategy and sphere coordinate transformation［J］.Intelligent Automation and Soft Computing，2009，15（3）：361-384.

［17］Ma Xiaoliang，Liu Fang，Qi Yutao，et al.MOEA/D with biased weight adjustment inspired by user preference and its application on multi-objective reservoir flood control problem［J］.Soft Computing，2016，20（12）：4999-5023.

［18］王興銀.超多目標(biāo)優(yōu)化問(wèn)題的算法研究［D］.西安：西安電子科技大學(xué)，2020.（Wang Xingyin.Research on many-objective evolutio-nary algorithm［D］.Xi’an：Xidian University，2020.）

［19］宋佳音，池志祥，張曉鵬，等.基于樽海鞘和自適應(yīng)差分進(jìn)化的相機(jī)內(nèi)參優(yōu)化［J］.自動(dòng)化與儀表，2020，35（4）：1-5，10.（Song Jiayin，Chi Zhixiang，Zhang Xiaopeng，et al.Optimization of camera internal parameters based on salvia and adaptive differential evolution［J］.Automation and Instrumentation，2020，35（4）：1-5，10.）

［20］沈鑫，鄒德旋，張強(qiáng).采用雙變異策略的自適應(yīng)差分進(jìn)化算法及應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2020，56（4）：151-162.（Shen Xin，Zou Dexuan，Zhang Qiang.Adaptive differential evolution algorithm using double mutation strategy and its application［J］.Computer Engineering and Applications，2020，56（4）：151-162.）

［21］Chen Fang，Zhou Jianzhong，Wang Chao，et al.A modified gravitatio-nal search algorithm based on a non-dominated sorting genetic approach for hydro-thermal-wind economic emission dispatching［J］.Energy，2017，121：276-291.

［22］Cheng Ran，Jin Yaochu，Olhofer M，et al.A reference vector guided evolutionary algorithm for many-objective optimization［J］.IEEE Trans on Evolutionary Computation，2016，20（5）：773-791.

［23］劉元，鄭金華，鄒娟，等.基于鄰域競(jìng)賽的多目標(biāo)優(yōu)化算法［J］.自動(dòng)化學(xué)報(bào)，2018，44（7）：1304-1320.（Liu Yuan，Zheng Jinhua，Zou Juan，et al.Multi-objective optimization algorithm based on neighborhood competition［J］.Acta Automatica Sinica，2018，44（7）：1304-1320.）

收稿日期：2021-08-21；修回日期：2021-11-16基金項(xiàng)目：教育部產(chǎn)學(xué)合作協(xié)同與人項(xiàng)目（202101374004）

作者簡(jiǎn)介：郝秦霞（1980-），女，陜西西安人，副教授，博士研究生，主要研究方向?yàn)槲锫?lián)網(wǎng)應(yīng)用、數(shù)據(jù)決策分析（haoqinxia@xust.edu.cn）；汪連連（1997-），女，陜西安康人，主要研究方向?yàn)槲锫?lián)網(wǎng)應(yīng)用、數(shù)據(jù)決策分析．