基于t-分布的混沌蝙蝠算法及其在弹簧设计中的应用

杨旭日，贺兴时，李文超

(西安工程大学 理学院，西安 710048)

近年来，受自然现象和动物群体行为的启示产生的一类元启发式算法成为研究热点[1]，如海鸥算法[2]、鲸鱼群算法[3]、灰狼搜索算法[4]等。元启发式算法虽然便于理解实现，架构简单且参数较少，但易陷入局部极值，收敛速度和精度较低，没有形成标准体系框架，仍可进行相关的理论扩充和算法改进。

蝙蝠算法(Bat Algorithm，BA)是2010年杨新社教授受蝙蝠能从喉头发出超声脉冲回声进行定位，在夜间飞行并精确捕食的启发而提出的。[1]该算法参数设置简单、易于理解和实现。但是，它在局部寻优中易产生早熟收敛陷入极值，求解问题的复杂度不高。为克服这些缺陷，大多数学者通过调节个体位置和速度参数、飞行机制、多种群进化等角度进行改进。如文献[5]为增加蝙蝠种群的全局搜索寻优能力，在维数一定的情况下对惯性权重因子进行改进，提出增强型蝙蝠算法(MBA)，以提升收敛性；文献[6]提出了一种改进搜索机制的多模态蝙蝠算法(MMBAIS)，有效地缓解了局部过早收敛的问题；文献[7]在标准的蝙蝠算法中添加了突变函数，提出基于均匀分布和高斯变异的蝙蝠算法(UGBA)。此外，还有许多学者致力于扩展蝙蝠算法的应用领域，如文献[8]提出采用多目标搜索蝙蝠算法(MOBA)解决大规模集成设计中的问题；文献[9]提出采用混合机制的二元蝙蝠粒子群优化算法(HBBEPSO)解决特征选择问题；文献[10]采用改进的离散蝙蝠优化算法(IBA)解决对称和非对称旅行推销问题。综上所述，蝙蝠算法的改进策略仍在探索和发展中，但是在实际应用中仍存在一些问题。仅仅通过改变参数调节速度与位置的更新，会局限个体的全局寻优；通过调整飞行机制融合其他算法，会增加参数的设置，导致算法计算量增大且时间复杂度提升，从而降低了算法的执行效率。

综上所述, 虽然蝙蝠算法有一定程度的改进,但仍存在收敛精度低和运行不稳定等问题，可见BA算法有较大的改进空间。本文提出一种基于惯性权重和t-分布的混沌蝙蝠算法(Chaotic bat algorithm based on inertia weight and t-distribution，CTBA)，其主要有以下改进: (1)改善随机初始化种群产生无效解，用Tent映射的概率密度分布较为均匀的优点干扰种群初始化数目，在保证种群多样性的同时又增强分布的随机性；(2)为扩大搜索空间，引入动态递减的惯性权重的更新速度和位置，平衡种群全局搜索与局部勘测的开发能力；(3)采用t-分布策略产生远离原始点的随机数，更新蝙蝠个体的位置，在优化前期提高全局搜索能力，后期以较小的速度缓慢更新，提高算法收敛的稳定性；(4)重新调整响度和速率参数因子，增强算法寻优过程的随机性，提升后期的收敛速度。

1 基本蝙蝠算法

蝙蝠算法是利用蝙蝠的回声定位能力来模拟其夜间飞行行为[11]，其捕食模式是从耳朵产生声波，发生频率的震荡变化，实现速度和位置的更新来模拟捕食过程中避免障碍物的随机搜索。该算法的实现是基于以下理想化假设[12]：

(1)蝙蝠种群利用回声定位系统感知猎物距离进行探测，避免障碍物;

(2)在飞行中，蝙蝠个体产生固定脉冲率，根据猎物距离自适应调整发射波长λ和脉冲响度A;

(3)根据脉冲响度的变化方式假设由初始值A0变化到最小值Amin。

fi=fmin+(fmax-fmin)·β

(1)

(2)

(3)

