林秀麗,李均利,聶君鳳

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,成都 610101)

1 引 言

差分進(jìn)化算法(Differential Evolution,DE)是由Storn和Price[1]所提出的一種求解優(yōu)化問題的全局優(yōu)化算法.差分進(jìn)化算法原理簡(jiǎn)單易于實(shí)現(xiàn),具有魯棒性強(qiáng)、控制參數(shù)少、搜索能力強(qiáng)[2]等優(yōu)點(diǎn).它不僅能夠解決多模態(tài)和非線性函數(shù),還能并行處理大規(guī)模問題.因此,該算法廣泛應(yīng)用于機(jī)械工程、信號(hào)處理、人工智能、數(shù)據(jù)挖掘和模式識(shí)別等多個(gè)領(lǐng)域.但在求解復(fù)雜優(yōu)化問題時(shí),隨著種群多樣性的降低,差分進(jìn)化算法容易早熟,并且在搜索后期易陷入局部最優(yōu)值,收斂的精度也會(huì)降低.另外,差分進(jìn)化算法的優(yōu)化性能[3]對(duì)控制參數(shù)(如種群大小NP、放縮率因子F和交叉概率因子CR)和變異策略非常敏感.為了解決這些問題,差分進(jìn)化算法的改進(jìn)方案主要包括對(duì)控制參數(shù)的設(shè)置、變異策略的選擇、結(jié)合其他優(yōu)化算法和實(shí)現(xiàn)多種群并行搜索等.

研究者通過參數(shù)調(diào)整來提高DE的性能,如Draa A等[4]引入了正弦微分進(jìn)化(SinDE),SinDE采用了兩個(gè)正弦公式來調(diào)整縮放因子和交叉率的值.Deng等[5]試圖使用小波基函數(shù)來選擇參數(shù),僅在部分問題上提高了DE的性能.Cui等人[6]提出了一種參數(shù)自適應(yīng)方案(chDE),其中通過二分法來壓縮控制參數(shù)空間.另外,Fan and Yan[7]提出一種具有控制參數(shù)分區(qū)進(jìn)化和自適應(yīng)變異策略的自適應(yīng)DE算法,其中變異策略隨著種群進(jìn)化而自動(dòng)調(diào)整,控制參數(shù)在各自的區(qū)域內(nèi)進(jìn)化,以自適應(yīng)地發(fā)現(xiàn)近似最優(yōu)值.自適應(yīng)控制參數(shù)是指在迭代過程中的每個(gè)階段應(yīng)選擇合適的控制參數(shù)進(jìn)行迭代,這可以加快收斂速度,減少陷入局部最優(yōu)值的概率.但是,通常這樣的操作會(huì)增加算法的時(shí)間復(fù)雜度;研究者通過變異策略來提高DE的性能,如Wang 等[8]將復(fù)合策略應(yīng)用到DE中,在深入研究現(xiàn)有變異算子和參數(shù)的性質(zhì)后,提出了復(fù)合差分進(jìn)化算法(CoDE).CoDE在3種不同的變異策略中隨機(jī)選擇一種來執(zhí)行變異操作.Duan等[9]提出了一種具有雙重偏好學(xué)習(xí)變異(DPLDE)的差分進(jìn)化算法.吳文海等[10]提出了一種基于隨機(jī)鄰域變異策略和廣義反向?qū)W習(xí)的自適應(yīng)差分進(jìn)化算法,將鄰域的概念引入到差分進(jìn)化算法中,并將局部鄰域變異和全局鄰域變異結(jié)合為一種新的策略.雖然差分進(jìn)化算法的各種變異策略可以獲得更高的收斂精度和更快的收斂速度,但在求解復(fù)雜優(yōu)化問題時(shí)容易陷入局部最優(yōu);研究者結(jié)合變異策略和參數(shù)自適應(yīng)來提高DE性能,如Yi等[11]人利用混合變異策略操作和自適應(yīng)控制參數(shù)提出了一種新的差分進(jìn)化算法,該算法將種群分為兩部分.Fan等[12]提出了一種具有策略自適應(yīng)和基于知識(shí)的控制參數(shù)(SAKPDE).在該算法中,采用了一種學(xué)習(xí)遺忘機(jī)制來實(shí)現(xiàn)變異和交叉策略的自適應(yīng).Sun等[13]為了提高差分進(jìn)化算法性能,提出一種新的高斯變異算子和一種改進(jìn)的突變算子來協(xié)同產(chǎn)生新的變異向量,并利用非周期函數(shù)和高斯函數(shù)分別生成所需的比例因子值和交叉率值,部分工作主要集中在控制參數(shù)的自適應(yīng)策略上.然而,沒有免費(fèi)午餐定理[14]指出,沒有一個(gè)算法可以解決所有類型的優(yōu)化問題.如果可以將其他算法的優(yōu)勢(shì)融入差分進(jìn)化算法中,充分利用各自的優(yōu)勢(shì)進(jìn)行協(xié)同搜索來提高優(yōu)化性能.研究者提出結(jié)合其他算法來提高DE的性能,如Chen等[15]人將混合粒子群算法和標(biāo)準(zhǔn)差分算法結(jié)合提高DE算法的搜索能力.Pan等[16]將蛙跳算法和標(biāo)準(zhǔn)差分進(jìn)化算法提升算法性能.另外,Jia等[17]提出了一種結(jié)合螞蚱算法(GOA)來提升差分算法(jDE),稱為GOA_jDE.

