基于云計算平臺的差分進(jìn)化算法改進(jìn)研究

孫潔 連暢

摘 要： 針對差分進(jìn)化算法（DE）收斂速度慢、多樣性不足和易陷于局部最優(yōu)的問題，進(jìn)行基于云計算的差分進(jìn)化算法改進(jìn)研究。該方法基于云對差分算法的運行速度進(jìn)行改善，并以差分算法與輪盤賭相結(jié)合的方式改進(jìn)差分算法易陷于局部最優(yōu)的問題，即在交叉變異之后對種群以輪盤賭法的方式對其進(jìn)行篩選，使之能夠更好地對個體進(jìn)行最優(yōu)的選擇，從而實現(xiàn)全局最優(yōu)的結(jié)果。實驗結(jié)果表明，算法改進(jìn)后對基本差分算法的收斂速度慢，易陷入局部最優(yōu)的缺陷有了進(jìn)一步的改善，并很好地提高了最優(yōu)解的質(zhì)量，具有良好的實用性。

關(guān)鍵詞： 差分算法； 云計算； 輪盤賭； 多樣性； 全局最優(yōu)； 交叉變異

中圖分類號： TN911.1?34； TP301 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）17?0163?04

Abstract： Since the differential evolution （DE） algorithm has slow convergence speed and poor diversity， and is easy to fall into local optimum， an improved DE algorithm based on cloud computing platform is studied. This method based on cloud platform is used to improve the running speed of the DE algorithm. The DE algorithm and roulette method are combined to improve the problem that the DE algorithm is easy to fall into local optimum， in which the population after cross variation is screened by means of roulette method to select the optimal individual and realize the global optimum. The experimental results show that the improved algorithm can further improve the defects of the basic differential algorithm， greatly improve the quality of the optimal solution， and has high practicability.

Keywords： differential evolution algorithm； cloud computing； roulette； diversity； global optimum； cross variation

0 引 言

云計算云平臺中數(shù)據(jù)的開發(fā)和并行一般使用Hadoop平臺處理。Hadoop平臺由Hadoop分布式文件系統(tǒng)（HDFS）和MapReduce計算模型兩個板塊構(gòu)成。運行成本低，具有很強的擴容能力，運算效率高等是Hadoop平臺的主要特點。

差分進(jìn)化算法（Differential Evolution，DE）是近年來眾多新興算法中的一種[1]。最開始DE只用于一種多項式問題的解決，后來發(fā)現(xiàn)有關(guān)復(fù)雜優(yōu)化的問題也可以用DE研究解決，差分進(jìn)化算法更是一種群體智能指導(dǎo)的優(yōu)化搜索。

目前，很多學(xué)者也都對DE進(jìn)行了非常深入的研究，文獻(xiàn)[2]提出一種基于反向?qū)W習(xí)的跨種群的差分進(jìn)化改進(jìn)方法，以此提高算法對單峰函數(shù)的求解精度和穩(wěn)定性；文獻(xiàn)[3]提出一種基于反省學(xué)習(xí)的約束差分進(jìn)化算法，將反向?qū)W習(xí)的機器學(xué)習(xí)方法的框架運用到差分進(jìn)化算法中；文獻(xiàn)[4]提出一種改進(jìn)種群多樣性的雙變異差分進(jìn)化算法，通過引入BFS?best機制（基于排序的可行解選取遞減策略）對變異算子進(jìn)行改進(jìn)；文獻(xiàn)[5]采用DE 標(biāo)準(zhǔn)框架，當(dāng)群體適應(yīng)值方差小于一定閾值時，引入極值優(yōu)化算法，提出基于極值優(yōu)化的混合差分進(jìn)化算法；文獻(xiàn)[6]提出一種基于代理模型的差分進(jìn)化算法（DESSA），通過對多策略機制的運用實現(xiàn)對單一策略的改進(jìn)，將多個策略在每一步的進(jìn)化中進(jìn)行滲透。雖然上述方法都對差分算法進(jìn)行了改進(jìn)，并在不同程度上對算法的收斂速度進(jìn)行了提高，但收斂精度卻普遍不高，且有著使差分進(jìn)化算法擁有大量的迭代并易陷入局部最優(yōu)的問題。為了改進(jìn)這些缺陷，本文通過在差分進(jìn)化算法中加入輪盤賭的方式對其收斂速度進(jìn)一步進(jìn)行改善，改進(jìn)算法易限于局部最優(yōu)的問題。

