基于云模型的入侵雜草優(yōu)化算法

劉 挺,王聯(lián)國(guó)

(甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院,蘭州730070)

1 概述

雜草具有生命力旺盛、繁殖力強(qiáng)、傳播途徑多樣等特性,長(zhǎng)久以來(lái)對(duì)農(nóng)作物的生長(zhǎng)構(gòu)成了嚴(yán)重的威脅。根據(jù)雜草的特點(diǎn),文獻(xiàn)[1]提出了一種入侵雜草優(yōu)化(Invasive Weed Optimization,IWO)算法。如今,IWO 已經(jīng)被成功應(yīng)用于DNA 編碼排序[2]、電力優(yōu)化調(diào)度[3]、無(wú)線(xiàn)電配置[4]以及圖像聚類(lèi)[5]等眾多領(lǐng)域。盡管如此,雜草算法也存在著求解精度低、易陷入局部值等缺點(diǎn)[6]。針對(duì)這些問(wèn)題,眾多學(xué)者采取了各種不同的策略致力于提高IWO 的性能[7-8]。

云模型的概念是由李德毅于1995 年提出的[9]。云模型把隨機(jī)性和模糊性結(jié)合起來(lái),用數(shù)字特征熵,揭示隨機(jī)性與模糊性的關(guān)聯(lián)性,實(shí)現(xiàn)了定性與定量之間轉(zhuǎn)換的過(guò)程。本文提出了一種云自適應(yīng)雜草優(yōu)化(Cloud Adaptive IWO,CLIWO)算法,根據(jù)雜草的適應(yīng)度值大小進(jìn)行分群操作,并根據(jù)云理論和每個(gè)群的實(shí)際情況自適應(yīng)選擇調(diào)整因子[10]。

2 基本雜草優(yōu)化算法

基本IWO 算法對(duì)雜草的生長(zhǎng)繁殖過(guò)程進(jìn)行了模擬,主要分為種群初始化、產(chǎn)生種子、空間擴(kuò)散以及競(jìng)爭(zhēng)排斥4 個(gè)過(guò)程,具體的操作步驟如下：

步驟1種群初始化

初始化種群起始位置,初始化種群數(shù)目Popsize、最大種群數(shù)Pmax,規(guī)定搜索空間大小、空間維數(shù)、最大最小種子生成數(shù),最大迭代次數(shù)、初始標(biāo)準(zhǔn)差、終止標(biāo)準(zhǔn)差以及非線(xiàn)性調(diào)和指數(shù)。

步驟2產(chǎn)生種子

生成種子的數(shù)目是根據(jù)父代雜草適應(yīng)度值大小比例而定的,每個(gè)雜草所產(chǎn)生的種子數(shù)目為：

其中,fi代表第i個(gè)雜草的適應(yīng)度值；SdNum為父代雜草生成種子的數(shù)目；fmax,fmin分別為種群當(dāng)前最大與最小的適應(yīng)度值；Sdmax,Sdmin分別為個(gè)體能生成的最大、最小種子數(shù)目。

步驟3空間擴(kuò)散

生成的種子以正態(tài)分布的形式擴(kuò)散在父代雜草個(gè)體周?chē)?具體實(shí)現(xiàn)按照式(2)所示。

其中,σnow為當(dāng)前的標(biāo)準(zhǔn)差；σini,σfin分別為初始、終止標(biāo)準(zhǔn)差；iter為當(dāng)前的迭代次數(shù)；mxiter為最大迭代次數(shù)；n一般取3 為非線(xiàn)性調(diào)和指數(shù)；Lson表示產(chǎn)生的種子位置；Lpar代表父代雜草位置；S為正態(tài)分布函數(shù)。

