徐英杰,閻曉琳,鄧 武

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

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

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

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

1 差分進(jìn)化算法

1.1 差分進(jìn)化算法概述

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

1.2 初始化

DE算法采用NP個(gè)D維向量作為初始解設(shè)種群數(shù)量N，每個(gè)個(gè)體可表示為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)的隨機(jī)數(shù).

1.3 變異

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

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)隨機(jī)生成的不同整數(shù).縮放因子F是差分向量的一個(gè)控制參數(shù).xbest(G) 是群體在第G代中具有最佳適應(yīng)度值的個(gè)體向量.

1.4 交叉

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

(7)

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

1.5 選擇

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

(8)

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

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

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

(9)

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

改進(jìn)DE算法詳細(xì)步驟描述如下.

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

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

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

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

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

3 實(shí)例驗(yàn)證與分析

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

表3 實(shí)驗(yàn)結(jié)果對(duì)比分析

3.3 結(jié)果分析

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

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

4 結(jié)論

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