賈 欣，王宇嘉，聶方鑫，孫福祿

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

1 引 言

許多工程優(yōu)化中涉及到數(shù)量龐大的參數(shù)問題、聚類問題[1，2]、特征選擇問題[3，4]，這類問題的特點(diǎn)是決策變量個(gè)數(shù)多，變量之間存在較強(qiáng)的相關(guān)性，稱具有這類特點(diǎn)的問題為大規(guī)模全局優(yōu)化(Large Scale Global Optimizations，LSGO)[5]問題.進(jìn)化計(jì)算在低維問題求解中，取得了較好的效果，但是在求解LSGO問題時(shí)，往往會(huì)遭遇“維數(shù)災(zāi)難”，為了緩解維度災(zāi)難問題，研究者們提出了分治策略，即對(duì)一個(gè)LSGO問題首先進(jìn)行分解，將其分解成多個(gè)低維問題，然后對(duì)分解后的低維問題分別進(jìn)行求解.采用分治策略，緩解了維數(shù)災(zāi)難導(dǎo)致的進(jìn)化算法性能下降的問題.

協(xié)同進(jìn)化(Cooperative Coevolution，CC)[6]是采用分治策略解決LSGO的一般選擇.協(xié)同進(jìn)化算法(Cooperative Coevolution Evolutionary Algorithms，CCEAs)的難點(diǎn)是進(jìn)行有效的分組[7，8]，在處理LSGO問題時(shí)，由于決策變量之間相關(guān)性，使得CCEAs在分治求解的過程中并沒有最優(yōu)的方法將決策變量進(jìn)行分組.

在CCEAs發(fā)展之初，靜態(tài)分組和隨機(jī)分組被廣泛應(yīng)用.Potter和De Jong[9]提出了靜態(tài)變量分組算法(Cooperative Coevolution Genetic Algorithm，CCGA)，該算法將LSGO問題的n個(gè)變量分解為n個(gè)一維的問題，通過GA對(duì)分解后的一維問題進(jìn)行協(xié)同優(yōu)化.Yang等人[10]提出隨機(jī)分組的差分協(xié)同進(jìn)化算法(Differential Coevolution Evolution random Grouping，DECC-G)，DECC-G將LSGO問題的n個(gè)決策變量隨機(jī)進(jìn)行分組，通過DE對(duì)分組后的組件進(jìn)行協(xié)同優(yōu)化.CCGA和DECC-G在解決完全可分離的LSGO問題時(shí)取得了較好的優(yōu)化結(jié)果，但在處理變量之間存在相關(guān)性的LSGO問題時(shí)，破壞了變量之間的相互作用，導(dǎo)致最終優(yōu)化結(jié)果不佳.隨后，研究者們提出了變量交互學(xué)習(xí)[11，12]分組方法，Omidvar等人[13]提出差分分組(Differential Group，DG)，相比隨機(jī)分組不考慮變量之間的相互影響，DG通過檢測(cè)變量之間的相關(guān)性，將相互影響的變量分到同一組，增大組內(nèi)變量相互作用，減少組間變量相互作用，提高了算法的優(yōu)化性能.Mohammad等人[14]提出遞歸分組(Recursive Difference Grouping，RDG)，RDG使用貪婪分解策略[15]，將相互重疊的變量隨機(jī)分配給與之交互的組件，提高了算法在處理變量重疊問題時(shí)的優(yōu)化性能；但是DG和RDG在分組時(shí)僅考慮變量之間的相互作用，未考慮變量對(duì)適應(yīng)度值的影響，所以降低了算法的收斂性.Philip等人[16]提出全局分組(Global Differential Grouping，GDG)，首先對(duì)問題進(jìn)行建模，然后采用微分分組策略對(duì)問題進(jìn)行分組，提高了分組精度.Li等人[17]提出改善的差分分組(Effective Differential Grouping，DG2)，該方法通過成對(duì)變量交互作用來估計(jì)舍入誤差，提高算法分組精度.但是因?yàn)镚DG和DG2增加了建模和估計(jì)誤差操作，所以在分組時(shí)導(dǎo)致適應(yīng)度評(píng)估次數(shù)和時(shí)間計(jì)算成本的增加.

