封全喜 金培源 岑健銘 艾 武 林 彬

差分進(jìn)化(Differential Evolution, DE)是Storn等[1]提出的一種簡單且功能強(qiáng)大的進(jìn)化算法.算法基于種群內(nèi)個(gè)體之間的差異性進(jìn)行迭代,具有較強(qiáng)的全局搜索能力,現(xiàn)已成功應(yīng)用于許多工程領(lǐng)域,包括:無人機(jī)路徑規(guī)劃[2]、斜拉橋索力優(yōu)化[3]、系統(tǒng)功率分配[4]、飛行控制率評估[5]、激光熔覆工藝參數(shù)優(yōu)化[6]等.

差分進(jìn)化算法主要由變異、交叉、選擇三個(gè)算子構(gòu)成.變異算子是差分進(jìn)化算法的重要組成部分,不同的變異算子迭代效果不同.因此,在算法迭代過程中,需要選擇合適的變異算子.針對此問題,學(xué)者們提出多種不同的變異算子及其選擇策略.常見的變異算子選擇策略都是基于概率模型提出的.Qin等[7]提出SaDE(Self-Adaptive DE),根據(jù)各變異算子的前期迭代效果計(jì)算后驗(yàn)概率,并依據(jù)概率值選擇合適的變異算子.Liu等[8]提出HHDE(Historical and Heuristic DE),基于個(gè)體歷史成功經(jīng)驗(yàn)和其當(dāng)前狀態(tài)信息動態(tài)選擇變異算子和控制參數(shù).Pan等[9]提出SspDE(DE Algorithm with Self-Adaptive Trial Vector Generation Strategy and Control Parameters),設(shè)計(jì)變異算子列表,存放上一代變異成功的變異算子,并據(jù)此計(jì)算選擇概率.

此外,還有學(xué)者提出基于多策略共存的變異算子選擇策略.Wang等[10]提出CoDE(Composite DE),算法中每個(gè)個(gè)體采用多個(gè)不同類型的變異算子,產(chǎn)生多個(gè)候選個(gè)體,并選擇適應(yīng)度值高的個(gè)體進(jìn)入下一代.Wang等[11]在CoDE的基礎(chǔ)上,提出C2oDE(Constrained CoDE),采用三種不同變異算子,其中兩個(gè)算子側(cè)重收斂性能,一個(gè)算子側(cè)重搜索性能.此外將可行性準(zhǔn)則和ε約束方法進(jìn)行搭配,進(jìn)而選擇合適的個(gè)體進(jìn)入下一代.數(shù)值實(shí)驗(yàn)表明該算法是一種有效的算法.還有學(xué)者通過種群劃分方式,分別為不同類型的種群分配不同的變異算子.Wu等[12]提出MPEDE(Multi-population Based Ensemble DE),將種群分為三個(gè)規(guī)模相同的指標(biāo)種群和一個(gè)獎勵子種群,并為每個(gè)指標(biāo)種群分配不同的變異算子.每隔一定代數(shù)后,根據(jù)三個(gè)變異算子的迭代效率,將性能最優(yōu)的變異算子分配給獎勵子種群.

近年來,也有學(xué)者基于種群的分布信息選擇變異算子.Liu等[13]提出TSDE(DE with a Two-Stage Optimization Mechanism),利用迭代過程中前期注重全局搜索和后期注重局部收斂的特點(diǎn),將迭代過程均衡劃分為兩個(gè)階段,分別設(shè)計(jì)變異算子池.Zhou等[14]提出DEMS(DE with Multi-stage Strategies),利用種群中個(gè)體間的平均距離將迭代過程劃分成搜索、平衡和收斂三個(gè)階段,不同階段分別使用不同類型的變異算子.Zhan等[15]提出APSO(Adaptive Particle Swarm Optimization),計(jì)算種群中所有個(gè)體之間的歐氏距離,評估種群的分布情況,并針對不同的分布情況采用不同的變異算子.Yu等[16]提出ADE(Adaptive DE),利用種群中最優(yōu)個(gè)體與其它個(gè)體之間的歐氏距離評估種群的分布情況.考慮到計(jì)算所有個(gè)體之間歐氏距離的計(jì)算復(fù)雜度較高,Zhan等[17]提出ADDE(Adaptive Distributed DE),利用種群中最優(yōu)個(gè)體和中間個(gè)體評估種群的分布情況.Li等[18]提出DEET,計(jì)算所有個(gè)體距離與目標(biāo)函數(shù)值的相關(guān)性,評估種群進(jìn)化狀態(tài).

