基于云模型的入侵杂草优化算法

刘 挺,王联国

(甘肃农业大学信息科学技术学院,兰州730070)

1 概述

杂草具有生命力旺盛、繁殖力强、传播途径多样等特性,长久以来对农作物的生长构成了严重的威胁。根据杂草的特点,文献[1]提出了一种入侵杂草优化(Invasive Weed Optimization,IWO)算法。如今,IWO 已经被成功应用于DNA 编码排序[2]、电力优化调度[3]、无线电配置[4]以及图像聚类[5]等众多领域。尽管如此,杂草算法也存在着求解精度低、易陷入局部值等缺点[6]。针对这些问题,众多学者采取了各种不同的策略致力于提高IWO 的性能[7-8]。

云模型的概念是由李德毅于1995 年提出的[9]。云模型把随机性和模糊性结合起来,用数字特征熵,揭示随机性与模糊性的关联性,实现了定性与定量之间转换的过程。本文提出了一种云自适应杂草优化(Cloud Adaptive IWO,CLIWO)算法,根据杂草的适应度值大小进行分群操作,并根据云理论和每个群的实际情况自适应选择调整因子[10]。

2 基本杂草优化算法

基本IWO 算法对杂草的生长繁殖过程进行了模拟,主要分为种群初始化、产生种子、空间扩散以及竞争排斥4 个过程,具体的操作步骤如下：

步骤1种群初始化

初始化种群起始位置,初始化种群数目Popsize、最大种群数Pmax,规定搜索空间大小、空间维数、最大最小种子生成数,最大迭代次数、初始标准差、终止标准差以及非线性调和指数。

步骤2产生种子

生成种子的数目是根据父代杂草适应度值大小比例而定的,每个杂草所产生的种子数目为：

其中,fi代表第i个杂草的适应度值；SdNum为父代杂草生成种子的数目；fmax,fmin分别为种群当前最大与最小的适应度值；Sdmax,Sdmin分别为个体能生成的最大、最小种子数目。

步骤3空间扩散

生成的种子以正态分布的形式扩散在父代杂草个体周围,具体实现按照式(2)所示。

其中,σnow为当前的标准差；σini,σfin分别为初始、终止标准差；iter为当前的迭代次数；mxiter为最大迭代次数；n一般取3 为非线性调和指数；Lson表示产生的种子位置；Lpar代表父代杂草位置；S为正态分布函数。

根据式(2)可以看出,算法初期,由于迭代次数较小,当前标准差较大,S和σnow的乘积也相对较大,算法搜索的范围也较大,因此算法这时处于全局搜索阶段；随着搜索的进行以及迭代次数的不断增加,当前标准差会随之减小,S与σnow的乘积也会随之减小,搜索的范围也在减小,这时搜索过程则变得更加精细。

步骤4竞争排斥

算法经过扩散后种群数量会达到一个最大值Pmax,将种子和父代杂草个体一并按照适应度值大小进行排序,选取适应度值较好的前Pmax个个体进入下一次迭代。

3 云模型

定义设X是一个普通集合,X={x},称为论域,关于论域X中的模糊集合A,是指对于任意元素x都存在一个有稳定倾向的随机数uA(x),叫做x对A的隶属。如果论域中的元素是简单有序的,则X可以看作是基础变量,隶属度在X上的分布叫做隶属云；如果论域中的元素不是简单有序的,而根据某个法则f,可将X映射到另一个有序的论域X’上,X’中的一个且只有一个x’和x对应,则X’为基础变量,隶属度在X’上的分布叫做隶属云。

若隶属度在X上的分布满足正态分布叫做正态云模型,正态云是一个具有稳定倾向的随机数组成的集合,用期望Ex,熵En,超熵He这3 个概念表示。

X条件云发生器[11]：X条件云发生器是根据期望Ex,熵En,超熵He这3 个特征值,在X上产生的满足正态隶属云分布规律的云滴σ(x0,u),这种发生器装置叫做X条件云发生器。

