云環(huán)境下求解大規(guī)模優(yōu)化問(wèn)題的協(xié)同差分進(jìn)化算法

譚旭杰，鄧長(zhǎng)壽，吳志健，彭虎，朱鵲橋

差分進(jìn)化算法(differential evolution，DE)是一種基于實(shí)數(shù)編碼的全局優(yōu)化算法[1]，因其簡(jiǎn)單、高效以及具有全局并行性等特點(diǎn)，近年來(lái)已成功應(yīng)用到工業(yè)設(shè)計(jì)和工程優(yōu)化等領(lǐng)域。研究人員對(duì)DE算法進(jìn)行了改進(jìn)和創(chuàng)新并取得了一些成果。比如Brest等[2]構(gòu)造了控制參數(shù)的自適應(yīng)性方法并提出了自適應(yīng)DE算法(jDE)。Wang等[3]提出了復(fù)合DE算法(CoDE)，其將精心選擇的3種變異策略和3組控制參數(shù)按照隨機(jī)的方法進(jìn)行組合。這些研究成果主要集中于低維問(wèn)題(30維)，然而當(dāng)面向高維問(wèn)題(1 000維)時(shí)，這些DE算法的性能將急劇下降，而且搜索時(shí)間隨著維數(shù)成指數(shù)增長(zhǎng)，求解極為困難，“維災(zāi)難”問(wèn)題依然存在[4]。

為了有效求解高維優(yōu)化問(wèn)題，學(xué)者們提出不同的策略，其中具有代表性的是協(xié)同進(jìn)化(cooperative coevolution，CC)[5]。CC 采用“分而治之”的思想，首先將高維復(fù)雜問(wèn)題分解成低維簡(jiǎn)單的子問(wèn)題；其次對(duì)每個(gè)子問(wèn)題分別進(jìn)行求解；最后通過(guò)所有子問(wèn)題解的協(xié)同機(jī)制，得到整個(gè)問(wèn)題的解。Yang等[6]提出的隨機(jī)分組策略，可將兩個(gè)相關(guān)變量以極大的概率放在同一組，在大規(guī)模優(yōu)化問(wèn)題中得到較精確的解。研究人員已將CC應(yīng)用到多個(gè)領(lǐng)域，如大規(guī)模黑盒優(yōu)化問(wèn)題[7]、SCA 問(wèn)題[8]、FII算法[9]、CCPSO 算法[10]、DG2 算法[11]，然而它們?cè)谇蠼飧呔S優(yōu)化問(wèn)題時(shí)，采用串行方式求解，因此，問(wèn)題求解需要較長(zhǎng)的計(jì)算時(shí)間，很難在有效時(shí)間內(nèi)提供滿意的解。近年來(lái)云計(jì)算已應(yīng)用到大規(guī)模信息處理領(lǐng)域中，如在機(jī)器學(xué)習(xí)[12]、蟻群算法[13]、CRFs算法[14]、差分進(jìn)化算法[15-16]、圖數(shù)據(jù)分析[17]、分類算法[18]等獲得了成功。因此，有必要將云計(jì)算的分布式處理能力與CC的優(yōu)勢(shì)相結(jié)合，為大規(guī)模優(yōu)化問(wèn)題的求解提供新方法。

研究人員已在Google開源平臺(tái)Hadoop的Map-Reduce模型之上提出了一些分布式差分進(jìn)化算法[19-20]。實(shí)踐中研究人員發(fā)現(xiàn)，MapReduce模型是一個(gè)通用的批處理計(jì)算模型，缺乏并行計(jì)算數(shù)據(jù)共享的有效機(jī)制，對(duì)迭代運(yùn)算無(wú)法提供有效支持。因此，基于MapReduce模型的差分進(jìn)化算法需要通過(guò)頻繁讀寫文件來(lái)交換數(shù)據(jù)，降低了其效率[21]。

Spark云平臺(tái)是伯克利大學(xué)提出的分布式數(shù)據(jù)處理框架[22]，在許多領(lǐng)域獲得了成功應(yīng)用。Spark提出了一種全新的數(shù)據(jù)抽象模型RDD(彈性分布式數(shù)據(jù)模型)。RDD模型能夠有效支持迭代計(jì)算、關(guān)系查詢、批處理以及流失數(shù)據(jù)處理等功能，使得Spark可以應(yīng)用于多種大規(guī)模處理場(chǎng)景。由于RDD模型基于內(nèi)存計(jì)算，避免了MapReduce模型頻繁讀寫磁盤數(shù)據(jù)的弊端，提高了效率。