本文通過調(diào)整參數(shù)和調(diào)整變異策略的方法來提升DE的性能,為了進(jìn)一步加快收斂速度而不增加時(shí)間復(fù)雜度并且提高差分進(jìn)化算法的準(zhǔn)確性和穩(wěn)定性,于是本文提出了一種參數(shù)自適應(yīng)的精英變異差分進(jìn)化算法(A parameter Adaptive Elite Mutation Eifferential Evolution algorithm,AMEDE).AMEDE算法,在基本變異策略(DE/rand-to-best/1)的基礎(chǔ)上設(shè)計(jì)了一種新的精英變異策略(DE/rand-to-elite/1).首先,將精英變異策略與新引入的權(quán)重因子控制參數(shù)相結(jié)合,采用精英變異策略(DE/rand-to-elite/1)進(jìn)行變異操作,可以有效地避免收斂早熟,有利于搜索較大的空間,從而找到更有前途的區(qū)域,其目的是提高算法的搜索效率.最后,利用參數(shù)自適應(yīng)的學(xué)習(xí)方法對(duì)控制參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整設(shè)置,目的是為不同的優(yōu)化問題選擇不同的參數(shù)來求解全局最優(yōu)值.這有利于加快收斂速度,降低時(shí)間復(fù)雜度,提高優(yōu)化性能.

2 標(biāo)準(zhǔn)差分進(jìn)化算法(DE)

差分進(jìn)化算法是一種基于群體差異的啟發(fā)式并行搜索方法,作為一種基于群體導(dǎo)向的隨機(jī)搜索技術(shù),差分進(jìn)化算法的執(zhí)行過程主要包括4個(gè)部分:初始化種群、變異操作、交叉操作和選擇操作.

2.1 初始化種群

若優(yōu)化問題的目標(biāo)函數(shù)為min(f(x)),搜索空間為s∈R.DE采用一個(gè)D維的向量(M)作為優(yōu)化問題的初始解.設(shè)置種群大小(NP),每個(gè)個(gè)體都是解空間中的一個(gè)候選解,個(gè)體可以表示Xi,G={X1,X2,X3,…,Xm},i=1,2,3,…,NP.NP表示種群數(shù)量,M是候選解個(gè)數(shù).在問題搜索空間范圍內(nèi)[xmax,xmin],采用隨機(jī)方法生成個(gè)體如公式(1)所示:

xi,G=xmin+rand(0,1)*(xmax+xmin)

(1)

公式中,G表示第G次迭代的解,xmax表示問題搜索空間的上限值,xmin表示搜索空間的下限值.rand為[0,1]之間的符合正態(tài)分布的隨機(jī)數(shù).

2.2 變異操作

差分進(jìn)化算法通過變異操作產(chǎn)生新的變異個(gè)體向量vi=[vi,1,vi,2,vi,3,…,vi,G],通常情況下采用以下變異策略進(jìn)行變異操作:

1)DE/rand/1

vi=xr1+F×(xr2-xr3)

(2)

2)DE/best/1

vi=xbest+F×(xr1-xr2)

(3)

3)DE/current-to-best/1

vi=xi+F×(xbest-xr1)+F×(xr2-xr3)

(4)

4)DE/best/2

vi=xbest+F×(xr1-xr2)+F×(xr3-x4)

(5)

5)DE/rand/2

vi=xr1+F×(xr2-xr3)+F×(xr4-x5)

(6)

其中,r1,r2,r3,r4,r5∈{1,2,3,4,5,…,NP}并且r1≠r2≠r3≠r4≠r5;F是一個(gè)重要的控制參數(shù),放縮率因子F∈[0,1]主要是用來控制差分向量的幅度.xbest=[xbest,1,xbest,2,…,xbest,G]表示當(dāng)前種群中的最佳個(gè)體.在變異策略(例如:DE/rand/1)中,向量xr1表示偏差擾動(dòng)向量,也稱為基向量,xr2,xr3是方向向量,xr2-xr3視為差向量.差分進(jìn)化算法的變異策略是將種群中的兩個(gè)個(gè)體之間的加權(quán)差向量加到基向量上所產(chǎn)生的,相當(dāng)于在基向量上加上了一個(gè)隨機(jī)偏差擾動(dòng).實(shí)際上,可以將基向量作為搜索區(qū)域的中心點(diǎn),利用差分向量設(shè)置搜索方向,利用放縮率因子控制步長(zhǎng).

2.3 交叉操作

交叉操作是采用變異后得到的變異個(gè)體vi,G和目標(biāo)個(gè)體xi,G進(jìn)行交叉后得到目標(biāo)個(gè)體的候選個(gè)體ui,G.在差分進(jìn)化算法中,交叉策略為二次項(xiàng)交叉,如公式(7)所示:

(7)

