劉龍龍

差分進化算法存在進化后期收斂變慢，易陷入局部最優(yōu)等情況，本文從差分進化算法的變異算子，變異策略等方面改進，提出一種新的改進差分進化算法（IRDE）。利用4個基準(zhǔn)函數(shù)對IRDE算法進行檢驗，檢驗結(jié)果表明，本文提出的改進方式能夠有效的提升DE算法的收斂速度和全局尋優(yōu)能力。

差分進化算法（DE，Differential Evolution）是在1995年被Stron等人提出的一種智能尋優(yōu)算法，該算法的主要思想是在解空間中以隨機初始化的方式產(chǎn)生第一代個體，并通過變異、交叉、選擇等策略在解空間中尋找適應(yīng)度最好的個體作為最優(yōu)個體輸出。該算法具有魯棒性較強，簡單易實現(xiàn)等特點，因此受到了相關(guān)研究人員的關(guān)注。由于DE算法種群中個體的差異程度會影響算法進化效率，而在算法運行后期，種群間個體的相似程度較高、差異性較小，導(dǎo)致算法的進化效率變低、收斂能力下降。針對該不足之處，當(dāng)前最為常見的改進方式主要有兩類：一種是對算法本身的公式或參數(shù)進行改進；第二類是將兩種算法結(jié)合，形成更具優(yōu)勢的新算法。

文獻中作者將現(xiàn)有策略DE/rand/1與DE/best/1組合形成一種多變異策略的改進DE算法，并利用4個Benchmark函數(shù)對改進算法進行測試，測試結(jié)果表明該改進方法取得了較好的效果。文獻中作者對算法后期的易陷入局部最優(yōu)的情況進行分析，在對種群的多樣度理論進行研究的基礎(chǔ)上，提出一種可以改善種群多樣性的改進差分進化算法。文獻中作者分別引入變異策略、縮放因子以及交叉參數(shù)的候選集，通過運行過程中的歷史信息來自適應(yīng)的選擇變異策略、縮放因子以及交叉參數(shù)進行組合，提出了一種新的改進差分進化算法（SMDE），并采用10個測試函數(shù)對其進行測試。文獻中作者將PSO算法中的社會學(xué)習(xí)機制與差分進化算法相結(jié)合，通過隨機變異操作來增加種群的多樣性，保證算法的全局尋優(yōu)能力，并利用最優(yōu)個體信息指引種群進化方向，經(jīng)過測試表明，改進算法具有較好的優(yōu)化效果。文獻中作者將模擬退火算法中的模型退火操作引入到DE算法中，通過模型退火算子的突變搜索能力增加算法的種群多樣性，增強算法的全局尋優(yōu)能力。

本文主要采用第一類改進方式，在標(biāo)準(zhǔn)DE算法的基礎(chǔ)上，對其變異算子，變異策略等進行改進，提出一種新型的改進差分進化算法（IRDE）。

1標(biāo)準(zhǔn)DE算法

標(biāo)準(zhǔn)差分進化算法通過種群間的差異性進行進化，具有結(jié)構(gòu)簡單、容易實現(xiàn)、受控參數(shù)少等優(yōu)點，其主要步驟包括以下幾項：

1） 初始化. 此階段為算法的起始階段，在該步驟中，需要確定算法參數(shù)以及種群初始化的方式。標(biāo)準(zhǔn)DE算法中的種群初始化方式如下所示：

其中， 為第一代種群， 為種群中個體元素的取值下界， 為元素的取值上界， 為種群規(guī)模， 為每個個體的長度（即個體中元素的數(shù)量）。

2） 變異. 在該步驟中，DE算法隨機從父代種群中選取三個個體進行變異操作，選擇其中的一個作為待變異個體，利用剩余兩個個體進行差分操作，并將其差分結(jié)果與變異算子相乘后與待變異個體相加，產(chǎn)生變異后的新個體，變異策略如式（2）所示，之后對該新個體中元素的取值進行篩選，防止出現(xiàn)超出給定范圍的元素，其篩選方式如（3）式所示。

其中， 表示變異產(chǎn)生的中間個體， 為第 代的第 個父代個體， 且互異， 為第 個變異個體的第 個元素， 為變異算子，其在標(biāo)準(zhǔn)算法中為常數(shù)。

3） 交叉. 交叉操作有利于增加算法的種群多樣性，在該步驟中，將按照一定的規(guī)則，從變異產(chǎn)生的個體與父代個體中選擇元素組成新個體，交叉策略所遵循的規(guī)則如下：

其中， 為經(jīng)交叉操作后產(chǎn)生的新個體， 為交叉算子，標(biāo)準(zhǔn)算法中 為常數(shù)， 為 間的整數(shù)。

4） 選擇. 在該操作中，標(biāo)準(zhǔn)DE算法通過對比父代個體與交叉產(chǎn)生的新個體的適應(yīng)度大小，選擇其中適應(yīng)度較小的個體進入新種群。選擇策略如下所示：

