求解大規模優化問題的新型協同差分進化算法

董小剛，鄧長壽，譚毓澄，彭 虎，吳志健

(1.九江學院 信息科學與技術學院，江西 九江 332005； 2. 九江學院 理學院，江西 九江 332005；3.軟件工程國家重點實驗室(武漢大學), 武漢 430072)

求解大規模優化問題的新型協同差分進化算法

董小剛1，鄧長壽1*，譚毓澄2，彭 虎1，吳志健3

(1.九江學院 信息科學與技術學院，江西 九江 332005； 2. 九江學院 理學院，江西 九江 332005；3.軟件工程國家重點實驗室(武漢大學), 武漢 430072)

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

大規模優化；變量分組；加性可分；優化器；協同進化

0 引言

工業界和學術界各類數據規模的爆炸式增長，使得大規模數據處理技術成為各領域研究的熱點， 數據優化領域也進入了大規模時代。大規模黑盒優化問題高度復雜，無法采用傳統的數學方法有效求解，其中決策變量的大規模性是構成求解難度的關鍵因素。進化計算是一類求解復雜優化問題的高效方法，過去二十多年的研究和應用表明，在小規模優化問題上進化算法取得了理想求解結果; 然而，當優化問題的規模迅速增大時，進化計算面臨嚴重的挑戰，求解性能惡化嚴重。如何利用進化計算方法，求解大規模優化問題，是目前科學和工程應用領域的研究熱點。

1 相關工作

當前，針對大規模優化問題的求解，學者們進行了多方面的研究工作，這些工作可歸納為以下兩個方面。

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

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

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

2 新型變量分組策略

2.1 函數的加性可分性原理

大規模黑盒優化問題由于其數學模型未知和不可獲取，傳統的數學方法，如求導法、單純形法、梯度法等不再適用。針對這一情況，當前廣泛采用的方法是通過對決策變量的分組，將問題分解成多個低維度的子問題來進行各個擊破的獨立求解。然而，當決策變量之間存在復雜的相互依賴關系時，盲目分組顯然無法達到有效求解的目的。

基于加性可分性原理對變量之間的依賴關系進行先期學習，然后據此進行變量分組，可以最大限度地降低子問題之間的依賴關系，對提高求解性能有很大的促進作用。

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

(1)

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

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

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

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

以此類推可得出如下推論：

n維函數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相互依賴，不可分。

式(2)和式(3)由加性可分性函數的定義導出，是函數加性可分的性質。

文獻[15]利用式(2)構建了大規模優化問題自動分組(DG)算法。DG算法在可行域中選取4個測試點(邊界和中心)，計算式(2)左右兩側的兩個差值Δ1和Δ2，通過比較表達式│Δ1-Δ2│ 的值和設定閾值的關系來判定決策變量之間是否存在依賴關系，進而形成變量分組。DG算法合理利用了函數加性可分的性質，能夠較為準確地實現決策變量的分組。

然而，DG算法的實現仍然存在以下幾個方面的不足：

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

x1*xn*(xn2-25)*n

(4)

設式(4)所示函數的定義域為[-5，5]。假設n=4，則f(x)為4維函數。依據DG算法，用定義域的邊界構造4個點，檢測第一維和第二維的相關性，具體過程如下：

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

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

(5)

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

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

(6)

|Δ1-Δ2|

(7)

則式(7)的值必定為0。據此，DG算法將第一維和第二維識別為不相關變量。此結論顯然與函數本身的性質不符。

2)排除已經形成分組的所有相關變量，導致依賴關系檢測不全面，影響了分組的成功率。

3)沒有充分地利用分組學習階段所獲得的信息。比如將所有可分變量歸為一個分組，當可分變量數量比較大時，所形成的分組規模較大，無法達到有效降維的目的，并且浪費了較多的評價資源。

2.2 新型分組算法

為了進一步提高變量分組的精度，提高大規模優化問題的求解性能。針對DG算法3個不足進行改進，提出一種新的變量分組(NDG)算法。

首先，NDG算法避免采用可行域的邊界作為測試點，而以邊界附近的隨機值為測試點。

其次，NDG算法采用遍歷形式對變量相關性進行檢測，也就說并不因為形成分組而排除某個變量的相關性檢測，從而避免遺漏。

最后，為對相關性學習的結果進行充分利用，尤其是針對學習后判定為可分的變量組，若其大小仍然較大，則對其進行二次分組，進一步降低維度。

