科学网 › 标签 › 烟花算法引论

标签: 烟花算法引论

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

烟花算法的未来发展方向: sciencepress 2015-7-20 07:45; 本博之前介绍了《一种新型群体智能算法——烟花算法》及《烟花算法的研究历史与现状》（点击蓝色标题可了解详细内容），在此继续介绍烟花算法的未来发展方向。目前，烟花算法的研究还非常初步，正处于逐渐发展的过程中。新的思想和算法还在不断涌现，许多方面的研究还很肤浅，还存在空白，需要广大有兴趣的研究人员对其进行广泛探讨和深入研究。烟花算法的未来发展方向 ▼ 烟花算法的未来发展归纳起来有如下几个方面。 1.算法的理论基础和分析(稳定性、收敛性、收敛特性、参数灵敏度分析)。 2.各种改进方法的深入研究(各种因素对烟花算法性能的影响，如何有效控制和调整，重点是子烟花间的协同机制建立和研究，发展出协作型烟花算法)。 3.混合方法的研究。 4.大数据问题的求解(如何处理巨大数据、如何处理大量目标的协同优化)。 5.动态优化问题的求解(优化目标值随时间变化的情况，如群体机器人的动态目标追踪搜索问题)。 6.发展更为广泛的应用。未来五年内需要研究的 25 个问题 ▼ 根据我们对烟花算法的长期研究，经过归纳整理可以提出未来五年内有关烟花算法需要研究的25个问题。 1.研究烟花算法求解轨迹特点。 2.研究烟花算法的收敛性、稳定性、全局性能。 3.研究建立烟花算法求解的概率模型，分析其求解性能。 4.研究烟花算法的求解效率，即如何充分利用已经获得目标函数值信息提高搜索效率。 5.研究烟花算法各种参数的作用和如何合理设定。 6.研究烟花算法爆炸算子的作用。 7.研究更少设定参数的简化烟花算法。 8.研究不同概率分布类型的随机数对烟花算法的影响。 9.研究莱维(Lμevy) 烟花算法。 10.研究烟花算法的协作和竞争机制，发展协作型(Cooperative) 烟花算法。 11.研究现有烟花算法的改进方法。 12.研究混合型烟花算法，即其他计算方法与烟花算法结合的高效方法。 13.研究多目标烟花算法，以及求解许多目标的优化烟花算法。 14.研究烟花算法求解动态优化问题。 15.研究求解约束优化问题的烟花算法。 16.研究求解组合优化问题的离散烟花算法。 17.研究处理大数据的烟花算法。 18.研究高维空间搜索的烟花算法。 19.研究烟花算法的并行化实现方法。 20.研究基于GPU 的并行烟花算法。 21.研究烟花算法在智能电网中的应用问题。 22.研究烟花算法在数据挖掘与知识发现中的应用问题。 23.研究烟花算法在群体机器人搜索控制中的应用问题。 24.研究烟花算法在语音、图像处理与分析中的应用问题。 25.研究烟花算法在互联网搜索技术中的应用问题。本文由刘四旦摘编自谭营著《烟花算法引论》一书。《烟花算法引论》系统描述了作者提出的一种新型群体智能算法——烟花算法,它的产生、算法实现、理论分析、算法改进及其应用,为读者勾勒出了烟花算法的全景图像。主要内容包括:烟花算法的基本原理与实现及其性能分析、收敛性和时间复杂度分析、多种改进算法、混合方法、离散烟花算法、烟花算法的并行化实现,以及几种应用实例。书中重点介绍了烟花算法的参数设定,各种改进方法、并行化实现、与典型群体智能算法的性能对比分析等。书中还包括了烟花算法的最新资料和一些重要算法的流程图,以及源代码的链接,供感兴趣读者参阅和使用。非经授权，请勿转载转载请留言或联系：（010）64000159 科学出版社│微信ID：sciencepress-cspm 专业品质学术价值原创好读科学品味; 个人分类: 科学书摘|4640 次阅读|0 个评论

