王彬，任露，王曉帆，曹雅娟

（1.西安理工大學(xué)計算機科學(xué)與工程學(xué)院，陜西 西安 710048；2.西安理工大學(xué)陜西省網(wǎng)絡(luò)計算與安全技術(shù)重點實驗室，陜西 西安 710048）

0 引言

隨著現(xiàn)代科技的不斷發(fā)展，為了得到最佳的解決方案，需要對工程問題進行數(shù)學(xué)建模求解，但是許多大規(guī)模優(yōu)化問題在建模之后目標函數(shù)不可導(dǎo)，導(dǎo)致傳統(tǒng)的優(yōu)化算法難以求解。為了更好地求解大規(guī)模優(yōu)化問題，研究者不斷探索并設(shè)計出更加高效的進化算法[1-10]。求解大規(guī)模優(yōu)化問題有2 種主流進化方法，具體介紹如下。

1) 基于非分解的方法

文獻[11]提出了多軌道搜索算法，該算法有3 個全局搜索能力和局部搜索能力不同的搜索算子，在進化過程中，使用這3 個搜索算子對目標空間進行搜索，3 個搜索算子在種群進化過程中相輔相成，使全局搜索和局部搜索能夠得到均衡。文獻[12]提出了多后代采樣算法，具體是在種群進化的開始為每種算法分配相同的計算資源，在之后的進化過程中，根據(jù)種群中個體的適應(yīng)度值對每種算法進行評價，然后計算出2 種算法在進化過程中的參與率，根據(jù)參與率計算出下一輪優(yōu)化過程中每種算法被分配的計算資源，不斷進化直到計算資源用盡。與其他算法相比，其性能較好，但是多后代采樣算法對優(yōu)化算子的選擇比較敏銳，不同優(yōu)化算子會影響算法的性能。

2) 基于分解的方法

比較典型的是合作協(xié)同進化（CC,cooperative coevolution）算法，即對優(yōu)化問題進行分解，將高維優(yōu)化問題分解為多個低維優(yōu)化問題，然后對每個子組件進行優(yōu)化。合作協(xié)同進化算法的性能取決于分解策略，目前研究者已經(jīng)提出了多種分解策略。文獻[13]為了提高遺傳算法的性能，首次提出將問題進行分解，使用的分解策略是單維分解和折半分解。單維分解是將M維問題分解成M個一維問題；折半分解是將整個優(yōu)化問題一分為二。在30 維測試函數(shù)上進行測試，對于可分的問題，該算法的性能比遺傳算法好；對于不可分的問題，由于在分解過程中2 種策略并沒有考慮變量之間的相關(guān)性，因此算法性能不如遺傳算法好，并且隨著優(yōu)化問題維度的增加，這2 種分解策略會失效。文獻[14]將CC框架應(yīng)用到粒子群優(yōu)化算法，使用的分解策略是固定分組策略，它將一個M維的優(yōu)化問題分解成S個k維的問題，即M=Sk，但是這種固定分組策略只對低于30 維的優(yōu)化問題有效。以上幾種分解策略都需要預(yù)先設(shè)置問題分解的數(shù)目，且對高維問題效果不佳。文獻[15]提出了隨機分組策略，可以對變量進行隨機分組，這種分組方法增大了將有關(guān)聯(lián)性的變量分到同一子組件的概率，但是隨著有關(guān)聯(lián)性變量的數(shù)目增加，隨機分組的性能就會下降。文獻[16]提出了多層次的協(xié)同進化算法用來解決上述問題，設(shè)置了一個分解器池，里面不同的分解器代表不同的分組數(shù)目，記錄每個分解器的性能，在進化過程中根據(jù)記錄的歷史數(shù)據(jù)自適應(yīng)地選擇合適的分解器，根據(jù)分解器中的分組數(shù)目，將目標向量分解成設(shè)定的子組件。雖然多層次的協(xié)同進化克服了隨機分組手動設(shè)置分組大小的缺點，但是在實際應(yīng)用中并不廣泛。文獻[17]提出了差分分組（DG,differential grouping）策略，能夠檢測變量之間的關(guān)聯(lián)性。DG與其他的分組策略相比具有良好的性能，但它只能檢測變量之間的直接相關(guān)性，并不會檢測間接相關(guān)性，在一些測試集上的效果并不理想。文獻[18]提出了擴展的差分分組（XDG,extended differential grouping）策略來解決DG 的缺陷。