本文基于Spark云平臺(tái)提出了合作協(xié)同的差分進(jìn)化算法。SparkDECC算法采用“分治”策略，將高維優(yōu)化問(wèn)題按隨機(jī)分組策略分解成低維子問(wèn)題，并封裝成RDD；在RDD中，每個(gè)子問(wèn)題獨(dú)立并行進(jìn)化若干代；利用協(xié)同機(jī)制將所有子問(wèn)題合并成完整問(wèn)題，評(píng)價(jià)出最優(yōu)個(gè)體。SparkDECC算法在13個(gè)標(biāo)準(zhǔn)函數(shù)進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明該算法是有效可行的。

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

差分進(jìn)化算法是一種仿生的群體進(jìn)化算法，具體操作如下[23]。

1) 種群初始化

DE算法首先在[xmin，xmax]范圍內(nèi)隨機(jī)初始化NP個(gè)D維向量xi的種群，其中NP為種群大小，D為種群的維度，xmin為最小值，xmax為最大值，i∈[1, NP]。

2) 變異

變異主要是通過(guò)種群中個(gè)體之間的差向量來(lái)改變個(gè)體的值。DE算法根據(jù)基準(zhǔn)向量的選取和差分向量數(shù)目不同，有多種變異操作。本文的目標(biāo)向量xi主要通過(guò)最常用的變異算子產(chǎn)生，如式(1)。

式中：i, r1, r2, r3∈[1, NP]且互不相同的4個(gè)隨機(jī)整數(shù)；vi,g為目標(biāo)向量xi在第g代時(shí)產(chǎn)生的變異向量；縮放因子F∈[0, 1]。

3) 交叉

變異后，DE算法通過(guò)交叉概率在目標(biāo)向量xi與變異向量vi進(jìn)行交叉，產(chǎn)生新的試驗(yàn)向量ui。具體操作如式(2)所示。

式中：交叉概率 CR∈[0, 1]，j∈[1, D]，隨機(jī)數(shù)rnd1∈[0, 1]，隨機(jī)整數(shù) rnd2∈[1, D]。

4) 選擇

DE算法主要通過(guò)“貪婪”原則對(duì)個(gè)體進(jìn)行選擇，較優(yōu)個(gè)體進(jìn)入下一代。具體操作如式(3)所示。

式中f (xi,g)為個(gè)體xi,g的適應(yīng)度值。

DE算法通過(guò)變異、交叉、選擇之后，根據(jù)循環(huán)代數(shù)或求解精度來(lái)結(jié)束搜索。

2 合作協(xié)同的云差分進(jìn)化算法Spark-DECC

2.1 Spark云平臺(tái)

為了更加高效地支持迭代運(yùn)算，Spark平臺(tái)在MapReduce云模型的基礎(chǔ)上進(jìn)行了擴(kuò)展[24]。Spark平臺(tái)提供了兩個(gè)重要的抽象：RDD和共享變量。RDD本質(zhì)是一個(gè)容錯(cuò)的、并行的數(shù)據(jù)結(jié)構(gòu)，提供了一種只讀、分區(qū)記錄并存放在內(nèi)存的數(shù)據(jù)集合。Broadcast是一種共享變量，將數(shù)據(jù)緩存在每個(gè)結(jié)點(diǎn)上，不再需要傳遞數(shù)據(jù)，減少通信開銷，提高通信性能。Spark平臺(tái)的API為RDD提供了兩種算子：轉(zhuǎn)換算子(Transformations)和動(dòng)作算子(Actions)，其中，轉(zhuǎn)換算子都是惰性的，對(duì)RDD分區(qū)的每個(gè)數(shù)據(jù)執(zhí)行相同的操作，并返回新的RDD；而動(dòng)作算子將觸發(fā)RDD上的運(yùn)算，并將值返回給主控結(jié)點(diǎn)。RDD內(nèi)部實(shí)現(xiàn)機(jī)制基于迭代器，使得數(shù)據(jù)訪問(wèn)更高效，避免了中間結(jié)果對(duì)內(nèi)存的消耗，使迭代計(jì)算更加高效快速。

DE是一種基于群體的進(jìn)化算法，具有內(nèi)在并行性的特點(diǎn)。因此，DE能與Spark的并行性充分融合。Spark在主控結(jié)點(diǎn)通過(guò)Parallelize方法將種群并行初始化，并采用“鍵–值”的方式存放在內(nèi)存中，即：

式中：m是子種群的數(shù)目；keyi是整數(shù)，表示第i個(gè)子種群的編號(hào)；valuei是第i個(gè)子種群。DE在Spark上的具體實(shí)現(xiàn)如圖1所示。

圖1 基于Spark的DE算法Fig. 1 DE based on spark

