李 斌

（河南建筑職業(yè)技術(shù)學(xué)院，河南 鄭州 450064）

差分進(jìn)化算法的研究進(jìn)展

李 斌

（河南建筑職業(yè)技術(shù)學(xué)院，河南 鄭州 450064）

差分進(jìn)化算法是一類當(dāng)前較為強(qiáng)大的隨機(jī)實(shí)參數(shù)優(yōu)化算法，已成功解決很多實(shí)際問題。它具有全局優(yōu)化性能好、結(jié)構(gòu)簡單易于實(shí)現(xiàn)、控制參數(shù)少和搜索能力強(qiáng)等優(yōu)點(diǎn)，差分進(jìn)化算法吸引了眾多進(jìn)化算法研究者的關(guān)注。文中詳細(xì)概述了差分進(jìn)化算法的基本概念、特點(diǎn)、改進(jìn)和應(yīng)用現(xiàn)狀，就DE算法的進(jìn)一步研究進(jìn)行了探討和展望。

差分進(jìn)化；進(jìn)化算法；遺傳算法

1 引言

根據(jù)達(dá)爾文的生物進(jìn)化理論，自然界的物種會(huì)隨著客觀環(huán)境的變化而發(fā)生變異，各個(gè)物種在競(jìng)爭(zhēng)環(huán)境中生存，優(yōu)勝劣汰，使得生物不斷進(jìn)化。為了求解復(fù)雜優(yōu)化問題，一些研究人員嘗試借鑒自然界物種進(jìn)化的思想來開展優(yōu)化算法研究，從而開啟了一個(gè)重要研究方向——進(jìn)化計(jì)算（Evolutionary Computation，簡稱EC）。進(jìn)化計(jì)算具有穩(wěn)健性、易實(shí)現(xiàn)性和全局搜索能力強(qiáng)等特點(diǎn)，同時(shí)不依賴待求問題的種類和性質(zhì)，因此在眾多領(lǐng)域倍受關(guān)注。

類似于其他的進(jìn)化計(jì)算算法，差分進(jìn)化（Differential Evolution，簡稱DE）算法也是一種基于種群的全局隨機(jī)搜索算法[1]，它最初是由Storn和Price為求解切比雪夫多項(xiàng)式擬合問題于1995年提出的。1996年5月在日本舉行的第一屆國際進(jìn)化優(yōu)化方法競(jìng)賽（International Contest on Evolutionary Optimization， ICEO）中，DE算法表現(xiàn)突出，獲得了第三名的成績。1997年的第二屆國際進(jìn)化優(yōu)化方法競(jìng)賽中Price通過大量優(yōu)化實(shí)驗(yàn)證明了DE是一種性能優(yōu)異的進(jìn)化算法。從此，DE算法得到更多研究者的關(guān)注。自2005年以來，在IEEE Conference on Evolution Computation（CEC）會(huì)議關(guān)于實(shí)參優(yōu)化、多目標(biāo)優(yōu)化、動(dòng)態(tài)不確定性優(yōu)化等多次競(jìng)賽中，DE具有非常優(yōu)異的表現(xiàn)。

DE算法是一種基于種群的智能優(yōu)化方法，不依賴問題的特征信息，主要借助于種群個(gè)體之間的差分信息對(duì)個(gè)體形成擾動(dòng)來探索整個(gè)種群空間，并利用貪婪競(jìng)爭(zhēng)機(jī)制進(jìn)行優(yōu)化，尋求問題最優(yōu)解。DE算法采用實(shí)數(shù)編碼，首先在搜索空間內(nèi)隨機(jī)產(chǎn)生初始群體，使用變異操作、交叉操作生成新的個(gè)體，但與一般的進(jìn)化算法不同的是，差分進(jìn)化算法采用一對(duì)一的淘汰機(jī)制來更新進(jìn)化群體，降低了進(jìn)化操作的復(fù)雜性。不同的是差分進(jìn)化算法把一定比例的多個(gè)個(gè)體的差分信息作為個(gè)體的擾動(dòng)量，使得算法在跳躍距離和搜索方向上具有自適應(yīng)性[2]。在進(jìn)化的早期，因?yàn)榉N群中個(gè)體的差異性較大使得擾動(dòng)量較大，從而使得算法能夠在較大范圍內(nèi)搜索，具有較強(qiáng)的探索能力（exploration）；而到了進(jìn)化的后期，當(dāng)算法趨向于收斂時(shí)，種群中個(gè)體的差異性較小，算法在個(gè)體附近搜索，這使得算法具有較強(qiáng)的局部開采能力（exploitation）[2]。

