帶局部搜索的自適應(yīng)動(dòng)態(tài)差分進(jìn)化算法

，

(天津石油職業(yè)技術(shù)學(xué)院 資源勘查系，天津 301607)

差分演化算法[1、2]是于1995年由R.Storn和K.Price提出來的一種演化算法。該算法和其他進(jìn)化類算法主要的不同在于差分變異的使用。 DE 與人工生命,特別是進(jìn)化算法有著極特殊的聯(lián)系。DE 和微粒群算法一樣,都是基于群體智能理論的優(yōu)化算法,通過群體內(nèi)個(gè)體間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。但相比于其他進(jìn)化算法，DE 算法簡單、魯棒性高、易于程序?qū)崿F(xiàn)、全局收斂能力強(qiáng)。 但是其隨機(jī)性又導(dǎo)致其收斂速度慢，本文提出了利用單純形搜索的方法將群體中較差部分通過單純形搜索進(jìn)行優(yōu)化后再進(jìn)行差分進(jìn)化的方法，使得進(jìn)化速度有了較大的提高[3]。對于差分進(jìn)化算法來說，差分比例因子F,和交叉概率因子CR都在很大程度上影響了差分進(jìn)化算法的性能。因此本文提出了一種自適應(yīng)的差分進(jìn)化算法，使得進(jìn)化速度有了較大的提高，同時(shí)保留了DE全局搜索的優(yōu)越性。針對此，本文提出了一種自適應(yīng)參數(shù)的差分進(jìn)化算法。

一、 差分進(jìn)化算法和改進(jìn)的單純形搜索算法

(一) 基本差分進(jìn)化算法

差分進(jìn)化算法采用的選擇、交叉和變異這三種基本差分操作是算法的基礎(chǔ)。構(gòu)成差分進(jìn)化算法的要素主要有：個(gè)體適應(yīng)度評價(jià)，差分操作和參數(shù)設(shè)置。

1. 適應(yīng)度函數(shù)

在差分進(jìn)化算法中，差分操作主要通過適應(yīng)度函數(shù)(fitness function)的導(dǎo)向來實(shí)現(xiàn)的，它是用來評估個(gè)體相對于整個(gè)群體的優(yōu)劣的相對值的大小。通常根據(jù)具體問題定義適應(yīng)度函數(shù)。

2. 差分進(jìn)化算法的主要操作

在迭代過程中,每一代G的種群中都包含 N 個(gè)個(gè)體，這個(gè)種群可以用 N個(gè)D維的參向量來表示： XiG=(X1,……Xn)對于每個(gè)個(gè)體進(jìn)行如下操作：

變異操作：變異操作指算法按照這種策略從父代種群中生成新個(gè)體進(jìn)入中間代。通過式(1) 對每一個(gè)個(gè)體XiG實(shí)施變異操作,得到與其相對應(yīng)的變異個(gè)體VGi=(c1,c2，……cn)

VGi=Xr1+F·(Xr2-Xr3)

(1)

這里r1、r2 和r3是從區(qū)間[1 N]上隨機(jī)選取的互不相同的整數(shù)，且不同于下標(biāo)指數(shù)I,變異因子F是[0 2]上的一個(gè)實(shí)常數(shù)，其主要作用是控制差分向量的放大程度。

其中

選擇操作：如果新個(gè)體X′r優(yōu)于父代個(gè)體Xr，則用X′r來替換Xr，否則保持不變。在差分進(jìn)化算法中，選擇操作采取的是貪婪策略，即只有子代個(gè)體優(yōu)于父代個(gè)體時(shí)才被保留，否則，父代個(gè)體會(huì)被保留至下一代。

(二) 單純形改進(jìn)局部搜索算法

首先從群體中選擇適應(yīng)值較優(yōu)的N1個(gè)個(gè)體作為學(xué)習(xí)對象，計(jì)算質(zhì)心(式3)，較差的N2=N- N1個(gè)個(gè)體作為搜索對象，按照流程(圖1)對每個(gè)個(gè)體進(jìn)行搜索。

二、自適應(yīng)單純形差分進(jìn)化算法

(一) 改進(jìn)方法

由差分進(jìn)化算法變異算子(式1)和交叉因子(式2)的隨機(jī)性使得此算法具有全局搜索，魯棒性好的特點(diǎn)，但同時(shí)也導(dǎo)致了算法收斂速度慢。為了改善其收斂速度，本文提出了使用單純形快速搜索的方法，利用較好群體形成的單純形質(zhì)心對較差個(gè)體進(jìn)行初步優(yōu)化改進(jìn)后再用于差分進(jìn)化，加快算法的收斂。但本文方法與傳統(tǒng)的單純形搜索不同，在每次搜索，不是針對最差個(gè)體進(jìn)行的，而是對每個(gè)個(gè)體以最佳群體的質(zhì)心為質(zhì)心進(jìn)行優(yōu)化，這樣使每個(gè)個(gè)體質(zhì)心或最優(yōu)個(gè)體學(xué)習(xí)，比傳統(tǒng)只針對最差個(gè)體提高了搜索的范圍，改善了算法的收斂速度(見圖1)。