上述種群狀態(tài)評估算法取得良好的效果,表明根據(jù)種群個(gè)體的分布信息和目標(biāo)函數(shù)值評估種群狀態(tài),再選擇合適變異算子,有助于提升差分進(jìn)化算法的性能.然而,部分種群狀態(tài)評估算法只是單純使用最優(yōu)個(gè)體或中位數(shù)個(gè)體以評估種群狀態(tài),導(dǎo)致種群狀態(tài)評估不準(zhǔn)確.還有部分種群狀態(tài)評估算法即使利用種群分布信息和目標(biāo)函數(shù)值,也僅僅以最優(yōu)個(gè)體作為參照評估種群狀態(tài),容易導(dǎo)致評估結(jié)果不穩(wěn)定.還有部分種群狀態(tài)評估算法利用種群中所有個(gè)體,導(dǎo)致算法的計(jì)算復(fù)雜度較高.

為了有效評估種群狀態(tài),本文提出基于耦合協(xié)調(diào)種群狀態(tài)評估的差分進(jìn)化算法(DE Algorithm Based on Coupling and Coordination Population State Evaluation, CCPDE),計(jì)算四個(gè)不同等級目標(biāo)函數(shù)值和個(gè)體間距離的耦合協(xié)調(diào)度,評估種群在迭代過程中所處的進(jìn)化狀態(tài).根據(jù)評估結(jié)果將種群狀態(tài)分為搜索、平衡、收斂三種進(jìn)化狀態(tài),并針對不同的進(jìn)化狀態(tài)構(gòu)造相應(yīng)的變異算子池.此外,通過自適應(yīng)Powell方法[19],提升算法的收斂速度.最后,在CEC2017測試函數(shù)集上的數(shù)值實(shí)驗(yàn)驗(yàn)證本文算法的有效性.

1 差分進(jìn)化算法

差分進(jìn)化算法是一種新興的進(jìn)化計(jì)算技術(shù),最初用于解決切比雪夫多項(xiàng)式問題,后來逐漸發(fā)展成為解決復(fù)雜優(yōu)化問題的有效技術(shù).差分進(jìn)化算法是一種基于群體智能的全局隨機(jī)搜索算法,具有控制參數(shù)較少、容易實(shí)現(xiàn)、優(yōu)化效果穩(wěn)健等優(yōu)點(diǎn).在算法迭代過程中,差分進(jìn)化算法特有的記憶能力有助于算法動態(tài)跟蹤當(dāng)前搜索情況,調(diào)整搜索策略.

與其它進(jìn)化算法類似,差分進(jìn)化算法的迭代過程中不需要借助問題的特征信息,適應(yīng)于求解各種類型的復(fù)雜優(yōu)化問題.算法主要通過種群內(nèi)個(gè)體間的差異產(chǎn)生下一代種群.

相比其它進(jìn)化算法,差分進(jìn)化算法基于種群的全局搜索策略、差分變異操作和“一對一”的競爭選擇策略.算法主要由變異、交叉和選擇這三個(gè)基本操作組成.

變異算子是差分進(jìn)化算法的重要組成部分,根據(jù)向量之間的差異提升種群的多樣性.不同的變異算子具有不同的性能.下面列出7種常見的變異算子.

1)DE/rand/1:

2)DE/best/1:

3)DE/best/2:

4)DE/current-to-rand/1:

5)DE/current-to-best/1:

6)DE/current-to-pbest/1[20]:

7)DE/current-to-ci_mbest/1[21]:

其中,D表示函數(shù)維數(shù),jrand表示{1,2,…,D}中的一個(gè)隨機(jī)整數(shù),CR表示交叉概率.

2 基于耦合協(xié)調(diào)種群狀態(tài)評估的

差分進(jìn)化算法

差分進(jìn)化算法是一種群體智能進(jìn)化算法,其“貪婪”的選擇算子有助于算法在迭代過程中不斷進(jìn)行優(yōu)勝劣汰.在迭代過程中,差分進(jìn)化算法通常利用某些個(gè)體或某些群體,如最優(yōu)個(gè)體、最優(yōu)子種群等信息引導(dǎo)種群朝著更好的方向進(jìn)化.然而,這些進(jìn)化方式由于種群狀態(tài)的不同而呈現(xiàn)多樣化.