NDG算法的基本流程如下：

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

1)

設置Dims={1,2,…,1 000},定義可分組變Seps，相關分組變量Cgroups，中間集合變量group,Agroups，Bgroups；初始化上下界變量lb，ub，評價次數變量FES=0；

2)

while (Dims不為空)

3)

group=[Dims(1)];

4)

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

5)

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

6)

Δ1=f(p1)-f(p2)，FES=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)，FES=FES+2;

12)

if abs(Δ1-Δ2)>eps

group=[group,Dims(i)]

13)

end if

14)

end For循環

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)

設置Dims(1)=[]

19)

end if

20) end while循環

21) 合并Agroup中包含相同元素的相關組，將結果賦值給Cgroup

22)

返回Seps，Cgroups;

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

3 基于改進差分進化算法的子問題優化器

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

3.1 改進的進化策略和參數調整方案

縮放因子F和交叉概率CR是影響DE算法性能的兩個核心參數。關于DE參數的大量研究已經證明固定的參數設置并非提高算法性能的最好設置。一般來說，較大的F和CR適合用于進化初期提升算法的全局搜索性能。而較小的F和CR適合在進化后期加強算法的局部開采性能，并加速收斂；然而，簡單的前大后小的設置對提高算法的性能意義不大。

CUDE采用雙邊高斯分布進行F和CR的動態自適應更新。具體設置依據式(8)和(9)進行:

(8)

(9)

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

另外，為避免單一進化策略對問題的依賴性，CUDE選擇DE/rand/1、DE/best/1、DE/target-to-rand/1三種進化策略與雙邊高斯參數設置進行組合使用。

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

SRsch,i=Ssch,i/Tsch,i

(10)

依據SRsch,i，構建學習字典二維表。在下一代中依據學習字典，采用輪盤賭的方式選擇每個個體的進化方案。

3.2 基于均勻設計的局部搜索

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

均勻設計依據均勻設計表來安排實驗方案。一個均勻設計表可表示為Un(qS),其中n為表的行數，代表要安排的實驗次數；S為列數，代表要考慮的因素數；q代表每個因素要考慮的水平數。CUDE所采用的ULS局部搜索方法，選擇均勻設計表U6(66)進行實驗方案安排。關于U6(66)的構造參考文獻[16]。

表1 均勻設計表 U6(66)Tab. 1 Uniform design table U6(66)

CUDE采用以上兩個方面的改進提高了算法的尋優能力，算法詳細流程及參數見文獻[16]。

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

算法2 ULS算法。

1)輸入：種群P，評價次數計數器FEs。

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

3)根據xi,g和xj,g，利用U6(66)進行均勻，產生6個實驗個體y1,y2,…,y6。

4)評價6個實驗個體。

5)選取適應度最高的一個實驗個體O。

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

7)FEs=FEs+6。

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

3.3 協同進化框架

為了進一步提高求解大規模優化問題的性能，將NDG和CUDE引入到協同進化框架之下，構建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 實驗與分析

為了合理公平地評價NDG算法對變量進行分組的準確性和有效性， 本文仿真分別進行分組和優化兩個實驗。分組實驗驗證NDG對變量分組的準確性，并將分組結果和文獻[15]的DG方法進行比較，優化實驗驗證了DECC-NDG-CUDE求解大規模優化問題的性能，并將實驗結果與DECC-DG(Differential Evolution with Cooperative Co-evolution and differential Grouping)[15]、DECCG(Differential Evolution with Cooperative Co-evolution and Random Grouping)[11]兩種算法進行比較。

4.1 測試問題

為保證真實性、有效性，選取CEC2010[20]標準測試集的10個1 000維的問題進行仿真實驗。10個問題的特征信息如表2所示。

其中：可分變量數(Sep_Vars)為1 000，不可分變量數(NonSep_Vars)為0，不可分變量組數(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)表達式中，x=(x1,x2,…,xD)為候選解；z=x-o為偏移候選解，o=(o1,o2,…,oD)全局最優解；P是{1,2,…,D}的一個隨機排列，D為問題維度。

4.2 分組實驗結果與分析

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

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

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

表2和表3的分組結果顯示，在兩種閾值下，對兩個完全可分的問題f1、f2上，NDG和DG算法都能準確的識別出為完全可分問題，說明兩種算法能準確的區分出可分解的決策變量；在兩種閾值下，對f3、f4、f6三個部分可分解問題上，NDG和DG算法的結果相同，能準確的識別出可分解變量和相關變量，說明兩種算法對著三個問題的分解沒有受到閾值的影響，成功識別了變量的相關性，并且相關變量的分組也準確無誤。

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