圖1 改進(jìn)的單純形搜索算法流程(圖中X為質(zhì)心; Xb為群體最優(yōu)個(gè)體)

當(dāng)群體最好適應(yīng)值和最差適應(yīng)值不等時(shí)使用文獻(xiàn)[3]介紹的方法使用個(gè)體信息動(dòng)態(tài)更新F(式4)，差分向量適應(yīng)能力較近時(shí)，F(xiàn)的絕對值較小，使得變異個(gè)體VGi相對基向量Xr1變化較小反之變異個(gè)體VGi相對基向量Xr1變化較大。概率選擇因子使用二項(xiàng)分布模型(式5)進(jìn)行動(dòng)態(tài)更新。

(二)算法的流程

綜上所述，此差分進(jìn)化算法的約束處理技術(shù)的流程可表示如下：

step1. 隨機(jī)生成群體規(guī)模都為N(N1+N2)的種群。

step2. 然后按照適應(yīng)值大小進(jìn)行從小到大排序，然后將最優(yōu)的前N1個(gè)優(yōu)秀個(gè)體和底部N2個(gè)較差個(gè)體分別組成群體X(N1個(gè))和Y(N2)。

step3. 生成X群體的質(zhì)心，對Y群體進(jìn)行單純形搜索，得到較優(yōu)的個(gè)體群Y。

step4. 合并X群體和Y群體為P。

step5. 獲得初始化群中最佳個(gè)體適應(yīng)值和最差個(gè)體適應(yīng)值及參數(shù)CR。

step6. 隨機(jī)從P個(gè)個(gè)體中選擇3個(gè)與生成的變異個(gè)體Vi序號i不同的個(gè)體，通過式2計(jì)算F值。

step7. 變異算法(式1)。

step8. 交叉算法。按照(2)式進(jìn)行交叉，生成新的實(shí)驗(yàn)個(gè)體Vi。

step9. 選擇操作。如果新個(gè)體Vi優(yōu)于父代個(gè)體Xi、則用Vi來替換Xi，否則保持不變。

step10. 判斷是否達(dá)到結(jié)束搜索條件，如果則輸出最佳個(gè)體Gbest，否則轉(zhuǎn)向step2

三、數(shù)值試驗(yàn)

本文選擇9個(gè)不同特點(diǎn)的基函數(shù)(表1)，維數(shù)都為30，在Matlab7環(huán)境下進(jìn)行了算法的實(shí)驗(yàn)與驗(yàn)證。

其中f1、f2為只有一個(gè)極小值單峰函數(shù)，f3-f8為具有無數(shù)個(gè)局部極小值的多峰函數(shù)。本文為驗(yàn)證SADCDE算法的優(yōu)越性，與標(biāo)準(zhǔn)差分進(jìn)化算法DE/rand/1及文獻(xiàn)[5]算法SADE及文獻(xiàn)[4]的算法FEP 、 CEP進(jìn)行了比較(表2)。為了比較的公平性，SADCDE算法參數(shù)設(shè)置與文獻(xiàn)[5]TABLE III中數(shù)據(jù)一樣。群體規(guī)模NP設(shè)為100 , 評估次數(shù)設(shè)為1500。SADCDE算法對表1中9個(gè)具有代表性的測試函數(shù)分別獨(dú)立運(yùn)行50次,求解結(jié)果的平均最優(yōu)值、最優(yōu)值方差分別和DE、SADE、LEP和BestLevy四種算法進(jìn)行了比較。表2中除了SADCDE算法外其它算法實(shí)驗(yàn)數(shù)據(jù)都來源于文獻(xiàn)[5]。

表1 維數(shù)D為30的函數(shù)f 1 - f9搜索區(qū)間及全局最優(yōu)值

