0 引言

蝙蝠算法^[1-3]是基于蝙蝠超声定位的智能优化算法.目前蝙蝠算法已经被广泛应用于各种约束和非约束优化问题, 如航迹规划^[4]、TSP问题^[5]、函数优化^[6]、视觉追踪^[7].相比传统进化算法, 蝙蝠算法具有较高的进化效率、较好的鲁棒性能, 其中文献[8]提出一种改进的蝙蝠算法用于优化神经网络模型, 蝙蝠个体保留当前最优解和最优路径, 并依据历史最优解、当前最优解和当前位置的多种线性组合更新速度, 同时在进化算法中采用分段线性混沌和Logistic混沌, 便于算法进行局部开采.文献[9]提出一种改进的自适应蝙蝠算法, 引入了交叉和变异方式, 同时对参数进行了自适应设计.文献[10]提出一种混合多目标蛙跳蝙蝠算法, 将蛙跳算法与蝙蝠算法进行有效的融合, 并应用于不同电力负载下的电力单元布局和规模问题.文献[11]在蝙蝠算法中融入了杂草算法与遗传算法, 利用遗传算法的变异和交叉对个体进行操作, 并依据轮盘赌方式选择个体.通过对蝙蝠算法的研究和分析, 当前对其主要改进方式可概括为:

1) 引入局部寻优算子和搜索方式, 如将遗传进化中的交叉和变异^{[9, 11]}引入蝙蝠算法中, 在速度和位置的更新过程中引入Levy飞行.

2) 与其他算法的有机融合, 引入蛙跳算法^[10]、遗传算法和杂草算法^[11]等优化算法.

3) 通过寻优结构和种群规模的调整, 利用多种群协同进化方式, 提高种群和个体之间的协同性能.如文献[12]提出利用两个种群协同分工进行勘探和开采的操作; 文献[13]提出多种不同的种群协同结构, 提高蝙蝠算法的进化能力.

由蝙蝠算法的基本特性和相关改进情况可以看出, 蝙蝠算法作为一种新兴仿生进化算法, 不可避免地会出现陷入局部极值, 无法收敛到全局最优解等缺点.尽管蝙蝠算法已经有了诸多改进版本, 并且算法性能也有了一定程度的提高, 但自始至终采用单一的进化结构, 往往不能满足进化需求, 同时算法局部搜索能力也有待提高.因此, 为提高蝙蝠算法的进化能力, 本文提出一种进化框架结构可变的自适应协同进化蝙蝠算法(Adaptive cooperation evolutionary bat algorithm, ACEBA), 依据种群多样性适时变换种群进化结构, 在不同的种群内部采用了相应的速度和位置更新方式, 并采用参数自适应方法, 从全局和局部搜索方式提高蝙蝠算法的进化能力.

1 基本蝙蝠算法及其特性分析

在蝙蝠算法中, 包含3个重要的因素, 分别是搜索脉冲频率、脉冲音量和脉冲频度.在d维搜索空间中, 第i只蝙蝠在t时刻的位置和速度分别为x_i^t和v_i^t, t+1时刻的位置和速度为

(1)

(2)

(3)

其中: f_max、f_min和f_i分别表示第i只蝙蝠在t时刻声波的最大频率、最小频率以及当前的频率; β为[0, 1]区间范围内的随机数; x^*为当前的最优值.

从当前的最优解集中选定某个优良个体后, 该蝙蝠个体位置的更新可以按照下式进行:

(4)

其中: x_old表示从当前最优解集中选出的优良个体; A(t)表示t时刻所有蝙蝠个体的平均响度; ε为d维随机变量, ε∈[-1, 1].

随着迭代过程的进行, 音量和脉冲频度会实时更新.通常在靠近猎物的过程中, 音量会逐渐降低, 脉冲发射的频度会逐渐增高, A_i=0时意味着蝙蝠i刚刚找到一只猎物, 暂时停止发音, 更新方程可以按照下式进行:

(5)

(6)

其中: 0 < α < 1, γ>0, 且均为常数.可以看到, 当t→∞时, A_i^t→0, R_i^t→ R_i⁰.