總之，合作協(xié)同進化算法利用分組策略將大規(guī)模優(yōu)化問題進行分解，加快了進化過程的收斂速度，但當(dāng)決策變量部分可分離或完全不可分時，協(xié)同進化的優(yōu)化效果并不理想，因為合作協(xié)同進化只是根據(jù)變量之間的相關(guān)性將變量進行一個大的分類，并沒有考慮分類之后每個子組件中變量之間的相互作用是否影響進化過程?；谏鲜龇治觯疚奶岢隽艘环N基于協(xié)方差分析的合作協(xié)同進化差分進化算法，簡稱CC-COV-DE 算法。

本文的主要研究工作如下。

1) 在協(xié)同進化利用分組策略對決策變量進行分組之后，針對子組件中變量之間的相關(guān)性對種群進化過程的影響進行了分析。

2) 在種群進化開始時對問題進行傳統(tǒng)分解，在優(yōu)化每個子組件時利用協(xié)方差分析子組件中變量的數(shù)據(jù)特征，構(gòu)造協(xié)方差矩陣，根據(jù)特征向量旋轉(zhuǎn)原始坐標系，目的是消除組內(nèi)變量之間的相關(guān)性，提高算法的性能。

3) 提出了一種基于協(xié)方差分析的合作協(xié)同差分進化算法，并在CEC 2014 測試集上與最新的差分進化算法進行了仿真實驗，實驗結(jié)果證實了所提算法的有效性、高效性以及可競爭性。

1 相關(guān)工作

1.1 差分進化

進化算法作為元啟發(fā)式的算法，其思想類似于達爾文進化論，簡單易懂，操作容易，可被廣泛應(yīng)用于求解優(yōu)化問題。差分進化（DE,differential evolution）是經(jīng)典的進化算法[19]。

差分進化的操作包括突變、交叉和選擇，使用一組實參向量xi=(xi1,…,xiD),i=1,2,…,N表示，其中，D是問題的維度，N是種群規(guī)模。在種群開始進化之前，隨機初始化種群中的個體；在進化過程中，通過突變操作產(chǎn)生突變向量，根據(jù)交叉操作產(chǎn)生實驗向量，最后通過選擇操作為下一代選擇適應(yīng)度值較好的個體。差分進化的操作過程如下。

1) 突變

在進化過程中，通過目標向量xi,G來產(chǎn)生突變向量vi,G。突變計算式為

其中，r1,r2,r3是從[1,N]中隨機選擇的不同于i的下標，F(xiàn)是比例因子。

2) 交叉

根據(jù)目標向量xi,G和突變向量vi,G，生成實驗向量ui,G。二項式交叉操作為

其中，rand(0,1)是0 和1 之間的隨機數(shù)，jrand是從[1,D]中隨機選擇的決策變量的下標，CR 是交叉率。

3) 選擇

使用貪婪選擇，在目標向量xi,G和實驗向量ui,G之間根據(jù)目標函數(shù)的適應(yīng)度值選擇較好的個體進入下一代，選擇計算式為

由DE 的操作過程可以看出，當(dāng)控制參數(shù)較少時，操作相對簡單，可以在低維優(yōu)化問題中快速找到最優(yōu)解。

1.2 合作協(xié)同進化框架

合作協(xié)同進化框架最早在1994 年被提出來解決大規(guī)模優(yōu)化問題，首先將高維問題分解成多個低維問題，然后對子組件進行循環(huán)優(yōu)化。合作協(xié)同進化算法的偽代碼如算法1 所示。

