一種基于多種群協(xié)作進(jìn)化的自適應(yīng)差分進(jìn)化算法研究?

周 頔

（四川文理學(xué)院智能制造產(chǎn)業(yè)技術(shù)研究院 達(dá)州 635000）

1 引言

差分進(jìn)化（Differential Evolution，DE）是1995年提出的一種啟發(fā)式隨機(jī)搜索的智能優(yōu)化算法［1］。由于DE算法通過群體內(nèi)個(gè)體之間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索，其原理簡(jiǎn)單，可對(duì)在連續(xù)空間內(nèi)進(jìn)行隨機(jī)、并行、有效的全局搜索，具有較強(qiáng)的魯棒性、穩(wěn)健性以及強(qiáng)大的全局尋優(yōu)能力，所以該算法越來越受到學(xué)術(shù)界和工程界的廣泛關(guān)注，在約束優(yōu)化計(jì)算、信號(hào)處理、環(huán)境保護(hù)和運(yùn)籌學(xué)以及NP問題等多個(gè)領(lǐng)域得到廣泛的應(yīng)用。

然而由于DE算法是通個(gè)體之間的差分矢量進(jìn)行變異、交叉和選擇來實(shí)現(xiàn)尋優(yōu)，所以它存在著早熟收斂、易陷入局部最優(yōu)和尋優(yōu)效率不高等缺陷。近年來，許研究者針對(duì)這些存在的缺陷，提出了很多的改進(jìn) DE 算法［2～12］。Lee等［2］采用適應(yīng)性步長(zhǎng)局部搜索策略來確定DE 算法合適的縮放比例因子，目的是為了加速算法搜索。方強(qiáng)等［3］將單純形尋優(yōu)操作引入DE 算法，以提高算法的搜索精度。張雪霞等［4］基于二次規(guī)劃法，提出一種改進(jìn)的DE 算法。Brest 等［5］提出一種改進(jìn)的 DE 算法，以自適應(yīng)調(diào)節(jié)算法的參數(shù)縮放因子和交叉概率。吳亮紅等［6］提出一種基于雙種群結(jié)構(gòu)的偽并行DE 算法，以提高DE算法的收斂速率和全局搜索能力。Gong等［7］利用正交設(shè)計(jì)法來改進(jìn)DE 算法的收斂速度，提高其綜合尋優(yōu)性能。Ali等［8］將懲罰函數(shù)加入DE算法，用于較好地求解約束條件問題。賈東立等［9］將混沌變異和高斯變異用作局部搜索策略，基于混沌理論和高斯局部?jī)?yōu)化方法，提出一種新的混合DE算法。葛延峰等［10］通過改進(jìn)個(gè)體差異信息和適度值取值范圍，提出一種改進(jìn)自適應(yīng)DE 算法。曲福恒等［11］利用并行多個(gè)策略與參數(shù)組合來提高個(gè)體多樣性，提出了一種改進(jìn)的差分進(jìn)化算法。陳華等［12］提出一種可自動(dòng)調(diào)節(jié)縮放因子和交叉概率因子的自適應(yīng)DE算法。

這些改進(jìn)的DE 算法能夠較好地服了DE 算法的陷入局部最優(yōu)和早熟收斂性問題，但算法的局部搜索能力、收斂速度和尋優(yōu)精度還有待進(jìn)一步加強(qiáng)。本文為了充分利用局部搜索策略，協(xié)同進(jìn)化機(jī)制以及多種群進(jìn)化等優(yōu)點(diǎn)，提出一種改進(jìn)的多種群協(xié)作自適應(yīng)差分進(jìn)化（MSDPIDE）算法，通過函數(shù)優(yōu)化驗(yàn)證MSDPIDE算法的有效性。

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

DE 算法采用了遺傳算法的基本框架，同時(shí)借鑒了Nelder-Mead 單純形方法，設(shè)計(jì)了獨(dú)特的差分變異算子［5］。DE 算法包括變異操作、交叉操作和選擇操作［13～14］。

2.1 初始化

其中xjmin和xjmax分別表示種群中個(gè)體的下界和上界。rand 是［0，1］區(qū)間上的均勻隨機(jī)數(shù)發(fā)生器。