式中randj∈[0,1]為服從均勻分布的隨機(jī)數(shù),交叉因子CR∈[0,1]也是進(jìn)化算法中的一個(gè)重要控制參數(shù),根據(jù)交叉因子進(jìn)行交叉操作.

2.4 選擇操作

差分進(jìn)化算法采用貪婪算法更新下一代種群中的個(gè)體,更新為公式(8)所示:

(8)

3 參數(shù)自適應(yīng)的精英變異差分進(jìn)化算法

3.1 精英變異策略

在差分進(jìn)化算法中,變異策略的選擇和控制參數(shù)的設(shè)置直接影響到算法的探索能力、收斂精度和速度.為了解決這個(gè)問題,在精英變異策略中引入新的權(quán)重因子ω,以確保個(gè)體收斂,并采用精英個(gè)體替代最優(yōu)個(gè)體的方法增加種群搜索范圍.在每一代進(jìn)化過程中,算法從當(dāng)前種群中選擇出n個(gè)個(gè)體組成精英組,并從精英組中隨機(jī)選擇其中一個(gè)個(gè)體作為精英個(gè)體.精英個(gè)體指的是種群中優(yōu)秀的個(gè)體,精英個(gè)體對(duì)種群的進(jìn)化起著推動(dòng)性作用.精英變異策略“DE/rand-to-elite/1”,具體可以表示為公式(9):

Vi=ω·Xi+F·(eliteX-Xi)+F·(Xr1-Xr2)

(9)

式中ω為(0,1)范圍內(nèi)的權(quán)重因子,由于在DE中較大的Xi值可能導(dǎo)致個(gè)體發(fā)散,不利于收斂,如圖1所示.eliteX為種群中適應(yīng)度值最小的前百分之十的個(gè)體之中的一個(gè)隨機(jī)個(gè)體則稱為精英個(gè)體,計(jì)算公如下:

圖1 AMEDE算法變異策略

eliteX=rand(sort(Fitness(Xi))*10%)

(10)

3.2 參數(shù)自適應(yīng)策略

為了使控制參數(shù)值的選擇不受具體優(yōu)化問題的影響,本文提出了一種改進(jìn)的控制參數(shù)自適應(yīng)策略,在AMEDE算法中,每個(gè)個(gè)體都有屬于自己的控制參數(shù),其包含權(quán)重因子ω,放縮率因子F和交叉率因子CR,并使其在進(jìn)化過程中進(jìn)行動(dòng)態(tài)調(diào)整,如圖2所示.與傳統(tǒng)的差分進(jìn)化算法(DE)中采用固定的控制參數(shù)值相比,參數(shù)自適應(yīng)調(diào)整策略更有利于種群進(jìn)化.本文也充分利用了進(jìn)化過程中精英個(gè)體的信息,在參數(shù)自適應(yīng)策略中提出了兩種控制參數(shù)學(xué)習(xí)的方法,分別是全體學(xué)習(xí)法和重置參數(shù)法.

圖2 AMEDE算法參數(shù)自適應(yīng)

圖3 AMEDE算法流程圖

3.2.1 控制參數(shù)學(xué)習(xí)方法

“三人行,必有我?guī)熝?擇其善者而從之,則其不善而改之”,人和動(dòng)物都可以模仿、學(xué)習(xí)優(yōu)秀的對(duì)象來進(jìn)步.這一現(xiàn)象也可以應(yīng)用到本文的控制參數(shù)學(xué)習(xí)中,學(xué)習(xí)種群中表現(xiàn)優(yōu)異的個(gè)體.本文中表現(xiàn)優(yōu)異的個(gè)體稱為精英個(gè)體,利用精英個(gè)體的控制參數(shù)信息,更新其他個(gè)體的控制參數(shù).

將個(gè)體中按照個(gè)體適應(yīng)度進(jìn)行從小到大的排序,對(duì)種群中個(gè)體適應(yīng)度值排名后40%的個(gè)體的控制參數(shù)按照以下操作進(jìn)行更新.

操作1.全體學(xué)習(xí)

充分利用精英個(gè)體的信息,在本文中如果精英個(gè)體的位置是優(yōu)秀的,那么精英個(gè)體的控制參數(shù)也是優(yōu)秀的.本文利用適應(yīng)度值排名前五的個(gè)體的平均控制參數(shù)來更新自身的控制參數(shù),更新如公式(11)和公式(12):

eliteCPG=top5(Fitness(XG))

(11)

CPi,1G+1=CPiG+r·(mean(eliteCPG)-CPiG)

(12)

式中,Fitness(XG)表示當(dāng)前種群的適應(yīng)度值,在本文中適應(yīng)度值越小說明全局最優(yōu)值越優(yōu)秀,eliteCPG={eliteFG,eliteCRG,eliteωG},利用適應(yīng)度值取出排名前5個(gè)個(gè)體的控制參數(shù)值,CPiG表示個(gè)體i的控制參數(shù)向量[Fi,1G,CRi,2G,ωi,3G],r為(0,1)之間的隨機(jī)數(shù),mean(eliteCPG)為適應(yīng)度排名前五的個(gè)體的控制參數(shù)的均值.

操作2.重置參數(shù)

