基于微分進(jìn)化的改進(jìn)雜草優(yōu)化算法

陶 玲，高曉智

(1.上海海事大學(xué) 信息工程學(xué)院，上海 201306;2.芬蘭阿爾托大學(xué)，赫爾辛基 00076)

入侵雜草優(yōu)化算法［1］即Invasive Weed Optimization，在 2006 年由伊朗的 A.R.Mehrabian和 C.Lucas在Ecological Informatics雜志上發(fā)表的一篇論文中首次提出。它是一種模擬自然界雜草繁殖過程的隨機(jī)搜索方法，包括雜草入侵的種子空間擴(kuò)散、生長、繁殖和競爭等過程，具有很強(qiáng)的魯棒性和自適應(yīng)性，且算法簡單，易于實(shí)現(xiàn)。到目前為止，該算法已成功應(yīng)用于基因調(diào)控網(wǎng)絡(luò)中的模糊神經(jīng)模型的知識提?。?］、文本特征選擇［3］、DNA計(jì)算編碼序列的設(shè)計(jì)［4］等眾多領(lǐng)域。

在標(biāo)準(zhǔn)的IWO算法中，隨著迭代次數(shù)的增加，雜草個(gè)體產(chǎn)生種子，種子個(gè)體以父代雜草為均值，正態(tài)分布于雜草周圍。正是由于這種擴(kuò)散機(jī)制，使得個(gè)體之間不存在信息交換，導(dǎo)致迭代后期種群多樣性差，局部搜索能力降低。同時(shí)，在標(biāo)準(zhǔn)IWO中存在以適應(yīng)度為基準(zhǔn)的繁殖機(jī)制。盡管這種機(jī)制給予了適應(yīng)度差的個(gè)體生存和繁殖的機(jī)會(huì)，但適應(yīng)度小的個(gè)體相應(yīng)產(chǎn)生的種子也少，最終很有可能被直接剔除。這樣隨著繁殖的繼續(xù)，就會(huì)丟失很多有用信息，使算法陷入局部最優(yōu)。為此，2008年Zhang等［5］提出一種基于文化框架的IWO算法(CIWO)，引入信念空間提高算法的局部尋優(yōu)能力，使算法的收斂速度加快;2009年，Hajimirsadeghi等［6］將IWO和 PSO兩種算法進(jìn)行融合，將PSO中粒子的速度和位移公式引入到雜草繁殖的種子個(gè)體中，使種子個(gè)體像PSO中的粒子一樣擁有速度，然后再對種子進(jìn)行正態(tài)分布擴(kuò)散，避免了算法陷入局部最優(yōu);2010年，Zhang等［7］又提出了一種改進(jìn)的 IWO算法(MIWO)，在雜草產(chǎn)生后代時(shí)引入交叉算子以改進(jìn)算法性能;2012年，Chen等［8］提出了一種基于混沌序列的多種群雜草算法，引入混沌序列和多種群機(jī)制來避免算法早熟，提高算法收斂速度和尋優(yōu)精度;2013年，Peng等［9］將遺傳算法中的交叉和變異操作加入到IWO算法中，改善了算法的全局優(yōu)化性能，獲得了較好的效果。

本文提出的IWODE算法在父代雜草個(gè)體繁殖種子后，引入一個(gè)隨機(jī)數(shù)對種子個(gè)體進(jìn)行改進(jìn)，以提高種子個(gè)體的質(zhì)量，然后對繁殖一代后的種群引入差分進(jìn)化算法中的變異、交叉和選擇思想，增加種群多樣性，提高算法性能。采用9個(gè)benchmark函數(shù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明:IWODE算法是有效的，其收斂精度和穩(wěn)定性均有較大提高。

1 IWO算法

IWO算法基本流程［10］包括以下5個(gè)步驟:

1)初始化種群。雜草個(gè)體隨機(jī)擴(kuò)散在D維搜索空間，初始種群大小可根據(jù)實(shí)際問題具體確定。

2)生長繁殖。雜草個(gè)體根據(jù)其適應(yīng)度產(chǎn)生種子，適應(yīng)度大的產(chǎn)生種子多，適應(yīng)度小的產(chǎn)生種子少。父代雜草個(gè)體產(chǎn)生種子數(shù)與其適應(yīng)度成線性關(guān)系，如圖1所示。