根據(jù)式(2)可以看出,算法初期,由于迭代次數(shù)較小,當(dāng)前標(biāo)準(zhǔn)差較大,S和σnow的乘積也相對(duì)較大,算法搜索的范圍也較大,因此算法這時(shí)處于全局搜索階段；隨著搜索的進(jìn)行以及迭代次數(shù)的不斷增加,當(dāng)前標(biāo)準(zhǔn)差會(huì)隨之減小,S與σnow的乘積也會(huì)隨之減小,搜索的范圍也在減小,這時(shí)搜索過(guò)程則變得更加精細(xì)。

步驟4競(jìng)爭(zhēng)排斥

算法經(jīng)過(guò)擴(kuò)散后種群數(shù)量會(huì)達(dá)到一個(gè)最大值Pmax,將種子和父代雜草個(gè)體一并按照適應(yīng)度值大小進(jìn)行排序,選取適應(yīng)度值較好的前Pmax個(gè)個(gè)體進(jìn)入下一次迭代。

3 云模型

定義設(shè)X是一個(gè)普通集合,X={x},稱(chēng)為論域,關(guān)于論域X中的模糊集合A,是指對(duì)于任意元素x都存在一個(gè)有穩(wěn)定傾向的隨機(jī)數(shù)uA(x),叫做x對(duì)A的隸屬。如果論域中的元素是簡(jiǎn)單有序的,則X可以看作是基礎(chǔ)變量,隸屬度在X上的分布叫做隸屬云；如果論域中的元素不是簡(jiǎn)單有序的,而根據(jù)某個(gè)法則f,可將X映射到另一個(gè)有序的論域X’上,X’中的一個(gè)且只有一個(gè)x’和x對(duì)應(yīng),則X’為基礎(chǔ)變量,隸屬度在X’上的分布叫做隸屬云。

若隸屬度在X上的分布滿(mǎn)足正態(tài)分布叫做正態(tài)云模型,正態(tài)云是一個(gè)具有穩(wěn)定傾向的隨機(jī)數(shù)組成的集合,用期望Ex,熵En,超熵He這3 個(gè)概念表示。

X條件云發(fā)生器[11]：X條件云發(fā)生器是根據(jù)期望Ex,熵En,超熵He這3 個(gè)特征值,在X上產(chǎn)生的滿(mǎn)足正態(tài)隸屬云分布規(guī)律的云滴σ(x0,u),這種發(fā)生器裝置叫做X條件云發(fā)生器。

輸入{Ex En He},n,x0

輸出{(x0,u1),(x0,u2),…,(x0,un)}

4 云自適應(yīng)雜草優(yōu)化算法

4.1 自適應(yīng)分群策略

設(shè)雜草種群大小為N,種群中每個(gè)雜草個(gè)體對(duì)應(yīng)的適應(yīng)度為fi,將種群中所有雜草個(gè)體求平均適應(yīng)度得種群最優(yōu)雜草個(gè)體的適應(yīng)度值為fmin；對(duì)于適應(yīng)度值優(yōu)于fmean的個(gè)體,將它們的適應(yīng)度求平均值得到f′mean；對(duì)于適應(yīng)度值次于fmean的個(gè)體,將它們的適應(yīng)度求平均值得到f″mean。本文算法將雜草的擴(kuò)散公式按式(3)調(diào)整。

其中,CR∈[0,1]為調(diào)整因子[12]。

在基本雜草算法中雜草每次擴(kuò)散的步長(zhǎng)是根據(jù)迭代次數(shù)增加而非線(xiàn)性減小的,這種擴(kuò)散方式在每代中σnow是一個(gè)不變的常數(shù),這樣如果σnow過(guò)大或者過(guò)小很有可能使搜索跳過(guò)或者未能到達(dá)最優(yōu)個(gè)體,這樣就導(dǎo)致了搜索能力的下降。針對(duì)這種情況,將雜草分為3 個(gè)子群,根據(jù)不同子群的情況采取不同的調(diào)整因子生成策略,具體分群策略如下：

(1) 優(yōu)良子群：fi優(yōu)于f′mean