在執(zhí)行全體學(xué)習(xí)控制參數(shù)時(shí)可能陷入局部最優(yōu)導(dǎo)致過早收斂,從而降低了種群多樣性.因此,合理控制種群多樣性可以對(duì)一部分個(gè)體進(jìn)行重置參數(shù)如公式(13):

(13)

式中,R表示一個(gè)3維的隨機(jī)向量,每個(gè)維度的取值范圍為(0,1).“o”表示將對(duì)應(yīng)元素相乘.CPU為各控制參數(shù)的上限值,CPL為各控制參數(shù)的下限值,本文中PU=[0.9,0.9,0.9],PL=[0.1,0.1,0.2].

3.2.2 概率閾值自適應(yīng)策略

在迭代過程中,通過計(jì)算種群中個(gè)體適應(yīng)度值的多樣性概率閾值公式(14)來選擇控制參數(shù)學(xué)習(xí)方法中的操作1或者操作2:

τ=fitness(bestX)-mean(fitness(X))

(14)

式中,fitness(bestX)表示每一代中的最優(yōu)適應(yīng)度值,mean(fitness(X)為平均適應(yīng)度值.τ是0和1之間的實(shí)數(shù).如果τ值越大,則個(gè)體相似性越低,那么個(gè)體差異大,種群多樣性越強(qiáng).反之,如果τ值越小,說明個(gè)體相似性越強(qiáng),那么種群多樣性降低.本文中利用概率閾p值判τ的大小,則概率閾值自適應(yīng)策略可以表示為公式(15):

(15)

根據(jù)以上分析可以得出兩種情況:1)當(dāng)前種群呈現(xiàn)良好的多樣性時(shí),保持當(dāng)前控制參數(shù)向精英個(gè)體參數(shù)學(xué)習(xí),這有利于更快收斂到全局最優(yōu)值;2)當(dāng)種群多樣性下降,應(yīng)調(diào)整和重置一部分控制參數(shù)值,以便產(chǎn)生新的后代個(gè)體.這些新的后代個(gè)體將有利于提高當(dāng)前種群的多樣性,幫助個(gè)體擺脫局部最優(yōu),從而避免過早收斂.因此,控制參數(shù)值的調(diào)整規(guī)則既保持了種群多樣性,又保證了算法的收斂性能.

3.3 AMEDE算法流程

3.3.1 AMEDE算法的偽代碼

輸入:目標(biāo)函數(shù)f,最大迭代次數(shù)M,問題維度D,問題搜索空間(l,u),種群大小NP,控制參數(shù)變化范圍CPU、CPL,交叉策略CS和變異策略MS

輸出:全局最優(yōu)解

Step 1. 隨機(jī)初始化種群中個(gè)體的位置X、初始化控制參數(shù)CP值、初始化精英個(gè)體eliteX的位置

Step 2. 將迭代器i=0,M=1000

Step 3.while(i

Step 4.Fort=1:NP

Step 5. 評(píng)價(jià)個(gè)體適應(yīng)度值fitness(X)

Step 6. 通過公式(11)求解排名前五的精英個(gè)體控制參數(shù)eliteF、eliteCR和eliteω

Step 7. End for

Step 8. 按公式(10)求出精英個(gè)體的位置,并更新精英個(gè)體位置eliteX

Step 9. 按公式(15)概率閾值公式選擇自適應(yīng)參數(shù)操作

Step 10.p=rand(0,1);

Step 11. Ifp<τ

Step 12. 按公式(12)更新CPi參數(shù);

Step 13. Else

Step 14. 按公式(13)更新控制參數(shù)CPi;

Step 15. End if

Step 16. 按公式(9)執(zhí)行“DE/rand-to-eliteX/1”變異操作,生成變異個(gè)體Vi

Step 17. 按公式(7)執(zhí)行交叉操作生成新的候選個(gè)體

Step 18. 計(jì)算新的候選個(gè)體適應(yīng)度值,并更新初始種群個(gè)體

Step 19.Fort=1:NP

Step 20. If fitness(Xi)

Step 21.X(i)=U(i);

Step 22. fitness(Xi)=fitness(Ui);

Step 23. End if

Step 24. End for

Step 25. 更新初始種群個(gè)體后,按照公式(10)更新精英個(gè)體位置

Step 26. 更新初始種群個(gè)體后,按照公式(11)更新精英個(gè)體控制參數(shù)值

Step 27. i++;

Step 28. END while;

3.3.2 AMEDE算法流程圖

AMEDE算法流程圖如圖5所示.

3.4 AMEDE 算法復(fù)雜度分析

AMEDE時(shí)間復(fù)雜度分析如下,考慮在一次迭代中最壞情況下的時(shí)間復(fù)雜度:

1)初始化種群中的時(shí)間復(fù)雜度為O(NP);

2)在求解和更新精英個(gè)體位置的時(shí)間復(fù)雜度為O(NP);

3)在不考慮適應(yīng)度函數(shù)的計(jì)算成本,則評(píng)價(jià)個(gè)體適應(yīng)度的時(shí)間復(fù)雜度為O(NP*D);