根據(jù)解的近似最優(yōu)性原理可知,優(yōu)良解之間具有相似結(jié)構(gòu)[22].此原理廣泛應(yīng)用于提升進(jìn)化算法的性能,特別是具有較大山谷結(jié)構(gòu)的優(yōu)化問題.連續(xù)優(yōu)化問題的搜索空間可以大致分為三類:單峰函數(shù)、有大山谷結(jié)構(gòu)的多模態(tài)函數(shù)和無大山谷結(jié)構(gòu)的多模態(tài)函數(shù)[18].這3種不同類型函數(shù)的極值點(diǎn)分布如圖1所示.

由圖1可知,第一個(gè)函數(shù)只有一個(gè)駐點(diǎn),即單峰函數(shù)的極值點(diǎn).因此,采用最優(yōu)個(gè)體作為基向量,有助于提高最優(yōu)解的精度和算法的收斂速度.第二個(gè)函數(shù)為有大山谷結(jié)構(gòu)的多模態(tài)函數(shù),解空間包含多個(gè)結(jié)構(gòu)明顯的局部極值點(diǎn),但總體上看呈現(xiàn)大山谷結(jié)構(gòu).在這種情況下,雖然最優(yōu)個(gè)體仍然能較好地指導(dǎo)種群進(jìn)化,但為了避免種群陷入局部最優(yōu)解,應(yīng)選擇特定的最優(yōu)群體作為基向量較為合適.第三個(gè)函數(shù)為無大山谷結(jié)構(gòu)的多模態(tài)函數(shù),解空間具有多個(gè)局部極值點(diǎn)且分布結(jié)構(gòu)不明顯,這種情況使用全局搜索性能更強(qiáng)的變異算子搜索更有希望的區(qū)域,避免算法陷入局部最優(yōu)解.

(a)單峰函數(shù) (b)有大山谷結(jié)構(gòu)的多模態(tài)函數(shù) (c)無大山谷結(jié)構(gòu)的多模態(tài)函數(shù)

基于上述分析可知,差分進(jìn)化算法的進(jìn)化過程中種群狀態(tài)會動態(tài)變化.本文將上述三種情況分別記為收斂狀態(tài)、平衡狀態(tài)和搜索狀態(tài).根據(jù)“沒有免費(fèi)午餐”定理[23],每個(gè)變異算子都有自己特定的適用范圍.因此,如何針對不同種群狀態(tài)選擇合適的變異算子是一個(gè)極具挑戰(zhàn)的任務(wù).

因此,本文首先利用耦合協(xié)調(diào)度模型度量種群的分布情況,將種群進(jìn)化狀態(tài)分為搜索、平衡、收斂三種情況,再根據(jù)不同的進(jìn)化狀態(tài),分別設(shè)計(jì)不同的變異算子池.

2.1 基于耦合協(xié)調(diào)度模型的種群進(jìn)化狀態(tài)識別

耦合協(xié)調(diào)度模型常用于分析事物的協(xié)調(diào)發(fā)展水平,由耦合度和協(xié)調(diào)度兩部分構(gòu)成.耦合度的概念源于物理學(xué)領(lǐng)域[24],一般用于刻畫多個(gè)指標(biāo)之間相互影響的程度,已廣泛應(yīng)用于社會科學(xué)領(lǐng)域[25-26].協(xié)調(diào)度指耦合相互作用關(guān)系中良性耦合程度的大小,可體現(xiàn)協(xié)調(diào)狀況的好壞.

本文使用耦合協(xié)調(diào)度模型評估目標(biāo)函數(shù)值與個(gè)體距離兩個(gè)指標(biāo)之間的關(guān)系,從而多角度度量當(dāng)前種群進(jìn)化狀態(tài),減少種群進(jìn)化狀態(tài)的誤判.根據(jù)統(tǒng)計(jì)學(xué)中四分位數(shù)概念,本文以上四分位數(shù)、中位數(shù)、下四分位數(shù)3個(gè)分割點(diǎn),將排序后種群分為4個(gè)等級的子種群,再通過耦合協(xié)調(diào)度模型計(jì)算種群的進(jìn)化狀態(tài).具體步驟如下.

1)將種群中所有個(gè)體按目標(biāo)函數(shù)值的優(yōu)劣排序,并根據(jù)排序結(jié)果將種群均分成4個(gè)不同等級的子種群,分別記為POP1、POP2、POP3、POP4.

2)從4個(gè)子種群POP1、POP2、POP3、POP4中分別隨機(jī)抽取4個(gè)個(gè)體X1,i1、X2,i2、X3,i3、X4,i4,它們的目標(biāo)函數(shù)值分別記為f1,i1、f2,i2、f3,i3、f4,i4,計(jì)算個(gè)體兩兩之間目標(biāo)函數(shù)值的差:

Δfk, j=|fk,ik-fj,ij|,