Spark將內(nèi)存中的數(shù)據(jù)按“鍵–值”對(duì)的方式抽象成RDD，并根據(jù)keyi值將子種群分區(qū)保存在不同的結(jié)點(diǎn)上。利用RDD的并行操作算子對(duì)各子種群并行進(jìn)化若干代，再通過(guò)collect算子合并生成新的種群。循環(huán)結(jié)束后通過(guò)動(dòng)作算子reduce獲取整個(gè)種群的最優(yōu)值。

2.2 SparkDECC算法

CC框架處理大規(guī)模優(yōu)化問(wèn)題優(yōu)勢(shì)明顯。然而，隨著種群規(guī)模的增加，CC框架所需時(shí)間快速增加。為了提高CC框架的收斂速度，將云計(jì)算的優(yōu)勢(shì)與CC框架相結(jié)合，提出了基于Spark的合作協(xié)同進(jìn)化算法-SparkDECC算法。

SparkDECC算法首先將高維問(wèn)題按隨機(jī)分組方法分解成若干個(gè)低維子問(wèn)題，一個(gè)子問(wèn)題對(duì)應(yīng)一個(gè)子種群，保留每個(gè)子問(wèn)題在完整問(wèn)題的位置信息；按keyi值將低維子種群分發(fā)到RDD中相應(yīng)的分區(qū)，每個(gè)分區(qū)中的子種群并行執(zhí)行DE算法的變異、交叉、選擇等操作，其中子種群在計(jì)算個(gè)體適應(yīng)度值時(shí)，選取上一輪的最優(yōu)個(gè)體合作組成完整的種群并進(jìn)行局部尋優(yōu)。低維子種群在對(duì)應(yīng)的分區(qū)中進(jìn)化若干代后，按照其位置信息合并成新的完整種群，并通過(guò)全局搜索返回最優(yōu)個(gè)體。SparkDECC算法的流程圖如圖2所示。

圖2 SparkDECC算法流程圖Fig. 2 Flowchart of SparkDECC algorithm

SparkDECC算法的具體步驟如下。

1) 初始化參數(shù)：種群規(guī)模NP、縮放因子F、交叉概率CR、問(wèn)題的維度D、子問(wèn)題的維度DimSub、子種群數(shù)M=D/DimSub、子種群的位置信息subscript、分區(qū)數(shù)Num、進(jìn)化代數(shù)Gen、子種群合并輪數(shù)Cycles；

2) 初始化種群Pop，通過(guò)cache()將數(shù)據(jù)存放在內(nèi)存中；

3) 獲取種群最優(yōu)個(gè)體向量bestInd、最優(yōu)值best；

4) 將控制合并輪數(shù)的變量c賦值為0;

5) 判斷合并輪數(shù)c是否小于等于Cycles，若是，則循環(huán)結(jié)束；否則，繼續(xù)；

6) 變量c自動(dòng)加1;

7) 利用parallelize方法將Pop按隨機(jī)分組策略分解成M個(gè)低維的子種群，將子種群的位置信息存放subscript中，并按key值將子種群分發(fā)到相應(yīng)分區(qū)；

8) 通過(guò)broadcast變量將Pop廣播至每個(gè)結(jié)點(diǎn)；

9) 各子種群并行進(jìn)化Gen代，具體的計(jì)算過(guò)程為：

① 變異操作，執(zhí)行式(1)；

② 交叉操作，執(zhí)行式(2)；

③ 選擇操作，執(zhí)行式(3)，其中子種群在計(jì)算適應(yīng)度值時(shí)，按照其位置信息替換掉bestInd中的部分解。

10) 利用collect動(dòng)作算子將所有低維子種群按協(xié)同機(jī)制合并成完整種群，并更新Pop；

11) 對(duì)Pop進(jìn)行全局搜索并返回最優(yōu)個(gè)體bestInd；

12) 轉(zhuǎn)到 5)；

13) 循環(huán)結(jié)束，通過(guò)reduce返回最優(yōu)值best。

在上述SparkDECC算法中，包含兩個(gè)循環(huán)，即6)、10)。外循環(huán)6)控制問(wèn)題的全局優(yōu)化，內(nèi)循環(huán)10)控制子問(wèn)題的局部?jī)?yōu)化。

上述算法的時(shí)間復(fù)雜度主要集中在10)，其主要功能是在Num個(gè)分區(qū)中同步并行優(yōu)化M個(gè)低維子問(wèn)題。一個(gè)低維子問(wèn)題的時(shí)間復(fù)雜度為O(M×NP)，M個(gè)低維子問(wèn)題在一個(gè)分區(qū)里按串行方式進(jìn)化Gen代，運(yùn)行Cycles輪的時(shí)間復(fù)雜度為O(M×NP×Gen×Cycles)。在上述算法中，略去其他步的時(shí)間復(fù)雜度。因此，SparkDECC算法在每個(gè)分區(qū)的時(shí)間復(fù)雜度為O(M×NP×Gen×Cycles)/Num。

