差分進(jìn)化算法

差分進(jìn)化算法（DifferentialEvolution）差分優(yōu)化算法起源差分進(jìn)化算法(DifferentialEvolution)是一種新興的進(jìn)化計(jì)算技術(shù)，它是由Storn等人于1995年提出的,最初的設(shè)想是用于解決切比雪夫多項(xiàng)式問題[1]。DE是一種隨機(jī)的自適應(yīng)全局搜索算法,它可對非線性不可微連續(xù)空間函數(shù)進(jìn)行最小化,以其易用性、穩(wěn)健性和強(qiáng)大的全局尋優(yōu)能力在多個領(lǐng)域取得成功。標(biāo)準(zhǔn)差分進(jìn)化算法原理算法的基本思想是:從一個隨機(jī)初始化的種群開始搜索，然后經(jīng)過變異操作、交叉操作、選擇操作產(chǎn)生下一時刻的種群，該過程重復(fù)進(jìn)行，直到滿足停止條件[2]。群體初始化變異操作交叉操作選擇操作群體初始化算法首先在問題的可行解空間隨機(jī)產(chǎn)生第0代種群NP為群體規(guī)模.

用于表征第ｔ代種群中第ｉ個個體D為優(yōu)化問題的維數(shù).

初始個體第j維元素值可由公式隨機(jī)取樣確定：表示一個位于0和1之間的滿足均勻分布的隨機(jī)數(shù)對于不同的個體，它的每一維元素值都是獨(dú)立生成的為第ｊ維上的取值范圍

其中1≤ｉ≤ＮＰ，1≤ｊ≤Ｄ變異操作從生物角度看，變異意味著染色體中的基因發(fā)生改變。在進(jìn)化計(jì)算領(lǐng)域里，變異被看作某個元素發(fā)生改變。DE通過差分策略實(shí)現(xiàn)個體變異,這也是區(qū)別于遺傳算法的重要標(biāo)志.

其中兩個向量的差值進(jìn)行縮放，并與第三個向量相加得到一個變異向量Vi(t)顯然,xr2(t)

,xr3(t)之間的差分向量越小，擾動也就越小，這就意味著，在算法的初始階段，由于個體彼此相差較大，擾動較大，算法在比較大的范圍進(jìn)行搜索，在算法的后期，因?yàn)槿后w都靠近最優(yōu)個體，擾動值偏小，算法在小范圍的內(nèi)進(jìn)行搜索．

目前被廣泛采用的其他四種變異算子如下：

在進(jìn)化過程中，為了保證解的有效性，必須判斷變異后的向量個體是否滿足邊界條件。如果不滿足邊界條件，則重新生成

交叉操作為了提高種群的多樣性，差分進(jìn)化算法還有交叉操作。與其他進(jìn)化算法中基于多個來自父代中的基準(zhǔn)向量交換基因的交叉操作不同的是，差分進(jìn)化算法中的交叉操作采用基準(zhǔn)向量和變異向量進(jìn)行操作。對第t代種群{xi(t)}及其變異的中間體vi(t+1)進(jìn)行個體間的交叉操作,以二項(xiàng)式交叉操作（Binomial）具體說明如下其中ｊ∈｛１,２,…,Ｄ｝randj[0,1]是[0,1]之間的隨機(jī)數(shù)jrand是在區(qū)間[1,D]中隨機(jī)選擇的整數(shù)，Cr是介于０和１之間的交叉概率．Cr的取值越大，發(fā)生交叉的可能越大。

保證ui(t+1)至少要從vi(t+1)中獲得一個值，以確保試驗(yàn)向量與目標(biāo)向量和變異向量都不相同，從而避免群體的無效交叉

圖1為6個元素的個體交叉操作示意圖.為了確保變異中間體vi(t+1)的每個

個體至少有一個元素

遺傳給下一代,第一個交叉操作的元素是隨機(jī)取出vi(t+1)中的第jrand位元素作為交叉后個體ui(t+1)第jrand位等位“基因”.后續(xù)的交叉操作過程,則是通過交叉概率CR來選取xi(t)還是vi(t+1)的元素ui(t+1)的元素.選擇操作ＤＥ的選擇操作是一種基于貪婪的選擇機(jī)制,若ui(t+1)的適應(yīng)度值好于xi(t)的適應(yīng)度值,則保留到下一代種群的個體是ui(t+1),否則保留的將是xi(t).對于最小優(yōu)化問題,則選擇算子可由下式描述其中f為目標(biāo)函數(shù).