該子群中的雜草個(gè)體屬于種群中的優(yōu)秀個(gè)體,其距離全局最優(yōu)個(gè)體比較近,因此,采用較小的調(diào)整因子CR,達(dá)到精細(xì)搜索的目的。CR的取值為0.2。

(2) 普通子群：fi優(yōu)于f″mean但差于f′mean

該種群中的個(gè)體為質(zhì)量一般的部分,也是相對(duì)其他2 個(gè)種群雜草個(gè)體數(shù)量最多的種群。該種群的調(diào)整因子使用X條件云發(fā)生器產(chǎn)生,對(duì)種群進(jìn)行動(dòng)態(tài)的調(diào)整,具體產(chǎn)生過(guò)程如下：

(3) 較差子群：fi次于f′mean”

該種群中的個(gè)體屬于質(zhì)量較差的個(gè)體,相對(duì)最優(yōu)個(gè)體距離較遠(yuǎn),因此,采用較大的調(diào)整因子,增加搜索的范圍,有助于更加迅速地找到最優(yōu)解。這里CR 的取值為0.9。

4.2 算法流程

CLIWO 算法流程如下：

步驟1在D維空間中初始化種群大小N,確定Popsize,Pmax,σini,σfin,Sdmax,Sdmin以及mxiter等相關(guān)參數(shù)。

步驟2判斷算法是否達(dá)到終止條件。若達(dá)到,輸出最優(yōu)解；否則,執(zhí)行步驟3。

步驟3計(jì)算種群中每個(gè)雜草個(gè)體的適應(yīng)度值,并計(jì)算fmean,fmin,f′mean,f′mean’。

步驟4依照自適應(yīng)分群策略將雜草分為3 個(gè)子群。

步驟5對(duì)于每個(gè)子群中的每個(gè)個(gè)體按照式(1)產(chǎn)生相應(yīng)的種子。

步驟6針對(duì)每個(gè)子群的情況,根據(jù)式(3)將子代雜草進(jìn)行擴(kuò)散操作。

步驟7將3 個(gè)子群的父、子代雜草放在一起,并且按照適應(yīng)度大小進(jìn)行排序,選擇適應(yīng)度較優(yōu)的前Pmax個(gè)雜草,然后轉(zhuǎn)步驟2。

時(shí)間復(fù)雜度分析：

(1) 需要對(duì)N個(gè)雜草進(jìn)行初始化,且每個(gè)個(gè)體是D維的,時(shí)間復(fù)雜度為O(N×D)。

(2) 判斷終止條件,時(shí)間復(fù)雜度為常數(shù)。

(3) 計(jì)算雜草適應(yīng)度,并計(jì)算fmean等相關(guān)值,l,s,p(l+s+p=N)分別表示3 個(gè)不同子群的雜草個(gè)數(shù)數(shù)目,Tl,Ts,Tp分別表示3 個(gè)子群迭代需要的時(shí)間,由于Tl,Tp的時(shí)間為O(1),Ts的時(shí)間為O(s×D),時(shí)間復(fù)雜度為2O(1) +O(s×D)。

(4) 根據(jù)適應(yīng)度分群,時(shí)間復(fù)雜度為O(N)。

(5) 種子產(chǎn)生,時(shí)間復(fù)雜度為O(N)。

(6) 種子擴(kuò)散,時(shí)間復(fù)雜度為O(N)。

(7) 進(jìn)行競(jìng)爭(zhēng)排序機(jī)制,若產(chǎn)生種子個(gè)數(shù)為Ns,則最小時(shí)間復(fù)雜度為(N+Ns)(lb(N+Ns))。

與基本IWO 算法相比,CLIWO 需要將所有雜草個(gè)體分群之后,再對(duì)群成員進(jìn)行繁殖、擴(kuò)散操作,s是N中的個(gè)體,分群調(diào)整因子生成策略的時(shí)間復(fù)雜度2O(1) +O(s×D)不會(huì)高于O(N×D),不足以提高基本IWO 算法的復(fù)雜度數(shù)量級(jí)。

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

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