输入{Ex En He},n,x0

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

4 云自适应杂草优化算法

4.1 自适应分群策略

设杂草种群大小为N,种群中每个杂草个体对应的适应度为fi,将种群中所有杂草个体求平均适应度得种群最优杂草个体的适应度值为fmin；对于适应度值优于fmean的个体,将它们的适应度求平均值得到f′mean；对于适应度值次于fmean的个体,将它们的适应度求平均值得到f″mean。本文算法将杂草的扩散公式按式(3)调整。

其中,CR∈[0,1]为调整因子[12]。

在基本杂草算法中杂草每次扩散的步长是根据迭代次数增加而非线性减小的,这种扩散方式在每代中σnow是一个不变的常数,这样如果σnow过大或者过小很有可能使搜索跳过或者未能到达最优个体,这样就导致了搜索能力的下降。针对这种情况,将杂草分为3 个子群,根据不同子群的情况采取不同的调整因子生成策略,具体分群策略如下：

(1) 优良子群：fi优于f′mean

该子群中的杂草个体属于种群中的优秀个体,其距离全局最优个体比较近,因此,采用较小的调整因子CR,达到精细搜索的目的。CR的取值为0.2。

(2) 普通子群：fi优于f″mean但差于f′mean

该种群中的个体为质量一般的部分,也是相对其他2 个种群杂草个体数量最多的种群。该种群的调整因子使用X条件云发生器产生,对种群进行动态的调整,具体产生过程如下：

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

该种群中的个体属于质量较差的个体,相对最优个体距离较远,因此,采用较大的调整因子,增加搜索的范围,有助于更加迅速地找到最优解。这里CR 的取值为0.9。

4.2 算法流程

CLIWO 算法流程如下：

步骤1在D维空间中初始化种群大小N,确定Popsize,Pmax,σini,σfin,Sdmax,Sdmin以及mxiter等相关参数。

步骤2判断算法是否达到终止条件。若达到,输出最优解；否则,执行步骤3。

步骤3计算种群中每个杂草个体的适应度值,并计算fmean,fmin,f′mean,f′mean’。

步骤4依照自适应分群策略将杂草分为3 个子群。

步骤5对于每个子群中的每个个体按照式(1)产生相应的种子。

步骤6针对每个子群的情况,根据式(3)将子代杂草进行扩散操作。

步骤7将3 个子群的父、子代杂草放在一起,并且按照适应度大小进行排序,选择适应度较优的前Pmax个杂草,然后转步骤2。

时间复杂度分析：

(1) 需要对N个杂草进行初始化,且每个个体是D维的,时间复杂度为O(N×D)。

(2) 判断终止条件,时间复杂度为常数。

(3) 计算杂草适应度,并计算fmean等相关值,l,s,p(l+s+p=N)分别表示3 个不同子群的杂草个数数目,Tl,Ts,Tp分别表示3 个子群迭代需要的时间,由于Tl,Tp的时间为O(1),Ts的时间为O(s×D),时间复杂度为2O(1) +O(s×D)。

(4) 根据适应度分群,时间复杂度为O(N)。

(5) 种子产生,时间复杂度为O(N)。

(6) 种子扩散,时间复杂度为O(N)。

(7) 进行竞争排序机制,若产生种子个数为Ns,则最小时间复杂度为(N+Ns)(lb(N+Ns))。

与基本IWO 算法相比,CLIWO 需要将所有杂草个体分群之后,再对群成员进行繁殖、扩散操作,s是N中的个体,分群调整因子生成策略的时间复杂度2O(1) +O(s×D)不会高于O(N×D),不足以提高基本IWO 算法的复杂度数量级。

5 仿真实验与结果分析

5.1 测试函数

为了检验CLIWO 的寻优性能,本文选取了7 个以最小值为基准的测试函数,并进行了仿真实验。测试函数f1～f7均存在最小值,并且最小值为0。其中,f1～f4属于单峰函数,f5～f7属于多峰函数。具体函数参见表1。