4)在執(zhí)行參數(shù)自適應(yīng)策略時(shí),需要更新eliteF、eliteCR和eliteω,產(chǎn)生的時(shí)間復(fù)雜O(NP*D);

綜上,可以得出AMEDE算法復(fù)雜度為O(NP*D),與標(biāo)準(zhǔn)差分進(jìn)化算法時(shí)間復(fù)雜度O(Popsize*D)相比,AMEDE算法在變異策略、參數(shù)自適應(yīng)選擇策略階段產(chǎn)生額外的計(jì)算量,但并沒有明顯增加算法時(shí)間復(fù)雜度.

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

4.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證AMEDE算法的優(yōu)化性能,本文選取了16個(gè)測(cè)試基準(zhǔn)函數(shù).具體16個(gè)測(cè)試基準(zhǔn)函數(shù)的表達(dá)式、取值范圍和屬性詳見表1所示.在這個(gè)16個(gè)測(cè)試基準(zhǔn)函數(shù)當(dāng)中,F1～F5為單峰函數(shù),主要用于評(píng)估收斂精度和收斂速度.F6～F16為多峰函數(shù),主要是用于評(píng)估全局搜索能力.為了保證實(shí)驗(yàn)結(jié)果的真實(shí)可靠,實(shí)驗(yàn)中所有算法在相同參數(shù)設(shè)置下分別在測(cè)試基準(zhǔn)函數(shù)獨(dú)立運(yùn)行30次,函數(shù)最大評(píng)估測(cè)試為1000次.采用全局最優(yōu)值的平均值和標(biāo)準(zhǔn)差作為實(shí)驗(yàn)結(jié)果的主要分析依據(jù).具體實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)參數(shù)設(shè)置如下:

表1 基準(zhǔn)測(cè)試函數(shù)

1)實(shí)驗(yàn)環(huán)境:

采用Linux系統(tǒng)中的MATALAB.R2020運(yùn)行所有程序.

2)實(shí)驗(yàn)參數(shù)設(shè)置如表2所示.

表2 實(shí)驗(yàn)參數(shù)設(shè)置

4.2 對(duì)比實(shí)驗(yàn)及結(jié)果分析

4.2.1 AMEDE與標(biāo)準(zhǔn)DE比較分析

將本文提出的AMEDE算法與標(biāo)準(zhǔn)差分進(jìn)化(DE)算法進(jìn)行對(duì)比,標(biāo)準(zhǔn)差分進(jìn)化算法中包含5個(gè)變異策略,分別是“DE/best/1”、“DE/rand/1”、“DE/rand-to-best/1”、“DE/best/2”和“DE/rand/2”.實(shí)驗(yàn)中,根據(jù)文獻(xiàn)[18],設(shè)置差分算法的控制參數(shù)為:種群大小(NP=100),放縮率因子(F=0.5),交叉率因子(CR=0.3).每種算法對(duì)每個(gè)函數(shù)得到的最優(yōu)解均值(mean)和標(biāo)準(zhǔn)差(std)如表3、表4所示,其中最優(yōu)值用粗體表示.每種算法的成功率(sr)和每個(gè)函數(shù)達(dá)到指定收斂精度所需的平均迭代次數(shù)(mgen)在表5中所示,其中“null”表示不適用.收斂精度設(shè)置:F8為-10+5為F5、F14和F16為10-1,F2和F9為10-5,F1、F7、F11、F12和F15為10-15,其他均為10-10.mgen和sr分別用于比較各算法的收斂速度和可靠性.為了便于說明,將函數(shù)的收斂曲線繪制在圖4中.

表3 6種策略的測(cè)試結(jié)果(D=30)

表4 6種策略的測(cè)試結(jié)果(D=50)

表5 6種策略的穩(wěn)定性測(cè)試結(jié)果(D=30)

圖4 F1-F16收斂圖

算法結(jié)果分析如下:

從實(shí)驗(yàn)結(jié)果中可以看出,AMEDE算法在D=30和D=50的情況下,都能夠在所有的基準(zhǔn)測(cè)試函數(shù)上找到最優(yōu)值,且收斂速度快,穩(wěn)定性強(qiáng).當(dāng)D=30時(shí),AMEDE算法僅在測(cè)試基準(zhǔn)函數(shù)F14上沒有找到比“DE/rand/1”、“DE/rand-to-best/1”和“DE/rand/2”更小的最優(yōu)值,但AMEDE算法也取得了不錯(cuò)的最優(yōu)值結(jié)果.AMEDE算法能在16個(gè)測(cè)試基準(zhǔn)函數(shù)中能獲取到5個(gè)基準(zhǔn)測(cè)試函數(shù)(F5、F9、F11、F13和F16)的全局最優(yōu)值,另外在13個(gè)基準(zhǔn)測(cè)試函數(shù)上優(yōu)于“DE/rand/2”,在15個(gè)基準(zhǔn)測(cè)試函數(shù)上優(yōu)于“DE/rand/1”和在16個(gè)基準(zhǔn)測(cè)試函數(shù)優(yōu)于“DE/best/1”、“DE/rand-to-best/1”和“DE/best/2”.當(dāng)D=50時(shí),AMEDE算法仍能夠在基準(zhǔn)測(cè)試函數(shù)F5、F9、F11和F13上獲取到全局最優(yōu)值,除在F14上沒有明顯優(yōu)于其他變異策略以外,在其他的基準(zhǔn)測(cè)試函數(shù)上都獲取到了最優(yōu)值.這說明AMEDE算法在高維基準(zhǔn)問題下,仍能夠保持一個(gè)較好的尋優(yōu)能力.