2.2 變異操作

變異操作是DE 算法與遺傳算法的不同之處。在DE算法中，主要是對(duì)父代的差分矢量進(jìn)行變異，不同的兩個(gè)個(gè)體（）構(gòu)成矢量對(duì)。不同的DE算法方法如下:

1）DE/rand/1/bin

2）DE/rand/2/bin

3）DE/best/1/bin

4）DE/rand/2/bin

5）DE/current-to-best/1

2.3 交叉操作

均勻交叉變異產(chǎn)生的個(gè)體xk和種群中的第i個(gè)個(gè)體，用來補(bǔ)償上一步的變異搜索，進(jìn)而產(chǎn)生試驗(yàn)向量xG。本文采用二項(xiàng)式交叉方法。具體交叉操作的方程為

其中，jrand?{1,2,…,D}是一個(gè)隨機(jī)整數(shù)，用來保證目標(biāo)個(gè)體至少有一個(gè)分量進(jìn)行了交叉操作。交叉概率CR ∈［0，1］。

2.4 選擇操作

DE算法選擇個(gè)體xG和適應(yīng)度更好的個(gè)體，作為子代個(gè)體。選擇的的標(biāo)準(zhǔn)如下:

3 多種群協(xié)作自適應(yīng)差分進(jìn)化（MSDPIDE）算法

3.1 局部搜索策略

為了提高DE 算法個(gè)體產(chǎn)生策略的多樣性，避免DE 算法早熟收斂問題，本文采用局部搜索策略來調(diào)整自適應(yīng)DE 算法搜索。假設(shè)當(dāng)前DE 算法種群規(guī)模為 NP ，最優(yōu)解為。隨機(jī)選擇個(gè)體x=(x1,x2,…,xD)，采用下列等式對(duì)最優(yōu)解xtgbest 進(jìn)行局部搜索，產(chǎn)生新的個(gè)體。

其中，j=1,2,3…,D ，U(-1,1)表示-1～1 之間均勻分布的隨機(jī)數(shù)。

3.2 多種群協(xié)作進(jìn)化

將種群個(gè)體分成N 個(gè)子群體，用于代替單一種群在可行解空間中進(jìn)行搜索，促進(jìn)個(gè)體間的交換信息。在算法迭代中，為了增加算法的搜索速度，降低算法的復(fù)雜度，首先基于不同策略，協(xié)同進(jìn)化各個(gè)子種群，然后按子種群中個(gè)體適應(yīng)度值排序，獲得每個(gè)子種群的最優(yōu)個(gè)體，更新每個(gè)子群體的最差個(gè)體，并評(píng)價(jià)適應(yīng)度值。接著重新合并N個(gè)子種群為一個(gè)種群，再隨機(jī)分為N 個(gè)子群體，再得每個(gè)子種群的最優(yōu)個(gè)體。并進(jìn)行最優(yōu)個(gè)體的比較，把優(yōu)秀個(gè)體保留下來，實(shí)現(xiàn)不同群體間動(dòng)態(tài)交換信息。這樣能促進(jìn)各個(gè)種群并行進(jìn)化，保持優(yōu)秀個(gè)體進(jìn)化的穩(wěn)定性，避免過早收斂現(xiàn)象。

3.3 MSDPIDE算法思想與描述

由于自適應(yīng)DE算法存在不能及時(shí)更新進(jìn)化策略，所以基于局部搜索策略，改進(jìn)自適應(yīng)DE 算法。針對(duì)求解問題，動(dòng)態(tài)產(chǎn)生獨(dú)立進(jìn)化的子種群，增強(qiáng)子種群個(gè)體間的信息交換，保持種群的多樣性；通過利用群體之間的對(duì)等的相互移民策略均衡全局探索能力和收斂速度之間的矛盾，使得算法在合理的計(jì)算復(fù)雜度下具有較高的全局收斂率。

MSDPIDE算法的具體步驟如下:

第一步:初始化算法各參數(shù):這些參數(shù)包括種群大小N 、迭代次數(shù)Tmax、交叉概率CR、縮放因子F 、自變量的下界和上界、初始衰減率α 以及初始增長(zhǎng)率 β 等。