鑒于差分進(jìn)化算法具有控制參數(shù)少、原理相對(duì)簡單、易于理解和實(shí)現(xiàn)的優(yōu)點(diǎn)，再加上其表現(xiàn)出來的高可靠性、強(qiáng)魯棒性以及良好的優(yōu)化性能，目前已經(jīng)成為進(jìn)化計(jì)算研究領(lǐng)域的熱點(diǎn)。它廣泛應(yīng)用于很多領(lǐng)域，如控制系統(tǒng)與機(jī)器人、化學(xué)工程、模式識(shí)別與圖像處理、人工神經(jīng)網(wǎng)絡(luò)、生物信息學(xué)和信號(hào)處理等取得了驚人的效果。

2 差分進(jìn)化算法基本原理

DE的基本思想是：利用從種群中隨機(jī)選擇的兩個(gè)個(gè)體向量的差分量作為第三個(gè)隨機(jī)基準(zhǔn)向量的擾動(dòng)量，得到變異向量，然后變異向量與基準(zhǔn)向量（或稱為目標(biāo)向量）進(jìn)行交叉操作，生成試驗(yàn)向量。最后基準(zhǔn)向量和試驗(yàn)向量競(jìng)爭(zhēng)，較優(yōu)者保存在下一代群體中。這樣，差分進(jìn)化算法逐代改善群體質(zhì)量，引導(dǎo)種群聚焦到最優(yōu)解位置。

圖1給出了差分進(jìn)化算法的主要步驟，包括種群初始化，以及選擇多個(gè)個(gè)體進(jìn)行變異操作產(chǎn)生變異個(gè)體，變異個(gè)體與目標(biāo)個(gè)體進(jìn)行交叉操作，目標(biāo)個(gè)體與試驗(yàn)個(gè)體競(jìng)爭(zhēng)選擇操作等。從圖1中我們可以看出，DE算法執(zhí)行簡單，易于實(shí)現(xiàn)。

圖1 DE算法的主要步驟

2.1 初始化

個(gè)體每一維上的取值可按下式產(chǎn)生：

2.2 變異

在DE算法中，種群內(nèi)個(gè)體的差分向量經(jīng)過縮放之后，與種群內(nèi)另外的相異個(gè)體相加得到變異向量。根據(jù)變異向量生成方法不同，形成了多種變異策略[3]。目前被廣泛采用的五種變異策略如下[1]：

2.3 交叉

變異操作完成后，對(duì)目標(biāo)向量和變異向量進(jìn)行交叉操作生成試驗(yàn)向量，DE算法有兩種交叉方式：二項(xiàng)式交叉（用bin表示）和指數(shù)交叉（用exp表示）。以二項(xiàng)式交叉具體說明如下：

通過隨機(jī)選擇，使試驗(yàn)向量至少有一個(gè)分量由變異向量貢獻(xiàn)。二項(xiàng)式交叉操作的方程為：

2.4 選擇

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

在各種應(yīng)用領(lǐng)域和多次進(jìn)化大賽中，差分進(jìn)化算法已經(jīng)展現(xiàn)出驚人的魅力。然而，DE算法不可避免地存在搜索停滯和早熟收斂、搜索性能對(duì)參數(shù)具有依賴性、算法在有限情況下很難保證獲得全局最優(yōu)解等問題，因此從多方面深入分析算法的運(yùn)行機(jī)理，并提出相應(yīng)的改進(jìn)DE算法性能的調(diào)整策略，從而達(dá)到平衡算法的探索能力與開發(fā)能力的目的，依然是當(dāng)前進(jìn)化算法研究的重要領(lǐng)域。

3.1 控制參數(shù)調(diào)整策略的改進(jìn)

DE算法的控制參數(shù)包括縮放因子F、交叉率CR以及種群規(guī)模NP。DE算法性能的優(yōu)劣很大程度上取決于其控制參數(shù)的選擇[4]。

1）種群規(guī)模NP：如果種群規(guī)模NP較小，算法可能收斂快，但是會(huì)導(dǎo)致算法早熟；相反，NP過大，可以增加種群的多樣性，增加搜索到最優(yōu)解的概率，但會(huì)導(dǎo)致計(jì)算量加大，收斂速度較慢。