為了克服以上的問題，本文提出了一種基于自適應(yīng)兩階段分組的差分協(xié)同進(jìn)化算法(Cooperative-Coevolution-DE with Two-StageGrouping in LSGO，DECC-TSL)來求解大規(guī)模全局優(yōu)化問題.該算法通過兩個(gè)階段對(duì)變量進(jìn)行分組操作，在第1階段分組中，判斷決策變量貢獻(xiàn)度正負(fù)性，將其分為正促進(jìn)組和負(fù)抑制組.在第2階段分組中，分別對(duì)兩組內(nèi)的變量進(jìn)行相關(guān)性的識(shí)別，統(tǒng)計(jì)并記錄每個(gè)變量與之直接相關(guān)的變量個(gè)數(shù)，根據(jù)相關(guān)變量個(gè)數(shù)所占比例，確定組內(nèi)變量個(gè)數(shù).由于分組時(shí)增加了變量對(duì)函數(shù)貢獻(xiàn)度的正負(fù)性判斷，因此可以更好的避免將兩個(gè)正負(fù)性相反的變量分到同一組內(nèi).在整個(gè)演化過程中，采用差分協(xié)同進(jìn)化框架，使算法能快速地向問題的最優(yōu)解方向收斂，有效地提高算法性能.

2 相關(guān)工作

2.1 大規(guī)模全局優(yōu)化問題

在優(yōu)化算法的發(fā)展初期，含有幾十或上百個(gè)決策變量的問題被認(rèn)為時(shí)LSGO問題，但隨著優(yōu)化問題復(fù)雜性的提高，現(xiàn)在一般認(rèn)為存在上千個(gè)決策變量的問題為L(zhǎng)SGO問題.LSGO問題可以描述為：

(1)

其中，f表示目標(biāo)函數(shù)，x1，x2，…，xn表示決策變量，n表示決策變量的個(gè)數(shù).

2.2 變量分離問題

定義變量分離問題[18]建立在變量相互依賴的基礎(chǔ)上，變量的相互依賴性由公式(2)定義：

(2)

定義1.(直接相關(guān)作用)：給定一個(gè)n維函數(shù)f(X)X=(x1，x2，…，xn)，n≥2，當(dāng)且僅當(dāng)滿足公式(2)時(shí)，xp和xq(1≤p≤q≤n)互為直接相關(guān)作用.

定義2.(間接相關(guān)作用)：給定一個(gè)n維函數(shù)f(X)，X=(x1，x2，…，xn)，n≥3，當(dāng)且僅當(dāng)它們沒有直接相互作用且存在子集合Θ，Θ?X，Θ=(x1，x2，…,xm)，0

定義3.(獨(dú)立變量)：給定一個(gè)n維函數(shù)f(X)，X=(x1，x2，…，xn)，n≥2，當(dāng)且僅當(dāng)xp和xq既不存在直接相關(guān)作用也不存在間接相關(guān)作用時(shí)，xp和xq為獨(dú)立變量.

根據(jù)上述3種定義，可以將LSGO問題大致分為兩類，分別為可分問題和不可分問題.

定義4.(可分問題)：當(dāng)?p，q∈{1，2，…n}，p≠q，xp和xq為獨(dú)立變量，則函數(shù)f(X)是可分問題.

定義5.(不可分問題)：當(dāng)?p，q∈{1，2，…n}，p≠q，xp和xq之間存在直接或者間接相關(guān)作用，則函數(shù)f(X)是不可分問題.

以變量為節(jié)點(diǎn)，直接相關(guān)作用為邊，每對(duì)變量之間的相關(guān)性如圖1所示.

圖1 大規(guī)模問題分類

根據(jù)以上定義，圖1(a)和圖1(b)分別表示部分可分離函數(shù)和完全可分離函數(shù)；圖1(c)是含有重疊變量的不可分離函數(shù)；圖1(d)是完全不可分離函數(shù).

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

差分進(jìn)化算法(Differential Evolution，DE)[19]采用了遺傳算法的基本框架，設(shè)計(jì)了獨(dú)特的差分變異算子.

2.3.1 初始化

初始化種群：

(3)

(4)