1 云計算

1.1 HDFS分布式文件系統(tǒng)

HDFS分布式文件系統(tǒng)的架構(gòu)采用主/從（Master/Slave）架。系統(tǒng)一共由NameNode節(jié)點、Secondary?NameNode節(jié)點和DataNode節(jié)點構(gòu)成，其中NameNode和DataNode分別為系統(tǒng)的主、從節(jié)點，主、從節(jié)點都以Java程序的形式以Linux為操作系統(tǒng)運行在普通商用計算機上。

1.2 MapRaduce框架

MapRaduce模型一般采用“分而治之”的思想處理大規(guī)模的數(shù)據(jù)集，將所有待處理的大規(guī)模數(shù)據(jù)分割成許許多多的小數(shù)據(jù)塊，所有小數(shù)據(jù)塊經(jīng)map（）函數(shù)并行處理后輸出新的結(jié)果。

將[f]設(shè)為最小化適應(yīng)度函數(shù)，參數(shù)的候選方案是從適應(yīng)度函數(shù)以實數(shù)向量的方式確定，reduce（）函數(shù)將多任務(wù)處理后所得結(jié)果進(jìn)行匯總得到最終結(jié)果。MapRaduce框架分為兩個階段，分別為Map階段和Reduce階段，并依次自定義為map（）函數(shù)和reduce（）函數(shù)，并且這兩個函數(shù)將數(shù)據(jù)在數(shù)據(jù)集中相互轉(zhuǎn)化[7]，處理數(shù)據(jù)過程如圖1所示。

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

差分進(jìn)化算法通過交叉因子、縮放因子和種群大小3個控制參數(shù)實現(xiàn)。差分進(jìn)化算法不僅具有運算原理簡單、易于學(xué)習(xí)和容易實現(xiàn)的特點，并且其運行結(jié)果還具有可靠性、魯棒性和收斂速度快等優(yōu)點。

基本差分進(jìn)化算法大多以候選方案種群為基礎(chǔ)，方案由搜索空間對候選方案進(jìn)行搜索確定，將簡單的數(shù)學(xué)公式與種群中的現(xiàn)有方案相結(jié)合進(jìn)行實現(xiàn)。將原有方案和新方案相互比較，若新方案與原有方案相比有所進(jìn)化，則接受新方案；反之，則重新開始，重復(fù)以上過程。