由当前蝙蝠算法的研究现状和基本特性可以看出, 虽然蝙蝠算法已经有了较多的改进方法, 但蝙蝠算法进化方式单一, 进化性能有待提高, 其存在的主要问题可以概述为:

1) 传统蝙蝠算法往往是单一种群进化, 无法有效地进行勘探和开采的协调, 当发现优良解集时, 不能保证算法在进化过程中始终在优良解区域进行开采;

2) 缺少局部搜索方式, 从而导致种群多样性降低, 使得算法易陷入局部极值, 响度和脉冲频率以一定概率决定了更新位置, 但不可避免地受到局部极值吸引, 导致缺乏深度开采能力;

3) 参数的更新方式往往是固定不变或者线性变化的, 使得蝙蝠算法在搜索进化过程中缺乏灵活性, 不能根据当前种群进化过程动态调整, 无法保证种群具有良好的多样性.

由于基本蝙蝠算法存在诸多缺点, 使得算法寻优性能不高, 不可避免地容易陷入局部极值, 为此本文提出一种自适应协同进化蝙蝠算法(ACEBA).下面详细阐述算法流程.

2 自适应协同进化蝙蝠算法 2.1 搜索结构自适应变化

传统的蝙蝠算法, 往往采用单一种群, 进化方式单一, 不能实现个体之间的协同进化.为了有效提高种群进化的多样性, 增强算法的全局勘探和局部开采的能力, 避免算法采用单一种群陷入局部极值问题, 本文提出一种多种群协同的蝙蝠算法.将蝙蝠种群划分为主种群和子种群, 其进化结构如图 1所示.

在图 1的进化结构中, 主种群为M, 子种群分别设定为E₁、E₂和E₃, g₁、g₂和g₃分别表示每个子种群的最优值, 各子种群将最优个体与主种群进行交流.但是, 如果进化过程中都采用同样的框架结构, 即采用图 1所示的集中式结构, 虽然能保证全局勘探能力的提高, 但无法有效地发挥局部开采能力, 限制了算法的寻优性能, 无法保证算法具备较高的进化效率.为有效提高进化过程中各种群的小生境进化能力, 种群结构可在集中式结构与分布式结构之间适时进行切换, 其中分布式结构如图 2所示.

本文提出种群结构能够在图 1所示的集中式结构与图 2所示的分布式结构之间实现搜索框架的切换.结构的自适应切换^[12]可以有效地实现勘探和开采性能的统一.各个子种群分别进行独立进化, 有效地提高了主种群的全局勘探能力.由于将每个子种群单独进行进化, 提高了进化种群的进化速度, 有效地加强了种群的开采能力.以下详细阐述种群进化结构切换的依据和方法.

1) 集中式结构向分布式结构转换.

集中式进化结构向分布式进化框架切换的依据是将分布熵作为判断准则.分布熵可以有效度量种群进化的多样性.以往较多文献利用方差度量种群多样性, 与方差度量种群多样性进行对比发现, 当少数个体明显偏离群体多样性时, 方差不能有效地度量该多样性, 而其在多模态的情况下, 方差和种群多样性往往并不一致.在协同进化框架结构中, 种群规模为N, 主种群和3个子种群的个体数目分别为c_i(i=0, 1, 2, 3), 则种群P此时的分布熵可以表示为

(7)

依据分布熵确定整个种群的分布程度^[14], 并依据如下两个准则实现集中式框架结构向分布式种群框架结构的切换:

ⅰ)当分布熵H(P)低于设定阈值σ₁时, 说明种群个体的多样性降低, 个体出现明显的集聚性, 因此将集中式框架结构变换为分布式框架结构;

ⅱ)当分布熵连续τ代, 其变化范围保持在τ₂以内, 此时说明种群进化性能连续τ代变化不大, 原有框架结构已经不能满足种群进化要求, 需要增加种群多样性, 因此需要将集中式框架结构变换为分布式框架结构.

2) 分布式结构向集中式结构转换.

