智能优化算法--萤火虫算法研究综述

编辑:佚名 日期:2024-05-20 19:09 / 人气:

翻译自:A survey on firefly algorithms - ScienceDirect

萤火虫算法(FA)是群智能算法领域的流行算法之一。在过去几年中,文献有了显著的扩展。本文及时回顾了FA及其新变体。对FA的不同变体进行分类和分析。这里还详细回顾和总结了快速发展的领域的应用和案例研究。本文最后将给出萤火虫算法需要进一步解决的问题和未来的研究方向。

萤火虫算法的灵感来自于萤火虫如何通过闪烁的光线相互发出信号来吸引伴侣或警告潜在的捕食者。显然,闪烁的光和它的强度可以遵守一些规则,包括物理规律。为了构建萤火虫算法的搜索模型,Xin-She Yang提出了三个理想化的规则:

(1)萤火虫不分性别,即萤火虫之间的相互吸引只考虑个体发光的亮度;

(2)吸引力与发光亮度成正比,与个体之间的距离成反比;

(3)萤火虫的亮度由待优化的目标函数值决定。

萤火虫算法是一种基于种群的随机搜索算法。每只萤火虫随机的分布在目标函数的搜索空间内。每个萤火虫的亮度与它所在位置的目标函数对应的适应度值有关。越亮的萤火虫表示它所处的位置对应的目标函数值更优。每只萤火虫均受到其它更亮的萤火虫的吸引而产生移动,以获得更好的解。随着种群的不断进化,最终获得优化问题的有效解。

对于一个D 维的搜索空间,设种群中萤火虫总个数为NP,则第 i 只 (i=1,2, ···,NP ) 萤火虫的位置表示为X_{i} =( x_{i1} , x_{i2} ,..., x_{iD} )。

萤火虫算法认为光的强度和萤火虫之间的吸引力是两个重要的变量。每只萤火虫都会被另一只比它自己更亮的萤火虫所吸引。换句话说,任何一种萤火虫的吸引力都与它的闪光强度成正比,与测量光强度的距离成反比。因此,萤火虫 i 和萤火虫 j 之间的吸引力 \\beta_{ij} 计算如下:

\\beta_{ij}=\\beta_{0}\	imes e^{-\\gamma\	imes r_{ij}^{2}}

其中 \\gamma 是光吸收系数, \\beta_{0} 是当距离为零时的吸引力,吸引力可以定义为另一种萤火虫观察到的光强度。 r_{ij} 是萤火虫个体 i j 之间的欧氏距离,由下式确定。

r_{ij}=\\sqrt{\\sum_{d=1}^{D}{(x_{id}-x_{jd})^{2}}}

对于萤火虫 x_{i}x_{j} ,如果 x_{j}x_{i} 亮, x_{i} 将向 x_{j} 移动。位置更新公式如下:

x_{i}^{t+1}=x_{i}^{t}+\\beta\	imes (x_{j}^{t}-x_{i}^{t})+\\alpha\\varepsilon

其中第二项是吸引力。第三项是随机化,α 为步长因子,ε 为高斯随机数。t 是当前的迭代次数。

对于最亮的萤火虫, x_{b} ,因为没有其他更亮的萤火虫,来遵循上面等式中的第二个表达式,该项将被省略,如在下面等式中所示。

x_{b}^{t+1}=x_{b}^{t}+\\alpha\\varepsilon

萤火虫算法的主要步骤可以概括为下面的伪代码。

萤火虫算法伪代码

就复杂度而言,基本上所有的元启发式算法都是较为简单的,并且容易付诸实施。从算法伪代码可以看出,当种群规模为NP,萤火虫算法有两个内部循环,一个外部循环用于G 次迭代。这也就是说,萤火虫算法复杂度的极限值也就是O( NP^{2}G )。一般情况下,种群的个数NP 是比较小的,通常取值为40,最大迭代次数通常取值为5000。所以计算成本相对低廉。因此,算法复杂度基本上可视作是关于最大迭代次数呈线性变化的。事实上,萤火虫优化算法主要代价是花费在对目标函数的评估上,因为算法事先对所要求解的目标函数是一无所知的,目标函数的复杂度关系到萤火虫优化算法的复杂度。这也是所有的元启发算法耗费时间的主要原因,因为对于所要求解的优化问题,毕竟评估目标函数是需要花费运算代价的。

另外,如果种群规模比较大,就可以使用一个内循环,通过排序算法对所有萤火虫的吸引力或亮度进行排序。此时FA的算法复杂度为O (NP log(NP ) G )。

这里要指出的是,种群规模对萤火虫算法的寻优精度和迭代速度有重要影响。对于相同的待优化问题,在迭代次数相同的条件下,规模较小的种群,算法的迭代速度较高,但是最终的寻优精度相对较低;对于规模较大的种群规模,算法的迭代速度随之降低,但是最终的寻优精度会明显提高。通过目前的实验研究可以得出,对于一般的待优化问题,种群规模设定为 40 到 50 就可以满足优化目的,对于多峰问题,增加种群规模,可有效提高优化精度。