為了檢驗(yàn)CLIWO 的尋優(yōu)性能,本文選取了7 個(gè)以最小值為基準(zhǔn)的測(cè)試函數(shù),并進(jìn)行了仿真實(shí)驗(yàn)。測(cè)試函數(shù)f1～f7均存在最小值,并且最小值為0。其中,f1～f4屬于單峰函數(shù),f5～f7屬于多峰函數(shù)。具體函數(shù)參見(jiàn)表1。

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

5.2 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)中具體參數(shù)設(shè)置為：種群規(guī)模為15 株雜草,雜草的最大生成數(shù)目為30 株,算法的最大迭代次數(shù)為200,非線(xiàn)性調(diào)和指數(shù)n為3；在此基礎(chǔ)上,為了確定算法中另外3 個(gè)重要參數(shù),對(duì)CLIWO 進(jìn)行了如下的實(shí)驗(yàn)：

(1) 在保持初始結(jié)束標(biāo)準(zhǔn)差以其他相關(guān)參數(shù)相同的情況下,固定種子的最小生成數(shù)目為0,使種子的最大生成數(shù)Sdmax取不同值并且經(jīng)過(guò)了多次實(shí)驗(yàn),結(jié)果選取最佳的Sdmax。

(2) 由于算法的初始標(biāo)準(zhǔn)差過(guò)大會(huì)導(dǎo)致搜索的實(shí)際步長(zhǎng)超過(guò)搜索空間的范圍,因此在(1)的基礎(chǔ)上,固定最終標(biāo)準(zhǔn)差為0.01 以及其他實(shí)驗(yàn)相關(guān)參數(shù),在可行域內(nèi)調(diào)整初始標(biāo)準(zhǔn)差σini并經(jīng)過(guò)多次實(shí)驗(yàn),選取最佳的σini。

(3) 在(1)、(2)的基礎(chǔ)上,嘗試分別在[0,1]選取多個(gè)不同數(shù)值作為CR的取值,經(jīng)過(guò)多次實(shí)驗(yàn),選取最佳的CR值。

受篇幅影響,只列出最終的實(shí)驗(yàn)結(jié)果,種子的最大生成數(shù)Sdmax取15,初始標(biāo)準(zhǔn)差σini設(shè)為WD/3(WD為搜索的上界),CR的臨界值取為0.2 與0.9,算法尋優(yōu)結(jié)果最佳。

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

用基本雜草優(yōu)化算法(IWO)、文獻(xiàn)[13]中的算法(CMIWO)與本文算法(CLIWO),分別對(duì)以上7 個(gè)測(cè)試函數(shù)進(jìn)行優(yōu)化,測(cè)試的結(jié)果取獨(dú)立運(yùn)行50 次后得到的平均值。實(shí)驗(yàn)結(jié)果如表2 所示。圖1描述了上述3 種算法對(duì)函數(shù)f1～f7經(jīng)歷200 次迭代的適應(yīng)度進(jìn)化曲線(xiàn)。

表2 7 個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果

圖1 函數(shù)f1～f7適應(yīng)度進(jìn)化曲線(xiàn)

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

表2 從最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差4 個(gè)方面對(duì)3 種算法進(jìn)行了比較。對(duì)于函數(shù)f1,f6,CLIWO得到的優(yōu)化結(jié)果較其他2 種算法優(yōu)勢(shì)較為明顯,平均值方面好于被比較的2 種算法2～4 個(gè)數(shù)量級(jí)。對(duì)于函數(shù)f2,f3,f4,CLIWO 得到的平均值與標(biāo)準(zhǔn)差分別優(yōu)于對(duì)比的2 種算法1～2 個(gè)數(shù)量級(jí)。對(duì)于函數(shù)f5,f7,CLIWO 與CMIWO 的平均值處于同一數(shù)量級(jí)上,這是由于雖然CLIWO 根據(jù)不同種群采取不同的CR,但是每個(gè)階段的調(diào)整因子仍然是具有隨機(jī)性的,有些函數(shù)得到的優(yōu)化程程度可能與CMIWO 相似。但是從數(shù)值上看CLIWO 的結(jié)果明顯優(yōu)于其他2 種算法,這說(shuō)明,CLIWO 算法的優(yōu)化精度較高,穩(wěn)定性更好。

