李 斌
(河南建筑職業(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)化算法;遺傳算法
根據(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)處理等取得了驚人的效果。
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算法的主要步驟
個(gè)體每一維上的取值可按下式產(chǎn)生:
在DE算法中,種群內(nèi)個(gè)體的差分向量經(jīng)過縮放之后,與種群內(nèi)另外的相異個(gè)體相加得到變異向量。根據(jù)變異向量生成方法不同,形成了多種變異策略[3]。目前被廣泛采用的五種變異策略如下[1]:
變異操作完成后,對(duì)目標(biāo)向量和變異向量進(jìn)行交叉操作生成試驗(yàn)向量,DE算法有兩種交叉方式:二項(xiàng)式交叉(用bin表示)和指數(shù)交叉(用exp表示)。以二項(xiàng)式交叉具體說明如下:
通過隨機(jī)選擇,使試驗(yàn)向量至少有一個(gè)分量由變異向量貢獻(xiàn)。二項(xiàng)式交叉操作的方程為:
在各種應(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)域。
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。
除基本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ù)問題。
混合技術(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)化方案。
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