基于自適應(yīng)小生境的改進(jìn)入侵性雜草優(yōu)化算法

賈盼龍， 田學(xué)民

（中國(guó)石油大學(xué)（華東）信息與控制工程學(xué)院，山東 青島266580）

入侵性雜草優(yōu)化算法（Invasive Weed Optimization，IWO）是由 Mehrabian等[1]在2006年提出了一種新穎的數(shù)值優(yōu)化模型。該算法模仿了雜草入侵的種子空間擴(kuò)散、生長(zhǎng)、繁殖和競(jìng)爭(zhēng)性消亡的基本過(guò)程，具有很強(qiáng)的魯棒性和自適應(yīng)性。與遺傳算法及其他群智能算法相比，IWO算法簡(jiǎn)單易于實(shí)現(xiàn)，不需要遺傳操作算子，能簡(jiǎn)單而有效地逼近于問(wèn)題的最優(yōu)解，是一種強(qiáng)有力的智能優(yōu)化工具，已被應(yīng)用到圖像聚類[2]、工程約束問(wèn)題[3]、控制器參數(shù)整定[4]、DNA 編碼[5]等眾多領(lǐng)域之中。

標(biāo)準(zhǔn)IWO算法種群繁殖和優(yōu)勝略汰的競(jìng)爭(zhēng)機(jī)制都是直接根據(jù)個(gè)體的適應(yīng)度來(lái)進(jìn)行的。適應(yīng)度小的個(gè)體產(chǎn)生少量種子或直接被淘汰，很可能會(huì)導(dǎo)致附近存在全局最優(yōu)解的個(gè)體被淘汰出局，使算法陷入局部最優(yōu)，影響到算法的尋優(yōu)效果。為此，Giri等[6]對(duì)空間擴(kuò)散矩陣做出了改進(jìn)；Zhang等[7]將交叉操作引入到IWO算法中；Hajimirsadeghi等[8]將IWO算法與粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）相結(jié)合，這些改進(jìn)方法都在一定程度上增加了IWO算法的種群多樣性，使得算法全局收斂性有所提高。

本文將小生境思想引入到IWO算法，提出一種改進(jìn)的小生境雜草優(yōu)化算法（Niche Invasive Weed Optimization，NIWO），對(duì)種群進(jìn)行分類競(jìng)爭(zhēng)繁殖，增加保持種群多樣性，提高算法的全局尋優(yōu)能力，同時(shí)采用自適應(yīng)小生境數(shù)來(lái)提高算法后期的收斂精度。通過(guò)對(duì)4個(gè)常用標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)，驗(yàn)證了該算法的有效性。

1 標(biāo)準(zhǔn)IWO算法

標(biāo)準(zhǔn)IWO算法[1-3]的執(zhí)行過(guò)程要經(jīng)歷4個(gè)過(guò)程：初始化種群，生長(zhǎng)繁殖，空間分布，競(jìng)爭(zhēng)性生存。

1.1 初始化種群

初始化量主要有雜草初始個(gè)數(shù)p和雜草最大個(gè)數(shù)Q、最大迭代次數(shù)it，max、問(wèn)題維數(shù)k、最大和最小可生成種子數(shù)Smax和Smin、非線性指數(shù)n、區(qū)間步長(zhǎng)初始值σinit和最終值σfinal以及初始搜索空間X，并生成隨機(jī)P個(gè)初始解。

1.2 生長(zhǎng)繁殖

雜草種群中的成員能夠產(chǎn)生的種子數(shù)是根據(jù)該成員的適應(yīng)值、最大和最小可生成種子數(shù)來(lái)決定的。

式中，C，D分別為種群最大適應(yīng)度和最小適應(yīng)度；x為植株的適應(yīng)度。圖1描述了種子數(shù)的確定過(guò)程。

圖1 種子數(shù)計(jì)算方法Fig.1 Seed number calculation

1.3 空間擴(kuò)散

IWO算法種群產(chǎn)生的種子被隨機(jī)播撒在d維空間中，產(chǎn)生種子的方式是通過(guò)將某個(gè)解加上某個(gè)數(shù)值，而該數(shù)值的變化區(qū)間步長(zhǎng)的大小由σ來(lái)決定，式中，it為迭代次數(shù)；it，max為最大迭代次數(shù)；Si為產(chǎn)生的種子在i維上的值；Wi為當(dāng)前植株在i維上的值。