圖1 雜草產(chǎn)生種子的示意圖

3)空間擴(kuò)散。子代個(gè)體以正態(tài)分布的方式擴(kuò)散在D維空間中，以父代雜草為均值。每代擴(kuò)散步長的計(jì)算如下:

其中，iter為當(dāng)前迭代次數(shù)。

4)競爭排除。當(dāng)繁殖數(shù)代后，種群規(guī)模超過環(huán)境的承受能力，則需要按照適應(yīng)度進(jìn)行淘汰，以達(dá)到種群上限要求。

5)重復(fù)步驟2)～4)，若達(dá)到最大迭代次數(shù)或最大種群規(guī)模，則結(jié)束循環(huán)，輸出最優(yōu)解。

算法流程如圖2所示。

圖2 IWO算法流程

2 IWODE算法模型

IWODE算法流程如圖3所示。

圖3 IWODE算法流程

2.1 對種子個(gè)體的改進(jìn)

在解決連續(xù)性的工程問題時(shí)，種子個(gè)體采用正態(tài)分布的方式擴(kuò)散在父代雜草周圍，這是雜草優(yōu)化算法與其他優(yōu)化算法的最大區(qū)別。由于本文求解的都是標(biāo)準(zhǔn)測試函數(shù)的極小值，所以在產(chǎn)生子代個(gè)體時(shí)，引入一個(gè)0～1之間的隨機(jī)數(shù)可以提高子代個(gè)體的質(zhì)量，使得最終結(jié)果更加逼近最優(yōu)解。種子個(gè)體正態(tài)分布計(jì)算見式(2)和(3)。

其中:delta_iter為標(biāo)準(zhǔn)差;X(i，:)為父代雜草個(gè)體。

2.2 對繁殖后的父子代種群的改進(jìn)

在競爭排除前，對于繁殖了的種群，父代和子代個(gè)體一起，引入差分進(jìn)化(DE)算法［11］中的變異操作，見式(4);隨機(jī)選擇待變異的個(gè)體，產(chǎn)生中間種群，然后對當(dāng)代種群及其變異產(chǎn)生的中間種群進(jìn)行個(gè)體間的交叉操作，見式(5);以一定的交叉概率判斷是否將中間種群的個(gè)體保留到下一代，最后對交叉后的種群進(jìn)行選擇操作，見式(6);然后根據(jù)適應(yīng)度值的大小判定要選擇的進(jìn)入下一代的個(gè)體。

DE算法中的變異操作:

其中:i≠r1≠r2≠r3;G為壓縮因子;xi(g)表示第g代種群中第i個(gè)個(gè)體。

DE算法中的交叉操作:

其中，CR為交叉概率 jrand∈［1，2，…，dim］的隨機(jī)整數(shù)。

DE算法中的選擇操作:

其中，f為測試函數(shù)。

2.3 IWODE算法復(fù)雜度分析

IWODE算法描述如下:

步驟1 產(chǎn)生初始種群個(gè)體數(shù)為M0個(gè);

步驟2 根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度值，找到最大和最小適應(yīng)度值;

步驟3 當(dāng)iter=1，while iter＜=itmax;

步驟3.1 根據(jù)適應(yīng)度值計(jì)算每個(gè)父代個(gè)體產(chǎn)生的種子數(shù);

步驟3.2 根據(jù)式(1)計(jì)算每代種群正態(tài)分布的標(biāo)準(zhǔn)差;

步驟3.3 根據(jù)式(2)和(3)將種子個(gè)體正態(tài)分布于父代個(gè)體周圍;

步驟3.4 根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)種子個(gè)體的適應(yīng)度值;

步驟3.5 將新的種子個(gè)體加入到父代種群中構(gòu)成父子代種群;

步驟3.6 根據(jù)適應(yīng)度函數(shù)計(jì)算父子代種群每個(gè)個(gè)體的適應(yīng)度值;

步驟3.7 對于父子代種群中的每個(gè)個(gè)體:

當(dāng) it=1，while it＜ =100;

① 根據(jù)式(4)、(5)、(6)對個(gè)體引入DE中的3種操作;

② it=it+1，end while;