k=1,2,3,4,j=1,2,3,4.

(1)

Δfk, j標(biāo)準(zhǔn)化后得

(2)

3)計(jì)算4個(gè)個(gè)體X1,i1、X2,i2、X3,i3、X4,i4兩兩之間的歐氏距離:

(3)

同樣,dk, j標(biāo)準(zhǔn)化后得

(4)

4)計(jì)算4個(gè)個(gè)體X1,i1、X2,i2、X3,i3、X4,i4兩兩之間的耦合協(xié)調(diào)度:

(5)

Tk, j=β1U1k, j+β2U2k, j,

k=1,2,3,4,j=1,2,3,4.

其中:Ck, j表示第k個(gè)個(gè)體與第j個(gè)個(gè)體的耦合度;Tk, j表示第k個(gè)個(gè)體與第j個(gè)個(gè)體的協(xié)調(diào)度;本文令

5)計(jì)算每個(gè)個(gè)體之間的耦合協(xié)調(diào)度平均值,即種群狀態(tài)評估值:

(6)

并依據(jù)θ將進(jìn)化種群劃分成如下3種狀態(tài).

(1)當(dāng)θ≤1-μ時(shí),說明4個(gè)不同等級個(gè)體之間的總體耦合協(xié)調(diào)度值較低,即4個(gè)個(gè)體分布較分散,此時(shí)種群處于搜索狀態(tài).

(2)當(dāng)1-μ<θ<μ時(shí),說明4個(gè)不同等級個(gè)體之間分布有聚合有分散,此時(shí)種群處于平衡狀態(tài).

(3)當(dāng)θ≥μ時(shí),說明四個(gè)不同等級的個(gè)體處于聚合情況,即目標(biāo)函數(shù)值和距離均較接近,此時(shí)種群處于收斂狀態(tài).

μ為給定的閾值,范圍在[0.5,1)內(nèi).

2.2 變異算子池

在完成種群狀態(tài)的評估之后,需要根據(jù)不同進(jìn)化狀態(tài)設(shè)計(jì)合適的變異算子池,具體設(shè)計(jì)方式如下.

1)搜索狀態(tài)變異算子池

{DE/rand/1,DE/best/2,DE/current-to-rand/1}.

在搜索狀態(tài)下,需要增強(qiáng)算法的全局搜索能力,故應(yīng)選擇搜索性能較優(yōu)的變異算子.在所有的變異算子中,DE/rand/1為較常用的一種.相比DE/rand/1,DE/best/2包含2個(gè)不同的差分向量,具有更好的全局探索能力.DE/current-to-rand/1在解決旋轉(zhuǎn)問題時(shí)具有較好表現(xiàn).因此本文選擇DE/rand/1、DE/best/2、DE/current-to-rand/1這3個(gè)變異算子組成搜索狀態(tài)的變異算子池.

2)平衡狀態(tài)變異算子池

{DE/current-to-pbest/1,DE/current-to-ci_mbest/1}.

在平衡狀態(tài)下,種群個(gè)體聚集和分散情況不明顯,此時(shí)應(yīng)同時(shí)關(guān)注算法的搜索性能和收斂性能.DE/current-to-pbest/1利用表現(xiàn)較優(yōu)的個(gè)體作為目標(biāo)向量,引導(dǎo)種群向優(yōu)秀個(gè)體進(jìn)化,能有效平衡算法搜索和收斂性能.DE/current-to-ci_mbest/1集成多個(gè)優(yōu)秀個(gè)體的信息,以此作為目標(biāo)向量,引導(dǎo)種群向有前途的方向進(jìn)化,是近年來表現(xiàn)較優(yōu)的一種變異算子.因此,本文選擇DE/current-to-pbest/1和DE/current-to-ci_mbest/1兩個(gè)算子組成平衡狀態(tài)的變異算子池.

3)收斂狀態(tài)變異算子池

{DE/best/1,DE/current-to-best/1}.

在收斂狀態(tài)下,種群已聚集在某一局部區(qū)域,此時(shí)應(yīng)該提升算法的收斂速度和解的精度.故本文選擇DE/best/1和DE/current-to-best/1兩個(gè)算子組成收斂狀態(tài)的變異算子池.

2.3 自適應(yīng)Powell方法

Powell共軛梯度下降法[27]是一種直接優(yōu)化方法.從一個(gè)初始點(diǎn)出發(fā),輪流對每個(gè)方向進(jìn)行雙向搜索,直到滿足最優(yōu)性條件.

