基于耦合協(xié)調(diào)種群狀態(tài)評估的差分進化算法

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

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

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

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

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

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

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

1 差分進化算法

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

與其它進化算法類似,差分進化算法的迭代過程中不需要借助問題的特征信息,適應于求解各種類型的復雜優(yōu)化問題.算法主要通過種群內(nèi)個體間的差異產(chǎ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}中的一個隨機整數(shù),CR表示交叉概率.

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

差分進化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

Δfk, j標準化后得

(2)

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

(3)

同樣,dk, j標準化后得

(4)

4)計算4個個體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個個體與第j個個體的耦合度;Tk, j表示第k個個體與第j個個體的協(xié)調(diào)度;本文令

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

(6)

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

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

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

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

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

2.2 變異算子池

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

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

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

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

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

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

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

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

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

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

2.3 自適應Powell方法

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

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

(7)

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

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

自適應Powell方法偽代碼如算法1所示.

算法1自適應Powell方法[19]

給定初始點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 本文算法步驟

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

算法2CCPDE

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

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

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

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

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

WHILEFES

Gen=Gen+1

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

IFθ≤1-μ

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

ELSE IF 1-μ<θ<μ

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

ELSE

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

END IF

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

FES=FES+NP

IFmod(Gen,G)=0

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

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

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

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

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

END IF

END WHILE

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

3 實驗及結(jié)果分析

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

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

本文選擇目標函數(shù)值誤差均值和標準差度量算法性能.每個測試函數(shù)獨立運行25次,以25次目標函數(shù)值誤差均值作為最終結(jié)果,目標函數(shù)值的最大計算次數(shù)

MaxFES=10000D,

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

通過Wilcoxon符號秩檢驗和Friedman檢驗對數(shù)值實驗結(jié)果進行檢驗分析,顯著性水平為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)境上進行數(shù)值實驗,在matlabR2020b上編碼實現(xiàn).

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

為了驗證CCPDE的有效性,在CEC2017測試集上進行數(shù)值實驗.選擇如下對比算法: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ù)設置與原文獻一致.CCPDE的F和CR參數(shù)值采用JADE[19]的自適應參數(shù)調(diào)整方案,狀態(tài)參數(shù)閾值μ設置為0.8.

6種算法在CEC2017測試函數(shù)上的Wilcoxon符號秩檢驗的對比結(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ù)下的誤差均值對比

為了進一步分析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由于使用多個變異算子,更傾向于提升算法的綜合性能.在(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 與其它進化算法對比結(jié)果

為了進一步驗證CCPDE的有效性,選擇如下對比算法.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了進一步衡量狀態(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檢驗結(jié)果

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

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

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

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

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

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

4 結(jié) 束 語

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