求解大規(guī)模優(yōu)化問(wèn)題的新型協(xié)同差分進(jìn)化算法

董小剛，鄧長(zhǎng)壽，譚毓澄，彭 虎，吳志健

(1.九江學(xué)院 信息科學(xué)與技術(shù)學(xué)院，江西 九江 332005； 2. 九江學(xué)院 理學(xué)院，江西 九江 332005；3.軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)), 武漢 430072)

求解大規(guī)模優(yōu)化問(wèn)題的新型協(xié)同差分進(jìn)化算法

董小剛1，鄧長(zhǎng)壽1*，譚毓澄2，彭 虎1，吳志健3

(1.九江學(xué)院 信息科學(xué)與技術(shù)學(xué)院，江西 九江 332005； 2. 九江學(xué)院 理學(xué)院，江西 九江 332005；3.軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)), 武漢 430072)

基于分而治之的策略，研究求解大規(guī)模優(yōu)化問(wèn)題的新方法。首先，基于加性可分性原理提出一種改進(jìn)的變量分組方法，該方法以隨機(jī)取點(diǎn)的方式，成對(duì)檢測(cè)所有變量之間的相關(guān)性；同時(shí)，充分利用相關(guān)性學(xué)習(xí)的信息，對(duì)可分變量組進(jìn)行再次降維；其次，引入改進(jìn)的差分進(jìn)化算法作為新型子問(wèn)題優(yōu)化器，增強(qiáng)了子空間的尋優(yōu)性能；最后，將兩項(xiàng)改進(jìn)引入到協(xié)同進(jìn)化框架構(gòu)建DECC-NDG-CUDE算法。在10個(gè)選定的大規(guī)模優(yōu)化問(wèn)題上進(jìn)行分組和優(yōu)化兩組仿真實(shí)驗(yàn)，分組實(shí)驗(yàn)結(jié)果表明新的分組方法能有效識(shí)別變量的相關(guān)性，是有效的變量分組方法；優(yōu)化實(shí)驗(yàn)表明，DECC-NDG-CUDE算法對(duì)10個(gè)問(wèn)題的求解相對(duì)于兩種知名算法DECC-DG、DECCG在性能上具備整體優(yōu)勢(shì)。

大規(guī)模優(yōu)化；變量分組；加性可分；優(yōu)化器；協(xié)同進(jìn)化

0 引言

工業(yè)界和學(xué)術(shù)界各類(lèi)數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，使得大規(guī)模數(shù)據(jù)處理技術(shù)成為各領(lǐng)域研究的熱點(diǎn)， 數(shù)據(jù)優(yōu)化領(lǐng)域也進(jìn)入了大規(guī)模時(shí)代。大規(guī)模黑盒優(yōu)化問(wèn)題高度復(fù)雜，無(wú)法采用傳統(tǒng)的數(shù)學(xué)方法有效求解，其中決策變量的大規(guī)模性是構(gòu)成求解難度的關(guān)鍵因素。進(jìn)化計(jì)算是一類(lèi)求解復(fù)雜優(yōu)化問(wèn)題的高效方法，過(guò)去二十多年的研究和應(yīng)用表明，在小規(guī)模優(yōu)化問(wèn)題上進(jìn)化算法取得了理想求解結(jié)果; 然而，當(dāng)優(yōu)化問(wèn)題的規(guī)模迅速增大時(shí)，進(jìn)化計(jì)算面臨嚴(yán)重的挑戰(zhàn)，求解性能惡化嚴(yán)重。如何利用進(jìn)化計(jì)算方法，求解大規(guī)模優(yōu)化問(wèn)題，是目前科學(xué)和工程應(yīng)用領(lǐng)域的研究熱點(diǎn)。

1 相關(guān)工作

當(dāng)前，針對(duì)大規(guī)模優(yōu)化問(wèn)題的求解，學(xué)者們進(jìn)行了多方面的研究工作，這些工作可歸納為以下兩個(gè)方面。

一方面，基于先進(jìn)的進(jìn)化計(jì)算算法[1-3]進(jìn)行改進(jìn)，開(kāi)發(fā)可靠性、精確性更高的進(jìn)化計(jì)算算法(新的進(jìn)化算子、混合進(jìn)化模式、增強(qiáng)局部搜索、代理模型等)，從而提高大規(guī)模優(yōu)化問(wèn)題的求解性能。如：文獻(xiàn)[4]的研究證明將進(jìn)化計(jì)算與其他技術(shù)進(jìn)行混合，可以有效提高優(yōu)化算法求解大規(guī)模問(wèn)題的性能。文獻(xiàn)[5]將高效的局部搜索技術(shù)與進(jìn)化算法結(jié)合，提出一種文化基因算法(Memetic Algorithm, MA)，該算法在一定程度上改善了復(fù)雜的組合優(yōu)化問(wèn)題的求解性能。文獻(xiàn)[6]將正交交叉和反向?qū)W習(xí)結(jié)合，提出一種反向正交交叉的差分進(jìn)化算法，實(shí)驗(yàn)結(jié)果表明，該算法對(duì)大規(guī)模優(yōu)化問(wèn)題的求解性能相對(duì)于其他幾種知名的差分進(jìn)化算法有明顯的提升。文獻(xiàn)[7]利用改進(jìn)的精英學(xué)習(xí)進(jìn)化算子和島模型兩種機(jī)制，對(duì)差分進(jìn)化算法的優(yōu)化性能進(jìn)行改進(jìn)，并將其部署到分布式平臺(tái)Hadoop上，實(shí)驗(yàn)結(jié)果證明該方法可有效提高差分進(jìn)化算法求解大規(guī)模優(yōu)化問(wèn)題的性能，同時(shí)具有較好的加速比。文獻(xiàn)[8]提出一種代理模型輔助的群智能優(yōu)化算法；該算法采用代理模型輔助的粒子群算法及基于粒子群的社會(huì)學(xué)習(xí)算法的協(xié)同優(yōu)化來(lái)求解高維優(yōu)化問(wèn)題；兩組不同維度的仿真實(shí)驗(yàn)結(jié)果表明，該方法所求得的解質(zhì)量高于其他比較算法。