考慮到差分進(jìn)化算法的局部搜索能力較弱,本文引入自適應(yīng)Powell方法[19],每隔固定代數(shù)G執(zhí)行一次此方法,進(jìn)行局部搜索,提升CCPDE搜索效率.自適應(yīng)Powell方法自適應(yīng)調(diào)節(jié)Powell方法的容忍度ε和步長δ.第j維的步長為:

(7)

其中,NP·10%表示計(jì)算步長解的數(shù)目,xi表示第i個(gè)個(gè)體,xbest表示種群的最優(yōu)解.

自適應(yīng)Powell方法基于迭代次數(shù)自適應(yīng)調(diào)整Powell方法的搜索過程,并通過混合外推技術(shù)結(jié)合逆黃金分割法與拋物線插值方法,從而優(yōu)化種群中個(gè)體.

自適應(yīng)Powell方法偽代碼如算法1所示.

算法1自適應(yīng)Powell方法[19]

給定初始點(diǎn)x0,D維的單位矩陣E,容忍度ε,

搜索步長δ=(δ1,δ2,…,δD)

WHILE |f(x0)-f(xD+1)|<ε未滿足

FORk=1∶D

令g(λ)=f(xk-1+λEk)

結(jié)合逆黃金分割法和逆拋物線插值法,構(gòu)造混合外推法

以δk為初始步長,尋找包含λ2的區(qū)間[λ1,λ3],使得g(λ2)

用Brent′s搜索方法尋找函數(shù)g(λ)在區(qū)間[λ1,λ3]上的最優(yōu)值λ

令xk=xk-1+λEk

FORj=1 toD-1

Ej=Ej+1

END FOR

ED=xD-x0,g(λ)=f(xD+λED)

同樣構(gòu)造λ的區(qū)間[λ1,λ3],用Brent′s搜索方法尋找函數(shù)g(λ)最優(yōu)值λ

xD+1=xD+λDED

END FOR

END WHILE

2.4 本文算法步驟

為了充分利用種群的個(gè)體間距離和目標(biāo)函數(shù)值,有效評估種群進(jìn)化狀態(tài)并選擇合適的變異算子,本文提出基于耦合協(xié)調(diào)度種群狀態(tài)評估的差分進(jìn)化算法(CCPDE),偽代碼如算法2所示.

算法2CCPDE

輸入最大評價(jià)次數(shù)MaxFES,種群大小NP,

狀態(tài)閾值μ,縮放因子F,交叉概率CR,

固定代數(shù)G,容忍度ε

輸出種群中最優(yōu)解

初始化種群POP,Gen=0,FES=NP

WHILEFES

Gen=Gen+1

按目標(biāo)函數(shù)值將種群分為4個(gè)子種群.從子種群中分別隨機(jī)選擇一個(gè)個(gè)體,通過式(1)～式(6)計(jì)算耦合協(xié)調(diào)度,得到種群進(jìn)化狀態(tài)評估值θ

IFθ≤1-μ

{DE/rand/1,DE/current-to-rand/1,DE/best/2}中隨機(jī)選擇一個(gè)變異算子,對當(dāng)前種群POP執(zhí)行變異操作

ELSE IF 1-μ<θ<μ

{DE/current-to-pbest/1,DE/current-to-ci_mbest/1}中隨機(jī)選擇一個(gè)變異算子,對當(dāng)前種群POP執(zhí)行變異操作

ELSE

{DE/best/1,DE/current-to-best/1}中隨機(jī)選擇一個(gè)變異算子,對當(dāng)前種群POP執(zhí)行變異操作

END IF

交叉、選擇、更新參數(shù)

FES=FES+NP

IFmod(Gen,G)=0

根據(jù)式(7)計(jì)算δ

隨機(jī)產(chǎn)生正整數(shù)k∈{1,2,…,NP}

x0=xbest+rand(0,1)·(xbest-xk)

以x0為初始點(diǎn),調(diào)用算法1中的Powell方法, 產(chǎn)生新的解y

利用y代替種群中的最差解

END IF

END WHILE

由算法2可知,CCPDE的步驟具體如下:首先,初始化種群以及設(shè)置各參數(shù).再利用耦合協(xié)調(diào)度評估種群的進(jìn)化狀態(tài).然后,根據(jù)種群所處的進(jìn)化狀態(tài)選擇相應(yīng)的變異算子池.最后,每隔固定代數(shù),利用Powell方法更新種群,直到迭代終止,輸出最優(yōu)解.

3 實(shí)驗(yàn)及結(jié)果分析

3.1 測試函數(shù)與參數(shù)設(shè)置