2）縮放因子F：縮放因子影響對(duì)基向量的擾動(dòng)程度，F(xiàn)較大時(shí)，擾動(dòng)較大導(dǎo)致搜索步長的取值在一個(gè)更大的范圍內(nèi)，能夠在更大范圍內(nèi)尋求有潛力的解，從而提高種群的多樣性，但是削弱了算法的局部搜索能力；F較小，擾動(dòng)量小，搜索范圍較小，有利于進(jìn)化的快速進(jìn)行，提高算法的收斂速度。

3）交叉率CR：交叉率對(duì)種群的多樣性具有重要的影響，決定種群中有多少個(gè)體可能被改變。CR較小時(shí)，種群中被改變的個(gè)體較少，當(dāng)前種群中解的特征被較多地保留下來，有利于進(jìn)化過程的穩(wěn)定進(jìn)行；CR較大時(shí)，會(huì)引起種群中更多個(gè)體發(fā)生改變，使種群多樣性增強(qiáng)，有利于搜索到最優(yōu)解。

Liu和Lampinen提出了一種基于模糊控制的適應(yīng)差分進(jìn)化算法FADE，通過模糊邏輯控制器來調(diào)節(jié)參數(shù)F和CR，仿真結(jié)果顯示該算法在優(yōu)化高維問題時(shí)的性能遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)DE算法[5]。

Qin等提出一種新的自適應(yīng)差分進(jìn)化（SaDE）算法，F(xiàn)和CR借鑒前期產(chǎn)生優(yōu)質(zhì)解的經(jīng)驗(yàn)進(jìn)行自適應(yīng)調(diào)整[6]。該算法中F的設(shè)置服從均值為0.5、標(biāo)準(zhǔn)方差為0.3的正態(tài)分布N（0.5，0.32），并應(yīng)用于當(dāng)前種群的每一差分向量，從而平衡整個(gè)優(yōu)化過程的探索（F較大時(shí)）與開發(fā)（F較小）能力。CR的值服從均值為CRm，標(biāo)準(zhǔn)方差為Std的正態(tài)分布N（CRm， Std2）。將CRm初始化為0.5，此時(shí)Std應(yīng)設(shè)置為一個(gè)很小的值保證CR的取值為[0，1]，因此將Std設(shè)置為0.1。SaDE算法中的自適應(yīng)機(jī)制中也涉及參數(shù)的調(diào)節(jié)，如正態(tài)分布的標(biāo)準(zhǔn)方差。算法中對(duì)問題不太敏感的參數(shù)代替敏感度較高的參數(shù)，因此自適應(yīng)DE算法能夠獲得比傳統(tǒng)DE算法更好的性能。

Zhang和Sanderson[7]提出一種新的適應(yīng)差分進(jìn)化算法（JADE）。在JADE算法中，對(duì)每個(gè)個(gè)體，分別應(yīng)用標(biāo)準(zhǔn)正態(tài)分布和柯西分布采樣確定交叉概率CR和縮放因子F。

3.2 操作算子策略的改進(jìn)

除基本DE所介紹的5個(gè)變異策略外，研究人員對(duì)其他一些變異策略進(jìn)行了研究。

Fan和Lampinen提出三角變異策略[8]：

該算法利用隨機(jī)選擇的三個(gè)個(gè)體中最好個(gè)體信息，引導(dǎo)試驗(yàn)向量向其靠近，該方法可視為一種局部搜索策略。為了進(jìn)一步在收斂速度和搜索能力之間尋求一種平衡，算法使用一個(gè)概率來控制三角變異算子的使用頻率。

Zhang和Sanderson提出DE/current-to-pbest策略[7]，即JADE：

Liang等[9]提出利用適應(yīng)度歐式距離比值改進(jìn)算法的性能，用于優(yōu)化多模函數(shù)問題。

3.3 混合差分進(jìn)化算法

混合技術(shù)是指將兩個(gè)或多個(gè)算法的優(yōu)點(diǎn)結(jié)合在一起，在特定問題求解范圍內(nèi)，形成一種新的算法，近年來正成為優(yōu)化算法的研究熱點(diǎn)。研究者對(duì)DE與其他算法相混合的技術(shù)進(jìn)行了大量的研究，包括與其他智能優(yōu)化算法以及局部搜索方法的融合。

