基于搜索策略的烟花算法研究

赵伟 郭乙江

摘  要： 为了克服烟花算法容易早熟，提高其寻优精度，提出一种基于搜索策略的烟花算法。首先，通过最小爆炸半径检测，得到种群适应度值。其次，在烟花种群多次迭代过程中对当前最佳烟花个体进行动态随机搜索，增强对当前阶段最佳个体邻域范围内的搜索。最后，根据当前最佳个体之间的拥挤程度，存留10%的最佳個体，对剩余烟花个体采用佳点集策略进行初始化操作，辅助种群个体逃离局部最优。实验结果表明，所提算法相比同类烟花算法有效提高了求解精度，且收敛速度较快。

关键词： 搜索策略; 烟花算法; 动态随机搜索; 佳点集策略; Benchmark函数; 个体逃离

中图分类号： TN911?34; TP18                    文献标识码： A                      文章编号： 1004?373X（2020）02?0074?03

Research on fireworks algorithm based on search strategy

ZHAO Wei， GUO Yijiang

Abstract： A fireworks algorithm based on search strategy is proposed to overcome the premature explosion of the fireworks algorithm and improve its optimization accuracy. The fitness value of the population is obtained by detecting the minimum explosion radius. In the course of the multiple iterations of the fireworks population， the dynamic random search for the current best fireworks individuals is carried out to enhance the search within the neighborhood scope of the optimal individuals at the current stage. The 10% best fireworks individuals are retained according to the current crowdedness degree among them， and the rest is initialized by means of the good?point set strategy to assist the individuals to escape from the local optimum. The experimental results show that in comparison with similar fireworks algorithms， the proposed algorithm can more effectively improve the solution accuracy， and has faster convergence speed.

Keywords： search strategy; fireworks algorithm; dynamic random search; good point set strategy; Benchmark function;individual escape

0  引  言

烟花算法作为一种求解众多优化问题的智能优化算法，近年来得到了快速发展，在图像识别、安防、交通驾驶、社会行为预测等众多领域得到广泛应用[1]。

通过引入历史成功信息构造学习因子，文献[2]提出动态搜索烟花算法。学习因子可使用搜索阶段种群各代最佳烟花个体，使个体具备向种群内部最佳搜索信息学习能力。该算法涉及的计算参数较少，求解速度较快。与传统的智能优化算法雷同，对高维函数的处理，在收敛速度以及优化方面存在明显不足。为了改善烟花算法的收敛能力，文献[3]提出具有反向学习能力与记忆功能反馈的烟花算法。利用反向学习机制，构造合理的种群规模，并保证烟花种群多样性。文献[4]针对烟花算法求解精度低的问题，提出具有灰色关联算子的烟花算法。该算法在粒子群算法寻优阶段，采用灰色关联算子为种群所有个体配备一个引导粒子，通过引导粒子对种群个体维度信息进行动态更新。该算法与原烟花算法相比，求解能力更佳。文献[5]针对标准烟花算法粒子之间信息交流缺陷，提出差分进化算法引导趋化算子的改进烟花算法。结合差分进化以及趋化算子的综合优势搜索种群迭代过程中的最佳个体，根据最佳个体信息对烟花算法粒子维度信息进行修正，加强粒子之间的信息交流。

本文提出基于搜索策略的烟花算法。在种群迭代过程中，采用动态随机搜索机制对种群内部当前阶段的最佳烟花个体进行动态随机搜索，增强最佳个体邻近区域的搜索。同时为了保证种群多样性，在后期引入佳点集技术，根据烟花种群当前阶段最佳个体聚集程度，对剩余个体在解空间内进行初始化操作。实验结果表明，该算法相比同类烟花算法有效提高了求解精度，且收敛速度较快。

1  烟花算法

1.1  最小爆炸半径检测

设定烟花群体规模为[N]，维数为[d]，种群中第[i]个烟花爆炸生成的火花个数为[si]，爆炸半径为[Ai]，公式如下：

[si=M·fmax-f（xi）+θi=1N（fmax-f（xi））+θ]   （1）

[Ai=A·f（xi）-fmin+θi=1N（f（xi）-fmin）+θ] （2）

