基于蝙蝠算法的改进杂草算法研究

刘元苗，高晓智，2（.上海海事大学信息工程学院，上海20306；2.阿尔托大学自动化与系统技术系，芬兰赫尔辛基FI-00076）

基于蝙蝠算法的改进杂草算法研究

刘元苗1，高晓智1，2
（1.上海海事大学信息工程学院，上海201306；2.阿尔托大学自动化与系统技术系，芬兰赫尔辛基FI-00076）

提出了一种新型的混合算法并命名为混合杂草蝙蝠算法（Hybridize Invasive Weed Optimization with Bat Algorithm，IWOBA），该算法在杂草算法的基础上利用蝙蝠算法的回声定位来解决每代种子逐步寻优的问题。其原理是利用种群速度和位置的不断更新，增加种群的多样性，从而达到提高种群的全局收敛性。最后利用6个测试函数对该算法和标准杂草算法进行测试比较。仿真结果表明，IWOBA能够有效克服原算法早熟、易陷入局部最优的缺点，可加快算法收敛速度，具有良好的鲁棒性。

杂草算法；蝙蝠算法；回声定位

0 引言

入侵杂草算法（Invasive Weed Optimization，IWO）是由德黑兰大学的Mehrabian等在2006年提出来的，它是一种模拟自然界杂草入侵的新型的数值优化算法。该算法具有很强的鲁棒性和适应性，并且具有易于理解及实现等特点。近几年来，在很多学者的研究下，杂草算法已经成功应用到图像聚类、工程约束设计以及DNA编码等众多领域中[1-2]。

与其他智能算法相比较，标准杂草算法本身存在易于陷入局部最优解和收敛精度不高的不足，这些不足都影响着算法的寻优效果。因此，Hajimirsadeghi和Lucas提出了一种IWO和PSO融合的算法[3]，利用位置和速度的更新，使得算法避免了局部最优解；Zhang Xuncai等人在标准IWO算法中引入了交叉算子，避免算法早熟，提高了全局最优解[4]；张玉等人将遗传算法中的选择机制加入到标准IWO算法中，从而提高算法的多样性[5]。

而本文是将蝙蝠算法中的回声定位原理应用到杂草算法中。通过回声定位的特性，对种子个体的位置和速度进行不断地更新，使其避免出现早熟和陷入局部最优解的情况。且改进后的算法有更高的收敛精度。为了验证改进后算法的有效性，本文通过6个常用的标准测试函数进行仿真实验。

1 算法介绍

1.1 标准杂草优化算法

在杂草优化中，杂草通过繁殖产生种子，种子经过空间的扩散、生长和竞争排除，从而得到适应度较高的个体。其过程如下[6]：

（1）初始化种群和参数：在D维数下产生N个可行解。

（2）种群的生长繁殖：适应度高的杂草会产生更多的子代，适应度小的会慢慢消失。其计算公式：

式中，f是当前种群适应度；fmax和fmin分别是种群的最大和最小适应度；smax和smin分别表示种群的最大规模和最小规模。

（3）空间扩散：种群所产生的种子按平均值为0、标准差为δ的正态分布方式和步长Step∈[-δ，δ]分布在D维空间。在迭代初期标准差δ较大，随着δ逐渐减小，迭代步长也在逐渐减小。其公式如下：

（4）竞争排除：种群经过多次繁殖之后，其种群规模达到最大数量Pmax时，将种群中的个体根据适应度的大小进行排列，保留适应度前Pmax个个体。适应度差的个体将被淘汰。

1.2 蝙蝠算法

蝙蝠算法是受蝙蝠利用回声定位来扑捉猎物和蔽障的启发所提出的启元式算法[7]。其原理是蝙蝠通过调整频率的大小来不断更新其位置和速度从而达到扑捉猎物的目的。其速度和位置更新公式为：

式中，β∈[0，1]是一个随机变量，x*是当前最佳位置。在波长不变的情况下，fmin=0，fmax=100；开始每只蝙蝠的频率都是随机分配的。在进行局部搜索时，每只蝙蝠的最新解都是从现有的解集中选择的：

其中，ε∈[-1，1]是一个随机数，A是平均响度；随着迭代的进行，蝙蝠在捕捉时脉冲所发的速率和响度也在不断更新。更新公式为：

1.3 杂草算法与蝙蝠算法的融合算法BAIWO

利用回声定位的方法来更新杂草种群中个体的位置和速度[8]，具体实施步骤如下：

（1）初始化BAIWO的参数，并随机产生N0个个体的种群；

（2）计算种群个体的适应度函数值，确定当前最优值和最优解；

（3）种群个体进行繁殖、生长：

①对种群中每个种子利用式（3）～式（5）进行位置和速度更新；

②根据当前解集随机产生一个新解，并对该新解进行约束；

③通过条件（rand

（4）判断种群是否达到最大规模，若未达到，转到步骤（3），若达到，则继续执行；

（5）对种群个体的适应度值进行排序，保留前最大规模数的个体；

（6）判断是否达到最大迭代数，若否，转到步骤（3），若是，输出最优值和最优解。

从上述BAIWO算法的描述过程可知，BAIWO算法中的个体并不是在每次迭代过后直接进入下一代繁殖、生长，而是在种群中个体进行位置和速度更新后找出更优的个体进行下一代繁殖。这样，在迭代初期可以使得种群有着更强的全局搜索能力，到达迭代后期时，种群的寻优步长在不断变小，使得其具有更强的局部搜索能力。所以，BAIWO算法是将BA算法和IWO算法的各自优点融合起来，使得改进后的算法在初期拥有很好的全局搜索能力，到达后期对局部搜索更精确。从而克服了IWO算法前期陷入局部搜索，以及后期收敛精度不高和速度慢等缺陷[9-10]。