5） 判斷是否結(jié)束. 計算目標(biāo)函數(shù)值并對比目標(biāo)函數(shù)值與結(jié)束條件，若滿足，則結(jié)束；否則算法繼續(xù)迭代。

2改進DE算法

文獻指出，差分進化算法的收斂速度和尋優(yōu)能力與算法的種群多樣性有著較大的關(guān)系。算法中變異算子的取值、變異策略的選取以及交叉算子的取值均會對算法的種群多樣性產(chǎn)生一定影響，因此，本文將從變異算子、交叉算子以及變異策略對標(biāo)準(zhǔn)DE算法進行改進。

2.1自適應(yīng)變異算子.

從式（2）中可以看出， 的取值大小會對進化產(chǎn)生的新個體的生成位置產(chǎn)生影響。若給 賦予一個較大值，會增加算法的搜索范圍，有利于尋找全局最優(yōu)解，若給 賦予一個較小值，則算法會在一個較小的范圍內(nèi)進行尋優(yōu)操作，有利于算法加速收斂。因此，在算法初期應(yīng)給 賦予較大值，后期給 賦予一個較小值，基于此思想，提出一種遞減型變異算子，該算子前期取值為0.8，并隨著進化次數(shù)增加而逐漸減小，該算子的表達(dá)形式如下所示：

2.2隨機變異策略

標(biāo)準(zhǔn)DE算法中，變異策略為固定形式。本文為了增加變異個體的隨機性，對變異策略作出改進，通過設(shè)置一個隨機數(shù) （ ），比較 與變異算子的大小來選擇變異策略。由于 具有隨機性，因此，在IRDE算法中，變異策略將是隨機的。隨機變異策略的表達(dá)形式如下所示：

其中， 為變異產(chǎn)生的子代個體， 為0～1間的隨機數(shù)， 為算法的當(dāng)前最優(yōu)解， 且互不相同。

2.3自適應(yīng)交叉算子

交叉操作產(chǎn)生的新個體中的染色體主要來源于父代個體以及變異產(chǎn)生的子代個體。在該操作中， 的取值大小控制著新個體中父代個體染色體所占比例， 越小，更有利于保存父代個體的染色體，可以較好的實現(xiàn)全局尋優(yōu)；反之，有利于算法加速收斂?；谶@一情況，設(shè)置 的表達(dá)式如下。

其中， 與 分別表示當(dāng)前迭代次數(shù)與最大迭代次數(shù)。

由于本文僅在上述三處地方進行了改進，因此，其余操作均參照標(biāo)準(zhǔn)DE算法進行。

2.4改進算法測試

為了檢驗IRDE算法的效果，采用4個基準(zhǔn)函數(shù)（見表1）對IRDE算法進行測試。為了更好的體現(xiàn)出IRDE算法的改進效果，將IRDE算法與jDE（現(xiàn)有改進算法）]和標(biāo)準(zhǔn)DE算法進行比較，將三個算法的部分參數(shù)設(shè)置為： ，標(biāo)準(zhǔn)DE算法中， ，測試結(jié)果見表2.

從表2中可以看出，IRDE算法在對4個函數(shù)的尋優(yōu)測試中，除函數(shù)Schwefels2.21外，其余函數(shù)均可以尋找到最優(yōu)解，對于Schwefels2.21，IRDE算法也具有較高的收斂精度。相同情況下，在對jDE算法進行測試時，Schwefels2.26與Rastrigins函數(shù)存在一定的幾率尋優(yōu)成功，其余函數(shù)，jDE算法無法尋找到最優(yōu)解。標(biāo)準(zhǔn)DE算法在所有測試函數(shù)的測試過程中均無法找到最優(yōu)解。下文給出了4個函數(shù)測試效果圖。

從表2的測試結(jié)果及4個基準(zhǔn)函數(shù)的測試效果圖可以看出，本文算法在收斂速度、收斂精度以及全局收斂能力上均有一定的提升。

3結(jié)論

本文主要針對標(biāo)準(zhǔn)差分進化算法存在的收斂速度慢、收斂精度低的不足進行改進，提出了一種擁有自適應(yīng)變異算子、隨機變異策略以及自適應(yīng)交叉算子的改進差分進化算法（IRDE），并通過與jDE算法和標(biāo)準(zhǔn)DE算法的尋優(yōu)效果對比，結(jié)果表明，IRDE算法實現(xiàn)了收斂速度更快，收斂精度更高以及全局尋優(yōu)能力更強的目的，這一實驗結(jié)果證明了本文所提出的改進策略的有效性。

但是也存在一定的不足之處，在本文選取的測試函數(shù)中，仍存在一個函數(shù)無法尋到最優(yōu)解，后期還需要繼續(xù)對算法的全局尋優(yōu)能力及收斂速度進行研究。且本文算法僅在基準(zhǔn)函數(shù)上進行了測試，后期還需要考慮到算法的實際應(yīng)用，例如：將IRDE與SVM組合并應(yīng)用于實例。

（作者單位：東華理工大學(xué)理學(xué)院）