假設(shè)候選方案的輸出適應(yīng)值為一個任意數(shù)值，目的是能夠找到搜索空間內(nèi)全部原始方案[p]中存在的方案[m]，且方案[m]滿足條件[fm

假設(shè)[X=x1，x2，…，xn∈Rn]為種群中的一個個體，基本差分進(jìn)化算法如下所述[8]：

1） 將搜索空間中的所有個體全部初始化。

2） 在種群初始化后的所有個體中，從中隨機選擇三個不同的個體，設(shè)置為[a]，[b]和[c]。[R∈1，2，…，n]為被選擇的隨機索引，并把待優(yōu)化問題維數(shù)設(shè)為[n]，對每個[i∈1，2，…，n]進(jìn)行如下迭代計算，可能產(chǎn)生的新個體設(shè)為[Y=y1，y2，…，yn]， [ri?U0，1]為生成的隨機數(shù)。如果[i=R]或[ri

3） 重復(fù)上述操作直到找到滿足最大迭代數(shù)或找到滿足適應(yīng)值的個體才會停止。

需要說明的是[F∈0，2]為縮放因子，[CR∈0，1]為交叉因子，種群大小取值[CR>3]。

3 差分進(jìn)化算法的改進(jìn)

種群大小[NP]、交叉因子[CR]和縮放因子[F]都決定了差分進(jìn)化算法優(yōu)化效果的優(yōu)良。

3.1 種群規(guī)模

實驗研究證明，如果種群過小會限制搜索，并且使搜索進(jìn)入停頓狀態(tài)，結(jié)果將得不到全局最優(yōu)解，但若種群過大則會產(chǎn)生大量的無效移動，這些大量的無效移動會導(dǎo)致算法的收斂速度減慢。一般情況下全局最優(yōu)解的概率的搜索會隨著種群規(guī)模的增大而增大，但是相對應(yīng)的計算量和計算時間也會隨著種群規(guī)模的上升而上升，即種群規(guī)模的不斷增大并非能夠不斷提高最優(yōu)解的質(zhì)量。有時最優(yōu)解精度降低的原因恰恰是因為種群規(guī)模的增加。綜上可知，為了有效提高算法的搜索效率，需要對種群規(guī)模進(jìn)行合理取值。

一般當(dāng)最大進(jìn)化代數(shù)確定，在解決低維簡單問題時，若要取得最好的最優(yōu)解精度，可以將種群規(guī)模的取值范圍放到[15，35]內(nèi)，此時不僅最優(yōu)解的精度高而且也能保持種群多樣性和算法收斂速度之間的相對平衡；當(dāng)解決高維復(fù)雜問題時，需要將種群規(guī)模的取值放在[30，50]范圍內(nèi)，此時的優(yōu)化效果較好[9]。

3.2 縮放因子

差分進(jìn)化算法的優(yōu)化性能每一個參數(shù)都可以控制。特別是縮放因子[F]，[F]取值的大小不僅影響算法收斂性的優(yōu)劣還決定算法收斂速度的快慢。若要收斂速度較快，則[F]需要控制在較小的取值范圍內(nèi)，隨著[F]取值的降低，取值越小，越會使種群過早地收斂于非最優(yōu)解；當(dāng)[F]取值在較大范圍內(nèi)時，同時對其他參數(shù)進(jìn)行合理的取值，則能保證收斂到問題的最優(yōu)解，但缺陷是會出現(xiàn)收斂速度較慢的現(xiàn)象。文獻(xiàn)[10]對測試函數(shù)做了大量的數(shù)值模擬實驗，研究發(fā)現(xiàn)[0.2，0.9]通常為[F]的最佳取值范圍。優(yōu)化問題含有10個以上設(shè)計變量時，[F]的最佳取值范圍為[0.2，0.6]。由此，文獻(xiàn)[11]通過大量的實驗研究提出一個方案，此方案較為簡單地對縮放因子[F]進(jìn)行自適應(yīng)調(diào)整，即按式（1）對第[N]代的縮放因子[FN]進(jìn)行動態(tài)調(diào)整：

3.3 交叉和變異

對原始種群進(jìn)行交叉和變異操作的目的是產(chǎn)生不同于原始個體的新個體，產(chǎn)生在原來基礎(chǔ)上有所進(jìn)化的新種群，使原始種群得到不斷的進(jìn)化優(yōu)化。在變異操作之后，加入新的選擇機制，防止交叉操作破壞變異出的優(yōu)良個體。

3.3.1 輪盤賭法

輪盤賭法是比較常見的隨機選擇方法中的一種，相似于一種輪盤賭游戲，原理很簡單，就是把個體適應(yīng)度按比例全部轉(zhuǎn)化為選擇的概率，即按個體所占總體的比例將圓盤上的區(qū)域依次劃分，其中個體所占比例越大，在圓盤中所劃分的區(qū)域就越大，相應(yīng)地被選中的機會也就越大。每轉(zhuǎn)動一次圓盤，在其停止后指針?biāo)赶虻纳刃螀^(qū)域為選中區(qū)域，所選中的區(qū)域?qū)?yīng)的個體即為被選中的個體。輪盤賭法的運行過程如下：