算法1合作協(xié)同進化算法

1) 初始化種群

2) 使用分組策略將原始問題分解為m個低維度子組件

3) seti=1 開始一個新循環(huán)

4) 使用特定的進化算法來優(yōu)化第i個子組件并分配固定數(shù)量的評估時間

5) ifi＜mtheni++，轉(zhuǎn)至步驟3)

6) end if

7) if 滿足停止條件do

8) 停止循環(huán)

9) else

10) 轉(zhuǎn)至步驟2)進行下一個循環(huán)

11) end if

1.3 擴展的差分分組策略

協(xié)同進化求解大規(guī)模優(yōu)化問題的核心是如何對問題進行分解，即選擇什么樣的分解策略。

實際工程領(lǐng)域中的優(yōu)化問題較復(fù)雜，擴展的差分分組策略彌補了差分分組在識別相互關(guān)系上的缺陷，XDG 可以識別變量之間的2 種交互類型，如圖1 所示。類型Ⅰ表示變量之間的直接交互關(guān)系，如x1和x2、x2和x3；類型Ⅱ表示變量之間的間接交互關(guān)系，如x1和x3。

圖1 變量之間的2 種交互類型

變量之間的相關(guān)性定義如下。

定義1f(x)是部分可分函數(shù)，對于 ?a,b1≠b2,δ∈R,δ≠ 0，如果滿足

則xp和xq不可分離，存在相關(guān)性，其中，

定義2在目標函數(shù)f(x)中，如果xi和xj是直接相關(guān)的，則存在候選解x*滿足式（6），直接相關(guān)定義為xi?xj。

如果xi和xj是間接相關(guān)的，則所有的候選解滿足式(7)。

XDG 根據(jù)決策變量之間的相互關(guān)系將原問題進行分解。在對問題進行分解時，其可分成3 個階段。第一階段是確定變量之間的直接交互，根據(jù)定義1 以成對的方式檢測變量之間的交互關(guān)系。第二階段是為了確定變量之間的間接交互關(guān)系，搜索第一階段中子組件中的重疊部分，合并公共變量的子組件。第三階段是將所有可分離變量分配到同一子組件中，XDG 分組之后每個子組件之間是可分離的，但是子組件中的變量是相互關(guān)聯(lián)的。

2 算法設(shè)計

2.1 研究動機

1) 高維問題中子組件變量相關(guān)增加

求解大規(guī)模優(yōu)化問題最常見的方法是將高維問題分解成低維問題，即根據(jù)決策變量的相關(guān)性對所求解的優(yōu)化問題，將有相互依賴關(guān)系的變量分配到同一個子組件中，然后對所有的子組件循環(huán)進行優(yōu)化。在問題完全可分的情況下，利用這種方法求解優(yōu)化問題可以很大程度地提高算法的性能，加快種群的收斂。

如果在沒有端元光譜庫的情況下，利用該模型進行混合像元分解，通常的做法是先估計出端元的個數(shù)，然后提取端元光譜，再結(jié)合高光譜遙感圖像，進行基于最小二乘或其他方法的豐度估計[14]。然而，基于這種解混方法的思路，如果端元數(shù)目估計不準確，會給解混結(jié)果造成一定的影響。另外，由于同類地物端元存在光譜變異性，如果每種地物僅用一條標準的光譜定義也會造成結(jié)果不精確。為了解決上述問題，需要擺脫傳統(tǒng)解混方法思路的束縛，尋找新的解混框架和模型，獲取更精確的解混結(jié)果。隨著端元光譜庫的普及以及稀疏表示理論的發(fā)展，可以借助端元光譜庫對高光譜遙感圖像進行稀疏解混，具體介紹如下。

