改進的差分演化算法及其在函數優化中的應用

(許昌學院 信息工程學院，河南 許昌461000)

在復雜的工程設計應用領域中經常會涉及到一些較為復雜函數優化問題, 這些函數的特點往往是非線性、不可導、不連續、多峰值、多極值、凹凸性不明確, 而且時常還帶有各類的約束條件, 因此, 利用傳統的數學方法(共軛梯度法、單純性法等)很難得到理想的結果. 近年來, 許多學者把演化算法應用到復雜函數優化問題中, 取得較好的效果.差分演化算法就是其中的一種，差分演化算法(Differential Evolution, DE)[1]是由Storn 和Price科學家在1995年提出的一種高效簡單的全局優化算法.本算法最大的優勢在于差分變異算子具有較好的自搜索方向、自搜索步長等特點.目前，該算法已經較成功的應用在多個實際工程應用領域，如神經網絡、模式識別、數據挖掘、濾波器設計、電路優化設計、函數優化等問題中.

原始的差分演化算法里面主要涉及到三個基本參數：雜交概率CR；縮放因子F；種群規模NP；相關研究[2-4]表明，算法成功的關鍵就是參數的正確選擇.傳統的參數設置大部分是根據經驗來進行設置，如果參數設置不合理，可能導致算法效率不高，算法容易陷于局部最優，JDE[5]、SADE[6]、CoDE[7]等是目前較好的自適應差分演化算法，每種算法也有其各自的優劣勢.

基于以上的問題，本文對基本差分演化算法進行了改進, 提出一種改進的差分演化算法(本文的算法簡稱IDE算法), 該算法的主要特征是: 提出了混合混沌和逆向學習算子來初始化種群，保持種群的多樣性，加快算法的收斂速度，同時增強算法的全局搜索能力；提出了隨機排序的選擇策略，避免算法提前陷于局部最優，通過國際上標準的測試函數進行驗證本算法的優越性.

1 問題的描述

本文研究以最小化函數優化為目標，如公式1所示，其中S?RD,RD稱為搜索空間,D是變量維數,f(x)為目標函數，X是n維解向量X=[x1,x2,…,xn]T, 每個自變量xi滿足一定的約束條件，如公式2所示.最終的目標為求解目標函數的最小值作為最優，記做min(f(x)).

X=(x1,x2,…,xn)∈Rn，

(1)

Li≤xi≤Ui,i=1,2,…,n.

(2)

2 算法思路與框架流圖

差分演化算法求解函數優化問題需要通過對不同個體進行雜交，變異，選擇，優勝劣汰等自適應操作，經過若干代演化，求出算法的相對的最優解.基本的差分演化化算法求解問題偽代碼如表1所示[8]，其中從第5行到第13行是DE/rand/1/bin算法的變異策略；第9行是DE/rand/1算法的變異算子；第17行到第19行選擇算子rndint(1,D)函數表示在[1,D]區間隨機均勻生成整數變量，自變量維數為D；rndreal[0,1]函數代表在[0,1]之間隨機均勻產生浮點數.算法停機條件設置為演化代數、適應值的評價次數的極限等，需要用戶預先設置.

表1 求解問題偽代碼

3 實現的關鍵技術設計

3.1 混沌算子和逆向學習算子混合初始化種群

基本的差分演化算法采用隨機方法來生成初始化種群，由于隨機函數的性質，導致種群的不確定性，最終帶來結果的不穩定，為了盡量減小初始化種群對算法結果的最終影響，本文提出了混沌算法來初始化種群, 有效的改善了種群多樣性與穩定性，加快了算法的收斂速度.生成初始化種群的方法如表2所示，部分參數如下：迭代次數N=500，m=3.88，X=(X1,X2,Xi,…,XSD) 為最終的種群.

表2 初始化種群的方法

3.2 改進的選擇策略

在演化算法中，群體的多樣性對算法能否快速收斂到全局最優解極為重要，群體的多樣性越大，算法陷入局部最優解的可能性越小，為了盡可能保持群體的多樣性，本文算法克服傳統的算法容易陷于局部最優解的思想，提出了采用了隨機排序選擇策略來保持種群的多樣性，避免陷于局部最優解，根據適應度函數值進行排序時，通過一個隨機排序控制參數μ來控制排序過程，從而可以對排序結果進行一定的擾動，算法隨機排序過程描述為表3.

表3 算法隨機排列過程表

通過實驗發現μ值越大， 其隨機擾動就會越小，NP代表種群的規模，文中設置為100，種群所有個體執行每代算法后，按照小到大順序排序，按照排序的結果，從中選擇α個個體形成選擇群體，本文的α=4.

4 實驗與結論

4.1 實驗環境及參數設置

為了驗證本文提出了IDE算法的性能，我們選擇了國際通用標準22個測試函數[9]進行了測試，測試函數大概可以劃分為三大類(1)單峰測試函數f1-f5;(2)多峰測試函數f06-f14;(3)混合單峰、多峰測試函數(f15-f22).這些測試函數絕大多數具有位移或旋轉等特性，用普通的數學辦法很難求得最優解.

本文中所有參數如下:群體規模:M=100; 雜交概率: CR=0.85; DE策略: DE/rand/1/bin; 最大評價次數極限: NFFE=250 000; 父個體數目:P=6; 停機精度:ε=1e-30; 決策變量分塊大小: 當自變量維數N>8時,F=2; 其他,F=N; 等式約束容差:η=0.000 01，每個函數獨立運行50次，各類算法在相同條件下，運行的最優解如下表4所示.

4.2 結果與分析

本文提出的IDE算法以及被比較的其它三種算法，按照相同的測試函數重復進行50次獨立實驗，得出實驗數據，從表4來看，對于絕大多數測試函數, IDE算法比其它SADE、JDE和CODE算法都獲取了較理想的最優解，其它測試函數(如f12,f18,f19,f20)IDE與其它方法基本持平，表中加粗的部分表示四種方法的最好結果.因此本文提出用混沌算法與逆向學習算子相結合來初始化種群與隨機排序的選擇策略應用在函數優化問題中，在絕大多數測試函數本文的方法均優于被比較的其它算法.

表4 五種不同算法最優結果數據比較表