其中，t代表迭代次數(shù)，dim代表問題的維數(shù).當(dāng)前迭代中的解x為目標(biāo)向量.初始化之后，優(yōu)化過程主要有3個(gè)步驟：變異、交叉和選擇.

2.3.2 變異

變異產(chǎn)生的解稱為供體載體v.有5種常見的突變策略，它們具有不同的差異載體.

(5)

(6)

(7)

(8)

(9)

其中，r1、r2、r3、r4和r5是從[1，NP]中隨機(jī)選擇的，xbest是第t代中的最佳解.突變的形式可以表示為DE/a/b，其中′a′表示要擾動(dòng)的向量，而′b′表示擾動(dòng)向量′a′的差向量的數(shù)量.

2.3.3 交叉操作

對(duì)變異產(chǎn)生的供體載體v進(jìn)行交叉操作，交叉產(chǎn)生的向量為m，在交叉過程中，供體載體向量和v決策變量x以概率CR隨機(jī)選擇.

(10)

其中，qrand是從[1，dim]中的一個(gè)隨機(jī)整數(shù)，用來保證變量中至少有一個(gè)向量進(jìn)行了交叉操作.交叉概率CR∈[0，1].

2.3.4 選擇操作

選擇操作判斷是否可以將交叉向量m或目標(biāo)向量x迭代到下一次popt+1中.

(11)

其中，f(·)表示最小化問題中的目標(biāo)函數(shù).

3 算法框架

3.1 第1階段分組

3.1.1 變量貢獻(xiàn)度

基于貢獻(xiàn)度的分組策略，是一種根據(jù)變量收斂程度而進(jìn)行分組的策略.所謂變量貢獻(xiàn)度，是每個(gè)變量在迭代過程中，使適應(yīng)度值減小的程度，變量貢獻(xiàn)度計(jì)算過程如公式(12)所示，隨機(jī)生成的適應(yīng)度值作為變量貢獻(xiàn)度的初始值.

(12)

其中，xi表示第i個(gè)變量；t表示迭代次數(shù)；bi，t表示變量i在第t次迭代時(shí)的最佳變量；f(x|xi=bi.t)-f(x|xi=bi.t+1)表示兩次迭代適應(yīng)度的差值.

3.1.2 貢獻(xiàn)度分組

通過對(duì)決策變量貢獻(xiàn)度的計(jì)算，考慮到?jīng)Q策變量可能會(huì)對(duì)函數(shù)適應(yīng)度值的改變具有正促進(jìn)或負(fù)抑制的作用，如果把作用相反的兩個(gè)變量分到同一組內(nèi)，適應(yīng)度值可能會(huì)由于相互抑制，而不能朝著最優(yōu)解的方向進(jìn)行.針對(duì)這個(gè)問題，在第1階段分組時(shí)，判斷所有變量的Fxi，將Fxi>0的變量分到正促進(jìn)組，F(xiàn)xi<0的變量分到負(fù)抑制組.第1階段變量貢獻(xiàn)度分組過程如圖2所示.

圖2 第1階段分組Fig.2 First stage grouping

3.2 第2階段分組

3.2.1 變量相關(guān)性

在優(yōu)化問題中，決策變量之間相互作用，稱這樣的變量具有相關(guān)性.變量相關(guān)性由公式(13)和公式(14)表示：

Δδ，xpf(x)|xp=a，xq=b≠Δδ，xpf(x)|xp=a，xq=c

(13)

Δδ，xpf(x)=f(…，xp+δ，…)-f(…，xp，…)

(14)

其中，a，b，c代表不同的實(shí)數(shù)，δ代表對(duì)xp的擾動(dòng)，且δ≠0，當(dāng)xq取不同數(shù)值時(shí)，若對(duì)決策變量xp進(jìn)行δ擾動(dòng)導(dǎo)致適應(yīng)度值發(fā)生變化，那么變量xp和xq具有相關(guān)性，稱xp和xq互為非獨(dú)立變量.

3.2.2 變量相關(guān)性識(shí)別

在第2階段分組中，分別對(duì)正促進(jìn)組和負(fù)抑制組內(nèi)變量進(jìn)行變量識(shí)別，分為獨(dú)立變量組和非獨(dú)立變量組.

圖3 變量相關(guān)性識(shí)別Fig.3 Variable correlation recognition