其中：β∈[0,1]为均匀分布的随机向量，X*为局部最优解，fi为声波频率，随机数ε∈[0,1]，同代平均响度为At。局部搜索使用随机游走方式生成，如式(4)所示。

X*=xold+ε·At

(4)

蝙蝠在飞行搜索中逐渐靠近目标猎物，此时，蝙蝠个体的声波响度和频率更新如式(5)(6)所示。

(5)

(6)

2 改进的蝙蝠算法(CTBA)

2.1 Tent混沌映射初始化种群

蝙蝠初始种群的规模、飞行范围对优化算法稳定性、收敛速度有很大影响。[13]传统蝙蝠算法使用随机数初始种群的位置和速度，这使蝙蝠的位置不能有效地对解空间进行全面覆盖，降低种群多样性。[14]与常见的Logistic映射、Cat映射等相比，Tent映射的概率密度函数具有随机遍历的特性，对初值的依赖程度低，因此，利用混沌映射初始化蝙蝠种群，可以增加种群多样性和随机性，提升算法前期的搜索能力。Tent混沌映射方程如式(7)所示。

(7)

其中：i=1,2,…,N，表示种群数目，t=1,2,…,d，表示维数。Tent映射序列的分岔图如图1所示，图1表明Tent映射倍周期分岔情况，可以看出当α为0.5时，Tent映射是分段的二维线性映射，分布较为发散，混沌程度较强，有利于提高算法初始化阶段种群的多样性。

图1 Tent混沌映射分岔图

2.2 惯性权重改进策略

文献[15]对动态递减惯性权重进行了研究，表明动态递减策略中ω的值随着迭代次数的增加而缓慢减小，可以提升迭代前期的局部搜索能力和搜索精度，使算法跳出局部最优。受此启发引入动态递减的惯性权重对速度公式进行更新，当t→tmax时，动态惯性权重在区间[-0.4,0.4]内缓慢减小。在迭代后期，惯性权重系数逐渐减小，算法越接近最优解，有利于灵活改变蝙蝠的速度更新，使个体具有更好的局部寻优能力。改进后的惯性权重ω如式(8)、图2所示：

图2 改进的动态权重曲线图

(8)

其中：ωmax,ωmin表示ω的最大值和最小值，本文取ωmax=0.9，ωmin=0.4,t,tmax表示当前迭代次数和最大迭代次数。改进后的位置更新公式为

(9)

相较之前的基本算法，速度的更新系数由恒定值变为动态变化的值，改进后的惯性权重越大，个体的变化范围越大，有利于全球勘探和局部开发。惯性权值越小，个体变化范围越小，有利于算法对优化函数进行局部搜索，在迭代后期增加了算法的随机性。

2.3 t-分布变异策略

BA算法具有强随机性，会导致新产生的解偏离全局最优，当扰动性越小时易产生聚集而陷入局部极值，变异算子可以增强算法的多样性和扰动性[16]。当自由度参数n=1时为Cauchy分布，图像无限趋近于横轴；当自由度参数n逐渐增大为t-分布，更易产生远离原始点的随机数；当自由度参数n趋近无穷时为Gaussian分布。t-分布含有自由度参数n，具有可达性、无偏性、可标度性等特征，其概率密度函数如式(10)、图3所示。

图3 分布概率密度图

(10)

针对每只蝙蝠个体都生成随机数且小于变异概率的蝙蝠，进行t-分布干扰，新产生的个体位置更新公式为

xnew=xold+t(iteration)·At

(11)

其中：xnew表示第i只蝙蝠个体经过变异扰动后的位置。算法的迭代前期，变异项在有限的迭代次数中能够较强地干扰个体的位置，使种群具有足够的多样性和复杂性，使算法克服早熟收敛；迭代中期将t-分布近似为其他两个分布的融合，可较好遍历算法的全局搜索；随着迭代的延续，变异项逐渐增大但对算法的影响力减小，这时t-分布可以看作Gaussian分布，搜索在局部邻域中进行寻优[17]，提高了收敛过程的速度和精度，提供了更好的优化性能。随着自由度的减少，t-分布按照一定规律，通过改变标准正态分布的方差进行构造。其密度曲线的形状变得越来越尖峰、厚尾，并且这种趋势在自由度较小时，变动得更加明显。相对于正态分布，t-分布密度曲线形状的变化更加丰富。