在萤火虫算法中,并不需要一个好的初始解启动优化过程,也就是说,无论初始解是什么,它都会得到相同的最优解。

萤火虫算法具有通过控制其缩放参数来控制其模态和适应问题规模的能力。根据参数设置,FA可以区分两种渐近行为。前者在 \\gamma\\rightarrow0 时出现,后者在 \\gamma\\rightarrow\\infty 时出现。如果 \\gamma\\rightarrow0 , 则 \\beta=\\beta_{0} ,也就是说,在搜索空间内的任何地方,吸引力都是恒定的,这种行为是粒子群优化算法的特例。如果 \\gamma\\rightarrow\\infty ,则位置更新公式中,第二项从方程中消失,萤火虫运动变成了随机行走,本质上是模拟退火的并行版本。事实上,FA的每个实现都可以介于这两个渐近行为之间。也就是说,FA可以看作是一个非线性系统中增强的粒子群优化算法和模拟退火的良好组合。

与其它群智能算法相比,萤火虫优化算法具有其他算法所不具备的两点优势,分别是子种群的主动划分与对多极值待优化函数的处理。对于子种群的主动划分能力,由于在算法中吸引力与距离成反比例关系,该特点会促使萤火虫群体在算法的迭代寻优过程中自动地划分为若干个子群,并且分布在待优化函数在搜索空间中的各个局部极值区域周围。待优化函数的全局最优值可以根据这种主动分组的形式而得到。同时,在种群规模比待优化函数的峰值多的条件下,种群的主动分组特性可以促使种群的全部个体一起搜索全局最优值。考虑到萤火虫算法的寻优特点,萤火虫能够向着相对于自身位置最近而且最亮的个体运用,所以这个寻优特性能够使一个子群中相互之间可见的个体之间保持着相对平均的距离,推广到种群中,即全体个体都能够根据所得出的平均距离划分成子群。最特殊的一种状况是在 \\gamma=0 的条件下,种群中的个体之间相互不可见,此时无法划分成子群。对于待优化问题是多峰的或者是非线性的情况,自主分组的特点可以帮助萤火虫算法有效地处理这些特殊问题。在迭代寻优过程中,萤火虫优化算法的部分参数可以根据寻优情况进行动态变化,这类变化能够促使算法的收敛速度随之提升。该优势可以让萤火虫优化算法可以便捷高效地应对一些特殊问题,比如数据挖掘中的聚类和分类问题、连续优化和组合优化问题等。

此外,在粒子群优化算法和蝙蝠算法中,个体从一个或两个对象中学习,这使得算法很容易陷入过早收敛的状态。在FA中,每只萤火虫都会被所有比它更亮的萤火虫所吸引。在这种交互机制中,没有明确的全局最优个体,也没有使用历史最优值,避免了该算法的任何潜在缺点,具有较高的收敛性能。

对萤火虫算法的优化性能的进一步改进,并应用于更复杂的问题是萤火虫算法的研究趋势。但任何算法的研究都不能停留在对性能的改进和应用上,算法要最终达到成熟,理论性的基础研究是必不可少的。

萤火虫算法作为一种优化的数值算法,其收敛性如何的问题受到关注,比如,其最终的收敛是否能一定收敛到问题的最优解,还是只有在优化函数满足一定的条件时才能收敛到问题的最优解。但由于萤火虫算法是一个随机系统,受到随机系数的影响很大,分析比较困难。许多学者使用各种不同的方法对其进行收敛性分析,确定收敛的条件,指导算法的改进工作。

高伟明采取Clerc和Kennedy两位学者提出的动态分析方法。为了便于对萤火虫算法的收敛性能进行分析,简化了位置更新公式中的随机因素。并采用与logistic映射相同的数学分析方法分析其收敛性能和随机特性。最后通过数学推理得出结论:当 \\beta_{0} < 2 时,算法可收敛。通过这种分析方法,只是说明算法在一定条件下是否收敛的问题,但并没有证明算法是否收敛到问题的最优解。

为了完善萤火虫算法的收敛性理论,胡婷婷等人就萤火虫算法建立了 Markov 链数学分析模型。通过分析该 Markov 链的性质 ,证明萤火虫位置的群体状态序列是有限齐次 Markov链 ;通过分析萤火虫位置的群体状态转移过程 ,得到群体状态序列必将进入最优状态集的结论 ;然后证明萤火虫算法满足随机优化算法全局收敛的两个条件,从而保证萤火虫算法全局收敛。