第2階段變量相關(guān)性識(shí)別過程如圖3所示，以正促進(jìn)組為例，具體步驟如下：

Step1.從正促進(jìn)組選取x1作為被檢測(cè)變量，將其存入名為s1的變量組中，剩余變量存入名為s2的變量組；

Step2.從s2中選擇變量x2，根據(jù)公式(13)-公式(14)，檢測(cè)x1和x2的相關(guān)性；

Step3.若x1與x2相關(guān)，則將x2放入s1中，若不相關(guān)，x2放入原變量組中；

Step4.從s2中依次選取變量與x1進(jìn)行相關(guān)性檢測(cè)，重復(fù)Step 2-Step 3；直到x1與s2中m-1個(gè)變量完成相關(guān)性識(shí)別；

Step5.若x1與s2中m-1個(gè)變量均不相關(guān)，則將x1放入獨(dú)立變量組中，否則，將s1放入非獨(dú)立變量組；

Step6.重復(fù)上述Step 1-Step 5，直到將m個(gè)變量分別放入獨(dú)立變量組和非獨(dú)立變量組.

3.2.3 確定組內(nèi)變量個(gè)數(shù)

通過變量相關(guān)性的識(shí)別，將所有變量分為獨(dú)立變量組和非獨(dú)立變量組.對(duì)于非獨(dú)立變量組，變量之間存在相互作用，若組內(nèi)變量個(gè)數(shù)過多，容易導(dǎo)致算法收斂性不佳.針對(duì)這個(gè)問題，在固定分組和隨機(jī)分組策略中，均是提前定義好組內(nèi)變量個(gè)數(shù)，然后進(jìn)行分組.該策略易使算法陷入局部最優(yōu)而無法跳出，最終導(dǎo)致算法無法找到最優(yōu)解.本文提出一種自適應(yīng)確定組內(nèi)變量個(gè)數(shù)大小的差分分組策略(Two-stage Differential Grouping，TSDG)，該策略選取變量所占比例較高的組內(nèi)變量個(gè)數(shù)為分組大小，確定組內(nèi)變量個(gè)數(shù).當(dāng)算法陷入局部最優(yōu)時(shí)，該策略通過自適應(yīng)調(diào)整組內(nèi)變量個(gè)數(shù)，使算法跳出局部最優(yōu).

如圖4所示8個(gè)變量為例，以變量為節(jié)點(diǎn)，直接相關(guān)作用為邊，與x1，x2，x5，x8直接相關(guān)的變量有3個(gè)，占總變量1/2；與x3，x4，x6直接相關(guān)的變量有4個(gè)，占總變量3/8；與x7直接相關(guān)的有6個(gè)變量，占總變量1/8.所以首先選擇分組大小為每組4個(gè)，以組內(nèi)貢獻(xiàn)度最大原則進(jìn)行變量的分組.在迭代過程中，算法由于陷入局部最優(yōu)而無法跳出時(shí)，通過自適應(yīng)調(diào)整組內(nèi)變量個(gè)數(shù)，形成自適應(yīng)的分組策略.使算法跳出局部最優(yōu).

圖4 分組策略Fig.4 Grouping strategy

3.3 資源分配

LSGO問題分組后，相比分組之前，組件的數(shù)量會(huì)變多.目前，將計(jì)算資源平均分配給每一個(gè)組件是較為方便的一種策略，但是每一個(gè)組件對(duì)適應(yīng)度值的影響程度不同，若采用平均分配計(jì)算資源給每一個(gè)子組件，會(huì)使貢獻(xiàn)度較高的組件和貢獻(xiàn)度低的組件分配一樣的計(jì)算資源，顯然這種分配策略是不合理的.為了解決計(jì)算資源均勻分配的不足，本文主要采用CC算法下有效的資源分配(Resource Allocation in CooperativeCo-Evolution，CCFR)[20].CCFR采用公式(15)計(jì)算組件貢獻(xiàn)度，根據(jù)組件在最近兩次迭代中的平均貢獻(xiàn)度來分配計(jì)算資源.

(15)

其中，fb和fbi分別表示組件ci在上一次迭代和當(dāng)前迭代的最佳適應(yīng)度值，F(xiàn)ci是組件在上一個(gè)迭代的貢獻(xiàn)值.

