第3期 刘长平，等：具有Ly飞行特征的蝙蝠算法 ·241· 的生物学特性，Yang曾提出一种基于随机优化的蝙 基于群体进化的算法，首先在可行解空间随机初始 蝠算法[)，该算法具有模型简单、收敛速度快、可并 化种群，即确定个体的初始位置和初始速度，其中位 行处理等特点，在工程设计中得到了初步应用 置用于表征问题解；进而通过评价群体，找出群体最 通过仿真，笔者发现基本蝙蝠算法存在易被局部极 优位置：然后，分别按式(1)和(2)更新个体的飞行 值吸引、发生过早收敛、后期收敛速度慢等问题 速度和位置： 本文基于蝙蝠觅食的特点，在分析原有算法优 =1+(x-x)·f, (1) 化机理和局限性的基础上，提出了一种蝙蝠优化算 x=x1+ (2) 法，在优化过程中采用Levy flight策略来模拟蝙蝠的搜 式中：分别表示蝙蝠i在t-1和t时刻的飞行 索捕食行为，更加贴近蝙蝠真实捕食过程，从本质上提 速度：x表示蝙蝠i在t时刻的空间位置，x·表示在 升了算法的优化性能采用基准测试函数对所提算法进 当前群体中最佳蝙蝠所处位置：为蝙蝠i搜寻猎 行仿真测试，并与基本蝙蝠算法、PS0算法进行对比， 物时使用的脉冲频率，f∈[f。∫]为搜索脉冲频 测试结果验证了所提算法的可行性和优越性， 率范围 1基本蝙蝠算法优化机理和局限 根据生物学机理可知，在搜寻猎物过程中，蝙蝠 初始阶段发出的超声波脉冲音强大而频度低，有助于 1.1算法仿生原理及数学模型 在更广泛的空间搜索，发现猎物后，就逐渐减小脉冲音 蝙蝠在搜寻猎物时，每秒发出大约10~20个、 强同时增加脉冲发射次数，以利于精确掌握猎物的空 音强达110dB的超声波脉冲，脉冲音强在搜寻猎物 间位置，故用式(3)和(4)来模拟这种搜索特点， 时最大，在飞向猎物时逐渐减小，同时脉冲频度逐渐 rt'=[1-exp(-y×t)], (3) 增加，达到每秒发射约200个脉冲.脉冲音强大有助 A+1=a×A (4) 于蝙蝠探测更远的距离，脉冲频度高有助于精确掌 式中：表示蝙蝠i的最大脉冲频度；表示在t+1 握猎物不断变化的空间位置.通过这套精巧的“声呐 时刻蝙蝠i的脉冲频度：y是脉冲频度增加系数，为 系统”，蝙蝠能够在黑暗的环境中躲避如发丝粗细 大于零的常数；4：表示t时刻蝙蝠i发射脉冲的音强：α 的障碍物且能捕食猎物. 是脉冲音强衰减系数，通常取[0,1]上的常数 蝙蝠在复杂环境中精确定位、捕食的情形为模 基本蝙蝠算法流程图如图1所示，其中R,、R, 拟其生物学机理进行优化带来了启发，蝙蝠算法是 是随机生成数 初始化种群，找出最住蝙蝠个体 用新位置替换先前位置 更新速度和位置 新位置优于当 R<r N 新位置由当 前最佳位置 前最佳位置 扰动产生 Y 接受更新后位置 当前最佳 替换当前最佳位置，调器 位置不变 脉冲频度r和脉冲音强A 评估新位置 满足要求 N 新位置优于先前位 Y 置并且R<A, 输出结果 IN 原位置不变 图1基本蝙蝠算法流程 Fig.1 Procedure of original bat algorithm 1.2基本蝙蝠算法的局限性 1)算法缺乏变异机制，种群不易保持多样性.群 根据基本蝙蝠算法的优化机理，发现算法在两 智能算法是否高效，重要一点就是要具备优良的变 方面存在固有不足： 异机制，维持种群多样性，从而保持持续进化能力的生物学特性，Ｙａｎｇ 曾提出一种基于随机优化的蝙 蝠算法［５］ ，该算法具有模型简单、收敛速度快、可并 行处理等特点，在工程设计中得到了初步应用［６⁃７］ ． 通过仿真，笔者发现基本蝙蝠算法存在易被局部极 值吸引、发生过早收敛、后期收敛速度慢等问题． 本文基于蝙蝠觅食的特点，在分析原有算法优 化机理和局限性的基础上，提出了一种蝙蝠优化算 法，在优化过程中采用 Ｌéｖｙ ｆｌｉｇｈｔ 策略来模拟蝙蝠的搜 索捕食行为，更加贴近蝙蝠真实捕食过程，从本质上提 升了算法的优化性能．采用基准测试函数对所提算法进 行仿真测试，并与基本蝙蝠算法、ＰＳＯ 算法进行对比， 测试结果验证了所提算法的可行性和优越性． １ 基本蝙蝠算法优化机理和局限 １．１ 算法仿生原理及数学模型 蝙蝠在搜寻猎物时，每秒发出大约 １０ ～ ２０ 个、 音强达 １１０ ｄＢ 的超声波脉冲，脉冲音强在搜寻猎物 时最大，在飞向猎物时逐渐减小，同时脉冲频度逐渐 增加，达到每秒发射约 ２００ 个脉冲．脉冲音强大有助 于蝙蝠探测更远的距离，脉冲频度高有助于精确掌 握猎物不断变化的空间位置．通过这套精巧的“声呐 系统”，蝙蝠能够在黑暗的环境中躲避如发丝粗细 的障碍物且能捕食猎物． 蝙蝠在复杂环境中精确定位、捕食的情形为模 拟其生物学机理进行优化带来了启发，蝙蝠算法是 基于群体进化的算法，首先在可行解空间随机初始 化种群，即确定个体的初始位置和初始速度，其中位 置用于表征问题解；进而通过评价群体，找出群体最 优位置；然后，分别按式（１）和（２）更新个体的飞行 速度和位置： ｖ ｔ ｉ ＝ ｖ ｔ－１ ｉ ＋ （ｘ ｔ ｉ － ｘ ∗ ）·ｆ ｉ， （１） ｘ ｔ ｉ ＝ ｘ ｔ－１ ｉ ＋ ｖ ｔ ｉ ． （２） 式中：ｖ ｔ－１ ｉ 、ｖ ｔ ｉ 分别表示蝙蝠 ｉ 在 ｔ－１ 和 ｔ 时刻的飞行 速度；ｘ ｔ ｉ 表示蝙蝠 ｉ 在 ｔ 时刻的空间位置，ｘ ∗ 表示在 当前群体中最佳蝙蝠所处位置；ｆ ｉ 为蝙蝠 ｉ 搜寻猎 物时使用的脉冲频率，ｆ ｉ∈［ ｆｍｉｎ ，ｆｍａｘ ］为搜索脉冲频 率范围． 根据生物学机理可知，在搜寻猎物过程中，蝙蝠 初始阶段发出的超声波脉冲音强大而频度低，有助于 在更广泛的空间搜索，发现猎物后，就逐渐减小脉冲音 强同时增加脉冲发射次数，以利于精确掌握猎物的空 间位置，故用式（３）和（４） ［５］来模拟这种搜索特点． ｒ ｔ＋１ ｉ ＝ ｒ ０ ｉ ［１ － ｅｘｐ（ － γ × ｔ）］， （３） Ａ ｔ＋１ ｉ ＝ α × Ａ ｔ ｉ ． （４） 式中：ｒ ０ ｉ 表示蝙蝠 ｉ 的最大脉冲频度；ｒ ｔ＋１ ｉ 表示在 ｔ＋１ 时刻蝙蝠 ｉ 的脉冲频度；γ 是脉冲频度增加系数，为 大于零的常数；Ａ ｔ ｉ 表示 ｔ 时刻蝙蝠 ｉ 发射脉冲的音强；α 是脉冲音强衰减系数，通常取［０，１］上的常数． 基本蝙蝠算法流程图如图 １ 所示，其中 Ｒ１ 、Ｒ２ 是随机生成数． 图 １ 基本蝙蝠算法流程 Ｆｉｇ．１ Ｐｒｏｃｅｄｕｒｅ ｏｆ ｏｒｉｇｉｎａｌ ｂａｔ ａｌｇｏｒｉｔｈｍ １．２ 基本蝙蝠算法的局限性 根据基本蝙蝠算法的优化机理，发现算法在两 方面存在固有不足： １）算法缺乏变异机制，种群不易保持多样性．群 智能算法是否高效，重要一点就是要具备优良的变 异机制，维持种群多样性，从而保持持续进化能力． 第 ３ 期 刘长平，等：具有 Ｌéｖｙ 飞行特征的蝙蝠算法 ·２４１·