蔣兵兵

（湖南鐵路科技職業(yè)技術(shù)學(xué)院 湖南 株洲 412007）

0 引言

作為基于群體差異進(jìn)行隨機(jī)搜索的算法，差分進(jìn)化算法的應(yīng)用無需進(jìn)行編碼和解碼，在受控參數(shù)較少的情況下獲得了較強(qiáng)魯棒性，在全局尋優(yōu)方面的性能良好，目前在電力調(diào)度、多目標(biāo)路徑規(guī)劃等多個(gè)領(lǐng)域應(yīng)用廣泛。但在實(shí)際應(yīng)用過程中，差分進(jìn)化算法同樣存在過早收斂等問題，需要通過算法改進(jìn)獲得更高收斂精度。現(xiàn)階段，改進(jìn)差分進(jìn)化算法的方法較多，還應(yīng)掌握不同方法優(yōu)勢(shì)，以便結(jié)合實(shí)際需求合理進(jìn)行算法改進(jìn)和應(yīng)用。

1 差分進(jìn)化算法概述

1.1 算法原理

根據(jù)算法原理可知，對(duì)個(gè)體進(jìn)行初始化操作，從種群中隨機(jī)選擇互異個(gè)體進(jìn)行差分、縮放，與第3 個(gè)隨機(jī)個(gè)體生成變異個(gè)體。而利用父代個(gè)體和變異個(gè)體進(jìn)行交叉操作，可以獲得試驗(yàn)個(gè)體，完成適應(yīng)度值比較，選擇較優(yōu)個(gè)體繼續(xù)迭代，直至達(dá)到終止準(zhǔn)則[1]。從本質(zhì)上來講，就是對(duì)生物體的“優(yōu)勝略汰”進(jìn)化過程進(jìn)行模擬，通過自適應(yīng)自組織解決問題。將種群當(dāng)成是操作對(duì)象實(shí)施并行優(yōu)化，在迭代次數(shù)達(dá)到最大或找到最優(yōu)解后可以停止尋優(yōu)。

1.2 算法流程

標(biāo)準(zhǔn)的差分進(jìn)化算法可以劃分為種群初始化和進(jìn)化迭代兩個(gè)階段，前者需在可行域內(nèi)通過均勻分布等概率獲得初始空間解向量，后者包含變異、交叉、選擇等操作，在達(dá)到進(jìn)化條件時(shí)將進(jìn)行尋優(yōu)，直至算法結(jié)束，見圖1。該種算法具有記憶功能，經(jīng)典變異操作包含DE/rand/1、DE/best/1 等。從算法步驟來看，假設(shè)種群中含NP 個(gè)個(gè)體，每個(gè)代表一個(gè)問題解，各解為D 維向量，個(gè)體表達(dá)為Xi，0={xi，1，0，xi，2，0，L，xi，D，0}，滿足i=1，2，L，NP。

初始種群則為xi，j，0=xj，low+rand（0，1）·（xj，highxj，low），其中rand（0，1）服從均勻分布，在0 到1 之間隨機(jī)取值，xj，high 和xj，low 分別指的是變量分量的上下限。在變異操作中，各目標(biāo)向量將生成對(duì)應(yīng)變異向量，引入新算子參與優(yōu)解變異操作，能夠適應(yīng)種群動(dòng)態(tài)變化過程。采用不同變異策略，將得到不同的變異公式。如采用DE/rand/1，能夠得到：

式中，ui，jG+1、vi，jG+1和xi，jG+1分別指的是第i個(gè)試驗(yàn)向量、變異向量和目標(biāo)向量的G+1 代j分量，j=1，L，D。CR 為交叉概率，Jrand 為根據(jù)維數(shù)j生成的隨機(jī)數(shù)，能夠改善算法多樣性，確保至少一維分量來自變異個(gè)體，達(dá)到進(jìn)化目的。利用C R 確定試驗(yàn)向量中的變異向量個(gè)數(shù)，取值在0 ～1 范圍內(nèi)。將變異向量和目標(biāo)向量交叉獲得的試驗(yàn)向量UiG，需限制產(chǎn)生個(gè)體向量范圍，確保在規(guī)定上下限范圍內(nèi)。利用選擇算子完成目標(biāo)和試驗(yàn)向量選擇，能夠保存適應(yīng)度好的個(gè)體，作為解向量繼續(xù)迭代。

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

2.1 控制參數(shù)調(diào)整