在分布式寻优框架结构中, 利用方差判断种群多样性, 无法利用个体中的每一维数的信息, 不能保证个体基因位进化过程趋向于全局最优, 无法确保优良积木块的积累, 进而破坏优良模式的不断增长^[15].因此, 引入多样性判断准则

(8)

其中: L为种群编码长度, 为第j维的平均值.当div(P)连续μ代, 其变化范围保持在阈值σ₃以内时, 原有框架结构已经不能满足种群进化要求, 将分布式框架结构变换为集中式框架结构.

2.2 引入优良解的速度和位置更新

为提高种群进化速度和全局勘探能力, 并保证种群多样性的提高, 在集中式还是分布式进化框架结构中, 可充分利用历史最优解和当前第t代最优解指导进化方向, 以提高种群进化方向, 便于主种群进行有效勘探^[16].本文利用历史最优解和当前第t代最优解的线性组合确定更新位置, 并设置不同的频率.主种群M内的个体位置更新方式为

(9)

其中: X_g^t为截止到第t代时的全局最优解, x_b^t为第t代的最优解.

依据历史最优解和第t代最优解进行勘探寻优, 其中f₁和f₂更新过程如下所示:

(10)

(11)

在式(10)和(11)中, x_w^t为第t代产生的最差解.

在子种群内, 为了充分进行开采操作, 利用第t代平均解值和历史最优解值, 并设置不同的权重系数, 子种群中速度更新方式为

(12)

其中: x_av^t为第t代的平均位置值; w₁和w₂为权重系数, w₁+w₂=1.

2.3 参数自适应调整

在传统蝙蝠算法中, A_i^t+1和R_i^t+1一般按照式(5)和(6)进行迭代循环更新, 其中参数α和γ是固定常数.因此, 不能根据当前群体进化情况进行自适应更改, 导致进化尺度单调, 种群多样性不高.为提高种群进化的多样性, 使得参数能够根据迭代次数动态更改, 本文采用自适应进化参数, 其中

(13)

定义δ^t=g_b^t-g_b^t-1, 如果δ^t < 0, 则说明全局最优解性能下降, 需要加强局部搜索能力, 更新方式可变化为

(14)

2.4 对多普勒效应进行补偿修正

在基本蝙蝠算法中, 往往没有考虑多普勒效应的影响, 而在蝙蝠个体实际觅食过程中, 这种现象是存在的.因此, 为了有效地补偿多普勒效应对脉冲频率的影响^[17], 需对蝙蝠位置和速度进行适应性更新.此时频率值不仅要考虑f_max和f_min, 同时还需要考虑多普勒效应的影响, 进行有效的补偿措施.依据多普勒公式

(15)

当蝙蝠在捕食的过程中, 不断靠近猎物, 同时猎物会逃脱追捕, 式(15)可变更为

(16)

此时经过补偿修正后的频率值为

(17)

利用式(17)可以分别对f₁、f₂和f₃进行补偿修正, 当式(17)中的f⁰分别替换为f₁、f₂和f₃时, 即完成了对原有频率值的更新.其中: v_g^t为第t代全局最优值时的速度值; c为声音在空气中的传播速度, c=340 m/s; C∈[0, 1]为补偿因子, 当C=0时, 表示蝙蝠不能在回声定位中对多普勒效应进行补偿, 当C=1时, 表示能完全补偿.

依据以上的描述, 可以对本文提出的自适应协同进化蝙蝠算法(ACEBA)流程进行描述.在算法运行初始阶段, 初始化种群X(t), 设置算法的运行参数, 包括种群规模N, 最大循环迭代次数T_max, 脉冲频率范围f_max和f_min, 音量的衰减系数α, 以及μ、τ、σ₁、σ₂和σ₃等参数, 则算法的主要进化流程可表述如下.

Step 1:主种群设定为M, 子种群分别设定为E₁、E₂和E₃, 各子种群分别独立进化, 初始进化结构为集中式进化框架;

Step 2:在集中式进化框架中, 子种群将最优个体传递给主种群, 主种群进行贪婪选择, 在分布式进化框架中, 子种群和主种群可以进行个体交流, 并进行贪婪选择;

Step 3:利用式(10)和(11)更新获得f₁和f₂, 并依据式(17)进行多普勒补偿修正;