另一方面，引入?yún)f(xié)同進(jìn)化思想，提高求解大規(guī)模優(yōu)化問(wèn)題的性能。協(xié)同進(jìn)化思想的引入可分為兩類(lèi)。第一類(lèi)，基于多個(gè)種群的協(xié)同進(jìn)化。如文獻(xiàn)[9]針對(duì)大規(guī)模數(shù)據(jù)優(yōu)化問(wèn)題，提出一種并行差分進(jìn)化算法，該算法將協(xié)同進(jìn)化思想引入到差分進(jìn)化算法中，利用多個(gè)差分進(jìn)化算法隨機(jī)分解大規(guī)模優(yōu)化問(wèn)題，然后進(jìn)行并行求解。該方法在大規(guī)模非線性函數(shù)優(yōu)化問(wèn)題的求解上取得了更高的精度和效率。文獻(xiàn)[10]提出一種隨機(jī)擴(kuò)散搜索的協(xié)同差分進(jìn)化算法，該算法利用隨機(jī)擴(kuò)散搜索策略將種群劃分為成功和失敗兩個(gè)種群，利用不同進(jìn)化策略并行協(xié)同進(jìn)化，定期對(duì)兩個(gè)種群進(jìn)行信息交互。仿真實(shí)驗(yàn)表明該算法較基本差分進(jìn)化和粒子群算法具有收斂速率和精度上的優(yōu)勢(shì)。第二類(lèi)，基于分而治之的策略將大規(guī)模優(yōu)化問(wèn)題分解為多個(gè)子問(wèn)題進(jìn)行協(xié)同優(yōu)化。如：文獻(xiàn)[11]針對(duì)不可分問(wèn)題提出一種決策變量隨機(jī)分組(Random Grouping)的方法，該方法不考慮變量之間依賴(lài)關(guān)系，隨機(jī)地劃分變量分組。并通過(guò)多個(gè)輪次的進(jìn)化，提高了相關(guān)變量進(jìn)入同一分組的概率，一定程度上提高了大規(guī)模優(yōu)化問(wèn)題的求解效果。文獻(xiàn)[12]針對(duì)固定大小的分組，深入分析了種群大小和分組大小對(duì)優(yōu)化器求解性能的影響。在此基礎(chǔ)上提出將部分評(píng)價(jià)資源用于對(duì)二者進(jìn)行自適應(yīng)調(diào)整的協(xié)同進(jìn)化方法。實(shí)驗(yàn)表明該方法在分組大小固定的情況下，相對(duì)于其他CC框架具備一定的求解優(yōu)勢(shì)。文獻(xiàn)[13]針對(duì)應(yīng)用分而治之策略時(shí)子問(wèn)題與原問(wèn)題之間的維度匹配困難，提出一種自評(píng)價(jià)進(jìn)化(Self-Evaluation Evolution, SEE)方法。SEE采用元模型技術(shù)來(lái)解決由于維度匹配困難所造成的高計(jì)算消耗問(wèn)題，實(shí)驗(yàn)結(jié)果表明，SEE相對(duì)于四種代表性優(yōu)化算法，在大規(guī)模優(yōu)化問(wèn)題的求解表現(xiàn)更為突出。文獻(xiàn)[14]提出一種新的兩階段求解方法：第一階段，檢測(cè)搜索空間中變量之間的依賴(lài)關(guān)系，并據(jù)此形成變量的分組；第二階段，依據(jù)經(jīng)典的協(xié)同進(jìn)化框架進(jìn)行優(yōu)化求解。文獻(xiàn)[15]提出一種自動(dòng)分組(Differential Grouping，DG)方法，能較為準(zhǔn)確地發(fā)現(xiàn)決策變量之間的交互關(guān)系，并據(jù)此而形成相關(guān)變量的分組，一定程度上降低了各子分組之間的依賴(lài)關(guān)系，促進(jìn)了大規(guī)模優(yōu)化題求解性能的提升。

本文工作主要包括三方面：1)在DG算法的基礎(chǔ)上，提出一種新的變量分組(New Different Grouping, NDG)方法,進(jìn)一步改善了基于加性可分原理進(jìn)行變量分組的準(zhǔn)確性；2)利用前期研究提出的CUDE(enhancing Differential Evolution with Commensal learning and Uniform local search)算法[16]設(shè)計(jì)子問(wèn)題優(yōu)化器，增強(qiáng)算法對(duì)子空間的尋優(yōu)性能; 3)將以上改進(jìn)引入?yún)f(xié)同進(jìn)化框架，構(gòu)建求解大規(guī)模優(yōu)化問(wèn)題的新型協(xié)同差分進(jìn)化算法DECC-NDG-CUDE(Cooperative differential evolution with NDG and CUDE)算法，并在選定的測(cè)試集上進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，DECC-NDG-CUDE能進(jìn)一步提高大規(guī)模優(yōu)化問(wèn)題的求解性能，是一種有效的算法。

2 新型變量分組策略

2.1 函數(shù)的加性可分性原理

大規(guī)模黑盒優(yōu)化問(wèn)題由于其數(shù)學(xué)模型未知和不可獲取，傳統(tǒng)的數(shù)學(xué)方法，如求導(dǎo)法、單純形法、梯度法等不再適用。針對(duì)這一情況，當(dāng)前廣泛采用的方法是通過(guò)對(duì)決策變量的分組，將問(wèn)題分解成多個(gè)低維度的子問(wèn)題來(lái)進(jìn)行各個(gè)擊破的獨(dú)立求解。然而，當(dāng)決策變量之間存在復(fù)雜的相互依賴(lài)關(guān)系時(shí)，盲目分組顯然無(wú)法達(dá)到有效求解的目的。

基于加性可分性原理對(duì)變量之間的依賴(lài)關(guān)系進(jìn)行先期學(xué)習(xí)，然后據(jù)此進(jìn)行變量分組，可以最大限度地降低子問(wèn)題之間的依賴(lài)關(guān)系，對(duì)提高求解性能有很大的促進(jìn)作用。