3 數(shù)值實(shí)驗(yàn)與分析

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

為了測(cè)試SparkDECC算法求解大規(guī)模優(yōu)化問(wèn)題的性能，本文選取了文獻(xiàn)[25]中13個(gè)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)。其中f1～f8為單模函數(shù)，f9～f13為多模函數(shù)，f4和f5為不可分解的函數(shù)，其他函數(shù)都是可分解的。函數(shù)的詳細(xì)說(shuō)明詳見文獻(xiàn)[25]。

3.2 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)采用Spark云模型，每個(gè)節(jié)點(diǎn)的配置如下：64 bit corei7 CPU，主頻3.4 GB，內(nèi)存8 GB，Ubuntu13.10操作系統(tǒng)，安裝使用Hadoop2.2.0和Spark1.2.0，編程環(huán)境為IntellJ IDEA14.1.2，使用Scala和Java語(yǔ)言。

為了驗(yàn)證SparkDECC的性能以及影響其性能的各個(gè)因素，實(shí)驗(yàn)時(shí)SparkDECC中問(wèn)題的維度D=1 000，子問(wèn)題的維度DimSub=100，問(wèn)題規(guī)模NP=100，F(xiàn)=0.5，CR=0.9，每個(gè)子種群獨(dú)立運(yùn)行的代數(shù)MaxGen=100，合并輪數(shù)Cycles=50。為了驗(yàn)證SparkDECC算法的可擴(kuò)展性，將問(wèn)題的維度D擴(kuò)展到5 000，其他參數(shù)保持不變。

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

表1為 SparkDECC 與 OXDE[26]、CoDE、jDE、PSO[27]算法的平均最優(yōu)值和標(biāo)準(zhǔn)方差的結(jié)果對(duì)比。5種算法的參數(shù)設(shè)置一致，各算法獨(dú)立運(yùn)行25次。采用了Wilcoxon秩和檢驗(yàn)方法對(duì)4種算法的實(shí)驗(yàn)結(jié)果進(jìn)行了統(tǒng)計(jì)分析，顯著性水平為0.05，其中，“–”表示劣于，“+”表示優(yōu)于，“≈”表示相當(dāng)于。

表1中，SparkDECC與其他3種DE算法進(jìn)行對(duì)比，結(jié)果表明，SparkDECC 在 f1、f5、f6、f10～f13共7個(gè)函數(shù)能快速收斂到最優(yōu)結(jié)果，實(shí)驗(yàn)數(shù)據(jù)優(yōu)于其他3種算法；SparkDECC算法在f3、f8和f9等3個(gè)函數(shù)的收斂出現(xiàn)了停滯，實(shí)驗(yàn)結(jié)果弱于其他算法；在不可分解函數(shù)f4上各算法的運(yùn)行效果相當(dāng)；f2要劣于jDE，優(yōu)于OXDE和CoDE；帶噪聲函數(shù)f7的實(shí)驗(yàn)結(jié)果劣于CoDE，優(yōu)于jDE，與OXDE相當(dāng)。

表1 SparkDECC、OXDE、CoDE、jDE、PSO算法的平均值、標(biāo)準(zhǔn)差和Wilcoxon秩的檢驗(yàn)結(jié)果Table 1 Comparison of SparkDE, OXDE, CoDE, jDE and PSO algorithms for solving the results

SparkDECC與PSO算法的結(jié)果對(duì)比，實(shí)驗(yàn)結(jié)果表明SparkDECC算法除函數(shù)f8外其他都優(yōu)于PSO，說(shuō)明SparkDECC算法總體性能優(yōu)于PSO。

函數(shù)收斂曲線圖主要用來(lái)表示算法求解最優(yōu)值的一種趨勢(shì)走向，函數(shù)曲線下降得越快，收斂性能越好。為了比較 4 種不同 DE 算法在 f1、f3、f5、f6、f9、f10、f11、f13等函數(shù)的收斂性能(受篇幅限制，僅選擇這8個(gè)函數(shù))，選取了各算法獨(dú)立運(yùn)行20次中的平均收斂數(shù)據(jù)，收斂取值以10為底的對(duì)數(shù)形式，曲線圖如圖3所示。從圖3可以看出SparkDECC算法的收斂能力較強(qiáng)，在函數(shù)f1、f10、f11上的收斂曲線呈直線下降，收斂性能強(qiáng)；函數(shù)f5、f6、f13在進(jìn)化的前期有很好的收斂速度，但在后期出現(xiàn)了一定程度的局部收斂；函數(shù)f3，f9在整個(gè)進(jìn)化過(guò)程中處于局部收斂，收斂性能弱，收斂效果要劣于其他算法。

