基于云計算平臺的差分進化算法改進研究

孫潔 連暢

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

關鍵詞： 差分算法； 云計算； 輪盤賭； 多樣性； 全局最優； 交叉變異

中圖分類號： TN911.1?34； TP301 文獻標識碼： 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 引 言

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

差分進化算法（Differential Evolution，DE）是近年來眾多新興算法中的一種[1]。最開始DE只用于一種多項式問題的解決，后來發現有關復雜優化的問題也可以用DE研究解決，差分進化算法更是一種群體智能指導的優化搜索。

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

1 云計算

1.1 HDFS分布式文件系統

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

1.2 MapRaduce框架

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

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

2 差分進化算法

差分進化算法通過交叉因子、縮放因子和種群大小3個控制參數實現。差分進化算法不僅具有運算原理簡單、易于學習和容易實現的特點，并且其運行結果還具有可靠性、魯棒性和收斂速度快等優點。

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

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

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

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

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

3） 重復上述操作直到找到滿足最大迭代數或找到滿足適應值的個體才會停止。

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

3 差分進化算法的改進

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

3.1 種群規模

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

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

3.2 縮放因子

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

3.3 交叉和變異

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

3.3.1 輪盤賭法

輪盤賭法是比較常見的隨機選擇方法中的一種，相似于一種輪盤賭游戲，原理很簡單，就是把個體適應度按比例全部轉化為選擇的概率，即按個體所占總體的比例將圓盤上的區域依次劃分，其中個體所占比例越大，在圓盤中所劃分的區域就越大，相應地被選中的機會也就越大。每轉動一次圓盤，在其停止后指針所指向的扇形區域為選中區域，所選中的區域對應的個體即為被選中的個體。輪盤賭法的運行過程如下：

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

3.3.2 交叉和變異

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

4 實例仿真

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

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

5 結 論

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

參考文獻

[1] 魏玉霞.差分進化算法的改進及其應用[D].廣州：華南理工大學，2013.

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

[2] 張斌，李延暉，郭昊.基于反向學習的跨種群差分進化算法[J].計算機應用，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] 魏文紅，周建龍，陶銘，等.一種基于反向學習的約束差分進化算法[J].電子學報，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].運籌學學報，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] 王叢佼，王錫淮，肖建梅.基于極值優化的混合差分進化算法[J].計算機科學，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] 郭鵬.差分進化算法改進研究[D].天津：天津大學，2012.

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

[9] 王旭，趙曙光.解決高維優化問題的差分進化算法[J].計算機應用，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] 袁俊剛，孫治國，曲廣吉.差異演化算法的數值模擬研究[J].系統仿真學報，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] 許小健，黃小平，錢德玲.自適應加速差分進化算法[J].復雜系統與復雜性科學，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.