定義1 如果函數(shù)f(x) 滿足如下條件：

(1)

則函數(shù)f(x)為加性可分解函數(shù)，其中x=(x1,x2,…,xm)，xi為相互排斥的決策變量。

以二維函數(shù)f(x,y)為例，根據(jù)加性可分函數(shù)的定義可知：

若f(x,y)=f1(x)+f2(y)，顯然可得出f(x+Δx,y)-f(x,y)與y的無(wú)關(guān)。換句話說(shuō)就是：f(x1,y)-f(x2,y)與y無(wú)關(guān)，即存在如下等式：

f(x1,y1)-f(x2,y1)=f(x1,y2)-f(x2,y2)

以此類(lèi)推可得出如下推論：

n維函數(shù)f(x1,x2,…,xn)，xi與xj之間加性可分，則存在如下等式：

f|xi=p,xj=t1-f|xi=q,xj=t1=f|xi=p,xj=t2-f|xi=q,xj=t2

(2)

其中i≠j,p≠q,t1≠t2；反之，若：

f|xi=p,xj=t1-f|xi=q,xj=t1≠f|xi=p,xj=t2-f|xi=q,xj=t2

(3)

則xi與xj相互依賴(lài)，不可分。

式(2)和式(3)由加性可分性函數(shù)的定義導(dǎo)出，是函數(shù)加性可分的性質(zhì)。

文獻(xiàn)[15]利用式(2)構(gòu)建了大規(guī)模優(yōu)化問(wèn)題自動(dòng)分組(DG)算法。DG算法在可行域中選取4個(gè)測(cè)試點(diǎn)(邊界和中心)，計(jì)算式(2)左右兩側(cè)的兩個(gè)差值Δ1和Δ2，通過(guò)比較表達(dá)式│Δ1-Δ2│ 的值和設(shè)定閾值的關(guān)系來(lái)判定決策變量之間是否存在依賴(lài)關(guān)系，進(jìn)而形成變量分組。DG算法合理利用了函數(shù)加性可分的性質(zhì)，能夠較為準(zhǔn)確地實(shí)現(xiàn)決策變量的分組。

然而，DG算法的實(shí)現(xiàn)仍然存在以下幾個(gè)方面的不足：

1)采用可行域的邊界作為測(cè)試點(diǎn)；然而，邊界本身具有特殊性，不能反映一般性。例如式(4)所示的函數(shù):

x1*xn*(xn2-25)*n

(4)

設(shè)式(4)所示函數(shù)的定義域?yàn)閇-5，5]。假設(shè)n=4，則f(x)為4維函數(shù)。依據(jù)DG算法，用定義域的邊界構(gòu)造4個(gè)點(diǎn)，檢測(cè)第一維和第二維的相關(guān)性，具體過(guò)程如下：

設(shè)p1=[-5,-5,-5,-5],p2=p1，p2(1)=5。由此，求Δ1為：

Δ1=f(p1)-f(p2)

(5)

設(shè)p3=p1,p4=p2,p3(2)=0,p4(2)=0,由此，求Δ2為：

Δ2=f(p3)-f(p4)

(6)

|Δ1-Δ2|

(7)

則式(7)的值必定為0。據(jù)此，DG算法將第一維和第二維識(shí)別為不相關(guān)變量。此結(jié)論顯然與函數(shù)本身的性質(zhì)不符。

2)排除已經(jīng)形成分組的所有相關(guān)變量，導(dǎo)致依賴(lài)關(guān)系檢測(cè)不全面，影響了分組的成功率。

3)沒(méi)有充分地利用分組學(xué)習(xí)階段所獲得的信息。比如將所有可分變量歸為一個(gè)分組，當(dāng)可分變量數(shù)量比較大時(shí)，所形成的分組規(guī)模較大，無(wú)法達(dá)到有效降維的目的，并且浪費(fèi)了較多的評(píng)價(jià)資源。

2.2 新型分組算法

為了進(jìn)一步提高變量分組的精度，提高大規(guī)模優(yōu)化問(wèn)題的求解性能。針對(duì)DG算法3個(gè)不足進(jìn)行改進(jìn)，提出一種新的變量分組(NDG)算法。

首先，NDG算法避免采用可行域的邊界作為測(cè)試點(diǎn)，而以邊界附近的隨機(jī)值為測(cè)試點(diǎn)。

其次，NDG算法采用遍歷形式對(duì)變量相關(guān)性進(jìn)行檢測(cè)，也就說(shuō)并不因?yàn)樾纬煞纸M而排除某個(gè)變量的相關(guān)性檢測(cè)，從而避免遺漏。

最后，為對(duì)相關(guān)性學(xué)習(xí)的結(jié)果進(jìn)行充分利用，尤其是針對(duì)學(xué)習(xí)后判定為可分的變量組，若其大小仍然較大，則對(duì)其進(jìn)行二次分組，進(jìn)一步降低維度。

NDG算法的基本流程如下：

算法1 NDG(func,lbs,ubs,eps)

1)

設(shè)置Dims={1,2,…,1 000},定義可分組變Seps，相關(guān)分組變量Cgroups，中間集合變量group,Agroups，Bgroups；初始化上下界變量lb，ub，評(píng)價(jià)次數(shù)變量FES=0；

2)

while (Dims不為空)

3)

group=[Dims(1)];

4)

定義兩個(gè)1 000維向量p1和p2,各維在下界附近隨機(jī)取值;

5)

將向量p2的第Dims(1)維設(shè)置為上屆附近的隨機(jī)值；

6)

Δ1=f(p1)-f(p2)，F(xiàn)ES=FES+2

7)

Fori=2:length(Dims)

8)

p3=p1;

9)

p4=p2;

10)

p3(i)=p4(i)=(lb+ub)/2

11)

Δ2=f(p3)-f(p4)，F(xiàn)ES=FES+2;

12)

if abs(Δ1-Δ2)>eps

group=[group,Dims(i)]

13)

end if

14)

end For循環(huán)

15)

if length(group)==1

Seps=[Seps,group];