如圖2 所示，低維優(yōu)化問題中，由于維度較低，部分子組件內(nèi)部變量關(guān)聯(lián)性較低的概率較大，其中，子組件1、子組件2 和子組件4 中的變量有相互依賴關(guān)系，子組件3 中的變量在進化過程中不依賴其他任何變量，因而在進化過程中子組件3 的進化速度要比其他組件的進化速度快。

圖2 低維優(yōu)化問題的變量相關(guān)

如圖3 所示，高維優(yōu)化問題中，隨著維度的增加，子組件中被分配到的變量數(shù)目增加，相較于圖2中的低維問題，分組之后，每個子組件中變量之間的關(guān)聯(lián)概率增加。

圖3 高維優(yōu)化問題的變量相關(guān)

2) 子組件的變量相關(guān)性影響協(xié)同進化

協(xié)同進化在種群的進化過程中并沒有考慮子組件中相互作用的變量對進化的影響，利用差分算法對子組件進行優(yōu)化的過程中，變量之間的相互性會影響子組件的優(yōu)化。

相關(guān)變量對DE 搜索過程的影響如圖4 所示。理想情況下，根據(jù)DE 的突變計算式在目標空間中產(chǎn)生的突變向量是vi,G，但是向量與向量是相關(guān)的，向量的變化會影響向量。在進化過程中，會受的影響，從而產(chǎn)生突變向量vi,G，vi,G相較于vi,G偏離了全局最優(yōu)向量。

圖4 相關(guān)變量對DE 搜索過程的影響

3) 采用協(xié)方差分析的坐標旋轉(zhuǎn)消除變量相關(guān)

基于種群個體分布特征向量的坐標旋轉(zhuǎn)如圖5所示。優(yōu)秀個體往往分布在最優(yōu)解周圍，在假設(shè)高斯分布的基礎(chǔ)上，利用優(yōu)秀個體的位置，計算種群的協(xié)方差矩陣，估計分布的特征向量和特征值；利用計算出來的特征向量，對原坐標系（X,Y）進行旋轉(zhuǎn)，并重新計算個體在新坐標系（X′,Y′）下的坐標；在新坐標系下，個體的變量相關(guān)性降低，進化效率得到提高；將在新坐標系下進化得到的個體映射回原坐標系，計算適用度。

圖5 基于種群個體分布特征向量的坐標旋轉(zhuǎn)

2.2 CC-COV-DE 算法設(shè)計

在進化過程中，根據(jù)變量之間的相關(guān)性對變量進行分組，當(dāng)子組件中相互依賴的變量數(shù)目有很多時，會受變量之間的相互依賴牽引，種群在進化過程中很容易陷入局部最優(yōu)。因此，為了提高算法的性能，提出了基于協(xié)方差分析的合作協(xié)同進化差分進化算法，在使用分組策略對決策變量進行分組之后，使用協(xié)方差分析每個子組件中變量的特征，根據(jù)特征向量對坐標進行旋轉(zhuǎn)，消除變量之間的相關(guān)性。

CC-COV-DE 算法的流程如圖6 所示。

圖6 CC-COV-DE 算法的流程

1) 利用XDG 策略根據(jù)變量之間的相關(guān)性對問題進行分解。

2) 在子組件優(yōu)化過程中，使用協(xié)方差對子組件中的變量進行特征分析，構(gòu)造協(xié)方差矩陣，對原始坐標系進行旋轉(zhuǎn)，使子組件中變量之間的關(guān)聯(lián)性可以消除，從而避免在進化過程中陷入局部最優(yōu)，導(dǎo)致種群進化過程停滯。

在差分進化優(yōu)化器中，對于子組件中的M個個體，計算協(xié)方差矩陣

其中，cov(i,j)是子組件中M個個體的第i和第j維度的協(xié)方差，計算式為

其中，R表示D×D正交矩陣特征坐標系，R的每一行都是協(xié)方差矩陣R′表示從特征坐標系到原始坐標系的變換，∧表示由特征值組成的對角矩陣。

在目標空間中，子組件中的個體xi在特征坐標系中可表示為