Step 4:利用式(9)获得主种群内个体的位置信息, 利用式(12)并结合式(1)和(2)获得子种群内个体的位置信息;

Step 5:产生随机数rand, 如果rand>R_i^t, 则接受新产生的解, 否则, 当rand < A_i^t并且f(x_i(t)) < f(x_b)时, 更新当前最优解, 并依据式(5)、(6)、(13)和(14)更新A_i^t+1和R_i^t+1;

Step 6:判断当前进化种群结构, 若当前为集中式进化结构, 则依据式(7), 当分布熵低于设定阈值σ₁时, 或者在连续τ代变化范围保持在阈值σ₂以内时, 由集中式进化框架变换为分布式进化框架;

Step 7:若当前为分布式进化结构, 则依据式(8), div(P)在连续μ代, 其分布熵的变化范围保持在σ₃阈值以内, 由分布式进化框架变换为集中式进化框架;

Step 8:判断是否满足结束条件, 不满足则转Step 2, 否则结束输出.

3 收敛性分析

对本文提出的自适应协同进化蝙蝠算法的收敛性能和进化稳定性进行分析.本文所提出的ACEBA, 其核心进化过程可表示为

其中

则可得到

(18)

式(18)为一个二阶差分方程, 其中

可视作控制系统的外部输入, 并不影响系统的稳定性, 因此在分析系统稳定性过程中可以忽略.

定义1   对于离散时间序列{x(t), t=0, 1, ...}, x(t+1)收敛于最优解集x^*, 当且仅当.

对于式(18)而言, {x(t)}收敛于最优解x^*的充要条件是.

当前对进化算法稳定性的分析, 大多将时变线性系统视作线性定常系统, 即利用系数矩阵特征值根的模小于1, 但该判据适用于线性定常系统, 对线性时变系统并不一定适用, 推理结果的可信性降低.本文利用控制系统中的Jury稳定判据判断当系统稳定时参数的限制条件.

引理1 (劳斯-胡尔维茨稳定判据)   若线性系统其对应的特征方程为

其中a_n>0, 则该线性系统稳定的充要条件为:在特征方程中, 各项系数为正且不缺项.

连续系统的劳斯-胡尔维茨稳定判据, 是利用特征方程的系数和符号来判断系统的稳定性能, 而在离散线性系统中, 则不能直接套用, 因为离散线性系统是以特征根是否在z平面的单位圆内进行判断的, 即如果特征值|λ_i| < 1, 则判断该系统是稳定的, 否则不稳定^[18].

引理2(Jury稳定判据)   设n阶离散系统特征方程可以表示为

利用特征方程的系数, 构造(2n-3)(n+1)列朱利矩阵, 其中矩阵中2k+2行与2k+1行互为反向排列, 有

该离散系统特征根全部位于z平面单位圆内, 即系统稳定的充要条件为

并且|a₀| < a_n, |b₀|>|b_n-1|, |c₀|>|c_n-2|, |d₀|>|d_n-3|, ..., |q₀|>|q₂|.也就是说, 当以上条件都满足时, 离散系统才是稳定的, 否则系统是不稳定的.

定理1  自适应协同进化蝙蝠算法(ACEBA)稳定收敛的充分条件是

证明  由式(18)的差分方程, 对方程两边取数学期望后得到

方程右边可以表示为

则其特征方程为

特征根可以表示为

其通解为

其中c₁和c₂为待定系数, 由初值决定; K为常数.

对于二阶线性定常离散系统而言, 当n=2时, 判断其特征根的模是否在单位圆范围内, 此时引理2对应的稳定充要条件可以简化为判断是否满足D(1)>0, D(-1)>0, |1-f₁-f₂| < 1.由f₁、f₂和f₃的基本特性可知, 均满足f₁>0、f₂>0和f₃>0, 当满足上述条件后, 经过推理可以得到0 < f₁+f₂ < 2, f₁+f₂ < 2-f₃/2.

4 仿真分析