1.4 競(jìng)爭(zhēng)性生存

每個(gè)植株按照適應(yīng)度大小進(jìn)行排序，較優(yōu)植株產(chǎn)生較多后代，如圖1所示。每次繁殖之后，重新按適應(yīng)度值進(jìn)行排序繁殖，當(dāng)族群數(shù)目達(dá)到最大時(shí)，族群數(shù)保持固定，適應(yīng)度差的植株將被剔除。

IWO是一種數(shù)值啟發(fā)性搜索算法，它在函數(shù)優(yōu)化時(shí)模仿了雜草克隆的自然行為。該算法的基本步驟如下：① 初始化群體（包括參數(shù)的設(shè)置和初始解（植株）的生成和評(píng)價(jià)）。② 生長(zhǎng)繁殖，即每個(gè)雜草種子生長(zhǎng)到開花。對(duì)于每個(gè)解，根據(jù)式（1）確定允許的后代個(gè)數(shù)。③ 空間擴(kuò)散，即根據(jù)式（2）將產(chǎn)生的種子隨機(jī)地散布在整個(gè)搜索區(qū)域，長(zhǎng)成新種雜草。④ 重復(fù)步驟②和③，直到雜草的最大數(shù)。⑤ 競(jìng)爭(zhēng)排除，即只有較好適應(yīng)性的前M個(gè)雜草個(gè)體能生存并產(chǎn)生種子，其他則消亡。⑥ 重復(fù)步驟②～⑥，直到最大代數(shù)或有更好適應(yīng)值的雜草個(gè)體最接近最優(yōu)解為止。

2 改進(jìn)IWO算法

在物種的進(jìn)化初期，處于不同孤立小生境中的物種之間是不進(jìn)行競(jìng)爭(zhēng)而獨(dú)立生長(zhǎng)繁殖的。但隨著物種的進(jìn)化，小生境內(nèi)個(gè)體數(shù)量增大，領(lǐng)域也隨之?dāng)U張，各孤立小生境開始相互融合，使得小生境數(shù)逐漸減少。受此自然現(xiàn)象的啟發(fā)，本文對(duì)標(biāo)準(zhǔn)IWO算法加以改進(jìn)，提出了一種NIWO算法。此方法針對(duì)標(biāo)準(zhǔn)IWO 算法[9-13]種群多樣性差、易收斂于局部最優(yōu)的不足，對(duì)種群個(gè)體進(jìn)行分類，盡可能地保留一些有用的孤立個(gè)體，加強(qiáng)了雜草進(jìn)化過(guò)程中的種群多樣性，提高了算法的全局優(yōu)化能力，同時(shí)，采用自適應(yīng)小生境數(shù)策略來(lái)提高算法的收斂精度。

2.1 小生境方法的具體實(shí)現(xiàn)

小生境方法的基本思想就是物以類聚，反映到IWO算法中就是對(duì)種群中所有個(gè)體進(jìn)行分類，使個(gè)體在一個(gè)特定的生存環(huán)境中繁殖競(jìng)爭(zhēng)。本文分類操作的具體實(shí)現(xiàn)如下：

（1）對(duì)于每一代的雜草個(gè)體按照其適應(yīng)度進(jìn)行排序，選定適應(yīng)度最高的個(gè)體B＝（b1，b2，…，bk），k∈N作為第1個(gè)小生境的中心，并標(biāo)記此個(gè)體；

（2）計(jì)算種群中每個(gè)個(gè)體距離第1個(gè)小生境中心B的歐式距離，當(dāng)歐氏距離小于事先設(shè)定好的閾值R（即為小生境半徑）時(shí)，此個(gè)體屬于此小生境，并標(biāo)記此個(gè)體；

（3）選擇未標(biāo)記個(gè)體中適應(yīng)度最大的個(gè)體作為下一個(gè)小生境的中心，計(jì)算種群中每個(gè)個(gè)體距離該小生境中心的歐式距離，當(dāng)歐氏距離小于事先設(shè)定好的閾值R時(shí)，該個(gè)體屬于該小生境，并標(biāo)記該個(gè)體；