步驟3.8 對于新的種群:

if M＞Mmax;

①根據(jù)適應(yīng)度值將新的種群個(gè)體排序;

②排除多余的個(gè)體直到M=Mmax;

步驟 3.9 iter=iter+1，end while;

步驟4 輸出最優(yōu)解。

在IWODE算法中，最壞情況下的復(fù)雜度估計(jì)如下:

1)在步驟1中，時(shí)間復(fù)雜度，初始化M0個(gè)個(gè)體;

2)在步驟2中，計(jì)算每個(gè)個(gè)體的適應(yīng)度值;

3)在步驟3.1中，計(jì)算每個(gè)父代個(gè)體產(chǎn)生的種子數(shù);

4)在步驟3.2中，計(jì)算每代種群正態(tài)分布的標(biāo)準(zhǔn)差;

5)在步驟3.3中，種子個(gè)體正態(tài)分布于父代個(gè)體周圍;

6)在步驟3.4中，計(jì)算每個(gè)種子個(gè)體的適應(yīng)度值;

7)在步驟3.6中，計(jì)算父子代種群每個(gè)個(gè)體的適應(yīng)度值;

8)在步驟3.7中，引入DE操作，更新父子代種群。

以上是IWODE算法的復(fù)雜度估計(jì)，其他步驟中算法復(fù)雜度較低，可以忽略。

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

3.1 實(shí)驗(yàn)平臺(tái)

所有仿真實(shí)驗(yàn)均在Windows 7操作系統(tǒng)，CPU為酷睿 i3－2375，主頻為1.50 GHz，內(nèi)存為2 GB的計(jì)算機(jī)上完成，采用Matlab編程。

3.2 IWODE和IWO算法參數(shù)設(shè)置

兩種算法涉及到的所有參數(shù)設(shè)置見表1。分別對9個(gè)測試函數(shù)進(jìn)行仿真，所有測試函數(shù)均獨(dú)立運(yùn)行50次，每個(gè)函數(shù)每次迭代50代。

表1 算法參數(shù)設(shè)置

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

表2是本文采用的測試函數(shù)，其中:f1，f2，f3，f7，f8是單峰函數(shù)，f4，f5，f6，f9是多峰函數(shù)。

表3是IWODE與IWO獨(dú)立運(yùn)行50次的測試結(jié)果比較。圖4～12是9個(gè)函數(shù)分別迭代1 000代的收斂曲線。

表2 benchmark函數(shù)

圖4 函數(shù)f1的收斂曲線

圖5 函數(shù)f2的收斂曲線

圖6 函數(shù)f3的收斂曲線

圖7 函數(shù)f4的收斂曲線

圖8 函數(shù)f5的收斂曲線

圖9 函數(shù)f6的收斂曲線

圖10 函數(shù)f7的收斂曲線

圖11 函數(shù)f8的收斂曲線

圖12 函數(shù)f9的收斂曲線

3.2.2 結(jié)果分析

從表3可以看出:IWODE的各項(xiàng)測試結(jié)果幾乎均優(yōu)于 IWO。對于 f1，f2，f3，f5，f6，f7，f9，IWODE的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差均遠(yuǎn)優(yōu)于IWO。IWODE完全找到了相應(yīng)測試函數(shù)的全局最優(yōu)解，它的尋優(yōu)精度和穩(wěn)定性相比IWO要高很多。對于f4，IWODE的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差相比IWO分別高15，8，10，9個(gè)數(shù)量級。對于f8，雖然IWODE的最優(yōu)值次于IWO，但I(xiàn)WODE的最差值、平均值和標(biāo)準(zhǔn)差都比IWO好。以上結(jié)果表明:IWODE算法可行有效，且有較高的尋優(yōu)精度和穩(wěn)定性。

圖4～12是9個(gè)函數(shù)分別迭代1 000代的測試函數(shù)收斂曲線。圖4，5，6，10，11 分別是 f1，f2，f3，f7和 f8這 5 個(gè)單峰函數(shù)的收斂曲線，圖7，8，9，12分別是f4，f5，f6，f9這4個(gè)多峰函數(shù)的收斂曲線。從圖4～11可以看出:IWODE算法的收斂速度較IWO好，最后獲得的最優(yōu)解優(yōu)于IWO算法。而在圖12中，IWODE算法的收斂速度明顯快于IWO算法，且求得的最優(yōu)解也優(yōu)于IWO。以上結(jié)果表明:IWODE算法適合高維函數(shù)尋優(yōu)，無論函數(shù)是單峰的還是多峰的。