另外,陆克中等人首先从FA算法的收敛过程入手,对FA算法的收敛条件与收敛性进行了分析与论证,得出FA算法收敛的两个一般条件:随机扰动项的数学期望等于0;最大吸引度 \\beta_{0} ∈(0,2) ,通常取 \\beta_{0} ∈(0,1],并且 \\beta_{0} 越大,算法收敛速度越快。接着根据随机算法的收敛准则,证明了FA算法不具有全局收敛特性。然后应用数学归纳法,结合夹逼定理及反证法,从理论上证明了FA算法收敛于群体最优解,是一个局部收敛算法。

收敛性理论分析研究的主要目的是向研究者介绍如何分析FA的收敛性,并确定如何高效地指导算法的改进工作。

不同的研究人员提出了不同版本的萤火虫算法。为了对它们进行分类,需要采用一定的分类方案。根据要解决的目标问题领域,萤火虫算法可以初步分为传统的萤火虫算法、多目标萤火虫算法和离散版本的萤火虫算法。

请注意,传统的萤火虫算法主要用于连续优化问题。包括混合和在传统的萤火虫算法中所做的几种类型的修改,使该算法能够提供最优的结果。基于不同的方法,主要分为两种类型的修改。

第一种类型是在参数级别上进行的修改。在FA中,萤火虫依赖于个体之间的吸引力β和随机化参数α来更新它们的位置。如果算法的控制参数选择不当,就会导致不收敛的问题。因为学者们必须进行详细的参数研究,以找到最佳的参数设置。

第二种类型是在吸引模型层面上进行修改,其思想是优化FA的全吸引模型,这需要防止算法的振荡和收敛过慢。

总之,改进后的萤火虫算法可以分为两类:基于调整参数的萤火虫算法和基于改进后的吸引模型的萤火虫算法。

下图展示了萤火虫算法的分类。


萤火虫算法的分类

首先对于传统萤火虫算法的论文,分析和讨论了萤火虫算法的改进版本和混合版本的两种类型。此外,还对萤火虫算法的离散版本和多目标优化版本进行了综述。

为了平衡吸引力β和步长因子α对算法的影响,学者们在对参数的调整方面进行了大量的改进和优化。Eiben等人在1999年对进化算法的参数控制方法进行了明确的分类。他们在算法运行之前调用参数设置作为参数调整,并且这些参数的值在算法运行期间不会发生变化。另一种类型是,参数在算法运行之前有一个初始值。然后,随着算法的运行,参数值的值会不断变化。它允许在搜索过程的不同阶段使用不同的参数值。许多研究致力于自动参数调整或自适应参数控制,并将用户从参数值的选择任务中解放出来。

近年来,进化计算技术的自适应机制引起了广泛的关注,如何利用良好的自适应机制来提高系统的性能已成为许多学者的研究目标。

从理论上讲,萤火虫算法在迭代前期需要有较大的搜索步长来进一步搜索未知区域,在迭代后期需要有较小的搜索步长来微调优化精度,而FA的步长因子是常数,不利于算法的探索和开发。如果前期设置α值较大,该算法的搜索精度就会很低。α值较小,算法的搜索速度会很慢。因此固定的步长是无法平衡算法的精度与速度的。Wang等人通过理论推导,证明了当萤火虫算法收敛时,步长因子 α 将趋近于 0。在此基础上,众多学者们使用不同的策略来调整步长因子的值,使该值以许多不同的方式随着迭代次数的增加而减小。

Fister等人使当前步长因子等于上一代步长因子乘以一个介于(0,1)之间的数,该数由当前迭代次数决定。迭代次数越多,步长因子衰减越慢。王等人提出了与Fister等人类似的概念,只是随着迭代次数的增加,步长因子衰减得更快。Amaya等人使当前步长因子等于上一次迭代的步长因子和(0,1)中的随机数的乘积。上述研究中步长因子在搜索过程中下降得太快,这可能并不利于搜索。王等人使用动态参数策略来避免手动调整步长因子,使用递减速率k使步长因子在迭代过程中缓慢下降。实验结果表明所提出的 NDFA 获得了比其他四种 FA 变体更好的性能。因此,可以发现当设计另一种方法来减缓衰减时, 算法可以在大多数函数上得到有希望的解。

虽然递减的步长基本满足算法初期和后期对不同步长的需求,但在每次迭代中,不同萤火虫个体其邻域密度是不同的,随着迭代次数的增加,距峰值中心较近的个体邻域分布密度大,而较远的个体邻域分布稀疏。在这种分布密度不同的情况下使用相同的步长既不利于离峰值中心较远的萤火虫快速收敛到峰值上,也不利于离峰值较近的萤火虫个体进行微小的调整。在此基础上研究人员根据当前种群的进化状态,设置相应的反馈机制来动态调整步长因子。