16)

Else

Agroups={Agroups{1:end},group}

group_u=union(group_u,group)

17)

end if

18)

if (length(Dims)>0)

設(shè)置Dims(1)=[]

19)

end if

20) end while循環(huán)

21) 合并Agroup中包含相同元素的相關(guān)組，將結(jié)果賦值給Cgroup

22)

返回Seps，Cgroups;

其中，第4)和第5)步的隨機(jī)值NDG采用上界或下界附近的隨機(jī)值，有別于DG算法直接取上屆或者下界。 第12)步eps為閾值，當(dāng)小于該閾值時(shí)，即認(rèn)為兩個(gè)差值相等。大于該閾值時(shí)，認(rèn)為兩個(gè)差值不相等。并以此判斷變量之間的相關(guān)性。第22)步返回的可分組，在讀取分組結(jié)果時(shí)進(jìn)行判斷，若仍然較大，則進(jìn)行二次分組，按順序每50個(gè)構(gòu)成一個(gè)新的分組，最后一組為所有剩余變量。

3 基于改進(jìn)差分進(jìn)化算法的子問(wèn)題優(yōu)化器

高效的優(yōu)化器是提高大規(guī)模優(yōu)化問(wèn)題求解性能的有力工具。2016年文獻(xiàn)[16]提出一種改進(jìn)的差分進(jìn)化算法(CUDE)，實(shí)驗(yàn)表明CUDE尋優(yōu)能力突出。為進(jìn)一步提高求解大規(guī)模優(yōu)化問(wèn)題的性能，本文將CUDE作為子問(wèn)題優(yōu)化器引入到引入框架中。

3.1 改進(jìn)的進(jìn)化策略和參數(shù)調(diào)整方案

縮放因子F和交叉概率CR是影響DE算法性能的兩個(gè)核心參數(shù)。關(guān)于DE參數(shù)的大量研究已經(jīng)證明固定的參數(shù)設(shè)置并非提高算法性能的最好設(shè)置。一般來(lái)說(shuō)，較大的F和CR適合用于進(jìn)化初期提升算法的全局搜索性能。而較小的F和CR適合在進(jìn)化后期加強(qiáng)算法的局部開(kāi)采性能，并加速收斂；然而，簡(jiǎn)單的前大后小的設(shè)置對(duì)提高算法的性能意義不大。

CUDE采用雙邊高斯分布進(jìn)行F和CR的動(dòng)態(tài)自適應(yīng)更新。具體設(shè)置依據(jù)式(8)和(9)進(jìn)行:

(8)

(9)

其中:N代表高斯函數(shù)，Slower和Supper代表雙邊參數(shù)設(shè)置的上、下界。

另外，為避免單一進(jìn)化策略對(duì)問(wèn)題的依賴(lài)性，CUDE選擇DE/rand/1、DE/best/1、DE/target-to-rand/1三種進(jìn)化策略與雙邊高斯參數(shù)設(shè)置進(jìn)行組合使用。

對(duì)雙邊高斯參數(shù)設(shè)置和三種進(jìn)化策略，進(jìn)行兩兩組合，共構(gòu)造6種進(jìn)化方案。然后，在每一代進(jìn)化中CUDE采用輪盤(pán)賭的方式為每一個(gè)個(gè)體從6種方案中選擇一個(gè)進(jìn)行進(jìn)化。在每一代進(jìn)化之后，記錄每個(gè)方案對(duì)種群中每個(gè)個(gè)體的成功更新次數(shù)Ssch,i和嘗試更新次數(shù)Tsch,i，并進(jìn)行相除得到更新成功率參數(shù)SRsch,i，SRsch,i的計(jì)算公式如式(10)所示：

SRsch,i=Ssch,i/Tsch,i

(10)

依據(jù)SRsch,i，構(gòu)建學(xué)習(xí)字典二維表。在下一代中依據(jù)學(xué)習(xí)字典，采用輪盤(pán)賭的方式選擇每個(gè)個(gè)體的進(jìn)化方案。

3.2 基于均勻設(shè)計(jì)的局部搜索

采用基于均勻設(shè)計(jì)(Uniform Local Search，ULS)的局部搜索技術(shù)，CUDE有效地平衡了DE算法的勘探和開(kāi)采能力。均勻設(shè)計(jì)是一種高質(zhì)量的實(shí)驗(yàn)設(shè)計(jì)方法，其基礎(chǔ)理論為數(shù)論中的一致分布理論，最早由Wang等[17]和Fang等[18]提出。與同為實(shí)驗(yàn)設(shè)計(jì)方法的正交設(shè)計(jì)相比，均勻設(shè)計(jì)的優(yōu)勢(shì)是實(shí)驗(yàn)次數(shù)更少，這在以個(gè)體適應(yīng)度為評(píng)價(jià)體的進(jìn)化算法中尤為重要。近年來(lái)已有不少學(xué)者將均勻設(shè)計(jì)引入到進(jìn)化計(jì)算算法中，如文獻(xiàn)[19]在利用均勻設(shè)計(jì)來(lái)進(jìn)行算法種群的初始化。

均勻設(shè)計(jì)依據(jù)均勻設(shè)計(jì)表來(lái)安排實(shí)驗(yàn)方案。一個(gè)均勻設(shè)計(jì)表可表示為Un(qS),其中n為表的行數(shù)，代表要安排的實(shí)驗(yàn)次數(shù)；S為列數(shù)，代表要考慮的因素?cái)?shù)；q代表每個(gè)因素要考慮的水平數(shù)。CUDE所采用的ULS局部搜索方法，選擇均勻設(shè)計(jì)表U6(66)進(jìn)行實(shí)驗(yàn)方案安排。關(guān)于U6(66)的構(gòu)造參考文獻(xiàn)[16]。

表1 均勻設(shè)計(jì)表 U6(66)Tab. 1 Uniform design table U6(66)

CUDE采用以上兩個(gè)方面的改進(jìn)提高了算法的尋優(yōu)能力，算法詳細(xì)流程及參數(shù)見(jiàn)文獻(xiàn)[16]。