在其他的三個問題f5、f8、f9上，DG算法均對變量的相關性識別的成功率均未達到100%，即沒有準確識別所有相關變量，其中f9在兩種閾值下的相關變量識別均非常低。f5、f8兩個問題的相關變量的識別率，在閾值為10-1時分別為58.2%和64%，在閾值為10-3時分別為99.8%和99.6%。說明DG算法對這兩個問題的分解受到閾值的影響較大。然而，NDG算法在兩種閾值下，對于三個問題均能準確識別變量的相關性，且分組未出現差錯。

綜上所述，對于選定的10個大規模問題，NDG算法對變量相關性的識別性能整體上優于DG算法，能準確識別出相關變量并形成相關組。

圖1和圖2給出了存在差別的幾個問題上相關變量識別成功率的柱狀圖，進一步比較了兩種算法分組性能的區別。

圖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 優化實驗結果與分析

優化實驗驗證DECC-NDG-CUDE算法對10個問題的優化求解性能。實驗中各參數的設置為優化問題維度D=1 000，種群popsize=50，進化結束條件為適應度評價次數FEs=3E6。實驗獨立執行25次，記錄最優解的平均值和方差。同時，為進行對比分析，實現了DECCG[7]、DECC-DG[9]算法，依據原文先相同設置進行仿真實驗，并記錄結果。實驗結果見表4。

從表4的求解結果均值來看，與DECC-DG算法相比，DECC-NDG-CUDE 在7個問題上優于算法DECC-DG，3個問題上差于算法DECC-DG；與DECCG算法相比，DECC-NDG-CUDE在 7個問題上優于算法DECCG，3個問題上差于DECCG。這說明DECC-NDG-CUDE算法求解10個大規模問題的數據結果整體上優于DECC-DG和DECCG兩種算法結果。

為了保證以上數據結果的真實性，采用顯著水平為0.05的秩和檢驗(Wilcoson test)對兩種算法的實驗數據進行檢驗，檢驗結果用三種符號“+”“-”“≈”標注在表4中。

表4 優化實驗結果Tab. 4 Optimization results

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

弱于、優于和相當于對比算法(DECC-DG或DECCG)。首先，從檢驗統計結果來看，DECC-NDG-CUDE在6個問題(f1、f4、f6、f7、f9、f10)上是優于DECC-DG、3個問題(f2、f5、f8)上弱于DECC-DG、1個問題(f5)上與DECC-DG算法相當。這表明在f5上，與DECC-DG相比，DECC-NDG-CUDE數據結果的優勢存在偶然性，實際兩個算法的結果不存在差別。其次，與DECCG的檢驗結果與數據結果一致，這說明DECC-NDG-CUDE在這7個問題上的求解性能優于DECCG是真實的，與數據比較結果一致。

圖3給出了其中6個問題的收斂曲線。需要說明的是，在f9和f10兩個問題的收斂圖中，DECC-NDG-CUDE的收斂曲線差于DECCG，其原因是這兩個函數為完全不可分問題，DECC-NDG-CUDE變量相關性識別損失了較多的評價資源，影響了后期的優化效果。但是，從6幅圖的整體情況來看，收斂曲線仍然支持了以上數據分析的結果。

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

最后，為整體上比較三種算法求解10個大規模優化問題的性能，對三種算法優化結果進行Friedman排名檢驗，檢驗結果為，DECC-NDG-CUDE的排名值為1.60，DECC-DG排名值為2.10，DECCG排名值為2.30。因此， DECC-NDG-CUDE的Friedman檢驗排名第一，整體性能最好。

綜上所述，DECC-NDG-CUDE算法對于10個優化問題的優化性能在整體上優于DECC-DG和DECCG兩種算法。

5 結語

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

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] 董小剛,鄧長壽,袁斯昊,等. MapReduce模型下的分布式差分進化算法[J]. 小型微型計算機系統,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的并行協同差分進化算法研究[J]. 計算機工程與應用,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]. 計算機工程,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。

國家自然科學基金資助項目(61364025); 江西省教育廳科技項目(GJJ161072，GJJ161076)。

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

1001- 9081(2017)11- 3219- 07

10.11772/j.issn.1001- 9081.2017.11.3219

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

TP18

A