與D E相混合的智能優(yōu)化算法有粒子群優(yōu)化（PSO）、蟻群算法（ACO）、人工免疫算法（AIS）、模擬退火（SA）等。其中，DE與PSO混合的研究最多，Hendtlass首次將DE與PSO進(jìn)行融合，提出當(dāng)后代獲得較好的適應(yīng)值時(shí)更新粒子的位置，DE算法在指定的間隔對(duì)粒子群進(jìn)行作用。Xin等對(duì)PSO與DE相混合進(jìn)行了詳盡的分析和總結(jié)[10]。Capanio等在DE框架中將PSO和另外兩種局部搜索算法相結(jié)合，利用PSO在初始階段快速改善具有較差適值的解，并將其包含在DE種群中，使這些解引導(dǎo)DE搜索，兩種搜索方式按一定概率與DE算法相結(jié)合[11]。文獻(xiàn)[12]提出基于一種新的混合差分粒子群啟發(fā)式優(yōu)化算法的電子商務(wù)物流配送優(yōu)化方案。

4 總結(jié)與展望

DE算法的提出最初是為了解決連續(xù)領(lǐng)域的優(yōu)化問題，作為智能優(yōu)化技術(shù)的一個(gè)重要的分子，DE算法已經(jīng)引起優(yōu)化計(jì)算領(lǐng)域研究人員的普遍關(guān)注。目前DE算法已經(jīng)廣泛地應(yīng)用于許多領(lǐng)域，在算法改進(jìn)和應(yīng)用上得到了快速的發(fā)展，成為進(jìn)化計(jì)算領(lǐng)域新的研究熱點(diǎn)。但DE算法在其理論分析，算法改進(jìn)和應(yīng)用研究等方面仍有廣闊的值得挖掘的研究空間，需要加強(qiáng)并進(jìn)行深入研究。加強(qiáng)理論方面的研究，為其改進(jìn)和實(shí)際應(yīng)用提供依據(jù)，這非常具有挑戰(zhàn)性和吸引力，在這方面還需要做大量的研究。DE算法的改進(jìn)研究，它包括對(duì)其控制參數(shù)（種群規(guī)模NP、縮放因子F和交叉率CR）的研究，算子（差分變異、交叉率和選擇）以及種群拓?fù)浣Y(jié)構(gòu)等的研究，從平衡算法的探索與開發(fā)能力的角度出發(fā)，考慮種群多樣性以及個(gè)體適應(yīng)值在算法運(yùn)行過程中的變化情況，引入適應(yīng)性調(diào)節(jié)機(jī)制，提出高效穩(wěn)健的協(xié)調(diào)方法，仍是DE算法的重要研究內(nèi)容。

[1]Price K，Storn R，Lampinen J.Differential Evolution：A Practical Approach to Global Optimization [M].New York： Springer-Verlag， 2005.

[2]吳志峰.差異演化算法及其應(yīng)用研究[D].北京：北京交通大學(xué)，2009.

[3]張航，王偉，鄭玲等.一種基于密度聚類的小生境差分進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（23）：42-45.

[4]Mandal K K， Chakraborty N.Parameter study of differential evolution based optimal scheduling of hydrothermal systems [J].Journal of Hydroenvironment Research，2012，7（1）：72-80.

[5]Liu J， LampinenJ.A fuzzy adaptive differential evolution algorithm[J].Soft Computing，2005，9（6）：448-462.

[6]Qin.K，Huang VL，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization [J].IEEE Transactions on Evolutionary Computation， 2009，13（2）：398-417.

[7]Zhang J Q， Sanderson A C.JADE：adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation，2009，13（5）：945-958.

[8]H.Y.Fan and J.Lampinen.A trigonometric mutation operation to differential evolution[J].Journal of Global Optimization，2003，27（1）：l05-129.

[9]Liang J J，Qu B Y，Mao X B，et al.Differential evolution based on fitness Euclidean-distance ratio for multimodal optimization[J].Neurocomputing，2014，137（5）：252-260.

[10]Xin B，Chen J，Zhang J，et al.Hybridizing differential evolution and particle swarm optimization to design powerful optimizers： A review and taxonomy[J].IEEE Transactions on systems， Man & Cybernetics Part C，2012， 42（5）：744-767.

[11]Caponio A，Neri F，Tirronen V.Super-fit control adaptation in memetic differential evolution frameworks[J].Soft Computing，2009，13（8）：811-831.

[12]沈濟(jì)南，梁芳，鄭明輝.一種新的混合差分粒子群優(yōu)化算法及其應(yīng)用[J].四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2014.46（6）：38-43.

李斌（1974—），男（回族），河南建筑職業(yè)技術(shù)學(xué)院，高級(jí)講師，電氣、物理方向

2017-08-23