Yu等考虑萤火虫个体最佳位置与全局最佳位置之间的绝对距离,自适应调整每个萤火虫的步长因子。Al-Wagih提出了以当前最大、最小和平均适应度值作为反馈的步长因子调节机制。于等[8]以萤火虫种群前两次迭代 的信息作为反馈,设置当前萤火虫步长因子。Liu等人采用最优距离与高斯分布相结合的自适应偏差度策略,优化固定步长因子,基于反馈的自适应步长因子确定是当前的研究热点。

由FA算法的吸引力计算公式可知,吸引力 \\beta_{ij} ∈[0, 1],且β是距离r的指数函数。对于宽搜索区域和高维优化问题,萤火虫之间距离过大,吸引力很容易为0,此时萤火虫的移动几乎是随机搜索,难以利用群体的搜索经验,从而导致算法收敛变慢。当萤火虫不断靠近时,吸引力又会迅速增加到1,这不利于体现不同位置产生不同吸引力的多样性。另外,指数函数的计算成本较高。

考虑到这些问题,近年来研究人员对于吸引度的改进目标主要可以归结为两个方面。一方面,为防止由于个体间较大的距离而成为无效个体,减少个体间随机游走和产生“振荡”现象的可能性,Liu等人在吸引力的计算中引入自适应βmin, 即使在算法的早期萤火虫之间的距离变长,个体也不会失去更亮的萤火虫j的吸引力,反而会使个体受到更大的吸引力,提高算法的收敛速度。随着迭代次数的增加,βmin逐渐减小,在算法的后期,βmin的值变小,可以防止过度吸引引起的“振荡”现象。

另一方面,减缓吸引力随着距离的减少而增加的速度。周等人提出一种快速吸引力计算公式,该吸引力是关于距离的幂函数,使吸引力根据距离的减少能够以相对较慢的速率单调递增。保证了群体之间的信息交互,使得萤火虫能够充分利用群体的搜索经验。

但是,如果修改只针对一个单独的参数, FA的效率和鲁棒性的改进依然是有限的。因此,同时改进吸引力和步长因子做进一步的研究,以提高效率和准确性。Vahab等人提出了一种动态控制机制,随着算法的完整演化过程,动态地选择步长缩放因子、吸引力系数、吸收系数和种群规模的最佳性能组合。以提高萤火虫算法的( FA )收敛速度和最小化适应度函数。Tao等人针对多变量约束优化设计问题,提出了一种基于自适应策略的萤火虫算法,提出了吸引力β的自适应策略以提高挖掘能力,并提出了步长因子的自适应策略以保证探索和开发之间的更好平衡。

萤火虫算法的特点是每个个体会受到多个更优个体的吸引而移动,这种交互机制被称为完全吸引模型。这种吸引模型的优点是不存在一个明显的全局最优,因此算法不易陷入局部极值。缺点是移动操作频繁,时间复杂度高。

为了在降低计算成本的同时获得高质量的解,Wang等人首次尝试改进吸引模型,提出了一种随机吸引模型,即每只萤火虫仅随机选择一只萤火虫作为学习对象。Verma等人通过基于维度的更新规则找到全局最优个体,每个萤火虫都向全局最优个体学习。Zhang等人提出了一种基于帕累托优势的策略来寻找有吸引力的萤火虫,根据萤火虫的吸引力只选择一只萤火虫。 Wang等人提出了基于精英策略的随机引导萤火虫算法,每个萤火虫都由精英萤火虫引导。

可以发现,他们的研究机制类似于PSO和BA,每个个体向一个或两个对象进行学习。但是,这可能会导致过早陷入收敛停滞和收敛精度低的问题。因此,需要进行更多的研究工作来提高算法的精度,同时降低时间复杂度。

周等人提出了一种局部吸引模型,首先萤火虫根据亮度进行排序,而萤火虫随机选择三个较好的个体进行学习。Wang等提出了一种邻域吸引萤火虫算法(NaFA)。NaFA提前设定了领域范围。每个萤火虫只与其附近的其他萤火虫进行比较,并被附近适应度更高的萤火虫所吸引,从而实现位置更新。对13个基准函数的仿真结果表明,具有邻域吸引的FA比其他6种改进的FA具有更高的求解精度。在NEFA 中,每只萤火虫与从种群中随机选取的几只萤火虫进行比较。

上述改进吸引模型的FA变体的差异,不仅包括每次迭代中选择萤火虫的数量,还包括选取萤火虫的方法。那么如何正确地选择学习对象?

对于完全吸引模型,采用顺序选择,每个萤火虫都可以被选择。NaFA中萤火虫的选择方法是邻域选择,与邻域的几只萤火虫进行比较,即每个萤火虫被选中的概率相同。RaFA、PaFA和NEFA算法的选择方法都是从种群中随机选择固定数量的学习对象,这种学习机制导致一些萤火虫很少被选择,从而降低了种群间信息共享的效率。因此,通过分析可以发现,对于交互机制的设计需要通过考虑这两个方面来提高FA的性能:萤火虫的选择方法和降低吸引力模型的计算复杂度。

