徐英杰,閻曉琳,鄧 武

(1.大連交通大學 軟件學院,遼寧 大連 116028；2.大連交通大學，機械工程學院，遼寧 大連 116028)

差分進化(differential evolution，DE)算法是一種基于自然界中種群進化過程的隨機搜索算法[1].該算法采用實數(shù)編碼，原理簡單，易于理解和實現(xiàn)，具有較強的魯棒性、控制參數(shù)少、搜索能力強，是一種簡單高效的進化算法.近年來，在工程設(shè)計、運籌學、生物醫(yī)學等眾多領(lǐng)域取得了良好的應(yīng)用效果，但是也容易出現(xiàn)早熟和陷入局部最優(yōu)等問題.在進化過程，DE的控制參數(shù)(收縮因子、交叉概率等)需人工設(shè)置，這樣每代種群的所有個體均采用相同參數(shù)，而適用于不同優(yōu)化問題、不同進化階段和不同個體的控制參數(shù)一般并不相同，因此如何為DE算法設(shè)計有效而可靠的參數(shù)非常重要.

近年來，諸多學者為了提高DE的性能而開展了大量工作.主要包括以下幾方面：設(shè)計變異算子、自適應(yīng)調(diào)整參數(shù)、引入有效搜索策略、結(jié)合其他優(yōu)化算法、多策略多種群并行搜索等[2-10].Mallipeddi等[5]提出的改進DE算法(EPSDE)，該算法設(shè)置了不同的變異、交叉策略池和控制參數(shù)池，提高了算法的優(yōu)化性能.Qin等[6]提出的一種自適應(yīng)差分進化算法(SaDE)，設(shè)計了學習策略自適應(yīng)，加快了算法的收斂速度，但學習過程較復(fù)雜.Wang等[7]提出了復(fù)合差分進化算法(CoDE)，該算法在3種不同變異策略中隨機選取一種策略進行變異操作，產(chǎn)生后代個體，但不能根據(jù)前驗自適應(yīng)選擇相關(guān)策略，缺乏必要學習過程.

因此，在對DE算法研究基礎(chǔ)上，引入小波基函數(shù)，提出一種基于小波基函數(shù)的差分進化算法縮放因子改進方法.該方法采用小波基函數(shù)來改進DE縮放因子F，以保證解的多樣性、加速算法收斂和提高算法性能.選擇5個標準測試函數(shù)來驗證改進DE算法的有效性.

1 差分進化算法

1.1 差分進化算法概述

差分進化算法是一種基于群體智能的啟發(fā)式優(yōu)化算法，利用個體之間的差異性，使算法在種群進化過程中進行隨機搜索.其主要思想是將同一群體中2個不相同的個體向量進行差分操作，與該群體中的第3個個體向量做運算得到一個目標個體向量，然后目標個體向量與個體向量進行交叉生成試驗個體向量；最后將試驗個體向量與個體向量進行比較選擇，適應(yīng)度值小的個體向量進入下一代種群.差分進化算法的基本進化過程描述如下[11-12].

1.2 初始化

DE算法采用NP個D維向量作為初始解設(shè)種群數(shù)量N，每個個體可表示為xi(G)=(xi1(G),xi2(G),…,xiD(G)) ，初始種群在[xmin,xmax] 中產(chǎn)生：

xiD=xmin+rand(0,1)×(xmax-xmin),

(1)

其中，G表示第G代，xmax表示搜索空間的最大值，xmin表示搜索空間的最小值.rand(0,1)表示在(0,1)內(nèi)的隨機數(shù).

1.3 變異

DE算法使用變異操作生成當前種群中的每個個體xi(G)的目標個體向量Vi(G) .對于生成的每個個體向量，通過一定的變異策略生成相應(yīng)的目標個體向量.目前最常用的變異策略.

1)“DE/rand/1”:

Vi(G)=xr1(G)+F·(xr2(G)-xr3(G)),

(2)

2)“DE/best/1”

Vi(G)=xbest(G)+F·(xr1(G)-xr2(G)),

(3)

3)“DE/rand-to-best/1”

Vi(G)=xi(G)+F·(xbest(G)-xi(G))+F·(xr1(G)-xr2(G)),

(4)

4)“DE/best/2”

Vi(G)=xbest(G)+F·(xr1(G)-xr2(G))+F·(xr3(G)-xr4(G)),

(5)

5)“DE/rand/2”

Vi(G)=xr1(G)+F·(xr2(G)-xr3(G))+F·(xr4(G)-xr5(G)),

(6)

式中，索引r1,r2,r3,r4,r5是在[1,NP]內(nèi)隨機生成的不同整數(shù).縮放因子F是差分向量的一個控制參數(shù).xbest(G) 是群體在第G代中具有最佳適應(yīng)度值的個體向量.

1.4 交叉

變異結(jié)束后，對每一個個體向量xi(G) 及其對應(yīng)的目標個體向量Vi(G)進行交叉操作，生成對應(yīng)的試驗個體向量：Ui(G)=(u1(G),u2(G),…,ui(G)) .使用二項交叉定義如下：

(7)

其中，交叉率CR是(0,1)之間指定的常數(shù)，jrand是[1,D]內(nèi)隨機的隨機整數(shù).

1.5 選擇

計算試驗個體向量Ui(G)和對應(yīng)的個體向量Xi(G)的適應(yīng)度值，進行比較并執(zhí)行選擇操作.將每個試驗向量的適應(yīng)度值f(Ui(G))與當前種群中相應(yīng)的個體向量的適應(yīng)度值f(Xi(G))比較，如果試驗個體向量的適應(yīng)度值小于或等于相應(yīng)的個體向量適應(yīng)度值，則試驗個體向量取代對應(yīng)的個體向量，進入下一代種群.選擇操作可以表示為：

