賈盼龍， 田學民

（中國石油大學（華東）信息與控制工程學院，山東 青島266580）

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

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

本文將小生境思想引入到IWO算法，提出一種改進的小生境雜草優(yōu)化算法（Niche Invasive Weed Optimization，NIWO），對種群進行分類競爭繁殖，增加保持種群多樣性，提高算法的全局尋優(yōu)能力，同時采用自適應小生境數來提高算法后期的收斂精度。通過對4個常用標準測試函數的仿真實驗，驗證了該算法的有效性。

1 標準IWO算法

標準IWO算法[1-3]的執(zhí)行過程要經歷4個過程：初始化種群，生長繁殖，空間分布，競爭性生存。

1.1 初始化種群

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

1.2 生長繁殖

雜草種群中的成員能夠產生的種子數是根據該成員的適應值、最大和最小可生成種子數來決定的。

式中，C，D分別為種群最大適應度和最小適應度；x為植株的適應度。圖1描述了種子數的確定過程。

圖1 種子數計算方法Fig.1 Seed number calculation

1.3 空間擴散

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

1.4 競爭性生存

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

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

2 改進IWO算法

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

2.1 小生境方法的具體實現

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

（1）對于每一代的雜草個體按照其適應度進行排序，選定適應度最高的個體B＝（b1，b2，…，bk），k∈N作為第1個小生境的中心，并標記此個體；

（2）計算種群中每個個體距離第1個小生境中心B的歐式距離，當歐氏距離小于事先設定好的閾值R（即為小生境半徑）時，此個體屬于此小生境，并標記此個體；

（3）選擇未標記個體中適應度最大的個體作為下一個小生境的中心，計算種群中每個個體距離該小生境中心的歐式距離，當歐氏距離小于事先設定好的閾值R時，該個體屬于該小生境，并標記該個體；

（4）重復步驟（3），直到所有個體都被標記，則分類結束。

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

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

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

2.2 NIWO的算法流程

（1）初始化各參數，并隨機產生P個初始解；

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

（3）根據上述小生境實現方法對種群分類；

（4）對于每類雜草個體分別采用圖1和式（1）進行生長繁殖和空間擴散；

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

（6）依次在適應度由優(yōu)到次的小生鏡內篩選一個適應度最優(yōu)的雜草個體作為勝出個體，當到達最大小生境數時，重新從第一個小生境篩選，直到所有勝出個體的數目等于種群最大個數Q；

（7）判斷是否達到最大迭代次數，若是，程序結束；若否，返回步驟（2）。

3 仿真實驗

3.1 測試函數

本文選取4個標準測試函數[1]分別對標準IWO和NCIWO進行了算法性能測試。

（1）Shubert函數

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

（2）Rosenbrock函數

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

（3）Griewank函數

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

表1 公共參數選值Tab.1 Public parameter value selection

（4）Rastrigin函數

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

上述4個測試函數均為多峰函數，要對其做出滿意的搜索結果必須具備較強的全局搜索能力和精確搜索能力。為了更加清楚地說明算法改進的有效性，利用f2，f3，f4進行算法測試時，d分別取10，20。

3.2 參數設定

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

3.3 仿真結果

對于每個測試函數，IWO和NIWO算法運行100次后所得性能指標如表3所示。圖2所示為2種算法對4個測試函數獨立優(yōu)化100次后所得平均對數收斂曲線。

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

表2 NIWO算法參數取值Tab.2 Parameters of NIWO algorithm

表3 標準IWO算法和NIWO算法關于測試函數的比較Tab.3 Comparison of the standard IWO and NIWO algorithms for the test function

圖2 4種測試函數的收斂曲線Fig.2 Convergence curves of 4test functions

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

4 結 語

本文針對IWO算法易陷入局部最優(yōu)的不足，將小生境思想引入到IWO算法中，對雜草種群個體按照個體之間歐氏距離的大小進行分類繁殖競爭，加強了算法的種群的多樣性；同時，采用自適應小生境數策略，隨著迭代次數的增加，小生境數逐漸減少，提升了算法后期的收斂精度，加強了算法的全局收斂性能，使得算法在對高維多峰函數進行優(yōu)化時具有更高的精度和求解穩(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] .華南理工大學學報：自然科學版，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] 王俊年，申群太，沈洪遠，等.一種改進的小生境微粒群算法[J] .山東大學學報：工學版，2005，35（3）：98-102.

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