基于排他策略和反思算子的协同烟花算法_李克文.pdf

年月第 卷第期计算机工程与设计 基于排他策略和反思算子的协同烟花算法李克文，吴雪锋，王晓辉（中国石油大学（华东）计算机科学与技术学院，山东 青岛 ）摘要：针对烟花算法局部搜索能力弱、粒子间缺乏协同合作、粒子搜索区域重叠等问题，提出基于排他策略和反思算子的协同烟花算法（）。根据烟花粒子局部搜索中正确和错误方向上的经验进行反思学习寻找潜在优质解；在全局搜索中通过个体与优质粒子间的位置信息协同烟花搜索；基于距离的排他策略避免粒子搜索彼此重叠的区域，陷入局部最优。在 个标准测试函数上的实验结果表明，所提算法相较 、在寻优精度和收敛速度方面具有更好的优化性能。关键词：烟花算法；局部搜索；搜索经验；反思学习；协同搜索；基于距离的排他策略；优化性能中图法分类号：文献标识号：文章编号：（）：收稿日期：；修订日期：基金项目：国家自然科学基金重大基金项目（）；山东省自然科学基金项目（）作者简介：李克文（），男，黑龙江齐齐哈尔人，博士，教授，博士生导师，高级会员，研究方向为人工智能、机器学习与数据挖掘；通讯作者：吴雪锋（），男，河南信阳人，硕士研究生，研究方向为群智能优化、数据挖掘；王晓辉（），男，山东潍坊人，硕士研究生，研究方向为大数据分析。：，（，（），）：，（），：；引言烟花算法（）是 等基于烟花的爆炸结合进化计算的随机搜索提出的一种全局优化算法，。目前为止烟花算法仍存在一些不足有待改进，如寻优过程中局部搜索能力弱、粒子间缺乏协同合作、粒子搜索区域重叠等。针对上述问题，诸多学者提出了许多烟花算法变体提高算法的寻优效果。等对原始烟花的爆炸方式、变异算子等多个部分进行改进提出了。等在 中设计了一种传递函数将烟花的等级传递到火花数量和爆炸幅度的计算上。等提出了，将爆炸火花中的最差个体与最优个体之间的距离作为下一次迭代的爆炸半径。等针对最小爆炸幅值检测策略中的阈值问题，提出了 。等利用精英选择策略研究了近似算法对提高烟花算法收敛速度的影响。等引入了一种引导突变算子提出了 可以提高烟花的收敛速度和探测能计算机工程与设计 年力。等提 出 了 一 种 协 作 框 架 用 于 选 择 算 子。等针对解决多模式优化问题提出了一种基于淘汰者锦标赛的烟花算法（）。以上改进方法相对传统烟花算法性能有了较大的提升，但都没能很好地解决上述个问题。本文提出了一种基于排他策略和反 思 算子的协 同烟 花算法（），相较于传统烟花算法具有更高的寻优精度和更快的收敛速度。在迭代过程中根据粒子爆炸过程中在正确和错误方向上的爆炸经验构造反思算子寻找潜在最优解，提高算法的局部搜索能力；在全局搜索中充分利用粒子与优质粒子间的位置信息修正粒子搜索方向，协同烟花进行搜索，提高算法的全局搜索能力；根据基于距离的排他策略对搜索过程中搜索区域重叠的粒子进行调整，避免粒子重复搜索相同区域造成资源浪费。通过对 个不同标准测试函数的仿真实验，相较于传统的烟花算法，本文改进的 算法能够显著地提高算法的收敛速度和寻优精度，具有更好的优化性能和鲁棒性。烟花算法框架烟花算法是基于烟花爆炸现象的一种新型优化算法，主要步骤包括爆炸、变异、映射和选择。烟花通过爆炸和变异生成新火花，超出界限的火花根据规则映射到可行空间，从烟花粒子、火花粒子和变异粒子中选择出新一代的烟花，迭代该过程直到满足问题的精度或者达到最大函数评估次数。爆炸算子爆炸算子是烟花算法的核心组成，火花粒子的质量直接决定着烟花算法的寻优性能。（）爆炸火花数量：当前流行的几种烟花变体中，烟花爆炸产生的火花数量计算公式如下 （）（）（）（）（）其中，是控制一次迭代过程中产生爆炸火花总量的常量参数。在式（）的作用下，适应性更好的烟花在爆炸过程中可以产生更多的搜索火花，更彻底地搜索当前区域。但是这个公式也带来了一些问题：研究结果表明，不同的目标函数和搜索空间中的不同位置会导致适应度值波动较大，因此根据式（）计算的爆炸火花的数量在迭代过程中表现的极不稳定。本文采取一种简单且常见的幂律分布来控制每个烟花的火花数量，计算公式如下（）其中，为烟花的适应性排序，为烟花总数，为控制火花数量分布的参数。越大，适应性好的烟花就会产生更多的爆炸火花。文献 验证了这是一种很有效的资源分配方式。（）爆炸半径：在最近的几项工作中，只有核心烟花是采用动态爆炸半径的做法导致非核心烟花无法充分展现其搜索价值，本文中所有烟花的爆炸半径都采用以下公式进行动态控制（）（）（）（）（）其中，表示烟花在第次迭代中的爆炸半径，和分别表示放大和缩小系数。根据式（）动态控制烟花的爆炸半径可以有效提高烟花的搜索能力，如 果 烟 花 在迭代过程中没能找到适应性更好的火花，则说明此时爆炸半径太长，需要缩小爆炸半径以增大找到适应性更好的火花的可能性。相反，如果烟花 在迭代 过程中 产生 了适应性更好的火花，则说明当前搜索区域极大可能存在潜在最优解，放大搜索半径可以更好搜索此类搜索价值高的区域。（）烟花爆炸：烟花在第次迭代爆炸中产生个火花，其中第个火花产生方式如下 （）其中，表示随机选择的维度，表示烟花在第个维度的位置，表示区间，间的服 从均匀分布 的 随机变量。变异算子高斯变异是烟花算法中常用的变异方式，但是高斯变异容易导致烟花在原点附近陷入局部最优且很难跳出，因此为了避免这种情况，本文采取的是随机变异算子，变异烟花产生方式如下（）（）（）其中，、表示当前迭代中随机选取的两个烟花，表示区间，间的随机变量，分别为火花 中第个维度上的上下界。映射规则对于约束优化问题，需要将超出边界的火花映射到可行空间中。本文采用的是一种随机映射规则，当一个火花位于边界之外时，它将被一个从可行空间中均匀随机选取的新火花所取代，具体映射规则如下 （）（）选择策略传统的选择策略中，算法会从一个规模为的候选池（包括烟花、爆炸火花和高斯变异火花）中选择个个体作为新一代烟花。候选池中适应性最好的个体会被确定性地选择为新的烟花，而对于剩下的个烟花的选择采第 卷第期李克文，吴雪锋，王晓辉：基于排他策略和反思算子的协同烟花算法用轮盘赌的方法在候选池中进行选择。每次选择中所有烟花共享同一个候选池且只有核心烟花被确定性地选择为新的烟花，非核心烟花的优秀信息在选择过程中容易被忽视，导致核心烟花对优化的贡献远远超过了非核心烟花的贡献，算法容易陷入局部最优，难以跳出。本文采取的是独立选择策略，即 新 一 代 的每 个 烟 花都是从该烟花的独立候选池中选择的，该候选池仅包括自己的后代。每个烟火及其后代形成了一个单独的小种群，在每个独 立 小 种 群 的 选 择 中，采 用 精 英 选 择 机 制，选择每个种群中的最佳个体作为下一代烟花。与传统的选择策略相比，独立选择策略使烟花可以充分的继承和利用迭代 过 程 中 的 有 效 信 息，挖 掘 每 一 个 烟 花 的 搜 索价值。基于排他策略和反思算子的协同烟花算法烟花爆炸时会产生大量的火花粒子，但是传统的烟花算法仅仅考虑并选择其中适应性最好的火花作为下一代烟花，忽视了其他爆炸火花中所包含的宝贵信息，同时搜索过程中粒子搜索区域重叠会导致资源浪费、寻优速度变慢等问题。本文针对以上问题提出了基于排他策略和反思算子的协同烟花算法。反思算子烟花在一次爆炸中可以产生大量的火花粒子，这些粒子会落到不同的位置并表现出不同的适应性。传统的烟花算法会在这些粒子中选取表现最好的火花作为新一代的爆炸烟花来指导烟花的进化方向，但是对于其它表现好的甚至表现不好的火花粒子，传统的烟花算法并没有进行进一步的研究以及解释说明。在大部分纬度上适应性最好的火花都有着很好的表现，但是对于其余纬度则不然，这意味着仅仅根据适应性最好的火花个体指导烟花的进化方向会导致新一代烟花在继承了上一代的优秀信息的同时会继承一些低劣信息。与适应性最好的火花个体信息相比，本文认为适应性好的火花群体信息能够更加准确地指导烟花的进化方向。另外，适应性不好的火花群体信息同样存在为烟花的进化方向提供指导的能力，适应性不好的火花粒子表明烟花在当前爆炸方向找到优质解的可能性小，避免烟花落入当前爆炸方向则可以很好提高找到优质解的可能性。从人类依据正确以及错误的经验教训进行反思总结的社会行为中受到启发，为充分利用爆炸过程中产生的火花粒子的有效信息，本文在爆炸算子之后引入了反思算子，根据爆炸过程中烟花在正确和错误方向上产生的爆炸火花来构造反思向量，指导烟花寻找潜在优质解。烟花爆炸产生个火花粒子，根据适应度值对爆炸产生的火花粒子 进行排序后，选取其中个适应性最好的火花个体和最差的火花个体来构造反思向量并生成反思火花，过程如下 （）（）（）（）其中，是 控 制 构 造 反 思 向 量 的 爆 炸 火 花 数 量 的 参 数，表示烟花爆炸产生的适应性排序为的优异火花粒子，同理 表示烟花爆炸产生的适应性排序为的低劣火花粒子。由公式可以看出，构造反思向量时，优异火花群体的正确经验可以在继承上一代烟花的优秀信息的同时摒弃低劣信息，而低劣火花群体的错误经验可以有效避免烟花在进化过程中误入歧途。反思火花 可以有效利用爆炸过程产生的优异火花和低劣火花中的有效信息，指导烟花进化，提高找到优质解的可能性。公式中越大，反思向量涉及的爆炸火花数量越多，火花粒子的信息越能有效利用，反思算子找到最优解的可能性越高，但是涉及的计算成本也会相应增加，实验结果表明 时效果较好，在较少的计算成本下，可以有效提高烟花爆炸的局部搜索能力，加快搜索速度。协同搜索策略本文采取的独立选择策略可以有效避免算法陷入局部最优，使烟花可以充分继承和利用迭代过程中 的有 效信息，挖掘每一个烟花的搜索价值。但是同时独立选择策略将烟花种群从一个整体切分成多个独立的小规模烟花群体，各个独立烟花群体之间缺乏有效的信息交互，影响了烟花算法的全局搜索能力。本文提出了一种利用个体与优质粒子间的位置信息协同烟花进行搜索的方式来解决这个问题。烟花算法中，核心烟花即全局最优烟花在烟花搜索过程中有着重要的贡献，其所在的位置区域也有着更高的找到优质解的可能性。对于适应性差的非核心烟花，其所在的位置区域显然找到优质解的可能性较低。因此本文根据核心烟花的位置信息对适应性差烟花进行指导，协调烟花向具有高搜索价值的位置区域探索，提高烟花的搜索效率。协调方式如下 （），（），（）其中，和 分别表示当前烟花种群的烟花个体和核心烟花，表示当前烟花与核心烟花的适应性差异程度，按如下公式计算（）（）（）（）其中，为随机因子，是，间的随机数，和是按如下公式计算的系数向量计算机工程与设计 年（）（）其中，是随着迭代次数从递减到的收敛因子，和是，间的随机数。由公式可以看出，当 时，当前烟花的适应性差，其所在的位置区域找到优质解的可能性低，利用第一个式子可以协调烟花快速到达最优值附近，在高搜索价值区域进行探索，提高找到优质解的可能性；当 时，当前烟花适应性较好，利用第二个式子对当前烟花可以进行较小幅度的位置调整，使其逐步靠近最优值，寻找潜在最优解。当 时，当前烟花的适应性好，因此为充分发挥其搜索能力，对于此类烟花不对其进行调整。协同搜索策略可以保证烟花粒子间有效的信息交互，提高算法的全局搜索能力，提升算法的收敛速度。排他策略在传统烟花算 法的寻优过程 中，随 着 迭 代 次 数 的 进行，常常存在不同的烟花粒子搜索相同的优质解区域的情况。这种粒子搜索区域重叠的情况不仅导致了烟花搜索能力的浪费，还会造成算法无法跳出局部最优的问题。为解决上述问题，本文提出了一种基于标准化欧式距离的排他策略。当两个烟花粒子各个维度上的距离都比较相近时，才能认为出现了粒子搜索区域重叠的问题。因此，本文选择了标准化欧式距离来衡量烟花粒子的搜索区域重叠程度，其与尺度无关的特性可以避免烟花粒子上各个维度上尺度不一样带来的影响，计算公式如下（）（）其中，表示烟花和的标准化欧式距离，表示烟花，在第个维度的位置，表示烟花在第个维度上的标准差。如图（）所示，两个烟花的距离足够远，烟花、在不重叠的搜索区域内寻找优质解。这种情况下，烟花粒子的搜索能力可以被充分发挥，烟花的搜索效率最高，这是我们希望的。如图（）所示，两个烟花