表1 测试函数

5.2 实验参数设置

实验中具体参数设置为：种群规模为15 株杂草,杂草的最大生成数目为30 株,算法的最大迭代次数为200,非线性调和指数n为3；在此基础上,为了确定算法中另外3 个重要参数,对CLIWO 进行了如下的实验：

(1) 在保持初始结束标准差以其他相关参数相同的情况下,固定种子的最小生成数目为0,使种子的最大生成数Sdmax取不同值并且经过了多次实验,结果选取最佳的Sdmax。

(2) 由于算法的初始标准差过大会导致搜索的实际步长超过搜索空间的范围,因此在(1)的基础上,固定最终标准差为0.01 以及其他实验相关参数,在可行域内调整初始标准差σini并经过多次实验,选取最佳的σini。

(3) 在(1)、(2)的基础上,尝试分别在[0,1]选取多个不同数值作为CR的取值,经过多次实验,选取最佳的CR值。

受篇幅影响,只列出最终的实验结果,种子的最大生成数Sdmax取15,初始标准差σini设为WD/3(WD为搜索的上界),CR的临界值取为0.2 与0.9,算法寻优结果最佳。

5.3 实验结果

用基本杂草优化算法(IWO)、文献[13]中的算法(CMIWO)与本文算法(CLIWO),分别对以上7 个测试函数进行优化,测试的结果取独立运行50 次后得到的平均值。实验结果如表2 所示。图1描述了上述3 种算法对函数f1～f7经历200 次迭代的适应度进化曲线。

表2 7 个测试函数的实验结果

图1 函数f1～f7适应度进化曲线

5.4 实验结果分析

表2 从最优值、最差值、平均值和标准差4 个方面对3 种算法进行了比较。对于函数f1,f6,CLIWO得到的优化结果较其他2 种算法优势较为明显,平均值方面好于被比较的2 种算法2～4 个数量级。对于函数f2,f3,f4,CLIWO 得到的平均值与标准差分别优于对比的2 种算法1～2 个数量级。对于函数f5,f7,CLIWO 与CMIWO 的平均值处于同一数量级上,这是由于虽然CLIWO 根据不同种群采取不同的CR,但是每个阶段的调整因子仍然是具有随机性的,有些函数得到的优化程程度可能与CMIWO 相似。但是从数值上看CLIWO 的结果明显优于其他2 种算法,这说明,CLIWO 算法的优化精度较高,稳定性更好。

图1 分别描绘了函数f1～f7经200 次迭代适应度进化曲线。可以看出,对于多峰函数f7,CLIWO优化结果与CMIWO 较为接近,这也是因为CR具有随机性取值的原因,函数f1～f6都能更为快速地收敛于更好的解。这进一步说明了CLIWO 算法收敛速度比IWO 和CMIWO 要快且优化精度较高。

6 结束语

本文将自适应分群策略引入IWO 算法,把杂草种群分为优良子群、普通子群和较差子群,对于优良子群采取较小的调整因子,对于普通的子群采取基于云模型的调整因子生成策略,对于较差子群采取较大的调整因子,因地制宜地调整算法的扩散步长。仿真实验结果表明,本文算法在收敛速度和寻优精度上都有了明显的提高。

[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]苏守宝,方 杰,汪继文,等.基于入侵性杂草克隆的图像聚类方法[J].华南理工大学学报：自然科学版,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]李德毅,孟海军,史雪梅.隶属云和隶属云发生器[J].计算机研究与发展,1995,32(6)：15-20.

[10]李德毅,刘常昱.论正态云模型的普适性[J].中国工程科学,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]韦杏琼,周永权,黄华娟,等.云自适应粒子群算法[J].计算机工程与应用,2010,36(10)：233-235.

[13]陈 欢,周永权,赵光伟.基于混沌序列的多种群入侵杂草算法[J].计算机应用,2012,32(7)：1958-1961.