第8卷第3期 智能系统学报 Vol.8 No.3 2013年6月 CAAI Transactions on Intelligent Systems Jun.2013 D0I:10.3969/i.issn.1673-4785.201211047 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20130125.1436.003.html 具有Lévy飞行特征的蝙蝠算法 刘长平12，叶春明 (1.上海理工大学管理学院，上海200093：2.淮阴工学院经济管理学院，江苏淮安223001) 摘要：针对基本蝙蝠算法易早熟、收敛精度低等不足，在分析蝙蝠算法优化机理和局限性的基础上，从算法仿生原 理入手，采用Ly飞行搜索策略更为真实地模拟蝙蝠的捕食行为，取代原有算法的速度和位置更新方式，充分利用 Ly飞行会产生较大跳跃这种不均匀随机游走的特性，有效避免局部极值的吸引通过标准测试函数对所提算法进 行仿真测试，结果表明所提算法有效克服了原算法易早熟、收敛精度低等缺陷，在寻优精度和全局收敛性能方面明 显优于基本蝙蝠算法和粒子群优化算法，是解决复杂函数优化问题的一种有效工具 关键词：蝙蝠算法；Léy飞行；函数优化；粒子群优化算法 中图分类号：TP301.6:N945文献标志码：A文章编号：1673-4785(2013)03-0240-07 中文引用格式：刘长平，叶春明.具有Ly飞行特征的蝙蝠算法[J].智能系统学报，2013,8(3)：240-246. 英文引用格式：LIU Changping,.YE Chunming.Bat algorithm with the characteristics of Levy flights[J].CAAI Transactions on In- telligent Systems.2013,8(3):240-246. Bat algorithm with the characteristics of Levy flights LIU Changping'.2,YE Chunming' (1.College of Management,University of Shanghai for Science Technology,Shanghai 200093,China;2.College of Economics Management,Huaiyin Institute of Technology,Huaian 223001,China) Abstract:The basic bat algorithm (BA)in the past research studies reveal deficiencies as apt to be premature and low precision of convergence.This paper first analyzed the optimization mechanism and deficiency of bat algorithm (BA),and then considering the Levy flight behaviors of bats can simulate predatory more realistically,the study proposed substituting for the speed and location updating pattern of former algorithm.The proposed algorithm fully explored the trait of uneven random walks,so that clusters of short steps were connected by rare long steps,to a- void being trapped in local optimal solution.Simulation results for benchmark functions show that the proposed algo- rithm improved the global optimization ability remarkably and outperformed the basic BA and particle swarm optimi- zation (PSO)in accuracy and convergence property.Therefore,the proposed algorithm is an effective tool for sol- ving the optimization of complex functions. Keywords:bat algorithm;Levy flight;function optimization;particle swarm optimization 相对于传统优化方法，群智能算法在优化过程用.近年来，受自然规律和生物群体智能行为的启 中仅需要目标函数的信息，不受搜索空间连续或可 发，一些新颖的仿生群智能算法如人工鱼群算 微的限制，能够以较大概率找到最优解或近似最优 法口、蜂群算法[2】、萤火虫算法[34等相继被提出， 解，并且具有操作简单、适宜并行计算、鲁棒性强等 显示出独特的特点和效果 特点，在科学计算和工程技术领域内得到了广泛应 蝙蝠是自然界中惟一会飞的一类哺乳动物，拥 有令人惊异的回声定位能力，通过探测发出的超声 收稿日期：2012-11-27.网络出版日期：2013-01-25. 波回波的时间延迟，利用回波到达双耳的时间差、回 基金项目：国家自然科学基金资助项目(71271138)：教育部人文社会 科学规划基金资助项目(10Y门A630187);上海市教委科研 波音强的变化建立起周围环境的三维场景，蝙蝠不 创新重点资助项目(12ZS133):教育部高校博士学科点专 项科研基金资助项目(20093120110008). 仅能精确探测猎物的距离，还能识别其体型特征、方 通信作者：刘长平.E-mail:lcp_mail@163.com. 位和角度通过模拟蝙蝠借助超声波搜索、捕食猎物第 ８ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．３ ２０１３ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１２１１０４７ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３０１２５．１４３６．００３．ｈｔｍｌ 具有 Ｌéｖｙ 飞行特征的蝙蝠算法 刘长平１，２ ，叶春明１ （１．上海理工大学 管理学院，上海 ２０００９３； ２．淮阴工学院 经济管理学院，江苏 淮安 ２２３００１） 摘 要：针对基本蝙蝠算法易早熟、收敛精度低等不足，在分析蝙蝠算法优化机理和局限性的基础上，从算法仿生原 理入手，采用 Ｌéｖｙ 飞行搜索策略更为真实地模拟蝙蝠的捕食行为，取代原有算法的速度和位置更新方式，充分利用 Ｌéｖｙ 飞行会产生较大跳跃这种不均匀随机游走的特性，有效避免局部极值的吸引．通过标准测试函数对所提算法进 行仿真测试，结果表明所提算法有效克服了原算法易早熟、收敛精度低等缺陷，在寻优精度和全局收敛性能方面明 显优于基本蝙蝠算法和粒子群优化算法，是解决复杂函数优化问题的一种有效工具． 关键词：蝙蝠算法；Ｌéｖｙ 飞行；函数优化；粒子群优化算法 中图分类号： ＴＰ３０１．６；Ｎ９４５ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０３⁃０２４０⁃０７ 中文引用格式：刘长平，叶春明．具有 Ｌéｖｙ 飞行特征的蝙蝠算法［Ｊ］．智能系统学报， ２０１３， ８（３）： ２４０⁃２４６． 英文引用格式：ＬＩＵ Ｃｈａｎｇｐｉｎｇ， ＹＥ Ｃｈｕｎｍｉｎｇ． Ｂａｔ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ Ｌéｖｙ ｆｌｉｇｈｔｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（３）： ２４０⁃２４６． Ｂａｔ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ Ｌéｖｙ ｆｌｉｇｈｔｓ ＬＩＵ Ｃｈａｎｇｐｉｎｇ １，２ ， ＹＥ Ｃｈｕｎｍｉｎｇ １ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｍａｎａｇｅｍｅｎｔ， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｈａｎｇｈａｉ ｆｏｒ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｈａｎｇｈａｉ ２０００９３， Ｃｈｉｎａ； ２． Ｃｏｌｌｅｇｅ ｏｆ Ｅｃｏｎｏｍｉｃｓ ＆ Ｍａｎａｇｅｍｅｎｔ， Ｈｕａｉｙｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｈｕａｉａｎ ２２３００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｂａｓｉｃ ｂａｔ ａｌｇｏｒｉｔｈｍ （ＢＡ） ｉｎ ｔｈｅ ｐａｓｔ ｒｅｓｅａｒｃｈ ｓｔｕｄｉｅｓ ｒｅｖｅａｌ ｄｅｆｉｃｉｅｎｃｉｅｓ ａｓ ａｐｔ ｔｏ ｂｅ ｐｒｅｍａｔｕｒｅ ａｎｄ ｌｏｗ ｐｒｅｃｉｓｉｏｎ ｏｆ ｃｏｎｖｅｒｇｅｎｃｅ． Ｔｈｉｓ ｐａｐｅｒ ｆｉｒｓｔ ａｎａｌｙｚｅｄ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｃｈａｎｉｓｍ ａｎｄ ｄｅｆｉｃｉｅｎｃｙ ｏｆ ｂａｔ ａｌｇｏｒｉｔｈｍ （ＢＡ）， ａｎｄ ｔｈｅｎ ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ Ｌéｖｙ ｆｌｉｇｈｔ ｂｅｈａｖｉｏｒｓ ｏｆ ｂａｔｓ ｃａｎ ｓｉｍｕｌａｔｅ ｐｒｅｄａｔｏｒｙ ｍｏｒｅ ｒｅａｌｉｓｔｉｃａｌｌｙ， ｔｈｅ ｓｔｕｄｙ ｐｒｏｐｏｓｅｄ ｓｕｂｓｔｉｔｕｔｉｎｇ ｆｏｒ ｔｈｅ ｓｐｅｅｄ ａｎｄ ｌｏｃａｔｉｏｎ ｕｐｄａｔｉｎｇ ｐａｔｔｅｒｎ ｏｆ ｆｏｒｍｅｒ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｆｕｌｌｙ ｅｘｐｌｏｒｅｄ ｔｈｅ ｔｒａｉｔ ｏｆ ｕｎｅｖｅｎ ｒａｎｄｏｍ ｗａｌｋｓ， ｓｏ ｔｈａｔ ｃｌｕｓｔｅｒｓ ｏｆ ｓｈｏｒｔ ｓｔｅｐｓ ｗｅｒｅ ｃｏｎｎｅｃｔｅｄ ｂｙ ｒａｒｅ ｌｏｎｇ ｓｔｅｐｓ， ｔｏ ａ⁃ ｖｏｉｄ ｂｅｉｎｇ ｔｒａｐｐｅｄ ｉｎ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ． Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｆｏｒ ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏ⁃ ｒｉｔｈｍ ｉｍｐｒｏｖｅｄ ｔｈｅ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ａｂｉｌｉｔｙ ｒｅｍａｒｋａｂｌｙ ａｎｄ ｏｕｔｐｅｒｆｏｒｍｅｄ ｔｈｅ ｂａｓｉｃ ＢＡ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉ⁃ ｚａｔｉｏｎ （ＰＳＯ） ｉｎ ａｃｃｕｒａｃｙ ａｎｄ ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｐｅｒｔｙ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ｔｏｏｌ ｆｏｒ ｓｏｌ⁃ ｖｉｎｇ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｆｕｎｃｔｉｏｎｓ． Ｋｅｙｗｏｒｄｓ：ｂａｔ ａｌｇｏｒｉｔｈｍ； Ｌéｖｙ ｆｌｉｇｈｔ； ｆｕｎｃｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ； ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ 收稿日期：２０１２⁃１１⁃２７． 网络出版日期：２０１３⁃０１⁃２５． 基金项目：国家自然科学基金资助项目（７１２７１１３８）；教育部人文社会 科学规划基金资助项目（ １０ＹＪＡ６３０１８７）；上海市教委科研 创新重点资助项目（１２ＺＳ１３３）；教育部高校博士学科点专 项科研基金资助项目（２００９３１２０１１０００８）． 通信作者：刘长平．Ｅ⁃ｍａｉｌ：ｌｃｐ＿ｍａｉｌ＠ １６３．ｃｏｍ． 相对于传统优化方法，群智能算法在优化过程 中仅需要目标函数的信息，不受搜索空间连续或可 微的限制，能够以较大概率找到最优解或近似最优 解，并且具有操作简单、适宜并行计算、鲁棒性强等 特点，在科学计算和工程技术领域内得到了广泛应 用．近年来，受自然规律和生物群体智能行为的启 发，一些 新 颖 的 仿 生 群 智 能 算 法 如 人 工 鱼 群 算 法［１］ 、蜂群算法［２］ 、萤火虫算法［３⁃４］ 等相继被提出， 显示出独特的特点和效果． 蝙蝠是自然界中惟一会飞的一类哺乳动物，拥 有令人惊异的回声定位能力，通过探测发出的超声 波回波的时间延迟，利用回波到达双耳的时间差、回 波音强的变化建立起周围环境的三维场景，蝙蝠不 仅能精确探测猎物的距离，还能识别其体型特征、方 位和角度．通过模拟蝙蝠借助超声波搜索、捕食猎物