圖5 自適應(yīng)資源分配Fig.5 Self-adaptive resource allocation

CCFR資源分配過程如圖5所示，假設(shè)該問題包含3個(gè)組件，圖中每一個(gè)圓代表一個(gè)組件，圓的大小表示貢獻(xiàn)度大小.具體步驟如下：

Step1.在初始階段，根據(jù)公式(15)計(jì)算3組件的初始貢獻(xiàn)度；

Step2.在第2階段選擇最大貢獻(xiàn)度組件C2，分配計(jì)算資源；

Step3.循環(huán)Step 2，判斷C2貢獻(xiàn)度是否小于C3；

Step4.若小于，在下一階段選擇此時(shí)最大貢獻(xiàn)度組件C3，分配計(jì)算資源；

Step5.循環(huán)Step 2-Step 4，當(dāng)算法達(dá)到最大迭代次數(shù)時(shí)，算法停止.

3.4 基于自適應(yīng)兩階段分組的差分協(xié)同進(jìn)化算法

DECC-TSL算法流程如圖6所示.它與傳統(tǒng)的協(xié)同差分分組算法主要有兩個(gè)不同之處：1)在第1階段分組，判斷變量貢獻(xiàn)度的正負(fù)性，避免貢獻(xiàn)度值相反的變量分到同一個(gè)組件中；2)在變量相關(guān)性識(shí)別中檢測(cè)出非獨(dú)立變量組，選取變量所占比例較高的組內(nèi)變量個(gè)數(shù)為分組大小，確定組內(nèi)變量個(gè)數(shù).在整個(gè)優(yōu)化過程中，通過自適應(yīng)的調(diào)整組內(nèi)變量的個(gè)數(shù)，避免算法陷入局部最優(yōu).DECC-TSL算法具體步驟如下：

圖6 自適應(yīng)兩階段差分分組算法流程圖Fig.6 Flow of adaptive two-stage differential grouping algorithm

Step1.根據(jù)公式(12)對(duì)變量貢獻(xiàn)度FX進(jìn)行計(jì)算；

Step2.判斷FX的正負(fù)性；

Step3.若FX>0，則將該變量分到正促進(jìn)組，反之進(jìn)入負(fù)抑制組；

Step4.根據(jù)公式(13)和公式(14)，分別對(duì)正相關(guān)組和負(fù)相關(guān)組內(nèi)的變量進(jìn)行變量相關(guān)性檢測(cè)；

Step5.依次選取變量作為被檢測(cè)變量，判斷被檢測(cè)變量和剩余變量之間是否存在相關(guān)性；

Step6.若存在，將相關(guān)變量與被檢測(cè)變量放置在同一個(gè)組件內(nèi).若不存在，則將被檢測(cè)變量放在獨(dú)立變量組內(nèi)；

Step7.重復(fù)Step 5、Step 6，直到所有變量分到獨(dú)立變量組和非獨(dú)立變量組；

Step8.對(duì)于非獨(dú)立變量組，選取組內(nèi)數(shù)量比例較高的一組作為組內(nèi)變量個(gè)數(shù)，自適應(yīng)的調(diào)整組內(nèi)變量個(gè)數(shù)；

Step9.在資源分配階段，給獨(dú)立變量組中每個(gè)變量分配相同的計(jì)算資源進(jìn)行優(yōu)化，對(duì)非獨(dú)立變量組采用CCFR資源分配，在每次進(jìn)化周期中，選擇對(duì)適應(yīng)度值貢獻(xiàn)度最大的組件進(jìn)行優(yōu)化；

Step10.重復(fù)Step 8、Step 9，直到達(dá)到函數(shù)的最大評(píng)估次數(shù)，算法停止.

4 仿真結(jié)果與分析

本文采用標(biāo)準(zhǔn)測(cè)試函數(shù)集CEC2010[21]驗(yàn)證算法的有效性.CEC2010函數(shù)集一共包含20個(gè)測(cè)試函數(shù)，依據(jù)變量的不同性質(zhì)，可以將20個(gè)測(cè)試函數(shù)分為4大類：

1)F1-F3：此函數(shù)只包含獨(dú)立變量，稱該函數(shù)為完全可分離函數(shù)；