1.4 BAIWO算法时间复杂度分析

根据上述的BAIWO算法的流程步骤来对该算法进行时间复杂度分析，设n为种群个体的数目，d为目标函数的维数，T为最大迭代次数。时间复杂度如表1所示。

表1 BAIWO的时间复杂度

2 BAIWO算法仿真实验

2.1 实验的初始参数设置

该算法的最优参数设计：初始种群个体M0=30，最大种群个体Max=50，最大种子数为Smax=5，最小种子数为Smin=2，调和指数n=3，方差最大值和最小值分别为10和0.001，最大响度A=0.25，最大脉冲率R0=0.5，脉冲响度范围为[0，2]，脉冲衰减系数为0.9；6个不同的测试函数[11]f1～f6最大迭代次数分别为500，500，200，500，500，500。函数参数如表2所示。

表2 用于测试改进算法的函数参数

2.2 测试函数

在本实验中选取了6个标准测试函数分别对标准杂草算法和改进后杂草算法进行性能测试。

（1）Sphere函数

上述6个基准测试函数中，除了f1是单峰函数以外，其余的都是多峰函数。图1和图2分别是应用Rastrigin函数和Griewank函数对这两种算法在不同迭代次数下测试所得到的收敛曲线。

图1 Rastrigin函数优化测试

图2 Griewank函数优化测试

2.3 仿真结果分析

通过以上函数优化测试曲线可以看出，在迭代初期，BAIWO算法相较于标准IWO算法就具有较好的收敛效果，随着迭代次数的增加，到达迭代后期时，BAIWO算法也能得到更好的收敛值。说明改进后的算法提高了标准IWO算法的性能。

实验结果如表3所示，可以看出，无论在单峰还是多峰函数下，改进后算法结果都优于IWO算法，在求解函数f1（x）～f6（x）时，改进后的算法都能获得精确度较高的最优值，以及较好的平均值和方差。而IWO算法在求解这6个函数时，起始值较大，收敛速度很慢，很容易陷入局部最优解。总体而言，改进后的算法能够获得与理论值较近的值，以及很好的鲁棒性。

表3 六种基准函数的测试结果

3 结束语

本文针对杂草算法存在早熟现象和易陷入局部最优解等缺点，提出了利用蝙蝠算法中回声定位原理来对种群个体进行更新。从而使得种群前期拥有很好的全局收敛特性，后期可以使其避免陷入局部最优。从仿真结果看出，BAIWO算法在很大程度上提高了杂草算法的收敛性和寻优精度。然而，如何改变IWO算法中种群多样性来提高它的收敛性是今后要进一步研究的方向。

[1]张氢，陈丹丹，秦仙蓉，等.杂草算法收敛性分析及其在工程中的应用[J].同济大学学报（自然科学版），2010，38（11）：1689-1693.

[2]彭斌，胡常安，赵荣珍.基于混合杂草算法的神经网络优化策略[J].振动，测试与诊断，2013，33（4）：634-639.

[3]HAJIMIRSADEGHI H，LUCAS C.A hybrid IWO/PSO algorithm for fast and global optimization[J].IEEE EUROCON 2009.Piscataway：IEEE，2009：1964-1971.

[4]Zhang Xuncai，Niu Ying，Gui Gangzhao，et al.A modified invasive weed optimization with crossoever operation[C].The 8th world Congress on Intelligent Control and Automation，2010：11-14.

[5]张玉，蒋海荣，胡进，等.基于改进杂草优化算法的DFCW参数估计[J].现代雷达，2013，35（7）：20-23.

[6]贾盼龙，田学民.基于自适应小生境的改进入侵性杂草优化算法[J].上海电机学院学报，2012，15（4）：225-231.

[7]Yang Xinshe.Nature-inspired Metaheuristic Algorithms[M]. Beckington：Luniver Press，2010.

[8]李枝勇，马良，张惠珍.蝙蝠算法收敛性分析[J].数学的实践与认识，2013，43（12）：182-191.

[9]肖辉辉，段艳明.基于DE算法改进的蝙蝠算法的研究以及应用[J].计算机仿真，2014，31（1）：272-280.

[10]陈欢，周永权.入侵杂草算法的改进分析及研究[D].南宁：广西民族大学，2013.

[11]MEHRABIA A R，LUCAS C.A novel numerical optimization algorithm inspired from weed coloniz[J].Ecological Information，2006，1（4）：355-366.

Research of im proved invasive w eed optim ization algorithm base on bat algorithm

Liu Yuanmiao1，Gao Xiaozhi1，2
（1．Information Engineering Institute of Shanghai Maritime University，Shanghai 201306，China；2.Department of Automation and Systems Technology，Aalto University，Helsinki FI-00076，Finland）

A novel hybrid algorithm is proposed in this paper named hybridize invasive weed optimization with bat algorithm（IWOBA）.It is based on invasive weed optimization（IWO）and uses the echo-location of bat algorithm to solve optimization problem of each seeds steps of steps.The principle is the constantly update of the speed and position of population，and increase the diversity of the population，to enhance the global convergence of population.Finally six test functions were used to validate the algorithm and the standard of invasive weed algorithm（IWO）.The simulation results indicate that the IWOBA can effectively overcome the shortcoming of local optimum and the original in puberty，and accelerate the algorithm convergence speed and have good robustness.

invasive weed optimization algorithm；bat algorithm；echo-location

TP301

A

1674-7720（2015）03-0075-03

2014-10-03）

刘元苗（1987-），男，硕士研究生，主要研究方向：最优化理论应用及其研究。

高晓智（1972-），男，教授，阿尔托大学博士生导师，主要研究方向：软计算理论及其应用。