多方向螺旋搜索的混沌海鸥优化算法_张冰洁.pdf

小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家自然科学基金项目（）资助；贵州省省级科技计划项目（黔科合 字）资助；贵州省科技计划项目重大专项项目（黔科合重大专项字，）资助；贵州省公共大数据重点实验室开放课题项目（）资助；贵州省教育厅青年科技人才成长项目（黔科合 字）资助；贵州大学培育项目（黔科合平台人）资助 作者简介：张冰洁，女，年生，硕士研究生，研究方向为进化算法、数据融合；何 庆（通讯作者），男，年生，博士，副教授，研究方向为进化算法、大数据应用；戴松利，男，年生，硕士研究生，研究方向为材料模拟、数据可视化；杜逆索，男，年生，博士，讲师，研究方向为仿真模拟、数据分析、人工智能等多方向螺旋搜索的混沌海鸥优化算法张冰洁，何 庆，戴松利，杜逆索（贵州大学 大数据与信息工程学院，贵阳）（贵州大学 贵州省公共大数据重点实验室，贵阳）：摘 要：针对海鸥优化算法（）寻优路径单一、寻优精度较低、易陷入局部最优等问题，提出新的多方向螺旋搜索的混沌海鸥优化算法（）首先，利用混沌序列对海鸥种群进行初始化，令海鸥个体分布更加均匀，能够更加准确地接近目标；其次，让海鸥选择不同方向的螺旋飞行路径，使海鸥飞行路径不再单一，增加算法多样性；最后，根据算法收敛情况进行围绕目标的小范围搜索，避免算法过早收敛，提高算法跳出局部最优的能力 本文选取了 个基准测试函数对算法进行了实验，以不同角度对于算法的性能进行测试，并使用 秩和检验来证明算法的性能，结果表明了 算法改进在寻优能力、稳定性、鲁棒性等方面均有提升关 键 词：海鸥优化算法；混沌映射；螺旋搜索；元启发算法中图分类号：文献标识码：文 章 编 号：（），（，）（，）：（），（），；，；，：；引 言近些年来，越来越多的学者受到自然界动植物的启发，模拟动植物的行为提出优化算法，例如群智能算法中蝴蝶优化算法（，），樽海鞘算法（，），萤火虫算法（，），秃鹰搜索算法（，）等，以及后来提出的人工蜂群算法（，）、黏菌优化算法（，）、蝠鲼觅食优化（，）随着算法的性能不断地改进，这些算法已经成功被应用到各种复杂问题的优化解决海鸥优化算法（，）是 和 在 年提出一种新的基于生物行为启发的元启发式算法 算法模拟了现实生活中海鸥的生活方式，通过模拟海鸥寻找迁移位置和攻击候鸟的两种行为，实现了算法全局搜索以及局部搜索的功能 算法的原理较为简单，也容易实现，目前已经用于解决一些工业问题以及分类问题 虽然 算法在一定方面上具有较大的优势，但由于算法搜索能力不足、海鸥行动路线较为单一，导致海鸥算法容易陷入局部最优解，收敛精度较差 针对上述问题，目前提出的解决方法有对算法加入莱维飞行的机制，通过增加海鸥飞行过程中的随机性来提升算法全局搜索的能力 文献中还提出了一种添加非线性递减的惯性权重来调整海鸥的飞行位置，使得算法能够能快地找到解上述改进方法对于 算法的收敛速度和精度都有一定程度上的改善，为了进一步提高 算法的寻优性能和收敛速度，本文提出了多方向螺旋搜索的混沌海鸥优化算法（）首先，算法加入了二维的 映射混沌初始化，使得初始海鸥个体位置分布更加均匀，使海鸥能够更快、更加准确的接近目标食物源；其次，提出多方向螺旋飞行路径，让海鸥接近目标食物源时不再是以前的单一轨迹，用不同的飞行路径交换进行，使海鸥能够探索更多的区域，增加算法的多样性；最后，根据算法收敛情况控制海鸥个体围绕目标小范围搜索，当算法适应度方差小于一定数值之后对目标进行小范围搜索，减慢算法收敛速度，提高算法跳出局部最优的能力本文选取了 个基准测试函数对算法进行了实验，以不同角度对于算法的性能进行测试，并使用 秩和检验来证明算法的性能，结果表明了 算法改进在寻优能力、稳定性、鲁棒性等方面均有提升 海鸥优化算法海鸥优化算法，是通过模拟海鸥最重要的迁徙和攻击两种行为模式提出的算法 海鸥是群居动物，根据季节的更替会大规模地从一个地方迁徙到另外一个地方，目的是为了寻找最丰富的食物 在迁徙的过程中海鸥个体之间为了不发生碰撞会飞行在不同的位置，在一个群体中，每一个海鸥个体都会朝着最丰富食物的位置移动，来改变自身的位置 为了取得更多的食物，海鸥常常会攻击其他的候鸟，海鸥迁移和攻击的行为可以用如下数学模型来描述 迁移在这个过程中，算法模拟了海鸥种群从原来位置移动到一个新的位置 这个阶段里，海鸥个体要满足以下的 个条件：）避免碰撞：（）（）（）()()（）其中（）表示不会和其他海鸥碰撞的新位置，（）表示海鸥攻击的位置，表示迭代的次数，表示最大迭代次数，用于控制 的频率，这里 取值为，控制 从 下降到）最佳位置方向：（）（）（）（）（）其中（）是当前海鸥的移动方向，（）是指当前海鸥个体找到的最优位置，是一个取值为（，）的随机数）靠近最佳位置：（）（）（）（）（）是海鸥移动到的新位置，是绝对值 攻击在这个过程中，算法模拟了海鸥攻击候鸟的行为 当海鸥进行攻击时，它们利用翅膀在空中以螺旋形状进行运动，模拟三维坐标，来对它进行描述，海鸥的攻击位置可以用以下公式表示：（）（）（）（）（）是指这一时刻海鸥攻击的位置（）是上一时刻海鸥的位置，（）是上一时刻海鸥个体找到的最优位置 （）（）（）（）（）（）其中 表示移动时的螺旋半径，是在（，）中随机取值的角度 而 和 是定义 的常数 多方向螺旋搜索的混沌海鸥优化算法 映射初始化原本的海鸥优化算法初始化是在上下界内随机生成海鸥个体的位置，这样的初始化可能会使海鸥在空间中位置分布得不均匀，导致算法早熟，陷入局部最优解 为了解决这一问题，本文提出基于 混沌序列的初始化形式由于混沌映射的随机性、遍历性等性质，可将其用于群智能算法种群的初始化中 其原理是利用混沌映射产生的在，之间的序列，再根据混沌因子对海鸥种群进行初始化这样可以控制海鸥在最初的分布更加合理，避免早熟 映射的数学模型由式（）给出：（）|（）当 时，系统会呈现短周期状态，故本文中 的取值范围是（，）利用混沌映射初始化的模型由式（）给出：（）（）其中，与 分别代表自变量取值的下限和上限 为 映射函数产生的混沌因子图 初始化分布图 图（）和图（）分别给出了在（，）范围内，随机初始化和利用 序列初始化的分布图，可以看出图（）中种群在取值的边界处分布较为密集，而在中间地带则较为稀疏，图（）中种群分布则较为均匀利用混沌序列优化算法时，最初考虑 映射，但 映射并不是最好的 利用 映射初始化的序列在，范围内呈切比雪夫分布，从整体上来看，搜索盲区较 期 张冰洁 等：多方向螺旋搜索的混沌海鸥优化算法 大 本文采取 映射进行初始化 映射具有更好的遍历性，可以克服 映射的缺点，使初始化更加均匀图 为在 函数的测试下，海鸥算法利用随机初始化、初始化以及 初始化之后的收敛曲线 函数的最优值为，实验迭代次数为 可以看出，利用混沌序列初始化之后的算法收敛性均强于随机初始化，而利用 初始化在迭代 次以后的精度就明显强于利用 初始化 利用 序列进行初始化之后，海鸥个体的分布更加均匀，能够更加准确地接近目标，增加了算法的多样性图 初始化收敛曲线 多方向螺旋飞行路径在初始的海鸥算法中，攻击阶段的位置更新方式如按照公式（）所示 从式中可以看出，海鸥在经过迁移过后，基于迁移过后的位置依照给定的行动模型寻找攻击位置 由于行动模型单一化，海鸥移动时存在飞行死角，导致有可能错过最优位置 即搜索过程中找不到最优值，只能找到局部最优值的情况 为解决这一问题，本文提出以下这种新的海鸥攻击位置更新方式（）（）（）（）（）（）其中 是在（，）之间的随机数，为海鸥选择更新方式的阈值，在多次实验之后得出取值为 最为合适，此时（）为适应多方向螺旋的海鸥迁移位置，如式（）所示：（）（）（）（）（）、（）、（）含义已在海鸥优化算法中介绍过经过改进的位置更新方式让海鸥根据阈值选择攻击方式，两种不同的攻击方式使海鸥的飞行轨迹不再单一，能够搜索更多的区域 两种不同攻击方式交替进行，缩小了海鸥飞行死角，减少了飞行盲区 以不同的方式，可以得到不一样的结果，即以不同的角度更新最优值，增加了算法的多样性 根据收敛情况进行小范围搜索基于原始的海鸥算法存在易陷入局部最优值这一问题，本文提出一种新的位置更新机制 在每次迭代时计算种群中海鸥适应度的方差，根据方差的大小来判断是否围绕目标位置进行小范围的搜索 具体数学表达如式（）和式（）所示：（）（）其中 表示方差，为海鸥的种群数量，（）为第 个海鸥种群的适应度，为海鸥种群的平均适应度，为种群中的最优适应度，为种群的最差适应度当 时，为了避免算法过快收敛，新的位置更新公式如式（）所示：（）（）（）（）其中（）表示上一次迭代时的位置，为在（，）区间内服从正态分布的随机数图 阈值 收敛曲线 图 为在 函数的测试下，海鸥算法根据不同阈值 进行小范围搜索的收敛曲线，函数的最优值为，实验迭代次数为 由图 可以看出，加入小范围搜索后，算法精度明显高于加入之前，而当阈值 取 时，有最好的搜索效果 故当迭代过程中海鸥适应度方差小于 时，海鸥进行围绕目标的小范围搜索 每个海鸥个体利用正态分布模型，围绕前一刻的位置进行小范围搜索 在搜索的过程中，若发现比之前寻找的最优解更好的解，即重新更新最优解的值，再根据新的适应度值方差判断是否再次进行小范围搜索 这样的位置更新机制增加了算法的多样性，减慢算法收敛过程，避免算法陷入局部最优值，增强了算法跳出局部最优解的能力 算法本文提出的 算法将海鸥种群进行 初始化，对初始化后的海鸥种群进行迁移与多方向地攻击，更新海鸥位置，再根据方差判断是否进行小范围搜索 算法在增加了上述改进后，增加了算法多样性，提高了算法跳出局部最优的能力 多方向螺旋搜索的混沌海鸥优化算法的流程图可见图，算法的伪代码如下：算法 设置初始参数：种群规模，最大迭代次数，需要测试的函数 初始化种群，计算个体适应度 设置初始参数：种群规模，根据式（）更新海鸥迁移位置 根据式（）计算方差 ：根据式（）更新海鸥攻击位置 ：根据式（）更新海鸥攻击位置 根据式（）更新海鸥迁移位置 小 型 微 型 计 算 机 系 统 年 图 多方向螺旋搜索的混沌海鸥优化算法流程图 时间复杂度计算算法的时间复杂度可以表示算法运算的速度，从而反应算法的效率 若改进算法的过程中增加了时间复杂度，会让算法效率变低，这是不利于计算的，故本文在此计算算法改进前后的时间复杂度标准 算法需要计算：随机初始化参数（），计算算法初始适应度（），迭代计算函数最优值（），则整个算法所需的时间复杂度为：（）（）（）（）（）这里的 为种群大小，为迭代次数经过改进之后的 算法需要计算：混沌初始化参数（），计算算法初始适应度（），迭代计算最优值（），混合策略更新位置（），方差判断小范围搜索（），则整个算法所需的时间复杂度为：（）（）（）（）（）（）（）文献中的 算法对于 算法的优化改变了惯性权重（），增加了莱维飞行机制（），故 算法所需的时间复杂度为：（）（）（）（）（）（）（）由此可得，本文改进后的算法 时间复杂度（）与改进之前的 算法时间复杂度（）以及文献改进的 算法时间复杂度（）相同，没有增加，故 算法的改进对算法计算的效率并未产生负面影响 实验仿真与分析 实验环境和参数设置本文实验的运行环境为 位 操作系统，处理器是 ，使用的软件是 本文的实验引入了 个经典测试函数，如表 所示 其中 为单峰函数，函数的局部最优值就是函数的全局最优值，通常用于检测算法的收敛速度和寻优精度；为多峰函数，这些函数存在多个局部最优值，通常用于测试算法跳出局部最优值和对全局进行探索的能力表 测试函数 编号函数名定义域理论值，验证本文算法有效性为了验证本文算法的有效性，本文选择了 种不同的优化算 法：贝 叶 斯 优 化 算 法（）、灰 狼 优 化 算 法（）、鲸鱼优化算法（）来与未经改进的海鸥优化算法（）以及本文提出的改进算法 进行试验 为了降低实验偶然性，对每个测试函数均进行 次独立实验后，取实验结果的最优值、平均值和标准差进行对比本次实验时所设置的参数有：种群规模 ，最大迭代次数，空间维度