2)F4-F13：此函數(shù)同時(shí)包含獨(dú)立變量和非獨(dú)立變量組，稱該函數(shù)為第1類部分可分離函數(shù)；

3)F14-F18：此函數(shù)同時(shí)包含多個(gè)非獨(dú)立變量組，稱該函數(shù)為第2類部分可分離函數(shù)；

4)F19-F20：此函數(shù)僅包含一個(gè)非獨(dú)立組，稱該函數(shù)為完全不可分離函數(shù).

4.1 分組有效性分析

為了驗(yàn)證所提分組策略的有效性，利用CEC 2010測(cè)試集提出的20個(gè)測(cè)試函數(shù)對(duì)TSDG的性能進(jìn)行研究.將TSDG與DG、 DG2、RDG分別在D=(1000，2000，3000，4000，5000)維下進(jìn)行對(duì)比.

兩個(gè)指標(biāo)用于評(píng)價(jià)分組方法的性能：用于分解問題的函數(shù)評(píng)估的數(shù)量(FEs)和分組精度(Acc).FEs個(gè)數(shù)越少，Acc越高，則分組方法的性能越好.

分組方法的分組精度定義如下：

(16)

(17)

其中，sep代表函數(shù)包含可分變量的總數(shù)，nonsep代表函數(shù)包含不可分變量的總數(shù)，sep′和nonsep′分別代表真正正確識(shí)別出的可分變量和不可分變量.

如表1-表5所示，分別為TSDG在1000-d、2000-d、3000-d、4000-d、5000-d下與其他3種策略的對(duì)比結(jié)果.在分組精度上與其他策略對(duì)比，所提出的TSDG可以正確地分解除F6、F11之外的其他測(cè)試函數(shù)；在函數(shù)評(píng)估數(shù)量上與其他策略對(duì)比，僅F19在DG使用的評(píng)估次數(shù)少于TSDG，在其他19個(gè)函數(shù)上TSDG使用的FEs最少.

如表1所示1000維下TSDG與其他3種策略對(duì)比，針對(duì)分組精度，與DG相比，DG雖然在F6和F11上分組準(zhǔn)確率略好于TSDG，但在F4、F7、F8、F13、F18函數(shù)上TSDG分組準(zhǔn)確率高于DG；與DG2、RDG相比，雖然DG2、RDG在F6可分變量上分組精度略高于TSDG，但是DG2在F6上使用的FES是TSDG的100多倍，RDG在F6上使用的FES是TSDG的10多倍.此外，TSDG在F3上能進(jìn)行正確的分組，但DG2、RDG則不能.在剩余函數(shù)分組精度相同時(shí)，對(duì)比FEs，DG除了在F19上使用的FES略少于TSDG，在其他函數(shù)上使用的FES均高于TSDG，尤其是在完全可分離的函數(shù)F1-F3上，DG使用的FES是TSDG的300多倍；與DG2和RDG相比，TSDG使用的FES遠(yuǎn)少于DG2和RDG使用的FES，這是因?yàn)門SDG在變量識(shí)別時(shí)，分別對(duì)正促進(jìn)組和負(fù)抑制組兩組內(nèi)變量同時(shí)進(jìn)行識(shí)別，極大地減少了FEs在時(shí)間上的成本.

表1 CEC2010測(cè)試集在1000維上分組結(jié)果Table 1 Grouping results on the 1000-d CEC2010 functions

如表2所示2000維下TSDG與其他3種策略對(duì)比，在分組精度上與1000維結(jié)果一樣，但是隨著維度的增加，變量之間的相關(guān)性更加復(fù)雜，使得DG在F4、F7、F8、F13、F18函數(shù)上分組精度相比于在1000維上的分組精度減少，導(dǎo)致分組精度下降.在分組精度相同的函數(shù)中，對(duì)比FES，TSDG使用的FES遠(yuǎn)少于其他3種策略使用的FES.與DG相比，在完全可分函數(shù)F1-F3上，DG使用的FES是TSDG的600多倍，在部分可分函數(shù)上，DG使用的FES同樣高于TSDG使用的FES；與DG2相比，在可分離函數(shù)上DG2使用的FES是TSDG的300多倍，在部分可分離函數(shù)上，DG2使用的FES同樣高于TSDG使用的FES；與RDG相比，在可分離函數(shù)上RDG使用的FES略高于TSDG，但在部分可分離函數(shù)上，RDG使用的FES是TSDG的2-3倍；由此可見隨著維度的不斷增加，DG、DG2和RDG使用的FES遠(yuǎn)遠(yuǎn)高于TSDG使用的FES，且成倍數(shù)增加趨勢(shì).

