基于佳点集原理的多维竞争文化入侵杂草算法

邱　傲，项铁铭

(杭州电子科技大学天线与微波技术研究所，浙江 杭州 310018)



基于佳点集原理的多维竞争文化入侵杂草算法

邱傲，项铁铭

(杭州电子科技大学天线与微波技术研究所，浙江 杭州 310018)

摘要：针对入侵杂草算法收敛速度较慢，解决复杂高维问题时仍难跳出局部最优的不足，提出了基于佳点集原理的多维竞争文化入侵杂草算法.首先，采用佳点集原理均匀的初始化种群，从而提高初始解的质量；其次，采用多维竞争的机制，使算法更容易跳出局部最优；最后，将改进的入侵杂草算法嵌入到文化框架中，通过不断更新信念空间知识对种群进行全局指导，提高算法的收敛速度.通过5个经典测试函数的测试表明，算法不仅收敛速度快，而且跳出局部最优的能力也得到很大的提升.

关键词：佳点集；多维竞争；入侵杂草算法；文化框架

0引言

入侵杂草算法(Invasive Weed Optimization，IWO)由于其多样性丰富、鲁棒性好、代码易于实现，受到广泛关注和应用.目前，入侵杂草算法已应用到很多复杂问题中，如阵列天线方向图综合[1]、图像聚类、DNA序列设计[2]等.然而，该算法还有很多不足，如收敛速度慢、求解精度低等.为此，前人做出了很多的改进工作，总结起来有3种策略.一是跟其它智能算法混合，例如文献[3]采用文化框架，利用信仰空间群体指导种群空间进行进化，提高了算法的收敛速度；文献[4]将IWO和PSO混合，利用杂草算法的广度和PSO算法的深度，在子代扩散中以PSO算法中的位置、速度公式代替了杂草算法中的正态分布扩散，算法收敛速度和全局搜索能力有所提高.二是分群策略[5].三是改进IWO内在进化机制，例如文献[6]提出了离散二进制入侵杂草算法，并将改进的IWO用于解决离散问题.本文提出了基于佳点集构造的多维竞争文化入侵杂草算法(CMAIWO算法)，采用佳点集原理构造初始种群，使种群均匀分布在可行解空间，并且针对IWO淘汰机制过于僵化的严重缺陷，采用多维淘汰机制，使得种群竞争更为合理.通过大量实验证明，这种改进机制可行有效的.

1标准入侵杂草算法

入侵杂草算法是受杂草启发而提出的，它是模拟杂草入侵过程的算法.算法主要有种群初始化、繁衍后代、子代分布、竞争淘汰4个阶段，具体阶段如下：

1)种群空间初始化.采用随机的形式，若干的杂草种子扩散在D维的种群空间中.如果解决的问题维度比较大，一般选择的种群数目会多一点，要视具体情况而定，选择合适的种群数目.

3)子代分布.个体产生子代后，此时采用正态分布的形式，子代以父代为中心在D维空间中向周围扩散.在标准入侵杂草算法中，每一代扩散的标准差有其自己的规律，公式为

4)竞争淘汰.生存空间是有限制的，在繁殖一定的代数后，为了种群的可持续性，必须淘汰一些适应力较差的个体.通过设定种群最大存活数目Nmax来控制整个种群的数目，保证算法持续往下运行.算法的每一次迭代后，都会按照个体及其产生的子代的所有适应度值降序排列，然后将适应度值较大的前Nmax个个体选出来进行下一次迭代，剩下的个体则被环境淘汰.

以上就是标准入侵杂草算法的4个基本过程，环境决定了部分个体的淘汰，这样就导致了算法多样性相对较低，容易陷入局部最优.

2算法改进策略

2.1佳点集原理构造初始种群

为验证佳点集构造的优越性，本文选取随机抽样，拉丁超立方抽样与佳点集的构造进行比较.取种群个数为100，范围是[0，1]，图1中的(a)，(b)，(c)分别为不同初始条件下粒子在二维空间的分布图.

图1　不同抽样方法的粒子分布图

2.2多维竞争机制