针对本文提出的自适应协同进化蝙蝠算法(ACEBA), 利用15个基准函数进行仿真分析.首先设置算法进化参数信息, 种群规模N设置为100, 最大循环迭代次数T_max为100, 脉冲频率范围f_max=2和f_min=0, 音量的衰减系数α=0.9, 以及μ=5、τ=5、σ₁=0.094 8、σ₂=0.001、σ₃=0.002.

仿真所需计算机硬件配置为Intel(R) Core(TM)i3-3 220处理器, 内存2.00 GB, Window 7系统, 仿真软件为Matlab R2009 a.分别利用同类型算法和不同类型算法进行仿真对比, 其中函数F₉最小值为-1, 函数F₁₀最小值为-1.03, 其余函数的最优值都为0.以下详细进行阐述.

4.1 同类型算法对比分析

将本文提出的ACEBA, 利用函数F₁ ~ F₆, 分别与基本蝙蝠算法(BA)、文献[13]提出的多种群协同蝙蝠算法(BatRM-s)、文献[16]提出的定向蝙蝠算法(NBA)、文献[19]提出的二进制蝙蝠算法(BBA)进行仿真对比分析, 将5种算法分别独立运行20次, 并统计平均最优值(Best)、全局平均值(Mean)和标准差(Std), 同时为了更充分分析本文所提出算法的优化效果, 将ACEBA与对比算法进行单侧t检验, 构造的检验统计量为

其中: m₁和M₂分别表示本文所提出算法和待对比算法的平均值; n₁和n₂表示样本数量, 在文中可利用算法独立运行次数表示; S₁和S₂表示本文所提出算法和待对比算法的方差.由于函数的F₁ ~ F₆最优值均为0, 给定右侧检验假设为H₀:μ₁≥μ₂, H₁:μ₁ < μ₂, μ₁和μ₂分别是本文算法和对比算法的理论最优均值.给定显著性水平0.01, 则拒绝域为W={t>t_0.01(n₁+n₂-2)}, 经查表后t_0.01(38)=2.428, 统计结果如表 1所示.

由表 1的统计结果可以看出:本文提出的ACEBA在大部分性能指标上都能取得最优或者较优值, 显示出ACEBA具有良好的进化性能; 同时也发现, BBA编码具有局限性, 寻优性能相比基本蝙蝠算法提升不明显. BatRM-s由于在协同进化框架上作了比较多的改进, 采用多个种群协同进化, 并设置了主种群和辅助种群的环形进化方式, 从而有效地提高了种群个体的交流方式, 在勘探和开采之间实现了有机协调, 因而进化性能有所提高. NBA也采用了有利于全局勘探的随机操作和自适应性参数操作, 从而提高了蝙蝠算法的开采能力, 而本文提出的ACEBA不仅在进化框架上进行自适应调整, 确保全局勘探的正确性, 同时也注重内部参数的自适应调整, 提高开采品质, 确保在整体上提高算法性能.

另外, 本文还给出了统计检验结果, 由表 1可以看出, 在显著性水平为0.01下, 检验统计量t的计算结果均大于2.428, 也就是说均落在拒绝域范围内, 因此拒绝假设H₀:μ₁≥μ₂, 接受假设H₁:μ₁ < μ₂, 说明本文提出的算法平均值优于其他对比算法.

为了进一步对所提出的ACEBA进行对比分析, 给出F₃函数的仿真对比图, 如图 3所示.

由图 3可以看到:本文所提出的ACEBA兼顾了全局自适应框架结构和参数自适应, 因而收敛效果比较平稳, NBA与BatRM-s也采用了相应的全局搜索和局部开采操作, 都能较为顺利地寻找到较优解; 同时也注意到, 基本BA与BBA, 搜索过程中方向性不强, 往往需有较多的迭代次数才能找到最优解, 因此需要针对问题的特性选择适合的优化方法.

4.2 不同类型算法对比分析

为了更充分地进行对比分析, 将本文提出的ACEBA与混合遗传算法(CGA)^[20]、自调节粒子群算法(SRPSO)^[2]、增强型蚁群算法(RACO)^[22]、快速人工蜂群算法(FABC)^[23]进行对比, 利用函数F₇ ~ F₁₂, 将5种算法分别独立运行20次, 并统计平均最优值(Best)、全局平均值(Mean)和标准差(Std), 统计结果如表 2所示.