該算法需要對(duì)多峰復(fù)雜函數(shù)進(jìn)行求解，容易因參數(shù)設(shè)置不當(dāng)導(dǎo)致種群多樣性下降，因早熟而無法找到全局最優(yōu)解。從算法控制參數(shù)來看，除了涉及縮放因子F，還包含種群規(guī)模NP 和交叉概率CR。在F 數(shù)值過大時(shí)，能夠完成潛力解挖掘，反之則能為全局最優(yōu)解的查找提供便利。而N 數(shù)值小能夠加快算法收斂，出現(xiàn)早熟或停滯情況，反之可以提高種群多樣性，但容易因計(jì)算量過大出現(xiàn)收斂慢的問題。而CR 過大，將引發(fā)多個(gè)個(gè)體變化，提高種群多樣性，有助于尋解，數(shù)值過小則能保留更多個(gè)體信息。從早期研究來看，傾向于在較小數(shù)值范圍內(nèi)取值，如使F 在（0.5，1）范圍內(nèi)取值，使CR 在（0.9，1）范圍內(nèi)取值等，缺少算法執(zhí)行過程中的信息反饋，導(dǎo)致相同參數(shù)在解決不同問題時(shí)取得的效果不同[2]。采取動(dòng)態(tài)調(diào)整策略，在各代種群中根據(jù)個(gè)體目標(biāo)函數(shù)完成參數(shù)自適應(yīng)調(diào)節(jié)，能夠取得更好的算法改進(jìn)效果。如采用FADE 算法，通過模糊邏輯控制器和知識(shí)系統(tǒng)完成不一致參數(shù)實(shí)時(shí)調(diào)整，能夠完成各代F 和CR 值調(diào)節(jié)。對(duì)前期進(jìn)化優(yōu)質(zhì)解找尋經(jīng)驗(yàn)進(jìn)行借鑒，可以采用SaDE 算法進(jìn)行F 和CR 值調(diào)整，設(shè)定為統(tǒng)一服從高斯分布，F(xiàn) 的服從均值為0.5，標(biāo)準(zhǔn)差為0.3，CR 服從均值為0.5，標(biāo)準(zhǔn)差為0.1，每25 代需要完成一次成功CR 值的更新。在NP 數(shù)值調(diào)整方面，可以采用DESAP 算法，隨機(jī)生成（10×n）種群后，n 為參數(shù)變量個(gè)數(shù)，能夠得到初始化的NPi為round（10+randn(0，1)），將縮放因子設(shè)定為1 后進(jìn)化至預(yù)先指定種群大小，能夠確定下代新種群大小。

2.2 操作算子改進(jìn)

在算法操作中，包含變異、交叉和選擇算子。選擇算子僅根據(jù)適應(yīng)度值確定，相對(duì)簡(jiǎn)單，因此算子改進(jìn)研究主要針對(duì)變異算法和交叉算子。在變異算子改進(jìn)方面，目前提出的策略包含DE/current-to-rand/1、三角變異策略、DE/rand/1/either-or 等多種。采用不同算子，能夠通過取長(zhǎng)補(bǔ)短適應(yīng)種群進(jìn)化。如在JADE 算法中，可以采用DE/current-to-pbest/1 策略，得到vi，G=xi，G+Fi（xbest，G-xi，G）+Fi（xr1，G-xr2，G），可知指的是種群目前尋到的最優(yōu)個(gè)體，F(xiàn)i則為個(gè)體j 的縮放因子，除了來自外部較差個(gè)體存檔A和種群P 的并集，其余個(gè)體均來自種群P。此外，也可以將個(gè)別解協(xié)方差矩陣特征向量當(dāng)成是算子進(jìn)行交叉操作，具有旋轉(zhuǎn)不變性特征。運(yùn)用該算子進(jìn)行算法改進(jìn)，能夠使供體個(gè)體得到修改，然后投影至替代坐標(biāo)系特征向量上，適用于變化小的交叉策略[3]。

2.3 種群結(jié)構(gòu)優(yōu)化

通過優(yōu)化種群結(jié)構(gòu)方式進(jìn)行算法改進(jìn)，能夠?qū)λ惴ㄊ諗啃阅墚a(chǎn)生影響。如使用環(huán)形網(wǎng)絡(luò)拓?fù)鋵?shí)施并行運(yùn)算，能夠提高算法收斂速度。而采用分布式算法或自適應(yīng)算法，能夠優(yōu)化算法性能。如采用平均熵初始化策略完成種群拆分，利用不同變異策略加強(qiáng)種群信息交流，能夠完成種群差分運(yùn)算。利用自適應(yīng)值大小完成多種群分類，實(shí)施不同進(jìn)化策略可以完成全局優(yōu)化。采用反向的差分進(jìn)化算法，需要進(jìn)行反向搜索，能夠使種群的多樣性得到改善，達(dá)到跳出局部最優(yōu)的目的。此外，利用島嶼模型進(jìn)行并行分布運(yùn)算，將種群劃分為多個(gè)獨(dú)立亞種群，然后完成不同控制參數(shù)分配，可以得到固定世代間隔。使不同種群相互遷移，能夠確保亞種群始終體現(xiàn)良好多樣性，有助于算法改良。