3.3 IWODE和GA、PSO的比較

為進(jìn)一步表明本文算法的有效性，將IWODE和GA、PSO進(jìn)行比較，選擇函數(shù)f4進(jìn)行測試。其中，函數(shù)獨(dú)立運(yùn)行次數(shù)為50，維數(shù)為30，IWODE其余參數(shù)設(shè)置與表1相同。表4為仿真結(jié)果，表中的成功率定義為:n/50(n表示50次運(yùn)行結(jié)果中最優(yōu)解＜0.005的次數(shù))。

表4 仿真結(jié)果

從表4可以看出:IWODE的尋優(yōu)精度優(yōu)于GA和PSO，IWODE的平均值分別優(yōu)于GA和PSO 13，12個(gè)數(shù)量級，并且IWODE算法相比GA和PSO在迭代次數(shù)較少的情況下獲得了更好的結(jié)果。

4 結(jié)束語

本文針對基本IWO算法的不足，對產(chǎn)生的種子個(gè)體進(jìn)行改進(jìn)，以提高種子個(gè)體質(zhì)量，從而提高算法的尋優(yōu)精度，同時(shí)在父子代種群中引入差分進(jìn)化算法中的各種思想，增加后期種群多樣性，改善了算法的全局尋優(yōu)能力和算法的穩(wěn)定性。本文還將IWODE與PSO和GA進(jìn)行比較。從仿真結(jié)果可以看出:IWODE算法取得了較好的結(jié)果。

［1］MEHRABIAN A R，LUCAS C A.novel numerical optimization algorithm inspired from weed colonization［J］.Ecological Informatics，2006，1(4):355－366.

［2］PRATYUSHA RAKSHIT，PAPIA DAS，AMIT KONAR，et al.A recurrent fuzzy neural model of a gene regulatory network for knowledge extraction using invasive weed and artificial bee colony optimization algorithm［C］//1st Int’1 Conf.on Recent Advances in Information Technology|RAIT－2012|.Piscataway:IEEE，2012.

［3］劉逵.基于野草算法的文本特征選擇研究［D］.重慶:西南大學(xué)，2013.

［4］ZHANG XUNCAI，WANG YANFENG，CUI GUANGZHAO，et al.Application of a novel IWO to the design of encoding sequences for DNA computing［J］.Computers and Mathematics with Applications，2009，57(11/12):2001－2008.

［5］ZHANG XUNCAI，XU JIN，CUI GUANGZHAO，et al.Research on invasive weed optimization based on the cultural framework［C］//BICTA 2008:Proceedings of the 3rd International Conference on Bio-Inspired Computing:Theories and Applications.Piscataway:IEEE，2008:129－134.

［6］HAJIMIRSADEGHI H，LUCAS.A hybrid IWO/PSO algorithm for fast and global optimization［C］//IEEE EUROCON 2009.Piscataway:IEEE，2009:1964－1971.

［7］ZHANG XUNCAI，NIU YING，CUI GUANGZHAO，et al.A modified invasive weed optimization with crossover operation［C］//Proceedings of the 8th World Congress on Intelligent Control and Automation.Piscataway:IEEE，2010:11－14.

［8］陳歡，周永權(quán)，趙光偉.基于混沌序列的多種群入侵雜草算法［J］.計(jì)算機(jī)應(yīng)用，2012，32(7):1958－1961.

［9］彭斌，胡常安，邵兵，等.求解TSP問題的混合雜草優(yōu)化算法［J］.振動(dòng)、測試與診斷，2013，33(z1):66－69.

［10］賈盼龍，田學(xué)民.基于自適應(yīng)小生境的改進(jìn)入侵性雜草優(yōu)化算法［J］.上海電機(jī)學(xué)院學(xué)報(bào)，2012，15(4):225－230.

［11］楊啟文，蔡亮，薛云燦.差分進(jìn)化算法綜述［J］.模式識別與人工智能，2008，21(4):506－513.