首先對問題中的[n]個位串分別編號，其次對個體所占總體比例的概率進(jìn)行計算，按照概率的大小對編號依次排序，由此可以改進(jìn)輪盤賭程序的運行效率。分別計算所有的累計概率，并對其進(jìn)行統(tǒng)計，統(tǒng)計情況如圖2所示，累計概率的序列為[0，0.1，0.3，0.35，…]。利用rand函數(shù)產(chǎn)生一個[0，1] 之間的隨機數(shù)，并判斷此隨機數(shù)在累計概率序列中的位置，選擇其在序列值中所能大于的最大值[m]，即需要大于前一個累計概率并小于下一個累計概率，就是對[m]號位串進(jìn)行隨機選擇[12]。例如，假設(shè)圖2中產(chǎn)生的隨機數(shù)為0.12，選擇0.12在序列值中所能大于的最大值0.1，且小于下一個累計概率0.3，所以2號位串被選中。

3.3.2 交叉和變異

差分進(jìn)化算法每進(jìn)化一代會產(chǎn)生新的進(jìn)化種群，對進(jìn)化后的種群實施交叉變異操作，使得種群中的個體產(chǎn)生變異優(yōu)化的結(jié)果，分別選出產(chǎn)生新個體中最優(yōu)秀的個體和原始種群中最優(yōu)秀的個體，將兩個最優(yōu)個體相比較，若產(chǎn)生的新的個體更優(yōu)秀，則代替原有個體進(jìn)行下一代進(jìn)化，若不能產(chǎn)生更優(yōu)秀的個體，則進(jìn)行下一次進(jìn)化。

4 實例仿真

本節(jié)實驗在Linux環(huán)境下建立Hadoop 2.0集群環(huán)境，實驗集群由4個節(jié)點組成，使用4臺普通聯(lián)想PC機，其中1臺服務(wù)器用來管理其他工作節(jié)點，作為HDFS的主控制節(jié)點（Master），另外3臺PC機用來完成MapReduce任務(wù)，作為HDFS的工作節(jié)點（Slave）。軟件環(huán)境使用Linux為操作系統(tǒng)，Hadoop作為云計算平臺，編程環(huán)境涉及eclipse以及JDK。用改進(jìn)的差分進(jìn)化算法進(jìn)行仿真實驗，初始實驗參數(shù)設(shè)置如下：最大迭代次數(shù)為1 000，種群大小為40，縮放因子[FN=0.2+rand0，1×0.4]，交叉概率為0.9，變異概率為0.5。各函數(shù)進(jìn)化曲線如圖4，圖5所示。

由于兩種算法初始種群隨機產(chǎn)生，為了避免算法受一次隨機實驗的影響，分別對算法重復(fù)實驗50次，在得到最優(yōu)解的前提下結(jié)果如表1所示。圖4，圖5相比較可以看到，改進(jìn)后的差分進(jìn)化算法較原始差分算法迭代次數(shù)少，收斂速度快，說明本文改進(jìn)的DE算法進(jìn)一步提高了算法性能。

5 結(jié) 論

本文提出基于云計算平臺的差分進(jìn)化算法改進(jìn)研究的新思路，并將輪盤賭法與差分進(jìn)化算法相結(jié)合，從而改進(jìn)差分進(jìn)化算法，具有良好的可操作性。實例仿真證明新的改進(jìn)對全局優(yōu)化性能進(jìn)行了改善，提高了收斂速度和收斂精度，使優(yōu)化速度獲得了一定程度的提高，有效地克服了基本差分算法收斂速度慢、易陷于局部最優(yōu)的缺陷，在減少迭代次數(shù)的同時，進(jìn)一步提高了最優(yōu)解的質(zhì)量。

參考文獻(xiàn)