ＤＥ的選擇操作是在目標(biāo)向量和其對應(yīng)的試驗(yàn)向量兩者中保留最優(yōu),使得子代個體的適應(yīng)度值總是好于父代個體的適應(yīng)度值,從而導(dǎo)致種群始終向最優(yōu)解的位置進(jìn)化并逐步聚焦到最優(yōu)解位置或滿意解位置．DE算法的搜索性能取決于算法全局探索和局部開發(fā)能力的平衡,而這在很大程度上依賴于算法的控制參數(shù)的選取,包括種群規(guī)模、縮放比例因子和交叉概率等.差分優(yōu)化算法優(yōu)點(diǎn)歸納起來,DE算法具有如下優(yōu)點(diǎn):1)算法通用,不依賴于問題信息;2)算法原理簡單,容易實(shí)現(xiàn);3)群體搜索,具有記憶個體最優(yōu)解的能力;4)協(xié)同搜索,具有利用個體局部信息和群體全局信息指

導(dǎo)算法進(jìn)一步搜索的能力;5)易于與其他算法混合,構(gòu)造出具有更優(yōu)性能的算法.差分進(jìn)化算法的改進(jìn)

根據(jù)改進(jìn)方向不同，大體上可以分為4類：參數(shù)控制策略新的變異交叉策略混合策略多種群改進(jìn)策略參數(shù)控制策略DE主要涉及種群規(guī)模NP、縮放因子F、交叉概率CR這3個控制參數(shù).在標(biāo)準(zhǔn)差分進(jìn)化算法中，它的控制參數(shù)是固定的，是不隨進(jìn)化時間變化的。而理想情況是針對不同的問題、不同的進(jìn)化時刻，這些參數(shù)應(yīng)該有不同的值，以便達(dá)到最優(yōu)效果。參數(shù)自適應(yīng)的DE算法根據(jù)縮放因子F、交叉概率CR在尋優(yōu)過程中的作用,提出一種線性的變化策略:隨著進(jìn)化代數(shù)t的增加，CR線性減小，

F線性增加.CR(0):變異概率的初始值F(0):縮放因子的初始值CRmin:進(jìn)化過程中變異概率的最小值Fmax:進(jìn)化過程中縮放因子的最大值Gmax:最大進(jìn)化代數(shù)混合策略盡管基本差分進(jìn)化算法效率高、魯棒性能較好，但是一類算法不可能對所有不同形式的問題都表現(xiàn)良好。而混合策略能充分結(jié)合幾種不同的算法的優(yōu)良特性，進(jìn)一步提高算法的魯棒性.與模擬退火算法相結(jié)合與蟻群算法相結(jié)合與PSO算法相結(jié)合

與遺傳算法相結(jié)合受遺傳算法選擇壓力的啟發(fā),Bergey,根據(jù)父代個體適應(yīng)度的大小將種群重新排序,然后按照獨(dú)立伯努力實(shí)驗(yàn),在選擇壓力下生成變異的基向量.多種群改進(jìn)策略使用多種群策略也是一種常見的算法性能提升策略。當(dāng)多個種群共同執(zhí)行進(jìn)化搜索時,即使單個種群出現(xiàn)多樣性的喪失,由于種群間存在差異,通過種群間的信息共享和交換,依然可以保證整個算法繼續(xù)進(jìn)化.Tasgetiren等將主種群分成幾個子種群，同時子種群之間彼此之間進(jìn)行通信，以便交換信息.zhang等在主種群的基礎(chǔ)上，額外提出一個新的用于保存一些較劣解得輔助種群，該輔助種群為變異算子提供搜索方向信息。差分優(yōu)化算法應(yīng)用方向人工神經(jīng)網(wǎng)絡(luò)Liu等將PSO,DE與混沌搜索相結(jié)合來訓(xùn)練多層前饋神經(jīng)網(wǎng)絡(luò);Abbass[5]利用基于BP和DE學(xué)習(xí)的神經(jīng)元網(wǎng)絡(luò)來預(yù)測乳腺癌.應(yīng)用結(jié)果均顯示,利用DE設(shè)計(jì)神經(jīng)元網(wǎng)絡(luò)是一種快速、高效并具有潛力的方法化工領(lǐng)域Kiranmai等[6]利用DE確定固定薄膜生物反應(yīng)器的機(jī)理參數(shù).