圖3 收斂圖Fig. 3 Convergence graph

綜合以上實(shí)驗(yàn)數(shù)據(jù)分析表明，SparkDECC算法能有效地求解大規(guī)模優(yōu)化問(wèn)題，提高了DE算法的收斂精度和收斂速率。

加速比[28]是衡量算法并行性的有效指標(biāo)，其定義如式(5)所示。

圖4 加速比Fig. 4 Acceleration ratio

3.4 協(xié)同方式對(duì)算法性能的影響

SparkDECC算法對(duì)子種群進(jìn)行局部尋優(yōu)后，需要合并所有子種群并進(jìn)行全局搜索。SparkDECC算法按照原模型進(jìn)行組合，整個(gè)種群保持原來(lái)的結(jié)構(gòu)。為了分析子種群合并機(jī)制對(duì)SparkDECC算法性能的影響，本文選取了兩種不同的協(xié)同方式進(jìn)行對(duì)比實(shí)驗(yàn)。這兩種協(xié)同方式衍生出兩種算法，即SparkDECC-1算法和SparkDECC-2算法，這兩種算法在SparkDECC算法的基礎(chǔ)上，子種群按不同的協(xié)同方式進(jìn)行組合。其中，SparkDECC-1算法在所有子種群組合之前，首先將所有子種群的個(gè)體按其適應(yīng)度值升序排序，最后將所有子種群按線性方式組合成完整的種群；SparkDECC-2算法將所有子種群中的個(gè)體按隨機(jī)方式組合成完整的種群。為了驗(yàn)證3種不同的SparkDECC算法的性能，選擇了相同的參數(shù)設(shè)置，分別在13個(gè)函數(shù)上獨(dú)立運(yùn)行20次，實(shí)驗(yàn)結(jié)果如表2所示。

表2的實(shí)驗(yàn)結(jié)果表明，SparkDECC算法在f1、f2、f4、f5、f10、f11、f12、f13等 8 個(gè)函數(shù)的實(shí)驗(yàn)結(jié)果要優(yōu)于其他兩種協(xié)同方式。其中，SparkDECC-1算法在f3、f6、f8、f9等 4 個(gè)函數(shù)優(yōu)于 SparkDECC 算法，SparkDECC-2算法中的所有函數(shù)都劣于Spark-DECC算法?？傊琒parkDECC算法的其他組合方式不能有效地提高算法的收斂精度，且增加了種群個(gè)體的排列組合運(yùn)算，算法的運(yùn)行時(shí)間隨之增加。因此，SparkDECC算法選擇最初的協(xié)同方式合并子種群，維持原種群的結(jié)構(gòu)，能有效提高算法的精度和時(shí)間。

表2 SparkDECC 3種不同協(xié)同方式的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of SparkDECC on three different cooperative modes

3.5 子種群數(shù)對(duì)算法的影響

為了分析子種群數(shù)對(duì)SparkDECC性能的影響，分別選取了不同數(shù)目的子種群進(jìn)行對(duì)比實(shí)驗(yàn)，如1、2、5、10、20等5種不同的子種群。根據(jù)2.2節(jié)中的子種群數(shù)的計(jì)算公式，計(jì)算子種群的維度，如問(wèn)題維度為1 000，則上述5種不同子種群的維度分別為 1 000、500、200、1 00、50。算法的其他參數(shù)設(shè)置保持一致，分別在13個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行了20次，表3和表4分別記錄了5種不同子種群數(shù)下的平均最優(yōu)值和平均運(yùn)行時(shí)間。

表3 和表 4 的結(jié)果分析發(fā)現(xiàn)，f1、f2、f6、f8、f10、f12、f13共7個(gè)函數(shù)的收斂精度隨子種群數(shù)的增加而逐漸增強(qiáng)。f3、f4、f9這3個(gè)函數(shù)解的精度在種群不分解的情況下達(dá)到最優(yōu)，種群維度的分解并沒(méi)有提高解的精度。f7的解在子種群數(shù)為5時(shí)達(dá)到最優(yōu)，再增加子種群數(shù)并不會(huì)提高解的精度。f5、f11的解在子種群數(shù)為10時(shí)達(dá)到最優(yōu)。因此，對(duì)于可分解函數(shù)，SparkDECC的種群多樣性隨子種群數(shù)的增加逐漸增強(qiáng)，提高了解的收斂性。然后，隨子問(wèn)題數(shù)目增多，子問(wèn)題之間的交互時(shí)間隨之增加，從而增加了函數(shù)的收斂時(shí)間。表4的結(jié)果顯示，函數(shù)的運(yùn)行時(shí)間與子問(wèn)題數(shù)成正比，與2.2節(jié)中的時(shí)間復(fù)雜度相吻合。當(dāng)子問(wèn)題數(shù)增加到20時(shí)，13個(gè)函數(shù)總的平均時(shí)間是1個(gè)子問(wèn)題的11.5倍。因此，Spark-DECC應(yīng)從收斂時(shí)間和收斂精度兩方面綜合考慮選取合適的子種群數(shù)。