表2 CEC2010測(cè)試集在2000維上分組結(jié)果Table 2 Grouping results on the 2000-d CEC2010 functions

同上述分析一致，表3-表5分別為TSDG在3000-d、4000-d、5000-d下與其他3種策略的對(duì)比結(jié)果.隨著維度的增加，由于變量之間的相關(guān)性更加復(fù)雜，導(dǎo)致分組精度下降、FES增加.

表3 CEC2010測(cè)試集在3000維上分組結(jié)果Table 3 Grouping results on the 3000-d CEC2010 functions

表4 CEC2010測(cè)試集在4000維上分組結(jié)果Table 4 Grouping results on the 4000-d CEC2010 functions

表5 CEC2010測(cè)試集在5000維上分組結(jié)果Table 5 Grouping results on the 5000-d CEC2010 functions

但是TSDG在更高維度下測(cè)試20個(gè)函數(shù)，仍然能將18個(gè)測(cè)試函數(shù)進(jìn)行正確分組，同時(shí)TSDG在19個(gè)測(cè)試函數(shù)上使用了更少的FES.綜上所述，TSDG可以用更少的FEs將大部分測(cè)試函數(shù)的可分離變量和不可分離變量能進(jìn)行正確的分解，TSDG性能更好.

4.2 DECC-TSL收斂性分析

4.2.1 對(duì)比測(cè)試算法

為了分析所提算法的收斂速度和收斂精度，將提出的DECC-TSL算法與兩階段學(xué)習(xí)的粒子群算法(TPLSO)[22]、改進(jìn)的資源分配協(xié)同算法(CCFR2)[23]、隨機(jī)分組的差分算法(DECC-G)[24]、基于貢獻(xiàn)度分組策略(FCRACC)[25]、進(jìn)行仿真對(duì)比.其中，3個(gè)算法采用了不同的分組策略進(jìn)行優(yōu)化求解，具體區(qū)別如表6所示.

表6 算法分類描述

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

在實(shí)驗(yàn)對(duì)比中，測(cè)試問題維度D=1000，函數(shù)的最大評(píng)估次數(shù)FEs=3×106，實(shí)驗(yàn)中每一個(gè)算法對(duì)于每一個(gè)測(cè)試函數(shù)均獨(dú)立運(yùn)行25次.DECC-TSL算法種群大小N=50，分組閾值ξ=50.實(shí)驗(yàn)結(jié)果如表7所示，部分收斂曲線如圖7所示.

為了更直觀的了解DECC-TSL算法的性能，采用Wilcoxon秩和檢驗(yàn)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析，顯著性水平為0.05.秩和檢驗(yàn)結(jié)果在表7底部用符號(hào)“-”、“+”和“≈”表示，分別表示劣于、優(yōu)于和相當(dāng)于DECC-TSL的結(jié)果.

表7和圖7分別為改進(jìn)算法與其他4種算法的對(duì)比結(jié)果和對(duì)照?qǐng)D.其中，“Mean”和“Std”是每一個(gè)測(cè)試函數(shù)25次獨(dú)立運(yùn)行后所獲得的平均值和標(biāo)準(zhǔn)差，黑體字的值表示算法獲得的值在對(duì)應(yīng)測(cè)試函數(shù)上是最好的.從表7中我們可以看到在測(cè)試函數(shù)F3、F4、F7、F8、F9、F10、F12、F13、F14、F15、F16、F17、F20上，本文提出的DECC-TSL算法性能明顯優(yōu)于其他4種算法.在20個(gè)測(cè)試函數(shù)上，DECC-TSL算法性能僅在完全可分離函數(shù)F1、F2上優(yōu)化性能次于DECC-G和TPLSO，而在剩余18個(gè)測(cè)試函數(shù)(包含部分可分離函數(shù)和完全不可分離函數(shù))都優(yōu)于DECC-G和TPLSO，這是因?yàn)門PLSO采用無分組的競(jìng)爭(zhēng)學(xué)習(xí)策略，算法容易陷入局部最優(yōu)，而DECC-G采用隨機(jī)分組策略，破壞了變量之間的相關(guān)性，導(dǎo)致算法收斂性降低，而DECC-TSL通過兩階段分組，考慮變量之間相關(guān)性，提高了算法的收斂性.有效的避免算法陷入局部最優(yōu).

