计算机论文：一种基于lvy飞行轨迹的蝙蝠算法

   摘 要 针对新型元启发式蝙蝠算法存在收敛速度慢、求解精度低的现象,文中提出一种基于 Lévy 飞行轨迹的蝙蝠算法. 该算法具有易跳出局部最优,收敛速度快且求解精度高等特点. 通过对 12 个典型的测试函数进行仿真实验,结果表明该算法是有效、可行的,且在求解高维空间问题中也表现出优越的逼近性能.
       关键词 蝙蝠算法,Lévy 飞行,函数优化
   1 引 言近年来,愈来愈多的模拟自然或社会现象的群智能算法被提出,如遗传算法( Genetic Algorithm,GA ), 模 拟 退 火 算 法 ( Simulated Annealing,SA),粒子群优化算法( Particle Swarm Optimiza-tion,PSO ),萤 火 虫 算 法 ( Firefly Algorithm,FA,Glowworm Swarm Optimization,GSO) ,猴群搜索算法( Monkey Search,MS)[6],细菌觅食优化算法 ( Bacterial Foraging Optimization Algorithm,BFOA),入侵杂草优化算法( Invasive Weed Opti-mization,IWO),文化算法( Cultural Algorithms,CA),和谐搜索算法( Harmony Search,HS)和狩猎搜索算法( Hunting Search HS)等. 由于群智能算法能够解决一些传统算法不能解决的问题,因此,已在工程优化、科学计算、自动控制等领域得到了广泛地应用.蝙蝠算法( Bat Algorithm,BA) 是由 Yang提出的一种模拟蝙蝠回声定位行为的新型群智能优化算法. 该算法逐渐引起人们的极大关注,且在应用方面取得较大的成功. 如 Tsai 等将其改进后应用于解决数值优化问题; Yang用于解决多目标优化问题,Bora 等将其应用在 Brushless DCWheel Motor Problem 上. 蝙蝠算法虽是一种新的群智能算法,但在收敛速度和求解精度上还存在着缺陷. 因此,本文提出一种基于 Lévy 飞行轨迹的蝙蝠算法( Lévy-Flights Bat Algorithm,LBA) ,目的在于提高蝙蝠算法收敛速度和求解精度,最后,通过 14个经典的测试函数进行测试,实验结果表明,该算法相比基本蝙蝠算法,收敛速度和求解精度有较大提高.
       2 基本蝙蝠算法和 Lévy 飞行2. 1 蝙蝠的行为蝙蝠拥有回声定位能力,它们能产生短促而频率高的声波脉冲,这些声波在碰到附近物体便反射回来. 然后被蝙蝠超凡的大耳廓所接收,声波反馈的信息在它们微细的大脑中进行分析,为飞行提供导向. 蝙蝠对生物波的探测灵敏度和分辩力极高,据回声不仅能判别方向,为自身飞行路线定位,还能辨别出不同的昆虫和障碍物,进行有效追捕和回避. 大多数蝙蝠在觅食时每秒可发出高达 200 个频率范围在 25kHz~100kHz,持续时间在 5ms~20ms 的声波脉冲.
       2. 2 基本蝙蝠算法蝙蝠算法是在理想状态下,利用蝙蝠在觅食时所发出的脉冲的频率、响度、脉冲发射率的变化而模拟设计出的一种群智能算法. 基本蝙蝠算法是模拟蝙蝠的觅食行为,通过频率 f 的调整引起波长λ 的变化( 因为 λf = v,v 是声波在空气中的传播速度) ,波长 λ 的大小与蝙蝠所捕食的昆虫的大小相一致,从而可定位目标. 一般频率 f 在[fmin,fmax]范围内变化. 蝙蝠按脉冲发射率 ri∈[0,1]和响度 Ai发出声波脉冲,蝙蝠在定位的过程中,当发现目标时会增加脉冲的发射率,减小响度 Ai,从而逼近目标,以致捕食到猎物. 这里发射率 ri增加到 1 表示发出非常急促的脉冲,响度 Ai减小到0 表示靠近猎物,近似无声无息.Yang在提出蝙蝠算法时为模拟蝙蝠的回声定位特征给出以下理想化规则( Idealized Rules,IR)  IR1. 所有的蝙蝠运用回声定位去感应距离,还能以一种不为我们所知的方式"知道"猎物和背景障碍之间的区别;IR2. 蝙蝠在位置 xi处以速度 vi随意飞行,以固定的波长 λ、可变的频率 f、响度 Ai和脉冲发射率 ri去搜索猎物;IR3. 尽管响度会有很多方式变化,假定它的变化是从一个正的最大值 A0减小到最小常数值 Amin.在d维空间中,蝙蝠i在t时刻的位置xti、速度vti更新公式为fi= fmin+ ( fmax- fmin) β,vti= vt -1i+ ( xt -1i- x*) fi,xti= xt -1i+ vti,{( 1)其中,β ∈[0,1]是来自均匀分布的随机变量,x*是在 n 只蝙蝠中的全局最优解.对于局部搜索部分,每当一个解被选为当前最好解时,新解通过如下的随机游走方式产生:
  xnew= xold+ εAt, ( 2)这里的 ε ∈[- 1,1]是一个服从均匀分布的随机数,At= < Ati> 是在 t 时刻所有蝙蝠的平均响度.响度和脉冲发射率的更新公式为At +1i= αAti,rt +1i= r0i[1 - exp ( - γt) ], ( 3)其中,α 和 γ 是常数.在上述理想规则的基础上,蝙蝠算法实施步骤如下.step 1 确定目标函数和初始化相关参数.step 2 初始化蝙蝠种群位置 x1i( i =1,2,…,n)8 30模式识别与人工智能 26 卷和速度 v1i,定义第 i 只蝙蝠在位置 xi处的脉冲频率fi,初始化脉冲发射率 r1i响度 A1i.step 3 计算每只蝙蝠的初始适应度值.step 4 通过调整频率利用式( 1) 更新蝙蝠的速度 vti和位置 xti而产生后代个体.step 5 若随机产生的随机数大于脉冲发射率rti,则在当前所有个体中选择一个个体为全局最优个体 x*,且在选择的最优个体附近利用式( 2) 随机产生一个局部个体,并计算这个局部个体的适应度值.step 6 若由 step 5 产生局部个体的适应度值较全局最优个体有改进且产生的随机数小于响度Ati,则接受该新解为当前全局最优个体,保存这个个体的适应度值,用式( 3) 增大 rti和减小 Ati.step 7 更新算法迭代次数,判断是否达到终止条件. 是,则退出打印结果,否,则进入step 4 进行循环.
      2. 3 Lévy 飞行轨迹Lévy 飞行轨迹是 Lévy 提出,Benoist-Madelbrot进行描述的一种稳定分布. Lévy 飞行是一种随机游走过程,它的步长是一种连续的重尾分布.Lévy 飞行具有以下性能特性:
    1) 独立同分布的随机变量之和与随机变量本身具有相同的分布,即具有统计的自相似性和随机分形;2) 具有幂律渐进性 ~ x( -1-α),也就是所说的"重尾";3) 具有广义中心极限定理. 对随机变量和分布来说,Lévy 飞行是极限的一种,具有邻域的吸引,当系统的进化或实现结果由大量的随机数的和决定时,就会出现吸引;4) 具有无限均值和无限方差.研究表明,许多动物和昆虫的飞行行为验证Lévy 飞行的典型特征. 由 Reynolds 和 Frye 的研究表明果蝇探索其视野也是用一系列穿插着突然 90o转弯的的直线飞行路线,这是间歇规模的Lévy飞行自由搜索模式; 关于人类行为的Ju /'hoansi狩猎的觅食模式同样也表明这典型的 Lévy 飞行[19];Barthelemy 等发现光的 Lévy 飞行; Mercadier等在热原子蒸气中发现光子的 Lévy 飞行; 随之而来的是 Lévy 飞行也被应用到最优化和优化搜索中,结果表明,Lévy 飞行具有优越的性能.
      3 基于 Lévy飞行轨迹的蝙蝠算法3. 1 基本蝙蝠算法分析蝙蝠算法是一种受蝙蝠的回声定位行为启发的随机搜索算法,在蝙蝠的速度和位置的更新过程中,频率 fi本质上控制着这些蝙蝠群的移动步伐和范围. 蝙蝠在寻优过程中,通过调节脉冲发射率 ri和响度 Ai促使蝙蝠朝着最优解方向移动. 蝙蝠在刚开始搜索时只具有较小的脉冲发射率和较大的响度,蝙蝠有较大的概率选择更好的解,随着迭代的增加,脉冲发射率增加,响度减小,蝙蝠不断扫描定位目标,最终搜索到最优解.
      3. 2 LBA 算法思想本文在基本蝙蝠算法基础上,引入蝙蝠个体历史经验与蝙蝠群体间的信息交流机制来控制蝙蝠的飞行速度,指导蝙蝠的飞行定位,这一策略使得算法能快速地收敛到较好的解; 且使蝙蝠的声波频率线性自适应地增加,这在一定程度上加强了算法的探索能力,有助于跳出局部最优,且更符合自然. 同时,本文引入具有较好随机性的 Lévy 飞行,将其作用于蝙蝠位置的更新公式中,进而提升算法的性能.这是由于 Lévy 飞行可以一系列较小步长移动后突然获得一个较大步长,从而有助于跳出局部最优.Gaussian 分布、Cauchy 分布和 Lévy 分布都属于α 稳定分布[22],其中 Gaussian 分布和 Cauchy 分布的概率密度函数( PDF) 图是对称的,而 Lévy 分布则不是. 一种基于 Lévy 飞行轨迹的蝙蝠算法831xt +1i= xti+ αεt.若步长εt服从Gaussian 分布,这就是一个标准的随机游走,若步长εt来自Lévy 分布,则它的移动在一系列小步长之后可能获得一个较大的步长,但若步长太大,也可能跳到太远处. 所幸算法采用精英策略保留历史最优解,这样可保证蝙蝠再次移动到最优解附近,正因为这一步大跳,使得算法能跳出局部最优,并通过小步长开采到更好的解. 这在多样性与集中性之间取得较好的平衡,从而提高算法的性能.本文定义在 d 维空间中,蝙蝠i 在t 时刻的位置xti、速度 vti更新公式为fti= ( ( fmax- fmin)tnt+ fmin) β,vti= ( x∧i- x*) fti,xti= x∧i+ vti+ μsign[rand -12] Lévy,( 4)其中,β ∈[0,1]是来自均匀分布的随机变量,nt为设置的固定参数,x*是在n 只蝙蝠中的全局最优解. x∧i表示第i 只蝙蝠历史最优解,μ 是一个随机参数,符号 ? 表示点乘,rand ∈ [0,1],随机步长Lévy 来自于 Lévy 分布:
      3. 3 LBA 算法程序流程基于 Lévy 飞行轨迹的蝙蝠算法( LBA) 程序流程.在 LBA 迭代中,位置的更新是由式( 4) ~ ( 5)执行更新; 对每只蝙蝠,若一个随机产生的数大于或等于该蝙蝠的发射率,则由式( 2) 在该个体的历史最优位置附近产生一个新解; 对于响度和脉冲发射率的更新则由式( 6) 执行. LBA 算法流程图Fig. 2 Flow chart of LBA algorithm8 32模式识别与人工智能 26 卷4 仿真实验及分析4. 1 实验环境和参数设置为验证算法的有效性和正确性,下面通过 12个基准测试函数来验证算法的改进效果. 仿真平台: 操 作 系 统: Microsoft Windows Server 2003Enterprise Edition SP2; CPU: Intel( R) Xeon( R)E5405; 主频: 2. 00GHz; RAM: 2. 00GB; 编程工具: Matlab 2009a. 试验中的参数见表 1.实验参数表Table 1 Parameters of simulation experimentn fminfmaxA0ir0iα γntBA 40 0 100 ( 1,2) ( 0,0. 1) 0. 9 0. 9 -LBA 40 0 100 ( 1,2) ( 0,0. 1) 0. 9 0. 25 5000这里采用两种终止条件: 对于理论最小值确定的测试函数采用固定求解精度 Tol = 1. 0e - 5; 对于理论最优值不确定的采用目标函数最大估值次数( FEs) . 在实验中每个测试函数,BA 对应参数取值是原文推荐的,这里的最大估值次数是由迭代次数乘以种群规模所得,实验中取16000次( =200×40×2) .4. 2 测试函数实验对 12 个基准测试函数进行实验,包括单峰、多峰、低维、高维的无约束测试函数. f1~ f2是单峰函数,f3~ f12是多峰函数; f1~ f8是理论最小值确定的,f9~ f12没有确定的理论最小值.f1: Sphere 函数f( x) =∑ni = 1x2i,- 10 ≤ xi≤ 10,这里的 n 是维数,该函数在 x*= ( 0,0,…,0) 处取得全局最小值 fmin= 0.f2: Schwegel 函数 2. 22f( x) =∑ni = 1xi+∏ni = 1xi,- 10 ≤ xi≤ 10,该函数在x*= ( 0,0,…,0) 处取得全局最小值 fmin= 0.f3: Eggcrate 函数f( x,y) = x2+ y2+ 25( sin2x + sin2y) ,( x,y) ∈[- 2π,2π],该二维函数在( 0,0) 处取得全局最小值 fmin= 0,该函数是一个多峰函数.f4: Ackley 函数f( x) = - 20exp-151n∑ni = 1x2槡i[ ]-exp1n∑ni = 1cos( 2πxi)[ ]
  + 20 + e,- 30 ≤ x ≤ 30,该函数在 x*= ( 0,0,…,0) 处取得全局最小值 fmin=0,该函数是一个多峰函数.f5: Griewangk 函数f( x) =14000∑ni = 1x2i-∏ni = 1cos(xi槡i)+ 1,- 600 ≤ xi≤ 600,该函数在 x*= ( 0,0,…,0) 处取得全局最小值 fmin=0,该函数是一个多峰函数.f6: Salomon 函数f( x) = - cos(2π ∑ni = 1x2槡i)+ 0. 1∑ni = 1x2槡i+ 1,- 5 ≤ xi≤ 5,该函数在 x*= ( 0,0,…,0) 处取得全局最小值 fmin=0,该函数是一个多峰函数.f7: Rastrigin 函数f( x) = 10n +∑ni = 1[x2i- 10cos ( 2πxi) ],- 5. 12 ≤ xi≤ 5. 12,该函数在 x*= ( 0,0,…,0) 处取得全局最小值 fmin=0,该函数是一个多峰函数.f8: Zakharov 函数f( x) =∑ni = 1xi2+(12∑ni = 1ixi)2+(12∑ni = 1ixi)4,- 10 ≤ xi≤ 10,该函数在 x*= ( 0,0,…,0) 处取得全局最小值 fmin=0,该函数是一个多峰函数.f9: Easom 函数f( x,y) = - cosxcosyexp[- ( x - π)2+ ( y - π)2],- 10 ≤ x ≤ 10,- 10 ≤ y ≤ 10,该函数在( π,π) 处取得全局最小值 fmin= - 1,该函数是一个多峰函数.f10: Schwegel 函数f( x) = -∑ni = 1xisin( xi槡) ,- 500 ≤ xi≤ 500,该函数在 x*≈ ( 420. 9687,…,420. 9687) 处取得全局最小值 fmin≈- 418. 9829n 是一个多峰函数.f11: Shubert 函数f( x,y) =[∑5i = 1i cos( i + ( i + 1) x)]
  ·[∑5i = 1i cos( i + ( i + 1) y)],- 10 ≤ x ≤ 10,- 10 ≤ y ≤ 10,9 期 等: 一种基于 Lévy 飞行轨迹的蝙蝠算法833该函数有18 个全局最优值和742 个局部最优值,全局最小值fmin≈- 186. 7309.f12: Drop Wave 函数f( x) = -1 + cos(12 ∑ni =槡1xi2)12(∑ni = 1x2i)+ 2,- 5.12 ≤xi≤5.12,该函 数 在 x*= ( 0,0,…,0) 处 取 得 全 局 最 小值 fmin= - 1,该函数是一个多峰函数.4. 3 实验结果比较针对不同的函数采用不同的终止条件,对每组测试函数都独立运行 100 次,其结果见表 2 和表 3,其中加粗表示 LBA 更优,加下划线表示 BA 更优,不加表示相同. ( TC 表示终止条件,Tol = 1. 0e - 5,iter_max = 200 表示终止条件固定求解精度,在达不到精度的条件下最大迭代 200 次,即 FEs = 16 000,表示最大函数估值次数为 16 000 次. BenchmarkFunction 表示基准测试函数; Method 表示比较的两种方法; Fitness 表示基准测试函数的适应度值;Min,Mean,Max,Std 分别对应最小、平均、最大和标准偏差.从表 2 可看出,本文提出的算法对于给定搜索精度的函数寻优,LBA 最少迭代 4 次,精度可达 1. 0e - 5,而 BA 最好精度达到 1. 0e - 05 需200代才达到. 从各个函数运行得到的均值可看出,f1~ f8中,所有的测试函数都能得到满足条件的解. 从迭代次数来看,LBA 能更快地收敛,从平均迭代次数可 得 到 收 敛 速 度 比 BA 提 高 474. 71% ~1042. 86% ,从这 8 个函数来看,平均提高 810.20% . 对于 BA 和 LBA 都没有达到终止精度且都迭代 200 代的函数,在相同的条件下,本文的 LBA 所获得的最优值还是比 BA 获得的最优值要更接近于理论值,从而说明 LBA 具有较强的逼近能力.
      参 考 文 献[1] Holland J H. Adaptation in Natural and Artificial Systems. Cam-bridge,USA: MIT Press,1992[2]Kennedy J,Eberhart R. Particle Swarm Optimization / / Proc of theIEEE International Conference on Neural Networks. Perth,Australia,1995,IV: 1942-1948[3] Yang Xinshe. Nature-Inspired Metaheuristic Algorithms. Frome,UK: Luniver Press,2011[4]Yang Xinshe. Multiobjective Firefly Algorithm for Continuous Opti-mization. Engineering with Computers,2013,29( 2) : 175-184