烟花算法的研究历史与现状: sciencepress 2015-7-16 09:02; 自从烟花算法的开创性论文“Fireworks algorithm for optimization”由谭营于2010 年在首届国际群体智能大会上发表以后，业界对烟花算法的研究就逐步深入和铺开了。本文详细介绍了烟花算法的研究历史和研究现状，综述了到目前为止的烟花算法研究文献。通过对原始烟花算法深入、细致的分析，针对原始烟花算法存在的不足，相继提出了大量的改进方法，并据此发展了各种改进算法，以及几种混合型方法，极大地提高了原始烟花算法的性能，丰富了烟花算法的研究内容。进一步，研究了烟花算法求解不同类型优化问题的能力，还有大量的研究人员进行了烟花算法的应用研究，给出了一些典型的成功应用案例。 1、理论研究方面在收敛性的理论分析工作方面，Liu 等从理论上详细分析了烟花算法的收敛性，指出烟花算法是一个吸收马尔可夫过程，进而给出了收敛性定理，并给出严格的数学证明。此外，在本书中，我们首次研究了随机数对于烟花算法性能的影响，实验表明烟花算法对于随机数产生器的要求不高，不同的随机数生成方法对于算法性能的影响不明显。 2、算法研究方面烟花算法研究的开创性论文是由作者发表于首届国际群体智能大会。该文首次提出了受烟花爆炸启发的群体协同优化算法，即烟花算法。详细介绍了算法的组成、各个算子的要求和原则，以及各个算子的具体实现方法。该文指出烟花算法包括爆炸算子、高斯变异算子、映射规则和选择策略，并给出了满足原则的具体实现方案。为了验证烟花算法的有效性，实验对比了两个典型群体智能算法——标准粒子群优化算法和克隆粒子群优化算法，在由11 个测试函数组成的集合上，烟花算法具有明显的性能优势。Pei 等研究了适应度函数估计对于烟花算法加速性能的影响，讨论了不同适应度函数值的估计方法对性能的影响，实验表明二次多项式模型和随机选择样本策略的性能最优，并且相对于烟花算法其性能优势非常明显。Ding 等提出一种并行烟花算法GPU-FWA，它是基于图形处理单元(GPU) 的烟花算法的高效并行实现方案，可以全面加速烟花算法的运行速度，在当前流行的GPU 硬件和CUDA 平台下，实现了近200 倍的加速性能。相对于烟花算法，GPU-FWA 做了一些算子上的改动，主要目的是减少烟花之间交互的同时使得性能损失在一个可以接受的范围内。在文献中，烟花之间每隔一定代数才会计算爆炸半径和爆炸幅度。这极大地降低了烟花之间的交互，提高加速比。Zheng 等对烟花算法的算子进行了细致的分析，针对烟花算法存在的缺陷进行了改进，并最终提出增强烟花算法。改进的工作包括基本烟花算法中的爆炸算子、高斯变异算子、选择算子，以及映射规则等4 个方面。Zheng 等和Li等细致地研究了烟花算法中爆炸幅度的自适应策略，分别提出了动态搜索烟花算法和自适应烟花算法。此外，有部分学者研究了烟花算法和其他算法的混合算法。Zheng 等和Yu 等分别尝试将烟花算法和差分演化算法进行混合。混合算法FWA-DE 相对于烟花算法和差分演化算法在测试函数集合上具有更好的性能。Gao 等将烟花算法和文化算法进行混合，并应用到滤波器设计的优化问题中，同时对比了量子粒子群优化算法和自适应量子粒子群优化算法，实验结果表明文化烟花算法具有更好的性能。此外，Zhang 等提出了生物地理学优化{烟花混合算法(BBO-FWA)，该算法的性能要远远优于所基于的BBO 和FWA 两种算法。Pholdee 和Bureerat 系统比较研究了24 种元启发(meta-heuristic) 算法的优化性能，他们主要是针对具有动态约束的桁架(truss) 质量最小化问题，在不同问题规模的多种情况下仔细地比较了这些算法的性能，给出了客观的排名，其中烟花算法处于中上游，并被证明是一种有效的算法。 3、求解不同类型优化问题方面连续优化问题又分单目标问题和多目标问题。前述的大量算法都是针对单目标优化问题进行的，已经产生了大量的高效算法。对于多目标优化问题，目前研究的还不多。Zheng 等最先将烟花算法应用于多目标问题，并提出多目标烟花算法(MOFOA)，应用到施肥问题的求解中。相对于其他著名的多目标群体智能算法和多目标进化计算方法，MOFOA 表现出了非常优异的性能。目前，我们也在进行着这方面的研究工作，提出了基于S-metric 的多目标烟花算法，研究成果将另文报告。此外，我们首次尝试使用离散烟花算法用于求解旅行售货商问题，提出求解旅行商问题的离散烟花算法(TSP-FWA)，并将其应用到标准TSP 数据集上，取得了很不错的实验效果。 4、应用方面目前，烟花算法及其改进算法已被应用到了许多实际优化问题求解中。应用领域主要包括方程组求解、非负矩阵分解(NMF) 计算、垃圾邮件检测算法中参数优化、方向性特征距离度量、数字滤波器FIR 和IIR 的设计、油料作物的施肥问题、群体机器人多目标搜索、电力系统重构问题等。同时，我们也尝试将烟花算法扩展应用到文本聚类和模式识别问题优化中，即如何将烟花算法有效地应用于大数据的文本聚类问题。本文由刘四旦摘编自谭营著《烟花算法引论》一书。《烟花算法引论》系统描述了作者提出的一种新型群体智能算法——烟花算法,它的产生、算法实现、理论分析、算法改进及其应用,为读者勾勒出了烟花算法的全景图像。主要内容包括:烟花算法的基本原理与实现及其性能分析、收敛性和时间复杂度分析、多种改进算法、混合方法、离散烟花算法、烟花算法的并行化实现,以及几种应用实例。书中重点介绍了烟花算法的参数设定,各种改进方法、并行化实现、与典型群体智能算法的性能对比分析等。书中还包括了烟花算法的最新资料和一些重要算法的流程图,以及源代码的链接,供感兴趣读者参阅和使用。非经授权，请勿转载转载请留言或联系：（010）64000159 科学出版社│微信ID：sciencepress-cspm 专业品质学术价值原创好读科学品味; 个人分类: 科学书摘|9542 次阅读|0 个评论

一种新型群体智能算法——烟花算法: 热度 27 sciencepress 2015-7-7 08:33; 烟花算法是我在观察现实中的烟花在空中爆炸这一现象，受到启发而提出的一种具有爆炸搜索机制的全局优化求解的新型群体智能算法，它在求解复杂优化问题中表现出了非常优良的性能和很高的效率，已经逐渐获得了业界的高度关注和跟踪研究。通过近5年的发展，已经相继提出了二十余种烟花算法的改进方法、收敛性分析和多项典型应用，逐渐发展成为一种十分有效的群体智能算法。 1、烟花算法的起源与动机记得小的时候在四川老家，每逢一年中最重要的节日春节到来时，我都会邀上几位要好的小伙伴或同学一起到空旷的操场或人烟稀少的街道上，尽情燃放一种在空中爆炸的爆竹花炮。有时，几个小伙伴还会一起进行比赛，看看谁的爆竹扔得高、放得响，在空中燃放出最美丽的图像。这些都是伴随着我们儿时快乐和美好的时光，在我儿时的脑海里留下了很深的印迹。 2006 年春节，我来北京大学任教将近一年了。在这段时间里，我对进化计算投入了较多的精力，进行了深入的研究。因此，在这段时间不管在干什么和遇到什么新鲜的事物都会看看它们是否与进化计算能联系上。恰好在这一年春节期间，北京将禁放烟花爆竹的规定改为限放，首都市民都迫切地期待着除夕之夜的到来，盼望着过一个更加热闹和欢庆的春节。这年的除夕之夜，北京的天空尽情地开放，市民们都争相燃放。人们燃放出了大量绚丽多彩的礼花，将漆黑的夜空照得亮如白昼，五彩斑斓的烟花，燃放出各种美丽的图像，激发了我内心深处的儿时回忆，心情无比的畅快和愉悦。此时，我的脑海里突然将烟花的爆炸图像与进化计算中随机搜索建立起了联系，产生了一种可以用像烟花爆炸图像一样的方式来对问题解空间进行有效搜索的新方式。通过模拟烟花爆炸的方式来进行多点同时爆炸式搜索，这也许是一种高效的搜索方式，是有别于现有其他方法的新型搜索方法，从而有了研究这种爆炸搜索方式的想法，当时为其取名烟花算法(fireworks algorithm，FWA)。虽然烟花算法这个名称比较直观和简洁，但是由于它没有直接与优化等求解问题建立直接的联系，此后有些研究人员有时也用其他别称来称呼我们的烟花算法，如烟花优化算法、烟花爆炸算法、烟花爆炸优化算法、烟花爆炸搜索算法、爆炸搜索方法等。尽管有这些不同的别称，这里统一采用原始的名称烟花算法，以免混淆。我们对烟花算法的研究动机是希望寻求一种求解复杂问题的全局最优解的高效方法。尤其是对具有多模特性的复杂优化问题能够找到高效求解的新途径。在2006 年的夏季学期，我招收了来自吉林大学的朱元春同学做我的直博生，并安排他来我的实验室从事毕业设计工作。我将之前的想法和研究烟花算法的任务交代给他来实现，并将他的毕业设计题目拟定为“烟花算法的研究与实现”，与他一道开始了对烟花算法的全面研究。经过半年时间的深入研究，我们共同设计了烟花算法的各个主要要素、组成和基本框架，并以“爆炸算子”为基础搭建了基本的烟花算法。到2007 年5 月份，我们就完成了对烟花算法的基本研究工作。但是，在接下来的近两年的时间里，因为忙于主持一项国家863 计划项目，只得暂缓了对烟花算法的相关研究工作，直到2009 年夏才有机会重新展开对烟花算法的研究。2010 年，在首届国际群体智能大会上发表了题为“Fireworks algorithm for optimization”的开创性学术论文。自此烟花算法的研究开始受到业界的关注，对其的研究才开始在群体智能领域逐渐展开。 2、烟花算法属于群体智能优化算法研究范畴群体智能(swarm intelligence，SI) 是指由许多简单个体组成的群体呈现出的涌现(emergence) 行为所表现出的集体智能，是单个个体所不具备的强大能力，如生物群体系统有蚁群、鸟群、蜂群、鱼群、蜘蛛、萤火虫、细菌等。鸟群掠过天空、蚁群寻觅食物、鱼群在水中游荡、烟花在空中爆炸、蜘蛛的爬行等，这种群体的运动称为群体行为。尽管这些群体中的每个个体都非常简单，但大量个体组成的群体所表现出的集体行为却是非常复杂的，呈现出了智能的特色。群体智能是进化计算的一个活跃分支，隶属于计算智能的范畴。近几十年来，计算智能领域取得了丰富的研究成果，包括人工神经网络、模糊逻辑与系统、进化计算、混沌计算、模拟退火、禁忌搜索，以及各种混合策略等，都是通过模拟或揭示某些自然现象或过程来实现的。优化问题是一个古老且永恒的研究问题，也是解决众多问题的基础。大量学者和实际工作者都致力于对其进行不懈的研究。不同于经典优化算法采用确定性规则的方式，群体智能优化算法利用一种概率转移方式，通过各种随机因素结合元启发性规则，采用群体中的多个个体同时对解空间进行并行搜索的方式，通过群体中个体的相互协作与竞争来实现对优化问题的最优解的有效搜索，具有随机性、自适应性、鲁棒性、并行性等显著特点。在求解复杂优化问题时，群体智能优化算法表现出了非常明显的优势，引起了人们的高度重视，成为目前的研究热点。群体智能优化算法可以分为基于生物群体的群体智能优化方法和基于非生物群体的群体智能优化方法。前者包括蚁群优化、粒子群优化、鱼群搜索、虚拟蜜蜂算法、萤火虫算法-I、萤火虫算法-II、布谷鸟算法、蝙蝠算法、人工蜂群算法、人工鱼群算法、磷虾群算法、细菌觅食优化算法等。后者包括烟花算法、水滴算法、头脑风暴优化算法(BSO)、磁铁优化算法等。目前，群体智能算法研究主要包括理论、算法、求解问题类型、应用。其发展趋势包括混合算法、求解大规模问题(面临维数灾难、大数据难题)、新型改进算法、理论分析等。通常，群体智能优化算法都有一定的共性，即由组成群体的多个个体(社会昆虫、或粒子) 的相互协同，具有交互传递信息(直接或间接地) 和交互式地适应环境的能力，使群体中的个体对环境的适应性逐代变得越来越好，逐渐求得问题的全局最优解的足够好的近似解。群体智能优化算法所具有的这种协同交互能力能够打破没有免费午餐(NFL)定理的魔咒，预示了存在并且能够发展出具有性能更加优良的高效算法。这预示着对群体智能优化算法的深入研究将可能给我们带来难以预想的益处，因此激励更多的研究人员从事群体智能的研究和在更多的实际领域里积极采用群体智能的最新研究成果，使得群体智能可以更好地为人类社会服务。 3、烟花算法的组成与研究内容烟花算法的基本组成框架如下图所示，主要由爆炸算子(explosive operator)、变异操作(mutation operation)、映射规则(mapping rule) 和选择策略(selection strategy) 四大部分组成。爆炸算子包括爆炸强度、爆炸幅度、位移变异等操作；变异操作主要包括高斯变异操作等；映射规则包括有模运算规则，镜面反射规则和随机映射规则等操作；选择策略包括有基于距离的选择和随机选择等操作。图烟花算法的基本组成框架图烟花算法的工作过程与一般群体智能优化算法相似，首先随机选择N个烟花初始化群体，然后让群体中的每个烟花经历爆炸操作和变异操作，并应用映射规则保证变异后的个体仍处于可行域内，最后在保留最优个体(即精英策略) 的前提下，应用选择策略从生成的所有个体(烟花和火花) 中选择出余下的N-1 个个体共同组成下一代的群体。这样周而复始，逐一迭代下去。通过这种交互传递信息(直接或间接地) 使群体对环境的适应性逐代变得越来越好，从而求得问题的全局最优解的足够好的近似解。目前，对烟花算法的研究工作主要包括理论分析、算法研究、求解问题类型和应用研究。 (1) 理论分析。研究烟花算法的求解机理、收敛性质、演化轨迹特点，各参数对算法性能的影响等理论问题，为开发新的算法和改进现有算法提供理论指导。 (2) 算法研究方面。在算法研究方面，通过对烟花算法基本组成的各个成分进行深入分析和调整，不断改进烟花算法的性能(收敛性、解的精度、时间效率)，提出了各种不同的改进烟花算法。同时，通过与其他方法的结合，取长补短，发展出高效的混合型方法。 (3) 求解问题类型。由于烟花算法的通用性，可以用于求解下列不同类型的问题，即单目标优化问题、约束单目标优化问题、多目标优化问题、约束多目标优化问题、许多目标优化问题、组合优化问题(combinatorial optimization problem，COP)、动态优化问题(dynamic optimization problem，DOP)、其他优化问题。 (4) 应用。烟花算法是一类群体智能优化方法，具有求解复杂问题的全局最优解的能力，同时对求解问题的目标要求很低，不要求问题的目标函数的梯度信息，所以具有广泛的适应性。因此，烟花算法可以应用到许多实际应用领域，求解人们可能遇到的各类问题。 4、烟花算法的优点与特色烟花算法不仅继承了现有群体智能优化算法的许多优点，还具有明显的自身特色，归纳起来，烟花算法具有下面一些优点。（1）爆发性(explosive)。每次迭代开始，需要让烟花进行爆炸，在辐射范围内产生许多与该烟花本身不同的火花。之后，依据特定选择策略选择N 个火花或烟花做为下一代烟花群体，恢复烟花数目，并为下次爆炸过程做好准备。（2）瞬时性(instantaneity)。烟花算法中爆炸产生的火花，如果没有在选择策略中被选中成为下一代的烟花，这些火花或烟花本身都将在本次迭代中消亡，也就是说，一次特定的爆炸只存在于一次特定的迭代之中，具有瞬时存在性。（3）简单性(simplicity)。每个个体只能感知局部信息，个体的能力或遵循的规则非常简单，因此算法的组成和实现都非常简单。（4）局部覆盖性(locality)。对于某一个烟花而言，它的爆炸范围是整个自变量取值范围的一个小部分，其爆炸出的火花是这个爆炸范围内的一些局部点，只是对爆炸范围的区域内的点有一定程度的随机覆盖，但是不会涉及爆炸范围外的点，因此说这种爆炸具有一定的局部性。（5）涌现性(emergent properties)。使用简单交互规则，通过协同与竞争方式个体间相互作用，其群体总体表现出来的单个个体不具有的复杂行为，呈现出智能的特点。涌现现象是以相互作用为中心的, 它比单个行为的简单累加要复杂得多。（6）分布并行性(distributed parallelism)。群体中个体相对简单，没有一个直接的中心控制约束，每个个体进行局部相互作用，本质上是一个分布式方法，呈现出高度并行的特色，特别适合并行化处理。（7）多样性(diversity)。首先，烟花个体的多样性，我们通过一定的选择机制，使选择保留下来的烟花具有不同的位置，以保证算法的多样性特征。其次，爆炸强度和爆炸幅度的多样性，即在爆炸强度的作用下，根据各个烟花的优良度不同(适应度函数值大小不同)，各个烟花产生不同个数的火花。在爆炸幅度的作用下，根据各个烟花不同的优良度，各个烟花产生的火花拥有不同的变异幅度。最后，爆炸算子中的多种变异共存，正如烟花有多个隔层那样，我们设计出的爆炸幅度中存在有多种变异。目前有两种变异：一种是位移变异；另一种是高斯变异。其中，第一种位移变异是跟自变量的取值区间，以及粒子本身的优良度(决定了变异幅度的大小) 相关的一种变异；第二种高斯变异只与烟花本身的位置有关。这两种变异是本质上不同的变异，保证了变异的多样性。（8）可扩充性(scalability)。由于个体相对独立，个体间的协作通常通过间接的方式实现信息交流，增加或减少部分个体，对系统的影响都不剧烈，从而保证系统具有很强的可扩展性。（9）适应性(adaptability)。由于只使用各个个体的适应性来对系统求解能力进行评估，因此对所求解问题的要求非常低，甚至不要求所求解问题具有显式的表达。本文由刘四旦摘编自谭营著《烟花算法引论》一书。《烟花算法引论》系统描述了作者提出的一种新型群体智能算法——烟花算法 ,它的产生、算法实现、理论分析、算法改进及其应用,为读者勾勒出了烟花算法的全景图像。主要内容包括:烟花算法的基本原理与实现及其性能分析、收敛性和时间复杂度分析、多种改进算法、混合方法、离散烟花算法、烟花算法的并行化实现,以及几种应用实例。书中重点介绍了烟花算法的参数设定,各种改进方法、并行化实现、与典型群体智能算法的性能对比分析等、书中还包括了烟花算法的最新资料和一些重要算法的流程图,以及源代码的链接,供感兴趣读者参阅和使用。非经授权，请勿转载转载请留言或联系：（010）64000159 科学出版社│微信ID：sciencepress-cspm 专业品质学术价值原创好读科学品味; 个人分类: 科学书摘|29878 次阅读|68 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 烟花算法引论

相关帖子

相关日志

关闭安全验证