具體的從表4和圖4中可知,收斂精度和收斂速度方面,AMEDE是5種變異策略中表現(xiàn)最好的.這是因?yàn)锳MEDE通過改進(jìn)“DE/rand/1”模式和引入控制參數(shù)自適應(yīng)策略,可以動(dòng)態(tài)調(diào)整種群多樣性,提高收斂性能.從表5中可知,在可靠性方面,標(biāo)準(zhǔn)DE性能明顯不如AMEDE算法.對(duì)于標(biāo)差分進(jìn)化算法中的變異策略來說,使用固定的參數(shù)設(shè)置并不適合各種基準(zhǔn)測(cè)試函數(shù).例如,“DE/rand/2”和“DE/best/1”在單峰函數(shù)F1和F2上得到了較好的結(jié)果,而在多峰函數(shù)F7、F8和F11上結(jié)果較差.

對(duì)標(biāo)準(zhǔn)差分進(jìn)化算法中的各個(gè)變異策略方法和AMEDE算法在各基準(zhǔn)測(cè)試函數(shù)上的最優(yōu)結(jié)果的均值排名采用Friedman檢驗(yàn),結(jié)果如表6所示,均值排名為算法在各基準(zhǔn)測(cè)試函數(shù)上排名的均值,并且分為所有基準(zhǔn)測(cè)試函數(shù)、單峰基準(zhǔn)測(cè)試函數(shù)、多峰基準(zhǔn)測(cè)試函數(shù)3種情況進(jìn)行分析,卡方值為對(duì)應(yīng)的統(tǒng)計(jì)值,P值為對(duì)應(yīng)的概率值,如果P<0.05則可以說明,在0.05水平上對(duì)應(yīng)情況上6種變異策略方法有明顯差異顯著,而排名情況也能說明各個(gè)變異策略算法的優(yōu)劣.從表5中可以得出,在所有的基準(zhǔn)測(cè)試函數(shù)上p值均<0.05,并且在3種情況下AMEDE算法排名均為第一.在F檢驗(yàn)的結(jié)果下AMEDE算法相比于標(biāo)準(zhǔn)差分進(jìn)化算法中的變異策略方法有更好的尋優(yōu)效果.

表6 AMEDE算法與DE算法的F檢驗(yàn)結(jié)果

4.2.2 AMEDE與其他改進(jìn)DE比較分析

將AMEDE算法與復(fù)雜差分進(jìn)化算法(CoDE)[8]、自適應(yīng)差分進(jìn)化策略(JaDE)[19]、自適應(yīng)參數(shù)差分進(jìn)化算法(SaDE)[20]、帶有外部歸檔的自適應(yīng)差分進(jìn)化算法(JDE)[21]和基于高斯變異和動(dòng)態(tài)參數(shù)調(diào)整的差分進(jìn)化算法(GPDE)[13]等5種具有代表性的改進(jìn)差分進(jìn)化算法進(jìn)行對(duì)比.

實(shí)驗(yàn)中,各算法控制參數(shù)按照對(duì)應(yīng)參考文獻(xiàn)進(jìn)行設(shè)置.各個(gè)算法的實(shí)驗(yàn)結(jié)果如表7、表8、表9和表10所示,其中全局最優(yōu)值用粗體表示.

表7 6個(gè)算法的測(cè)試結(jié)果(D=30)

表8 6個(gè)算法的穩(wěn)定性測(cè)試結(jié)果(D=30)

表9 6個(gè)算法的測(cè)試結(jié)果(D=50)

表10 AMEDE算法對(duì)其他算法的T檢驗(yàn)結(jié)果

1)算法結(jié)果分析

根據(jù)實(shí)驗(yàn)結(jié)果可知,AMEDE算法在16個(gè)基準(zhǔn)測(cè)試函數(shù)中尋優(yōu)效果最好,能夠在15個(gè)基準(zhǔn)測(cè)試函數(shù)上獲得最優(yōu)值.表7和表8列出了6種差分改進(jìn)算法在16個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上獨(dú)立運(yùn)行30次后所出結(jié)果的平均值和標(biāo)準(zhǔn)差.從表中可以看出AMEDE算法在單峰函數(shù)F5和多峰函數(shù)F9、F11、F13和F16上收斂精度明顯優(yōu)于其他5個(gè)算法.AMEDE算法在多峰基準(zhǔn)測(cè)試函數(shù)F6上最優(yōu)值的收斂精度略次于SaDE算法.SaDE作為經(jīng)典差分改進(jìn)算法中的一員,在一些基準(zhǔn)測(cè)試函數(shù)上有較好的收斂結(jié)果,這也是不意外的.AMEDE算法在多峰函數(shù)F14上收斂精度和穩(wěn)定性略劣于CoDE、JaDE和JDE,優(yōu)于SaDE和GPED算法.對(duì)于SaDE和GPED,雖然采用了參數(shù)自適應(yīng)策略來提高DE的性能,但控制參數(shù)值的更新是隨機(jī)的,缺乏演化過程的指導(dǎo).對(duì)于GPED,在產(chǎn)生新的控制參數(shù)值時(shí),沒有考慮個(gè)體的差異,容易導(dǎo)致過早收斂.而在AMEDE中,控制參數(shù)值會(huì)根據(jù)種群多樣性自動(dòng)調(diào)整,并利用個(gè)體的差異來指導(dǎo)生成新的參數(shù),有利于提高個(gè)體逃避局部極小值的能力,促進(jìn)個(gè)體向正確方向搜索.因此,IMMSADE的性能最好.在AMEDE中,控制參數(shù)值會(huì)根據(jù)種群多樣性自動(dòng)調(diào)整,并利用個(gè)體的差異來指導(dǎo)生成新的參數(shù),有利于提高個(gè)體逃避局部極小值的能力,促進(jìn)個(gè)體向正確方向搜索.因此,IMMSADE的性能最好.