子組件中的個體使用DE 搜索方程在特征坐標系下生成候選解

其中，r1,r2,r3是從[1,M]中隨機選擇的。將特征坐標系中的候選解轉(zhuǎn)換到原始坐標系中，有

3) 根據(jù)目標函數(shù)的適應(yīng)度值，選出最優(yōu)的個體進入下一代。

CC-COV-DE 算法如算法2 所示，其中步驟21)～步驟29)是協(xié)方差分析的過程。

算法2CC-COV-DE 算法

輸入種群規(guī)模N，決策變量的維數(shù)D，當(dāng)前種群的更新代數(shù)gen，比例因子F，交叉率CR，函數(shù)的最大評價次數(shù)FESmax

輸出評價次數(shù)FES，最優(yōu)值Best

3 實驗結(jié)果分析

為了評估CC-COV-DE 的性能，本文在CEC 2014 基準測試函數(shù)集進行了仿真實驗。對比實驗表明CC-COV-DE 在解決大規(guī)模優(yōu)化問題的算法性能。

3.1 對比算法

為了證明CC-COV-DE 算法的有效性，本文引入了其他7 個對比算法，分別是基于合作協(xié)同進化的差分（CCDE）算法[20]、基于協(xié)方差分析的差分進化（COVDE）算法[21]、差分進化（DE）算法[19]、基于自適應(yīng)維度水平調(diào)整框架的差分進化（ADLADE）算法[3]、基于全局數(shù)值優(yōu)化組合策略的自適應(yīng)差分進化（CSDE）算法[22]、基于時變策略的差分進化（TVDE）算法[23]、基于合作協(xié)同進化和協(xié)方差的自適應(yīng)差分進化（A-CC/COV-DE）算法[24]。

3.2 測試函數(shù)

CC-COV-DE 在CEC 2014 上進行數(shù)值實驗，為了確保實驗結(jié)果的準確性，每個算法在測試函數(shù)上獨立運行50 次，CEC 2014 的測試函數(shù)可以分為4 類。F1～F3：單峰函數(shù)，不可分函數(shù)；F4～F16：簡單多峰函數(shù)，F(xiàn)8 和F10 為可分函數(shù)，其余為不可分函數(shù)；F17～F22：混合函數(shù)，不可分函數(shù)；F23～F30：復(fù)合函數(shù)，不可分函數(shù)。

3.3 參數(shù)設(shè)置

所有的仿真實驗都是在配置3.40 GHz CPU和8 GB RAM、Microsoft Windows 7 操作系統(tǒng)、Intel（R）Core? i7-3770M 的計算機端進行的，測試軟件是Microsoft Windows 7 操作系統(tǒng)下的MATLAB 2016a。其中，對比算法中公共參數(shù)設(shè)置如下。

1) 種群規(guī)模：N=2D。

3) 停止準則：為了使算法能夠正常停止運行，對于CEC 2014 測試函數(shù)集，函數(shù)的最大評價次數(shù)（FESmax）設(shè)置為10 000D。

4) 獨立運行次數(shù)：在本文實驗中，設(shè)置最大獨立運行次數(shù)（runmax）為50 次。

3.4 數(shù)值實驗

本節(jié)對8 個算法進行了對比實驗，利用收斂速度和數(shù)值分析對實驗結(jié)果進行了比較，體現(xiàn)了各個算法的差異。

1) 收斂速度。將8 個算法在不同測試函數(shù)上的收斂情況用曲線繪制出來，能夠很直觀地看出各個算法求解出的最優(yōu)解在收斂過程中的誤差值。