式中：[M]表示可调爆炸生成的火花个数的参数;[A]表示可调爆炸半径范围的参数;[f（xi）]表示烟花个体[xi]的种群适应度值;[fmax=max（f（xi））]表示种群中最劣烟花相应的适应度值[6];[fmin=min（f（xi））]表示种群中最优烟花相应的适应度值;[θ]为常数。

1.2  烟花的爆炸方式

根据上述所得爆炸火花数量和爆炸半径，烟花个体[i]爆炸生成[Si]个火花，爆炸过程随机选取[k]个维度，对随机选择的维度[k∈{1，2，…，d}]，利用式（2）进行位置偏移构成新的爆炸火花[7]。

[Δxki=xki+rand（0，Ai）]             （3）

式中，[rand（0，Ai）]为爆炸范围[Ai]内的随机数。

设定烟花个体[i]，[t]时段的当前位置为[Xit=（xi1t，xi2t，…，xint）]，此时种群全局最优位置可描述为[X?t=（x?1t，x?2t，…，x?nt）]。设烟花个体[i]按照以下方式爆炸，则：

[Xt+1i=Xti+rand（0，Ai）]            （4）

式中，[Ai]为烟花个体[i]的爆炸影响范围，即爆炸产生的火花在此区间内随机发生位置变化[8?9]，但无法超出此区间。

2  基于搜索策略的烟花算法

种群迭代过程中所生成的最佳爆炸点，含有相比其他烟花个体更为优秀的进化信息，更能引导烟花算法的收敛方向。因此，加强种群最佳个体邻近区域的搜索，有助于快速搜索到最佳解[10]，提高种群求解精度。故在烟花算法中引入动态搜索机制，种群迭代后针对当代最佳个体进行动态随机搜索。

2.1  动态随机搜索策略

考虑到烟花算法当前最佳个体[Xg（t）]邻近范围内可能存在更为优异的烟花个体，故种群迭代后针对种群烟花个体[Xc：Xb=Xc+Xr]，进行一次动态随机搜索，观测是否存在更为优异的烟花个体。具体步骤如下：

1） 种群参数初始化。設定烟花算法的最大迭代次数为[Max]，满足[Xc=Xb];

2） 设定烟花算法的初始搜索步长[stepk];

3） 烟花算法的所有维度[m]，进行如下步骤。

① 在区间[[-stepk，stepk]]内生成随机向量[Xr];

② 构造新的烟花个体[Xn：Xn=Xc+Xr]，[X′n：X′n=Xc-Xr];

③ 将[Xn]分别与[Xc]和[Xb]进行优劣对比，假设[Xn]比[Xc]和[Xb]更佳，则替换掉[Xc]和[Xb];

④ 调整搜索步长[stepk];

⑤ 循环迭代步骤①～步骤④，[k]次，即完成对算法不同空间维度的搜索;

⑥ 算法迭代是否满足结束条件，假设满足则输出结果，烟花算法结束，相反则返回步骤②。

2.2  佳点集技术

设定[s]维空间内包含某种形式为[Pn（k）=（{r（n）1·k}，}，…，{r（n）s·k}）]的立方体[Vs]。假设偏差[φ（n）=C（r，ε）n-1+ε]存在，[ε]表示常数，[C（r，ε）]表示与[r]，[ε]相关的参数，[Pn（k）]表示最佳点集合。

烟花种群内每个烟花相应的适应度值应当与种群内部的平均适应度值相接近。为了提高种群多样性，在烟花算法中加入一个参数[α=-j=1mfi-faf2]来描述烟花算法局部最优解的获取是否受限，[fj]表示烟花个体当前阶段的适应度值，[fa]表示烟花种群当前阶段的平均适应度值，该值越小，说明烟花个体聚集程度越高。设定一阈值[λ]，当满足[α≤λ]时，说明烟花算法种群多样性降低，此时使用佳点集技术进行初始化操作。

3  测试结果与分析

为了验证本文提出的基于搜索策略的烟花算法的求解能力，在硬件环境为Matlab 7.9（R2009b），Intel[?]CoreTMDuo CPU 2.1 GHz，Windows 7 Flagship下与其他两种算法进行对比。