另外,采用Kruskal-Wallis檢驗(yàn)顯著性水平為5%的非參數(shù)統(tǒng)計(jì)檢驗(yàn)進(jìn)行多重比較.表10為AMEDE算法對(duì)其他5個(gè)算法的T檢驗(yàn)值和檢驗(yàn)結(jié)果.“+”、“-”、“=”分別表示AMEDE算法對(duì)比相應(yīng)算法明顯優(yōu)于、明顯劣于、差異不明顯3種情況,分別用B、W、S表示.AMEDE算法對(duì)比CoDE算法、SaDE算法、JDE算法、JaDE和GPDE算法的B-W得分情況分別為14、13、16、15和16,都呈現(xiàn)出明顯優(yōu)勢(shì)且沒有出現(xiàn)明顯劣于其他的5個(gè)對(duì)比算法,T檢驗(yàn)結(jié)果表明AMEDE的性能明顯優(yōu)于其他的改進(jìn)差分算法.

2)算法收斂性分析

圖5分別是DE算法、CoDE算法、SaDE算法、JDE算法、JaDE算法和GPDE算法在16個(gè)基準(zhǔn)測(cè)試函數(shù)上的收斂曲線,其中橫坐標(biāo)為迭代次數(shù),縱坐標(biāo)為函數(shù)的適應(yīng)度值.為了方便對(duì)比,縱坐標(biāo)經(jīng)過了對(duì)數(shù)變換,僅畫出了各算法在基準(zhǔn)測(cè)試函數(shù)上的0-1000代之間的收斂曲線圖.從圖5中可知AMEDE算法在16個(gè)測(cè)試基準(zhǔn)函數(shù)上的收斂速明顯優(yōu)于其他算法,在單峰函數(shù)上尤其明顯,另外在大部分多峰函數(shù)上收斂表現(xiàn)也較好,這說明AMEDE算法尋優(yōu)速度快且收斂精度更高,除了在基準(zhǔn)測(cè)試函數(shù)F6上比DE算法略劣.另外,在測(cè)試函數(shù)F14上,前期收斂速度較慢但是后期也與其他算法相差甚少,AMEDE算法在大部分基準(zhǔn)測(cè)試函數(shù)上前期的收斂速度都優(yōu)于其他5個(gè)對(duì)比算法,由于精英組中的所有個(gè)體并不是全局最優(yōu)個(gè)體,因此個(gè)體的位置發(fā)生改變,因此放慢了收斂速度,但是通過學(xué)習(xí)控制參數(shù)后使得算法后期加快速收斂速度.AMEDE算法在前期利用精英個(gè)體代替全局最優(yōu)個(gè)體,保證了種群的多樣性,并采用學(xué)習(xí)精英個(gè)體控制參數(shù)信息的方法,加快了前期的收斂速度,為了進(jìn)一步確保種群中個(gè)體不發(fā)散引入的權(quán)重因子發(fā)揮了重要作用,增加了算法的收斂精度.

圖5 F1-F16收斂圖

4.2.3 AMEDE的變異策略和參數(shù)分析

AMEDE通過改進(jìn)“DE/rand-to-best/1”變異策略和引入控制參數(shù)自適應(yīng)策略來提高DE的性能.雖然,上文中的兩個(gè)實(shí)驗(yàn)驗(yàn)證AMEDE性能.但卻無法充分評(píng)估公式(5)所示的改進(jìn)變異策略和自適應(yīng)參數(shù)策略的有效性.為了解決這個(gè)問題,將不進(jìn)行參數(shù)自適應(yīng)的AMEDE算法和標(biāo)準(zhǔn)差分進(jìn)化算法與AMEDE進(jìn)行了比較.對(duì)DE中的控制參數(shù)分別設(shè)置為F=0.5,CR=0.9,對(duì)不進(jìn)行參數(shù)自適應(yīng)的AMEDE算法,ω=0.2,放縮率因子F=0.5,交叉率因子CR=0.9,另外AMEDE的參數(shù)設(shè)置與第一個(gè)實(shí)驗(yàn)相同.此外,AMEDE在參數(shù)自適應(yīng)策略中引入控制參數(shù)ω,因此確定ω的取值范圍對(duì)于不同的優(yōu)化問題是很有意義的.表12記錄了將ω分別設(shè)為0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9和1.0得到的實(shí)驗(yàn)結(jié)果.其中全局最優(yōu)值用粗體表示.