王等人采用随机吸引模型,在探索能力和开发能力之间取得了平衡。Zhao等人引入了基于水平的吸引模型。萤火虫首先根据亮度分为不同的级别,每只萤火虫从一个更高的级别中随机选择两只萤火虫来学习。基于层次的吸引模型可以增加个体学习的多样性,提高跳出局部优化的能力。Wang等人使用概率选择来确定萤火虫的学习对象。这样就可以降低萤火虫之间的吸引力,避免振荡,提高求解的精度,加快收敛速度。彭等人应用了荧光素酶抑制的机理,保证每只萤火虫都能被公平地选择。同时,为了降低计算复杂度,提出了一种新的吸引模型——自适应吸引模型,该模型可以在每次迭代中自适应地调整萤火虫的选择数量。实验结果表明,该改进算法在求解复杂函数时具有较好的性能。

除此之外,有学者根据萤火虫的生活习性对FA进行了修改。在原始FA中,Yang等人假设种群中的萤火虫没有性别,一只萤火虫可以被其他所有萤火虫吸引。Takeuchi等人提出了相反的观点。雄性萤火虫可以被其他所有的萤火虫吸引,而雌萤火虫则只能被雄性萤火虫吸引。王等人提出了一种新的基于性别的吸引模型,全局搜索利用雄性萤火虫的运动,局部搜索利用雌性萤火虫的运动。Peng等人提出了一种新颖的求偶学习(CL)模型来提高 FA 的性能。在改进的模型中,种群被分为雌性和雄性子群。采用雌性归档机制筛选优秀萤火虫,当被选中的雄性萤火虫发出的光比当前萤火虫的亮度低时,会从雌性档案中选择一个雌性个体来引导被选中的雄性萤火虫的运动。从这些研究中,我们发现互动和信息共享对 FA 至关重要。而原始FA的完全吸引模型没有有效地利用可用信息,具有一定的盲目性。Mahaboob等人提出了一种具有捕食者策略的萤火虫算法(PsFA)。PsFA对种群中适应度值较差(亮度较低)的萤火虫进行自由搜索,扩大搜索范围,增强算法的全局搜索能力,避免陷入局部最优。Wang等人提出了一种新的基于维度柯西突变的阴阳萤火虫算法(YYFA)。采用一个设计的随机吸引模型来帮助收敛。采用阴阳萤火虫自我学习策略来降低时间复杂度。结果表明,YYFA在CEC 2013和约束问题上具有竞争性能。

  • 与机器学习相结合

机器学习技术是人工智能领域中最重要的研究方向之一。一般来说,进化算法开始于随机产生的初始化种群,当满足终止条件时才结束。在这个过程中,由于缺少解的先验知识,算法的执行都是在试探中进行的。由于萤火虫算法在迭代过程中产生的数据包含了搜索空间和问题特征的知识,而机器学习技术则可以利用这些中间数据来提取有用的信息,从而提高算法性能。群智能算法与机器学习技术相结合已被证明有利于提高算法收敛速度和求解精度。

其中反向学习(OBL)技术应用于萤火虫算法效果显著,因此近年来受到了极大的关注。此外,随着研究工作的进行,目前已衍生了一些OBL的变种,如准反向、准反射优化、一般反向、和重心反向等。OBL及其变种应用到萤火虫算法的研究成果中,不仅可以以一定的概率用于算法迭代过程中个体位置的更新,也用于获得更好的种群初始化位置。这些方法利用了反向个体提供的丰富信息,提高了算法收敛精度。但他们在计算反向个体时,将个体的所有维都取其反向值,这显然损失了原个体的有利信息。Park等人指出,对于一个个体,并不是所有维上的反向值都优于个体的值。因此,在目前相关研究工作中存在没有充分利用群体搜索信息、没有充分利用反向空间中的有用信息等不足。

为了解决这些问题,周等人结合正交试验设计和反向学习技术,设计一种正交反向学习策略(Orthogonal Opposition-Based Learning, OOBL) 来发现并充分利用个体和反向个体中隐藏的有用信息。最近,周等人在利用反向学习技术的同时,借鉴了两点交叉的思想,提出了两点全交叉操作,并将其应用于重新组织个体和反向个体的信息,得到了部分维上是反向值的反向候选解,以提取个体和反向个体中隐含的有用信息,构建了两点全交叉重心反向学习策略,并将该学习策略应用于萤火虫算法中,与基于其它反向学习技术的萤火虫算法变体进行比较,实验结果表明全交叉重心反向学习的萤火虫算法具有更好的收敛性能。