设定不同算法种群规模一致，为25，迭代次数均为500次，对比不同算法求解结果的均值及方差。表1给出文献[4]算法、文献[5]算法以及本文算法求解结果的均值及方差，测试所用Benchmark函数如下：

[f（x）=i=130x2i，  xi≤100]        （5）

[f（x）=i=111ai-x1（b2i+bix2）b2i+bix3+x42]    （6）

[f（x）=4x21-2.1x41+x613+x1x2-4x22+4x42]   （7）

[f（x）=-i=14ciexp-i=13aij（xi-pij）2] （8）

分析表1可知，本文算法对于所有Benchmark函数的求解精度明显高于文献[4]算法和文献[5]算法。当文献[4]算法、文献[5]算法取得最优解的同时本文算法也能够获取到最优解;在部分Benchmark函数无法获取最优解时，本文算法同样取得了最优解;当其他两种算法无法获取最优解时，本文算法所得结果更逼近于最优解。通过求解结果可知，本文算法方差更小，说明本文提出的基于搜索策略的烟花算法运行过程中更为稳定、可靠。表2给出这三种算法对于Benchmark函数最优解获取的成功次数以及获取最优解收敛代数对比结果。

分析表2可知，本文算法搜索到Benchmark函数最优解的成功次数明显高于文献[4]算法以及文献[5]算法。这说明本文通过引入动态随机搜索策略，能够使烟花算法跳出局部最优，有效提高了算法对Benchmark函数进行求解的精度。同时迭代次数相比其他两种算法更少，说明在算法后将佳点集技术的引入是非常有效的。选取两个Benchmark函数，对比函数f1，f5在仿真过程中最优值的变化曲线，如图1、图2所示。

从图1和图2给出变化曲线可看出，本文算法的收敛速度相比文献[4]算法和文献[5]算法更快一些。

4  结  语

本文提出基于搜索策略的烟花算法。该算法采用动态随机搜索机制加强对最佳爆炸点邻近区域的搜索，有效提高算法求解精度。为了避免基础烟花算法在后期陷入局部最优，采用佳点集技术重新设定部分爆炸点，以保证烟花算法的种群多样性。实验结果表明，该算法相比同类烟花算法有效提高了求解精度，值得推广。

参考文献

[1] 杜振鑫.采用多精英指导的烟花算法[J].兰州理工大学学报，2017，43（5）：100?104.

[2] 李席广，韩守飞，刘晓静，等.基于反向學习与动态记忆反馈的烟花算法[J].计算机工程，2017，43（12）：203?210.

[3] 包晓晓，叶春明，黄霞.烟花算法求解JSP问题的研究[J].计算机工程与应用，2017，53（3）：247?252.

[4] 汪菊琴，史荧中，彭力，等.带有灰色关联算子的烟花算法[J].计算机工程与应用，2018，54（20）：150?156.

[5] 刘茜，毛力，杨弘.差分进化引导趋化算子的烟花优化算法[J].计算机工程与应用，2019，55（3）：145?151.

[6] 谢承旺，许雷，汪慎文，等.一种增强型多目标烟花爆炸优化算法[J].电子学报，2017，45（10）：2323?2331.

[7] 薛俊杰，王瑛，孟祥飞，等.二进制反向学习烟花算法求解多维背包问题[J].系统工程与电子技术，2017，39（2）：451?458.

[8] 韩守飞，李席广，拱长青.基于模拟退火与高斯扰动的烟花优化算法[J].计算机科学，2017，44（5）：257?262.

[9] 王晓楠，巨永锋，高婷.紧急状态下候选通信网络信息实时生成仿真[J].计算机仿真，2017，34（12）：165?168.

[10] 谢承旺，许雷，汪慎文，等.一种增强型多目标烟花爆炸优化算法[J].电子学报，2017，45（10）：2323?2331.

作者简介：赵  伟（1985—），女，河北邢台人，硕士，讲师，研究方向为计算机应用、应用数学、课程与教学论。

郭乙江（1984—），男，陕西扶风人，硕士，讲师，研究方向为数据挖掘、自然算法、人工智能。