(8)

2 基于小波基函數(shù)的差分進化算法縮放因子改進方法

當所優(yōu)化求解的目標不同時，需要建模的數(shù)學特征也不相同，使DE算法具有不同的搜索步長.當解距離最優(yōu)點較遠時，較長搜索步長有利于算法收斂到最優(yōu)解空間，而當解距離全局最優(yōu)點較近時，較小搜索步長有利于算法準確找到更優(yōu)解[13].因此，DE算法縮放因子F與搜索步長密不可分.因此DE算法縮放因子F的選擇至關(guān)重要.

針對DE算法縮放因子F選擇問題，充分利用小波基函數(shù)的特點，提出一種基于小波基函數(shù)的差分進化算法縮放因子改進方法，有效實現(xiàn)DE算法縮放因子F的改進.常用小波基有Haar小波、Daubechies(dbN) 小波、Mexican Hat(mexh)小波、Morlet小波、Meyer小波等[14].由于Mexican Hat(mexh)小波Mexican Hat函數(shù)為Gauss函數(shù)的二階導(dǎo)數(shù)，具有在時間域與頻率域都有很好的局部化的特點.因此，DE算法縮放因子F的改進策略如下：

(9)

采用Mexican hat(mexh)小波改進的DE算法縮放因子F，其值在(0,1)之間隨機取值，求解不同的問題時能夠取得所需的搜索步長，即控制因子F的值，使算法避免出現(xiàn)早熟，防止收斂到局部最優(yōu)，同時也增加了解的多樣性.DE算法縮放因子F的取值，見圖1所示.

改進DE算法詳細步驟描述如下.

Step 1 在(xmin,xmax) 中隨機產(chǎn)生初始種群，并初始化參數(shù)，種群大小NP=100，維數(shù)D=30，最大迭代次數(shù)Gmax=2000；初始迭代次數(shù)G=1.

Step 3 進行變異操作，對每個個體向量Xi(G) 用變異策略產(chǎn)生對應(yīng)的目標個體向量Vi(G) .

Step 4 進行交叉操作，在(0,1)中產(chǎn)生隨機數(shù)與交叉率CR比較，若小于CR，選取步驟三產(chǎn)生的目標個體向量Vi(G)作為試驗個體向量Ui(G)，反之，選取當代的個體向量Xi(G) 作為試驗向量Ui(G) .

Step 5 進行選擇操作，計算目標個體向量Xi(G)和試驗個體向量Ui(G)的適應(yīng)度值，進行比較，選取適應(yīng)度值小的作為Xi(G+1)并進入下一代種群中.

Step 6 若達到最大迭代次Gmax=2 000，輸出最優(yōu)值，否則跳到Step 2.

3 實例驗證與分析

3.1 測試函數(shù)的選擇

為了驗證改進DE算法的有效性，選擇5個測試函數(shù)對算法進行了測試，5個函數(shù)描述見表1.并與標準DE算法5種策略進行了比較.其中f1～f3是單峰函數(shù)，主要用于評價算法精確度、收斂速度等，f4～f5是多峰函數(shù)，主要用于評價算法的全局搜索性能和穩(wěn)定性[15].算法的參數(shù)設(shè)置，見表2所示.

表1 測試函數(shù)描述

表2 改進DE算法參數(shù)設(shè)置

3.2 實驗結(jié)果

5個測試函數(shù)的測試結(jié)果及其比較，見表3所示，并且最優(yōu)值、平均值和標準差被用來評價算法的有效性.5個測試函數(shù)的迭代曲線，見圖2所示.

表3 實驗結(jié)果對比分析

3.3 結(jié)果分析

從表3可以看出，對于求解的5個測試函數(shù)，改進的DE算法有較好的最優(yōu)值、平均值和標準差，說明改進的DE算法具有較好的穩(wěn)定性和較強的尋優(yōu)能力.從圖2可以看出，對于測試函數(shù)f1，改進的DE算法在迭代初期就表現(xiàn)出了良好的優(yōu)化性能，迭代曲線下降快，精度高.對于測試函數(shù)f2，改進的DE算法表現(xiàn)出相對較好的優(yōu)勢，在整個迭代過程中，尋優(yōu)能力強.對于測試函數(shù)f3，無論在尋優(yōu)能力還是在收斂性方面，改進的DE算法優(yōu)于其它策略.對于測試函數(shù)f4和f5，明顯可以看出改進的DE算法優(yōu)化效果極優(yōu).從圖2總體可知，對于測試函數(shù)f1～f3，改進的DE算法收斂曲線下降速度較快，能快速趨向于函數(shù)最優(yōu)值.對于測試函數(shù)f4～f5，可以看出改進的DE算法曲線拐點較多，說明改進的DE算法不斷跳出局部最優(yōu)值，逐漸趨向于全局最有值.

綜上所述，在DE算法參數(shù)縮放因子F不同的情況下，算法存在較大的性能差別，DE算法參數(shù)選取不當很可能無法獲得滿意的結(jié)果.而改進DE算法避免固定參數(shù)選擇的不足，具有局部搜索能力和全局搜索能力.

4 結(jié)論

針對差分進化算法在求解復(fù)雜優(yōu)化問題時存在的收斂性和開發(fā)能力較差以及控制參數(shù)難以確定的不足，引入小波基函數(shù)來控制DE算法參數(shù)F，提出了基于小波基函數(shù)的差分進化算法縮放因子改進方法，保證了解的多樣性、加速了收斂速度和提高了算法優(yōu)化性能.從實驗來看，無論對于單峰函數(shù)還是多峰函數(shù)，改進DE算法都有很好的適應(yīng)能力，表現(xiàn)出較強的尋優(yōu)能力和較好的收斂性能.