2.4 响度、脉冲频率

响度和脉冲频率计算时采用固定不变的步长α,γ，脉冲发射率影响蝙蝠个体的局部寻优，在算法后期，脉冲率逐渐增大时进行解的局部搜索寻优，而响度则随距离的减小而变弱，重新接受新解，故寻优后期原始算法设置的脉冲率和响度的当前解与最优解差距较大，不利于算法在解空间中覆盖[18]。因此，本文采用指数递变形式改进步长因子参数，构造出动态步长策略，模拟实际的捕猎情况。式(12)中α先缓慢减小后加速上升，呈凸性递减型；式(13)中γ为非线性递增因子，随着迭代次数的增加脉冲频率会逐渐增大，改进后的响度和脉冲频率的计算公式为

(12)

(13)

CTBA算法的基本步骤如下:

Step1:种群初始化。通过式(7)产生Tent混沌序列得到初始化蝙蝠的种群数目。

Step2:更新种群。根据式(1)至(4)更新蝙蝠的速度和位置，采用式(12)(13)更新响度和频率。

Step3:生成随机数，判断随机数满足rand

Step4:判断新解是否满足fnew≤fitness(i)，且如果满足rand>r，则更新当前适应度值为新的位置xnew。

Step5:产生新解并与当前最优解的适应度进行比较，满足fbest≤fnew，则更新当前适应度。

Step6:更新当前最优解的位置，判断结束条件，即是否达到预置的最大循环数，若否，则返回Step3继续执行，否则该算法终止。

2.5 复杂度分析

时间复杂度与算法的迭代次数和种群规模相关，迭代次数和种群规模越大，计算复杂度就越高。本文选择用时间复杂度衡量算法执行效率的高低。在D维空间中，M为种群规模，参数设置时间为t1，求解适应度的时间为f(D)，对适应度排序时间为t2，混沌映射时间为t3，则算法时间复杂度计算如下：

(1)BA的时间复杂度计算

BA算法在初始化阶段的时间复杂度为:T1=O(t1+M(f(D)+t2))=O(D+f(D))，在算法迭代阶段时间复杂度为：T2=O(t1+M(t2f(D)))=O(D+f(D))，所以，该算法的时间复杂度为T=T1+T2=O(D+f(D))。

(2)CTBA的时间复杂度计算

CTBA算法在初始化阶段的时间复杂度为:T1=O(t1+M(t3D+f(D)+t2))=O(D+f(D))，在算法迭代阶段，产生惯性权重的时间为t4，适应度比较的时间为t5，则该阶段时间复杂度为：T2=O(t1+M(t4+t5f(D)))=O(D+f(D))，在新解的更新阶段，产生新解的适应度时间仍为f(D)，每一维边界处理时间为t6，蝙蝠位置更新时间为t7，此阶段的时间复杂度为:T3=O(t6+M(t5+t7f(D)))=O(D+f(D))，所以，该算法的时间复杂度为T=T1+T2+T3=O(D+f(D))，和基本BA算法的时间复杂度一致，算法的执行效率不变。

3 仿真实验

3.1 仿真实验设计

为验证CTBA算法策略的有效性，本文通过选择多组标准测试函数测试算法的性能，如表1所示。

表1 Benchmark函数

测试集包含单峰、多峰、混合模态等特征，其中F1是Rosenbrock函数，其等高线呈抛物形，最小值为抛物线谷底，是典型的非凸单峰函数。F2为Noise函数，是一个连续可微分的检测算法的收敛速度性能的单峰函数。F3是Schwefel’s 2.2函数，其定义域为[-10,10]，理论最优值为0，是一个连续可微且不可分的单峰函数。F4为Ackley函数，是非线性多模态函数，存在大量的局部最优，可有效检测算法的全局收敛速度。F5为Rastrigin函数，是高维多模态函数，在解空间中有很多局部最小值。其峰值形状波动致使全局搜索相当困难。F6是Trid函数,该函数是可扩展的多模态函数，维数越高，局部最优数量就越多。F7为Generalized Penalized 1函数,是固定维度多峰测试函数，该函数会形成大量局部极值区域。F8为Griewank函数，它是一个连续可微、可伸缩的、多模态的多极端函数，具有许多局部最优值。它的优化难度极大，因此经常被用于测试算法的探索和开发能力。