ULS在每一代進(jìn)化中隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行局部搜索。以二維空間為例，假設(shè)所選取的兩個(gè)個(gè)體為A(x1,y2)和B(x2,y2)。則ULS首先會(huì)將A和B構(gòu)成的二維子空間的每一維均勻地分解成6個(gè)部分，每個(gè)部分看作一個(gè)因素。然后，依據(jù)均勻設(shè)計(jì)表U6(66)組合每個(gè)水平上的各個(gè)因素，構(gòu)造出6個(gè)實(shí)驗(yàn)體。最后，對(duì)6個(gè)實(shí)驗(yàn)個(gè)體進(jìn)行評(píng)價(jià)，選擇最優(yōu)的替換A和B的一個(gè)完成局部搜索。ULS的詳細(xì)流程如算法2。需說(shuō)明的是ULS 在進(jìn)化的每一代中僅執(zhí)行一次。

算法2 ULS算法。

1)輸入：種群P，評(píng)價(jià)次數(shù)計(jì)數(shù)器FEs。

2)從P中隨機(jī)選擇兩個(gè)個(gè)體xi,g和xj,g。

3)根據(jù)xi,g和xj,g，利用U6(66)進(jìn)行均勻，產(chǎn)生6個(gè)實(shí)驗(yàn)個(gè)體y1,y2,…,y6。

4)評(píng)價(jià)6個(gè)實(shí)驗(yàn)個(gè)體。

5)選取適應(yīng)度最高的一個(gè)實(shí)驗(yàn)個(gè)體O。

6)用O替換當(dāng)前種群P中的個(gè)體xi,g，替換條件為f(xi,g)>f(o)。

7)FEs=FEs+6。

8)返回新種群P和參數(shù)FEs。

3.3 協(xié)同進(jìn)化框架

為了進(jìn)一步提高求解大規(guī)模優(yōu)化問(wèn)題的性能，將NDG和CUDE引入到協(xié)同進(jìn)化框架之下，構(gòu)建DECC-NDG-CUDE算法(算法3)。

算法3 DECC-NDG-CUDE(func,lbs,ubs,n)。

1)

groups=NDG(func,lbs,ubs)

2)

pop=rand(popsize,n)

3)

(best,best_val)=min(func(pop))

4)

fori=1 tocyclesdo

5)

forj=1 to size(groups) do

6)

indicies=groups[j];

7)

subpop=pop[:,indicies]

8)

subpop=CUDE(best,subpop,FEs)

9)pop[:,indicies]=subpop

10) (best,best_val)=min(func(pop))

11)

end for

12)

end for

4 實(shí)驗(yàn)與分析

為了合理公平地評(píng)價(jià)NDG算法對(duì)變量進(jìn)行分組的準(zhǔn)確性和有效性， 本文仿真分別進(jìn)行分組和優(yōu)化兩個(gè)實(shí)驗(yàn)。分組實(shí)驗(yàn)驗(yàn)證NDG對(duì)變量分組的準(zhǔn)確性，并將分組結(jié)果和文獻(xiàn)[15]的DG方法進(jìn)行比較，優(yōu)化實(shí)驗(yàn)驗(yàn)證了DECC-NDG-CUDE求解大規(guī)模優(yōu)化問(wèn)題的性能，并將實(shí)驗(yàn)結(jié)果與DECC-DG(Differential Evolution with Cooperative Co-evolution and differential Grouping)[15]、DECCG(Differential Evolution with Cooperative Co-evolution and Random Grouping)[11]兩種算法進(jìn)行比較。

4.1 測(cè)試問(wèn)題

為保證真實(shí)性、有效性，選取CEC2010[20]標(biāo)準(zhǔn)測(cè)試集的10個(gè)1 000維的問(wèn)題進(jìn)行仿真實(shí)驗(yàn)。10個(gè)問(wèn)題的特征信息如表2所示。

其中：可分變量數(shù)(Sep_Vars)為1 000，不可分變量數(shù)(NonSep_Vars)為0，不可分變量組數(shù)(NonSep_Groups)為0。

其中：Sep_Vars為1 000，NonSep_Vars為0，NonSep_Groups為0。

f3(x)=frot_rastrigin[z(P1:Pm)]*106+

frastrigin[z(Pm+1:PD)]

其中：Sep_Vars為950，NonSep_Vars為50，NonSep_Groups為1。

frastrigin[z(PD/2+1:PD)]

其中：Sep_Vars為500，NonSep_Vars為500，NonSep_Groups為10。

fackley[z(PD/2+1:PD)]

其中：Sep_Vars為500，NonSep_Vars為500，NonSep_Groups為10。

fsphere[z(PD/2+1:PD)]

其中：Sep_Vars為500，NonSep_Vars為500，NonSep_Groups為10。

其中：Sep_Vars為0，NonSep_Vars為1 000，NonSep_Groups為20。

其中：Sep_Vars為0，NonSep_Vars為1 000，NonSep_Groups為20。

其中：Sep_Vars為0，NonSep_Vars為1 000，NonSep_Groups為20。

其中：Sep_Vars為0，NonSep_Vars為1 000，NonSep_Groups為1。

f1(x)～f10(x)表達(dá)式中，x=(x1,x2,…,xD)為候選解；z=x-o為偏移候選解，o=(o1,o2,…,oD)全局最優(yōu)解；P是{1,2,…,D}的一個(gè)隨機(jī)排列，D為問(wèn)題維度。

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

分組實(shí)驗(yàn)中利用NDG算法對(duì)10問(wèn)題進(jìn)行變量分組，檢驗(yàn)NDG算法對(duì)變量之間相關(guān)性的識(shí)別并依據(jù)其形成變量組的性能。為比較充分地驗(yàn)證NDG的性能，實(shí)驗(yàn)分別在兩種閾值(10-1和10-3)情況下進(jìn)行實(shí)驗(yàn)，記錄算法識(shí)別的可分變量數(shù)、相關(guān)變量數(shù)、相關(guān)變量分組數(shù)以及相關(guān)變量的識(shí)別成功率(所識(shí)別的相關(guān)變量除以相關(guān)變量總數(shù))，并將結(jié)果和文獻(xiàn)[15]中知名的算法DG進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果見(jiàn)表2和表3。