3.6 子種群進(jìn)化代數(shù)對(duì)算法的影響

SparkDECC算法在子種群進(jìn)化若干代后，需要合并成新的全局最優(yōu)解。因此，為了探索子種群局部尋優(yōu)的代數(shù)Gen對(duì)SparkDECC算法的影響，本文選取了10、20、50、100、250等5種情況分別進(jìn)行實(shí)驗(yàn)。5種情況的其他參數(shù)一致并設(shè)置相同的函數(shù)評(píng)價(jià)次數(shù)，分別獨(dú)立運(yùn)行25次，平均運(yùn)行時(shí)間及結(jié)果分別如表5和表6所示。

表3 SparkDECC在不同子種群數(shù)的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of SparkDECC in different number of sub-populations

表4 SparkDECC在不同子種群數(shù)的平均運(yùn)行時(shí)間Table 4 The average running time of SparkDECC in different number of sub-populations ms

表6 的結(jié)果顯示，f1、f2、f7、f8、f9、f10等 6 個(gè)函數(shù)的求解精度隨進(jìn)化代數(shù)的增加逐漸提高。f3和f4兩個(gè)函數(shù)增加局部尋優(yōu)的代數(shù)并不能提高解的精度，函數(shù)易陷入局部最優(yōu)。f6、f12和f13等3個(gè)函數(shù)的結(jié)果在進(jìn)化代數(shù)為100時(shí)達(dá)到最優(yōu)。f5和f11兩個(gè)函數(shù)在進(jìn)化代數(shù)為50時(shí)達(dá)到最優(yōu)，進(jìn)化代數(shù)的增加并不能提高解的質(zhì)量。由2.2節(jié)中的時(shí)間復(fù)雜度可知，在評(píng)價(jià)次數(shù)相同的情況下，不同進(jìn)化代數(shù)Gen的函數(shù)優(yōu)化時(shí)間幾乎相同。但從表5的結(jié)果顯示，SparkDECC算法的優(yōu)化時(shí)間隨參數(shù)Gen的增加而逐漸減少。其主要原因是，由2.2節(jié)中的算法可知，SparkDECC算法在評(píng)價(jià)次數(shù)相同的情況下，合并輪數(shù)Cycle的值隨進(jìn)化代數(shù)Gen變大而逐漸變小，減少了廣播變量執(zhí)行的次數(shù)，因此，函數(shù)的優(yōu)化時(shí)間會(huì)相應(yīng)減少，但總的優(yōu)化時(shí)間相差無(wú)異。

表5 進(jìn)化代數(shù)對(duì)SparkDECC優(yōu)化時(shí)間的影響Table 5 Optimization time of SparkDECC with generations ms

總之，SparkDECC算法的收斂精度與子問(wèn)題的進(jìn)化代數(shù)和合并輪數(shù)關(guān)系緊密，增加子問(wèn)題的進(jìn)化代數(shù)提高了子問(wèn)題的局部尋優(yōu)能力。子問(wèn)題的合并輪數(shù)改善了問(wèn)題多樣性。但是，在評(píng)價(jià)次數(shù)相同的情況下，子問(wèn)題的合并輪數(shù)隨子種群進(jìn)化代數(shù)的增加而減少。因此，為了在全局搜索和局部尋優(yōu)之間達(dá)到平衡，并能在有效時(shí)間內(nèi)提高算法的收斂精度，我們可以選擇合適的進(jìn)化代數(shù)，合理分配計(jì)算資源。

表6 進(jìn)化代數(shù)對(duì)SparkDECC優(yōu)化性能的影響Table 6 Performance affection of SparkDECC with generations

3.7 SparkDECC算法的可擴(kuò)展性分析

為了驗(yàn)證SparkDECC算法的可擴(kuò)展性，本文將文獻(xiàn)[25]中的13個(gè)測(cè)試函數(shù)擴(kuò)展到5 000維進(jìn)行實(shí)驗(yàn)。子問(wèn)題的維度 S=100，F(xiàn)=0.5，CR=0.9，F(xiàn)ES=5 000 D，問(wèn)題規(guī)模NP=100，算法獨(dú)立運(yùn)行10次。OXDE、CoDE和jDE 3種算法在5 000維的實(shí)驗(yàn)參數(shù)與SparkDECC的參數(shù)一致，實(shí)驗(yàn)結(jié)果如表7。