（4）重復(fù)步驟（3），直到所有個(gè)體都被標(biāo)記，則分類結(jié)束。

本文采用如下策略對(duì)小生境半徑取值

式中，umax，umin與un分別為算法可調(diào)參數(shù)，用于調(diào)節(jié)迭代過(guò)程中分類的多少；dis為每個(gè)個(gè)體距離小生境中心的歐氏距離；~R為中間變量。

調(diào)節(jié)3個(gè)可變參數(shù)保證小生境半徑R隨著迭代次數(shù)的增大而增大，從而小生境數(shù)隨之減小，這樣就能夠提升迭代后期算法的收斂精度。

2.2 NIWO的算法流程

（1）初始化各參數(shù)，并隨機(jī)產(chǎn)生P個(gè)初始解；

（2）計(jì)算個(gè)體適應(yīng)度，并按適應(yīng)度進(jìn)行由優(yōu)到次的排序；

（3）根據(jù)上述小生境實(shí)現(xiàn)方法對(duì)種群分類；

（4）對(duì)于每類雜草個(gè)體分別采用圖1和式（1）進(jìn)行生長(zhǎng)繁殖和空間擴(kuò)散；

（5）判斷所有解的個(gè)數(shù)是否大于最大種群數(shù)Q，若是，轉(zhuǎn)至步驟（7）；若否，則繼續(xù)；

（6）依次在適應(yīng)度由優(yōu)到次的小生鏡內(nèi)篩選一個(gè)適應(yīng)度最優(yōu)的雜草個(gè)體作為勝出個(gè)體，當(dāng)?shù)竭_(dá)最大小生境數(shù)時(shí)，重新從第一個(gè)小生境篩選，直到所有勝出個(gè)體的數(shù)目等于種群最大個(gè)數(shù)Q；

（7）判斷是否達(dá)到最大迭代次數(shù)，若是，程序結(jié)束；若否，返回步驟（2）。

3 仿真實(shí)驗(yàn)

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

本文選取4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)[1]分別對(duì)標(biāo)準(zhǔn)IWO和NCIWO進(jìn)行了算法性能測(cè)試。

（1）Shubert函數(shù)

此函數(shù)有760個(gè)局部極小，在（-1.425 13，-0.800 32）處取到全局最小值約為0。

（2）Rosenbrock函數(shù)

此函數(shù)的全局最優(yōu)點(diǎn)是（1，1，…，1），最優(yōu)值為0。

（3）Griewank函數(shù)

此函數(shù)的全局最優(yōu)點(diǎn)是（0，0，…，0），最優(yōu)值為0。

表1 公共參數(shù)選值Tab.1 Public parameter value selection

（4）Rastrigin函數(shù)

此函數(shù)的全局最優(yōu)點(diǎn)是（0，0，…，0），最優(yōu)值為0。

上述4個(gè)測(cè)試函數(shù)均為多峰函數(shù)，要對(duì)其做出滿意的搜索結(jié)果必須具備較強(qiáng)的全局搜索能力和精確搜索能力。為了更加清楚地說(shuō)明算法改進(jìn)的有效性，利用f2，f3，f4進(jìn)行算法測(cè)試時(shí)，d分別取10，20。

3.2 參數(shù)設(shè)定

2種算法中的共同參數(shù)取值如表1所示；NIWO算法特有參數(shù)取值如表2所示。

3.3 仿真結(jié)果

對(duì)于每個(gè)測(cè)試函數(shù)，IWO和NIWO算法運(yùn)行100次后所得性能指標(biāo)如表3所示。圖2所示為2種算法對(duì)4個(gè)測(cè)試函數(shù)獨(dú)立優(yōu)化100次后所得平均對(duì)數(shù)收斂曲線。

由表3可見(jiàn)，對(duì)于4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，NIWO算法的平均最優(yōu)值均小于標(biāo)準(zhǔn)IWO算法，而且其方差也顯著減小，這說(shuō)明引入小生境后，IWO算法的全局收斂性有了明顯提高，求解結(jié)果更加穩(wěn)定，算法求解效果得到改善。

表2 NIWO算法參數(shù)取值Tab.2 Parameters of NIWO algorithm

表3 標(biāo)準(zhǔn)IWO算法和NIWO算法關(guān)于測(cè)試函數(shù)的比較Tab.3 Comparison of the standard IWO and NIWO algorithms for the test function

