一種隨機變異策略的改進DE算法

劉龍龍

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

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

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

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

1標準DE算法

標準差分進化算法通過種群間的差異性進行進化，具有結構簡單、容易實現、受控參數少等優點，其主要步驟包括以下幾項：

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

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

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

其中， 表示變異產生的中間個體， 為第 代的第 個父代個體， 且互異， 為第 個變異個體的第 個元素， 為變異算子，其在標準算法中為常數。

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

其中， 為經交叉操作后產生的新個體， 為交叉算子，標準算法中 為常數， 為 間的整數。

4） 選擇. 在該操作中，標準DE算法通過對比父代個體與交叉產生的新個體的適應度大小，選擇其中適應度較小的個體進入新種群。選擇策略如下所示：

5） 判斷是否結束. 計算目標函數值并對比目標函數值與結束條件，若滿足，則結束；否則算法繼續迭代。

2改進DE算法

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

2.1自適應變異算子.

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

2.2隨機變異策略

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

其中， 為變異產生的子代個體， 為0～1間的隨機數， 為算法的當前最優解， 且互不相同。

2.3自適應交叉算子

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

其中， 與 分別表示當前迭代次數與最大迭代次數。

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

2.4改進算法測試

為了檢驗IRDE算法的效果，采用4個基準函數（見表1）對IRDE算法進行測試。為了更好的體現出IRDE算法的改進效果，將IRDE算法與jDE（現有改進算法）]和標準DE算法進行比較，將三個算法的部分參數設置為： ，標準DE算法中， ，測試結果見表2.

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

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

3結論

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

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

（作者單位：東華理工大學理學院）