本文使用CEC2017測試集[28]驗(yàn)證算法性能.CEC2017測試集包含30個(gè)測試函數(shù),F1～F3為單峰函數(shù),F4～F10為多峰函數(shù),F11～F20為混合函數(shù),F21～F30為復(fù)合函數(shù).

本文選擇目標(biāo)函數(shù)值誤差均值和標(biāo)準(zhǔn)差度量算法性能.每個(gè)測試函數(shù)獨(dú)立運(yùn)行25次,以25次目標(biāo)函數(shù)值誤差均值作為最終結(jié)果,目標(biāo)函數(shù)值的最大計(jì)算次數(shù)

MaxFES=10000D,

其中D表示函數(shù)維數(shù).

通過Wilcoxon符號秩檢驗(yàn)和Friedman檢驗(yàn)對數(shù)值實(shí)驗(yàn)結(jié)果進(jìn)行檢驗(yàn)分析,顯著性水平為0.05.對比結(jié)果中優(yōu)于、劣于、相似分別表示CCPDE的數(shù)值結(jié)果顯著優(yōu)于、劣于和相似于對比算法的數(shù)值結(jié)果.

所有算法均在Windows 11,Intel(R) Core(TM) i5-11300H@3.10 GHz,16 GB of RAM環(huán)境上進(jìn)行數(shù)值實(shí)驗(yàn),在matlabR2020b上編碼實(shí)現(xiàn).

3.2 與常見差分進(jìn)化算法對比結(jié)果

為了驗(yàn)證CCPDE的有效性,在CEC2017測試集上進(jìn)行數(shù)值實(shí)驗(yàn).選擇如下對比算法:TSDE[13],EPSDE(DE Algorithm with Ensemble of Parameters and Mutation and Crossover Strategies)[29],FADE(Fitness-Based Adaptive DE)[30],CJADE(Chaotic- Local-Search-Based JADE)[31],IMODE(Improved Multi-operator DE)[32].

對比算法參數(shù)設(shè)置與原文獻(xiàn)一致.CCPDE的F和CR參數(shù)值采用JADE[19]的自適應(yīng)參數(shù)調(diào)整方案,狀態(tài)參數(shù)閾值μ設(shè)置為0.8.

6種算法在CEC2017測試函數(shù)上的Wilcoxon符號秩檢驗(yàn)的對比結(jié)果如表1～表3所示,測試函數(shù)的維度分別為10、30、50.

由表1～表3中結(jié)果可知,CCPDE的整體性能均優(yōu)于其它對比算法,特別是在維數(shù)為30和50的測試函數(shù)上,綜合性能明顯優(yōu)于其它算法.

表1 各算法在10維測試函數(shù)下的誤差均值對比

表2 各算法在30維測試函數(shù)下的誤差均值對比

表3 各算法在50維測試函數(shù)下的誤差均值對比

為了進(jìn)一步分析6種算法的收斂性和魯棒性,以維數(shù)為30的測試函數(shù)為例,繪制6種算法在F1、F5、F13、F21測試函數(shù)的收斂曲線圖和箱線圖,具體如圖2所示.由(a)可以看出:CCPDE的收斂性與CJADE較接近,優(yōu)于其它4種算法;CCPDE的魯棒性與TSDE、EPSDE較接近,優(yōu)于FADE,稍劣于CJADE.由于CJADE傾向于算法的收斂性,因此在單峰函數(shù)上表現(xiàn)較優(yōu),而CCPDE由于使用多個(gè)變異算子,更傾向于提升算法的綜合性能.在(b)中,CCPDE性能明顯優(yōu)于其它5種算法.在(c)中,CCPDE的收斂性能與FADE較接近,另外根據(jù)箱線圖可看出,CCPDE所得最優(yōu)值優(yōu)于其它算法.在(d)中,IMODE的收斂性能最優(yōu),而觀察箱線圖可以看出,CCPDE的魯棒性優(yōu)于FADE、TSDE、EPSDE和IMODE.

綜合上述分析結(jié)果可知,對于各種不同類型的測試函數(shù),CCPDE的收斂性、魯棒性和解的精度等綜合性能都較優(yōu).

(a1)收斂曲線圖 (a2)箱線圖

(b1)收斂曲線圖 (b2)箱線圖

(c1)收斂曲線圖 (c2)箱線圖

(d1)收斂曲線圖 (d2)箱線圖

3.3 與其它進(jìn)化算法對比結(jié)果

為了進(jìn)一步驗(yàn)證CCPDE的有效性,選擇如下對比算法.