2) 數(shù)值分析。為了更加客觀地評價基于協(xié)方差分析的合作協(xié)同差分進化算法與對比算法之間的性能，本文使用Wilcoxon 秩和檢驗（0.05 顯著水平）對實驗結(jié)果進行統(tǒng)計分析，如果得到的p＞0.05，則認為比較的2 個算法沒有顯著的差異，否則就是有顯著的差異。根據(jù) Wilcoxon 秩和檢驗結(jié)果將CC-COV-DE 與其他對比算法之間的實驗結(jié)果標記為“+/–/～”，即CC-COV-DE 與其他算法的結(jié)果相比較好、較差或相近。表1 記錄了8 個算法在50維CEC2014 上的統(tǒng)計結(jié)果（運行50 次）。

從表1 中可以看出，CC-COV-DE 的實驗效果比CCDE 好，說明在使用XDG 根據(jù)決策變量之間的相關(guān)性對問題進行分解之后，子組件中變量的相關(guān)性影響種群的進化過程，利用協(xié)方差分析子組件中變量的數(shù)據(jù)特征，根據(jù)坐標旋轉(zhuǎn)可以消除變量之間的關(guān)聯(lián)性，提高了算法的性能。從CC-COV-DE 與其他對比算法的實驗結(jié)果可以看出，CC-COV-DE 的算法性能整體較好，尤其是在優(yōu)化混合函數(shù)和復(fù)合函數(shù)的效果方面，說明CC-COV-DE算法在優(yōu)化復(fù)雜函數(shù)時的性能良好，穩(wěn)健性強，與最新的算法相比具有可競爭性。

表1 8 個算法在50 維CEC2014 上的統(tǒng)計結(jié)果（運行50 次）

為了能夠更加清楚地比較CC-COV-DE 與對比算法的收斂速度，圖7 和圖8 分別給出了8 個算法在30 維和50 維的測試集上的平均收斂效果。從圖7和圖8 可以看出，CC-COV-DE 的整體收斂效果優(yōu)于其他對比算法。

圖7 8 個算法在30 維的測試集上的部分收斂效果

圖8 8 個算法在50 維的測試集上的平均收斂效果

通過計算CC-COV-DE 與其他7 個算法在30 維的CEC2014 測試函數(shù)集上的運行時間，并且比較其運行時間的比率，分析CC-COV-DE 的計算效率，實驗結(jié)果對比如圖9 所示，橫線代表運行時間的平均值。在30 個測試函數(shù)中，CC-COV-DE 的平均運行時間分別是CCDE、COVDE、DE、ADLADE、CSDE、TVDE、A-CC/COV-DE 的0.211 2、1、1.271 5、1.414 6、0.888 6、1.503 0、0.516 7 倍。通過分析可得，CC-COV-DE的計算成本高的原因是在優(yōu)化子組件的過程中需要計算協(xié)方差矩陣，計算的時間成本比其他算法稍大。

圖9 CC-COV-DE 與其他7 個算法在30 維的CEC2014 測試函數(shù)集上的運行時間比

4 結(jié)束語

協(xié)同進化算法在解決可分離問題時性能較好，然而隨著優(yōu)化問題維度的增加，子組件中有關(guān)聯(lián)性的變量相互作用關(guān)系更加復(fù)雜，若不消除子組件中變量之間的相關(guān)性，則會降低種群的進化速度。

本文提出的基于協(xié)方差分析的合作協(xié)同差分進化算法使用分組策略對優(yōu)化問題進行分解之后，在對子組件進行優(yōu)化的過程中利用協(xié)方差分析變量的數(shù)據(jù)特征，利用子組件中的變量構(gòu)造協(xié)方差矩陣，根據(jù)特征向量對原始坐標進行旋轉(zhuǎn)，消除子組件中變量之間的相關(guān)性，避免進化陷入局部最優(yōu)，加快種群的收斂速度。

與已有方法對比，本文使用協(xié)方差分析的方法消除子組件內(nèi)部變量之間的相關(guān)性，通過提高子組件內(nèi)部的進化效率，為子組件之間的協(xié)同進化提供更好的條件。協(xié)方差計算會增加一些時間開銷，但總體的綜合進化效率得到提升。在CEC 2014 測試函數(shù)集上進行仿真實驗，驗證了所提算法的有效性。