对所提出的CTBA算法及基本蝙蝠算法(BA)、自适应变异蝙蝠算法(ABA)[18]以及t-分布蝙蝠算法(TBA)[19]进行实验比较。实验环境是Windows 10操作系统，8GB内存，用软件MATLAB R2018b进行编程。算法参数设置如表2所示。

表2 算法参数设置

3.2 实验结果分析

未排除个体之间的差异性和随机性的影响，设置初始种群数目20只，迭代次数300次，重复独立实验20次，取平均值、最大值、最小值以及标准差进行记录，结果如表3所示。

表3 基准函数结果对比

本文设置了10维空间，以观察4种算法的性能变化。采用标准差表明算法的稳定性。从表3可以明确看出，本文提出的CTBA算法相较于基本的BA算法收敛精确度有明显提高。在传统算法中，随着解空间维数的逐渐递增，算法更难到达最优值，并且会出现解的精度低、耗时增加甚至无法得到最佳解的情况。而改进的算法则可以克服这些问题，较快达到最优解，并且在数值精度上有显著提升。

对比单峰函数F1，F2，F3的数据，不难发现CTBA算法与ABA算法、自适应TBA算法在求解过程中平均值和最小值的差异较大，给定相同的迭代次数，CTBA算法具体的求解结果显著优于其他两种算法，表现出较为优异的性能。在最小值的对比中，改进的算法相较于其他算法在数值上优化了10倍以上，而相应的标准差则更为明显，这就意味着CTBA算法的稳定性更强，可以更好地跳出局部，寻找到理论最优值且精度较高。而BA算法效果最差，寻优精度很低，存在较大劣势和改进空间。

对于函数F3，F4而言，改进的算法很快达到理论最优值，精确度准确，求解多峰函数，标准差最小，算法的鲁棒性强。

计算F5，F6时，随着维数的逐渐增加，CTBA算法在寻优精度上的优势十分明显，且算法标准差较小，稳定性强。

但是，对于复杂的函数F7而言，表明蝙蝠算法对于求解高维优化问题的优势并不明显，求解效果出现下滑。对于复杂的多模态函数F8来说，经过多次迭代，逐渐接近理论收敛值，相较基本算法表现出较好的收敛能力，并且较为稳定。这是因为CTBA算法引入t-分布变异策略使种群跳出局部束缚，能进行更好的遍历寻优，相比而言有所提升，但是算法进行全局寻优的优势不突出，差异性较小，并且维度越高差异化表现得越明显。

3.3 算法求解收敛性分析

图4直观显示了采用CTBA算法、TBA算法和ABA算法以及基本BA算法在迭代后独立运行时的收敛情况。

为进一步直观分析算法的收敛性能，图4给出3种算法求解基准函数的迭代收敛曲线，横轴表示进化迭代的次数，纵轴表示基准测试函数的fitness值。收敛曲线是衡量算法收敛性能和执行效率的重要指标，单峰函数常常比较算法执行能力。通过观察相应函数的对比曲线，可以看出CTBA算法表现出较好的突跳能力。从整体上看，CTBA算法在收敛速度上表现良好，较快达到理想结果。由于加入Tent映射扰动初始化改进，使得算法在初始过程有较好的表现，引入动态递减的惯性权重平衡了局部搜索能力。

(a)Rosenbrock函数

(b)Noise函数

(c)Schwefel’s 2.2函数

(d)Ackley函数

(e)Rastrigin函数

(f)Trid函数

(g)Generalized Penalized 1函数

(h)Griewank函数