表7 SparkDECC、OXDE、CoDE、jDE算法在5 000維的平均值、標(biāo)準(zhǔn)差和Wilcoxon秩和檢驗(yàn)結(jié)果Table 7 Comparison of SparkDECC, OXDE, CoDE, jDE algorithms for solving the results in 5 000 dimension

表7的結(jié)果顯示，隨著維度的增加，算法的求解性能下降，搜索時(shí)間成倍增長(zhǎng)。SparkDECC算法在 f1、f2、f5、f6、f7、f8、f10、f11、f12、f13等 10 個(gè)函數(shù)的最優(yōu)值都優(yōu)于其他3種算法，但在f3和f9兩個(gè)函數(shù)的最優(yōu)值都劣于其他3個(gè)算法，4種算法在函數(shù)f10上的結(jié)果相似。OXDE、CoDE和jDE 3種算法在13個(gè)測(cè)試函數(shù)的維度擴(kuò)展到5 000時(shí)的運(yùn)行時(shí)間分別是25.15天、16.68天和16.85天。SparkDECC算法的運(yùn)行時(shí)間為4.71天，大大提升了算法的收斂時(shí)間。實(shí)驗(yàn)結(jié)果顯示，SparkDECC算法在5 000維的整體性能優(yōu)于其他3種算法，具有很好的可擴(kuò)展性。

4 結(jié)束語(yǔ)

本文利用新型的迭代云計(jì)算模型，提出新的基于Spark的合作協(xié)同云差分進(jìn)化算法(SparkDECC)。SparkDECC算法按隨機(jī)分組策略將高維問(wèn)題分解成多個(gè)同維的低維子問(wèn)題，將每個(gè)子問(wèn)題與RDD模型中的分區(qū)一一對(duì)應(yīng)，每個(gè)子問(wèn)題并行執(zhí)行DE算法，子問(wèn)題獨(dú)立進(jìn)化若干代后，更新最優(yōu)個(gè)體，提高種群的多樣性。利用Scala語(yǔ)言在Spark云模型上實(shí)現(xiàn)了SparkDECC，通過(guò)13個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的對(duì)比實(shí)驗(yàn)，結(jié)果表明SparkDECC求解精度高，速度快，可擴(kuò)展性好。此外，選擇6個(gè)測(cè)試函數(shù)進(jìn)行加速比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明加速比與分區(qū)數(shù)量幾乎是線性的，加速效果良好。后續(xù)工作將在SparkDECC的基礎(chǔ)上探索新的分組策略，并不斷改進(jìn)其協(xié)同機(jī)制，提高算法的收斂效率和求解精度。

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

[2]BREST J, GREINER S, BOSKOVIC B, et al. Self-adapting cont-rol parameters in differential evolution: a comparati-ve study on numerical benchmark problems[J]. IEEEtransactions on evolutionary computation, 2006, 10(6): 646–657.

[3]WANG Yong, ZHANG Qingfu. Differential evolution with composite trial vector generation strategies and co-ntrol parameters[J]. IEEE transactions on evolutionary computation, 2011, 2(15): 55–66.

[4]FRANS V D B, ENGELBRECHT A P. A cooperative approach to particle swarm optimization[J]. IEEE transactions on evolutionary computation, 2004, 8(3): 225–239.

[5]POTTER M A, De JONG K A. A cooperative coevolutionary approach to function optimization[J]. Lecture notes in computer science, 1994, 866: 249–257.

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

[7]MEI Y, OMIDVAR M N, LI X, et al. A competitive divideand-conquer algorithm for unconstrained large-scale blackbox optimization[J]. ACM transactions on mathematical software, 2016, 42(2): 13.

[8]GUAN X, ZHANG X, WEI J, et al. A strategic conflict avoidance approach based on cooperative coevolution-ary with the dynamic grouping strategy[J]. International journal of systems science, 2016, 47(9): 1995–2008.

[9]HU X M, HE F L, CHEN W N, et al. Cooperation coevolution with fast interdependency identification for large scale optimization[J]. Information sciences, 2017, 381: 142–160.

[10]LI X, YAO X. Cooperatively coevolving particle swarms for large scale optimization[J]. IEEE transactions on evolutionary computation, 2012, 16(2): 210–224.

[11]OMIDVAR M N, YANG M, MEI Y, et al. DG2: a faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE transactions on evolutionary computation, 2017, 21(6): 929–942.

[12]MENG X, BRADLEY J, YUVAZ B, et al. Mllib: machine learning in apache spark[J]. Journal of machine research,2015, 17(34): 1235–1241.

[13]王詔遠(yuǎn), 王宏杰, 邢煥來(lái), 等. 基于Spark的蟻群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(10): 2777–2780.WANG Zhangyuan, WANG Hongjie, XING Huanlai, et al.An implement of ant colony optimization based on spark[J].Journal of computer applications, 2015, 35(10): 2777–2780.