标准入侵杂草算法在竞争淘汰阶段只是根据函数值大小选择最优个体来作为下一轮迭代的父代个体.这会造成多样性的降低，这显然是个严重的缺陷.本文针对这一缺陷提出新的改进方案，从每一代产生的子代中按照种群最大存活个数以一定的比例(本文选取10%)选出具有潜力的部分个体.设每一代具有潜力的个体数为Nalive，剩余存活的个体为Ns，种群最大存活个数为Nmax.本文的淘汰规则如下：

1)设每一父代产生的子代的潜力系数为Pi，表示为第i个父代个体所产生子代的适应度值与每个父代个体的适应度值之比，即Pi=fson/Fi，fson为保存第i个个体产生所有子代适应度值的矩阵，Fi为第i个个体的适应度值.由于本文算法是最小优化，Pi保存了每个子代的潜力系数，值越小说明该个体潜力越大；

2)潜力个体与剩余存活个体必须保证没有相同的个体，且满足Nalive+Ns=Nmax，然后潜力个体与剩余存活个体一起进入下一次迭代；

3)为保证每一代具有潜力的个体具有更大的活跃性，约定潜力个体并不受文化框架的指导，并且下一代的迭代中比其他个体多产生两个子代.

2.3嵌入文化框架

图2　文化算法框架

为提高算法的收敛速度，本文引入文化框架这个概念，将改进后的入侵杂草算法嵌入到文化框架.文化框架是模拟人类社会，将以往的经验知识世代传递作为历史经验以各种介质保存下来，然后人类从历史经验获取知识提高生产效率，避免危险等.往往人类进化的关键之源是以往经验积淀而形成的文化，也就是文化传承着历史信息.人们是通过学习文化来提高自己的知识储备，再运用学习到的知识从事社会活动；并且通过实践获取没有学习到的历史知识，形成新的文化，人类社会在获取知识和形成知识中不断进步和完善.假如不进行文化的传承，人类只会通过自身的实践来获取知识，往往浪费大量的时间、精力.这样就产生了一种新的框架，即文化算法[8]，用来模拟人类社会的历史经验积累传承.文化框架如图2所示，REYNOLDS将文化框架分为种群空间和信念空间，信念空间在宏观上表征种群进化过程中不断产生的文化知识，种群空间在微观上表征不断进化种群，并向信念空间获取知识指导种群进化.

2.4本文算法流程

以上给出了本文的对标准入侵杂草算法的改进策略，其算法流程如图3所示.图3中，T为当前迭代次数，AcceptStep本文取5，“T%AcceptStep”如果为0，将种群空间当前全局最好个体替换信仰空间中最差个体，否则继续进行种群空间的演化.信念空间和种群空间通过接受函数和影响函数这种通信协议来更新知识以及影响种群空间进化，多维竞争机制持续为进化选择更有质量的种子，佳点集的构造在源头控制种子的初始质量.通过实验分析，本文算法的时间复杂度不足以达到标准入侵杂草算法的数量级.

图3　本文算法流程

3算法分析与对比

3.1测试函数

本文采用5个有代表性的测试函数，分别从收敛速度、收敛精度等性能指标来验证本文算法的有效性.Sphere函数(f1)为单峰函数，一般用于测试算法的寻优精度；Griewwank函数(f2)有许多对称分布的全局最优；Rosenbrock函数(f3)函数为典型的病态非凸单模函数，极难找到全局最小值.Ackley函数(f4)有一个很小全局最优和周围许多较小的局部最优；Rastrigin函数(f5)为复杂多模函数，在搜索区域内有大量局部极小点(约有10 个全局极小值).所选5个测试函数的理论值均为0.

3.2实验结果分析

本文算法参数设置：初始化种群数取10，最大种群规模取30，初始化标准差取300，最终标准差取0.05，非线性因子取3；经过多次实验，结果显示最大种子个数和最小种子个数分别取15和0效果比较好.在相同参数设置的情况下，本文提出的CMAIWO算法分别与标准IWO和文献[9]的CMIWO算法进行对比.为减少随机性的影响，对每个测试函数独立运行50次，测试结果如表1所示.

表1　3种算法的收敛精度测试结果