圖1 分別描繪了函數(shù)f1～f7經(jīng)200 次迭代適應(yīng)度進(jìn)化曲線(xiàn)。可以看出,對(duì)于多峰函數(shù)f7,CLIWO優(yōu)化結(jié)果與CMIWO 較為接近,這也是因?yàn)镃R具有隨機(jī)性取值的原因,函數(shù)f1～f6都能更為快速地收斂于更好的解。這進(jìn)一步說(shuō)明了CLIWO 算法收斂速度比IWO 和CMIWO 要快且優(yōu)化精度較高。

6 結(jié)束語(yǔ)

本文將自適應(yīng)分群策略引入IWO 算法,把雜草種群分為優(yōu)良子群、普通子群和較差子群,對(duì)于優(yōu)良子群采取較小的調(diào)整因子,對(duì)于普通的子群采取基于云模型的調(diào)整因子生成策略,對(duì)于較差子群采取較大的調(diào)整因子,因地制宜地調(diào)整算法的擴(kuò)散步長(zhǎng)。仿真實(shí)驗(yàn)結(jié)果表明,本文算法在收斂速度和尋優(yōu)精度上都有了明顯的提高。

[1]Mehrabian A R,Lucas C.A Novel Numerical Optimization Algorithm Inspired from Weed Colonization[J].Ecological Informatics,2006,1(4)：355-366.

[2]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.

[3]Nayak M R,Krishnanand K R,Rout P K.Optimal Reactive Power Dispatch Based on Adaptive Invasive Weed Optimization Algorithm [C]//Proceedings of International Conference on Energy,Automation,and Signal.[S.l.]：IEEE Press,2011：1-7.

[4]Mallahzadeh A R,Oraizi H,Davoodi R Z.Application of the Invasive Weed Optimization Technique for Antenna Configurations [ C]//Proceedings of Conference on Antennas and Propagation.Piscataway,USA：IEEE Press,2008：425-428.

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

[6]Zhang Xuncai,Xu Jin,Gui Guangzhao,et al.Research on Invasive Weed Optimization Based on the Cultural Framework[C]//Proceedings of the 3rd International Conference on Bio-inspired Computing：Theories and Applications.Piscataway,USA：IEEE Press,2008：129-134.

[7]Hajimirsadeghi H,Lucas C.A Hybrid IWO/PSO Algorithm for Fast and Global Optimization [C]//Proceedings of IEEE EUROCON’09.Piscataway,USA：IEEE Press,2009：1964-1971.

[8]Zhang Xuncai,Niu Ying,Gui Guanzhao,et al.A Modified Invasive Weed Optimization with Crossover Operation [C]//Proceedings of the 8th World Congress on Intelligent Control and Automation.Piscataway,USA：IEEE Press,2010：11-14.

[9]李德毅,孟海軍,史雪梅.隸屬云和隸屬云發(fā)生器[J].計(jì)算機(jī)研究與發(fā)展,1995,32(6)：15-20.

[10]李德毅,劉常昱.論正態(tài)云模型的普適性[J].中國(guó)工程科學(xué),2004,6(8)：28-34.

[11]Zhu Yunfang,Dai Chaohua,Chen Weirong,et al.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm Based on Cloud Generators [J].Journal of Computational Information Systems,2005,1(4)：671-678.

[12]韋杏瓊,周永權(quán),黃華娟,等.云自適應(yīng)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,36(10)：233-235.

[13]陳 歡,周永權(quán),趙光偉.基于混沌序列的多種群入侵雜草算法[J].計(jì)算機(jī)應(yīng)用,2012,32(7)：1958-1961.