1)CSsin[33].改進(jìn)的布谷鳥搜索算法,設(shè)計(jì)線性概率調(diào)整的雙搜索策略,用于平衡布谷鳥搜索算法的搜索性和收斂性,并通過種群規(guī)模減輕計(jì)算負(fù)擔(dān).

2)PPSO(Proactive Particles in Swarm Optimi-zation)[34].自動調(diào)節(jié)性能的粒子群優(yōu)化算法,利用模糊邏輯,動態(tài)確定慣性權(quán)重、認(rèn)知因素和社會因素的最佳設(shè)置.

3)CGO(Chaos Game Optimization)[35].新型元啟發(fā)式算法.

4)AGBSO[36].基于替代搜索模式的頭腦風(fēng)暴算法,基于網(wǎng)格搜索,將搜索空間劃分為更小的搜索空間進(jìn)行算法搜索.

5)CMA-ES(Evolutionary Optimization Strategy Based on the Derandomized Evolution Strategy with Covariance Matrix Adaption)[37].基于去隨機(jī)化進(jìn)化策略和協(xié)方差矩陣適應(yīng)的新型進(jìn)化算法.

實(shí)驗(yàn)中這5種算法的參數(shù)設(shè)置與其原文獻(xiàn)相同,在CEC2017測試集上進(jìn)行對比分析.

各算法在30個(gè)測試函數(shù)上求解的目標(biāo)函數(shù)誤差均值和標(biāo)準(zhǔn)差如表4所示,表中黑體數(shù)字表示最優(yōu)值.

表4 6種進(jìn)化算法在30維測試函數(shù)上的誤差均值對比

觀察表4中結(jié)果可知,對于單峰函數(shù),CMA-ES表現(xiàn)最優(yōu),CCPDE次優(yōu).對于多峰函數(shù),CCPDE表現(xiàn)與AGBSO接近,優(yōu)于其它4種進(jìn)化算法.對于混合函數(shù),CCPDE的數(shù)值結(jié)果明顯優(yōu)于其它5種進(jìn)化算法.對于復(fù)合函數(shù),CSsin在F21、F23～F27測試函數(shù)上的數(shù)值結(jié)果最優(yōu).CCPDE在F29、F30測試函數(shù)上的結(jié)果最優(yōu).

根據(jù)上述分析,在CEC-2017測試集的30個(gè)測試函數(shù)上,CCPDE總體性能優(yōu)于5種進(jìn)化算法.

進(jìn)一步給出6種進(jìn)化算法誤差均值的Friedman秩和排名,具體如表5所示.由表可知,CCPDE的Fridman秩值為1.97,明顯優(yōu)于其它算法.秩排名第二和第三的分別是AGBSO與CSsin,Fridman秩值為3.36和3.47,較接近.秩排名第六位的是PPSO,秩值為4.38,明顯差于其它算法.由此可知,相比其它進(jìn)化算法,CCPDE具有一定優(yōu)勢.

3.4 與其它種群狀態(tài)評估方法對比結(jié)果

為了進(jìn)一步驗(yàn)證耦合協(xié)調(diào)度種群評估方法的有效性,本節(jié)使用DEMS[14]、ADDE[17]、DEET[18]替換CCPDE中的耦合協(xié)調(diào)度評估方法,在30維CEC2017 測試函數(shù)上開展數(shù)值實(shí)驗(yàn),誤差均值和標(biāo)準(zhǔn)差如表6所示,表中黑體數(shù)字表示最優(yōu)值.

表6 CCPDE與其它種群狀態(tài)評估方法的誤差均值對比

實(shí)驗(yàn)中DEET-CCPDE表示在狀態(tài)評估階段使用DEET的評估方法,其余算法內(nèi)容與CCPDE一致.同樣,ADDE-CCPDE、DEMS-CCPDE為ADDE和DEMS的評估方法與CCPDE結(jié)合形成的算法.由表6中結(jié)果可知,耦合協(xié)調(diào)度種群狀態(tài)評估方法能提升算法的性能.

為了進(jìn)一步衡量狀態(tài)評估方法的優(yōu)劣,給出4種算法的Friedman秩排名,具體如表7所示.由表可知,CCPDE的秩為1.70,表現(xiàn)最優(yōu),排名第二的是DEET-CCPDE,其次是DEMS-CCPDE和ADDE-CCPDE.

表7 CCPDE和3種種群狀態(tài)評估方法的Friedman檢驗(yàn)結(jié)果