表2 變量分組結(jié)果(ε=10-1)Tab. 2 Grouping result(ε=10-1)

表3 變量分組結(jié)果(ε=10-3)Tab. 3 Grouping result(ε=10-3)

表2和表3的分組結(jié)果顯示，在兩種閾值下，對(duì)兩個(gè)完全可分的問(wèn)題f1、f2上，NDG和DG算法都能準(zhǔn)確的識(shí)別出為完全可分問(wèn)題，說(shuō)明兩種算法能準(zhǔn)確的區(qū)分出可分解的決策變量；在兩種閾值下，對(duì)f3、f4、f6三個(gè)部分可分解問(wèn)題上，NDG和DG算法的結(jié)果相同，能準(zhǔn)確的識(shí)別出可分解變量和相關(guān)變量，說(shuō)明兩種算法對(duì)著三個(gè)問(wèn)題的分解沒(méi)有受到閾值的影響，成功識(shí)別了變量的相關(guān)性，并且相關(guān)變量的分組也準(zhǔn)確無(wú)誤。

在f5、f7、f8、f9、f10部分可分的問(wèn)題上，NDG和DG兩種算法表現(xiàn)出不同的性能。在閾值為10-1時(shí)，對(duì)問(wèn)題f10兩種算法分組結(jié)果相同；在閾值為10-3時(shí)，DG算法對(duì)相關(guān)變量的識(shí)別成功率較低，僅有8.2%。而NDG算法仍能準(zhǔn)確地識(shí)別出所有變量為相關(guān)變量，且相關(guān)變量分組也準(zhǔn)確無(wú)誤。這一結(jié)果表明，對(duì)問(wèn)題f10，DG算法受到了閾值設(shè)置的影響，在較小閾值的設(shè)置下，不能準(zhǔn)確識(shí)別相關(guān)量，性能弱于NDG算法；對(duì)問(wèn)題f7，在閾值10-3時(shí)，兩種算法表現(xiàn)相同，均能有效識(shí)別變量的相關(guān)性，并準(zhǔn)確分組；在閾值為10-1時(shí)，算法DG未能完全識(shí)別相關(guān)變量，但只有1個(gè)相關(guān)變量未能準(zhǔn)確識(shí)別，成功率為99%。而NDG算法能準(zhǔn)確識(shí)別所有變量的相關(guān)性，性能略優(yōu)于DG算法。

在其他的三個(gè)問(wèn)題f5、f8、f9上，DG算法均對(duì)變量的相關(guān)性識(shí)別的成功率均未達(dá)到100%，即沒(méi)有準(zhǔn)確識(shí)別所有相關(guān)變量，其中f9在兩種閾值下的相關(guān)變量識(shí)別均非常低。f5、f8兩個(gè)問(wèn)題的相關(guān)變量的識(shí)別率，在閾值為10-1時(shí)分別為58.2%和64%，在閾值為10-3時(shí)分別為99.8%和99.6%。說(shuō)明DG算法對(duì)這兩個(gè)問(wèn)題的分解受到閾值的影響較大。然而，NDG算法在兩種閾值下，對(duì)于三個(gè)問(wèn)題均能準(zhǔn)確識(shí)別變量的相關(guān)性，且分組未出現(xiàn)差錯(cuò)。

綜上所述，對(duì)于選定的10個(gè)大規(guī)模問(wèn)題，NDG算法對(duì)變量相關(guān)性的識(shí)別性能整體上優(yōu)于DG算法，能準(zhǔn)確識(shí)別出相關(guān)變量并形成相關(guān)組。

圖1和圖2給出了存在差別的幾個(gè)問(wèn)題上相關(guān)變量識(shí)別成功率的柱狀圖，進(jìn)一步比較了兩種算法分組性能的區(qū)別。

圖1 捕獲不可分變量成功率(ε=10-1)Fig. 1 Success rate of capturing nonseparables variables(ε=10-1)

圖2 捕獲不可分變量成功率(ε=10-3)Fig. 2 Success rate of capturing nonseparables variables(ε=10-3)

4.3 優(yōu)化實(shí)驗(yàn)結(jié)果與分析

優(yōu)化實(shí)驗(yàn)驗(yàn)證DECC-NDG-CUDE算法對(duì)10個(gè)問(wèn)題的優(yōu)化求解性能。實(shí)驗(yàn)中各參數(shù)的設(shè)置為優(yōu)化問(wèn)題維度D=1 000，種群popsize=50，進(jìn)化結(jié)束條件為適應(yīng)度評(píng)價(jià)次數(shù)FEs=3E6。實(shí)驗(yàn)獨(dú)立執(zhí)行25次，記錄最優(yōu)解的平均值和方差。同時(shí)，為進(jìn)行對(duì)比分析，實(shí)現(xiàn)了DECCG[7]、DECC-DG[9]算法，依據(jù)原文先相同設(shè)置進(jìn)行仿真實(shí)驗(yàn)，并記錄結(jié)果。實(shí)驗(yàn)結(jié)果見(jiàn)表4。

從表4的求解結(jié)果均值來(lái)看，與DECC-DG算法相比，DECC-NDG-CUDE 在7個(gè)問(wèn)題上優(yōu)于算法DECC-DG，3個(gè)問(wèn)題上差于算法DECC-DG；與DECCG算法相比，DECC-NDG-CUDE在 7個(gè)問(wèn)題上優(yōu)于算法DECCG，3個(gè)問(wèn)題上差于DECCG。這說(shuō)明DECC-NDG-CUDE算法求解10個(gè)大規(guī)模問(wèn)題的數(shù)據(jù)結(jié)果整體上優(yōu)于DECC-DG和DECCG兩種算法結(jié)果。

為了保證以上數(shù)據(jù)結(jié)果的真實(shí)性，采用顯著水平為0.05的秩和檢驗(yàn)(Wilcoson test)對(duì)兩種算法的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行檢驗(yàn)，檢驗(yàn)結(jié)果用三種符號(hào)“+”“-”“≈”標(biāo)注在表4中。