圖2 4種測(cè)試函數(shù)的收斂曲線Fig.2 Convergence curves of 4test functions

由圖2可見(jiàn)，在迭代前期，NIWO相對(duì)于IWO算法收斂速度沒(méi)有明顯的提高，但由于NIWO算法較IWO算法具有較好的種群多樣性，隨著迭代次數(shù)的增加，其求解結(jié)果能更加逼近問(wèn)題的最優(yōu)解，求解的精度和穩(wěn)定性都有所提高。

4 結(jié) 語(yǔ)

本文針對(duì)IWO算法易陷入局部最優(yōu)的不足，將小生境思想引入到IWO算法中，對(duì)雜草種群個(gè)體按照個(gè)體之間歐氏距離的大小進(jìn)行分類繁殖競(jìng)爭(zhēng)，加強(qiáng)了算法的種群的多樣性；同時(shí)，采用自適應(yīng)小生境數(shù)策略，隨著迭代次數(shù)的增加，小生境數(shù)逐漸減少，提升了算法后期的收斂精度，加強(qiáng)了算法的全局收斂性能，使得算法在對(duì)高維多峰函數(shù)進(jìn)行優(yōu)化時(shí)具有更高的精度和求解穩(wěn)定性，提高了算法的求解效果。

[1] Mehrabian A R，Lucas C.A novel numerical optimization algorithm inspired from weed colonization[J] .Ecological Informatics，2006，1（4）：355-366.

[2] 蘇守寶，方 杰，汪繼文，等.基于入侵性雜草克隆的圖像聚類方法[J] .華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，36（5）：95-100，105.

[3] Su Shoubao，Wang Jiwen，Zhang Ling，et al.An invasive weed optimization algorithm for constrained engineering design problems[J] .Journal of University of Science and Technology of China，2009，39（8）：885-893.

[4] Chen Zhihua，Wang Shuo，Deng Zhonghua，et al.Tuning of auto-disturbance rejection controller based on the invasive weed optimization[C] ∥2011 Sixth International Conference on Bio-Inspired Computing：Theories and Applications（BIC-TA）.Penang：IEEE，2011：314-318.

[5] Zhang Xuncai，Wang Yanfeng，Cui Guangzhao，et al.Application of a novel IWO to the design of encoding sequences for DNA computing[J] .Computers ＆ Mathematics with Applications，2009，57（11-12）：2001-2008.

[6] Giri R，Chowdhury A，Ghosh A，et al.A modified invasive weed optimization algorithm for training of feed-forward neural networks[J] .2010IEEE International Conference on Systems Man and Cybernetics（SMC）.Istanbul：IEEE，2010：3166-3173

[7] Zhang Xuncai，Niu Ying，Cui Guang Zhao，et al.A modified invasive weed optimization with crossover operation[C] ∥8th World Congress on Intelligent Control and Automation.Jinan：IEEE，China.2010：11-14.

[8] Hajimirsadeghi H，Lucas C.A hybrid IWO／PSO algorithm for fast and global optimization[C] ∥IEEE Congress on Evolutionary Computation.St-Petersburg：IEEE，2009：1964-1971.

[9] Ghosh A，Das W，Chowdhury A，et al.An ecologically inspired direct search method for solving optimal control problems with Bezier parameterization[J] .Engineering Applications of Artificial Intelligence，2011，24（7）：1195-1203.

[10] Petrowski A.A clearing procedure as a niching method for genetic algorithms[C] .Proceedings of International Conference on Evolutionary Computation.Nagoya，Japan：IEEE，1996：798-803.

[11] Lin C Y，Wu W H.Niche identification techniques in multimodal genetic search with sharing scheme[J] .Advances in Engineering Software，2002，33（11-12）：779-791.

[12] 王俊年，申群太，沈洪遠(yuǎn)，等.一種改進(jìn)的小生境微粒群算法[J] .山東大學(xué)學(xué)報(bào)：工學(xué)版，2005，35（3）：98-102.

[13] 陸 青，梁昌勇，楊善林，等.面向多模態(tài)函數(shù)優(yōu)化的自適應(yīng)小生境遺傳算法[J] .模式識(shí)別與人工智能，2009，22（1）：91-100.