一種隨機(jī)變異策略的改進(jìn)DE算法

劉龍龍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2改進(jìn)DE算法

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

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

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

2.2隨機(jī)變異策略

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

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

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

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

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

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

2.4改進(jìn)算法測(cè)試

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

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

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

3結(jié)論

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

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

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