由表 2的统计结果可看出:本文提出的ACEBA与几种改进智能进化算法相比也依然占有优势, 在大部分的基准函数上都能取得较优的收敛结果, 算法整体性能依然优越.由对比结果可以看出, CGA由于引入了细菌觅食算法中的趋药性, 在多次进化过程中也能找到最优解, 从F₉和F₁₀函数的统计结果可以清晰地看到这一点, 但整体性能还是与本文算法有一定差距. FABC对跟随蜂实施多次开采操作, 侧重于寻优速度上的提高, 提高了算法每次执行的效率, 各项寻优指标均劣于ACEBA. SRPSO在最优粒子中采用了自调节惯性权重, 同时在其他粒子中采用了搜索方向自我感知, 较好地协调了勘探和开采操作. RACO则考虑了蚂蚁以前的遍历路径, 并以此指导蚂蚁后续的路径选择和信息素更新, 因而上述两种算法与本文算法寻优效果性能指标接近, 甚至在函数F₈的平均值和标准差上还占有一定优势.从整体寻优效果上对比, 本文算法仍然能取得最佳的寻优效果, 主要是因为ACEBA不只是简单采用自我感知和调节, 而是引入了自适应的框架结构和自适应参数, 同时利用优良解指导进化方向, 因而与SRPSO和RACO相比, 提高了算法进化结构和进化方式的灵活性, 有效地增强了算法进化能力.

进一步对所提出的ACEBA进行对比分析, 给出F₁₁函数的迭代收敛图, 如图 4所示.

由图 4的收敛迭代结果可以看出: CGA虽然引入了细菌觅食算法中的趋药特性, 在一定程度上提高了算法进化程度, 但受制于进化框架结构, 寻优能力仍然有待提高; FABC侧重于挖掘跟随蜂的进化能力, 在提高算法效率的同时, 也在一定程度上增强了算法进化能力; SRPSO和RACO则具有较强的寻优能力, 与CGA和FABC相比, 能够快速向最优解趋近; 同时也看到本文提出的ACEBA利用较少的迭代次数能迅速向最优解收敛, 显示出本文算法设计时充分考虑了勘探和开采能力, 表现出强大的进化能力.

为了更充分地进行对比分析, 将本文所提出的ACEBA, 利用函数F₁₃~ F₁₅与文献[24]中的已有研究成果进行对比, 对比结果如表 3所示.

由表 3的对比结果可以看出, 本文提出的ACEBA相比早期传统的低阶进化算法(如DE、PBIL等算法), 具有极大的优势.低阶算法如果没有引入有利于全局勘探和局部开采的操作方法, 则寻优性能极差, 很难寻找到全局最优解.传统进化算法(如CS、KH等算法), 如果没有考虑协同进化或者自适应结构, 则容易陷入局部极值, 而IKH采用了局部开采方法和精英策略, 极大提高了算法的全局寻优能力.本文提出的ACEBA考虑了进化框架结构的自适应变化, 因此寻优能力得到了极大的增强, 与相关文献已有研究成果对比可以看出, 在大部分函数性能指标上, 都能取得最优的收敛效果.

5 结论

蝙蝠算法作为一种新兴的仿生智能进化算法, 已经引起越来越多的关注.本文针对其进化过程的基本特性和相关特点, 提出了一些改进策略, 采用自适应的进化框架使参数能够自适应调整, 从而更新了传统蝙蝠算法的进化过程, 使得蝙蝠算法的进化过程更具智能性和组织性.经过仿真验证对比, 并与同类型算法和不同类型智能进化算法对比分析, 充分看到了本文算法的特性和优缺点, 也反映了进化计算领域当前很难逾越的鸿沟——No Free Lunch定理, 即很难做到进化算法的所有指标都达到最优.因此在提高算法的收敛精度和进化效率的同时, 也必须注重降低算法的系统开销, 使得算法能够具备普适性, 这也是以后需要进一步研究的方向.