算法結(jié)果分析如下:

實(shí)驗(yàn)結(jié)果由表11可以得出,與DE相比,不帶參數(shù)自適應(yīng)的AMEDE性能明顯更好,這是因?yàn)楦倪M(jìn)的變異模式加快了在目標(biāo)的方向上的優(yōu)化搜索,提高了收斂性能.此外,還可以得出,AMEDE算法最好,無參數(shù)自適應(yīng)的AMEDE算法次之,DE最差.這表明改進(jìn)的突變模式是有效的.與無參數(shù)自適應(yīng)的AMEDE算法相比,AMEDE在收斂精度和收斂速度方面都有更好的表現(xiàn).這表明改進(jìn)的突變策略與參數(shù)適應(yīng)策略是一種有益的配合.在參數(shù)自適應(yīng)策略中為控制參數(shù)自適應(yīng)到合適的值,從而提高了算法的收斂性能.從表中還能看出,在D=30時(shí),沒有進(jìn)行參數(shù)自適應(yīng)的AMEDE算法,F3、F12和F15函數(shù)上要優(yōu)于AMEDE算法;在D=50時(shí),沒有進(jìn)行參數(shù)自適應(yīng)的AMEDE算法,F3和F12函數(shù)上要優(yōu)于AMEDE算法.這可能是由于AMEDE算法進(jìn)行控制參數(shù)適應(yīng)策略,在進(jìn)化后期,由于種群多樣性降低,可能需要頻繁調(diào)整參數(shù)值.但這些參數(shù)值可能不利于算法在有限的進(jìn)化生成數(shù)內(nèi)收斂,從而導(dǎo)致最終解的精度較低.此外,解決在高維度問題時(shí)參數(shù)的適應(yīng)性也進(jìn)一步提高了F6、F9、F13和F15函數(shù)的收斂精度.參數(shù)自適應(yīng)策略還可以幫助算法在求解具有多個(gè)局部極小值的函數(shù)時(shí),尋找更好的解,并保持較高的收斂速度.

表11 不進(jìn)行參數(shù)適應(yīng)的AMEDE與AMEDE對(duì)比(D=30、50)

如表12所示,ω取值為ω≥0.6時(shí),AMEDE表現(xiàn)較差.ω值越大,控制參數(shù)的更新速率越高,不利于新個(gè)體的產(chǎn)生和種群多樣性的維持.種群多樣性的降低導(dǎo)致早熟收斂,從而降低了收斂精度和收斂速度.相反,AMEDE設(shè)置ω≤0.5時(shí),性能更好.ω值越小,越有利于調(diào)整種群多樣性,從而提高全球勘探能力.因此,當(dāng)參數(shù)ω∈[0.1,0.6]時(shí),AMEDE的性能最佳.

表12 AMEDE的不同參數(shù)實(shí)驗(yàn)結(jié)果

通過以上實(shí)證分析,可以得出,所提出的AMEDE具有更快的收斂速度、更高的收斂精度和更強(qiáng)的魯棒性,滿足了過程優(yōu)化的實(shí)時(shí)性、準(zhǔn)確性和穩(wěn)定性要求.

5 結(jié)束語

本文提出的自適應(yīng)參數(shù)精英變異策略的差分進(jìn)化算法主要是為了解決標(biāo)準(zhǔn)差分算法中控制參數(shù)和變異策略敏感和過早收斂的問題.AMEDE算法結(jié)合了精英變異策略、參數(shù)自適應(yīng)策略和引入新的控制參數(shù)權(quán)重因子.精英變異策略利用種群中優(yōu)秀個(gè)體的信息來引導(dǎo)種群中其他個(gè)體,保證了算法的搜索效率;參數(shù)自適應(yīng)策略中的全體學(xué)習(xí)法,通過學(xué)習(xí)種群中精英個(gè)體的控制參數(shù)并對(duì)其他個(gè)體控制參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整,從而有效地避免了早熟收斂;通過概率閾值來選擇合適的參數(shù)自適應(yīng)策略,保證了種群的多樣性和收斂速度;新的控制參數(shù)權(quán)重因子是為了讓個(gè)體不再發(fā)散,確保個(gè)體收斂.通過16個(gè)測(cè)試基準(zhǔn)函數(shù)和3個(gè)對(duì)比實(shí)驗(yàn)的結(jié)果表明,本文提出的AMEDE算法具有更快的收斂速度、更高的收斂精度和更強(qiáng)的魯棒性,能夠滿足過程優(yōu)化的實(shí)時(shí)性、準(zhǔn)確性和穩(wěn)定性要求.

未來還繼續(xù)在自適應(yīng)參數(shù)和變異策略上再進(jìn)一步研究,提出不同的變異策略和不同的自適應(yīng)參數(shù)方法來提升算法性能.