第二步:隨機(jī)生成初始種群，t=1。

第三步:評(píng)價(jià)每個(gè)個(gè)體得適應(yīng)度值，找出最優(yōu)個(gè)體。

第四步:判斷最優(yōu)解是否滿足要求。若是輸出最優(yōu)解；否則，執(zhí)行第五步。

第五步:按照式（2）～（6），進(jìn)行變異操作。

第六步:按照式（7），進(jìn)行交叉操作。

第七步:按照式（8），對(duì)進(jìn)行選擇操作。

第八步:對(duì)最優(yōu)個(gè)體根據(jù)式（9），進(jìn)行局部搜索。

第九步:新的種群生成后，令t =t +1，轉(zhuǎn)第三步繼續(xù)進(jìn)行。

4 數(shù)值實(shí)驗(yàn)研究

4.1 測(cè)試函數(shù)

為了驗(yàn)證MSDPIDE 算法在高維復(fù)雜優(yōu)化函數(shù)中的性能，Benchmarks 函數(shù)被選作對(duì)算法進(jìn)行測(cè)試。本文選用的9 個(gè)經(jīng)典測(cè)試函數(shù)和變量范圍，如表1 所示，其全局最優(yōu)值均為0。同時(shí)MSDPIDE 算法與DE 算法和CADE算法［16］進(jìn)行比較。

表1 Benchmarks測(cè)試函數(shù)集

4.2 運(yùn)行環(huán)境與參數(shù)設(shè)置

實(shí)驗(yàn)開發(fā)環(huán)境如下:Matlab 2012a，運(yùn)行于I5 CPU 2.20GHz，4.0GB 內(nèi)存臺(tái)式電腦。實(shí)驗(yàn)參數(shù)設(shè)置如下:種群規(guī)模NP=100，函數(shù)維數(shù)為1000，群個(gè)數(shù)n=3，縮放因子 F =0.60，交叉概率CR=0.80，最大進(jìn)化代數(shù)為Tmax=500，每個(gè)算法獨(dú)立運(yùn)行20次。

4.3 實(shí)驗(yàn)結(jié)果與分析

DE 算法、CADE 算法和 MSDPIDE 算法運(yùn)行 20次的求解Benchmarks 測(cè)試函數(shù)，測(cè)試結(jié)果的最大最優(yōu)值、最小最優(yōu)值和平均最優(yōu)值，如表2所示。

表2 連續(xù)20次的運(yùn)行結(jié)果

從表2 中可以看出，根據(jù)MSDPIDE 算法和DE算法求解這9 個(gè)函數(shù)的結(jié)果，除DE 算法求解 f9函數(shù)獲得較好的結(jié)果外，MSDPIDE 求解 f1、f2、f3、f4、f5、f6、f7、f8函數(shù)均比DE 算法的求解效果好。MSDPIDE 算法與 ACDE 比較，ACDE 算法能夠較好地求解 f3和 f5函數(shù)，MSDPIDE 能夠較好地求解 f1、f2、f4、f6、f7、f8和 f9函數(shù)，且性能比ACDE算法好。綜上可知，本文提出的MSDPIDE算法在1000 維的高維復(fù)雜基準(zhǔn)函數(shù)測(cè)試中表現(xiàn)得更為穩(wěn)定，求解精度更高，能夠解決高維多極函數(shù)的復(fù)雜優(yōu)化問題。

5 結(jié)語

針對(duì)實(shí)際工程應(yīng)用中的高維復(fù)雜函數(shù)優(yōu)化問題，提出了利用局部搜索策略提高個(gè)體多樣性，成功地避免了算法的早熟收斂，提高了全局尋優(yōu)能力，保證個(gè)體之間能夠進(jìn)行充分高效的信息交換。利用自適應(yīng)調(diào)節(jié)機(jī)制，以平衡局部搜索與全局搜索。通過對(duì)9個(gè)典型benchmark函數(shù)進(jìn)行測(cè)試結(jié)果表明，該MSDPIDE 算法比DE 和CADE 算法總體性能優(yōu)。MSDPIDE 算法尋優(yōu)能力強(qiáng)，搜索精度高，穩(wěn)定性好，更適于處理高維函數(shù)優(yōu)化問題。