[1] 魏玉霞.差分進(jìn)化算法的改進(jìn)及其應(yīng)用[D].廣州：華南理工大學(xué)，2013.

WEI Yuxia. Improvement and application of differential evolution algorithm [D]. Guangzhou： South China University of Technology， 2013.

[2] 張斌，李延暉，郭昊.基于反向?qū)W習(xí)的跨種群差分進(jìn)化算法[J].計算機應(yīng)用，2017，37（4）：1093?1099.

ZHANG Bin， LI Yanhui， GUO Hao. Cross species differential evolution algorithm based on reverse learning [J]. Journal of computer applications， 2017， 37（4）： 1093?1099.

[3] 魏文紅，周建龍，陶銘，等.一種基于反向?qū)W習(xí)的約束差分進(jìn)化算法[J].電子學(xué)報，2016，44（2）：426?436.

WEI Wenhong， ZHOU Jianlong， TAO Ming， et al. A constrained differential evolution algorithm based on reverse lear?ning [J]. Acta electronica Sinica， 2016， 44（2）： 426?436.

[4] 李榮雨，陳慶倩，陳菲爾.改進(jìn)種群多樣性的雙變異差分進(jìn)化算法[J].運籌學(xué)學(xué)報，2017，21（1）：44?54.

LI Rongyu， CHEN Qingqian， CHEN Feier. Double mutation differential evolution algorithm for improving population diversity [J]. Operations research transactions， 2017， 21（1）： 44?54.

[5] 王叢佼，王錫淮，肖建梅.基于極值優(yōu)化的混合差分進(jìn)化算法[J].計算機科學(xué)，2013，40（5）：257?260.

WANG Congjiao， WANG Xihuai， XIAO Jianmei. Hybrid differential evolution algorithm based on extremum optimization [J]. Computer science， 2013， 40（5）： 257?260.

[6] LU X， TANG K， SENDHOFF B， et al. A new self?adaptation scheme for differential evolution [J]. Neurocomputing， 2014， 146（C）： 2?16.

[7] BARBIERU C， POP F. Soft real?time Hadoop scheduler for big data processing in smart cities [C]// 2016 IEEE International Conference on Advanced Information Networking and Applications. Crans?Montana： IEEE， 2016： 863?870.

[8] 郭鵬.差分進(jìn)化算法改進(jìn)研究[D].天津：天津大學(xué)，2012.

GUO Peng. Improvement of differential evolution algorithm [D]. Tianjin： Tianjin University， 2012.

[9] 王旭，趙曙光.解決高維優(yōu)化問題的差分進(jìn)化算法[J].計算機應(yīng)用，2014，34（1）：179?181.

WANG Xu， ZHAO Shuguang. Differential evolution algorithm for solving high dimensional optimization problems [J]. Journal of computer applications， 2014， 34（1）： 179?181.

[10] 袁俊剛，孫治國，曲廣吉.差異演化算法的數(shù)值模擬研究[J].系統(tǒng)仿真學(xué)報，2007，19（20）：4646?4648.

YUAN Jungang， SUN Zhiguo， QU Guangji. Numerical simulation of differential evolution algorithm [J]. Journal of system simulation， 2007， 19（20）： 4646?4648.

[11] 許小健，黃小平，錢德玲.自適應(yīng)加速差分進(jìn)化算法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2008，5（1）：87?92.

XU Xiaojian， HUANG Xiaoping， QIAN Deling. Adaptive accelerating differential evolution algorithm [J]. Complex system and complexity science， 2008， 5（1）： 87?92.

[12] LIPOWSKI A， LIPOWSKA D. Roulette?wheel selection via stochastic acceptance [J]. Physica A： statistical mechanics & its applications， 2012， 391（6）： 2193?2196.

[13] WU G， MALLIPEDDI R， SUGANTHAN P N， et al. Differential evolution with multi?population based ensemble of mutation strategies [J]. Information sciences， 2016， 329（C）： 329?345.