從表2可看出，相對于其它函數(shù)SADCDE具有很明顯的優(yōu)勢：對于一個(gè)簡單的超球面函數(shù)f1(Sphere函數(shù)),SADCDE具有很明顯的優(yōu)勢，其次是SADE、DE算法，但都優(yōu)于LEP和BestLevy的算法，相同的評估次數(shù),得到了精度更高的解和更小的方差。對于Quadric函數(shù)f2，SADCDE算法具有明顯的優(yōu)勢，最小適應(yīng)值求解精度遠(yuǎn)好于其它四種算法，而且SADE好于DE算法，DE算法好于LEP和BestLevy算法。對于函數(shù)f3，SADCDE與SADE算法有相同的精度，都能夠求解出全局最大值，好于DE和LEP、BestLevy算法。函數(shù)f4和f5是被經(jīng)常用來測試進(jìn)化算法全局搜索能力的Rastrigin 函數(shù)和Griewank 函數(shù)，有許多局部最小點(diǎn),對于f4函數(shù)，只有SADCDE算法得到了全局最小值點(diǎn)，SADE算法精度較高但沒有求出全局最小值點(diǎn)。對于函數(shù)f5，SADCDE算法和SADE算法都搜索到了全局最小值點(diǎn)，其它算法沒有搜索到。f6為有噪音的函數(shù), 有多個(gè)局部最優(yōu)解[6,7],同樣SADCDE算法和SADE算法的搜索精度好于其它三種算法，SADCDE算法略好于SADE算法。具有罰項(xiàng)的測試函數(shù)f7 和f8，具有多個(gè)局部最優(yōu)解，五種算法中只有SADCDE算法求出了全局最優(yōu)解，而其它算法都沒有求出最優(yōu)解。

為了比較說明本文SADCDE算法的全局收斂性，本文使用SADCDE算法與文獻(xiàn)[5]中的SADE算法、DE算法進(jìn)行了進(jìn)化圖上得比較(如圖2),群體規(guī)模NP都設(shè)為100,最大迭代次數(shù)都為1500，SADCDE算法初始F值設(shè)為0.5，CR為0.1，對于DE算法,F為0.5，CR設(shè)為0.1。SADE算法(詳見文獻(xiàn)5)Fl為0.1，F(xiàn)u為0.9，τ1=τ2=0。

表2 SADCDE算法與DE、SADE、LEP、Bestlevy算法的比較

從圖2中分析：對于單峰函數(shù)f1和f2。SADC-DE無論在收斂速度還是全局搜索能力上都具有明顯的優(yōu)勢；對于函數(shù)f3、f4、f5、f7、f8，SADCDE算法都搜索到了最優(yōu)解，而其它算法都沒能找到最優(yōu)解，同時(shí)收斂速度上也比其它算法要快；對函數(shù)f6,SADCDE算法收斂速度快于其它算法，全局搜索精度與SADE算法接近。

f1

f2

f3

f4

f5

f6

f7

f8

四、結(jié)論

本文借助單純形搜索算法的基本思想給出了一種基于改進(jìn)單純形局部搜索的自適應(yīng)的差分進(jìn)化算法，利用改進(jìn)的單純形快速收斂的特點(diǎn)改善部分非優(yōu)良不可行個(gè)體，結(jié)合參數(shù)F和CR的自適應(yīng)機(jī)制，在保持群體多樣性的基礎(chǔ)上加快了差分進(jìn)化算法的收斂。結(jié)合優(yōu)秀的自適應(yīng)參數(shù)算子F和CR和單純形搜索算法，對差分進(jìn)化算法進(jìn)行了進(jìn)一步改進(jìn)，加快收斂和全局搜索性能。通過與已有研究比較得出此算法相比純單純形搜索算法、差分算法、自適應(yīng)算法都優(yōu)秀，說明了本文提供的基于單純形局部搜索自適應(yīng)算法該算法中集合了幾種算法的優(yōu)點(diǎn)，提高了算法的性能。但任何一種算法不可能在所有的性能方面占盡優(yōu)勢，SADCDE算法計(jì)算量要稍高。也就意味著由于增加了局部搜索的使得相同進(jìn)化代數(shù)下，運(yùn)算時(shí)間的延長。這也是此算法需要進(jìn)一步改進(jìn)的地方。

參考文獻(xiàn)：

[1]Storn R, Price K. Differential evolution —A simple and efficient adaptive scheme for global optimization over continuous spaces [J]. Journal of Global Optimization , 1997，vol. 11, no. 4: 341-359.

[2]Janez Brest. Large Scale Global Optimization using Self-adaptive Differential Evolution Algorithm,WCCI 2010 IEEE World Congress on Computational Intelligence

July, 18-23, 2010:3097-3104.

[3]張曉偉.劉三陽免比例因子F 的差分進(jìn)化算法[J].電子學(xué)報(bào),2009,36(06).

[4]X. Yao, Y. Liu, and G. Lin. Evolutionary programming made faster[J],IEEE Transactions on Evolutionary Com-putation, 1999,vol. 3, no. 2, p. 82:82-102.

[5]Janez Brest.Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems[J]，IEEE Transactions on Evolutionary Compu-tation, 2006,vol. 10, no. 6:646-657.

[6]C. Y. Lee and X. Yao.Evolutionary programming using mutations based on the Levy probability distribution， IEEE Transactions on Evolutionary Computation[J], 2004,vol. 8,no. 1:1-13.

[7]張雪霞，陳維榮，戴朝華.帶局部搜索的動(dòng)態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化[J], 電子學(xué)報(bào),2010,38(08).