现实应用中存在许多复杂的高代价优化问题,其目标函数的评估需要消耗大量的时间和计算成本。为了减少优化过程的计算负担,代理模型广泛应用于工程设计中。群智能算法与代理模型结合,即利用了群智能算法求解高维多峰问题的优势,同时又利用近似模型降低目标函数的计算复杂性。代理模型也称为近似模型,本是机器学习算法的应用。2002年,Jin等人提出了演化算法与近似模型结合的初步方案一一一种基于代理模型的演化算法框架,用演化算法产生的历史数据来构建代理模型,再用于算法演化过程中。这个过程可视为将知识融入演化过程。这项研究成果受到了许多关注,更多的研究工作投入到这个领域。对于其他机器学习技术,Nasution等人利用模糊地理加权聚类与智能萤火虫算法(IFA)的杂交,在地区层面上表征了印度尼西亚社会脆弱性的主要因素。为了实现一种强大的方法来识别皮肤癌,而不进行任何不必要的皮肤活检,Sivaraj等人提出了一种新的混合技术,使用萤火虫与k-最近邻算法(FKNN)对皮肤图像进行分类。Ghorbani等利用支持向量回归(SVR)和FA预测从伊朗东阿塞拜疆省采集的215个土壤样本的田间容量(FC)和永久枯萎点(PWP),发现耦合方法优于SVR方法。Kardani等人将FA和SVR结合来预测伊朗北部的蒸发。将SVR与FA相结合,产生了一种继承了SVR的预测能力和优化能力的新方法。这种新方法可以以合理的速度进行高精度的预测。Chou等人开发了一种新的混合智能人工萤火虫群体算法,该算法基于SVR模型来预测码头附近的桥梁冲刷深度。Kumar等人提出了一种模糊的萤火虫贝叶斯滤波器来进行噪声的识别和去除。

  • 与元启发式算法相结合

根据无免费午餐定理,当在所有的优化问题上比较两个算法的平均表现时,他们是等价的。也就是说,每种算法具有各自的优点,有各自适用的应用问题和解决范围。以往的研究也同样证明没有哪一种算法能够对所有问题都能取得最好的解。但是,研究的目的在于提高算法整体性能,形成一种较为通用的问题解决程序,使得它对于多数类型的问题都能够得到更好的解。学者们很自然地想到将不同特点的算法结合起来,发挥各自的长处。

一方面,结合不同的元启发式算法,可以利用不同的启发式信息挖掘的知识来提高算法的性能。

不同SI算法具有不同的启发式信息,可以探索到问题中包含的不同知识。因此结合不同的SI算法可以利用不同启发式信息挖掘的知识,从而提高算法性能。另一方面,萤火虫算法的搜索具有全局性,而局部搜索算法具有高效找到局部最优解的特点。许多学者将两者结合并进行了深入的研究,取得了许多研究成果。

FA善于开发,而PSO则更利于探索。用PSO来弥补FA的表现是一个好主意。因此,Sivaranjani等人提出了混合粒子群优化-萤火虫算法(HPSOFA)来解决组合优化问题。Altabeeb等人提出了一种新的混合FA,称为CVRP-FA,它将FA与两种局部搜索和遗传操作符结合起来,以解决有能力的车辆路径问题。实验结果表明,CVRP-FA具有快速的收敛速度和较高的计算精度,并且在大多数测试实例中显著优于其他最先进的FA变体。Hassan等人开发了一种新的混沌正弦-余弦萤火虫(CSCF)算法来解决优化问题。基于工程设计的问题仿真结果验证了该算法的有效性、鲁棒性和有效性。Pitchaimanickam 等人提出了一种具有粒子群优化(HFAPSO)的混合萤火虫算法,以在浸出-c算法中寻找最优的聚类头选择。结果表明,与萤火虫算法相比,它获得了更好的吞吐量和剩余能量。

