基于多种群多策略的竞争粒子群算法.pdf

云南民族大学学报（自然科学版），（）：收稿日期：基金项目：辽宁省教育厅项目（、）作者简介：李媛媛（），女，博士，副教授 主要从事智能算法、人工智能研究基于多种群多策略的竞争粒子群算法李媛媛，李文博，尚志豪（大连交通大学 软件学院，辽宁 大连 ）摘要：针对标准粒子群算法遇到的易陷入局部最优、收敛差、求解精度低等问题，提出了多种群多策略竞争粒子群优化算法 新算法将每一代粒子根据适应度排序，将其划分为不同的子种群，并引入非线性 混沌映射权重、收缩因子和混合高斯 柯西扰动机制来更新这些子种群 使用不同的粒子更新方式平衡了算法整个时期的全局搜索和局部开发能力，从而加快了收敛速度最后，将多种群多策略竞争粒子群优化算法与标准粒子群算法和其它优化算法在 个测试函数上进行对比，结果表明，新算法在跳出局部最优解、和寻优精度方面显著优于标准粒子群算法，且有更快的收敛速度 在寻优能力和算法稳定性上大幅度强于其它对比算法关键词：种群划分；多策略；混合变异；混沌映射中图分类号：文献标志码：文章编号：（）粒子群优化算法是一种基于群体智能的优化算法，它通过模拟智能群体中每个个体的行为来解决优化问题 主要应用在工程设计 、控制工程 、路径规划 、计算机视觉 等方面 文献 为了在锻坯过程中找到最佳的工艺参数，改善传统数值模拟方法的不足，采用粒子群算法对参数进行优化，从材料本身和锻压成形节能的角度出发，采用该算法找到最合适的参数结果 文献 使用非线性 （）控件取代了传统的 控件，提出了一种基于广义对立学习算法的粒子群优化算法来优化 控制器，成功抑制了系统超调 文献 提出了一种灵活的卷积自编码器，利用粒子群优化设计了一种架构发现方法，该方法能够自动搜索所提出的柔性卷积自编码器的最优架构，无需任何人工干预，大大减少计算资源，解除了传统卷积自编码器对卷积层和池化层数量的禁锢，并证明了加入粒子群算法后的新的图像分类算法远优于其他同类算法标准粒子群优化算法（，）最初由 和 等 在 年提出，它拥有惯性权重，是为了解决原始 算法易陷入局部最优值而进行的改进 带有压缩因子的粒子群优化算法在 年由 等 提出，目的是在帮助粒子跳脱局部最优值的同时加快整个优化过程的收敛速度 这两种改进方式是针对原始 最经典的改进方法 其他的改进算法通常都是在此基础上进行改进，方法包括：改变粒子拓扑结构、与其他算法结合、引入新的机制、或是对参数进行修改 例如：为了克服传统的 最优前沿形状变化分解方法的不稳定性，等 提出了种基于对抗分解和邻域演化的动态多目标粒子群优化算法；针对存在多个 最优解且适应度值相同的多模态多目标优化问题，等 提出了一种具有自组织机制的多目标粒子群优化算法；等 通过将强化学习算法与粒子群算法结合起来，得到了自适应参数；为了使算法寻优过程中更轻松地跳出局部最优值，徐利锋等 在带有收缩因子的粒子群算法基础上引入了多级扰动机制粒子群优化算法的优势在于它可以快速收敛到最优解，同时具有较好的全局搜索能力 在众多应用中，粒子群优化算法已经取得了良好的效果，但是在实际应用中还是会出现易陷入局部最优 、收敛性差 、求解精度低 等问题 为了减少这些问题对算法的影响，作者对标准粒子群算法进行改进，提出基于 混沌映射权重及混合高斯、柯西扰动变异，同时使用了收缩因子的多种群多策略竞争粒子群算法（，）为了获得比标准粒子群算法更好的寻优性能，作者将每一代的粒子群划分为不同的子种群，并使用不同的更新机制来更新这些子种群，从而使粒子的全局搜索能力和局部开采能力在寻优过程中达到平衡 标准粒子群算法在粒子群算法中，每个粒子的位置代表了给定问题的潜在解决方案，并使用适应度函数来评判当前位置的优劣 群体中的粒子会通过信息共享机制来更新自身的速度和位置，从而更新整个群体 群体在迭代过程中不断追寻最优粒子，在解空间内进行搜索运动，从而逐渐从无序向有序演变，最终达到在限制条件内求得待解决问题的帕累托最优解的目的粒子速度和位置更新公式：（）（）（）（）（）（）（）（）（）（）（）其中，（）表示第 代粒子 在第 维度上的速度，（）部分表示上一代历史速度对当前速度的影响，惯性权重 用来调节此影响的大小，从而调节粒子在解空间的搜寻范围，使粒子全局搜索和局部开采能力达到平衡（）（）为粒子的自我认知部分，（）（）为社会认知部分 （），（）分别为粒子的个体历史最优位置和全局历史最优位置 加速度因子，分别用来调节粒子向自己历史最优位置和全局最优位置学习的步长 随机数，都取值 ，内，用以增加粒子搜索的随机性 改进的粒子群算法 标准 寻优过程一直伴随着局部搜索能力不够强，搜索精度差，处理复杂非线性多峰问题常陷入局部最优等问题 为了摆脱这个困扰，根据同代种群粒子的适应度值将粒子分别划为 个子种群：优等子群（）、普通子群（）、劣等子群（）；针对不同子种群粒子的特点分别加入扰动变异、混沌映射、收缩因子 种不同策略来进行粒子的更新；不同子种群产生的新一代粒子通过参与适应度值竞争排序后，更新到不同的子种群；算法中的每个子种群会通过粒子更新公式，不同程度的参与引领整个种群更新 不同于标准 的所有粒子只对本身历史最优和全局历史最优进行追逐，这种新的更新策略使整体算法寻优全程拥有较强的全局和局部寻优能力并兼具了易跳出局部最优、保持种群多样性的特性，弥补了标准 的不足 下面将详细介绍 的种群划分方式和不同子种群的更新策略 种群划分以求最小值问题为例，在 中，每一代的所有粒子按照适应度从低到高进行竞争排序后，求得当代种群适应度的平均值和标准差 在求最小值的优化问题中：取平均适应度一倍标准差内的粒子组成普通子群；取适应度值小于普通子群的粒子组成优等子群；取适应度值大于普通子群的粒子为劣等子群 劣等子群向优等子群和普通子群两个子群按照合理的权重学习更新，尽快向两个区域靠拢；普通子群使用带有 惯性的更新公式，平衡普通子群粒子的全局和局部探索能力适应度平均值和标准差的计算公式如下：（）（槡）（）其中，第 个粒子的适应度值为，粒子个数为 ，适应度值的平均值为，适应度值的标准差为 粒子按适应度排序后，子种群划分方式如图 所示 优等子群更新策略优等子群粒子已经获得了较优的适应度值，所以优等子群进行自我学习更新 同时，该种群粒子聚集在局部最优解附近 为了避免陷入局部最优，同时又使粒子具备好的局部寻优能力，作者设计了带有局部开发能力强的高斯变异和具有两翼分布概率且更易跳出局部最优的柯西变异的粒子更新方式云南民族大学学报（自然科学版）第 卷?/Kiff+i+InferiorsOrdinariesSuperiorsff f图 子种群划分方式高斯 柯西变异算子 定义式：（），（）（，）（，）（，）（）（，）（，）()()（）优等子群粒子更新公式：（）（）（）（）（）其中，表示优等子群中的粒子 在第 维度上的位置 为高斯 柯西变异算子，是根据公式（）产生的服从高斯分布的随机数，是根据公式（）产生的服从柯西分布的随机数 为预设的种群最大迭代次数，为当前种群迭代次数 通过 和 求得的 为控制变异步长的自适应参数，在优等子群的早期迭代中，使用较大的变异因子，较容易让粒子拜托局部最优；反之，在迭代后期，缩小变异因子的取值，会加速算法收敛根据公式（），随着迭代次数的增加，自适应参数 会变小 作者通过使用自适应变异步长 来平衡当前种群粒子的开发和探索能力 劣等子群更新策略劣等子群中的个体通过主要向优等子群学习，兼顾受种群中心平均值牵引的方式更新 采用收缩因子对整个更新过程进行压缩，使劣等子群的粒子能快速脱离劣势区域向优势区域收敛，同时又能对各个学习因子进行调节，均衡了该阶段算法的收敛性能，避免在快速靠近优等子群的过程中丧失了开发能力收缩因子 定义式：，（）槡（）劣等子群更新公式：（）（）（）（）（）（）其中，表示劣等粒子的位置、分别为劣等粒子向自身、优等子群和种群平均值的学习因子 调整 个学习因子的参数值可以控制粒子对不同引导部分学习的权重，在这部分需设置较大的 值，达到主要向优等种群学习的意图 设置收缩因子 将学习因子控制在合理范围内，为了避免部分学习因子或全部学习因子设置过大，破坏了收敛的平衡性 普通子群更新策略普通子群粒子处于解空间合理位置范围内，无明显优劣势，该子群进化过程中需要平衡算法的勘探和开采能力 算法使用的线性递减权重 在一定程度上平衡了粒子的全局探索和局部开发，但线性的调整方式在多维复杂非线性函数的优化过程中常陷入局部最优 混沌映射作为非线性映射方式的一种，其产生的随机序列具有良好的空间便利性 因此，作者在 算法基础上对权重 加入 混沌映射，用非线性权重 对粒子的速度进行更新，使算法搜索能力均衡的同时又能很好地遍历解空间，不易陷入局部最优 混沌映射惯性权重 定义式：（）（）（），（）（，）且 （），（）（）（）（）（）普通子群粒子更新公式：（）（）（）（）（）（）（）（）（）（）（）（）式（）中，等于 ，等于 为普通子群粒子 在第 维上的速度，为普通子群中粒子 在第 维上的位置 基于混沌映射的惯性权重 随迭代次数的变化如图 所示第 期李媛媛，李文博，尚志豪：基于多种群多策略的竞争粒子群算法图 惯性权重随迭代次数变化图 实验 标准函数测试选取 个基本测试函数与标准粒子群算法从寻优精度、寻优速度，跳出局部最优的能力等方面进行比对，来验证 算法的有效性 个标准测试函数的基本信息由表 给出，为函数最优值 函数 是用来测试算法寻优的快慢和所得解优劣的单峰函数，函数 为测试算法跳出局部最优，避免过早收敛的能力的多峰函数 算法性能测试将 与 进行对比实验，给予 种算法相同的种群大小 和最大迭代次数 ，令二者在一个 维的解空间内对 个基本测试函数进行最小值寻优 在相同的硬件条件下，运行两个算法 次，记录两种算法 次的寻优结果，分别求取平均值（）和标准差（，）作为评价算法性能的指标 算法参数设置见表 种算法对基本测试函数的寻优结果见表 表 个标准测试函数 ，()，（）（），（），槡()()，（），槡()，（）（）（）（）（，），（），（，）（），（），云南民族大学学报（自然科学版）第 卷 （）（）（）（）（，），（），（，）（），（），表 各算法参数表 ，表 种算法求解 个标准测试函数适应度的平均值和标准差 绘制出 和 在求解 个标准测试函数时的适应度曲线，以便更直观的对比观察 种算法的求解精度和收敛速度，如图 、图 、图 所示（）（）（）（）图 各算法 函数寻优适应度曲线第 期李媛媛，李文博，尚志豪：基于多种群多策略的竞争粒子群算法（）（）（）（）图 各算法 函数寻优适应度曲线（）（）（）图 各算法 函数寻优适应度曲线从表 可知，在标准测试函数 、上 算法的寻优精度较 算法有着明显的数量级优势，在剩余的测试函数上新算法求得适应度的平均值也更接近函数本身的最优值 从图 、图 、图 中各个测试函数的适应度曲线可以看出新算法收敛速度更加迅速，又得益于变异机制和混沌映射惯性权重，跳出局部最优解的能力也更强 对比实验为了证明 算法的优越性，将其与 种典型的 变体进行比较，包括自适应惯性权重的全局 （）、动态维度自适应 （）和局部竞争 （）具体的参数设置如表 所示 为确保用不同算法进行实验比较的公正性，测试函数的维度 设置为 ，种群规模 设置为 ，最大迭代次数 设置为 ，每个算法独立运行 次表 给出了 算法和当前 种 在 个基准测试函数上的性能比较结果表 算法参数表 ，实验结果分析：）算法寻优能力 将 算法与 、个算法在多个单峰、双峰函数下云南民族大学学报（自然科学版）第 卷进行测试，算法表现极佳 无论是在单峰测试函数、，还是多峰测试函数、上，其求得的 值比其它算法更接近测试函数的最优值 这说明该算法寻优能力出众）算法稳定性 在性能评价指标中的 值也远小于其它算法，这说明 算法性能稳定 美中不足的是在 和 上 算法的表现都不如 算法表 不同算法性能比较 对比标准 结语设计了 种可以根据不同子种群状况，采用不同更新策略的改进粒子群算法 利用竞争学习机制和收缩因子加快了劣等子群学习速度；通过引入融合的变异算子和使用自适应变异步长增大了优等子群中粒子局部开发能力和跳出局部最优的概率值；加入 混沌映射惯性权重令普通子群更好地遍历解空间 新的更新策略有效地避免种群在优化单峰、多峰问题时早熟收敛和无法跳出局部最优解改进后的算法在 个标准测试函数上的优化表现表明采用不同子种群不同更新策略能够有效取得探索和开发能力的最佳平衡 下一步的目标是将该算法引入到深度学习中，帮助神经网络模型选取优秀的初始权重和高效的网络结构模型参考文献：，：，：，：，第 期李媛媛，李文博，尚志豪：基于多种群多策略的竞争粒子群算法 ，（）：，：，（）：，：，：，（），：徐利锋，黄祖胜，杨中柱，等引入多级扰动的混合型粒子群优化算法 软件学报，（）：，（）：，（）：，：，（）：，：，（），：韩红桂，卢薇，乔俊飞一种基于种群多样性的粒子群优化算法设计及应用 信息与控制，（）：宋美，葛玉辉，刘举胜基于协同进化的动态双重自适应改进 算法 计算机工程与应用，（）：（），（）：，（，）：（），：；（责任编辑段鹏）云南民族大学学报（自然科学版）第 卷