表4 優(yōu)化實(shí)驗(yàn)結(jié)果Tab. 4 Optimization results

表4中，“+”“-”“≈”分別表示DECC-NDG-CUDE算法

弱于、優(yōu)于和相當(dāng)于對(duì)比算法(DECC-DG或DECCG)。首先，從檢驗(yàn)統(tǒng)計(jì)結(jié)果來(lái)看，DECC-NDG-CUDE在6個(gè)問(wèn)題(f1、f4、f6、f7、f9、f10)上是優(yōu)于DECC-DG、3個(gè)問(wèn)題(f2、f5、f8)上弱于DECC-DG、1個(gè)問(wèn)題(f5)上與DECC-DG算法相當(dāng)。這表明在f5上，與DECC-DG相比，DECC-NDG-CUDE數(shù)據(jù)結(jié)果的優(yōu)勢(shì)存在偶然性，實(shí)際兩個(gè)算法的結(jié)果不存在差別。其次，與DECCG的檢驗(yàn)結(jié)果與數(shù)據(jù)結(jié)果一致，這說(shuō)明DECC-NDG-CUDE在這7個(gè)問(wèn)題上的求解性能優(yōu)于DECCG是真實(shí)的，與數(shù)據(jù)比較結(jié)果一致。

圖3給出了其中6個(gè)問(wèn)題的收斂曲線。需要說(shuō)明的是，在f9和f10兩個(gè)問(wèn)題的收斂圖中，DECC-NDG-CUDE的收斂曲線差于DECCG，其原因是這兩個(gè)函數(shù)為完全不可分問(wèn)題，DECC-NDG-CUDE變量相關(guān)性識(shí)別損失了較多的評(píng)價(jià)資源，影響了后期的優(yōu)化效果。但是，從6幅圖的整體情況來(lái)看，收斂曲線仍然支持了以上數(shù)據(jù)分析的結(jié)果。

圖3 三種算法在6個(gè)問(wèn)題上的收斂曲線Fig. 3 Convergence curve of three algorithms on six problems

最后，為整體上比較三種算法求解10個(gè)大規(guī)模優(yōu)化問(wèn)題的性能，對(duì)三種算法優(yōu)化結(jié)果進(jìn)行Friedman排名檢驗(yàn)，檢驗(yàn)結(jié)果為，DECC-NDG-CUDE的排名值為1.60，DECC-DG排名值為2.10，DECCG排名值為2.30。因此， DECC-NDG-CUDE的Friedman檢驗(yàn)排名第一，整體性能最好。

綜上所述，DECC-NDG-CUDE算法對(duì)于10個(gè)優(yōu)化問(wèn)題的優(yōu)化性能在整體上優(yōu)于DECC-DG和DECCG兩種算法。

5 結(jié)語(yǔ)

針對(duì)大規(guī)模優(yōu)化問(wèn)題，本文首先提出一種改進(jìn)的分組方法NDG，該算法采用隨機(jī)選取測(cè)試點(diǎn)，逐一檢測(cè)每對(duì)決策變量的相關(guān)性，并依據(jù)相關(guān)性對(duì)變量進(jìn)行分組，從而將大規(guī)模優(yōu)化問(wèn)題劃分為多個(gè)子問(wèn)題，降低了子問(wèn)題之間的依賴(lài)關(guān)系; 同時(shí)，為了充分利用變量相關(guān)性的學(xué)習(xí)結(jié)果，將較大的可分變量組進(jìn)行二次分組，在不影響相關(guān)組的情況下，降低了待優(yōu)化子問(wèn)題的維度。仿真實(shí)驗(yàn)表明NDG算法提高了變量分組的精確度，能夠?qū)f(xié)同優(yōu)化求解起到促進(jìn)作用；另一方面，為進(jìn)一步提高優(yōu)化問(wèn)題求解進(jìn)度，在改進(jìn)的差分進(jìn)化算法CUDE的基礎(chǔ)之上，設(shè)計(jì)新的子問(wèn)題優(yōu)化器，并引入到CC框架之下，構(gòu)建DECC-NDG-CUDE算法。優(yōu)化仿真實(shí)驗(yàn)的結(jié)果表明，在10個(gè)大規(guī)模優(yōu)化問(wèn)題上，DECC-NDG-CUDE能夠進(jìn)一步提高求解精度，求解性能優(yōu)于DECC-DG和DECCG兩種知名算法，是求解大規(guī)模優(yōu)化問(wèn)題的一種有效的算法。在未來(lái)的研究工作中，將深入探索優(yōu)化過(guò)程中降低函數(shù)評(píng)價(jià)次數(shù)的合理途徑，從而減少因變量分組消耗評(píng)價(jià)次數(shù)對(duì)問(wèn)題優(yōu)化帶來(lái)的影響。

References)

[1] STORN R, PRICE K. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4):341-359.

[2] KENNEDY J, EBERHART R. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE, 1995: 1942-1948.

[3] KARABOGA D,BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3):459-471.

[4] GOLDBERG D E, VOESSNER S. Optimizing global-local search hybrids[EB/OL].[2016- 11- 20].http://pdfs.semanticscholar.org/21b8/ae2a75de794a625df6737466483d93441f9b.pdf.

[5] FACHBEREICH V,INFORMATIK E. Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies[EB/OL].[2016- 11- 20].http://dokumentix.ub.uni-siegen.de/opus/volltexte/2006/181/pdf/merz.pdf.

[6] DENG C, DONG X, YANG Y, et al. Differential evolution with novel local search operation for large scale optimization problems[C]// Proceedings of the 6th International Conference Advances in Swarm and Computational Intelligence. Berlin: Springer, 2015,9140:317-325.

[7] 董小剛,鄧長(zhǎng)壽,袁斯昊,等. MapReduce模型下的分布式差分進(jìn)化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng),2016,37(12):2695-2701.(DONG X G, DENG C S,YUAN S H, et al.Distributed differential evolution algorithm based on MapReduce model[J]. Journal of Chinese Computer Systems,2016,37(12):2695-2701.)