Kapadi[7]等利用DE解決間歇發(fā)酵最優(yōu)控制和參數(shù)選擇問題.Chaitali等[8]通過DE為黃原膠發(fā)酵過程選擇合適的初始反應(yīng)器物質(zhì)體積以及進(jìn)料濃度.電力系統(tǒng)Chang等[9]利用改進(jìn)DE優(yōu)化設(shè)計(jì)大規(guī)模多總線被動諧波濾波器,同時考慮了濾波器參數(shù)和加熱爐負(fù)荷的不確定性.Kannan等[10]系統(tǒng)考察了多種流行的現(xiàn)代啟發(fā)式算法(包括遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略、蟻群算法、PSO、禁忌搜索、模擬退火和DE等)在解決最低成本發(fā)電擴(kuò)張計(jì)劃問題(GEP)上的性能表現(xiàn),其中DE在該問題上的性能要好于其他方法.機(jī)械設(shè)計(jì)宋立明等[11]利用自適應(yīng)DE,結(jié)合曲面造型法,提出了一種葉輪機(jī)械三維氣動優(yōu)化設(shè)計(jì)方法.楊曉明等[12]利用DE進(jìn)行盤式制動器的全性能優(yōu)化設(shè)計(jì).Doyle等[13]利用DE自動設(shè)計(jì)照明器反射鏡.張吳明等[14]將傳統(tǒng)分步標(biāo)定Tsai方法與DE相結(jié)合,提出了一種新的相機(jī)標(biāo)定方法.機(jī)器人領(lǐng)域Aydin等[15]將DE與模糊推理相結(jié)合,用于解決機(jī)器人最優(yōu)路徑規(guī)劃問題.Shiakolas等[16]利用DE優(yōu)化設(shè)計(jì)機(jī)器人連續(xù)操縱器和鉸接處理器,使得機(jī)器人在滿足物理鏈接特性的約束下,完成特定動作所需要的扭矩最小.Joshi等[17]利用DE解決多傳感器融合的最小表達(dá)問題,用于復(fù)雜環(huán)境下的機(jī)器人系統(tǒng)的計(jì)劃和控制問題.信號處理領(lǐng)域Storn[18]利用DE設(shè)計(jì)濾波器.Shan等[19]利用基于DE的頻率域模型優(yōu)化超寬帶無線電系統(tǒng)的源脈沖和探測模型,使得自由空間的功率和接收端的相關(guān)檢測輸出最大.生物學(xué)領(lǐng)域Tsai等[20]利用DE對非線性生物動力系統(tǒng)進(jìn)行結(jié)構(gòu)辨識和參數(shù)估計(jì).Moloi等[21]利用DE尋找穩(wěn)定的原子或分子結(jié)構(gòu)來最小化勢能函數(shù),并用于半導(dǎo)體設(shè)計(jì)和基于結(jié)構(gòu)的藥品設(shè)計(jì).運(yùn)籌學(xué)領(lǐng)域Chakraborti等[22]利用DE優(yōu)化調(diào)度可逆式軋機(jī),使得錠鐵從給定初始厚度到指定最終厚度的熱軋時間最小.系統(tǒng)辨識與故障診斷鄧建軍等[23]利用基于DE的模糊邏輯系統(tǒng)來辨識非線性系統(tǒng).徐志高等[24]提出了一類基于DE和模糊神經(jīng)網(wǎng)絡(luò)相結(jié)合的故障診斷算法,構(gòu)造了某導(dǎo)彈動力系統(tǒng)的模糊神經(jīng)網(wǎng)絡(luò)模型.故障診斷實(shí)例結(jié)果表明,基于DE的模糊神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)速度快,且能夠正確分離導(dǎo)彈動力系統(tǒng)的單故障和多故障工作模式.其他Cruz等[25]將DE與可調(diào)控制權(quán)梯度法相結(jié)合來優(yōu)化萵苣生產(chǎn)模型,從而使得最大化種植者的利益同時保證作物的質(zhì)量(萵苣中的硝酸鹽濃度限制在一定的范圍內(nèi)).Pavlidis等26]利用DE求解了博弈論中的nashi均衡解.參考文獻(xiàn)[1]劉波,王凌,金以慧.差分進(jìn)化算法研究進(jìn)展[J].控制與決策,2007,07:721-729.[2]汪慎文,丁立新,張文生,郭肇祿,謝承旺.差分進(jìn)化算法研究進(jìn)展[J].武漢大學(xué)學(xué)報(理學(xué)版),2014,v.60;No.26604:283-292.[3]楊啟文,蔡亮,薛云燦.差分進(jìn)化算法綜述[J].模式識別與人工智能,2008,v.21;No.8804:506-513.[4]徐斌.基于差分進(jìn)化算法的多目標(biāo)優(yōu)化方法研究及其應(yīng)用[D].華東理工大學(xué),2013.[5]AbbassHA.Anevolutionaryartificialneuralnetworksapproachforbreastcancerdiagnosis[J].ArtificialIntelligenceinMedicine,2002,25(3):265-281.[6]KiranmaiD,JyothirmaiA,MurtyCS.Determinationofkineticparametersinfixed-filmbio-reactors:Aninverseproblemapproach[J].BiochemicalEngineeringJ,2005,23(1):73-83.[7]KapadiMD,GudiRD.Optimalcontroloffed-batchfermentationinvolvingmultiplefeedsusingdifferentialevolution[J].ProcessBiochemistry,2004,39(11)1709-1721.[8]ChaitaliM,KapadiM,SuraishkumarGK,etal.Productivityimprovementinxanthangumfermentationusingmultiplesubstrateoptimization[J].BiotechnologyProgress,2003,19(4):1190-1198.[9]ChangYP,WuCJ.Optimalmultiobjectiveplanningoflarge-scalepassiveharmonicfiltersusinghybriddifferentialevolutionmethodconsideringparameterandloadinguncertainty[J].IEEETransonPowerDelivery,2005,20(1):408-416.[10]KannanS,SlochanalSMR,PadhyNP.Applicationandcomparisonofmetaheuristictechniquestogenrationexpansionplanningproblem[J].IEEETransonPowerSystems.[11]宋立明,李軍,豐鎮(zhèn)平.跨音速透平扭葉片的氣動優(yōu)化設(shè)計(jì)研究[J].西安交通大學(xué)學(xué)報,2005,39(11):1277-1281.[12]楊曉明,邱清盈,馮培恩,等.盤式制動器的全性能優(yōu)化設(shè)計(jì)[J].中國機(jī)械工程,2005,16(7):630-633.[13]DoyleS,CorcoranD,ConnellJ.Automatedmirrordesignusinganevolutionstrategy[J].OpticalEngineering,1999,38(2):323-333.[14]張吳明,鐘約先.基于改進(jìn)差分進(jìn)化算法的相機(jī)標(biāo)定研究[J].光學(xué)技術(shù),2004,30(6):720-723[15]AydinS,TemeltasH.Fuzzy-differentialevolutionalgorithmforplanningtime-optimaltrajectoriesofaunicyclemobilerobotonapredefinedpath[J].AdvancedRobotics,2004,18(7):25-748.[16]ShiakolasPS,KoladiyaD,KebrleJ.Optimumrobotdesignbasedontaskspecificationsusingevolutionarytechniquesandkinematic,dynamicandstructuralconstraints[J].InverseProblemsinEngineering,2002,10(4):359-375.[17]JoshiR,SandersonAC.Minimalrepresentationmultisensorfusionusingdifferentialevolution[J].IEEETransonSystems,ManandCybernetics:A,1999,29(1):63-76.[18]StornR.Designingnonstandardfilterswithdifferentialevolution[J].IEEESignalrocessingMagazine,2005,22(1):103-106.[19]ShanDM,ChenZN,WuXH.SignaloptimizationfrUWBradiosystems[J].IEEETransonAntennasandPropagation,2005,53(7):2178-2184.[20]TsaiKY,WangFS.Evolutionaryoptimizationwithdatacollocationforreverseengineringofbiologicalnetworks[J].Bioinformatics,2005,21(7):1180-1188.[21]MoloiNP,AliMM.AnIterativeglobaloptimizationalgorithmforpotentialenergyminimization[J].ComputationalOptimizationandApplications,2005,30(2):119-132.[22]ChakrabortiN,KumarA.Theopt