2.4 混合算法分析

各種智能算法是基于不同現(xiàn)象和行為產(chǎn)生的，適用于不同場(chǎng)景?？紤]到采用單一算法存在較大局限性，可以通過將不同算法結(jié)合實(shí)現(xiàn)原有算法改進(jìn)。如在解決電力系統(tǒng)參數(shù)配置問題時(shí)，將DE 算法和粒子群算法融合，能夠加強(qiáng)種群開發(fā)和探索。利用標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行算法驗(yàn)證，能夠保證算法穩(wěn)定性。MDE-WOA 算法同樣為混合算法，可以在差分進(jìn)化運(yùn)算中嵌入壽命機(jī)制，通過增強(qiáng)算法搜索能力解決局部最優(yōu)問題，形成的算法不僅具有較強(qiáng)魯棒性，也能獲得較高準(zhǔn)確性。在解決車輛路徑規(guī)劃問題時(shí)，將DE算法與蜂群算法結(jié)合，在迭代中引入進(jìn)化算子，改善蜂群進(jìn)化速度慢的問題，能夠使形成的算法獲得較強(qiáng)魯棒性，并能實(shí)現(xiàn)全局收斂，保證算法的有效性[4]。針對(duì)組合優(yōu)化問題，可以將DE 算法和量子算法結(jié)合在一起，增強(qiáng)算法魯棒性，提高數(shù)據(jù)運(yùn)算效率。現(xiàn)階段，能夠與差分進(jìn)化算法結(jié)合的人工智能算法有較多，需要結(jié)合實(shí)際應(yīng)用需求選擇，確保算法混合能夠解決收斂、尋優(yōu)等問題，取得理想的算法應(yīng)用效果。

3 差分進(jìn)化算法的改進(jìn)實(shí)踐

3.1 約束優(yōu)化問題

約束優(yōu)化問題在生活中較為常見，但求解算法較少，面臨搜索空間復(fù)雜、約束條件難處理等困難。在解決約束優(yōu)化問題時(shí)，可知包含等式、不等式和邊界等不同約束條件，得到：

式中，f(x)為目標(biāo)函數(shù)，x=（x1，x2，...xn），取值范圍D 為n 維度決策空間，gj(x)和hj(x)分別為不等式和等式約束，p、q 分別為約束個(gè)數(shù)，ui和li為xi的上下界。根據(jù)x 到j(luò) 個(gè)約束的距離，可知x 到可行域間距離為約束違反程度G(x)：

式中，Gj(x)指的是x 到j(luò) 約束距離，δ 為正容忍因子，取值為0.000 1。

3.2 基于GOBL 的算法

在差分進(jìn)化算法改進(jìn)方面，采用自適應(yīng)約束方式過于強(qiáng)調(diào)判斷個(gè)體是否達(dá)到約束條件，導(dǎo)致種群中不可行個(gè)體數(shù)量過多，容易出現(xiàn)尋解精度不高問題。采用反向?qū)W習(xí)策略（GOBL）進(jìn)行種群結(jié)構(gòu)優(yōu)化，利用反向種群約束種群搜索空間，能夠根據(jù)反向解信息加快運(yùn)算[5]。根據(jù)可行率采取不同變異策略，實(shí)現(xiàn)算子自適應(yīng)設(shè)計(jì)，能夠提高種群多樣性。將變異前后的種群混合，排序后完成不同個(gè)體選擇，可以獲得新種群。應(yīng)用該算法，可知n 維空間中xi存在對(duì)應(yīng)反向解，得到：

式中，k 在0 到1 范圍內(nèi)取值，xi在j 維取值在aj和bj之間，超出這一區(qū)域需要采用rand 函數(shù)隨機(jī)生成xi，j數(shù)值。根據(jù)反向解縮小搜索空間，可以在初始化種群P 和新種群P1中選取數(shù)量為Np的個(gè)體。在處理無法滿足條件的個(gè)體時(shí)，應(yīng)利用自適應(yīng)權(quán)衡模型ATM 將種群劃分為可行、不可行、半可行3 種狀態(tài)，將目標(biāo)函數(shù)轉(zhuǎn)換為：

式中，σ 指的是可行率，xbest 和xworst 則為最好和最差個(gè)體，Z1和Z2分別為滿足和不滿足約束條件的個(gè)體序號(hào)。通過完成目標(biāo)函數(shù)值和違約值的標(biāo)準(zhǔn)化處理，能夠得到個(gè)體適應(yīng)值：