[8] SUN C, JIN Y, CHENG R, et al. Surrogate-assisted cooperative swarm optimization of high-dimensional expensive problems[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(4)：644-660.

[9] 劉劍英. 基于GPU的并行協(xié)同差分進(jìn)化算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用,2012,48(7):48-50.(LIU J Y. Research of parallel cooperation differential evolution algorithm based on GPU[J]. Computer Engineering and Applications, 2012, 48(7): 48-50.)

[10] 張大斌,周志剛,葉佳,等. 基于隨機(jī)擴(kuò)散搜索的協(xié)同差分進(jìn)化算法[J]. 計(jì)算機(jī)工程,2014,40(7):183-188.(ZHANG D B, ZHOU Z G, YE J, et al. Cooperation differential evolution algorithm based on stochastic diffusion search[J]. Computer Engineering, 2014, 40(7):183-188.)

[11] YANG Z, TANG K, YAO X. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences, 2008, 178(15):2985-2999.

[12] TRUNFIO G A, TOPA P, WAS J. A new algorithm for adapting the configuration of subcomponents in large-scale optimization with cooperative coevolution[J]. Information Sciences, 2016, 372:773-795.

[13] YANG P, TANG K, YAO X. Turning high-dimensional optimization into computationally expensive optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(9):1-14.

[14] CHEN W, WEISE T, YANG Z, et al. Large-scale global optimization using cooperative coevolution with variable interaction learning[C]// Proceedings of the 11th International Conference on Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 2010: 300-309.

[15] OMIDVAR M N, LI X, MEI Y, et al. Cooperative co-evolution with differential grouping for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 378-393.

[16] PENG H, WU Z, DENG C. Enhancing differential evolution with commensal learning and uniform local search[J]. Chinese Journal of Electronics, 2017, 26(4): 725-733.

[17] WANG Y, FANG K. A note on uniform distribution and experiment design[J]. Science Bulletin, 1981, 26(6):485-489.

[18] FANG K, MA C, WINKER P, et al. Uniform design: theory and application[J]. Technometrics, 2000, 42(3):237-248.

[19] PENG L, WANG Y. Differential evolution using uniform-quasi-opposition for initializing the population[J]. Information Technology Journal, 2010, 9(8): 1629-1634.

[20] TANG K, LI X, SUGANTHAN P N, et al. Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization[EB/OL].[2016- 11- 20].http://goanna.cs.rmit.edu.au/～xiaodong/ publications/lsgo-cec10.pdf.

This work is partially supported by the National Natural Science Foundation of China (61364025), the Science and Technology Project of Jiangxi Provincial Education Department (GJJ161072，GJJ161076).

DONGXiaogang, born in 1979, M.S.,lecturer. His research interests include intelligent computing.

DENGChangshou, born in 1972, Ph.D., professor. His research interests include intelligent computing, big data.

TANYucheng, born in 1964, M.S., associate professor. His research interests include applied mathematics, intelligent computing.

PENGHu, born in 1981, Ph.D., associate professor. His research interests include intelligent computing, big data.

WUZhijian, born in 1963, Ph.D., professor. His research interests include intelligent computing, parallel computing, intelligent information processing.

Cooperativedifferentialevolutionalgorithmforlarge-scaleoptimizationproblems

DONG Xiaogang1,DENG Changshou1*,TAN Yucheng2,PENG Hu1,WU Zhijian3

(1.SchoolofComputerScienceandTechnology,JiujiangUniversity,JiujiangJiangxi332005,China;2.CollegeofScience,JiujiangUniversity,JiujianJiangxi332005,China;3.StateKeyLaboratoryofSoftwareEngineering(WuhanUniversity),WuhanHubei430072,China)

A new method of large-scale optimization based on divide-and-conquer strategy was proposed. Firstly, based on the principle of additive separability, an improved variable grouping method was proposed. The randomly accessing point method was used to check the correlation between all variables in pairs. At the same time, by making full use of the interdependency information of learning, the large groups of separable variables were re-grouped. Secondly, a new subcomponent optimizer was designed based on an improved differential evolution algorithm to enhance the subspace optimization performance. Finally, this two kinds of improvements were introduced to co-evolutionary framework to construct a DECC-NDG-CUDE (Cooperative differential evolution with New Different Grouping and enhancing Differential Evolution with Commensal learning and Uniform local search) algorithm. Two experiments of grouping and optimization were made on 10 large-scale optimization problems. The experimental results show the interdependency between variables can be effectively identified by the new method of grouping, and the performance of DECC-NDG-CUDE is better than two state-of-the-art algorithms DECC-D (Differential Evolution with Cooperative Co-evolution and differential Grouping) and DECCG (Differential Evolution with Cooperative Co-evolution and Random Grouping).

large-scale optimization; variable grouping; additive separability; optimizer; cooperative co-evolution

2017- 05- 11;

2017- 06- 07。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61364025); 江西省教育廳科技項(xiàng)目(GJJ161072，GJJ161076)。

董小剛(1979—)，男，陜西寶雞人，講師，碩士，CCF會(huì)員，主要研究方向：智能計(jì)算； 鄧長(zhǎng)壽(1972—)，男，安徽合肥人，教授，博士，CCF會(huì)員，主要研究方向：智能計(jì)算、大數(shù)據(jù)； 譚毓澄(1964—)，男，江西九江人，副教授，碩士，主要研究方向：應(yīng)用數(shù)學(xué)、智能計(jì)算； 彭虎(1981—)，男，湖南長(zhǎng)沙人，副教授，博士，CCF會(huì)員，主要研究方法：智能計(jì)算、大數(shù)據(jù)； 吳志健(1963—)，男，江西上饒人，教授，博士、CCF會(huì)員，主要研究方向：智能計(jì)算、并行計(jì)算、智能信息處理。

1001- 9081(2017)11- 3219- 07

10.11772/j.issn.1001- 9081.2017.11.3219

(*通信作者電子郵箱dengtju@aliyun.com)

TP18

A