Xu等提出了一种基于矢量角学习机制(HFA-VAL)的混合萤火虫算法,该算法可以通过矢量角学习机制结合FA和DE的优点。HFA-VAL采用矢量角参数来自适应地调整萤火虫的移动步长,以避免落入局部最优状态。在进化过程中,采用差分法对主导领袖进行更新,以提高其他萤火虫的移动方向,扩大搜索能力。Xia等人在基于这两种算法的混合优化器中采用了三种新的算子。Rosi等提出了一种改进的自适应杂交萤火虫差异进化(AHFADE)算法,该算法基于FA和DE的杂交来估计目标的未知位置。所提出的AHFADE动态调整控制参数,从而在进化过程中保持较高的种群多样性。Goel和Maini 将蚁群算法和萤火虫算法相结合,提高了萤火虫算法的性能。Singh等人提出了一种新的混合优化技术(蜻蜓-萤火虫算法(DA-FA)。DA是最近提出的一种基于蜻蜓静态和动态群体行为的优化算法。该混合技术结合了DA的勘探能力和FA的开发能力,得到了理想的全局解。

另一方面,对FA的搜索是全局的,并且局部搜索算法具有有效地寻找局部最优解的特点。许多学者将这两种技术结合起来,并对它们进行了深入的研究,并取得了许多研究成果。

Long等人提出了一种将动态随机局部搜索算法与萤火虫算法相结合的混合萤火虫算法。研究结果表明:与其他启发式算法相比,该算法具有较强的寻优性能。张等人在 FA 中采用精英萤火虫的混沌局部搜索来获得探索和开发能力之间的权衡。Sahu等人将模式搜索作为局部搜索策略加入FA算法,更好地解决了多区域电力系统的自动发电控制问题。Zhou提出一种离散化的FA算法变种,对每次迭代的最优萤火虫执行k-opt局部搜索,进一步提高迭代最优解的质量。实验说明该算法在小规模TSP实例上得到了高质量的解。从大量文献可以看出,FA算法结构灵活,容易加入局部搜索,而且合适的局部搜索策略能够有效提高FA算法的性能。萤火虫算法在前期全局搜索能力相对较好,而在后期其局部搜索能力相对较强。根据这一特点,为了更好地平衡萤火虫算法的全局搜索能力和局部搜索能力,近年来,不少学者将其它算法与之进行了结合。一般来说,这种混合优化方法的收敛速度和综合性能相比其单一算法都有较为明显的提高。

到目前为止,针对FA的离散问题进行了不同的研究。根据所使用的更新空间,修改基本上可以分为两类。第一种类型是对连续空间执行更新机制,并将结果转换为离散值。常用的方法是利用s型和t型双曲函数根据概率条件将实值转换为二进制值。将得到的实解四舍五入到最近的整数值是处理整数和混合问题的另一种常用方法。第二类是在离散空间中进行更新。为了提高算法的性能,自适应步长是这方面的主要研究热点之一。

Zhang等人提出了一种基于距离的离散萤火虫算法。该方法动态更新了光吸收系数和步长因子,构建了一个交互式信息准则,提高了算法的效率。Li等人提出了一种改进的FA来定位物流无人机的配送中心。该算法将FA离散化,忽略了步长因子,基于改进后的萤火虫位置更新公式,引入了一种扰动机制和概率选择公式。Hsu等人提出了一种多群和离散萤火虫算法(MDFA)来同时处理多头门架表面安装技术机器的组件排序问题和馈线分配问题。MDFA包括一些新的特征,如多群、自适应步骤和探索到开发策略的使用。该改进方法使算法能够有效地搜索解空间。Bidar等人提出了自适应离散萤火虫算法(SADFA),这是一种解决最小扰动约束满足问题的新方法。在SADFA中,设计了一种自适应机制来赋予所提出的方法适当的活力,从而可以逃脱一些陷阱。实验结果表明,在非常合理的时间内,得到了满足所有新约束条件且与以往解具有较高相似率的最佳解。

针对现实日益困难而出现的复杂的多目标优化问题,有必要开发一些新的多目标优化算法。2013年,Yang 提出了一种多目标萤火虫算法(MOFA),对萤火虫的运动公式进行了改进,使运动公式的随机项在迭代过程中呈非线性递减,并使用权重比策略来确定当前的帕累托解。虽然现有的MOFA算法可以在某些MOPs上取得更好的效果,但其性能仍可以进一步提高。

Xie等人提出了一种混合多目标萤火虫算法(HMOFA)。在HMOFA中,采用混合正交试验设计的初始化方法和连续搜索空间的量化方法,在决策空间中生成一个均匀分布的初始总体。随机抽取外部档案中的精英来指导萤火虫在进化过程中的运动。并采用基于三点最短路径的归档剪枝策略来保持外部归档的多样性。实验结果表明,HMOFA算法相比,在收敛性、多样性和鲁棒性方面具有整体性能优势。但是,考虑到HMOFA需要为混合正交初始化方法指定两个合适的等级正交表,一些MOP问题不满足这些条件。可以看出,该算法虽然取得了良好的效果,但并不是通用的。

通过引入近似适应度计算的替代模型,Zhang等人提出了具有替代模型的多目标萤火虫算法(MOFA-SM)。在MOFA-SM中,根据混沌映射进行初始化。外部归档是基于偏好排序,采用轻量级聚类剪枝策略。在进化的过程中,我们使用从档案中选择的精英解决方案来指导寻找最优解决方案的运动。仿真结果表明,MOFA-SM在收敛迭代性和稳定性方面具有较好的性能。Bajaj等人新提出的基于帕累托的多目标萤火虫算法(pb-MOFA)。在pb-MOFA中,基于改进的萤火虫算法和帕累托前沿,建立了一种新的多目标优化方法,以解决无源功率滤波器的设计问题。通过将所得解与计算得到的三个pi进行比较,验证了所提出的pb-MOFA在解决相关多目标优化问题中的效率和准确性。Shayeteh等人提出了一种新的基于吸引和拥挤距离定律的多目标萤火虫算法。

不难发现,目前对多目标萤火虫算法的研究不仅结果较少,而且这些算法大部分仅来自算法的局部部分,并不能提高算法的整体性能。为了提高多目标萤火虫算法的整体性能,以更好地解决复杂的MOP问题,Xie等人提出了一种基于多重合作策略(MOFA-MCS)的多目标萤火虫算法。MOFA-MCS采用均匀化和随机化的方法生成初始种群,采用外部档案中的精英解引导萤火虫移动,利用Levy飞行在移动过程中增加随机干扰。同时也采用了ε-三点最短路径策略来保持归档解决方案的多样性。实验结果表明,MOFA-MCS在收敛性和多样性方面具有显著的性能优势。Lv等人提出了一种基于补偿因子和精英学习(CFMOFA)的多目标萤火虫算法。在CFMOFA中,将补偿因子引入萤火虫学习公式,将迭代产生的非劣解存储在外部档案中,并采用随机的外部档案粒子作为种群进化的精英粒子。结果表明,CFMOFA在收敛性、多样性和鲁棒性方面具有显著的优势。

杨最初开发了FA来解决连续优化问题。随后,将FA扩展到求解多模态优化问题、离散优化问题、动态和不确定优化问题和多目标优化问题。今天,FA及其变体已经被应用于优化和分类问题的几乎所有领域,以及工程实践问题。它的主要应用可以概括为以下类型的优化问题:连续、组合、约束和多目标。它还被用于机器学习、数据挖掘、特征选择和神经网络中的分类问题。此外,萤火虫算法几乎应用于工程的所有分支,如图像处理、工业优化、无线传感器网络、机器人、调度等。所开发的萤火虫算法应用程序的分类如下图所示。

(由于篇幅原因,应用研究的具体阐述部分请见原文。)

萤火虫算法的各种应用

FA是群智能领域的一个研究热点。它是近年来发展起来的一种相对新颖的优化算法,效率显著。萤火虫算法研究文献的快速扩展证明,萤火虫算法进入了成熟阶段。本文对最新的萤火虫算法及其应用进行了全面的综述,以向读者介绍最新的发展,并提供当前文献的发展现状。

萤火虫算法解决了以下领域的问题:连续优化、组合优化、约束优化、多目标优化,以及分类。工程应用体现了其适用性的重要领域。这次审查的目的有两个方面。首先,总结了不同应用领域的应用现状。本文综述证明了萤火虫算法可以实际应用于多个问题领域。其次,本文综述为萤火虫算法分析提供了突出的基础,并向研究人员提出了在使用该算法设计系统时必须应对的新技术趋势和设计挑战。如前所述,该算法在未来的研究中有更大的修改空间,它仍然是科学和工程领域最具应用和变体的模型之一。在今后的工作中,可以从以下几个方面进行进一步的探索和研究。

  • 算法理论分析:FA是一个复杂的非线性随机系统,在理论上难以进行分析。此外,现有的理论研究成果还不够充分,因此对萤火虫算法的理论分析仍然是未来的主要研究内容。特别需要注意的是,当算法满足一定条件时,算法收敛于问题的最优解的证明将是未来收敛性理论分析的重要组成部分。
  • 参数调优:所有的群智能算法,包括FA,都有参数,这对算法的性能有较大的影响。因此,如何在迭代过程中自动调整参数,使其智能地适应给定的问题,是未来需要进一步研究的工作。
  • 结合其他优化策略:在FA的改进研究中,应用机器学习技术和混合的其他智能优化算法都是从结合优化策略相互补充的角度来提高算法的性能。首先,对于混合算法,虽然FA有许多不同的变体,但毫无疑问,未来将会出现更多的混合变体。目前,混合方法是通过试错法来实现的。如何通过结合不同的算法来实现更好的混合变量还不清楚,这需要更多的研究和更深入的理解。此外,利用机器学习技术提高萤火虫算法的性能也取得了一些研究成果。但是,如何进一步分析FA解决方案过程中产生的数据,以及将机器学习技术应用于FA后产生的数据,以指导优化过程,仍需深入探索。
  • 多目标萤火虫算法是一种很有前途的多目标优化技术。然而,多目标萤火虫算法的研究和应用仍处于起步阶段。现有的多目标萤火虫算法在解决复杂的MOP问题方面也有很大的性能改进空间。
  • 应用:应用研究部分表明,FA几乎可以实际应用于所有领域。FA是一种简单、通用、灵活和非常高效的算法。毫不奇怪,FA及其变体几乎在科学的所有领域,工程和工业。利用FA可以有效地解决大量不同的实际问题,这可以吸引研究者在不久的将来将萤火虫算法应用于他们的问题领域。

现在致电 13988889999 OR 查看更多联系方式 →

Top 回顶部

平台注册入口