式中，ffanal(xi)指的是最終適應(yīng)值，fnor(xi)和Gnor(xi)分別為目標(biāo)函數(shù)值和違約值的標(biāo)準(zhǔn)化值，在可行時(shí)說明可以滿足全部約束條件，可以利用目標(biāo)函數(shù)值代表。按照傳統(tǒng)差分進(jìn)化算法，需要將父代向量中個(gè)體和新種群個(gè)體逐個(gè)比較，選擇適應(yīng)值更優(yōu)的個(gè)體，可能出現(xiàn)兩個(gè)適應(yīng)值均較差個(gè)體相互比較，導(dǎo)致留下的個(gè)體適應(yīng)值較大，影響收斂速度的同時(shí)，出現(xiàn)局部最優(yōu)問題。為改進(jìn)這一情況，需要完成父代種群和新種群合并，完成適應(yīng)值排序，然后進(jìn)行個(gè)體優(yōu)選。

3.3 改進(jìn)算法步驟

按照算法改進(jìn)方法，需要先根據(jù)適應(yīng)值完成個(gè)體排序，然后計(jì)算選擇概率：

式中，Ri為個(gè)體排序值，N 為種群個(gè)體數(shù)量，λ 取值將影響參與變異個(gè)體，決定最優(yōu)解搜索范圍，體現(xiàn)個(gè)體支配關(guān)系。在λ 取值為2 的情況下，個(gè)體選擇概率差值較大，支配關(guān)系更加顯著。而λ 取值為0.5，支配關(guān)系相對(duì)模糊。因此將λ 取值為2，能夠在進(jìn)化初期使不可行個(gè)體達(dá)到約束，獲得更多個(gè)體，依靠適應(yīng)值大的個(gè)體加快搜索。在種群可行時(shí)，則能降低稍差個(gè)體選擇概率，減少參與變異的個(gè)體，容易陷入局部最優(yōu)問題，因此應(yīng)使λ 取值為0.5。在采取變異策略時(shí)，比較不同策略可知，想要提高種群多樣性需要進(jìn)行自適應(yīng)變異，得到：

式中，各x 變量為t 代不同個(gè)體，vi，t為變異后試驗(yàn)向量，xgbest為適應(yīng)值最優(yōu)個(gè)體?？s放因子F 在0 到2 之間取值，可知早期進(jìn)化時(shí)個(gè)體較少，可行率較小，應(yīng)選擇DE/best/2 策略，利用最優(yōu)個(gè)體資源對(duì)其他變異個(gè)體進(jìn)行引領(lǐng)，達(dá)到快速收斂效果。在進(jìn)化后期可行個(gè)體增加，可行率也有所增大，應(yīng)選擇DE/rand/2 策略改善種群多樣性?？紤]到控制參數(shù)F 和CR 將給算法尋優(yōu)帶來影響，需要采用自適應(yīng)算子，得到：

式中，Gen 指的是最大迭代次數(shù)，t 為當(dāng)前迭代次數(shù)，F(xiàn)0則為常數(shù)，在0 到1 范圍內(nèi)取值。在F0數(shù)值較小時(shí)，算法收斂慢，但過大將出現(xiàn)尋優(yōu)能力下降問題，通過反復(fù)測(cè)試最終取值0.5。在早期進(jìn)化過程中，多數(shù)個(gè)體適應(yīng)值不佳，應(yīng)增加F 數(shù)值以獲得更大搜索范圍，提升種群多樣性。而經(jīng)過多次迭代后，可以逐漸使F 趨近于F0，盡可能保留優(yōu)秀個(gè)體，增加最優(yōu)解查找概率。

3.4 算法測(cè)試分析

為確定算法改進(jìn)效果，需要在問題處理時(shí)與標(biāo)準(zhǔn)DE算法和常見RMDE 算法進(jìn)行比較。在算法種群規(guī)模NP 達(dá)到100 時(shí)，將各算法迭代次數(shù)設(shè)定為1 500 代，利用g02、g03 和g06 函數(shù)分別執(zhí)行不同算法，然后對(duì)3 種算法的平均值等指標(biāo)進(jìn)行比較。如表1 所示，最終驗(yàn)證改進(jìn)算法可以獲得更好的尋優(yōu)精度。

表1 測(cè)試結(jié)果

4 結(jié)論

對(duì)差分進(jìn)化算法進(jìn)行改進(jìn)，可以采取調(diào)整控制參數(shù)、優(yōu)化種群結(jié)構(gòu)等多種方法。實(shí)際在改進(jìn)方法運(yùn)用過程中，需要結(jié)合實(shí)際需解決的問題選擇適合的改進(jìn)方法，如在解決約束優(yōu)化問題時(shí)需同時(shí)采取調(diào)整控制參數(shù)、改進(jìn)操作算子等措施，確保能夠加強(qiáng)優(yōu)秀個(gè)體資源利用，達(dá)到提高算法精度的目標(biāo)。