[14]朱繼召, 賈巖濤, 徐君, 等. SparkCRF: 一種基于 Spark 的并行CRFs算法實(shí)現(xiàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(8):1819–1828.ZHU Jizhao, JIA Yantao, XU Jun, et al. SparkCRF: a parallel implementation of crfs algorithm with spark[J]. Journal of computer research and development, 2016, 53(8):1819–1828.

[15]DENG C, TAN X, DONG X, et al. A parallel version of differential evolution based on resilient distributed datasets model[C]//Bioinspired Computing-Theories and Applications. Springer, Berlin, Heidelberg, 2015: 84–93.

[16]TEIJEIRO D, PARDO X C, GONZáLEZ P, et al. Implementing Parallel Differential Evolution on Spark[C]//European Conference on the Applications of Evolutionary Computation. Springer International Publishing, 2016:75–90.

[17]王虹旭, 吳斌, 劉旸. 基于Spark的并行圖數(shù)據(jù)分析系統(tǒng)[J]. 計(jì)算機(jī)科學(xué)與探索, 2015, 9(9): 1066–1074.WANG Hongxu, WU Bin, LIU Yang. Parallel graph data analysis based on spark[J]. Journal of frontiers of computer science and technology, 2015, 9(9): 1066–1074.

[18]劉志強(qiáng), 顧榮, 袁春風(fēng), 等. 基于SparkR 的分類算法并行化研究[J]. 計(jì)算機(jī)科學(xué)與探索, 2015, 9(11): 1281–1294.LIU Zhiqiang, GU Rong, YUAN Chunfeng, et al. Parallelization of classification algorithms based on sparkR[J].Journal of frontiers of computer science and technology,2015, 9(11): 1281–1294.

[19]袁斯昊, 鄧長(zhǎng)壽, 董小剛, 等. 求解大規(guī)模優(yōu)化問(wèn)題的云差分進(jìn)化算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(10):2949–2953.YUAN Sihao, DENG Changshou, DONG Xiaogang, et al.Cloud computing based differential evolution algorithm for large-scale optimization problems[J]. Application research of computers, 2016, 33(10): 2949–2953.

[20]董小剛, 鄧長(zhǎng)壽, 袁斯昊, 等. MapReduce模型下的分布式差分進(jìn)化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(12):2695–2701.DONG Xiaogang, DENG Changshou, YUAN Sihao, et al.Distributed differential evolution algorithm based on mapreduce model[J]. Journal of Chinese computer systems,2016, 37(12): 2695–2701.

[21]譚旭杰, 鄧長(zhǎng)壽, 董小剛, 等. SparkDE: 一種基于RDD云計(jì)算模型的并行差分進(jìn)化算法[J]. 計(jì)算機(jī)科學(xué), 2016,43(9): 116–119.TAN Xujie, DENG Changshou, DONG Xiaogang, et al.SparkDE: a parallel version of differential evolutionbased on resilient distributed datasets model in cloud computing[J]. Computer science, 2016, 43(9): 116–119.

[22]ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient di-stributed datasets: a fault-tolerant abstraction for inmemory cluster computing[C]//Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012: 2–2.

[23]DAS S, SUGANTHAN P N. Differential evolution: a survey of the state-of-the-art[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 4–31.

[24]王賢偉, 戴青云, 姜文超, 等. 基于Mapreduce的外觀設(shè)計(jì)專利圖像檢索方法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012,33(3): 626–632.WANG Xianwei, DAI Qingyun, JIANG Wenchao, et al.Retrieval of design patent images based on mapreduce model[J]. Journal of Chinese computer systems, 2012,33(3): 626–632.

[25]YAO X, LIU Y, LIN G. Evolutionary programming ma-de faster[J]. IEEE transactions on evolutionary computation,2000, 3(2): 82–102.

[26]WANG Y, CAI Z, ZHANG Q. Enhancing the search ability of differential evolution through orthogonal crossover[J]. Information sciences, 2012, 185(1): 153–177.

[27]范德斌, 鄧長(zhǎng)壽, 袁斯昊, 等. 基于MapReduce模型的分布式粒子群算法[J]. 山東大學(xué)學(xué)報(bào): 工學(xué)版, 2016, 46(6):23–30.FAN Debin, DENG Chanshou, YUAN Sihao, et al. Distributed particle swarm optimization algorithm based on mapreduce[J]. Journal Shandong university: engineering science, 2016, 46(6): 23–30.

[28]TAGAWA K, ISHIMIZU T. Concurrent differential evolution based on MapReduce[J]. International journal of computers, 2010, 4(4): 161–168.