表7 測(cè)試函數(shù)仿真結(jié)果

圖7 各算法對(duì)比收斂圖Fig.7 Algorithms convergence graph

與CCFR2算法對(duì)比，雖然DECC-TSL和CCFR2在進(jìn)化過程中均采取了分治策略，但是DECC-TSL僅在F5、F18兩個(gè)函數(shù)上優(yōu)化性能次于CCFR2，在剩余17個(gè)測(cè)試函數(shù)(F2除外，在F2函數(shù)上兩種算法表現(xiàn)相似)都要優(yōu)于CCFR2.這是因?yàn)镃CFR2是對(duì)種群進(jìn)行的隨機(jī)分組，未考慮變量之間的相關(guān)性，DECC-TSL通過檢測(cè)變量之間相關(guān)性，將其分為獨(dú)立變量組和非獨(dú)立變量組，在資源分配時(shí)，分別采用不同分配策略，使算法更加具有有效性和適用性.

與FCRACC算法對(duì)比，因?yàn)閮蓚€(gè)算法均對(duì)變量進(jìn)行多次分組的操作，所以從實(shí)驗(yàn)結(jié)果看出，對(duì)于部分函數(shù)，兩個(gè)算法最終收斂結(jié)果相差不大.但是DECC-TSL在F1、F2、F3、F4、F7、F8、F9、F11、F16這9個(gè)函數(shù)上優(yōu)于FCRACC.這是因?yàn)镕CRACC僅考慮變量貢獻(xiàn)度的大小，而DECC-TSL考慮變量貢獻(xiàn)度對(duì)函數(shù)適應(yīng)度值的正負(fù)性影響，避免將具有相反貢獻(xiàn)度的變量分為一組，從而提高了算法的收斂性.

分析表7底部Wilcoxon秩和檢驗(yàn)的統(tǒng)計(jì)結(jié)果，DECC-TSL算法相比于其他4種算法顯示出更好的優(yōu)勢(shì).綜合以上分析可以說明DECC-TSL算法與文中其他4種算法相比，具有較強(qiáng)的收斂性和適用性，在解決LSGO問題時(shí)，提高了算法的性能.

5 結(jié) 論

目前協(xié)同進(jìn)化是解決大規(guī)模全局優(yōu)化問題的一種有效策略，但是在處理變量之間存在相互作用的LSGO問題時(shí)，現(xiàn)有的協(xié)同進(jìn)化分組機(jī)制不能進(jìn)行有效的分組，最終導(dǎo)致算法優(yōu)化性能不佳.針對(duì)這一情況，本文提出一種基于自適應(yīng)兩階段分組的差分協(xié)同進(jìn)化算法.該算法通過對(duì)決策變量進(jìn)行變量貢獻(xiàn)度的提取并判斷其貢獻(xiàn)度的正負(fù)性，利用正負(fù)性進(jìn)行第1階段分組，分為正促進(jìn)組和負(fù)抑制組；然后分別對(duì)兩組內(nèi)的變量進(jìn)行變量相關(guān)性的識(shí)別，統(tǒng)計(jì)并記錄每個(gè)變量與之直接相關(guān)的變量個(gè)數(shù)，確定組內(nèi)變量個(gè)數(shù).為了驗(yàn)證算法的有效性，通過實(shí)驗(yàn)將本文提出的DECC-TSL算法與TPLSO、CCFR2、DECC-G、FCRACC 4個(gè)算法進(jìn)行對(duì)比，通過20個(gè)Benchmark測(cè)試函數(shù)，實(shí)驗(yàn)結(jié)果驗(yàn)證了DECC-TSL算法在求解LSGO問題上，提高了算法的收斂性和有效性.