表1的结果显示CMAIWO在解决高维复杂问题时有着明显的优势，对于函数f2，f3，f4，f5，CMAIWO在最优值和平均值方面，比CMIWO有1～4个数量级的提高，并且在标准差方面也有相当明显的优势.这是由于本文引入多维竞争机制，部分有潜力的个体被留下，这些个体一般会指向最优值的方向，往往能帮助种群跳出局部最优.

3种算法在迭代200次的情况下，各个测试函数的收敛轨迹如图4所示.各个测试函数的收敛轨迹表明，CMAIWO在很少的迭代次数内就可以达到很好的值.这是因为CMAIWO采用佳点集原理构造初始解，种群在空间内更容易找到最优解，并且采用文化框架，大大加快了收敛速度.经过多次的实验测试表明，每一代具有潜力个体个数的选取对算法的性能有很明显的影响，一般取种群个数的10%比较好.

图4　各个函数的收敛轨迹

4结束语

本文提出的基于佳点集构造的多维竞争文化入侵杂草算法从种群初始解优化，竞争机制优化，以及框架优化上做出了改进，对于解决高维复杂问题能力有了很大的提升，但没能从理论上做进一步分析，这是下一步要研究的方向.另外，在应用方面，以后本文算法的研究方向将转向解决多目标问题的研究.

参考文献

[1]刘燕,焦永昌,张亚明,等.基于分解的多目标入侵杂草算法用于阵列天线方向图综合[J].西北工业大学学报,2014,32(6):981-986.

[2]苏守宝,方杰,汪继文，等.基于入侵性杂草克隆的图像聚类方法[J].华南理工大学学报(自然科学版),2008,36(5):95-100.

[3]ZHANG X, XU J, CUI G, et al.Research on Invasive Weed Optimization Based on the Cultural Framework[J].Journal of Computational and Theoretical Nanoscience,2010,7(5)：820-825.

[4]HAJIMIRSADEHGI H, LUCAS C. A hybrid IWO/PSO algorithm for fast and global optimization[C]//EUROCON 2009, EUROCON'09. IEEE, 2009: 1964-1971.

[5]宋玉坚,叶春明,黄佐钘.多智能体入侵杂草算法[J].计算机应用研究, 2014, 31(10):2957-2961.

[6]张帅,王营冠,夏凌楠.离散二进制入侵杂草算法[J].华中科技大学学报, 2011, 39(10):55-60.

[7]陈义雄，梁昔明，黄亚飞. 基于佳点集构造的改进量子粒子群优化算法[J].中南大学学报(自然科学版), 2013, 44(4):1409-1414.

[8]LIU S, YOU X, WU Z. A Cultural Immune Quantum Evolutionary Algorithm and Its Application[J]. Journal of Computers, 2013, 8(1): 163-169.

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

DOI：10.13954/j.cnki.hdu.2016.03.018

收稿日期：2015-09-15

作者简介：邱傲(1990-)，男，湖北仙桃人，硕士研究生，智能优化算法及其应用.通信作者：项铁铭副教授，E-mail:tmxiang@126.com.

中图分类号：TP301.6

文献标识码：A

文章编号：1001-9146(2016)03-0089-05

Multi-dimensional Competitive Culture Invasive Weed Optimization Algorithm Based on Good-point Set

QIU Ao, XIANG Tieming

(InstituteofAntennaandMicrowaveTechnology,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：In the paper, the algorithm of multi-dimensional competitive based on the good-point set is proposed to solve the problem that the convergence rate of the invasive weed algorithm is slow and it is still difficult to solve the problem of local optimization. First, the algorithm uses the principle of the best point set, and then improves the initialization of the population to improve the quality of the initial solution; Second, for the invasion of weed algorithm is only based on the size of the fitness value of the problem, this paper uses the multi-dimensional competitive mechanism, making the algorithm more easy to jump out of local optimum; Third, the improved invasive weed algorithm is embedded into the cultural framework, and the global guidance of the population is improved by the continuous updating of the belief space knowledge. Through the test of the 5 test functions, the results show that the algorithm not only has a fast convergence speed, but also has a great improvement in the ability to jump out of the local optimum.

Key words：good-point set; multi-dimensional competition; invasive weed algorithm; cultural framework