ADDE的評估方法僅基于目標(biāo)函數(shù)值排名最優(yōu)和中位數(shù)這兩個(gè)特定個(gè)體的距離,容易出現(xiàn)誤判.DEMS的評估方法計(jì)算種群中每個(gè)個(gè)體兩兩之間距離的平均值,評估效果略優(yōu)于ADDE.DEET同時(shí)考慮種群分布、目標(biāo)函數(shù)值的影響,但是僅以最優(yōu)解作為參照,會出現(xiàn)評估不準(zhǔn)確的情況.相比而言,耦合協(xié)調(diào)度評估方法雖然只計(jì)算四個(gè)個(gè)體之間耦合情況,但四個(gè)個(gè)體分別來自于不同等級的子種群,取樣均勻,且耦合協(xié)調(diào)度模型能夠綜合考慮種群個(gè)體的分布與目標(biāo)函數(shù)值.

綜合上述結(jié)果可知,在CCPDE中,基于耦合協(xié)調(diào)度的種群評估方法優(yōu)于其它3種種群狀態(tài)評估方法,4種種群狀態(tài)評估方法的數(shù)值結(jié)果也進(jìn)一步驗(yàn)證此結(jié)果.

3.5 參數(shù)敏感性分析

為了分析狀態(tài)參數(shù)閾值μ對CCPDE性能的影響,本節(jié)主要探討μ對進(jìn)化狀態(tài)劃分的影響.為了選擇CCPDE的最優(yōu)狀態(tài)參數(shù)閾值,本節(jié)將μ固定在[0.5, 0.9]區(qū)間,步長設(shè)置為0.1,算法獨(dú)立運(yùn)行25次,測試函數(shù)維數(shù)設(shè)為10、20、30.5個(gè)不同閾值相應(yīng)算法的Friedman檢驗(yàn)結(jié)果如表8所示,表中黑體數(shù)字表示最優(yōu)值.

由表8結(jié)果分析可知:在測試函數(shù)維數(shù)為10、30,μ=0.8時(shí),均值排名最優(yōu);在測試函數(shù)維數(shù)為50,μ=0.7時(shí),均值排名最優(yōu),秩排名為2.12.由此可知,當(dāng)μ=0.8時(shí),算法的總體性能最佳.

表8 不同維度下μ值改變后的Friedman檢驗(yàn)結(jié)果

4 結(jié) 束 語

差分進(jìn)化算法在迭代過程中的種群狀態(tài)是動態(tài)變化的,不同的種群狀態(tài)對于變異算子的要求不同.如何有效評估種群狀態(tài),并選擇合適的變異算子,是本文研究的重點(diǎn).本文提出基于耦合協(xié)調(diào)種群狀態(tài)評估的差分進(jìn)化算法(CCPDE).首先,從不同等級的子種群中隨機(jī)選取四個(gè)個(gè)體,通過耦合協(xié)調(diào)度計(jì)算不同等級目標(biāo)函數(shù)值和不同距離個(gè)體的聚散程度,評估當(dāng)前種群所屬狀態(tài),并根據(jù)評估狀態(tài)將種群進(jìn)化分為搜索、平衡和收斂三種狀態(tài).然后,對于不同的進(jìn)化狀態(tài),從相應(yīng)的變異算子池選擇對應(yīng)的變異算子進(jìn)行種群迭代.最后,在迭代過程中,利用自適應(yīng)Powell方法,在固定代數(shù)進(jìn)行局部搜索,加快算法收斂速度.為了驗(yàn)證本文算法的有效性,基于CEC2017測試函數(shù)集,先后進(jìn)行與改進(jìn)差分進(jìn)化算法、其它進(jìn)化算法、不同種群狀態(tài)評估方法的對比數(shù)值實(shí)驗(yàn),以及參數(shù)敏感性分析實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明:1)相比其它種群狀態(tài)評估方法,CCPDE的基于耦合協(xié)調(diào)度種群評估方法充分考慮種群個(gè)體分布和目標(biāo)函數(shù)值關(guān)聯(lián)關(guān)系,性能優(yōu)于其它三種種群狀態(tài)評估方法;2)當(dāng)CCPDE的狀態(tài)參數(shù)閾值μ設(shè)置為0.8時(shí),算法總體性能較優(yōu);3)相比改進(jìn)差分進(jìn)化算法和進(jìn)化算法,CCPDE的魯棒性、收斂性較優(yōu),能夠有效處理不同類型問題的函數(shù),存在顯著優(yōu)勢.綜合所有數(shù)值實(shí)驗(yàn)可知,本文算法是一種有效的算法.今后考慮將CCPDE融入約束差分優(yōu)化、多目標(biāo)優(yōu)化等復(fù)雜實(shí)際問題中.