在单峰函数F1，F2，F3的图像中，原始的蝙蝠算法在求解过程中曲线没有较大改动，收敛速度最慢，没有显著的下降趋势，而改进的算法ABA在F3函数出现拐点时，有明显的趋势和速度进行收敛，但是相较本文提出的CTBA算法不具有较好的优势。对于多模态函数会产生大量的局部最优难以优化，用于测试算法的全局收敛能力，所以对比函数F4，F5的收敛曲线图，CTBA算法在种群初始值有明显的提升，收敛曲线近似垂直下落，并且能较快速度达到收敛，短时间内寻找全局最优，较快获得高质量的解。自适应的TBA算法也有较快的收敛速度，产生好的收敛性能。曲线上的拐点显示为函数F6迭代20次寻到理论极值，且算法稳定，鲁棒性好，这从侧面验证出t-分布变异有利于跳出局部最优，有效地获得了收敛速度较快的最优解，解的质量远高于其他两种算法。但是在高维函数F7上算法的优势表现并不明显，没有明显的下降趋势和拐点，容易陷入早熟收敛，未达到良好的收敛标准。而在高维度具有多个极值点的函数F8中，改进的算法依旧接近理论最优值，对比自适应的ABA算法收敛效果不及基本蝙蝠算法，这也验证了CTBA算法可以有效地避免局部收敛，适用于多极值点的复杂函数的求解。在迭代过程中,基本蝙蝠算法的种群最优蝙蝠吸引其他个体迅速向其聚拢,使得种群多样性急剧下降,收敛速度显著降低,种群进一步进化能力丧失，所以出现不收敛的情况。

3.4 弹簧设计问题

为了进一步验证所提出算法的有效性，采用文献[20]中的弹簧设计问题进行验证。这是一个约束工程问题，因为最优值是在有限的空间中搜索的。这个测试问题的目的是最小化压缩弹簧的重量。图5显示了弹簧及其参数示意图。优化设计必须满足弹簧弹力、震动频率和偏转的约束条件。该问题包含3个约束变量：平均线圈直x1(d)、有源线圈数x2(L)和导线直径x3(w)。

图5 弹簧示意图

弹簧设计问题模型如下：

(14)

(15)

(16)

(17)

(18)

其中:x1∈[0.05,2],x2∈[0.25,1.3],x3∈[2,15]。该模型输入函数为x1,x2,x3，输出函数为f(x1,x2,x3)，限制性函数为g1(x1,x2,x3),g2(x1,x2,x3),g3(x1,x2,x3),g4(x1,x2)。这个问题的主要目的是最小化f(x1,x2,x3)函数。为了证明所提出的基于自适应权重和t-分布的混沌蝙蝠优化方法的有效性，给出了一个比较表，并将其结果与灰狼优化(GWO)[4]、粒子群优化(PSO)[21]、引力搜索算法(GSA)[22]和遗传算法(GA)[23]进行了比较，结果如表4所示，相较于其他算法，本文所提出的CTBA算法取得了较好的结果。

表4 算法结果对比

4 结语

针对传统的BA算法在迭代前期全局寻优覆盖空间较小，在迭代后期收敛速度较为缓慢、精确度低等问题，提出了CTBA算法。利用Tent映射的随机性和遍历性初始化种群数目，克服随机分布多样性较低且密集的缺点。在位置更新过程中采用t-分布变异策略和自适应权重进行扰动，根据解的质量调整搜索范围，在此基础上又对响度和脉冲频率的参数进行改进，从而提高算法的求解精度和寻优能力。为验证提出的CTBA算法的有效性，我们选择了文献中广泛使用的8个数值基准函数，将所得结果与其他改进的算法进行比较，均取得了较好的结果。收敛性曲线表明，CTBA算法具有良好的最小化能力。此外，采用压缩弹簧设计问题进行实验，结果获得了较高的成功率，表明CTBA算法可具体应用于解决实际工程问题。但是，对于更加复杂的高维度函数问题难以达到理论最优解。在未来的改进算法研究中，将尝试更多的改进策略，如采用拓扑结构和变异算子提升的算法性能，解决现实生活中不可解问题的最优解。