第10卷第4期 智能系统学报 Vol.10 No.4 2015年8月 CAAI Transactions on Intelligent Systems Aug.2015 D0:10.3969/j.issn.1673-4785.201409042 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150630.1559.004.html 具有动态惯性权重的布谷鸟搜索算法 周欢1，李煜 (1.河南大学商学院，河南开封475004：2.河南大学管理科学与工程研究所，河南开封475004) 摘要：为提高布谷鸟搜索算法的搜索能力和寻优精度，提出一种具有动态惯性权重的布谷鸟搜索算法。该算法引 入动态惯性权重改进鸟窝位置的更新方式，依据动态惯性权重值保留上代鸟窝的最优位置并进行下一代位置更新， 从而有效平衡种群探索能力和开发能力之间的关系。并利用特征方程对改进算法进行了收敛性分析。仿真实验结 果表明，与基本布谷鸟搜索算法、粒子群算法和蚁群算法相比，改进后的布谷鸟搜索算法能显著减少迭代次数和运 行时间，有效提高算法的收敛速度和收敛精度。 关键词：布谷鸟搜索算法；函数优化：莱维飞行：动态惯性权重：种群规模：收敛性：复杂度：参数选取 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2015)04-0645-07 中文引用格式：周欢，李煜.具有动态惯性权重的布谷鸟搜索算法[J].智能系统学报，2015,10(4)：645-651. 英文引用格式：ZHOU Huan,LIYu.Cuckoo search algorithm with dynamic inertia weight[J].CAAI Transactions on Intelligent Systems,2015,10(4):645-651. Cuckoo search algorithm with dynamic inertia weight ZHOU Huan',LI Yu2 (1.School of Business Administration,He'nan University,Kaifeng 475004,China;2.Research Institute of Management Science and Engineering,He'nan University,Kaifeng 475004,China) Abstract:In order to improve the search ability and optimization accuracy of cuckoo search algorithm,the cuckoo search with dynamic inertia weight is proposed.By utilizing the dynamic inertia weight,the improved cuckoo search updates the next nest position based on the former best nest position that has been saved with dynamic inertia weight, which can well balance the relation between population exploration and development capabilities.This paper also has a convergence analysis of the improved cuckoo search by the characteristic equation.The performance of the new method is compared with the basic cuckoo search,particle swarm optimization,ant colony optimization and other al- gorithms,showing that the improved cuckoo search algorithm can significantly reduce the number of iterations and running time,and can effectively improve the convergence speed and convergence precision. Keywords:cuckoo search algorithm;function optimization;Levy flight;dynamic inertia weight;population size; convergence;complexity;parameter selection 布谷鸟搜索算法是由剑桥大学学者Yang和拉 于解决函数优化问题[)]、工程结构优化问题[)、TSP 曼工程大学Deb于2009年基于对布谷鸟寻窝寄生 问题4)和PD控制器调整[)等多个领域。此外，通 幼卵行为的模拟，提出的一种新的全局优化算法，即 过改进算法参数提高算法性能也成为一个重要的研 Cuckoo Search(CS)算法[)。由于其具有控制参数 究领域。Walton对布谷鸟搜索算法的步长进行改 少、寻优能力强和简单易实施等特点，现已成功应用 进，增加了个体间的信息交流[6。Zheng在鸟窝位 置选择更新方式中加入了高斯扰动项，进而提出基 收稿日期：2014-09-30.网络出版日期：2015-06-30 于高斯扰动的布谷鸟搜索算法[】。苏芙华等通过 基金项目：河南省科技攻关重点基金资助项目(122102210201)：河南大引入动态局部搜索技术，进一步提高了布谷鸟搜索 学研究生教育综合改革基金资助项目(Y1427056). 通信作者：李煜E-mail:lyhenu@163.com. 算法的性能[)。针对算法在求解复杂函数时，后期
第 １０ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．４ ２０１５ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０９０４２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０６３０．１５５９．００４．ｈｔｍｌ 具有动态惯性权重的布谷鸟搜索算法 周欢１ ，李煜２ （１．河南大学 商学院，河南 开封 ４７５００４； ２．河南大学 管理科学与工程研究所，河南 开封 ４７５００４） 摘 要：为提高布谷鸟搜索算法的搜索能力和寻优精度，提出一种具有动态惯性权重的布谷鸟搜索算法。 该算法引 入动态惯性权重改进鸟窝位置的更新方式，依据动态惯性权重值保留上代鸟窝的最优位置并进行下一代位置更新， 从而有效平衡种群探索能力和开发能力之间的关系。 并利用特征方程对改进算法进行了收敛性分析。 仿真实验结 果表明，与基本布谷鸟搜索算法、粒子群算法和蚁群算法相比，改进后的布谷鸟搜索算法能显著减少迭代次数和运 行时间，有效提高算法的收敛速度和收敛精度。 关键词：布谷鸟搜索算法；函数优化；莱维飞行；动态惯性权重；种群规模；收敛性；复杂度；参数选取 中图分类号： ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０４⁃０６４５⁃０７ 中文引用格式：周欢，李煜． 具有动态惯性权重的布谷鸟搜索算法［Ｊ］． 智能系统学报， ２０１５， １０（４）： ６４５⁃６５１． 英文引用格式：ＺＨＯＵ Ｈｕａｎ， ＬＩ Ｙｕ． Ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（４）： ６４５⁃６５１． Ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ ＺＨＯＵ Ｈｕａｎ １ ， ＬＩ Ｙｕ ２ （１．Ｓｃｈｏｏｌ ｏｆ Ｂｕｓｉｎｅｓｓ Ａｄｍｉｎｉｓｔｒａｔｉｏｎ， Ｈｅ＇ｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｋａｉｆｅｎｇ ４７５００４， Ｃｈｉｎａ； ２．Ｒｅｓｅａｒｃｈ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｅ＇ｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｋａｉｆｅｎｇ ４７５００４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｓｅａｒｃｈ ａｂｉｌｉｔｙ ａｎｄ ｏｐｔｉｍｉｚａｔｉｏｎ ａｃｃｕｒａｃｙ ｏｆ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ， ｔｈｅ ｃｕｃｋｏｏ ｓｅａｒｃｈ ｗｉｔｈ ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ ｉｓ ｐｒｏｐｏｓｅｄ． Ｂｙ ｕｔｉｌｉｚｉｎｇ ｔｈｅ ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ， ｔｈｅ ｉｍｐｒｏｖｅｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ ｕｐｄａｔｅｓ ｔｈｅ ｎｅｘｔ ｎｅｓｔ ｐｏｓｉｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ ｆｏｒｍｅｒ ｂｅｓｔ ｎｅｓｔ ｐｏｓｉｔｉｏｎ ｔｈａｔ ｈａｓ ｂｅｅｎ ｓａｖｅｄ ｗｉｔｈ ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ， ｗｈｉｃｈ ｃａｎ ｗｅｌｌ ｂａｌａｎｃｅ ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｐｏｐｕｌａｔｉｏｎ ｅｘｐｌｏｒａｔｉｏｎ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ ｃａｐａｂｉｌｉｔｉｅｓ． Ｔｈｉｓ ｐａｐｅｒ ａｌｓｏ ｈａｓ ａ ｃｏｎｖｅｒｇｅｎｃｅ ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ ｂｙ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｅｑｕａｔｉｏｎ． Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｎｅｗ ｍｅｔｈｏｄ ｉｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｂａｓｉｃ ｃｕｃｋｏｏ ｓｅａｒｃｈ， ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｏｔｈｅｒ ａｌ⁃ ｇｏｒｉｔｈｍｓ， ｓｈｏｗｉｎｇ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｃａｎ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｒｅｄｕｃｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｉｔｅｒａｔｉｏｎｓ ａｎｄ ｒｕｎｎｉｎｇ ｔｉｍｅ， ａｎｄ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ ａｎｄ ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｅｃｉｓｉｏｎ． Ｋｅｙｗｏｒｄｓ：ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ； ｆｕｎｃｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ； Ｌéｖｙ ｆｌｉｇｈｔ； ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ； ｐｏｐｕｌａｔｉｏｎ ｓｉｚｅ； ｃｏｎｖｅｒｇｅｎｃｅ； ｃｏｍｐｌｅｘｉｔｙ； ｐａｒａｍｅｔｅｒ ｓｅｌｅｃｔｉｏｎ 收稿日期：２０１４⁃０９⁃３０． 网络出版日期：２０１５⁃０６⁃３０． 基金项目：河南省科技攻关重点基金资助项目（１２２１０２２１０２０１）；河南大 学研究生教育综合改革基金资助项目（Ｙ１４２７０５６）． 通信作者：李煜．Ｅ⁃ｍａｉｌ：ｌｙｈｅｎｕ＠ １６３．ｃｏｍ． 布谷鸟搜索算法是由剑桥大学学者 Ｙａｎｇ 和拉 曼工程大学 Ｄｅｂ 于 ２００９ 年基于对布谷鸟寻窝寄生 幼卵行为的模拟，提出的一种新的全局优化算法，即 Ｃｕｃｋｏｏ Ｓｅａｒｃｈ（ＣＳ） 算法［１］ 。 由于其具有控制参数 少、寻优能力强和简单易实施等特点，现已成功应用 于解决函数优化问题［２］ 、工程结构优化问题［３］ 、ＴＳＰ 问题［４］和 ＰＩＤ 控制器调整［５］ 等多个领域。 此外，通 过改进算法参数提高算法性能也成为一个重要的研 究领域。 Ｗａｌｔｏｎ 对布谷鸟搜索算法的步长进行改 进，增加了个体间的信息交流［６］ 。 Ｚｈｅｎｇ 在鸟窝位 置选择更新方式中加入了高斯扰动项，进而提出基 于高斯扰动的布谷鸟搜索算法［７］ 。 苏芙华等通过 引入动态局部搜索技术，进一步提高了布谷鸟搜索 算法的性能［８］ 。 针对算法在求解复杂函数时，后期
·646. 智能系统学报 第10卷 收敛精度不高、迭代次数多、运算时间长等问题，本 速度钳制操作的控制机制，通过惯性权重的调整来 文提出一种基于函数优化的具有动态惯性权重的布 控制算法的局部和全局寻优能力。 谷鸟(cuckoo search with dynamic inertia weight,简称 动态变化惯性权重主要有以下几类： WCS)算法，通过加入动态惯性权重对鸟窝位置进 线性递减w的取值从较大值线性递减到一个 行更新，有效平衡局部搜索和全局搜索之间的关系。 较小的值[)： 实验结果表明，WCS算法能够有效提高算法的收敛 n,-t e(t)=(w(0)-w(n,)) +0(n,) 精度，减少算法的运行时间，具有较好的优化性能。 n w(0)>w(n,) 1基本布谷鸟算法 式中：n,为最大迭代次数，0(0)为初始惯性权重值， 布谷鸟算法源于对布谷鸟繁育行为的模拟，是 w(n,)为最终惯性权重值，w(t)为第t次的惯性权重 新型有效的全局优化算法。其原理是将布谷鸟所选 值，线性权重值一般从0.9递减为0.4。 宿主的鸟窝映射为空间中的解，用宿主鸟巢所在位 非线性递减0从较大值非线性递减到一个较 置的优劣表示解的适应度值，布谷鸟搜索和选择鸟 小值1： 窝的过程就是算法的搜索和优化过程[。 (o(t)-0.4)(n-t) 0(t+1)= 布谷鸟算法基于3个理想规则山： n,+0.4 规则1每只布谷鸟每次产一个卵，并随机选择 模糊调整由Eberhart和Shi(1998)采用模糊系 鸟巢孵化它； 统提出的具有动态调整特征的自适应惯性权重1) 规则2在随机选择的一组鸟巢中，最好的鸟巢 但其参数较多，增加了算法的复杂度和实现难度。 被保留至下一代： 随机调整Eberhart等II6]提出一种动态惯性权 规则3可选择的寄生巢的数量是固定的，寄生 重的方法，每次迭代都随机选取高斯分布中的一个 巢主人发现外来鸟蛋的概率为P,其中0≤P。≤1。 惯性权重值，较大的惯性权重和较小的惯性权重随 机出现。较大的惯性权重可以避免算法在初期陷入 基于这3个理想规则，Yang等采用式(1)对 局部最优，同时较小的惯性权重可以解决后期收敛 下一代鸟巢位置X+)进行更新： 精度不高等问题)。 X*)=Xo+a⊕Ley(A) (1) 基于以上分析，本文选取动态惯性权重中的随 式中：t为当前迭代次数，α为步长控制量，在大多 机调整惯性权重对布谷鸟算法进行改进。随机调整 数情况下，取a=I。⊕为点对点乘法，Levy(入)为 的惯性权重服从高斯分布即：W~N(0,σ)。较大 随机搜索路径，属于随机行走，采用莱维飞行(Levy) 的惯性权重和较小的惯性权重都会随机出现，使得 机制)，其行走的步长满足一个重尾的稳定分布。 算法能够实现局部搜索和全局搜索的平衡。随机惯 式(1)本质为随机行走方程，一般情况下，一个随机 性策略地的更新公式为 行走为一个马尔可夫链，其未来位置取决于当前位 w=rim+(rma-Tim）·normrnd（)+orandn() 置（式(1）的第1项)和转移概率（第2项）。 式中：T。表示惯性权重的最小值，r表示惯性权 基本布谷鸟搜索算法，按照更新式(1)对下一 重的最大值，normrnd()为服从均匀分布的随机数， 代的鸟窝位置进行更新，并且计算目标函数的适应 randn()为服从正态分布的随机数，o用来控制惯 度值，如果优于上一代适应度值，则保留到下一代， 性权重与期望值之间的偏差程度。 否则保持原来位置不变。随机产生的数值r服从0 因此，具有动态惯性权重的布谷鸟搜索算法采 到1均匀分布，并将其与鸟巢主人发现外来鸟蛋的 用动态惯性权重中的随机调整的惯性权重改进鸟窝 概率P.相比较，若r>P,则重新产生一组初始解向 位置更新方式，WCS算法实现流程如下： 量，否则保持不变。 1)确定目标函数f(X),设置优化函数的定义域 2具有动态惯性权重的布谷鸟搜索算法 [-L,L],维度d,发现概率P。和种群数量n。初始 化种群，随机并产生d维向量，即X= 2.1动态惯性权重的选择 (x1,x2,…,x4)T,n个鸟窝的初始位置为：X(i= 动态惯性改进策略是一种控制种群探索能力和 1,2,…,n); 开发能力的机制，能够有效提高算法的搜索能力，平 2)计算每个鸟窝的目标函数值，并记录当前鸟 衡局部搜索和全局搜索之间的关系。Shi和Eber- 窝位置的最优解； hart)将惯性权重引入粒子群算法，作为一种取代 3)保留上代最优鸟窝位置，产生随机动态惯性
收敛精度不高、迭代次数多、运算时间长等问题，本 文提出一种基于函数优化的具有动态惯性权重的布 谷鸟（ｃｕｃｋｏｏ ｓｅａｒｃｈ ｗｉｔｈ ｄｙｎａｍｉｃ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ，简称 ＷＣＳ）算法，通过加入动态惯性权重对鸟窝位置进 行更新，有效平衡局部搜索和全局搜索之间的关系。 实验结果表明，ＷＣＳ 算法能够有效提高算法的收敛 精度，减少算法的运行时间，具有较好的优化性能。 １ 基本布谷鸟算法 布谷鸟算法源于对布谷鸟繁育行为的模拟，是 新型有效的全局优化算法。 其原理是将布谷鸟所选 宿主的鸟窝映射为空间中的解，用宿主鸟巢所在位 置的优劣表示解的适应度值，布谷鸟搜索和选择鸟 窝的过程就是算法的搜索和优化过程［９］ 。 布谷鸟算法基于 ３ 个理想规则［１］ ： 规则 １ 每只布谷鸟每次产一个卵，并随机选择 鸟巢孵化它； 规则 ２ 在随机选择的一组鸟巢中，最好的鸟巢 被保留至下一代； 规则 ３ 可选择的寄生巢的数量是固定的，寄生 巢主人发现外来鸟蛋的概率为 Ｐａ ， 其中 ０≤ Ｐａ ≤１。 基于这 ３ 个理想规则，Ｙａｎｇ 等［１］ 采用式（１）对 下一代鸟巢位置 Ｘ （ ｔ＋ １）进行更新： Ｘ （ｔ＋１） ｉ ＝ Ｘ （ｔ） ｉ ＋ α Ｌｅｖｙ（λ） （１） 式中：ｔ 为当前迭代次数， α 为步长控制量，在大多 数情况下，取 α ＝ １。 ⊕为点对点乘法，Ｌｅｖｙ（ λ ）为 随机搜索路径，属于随机行走，采用莱维飞行（Ｌｅｖｙ） 机制［１０］ ，其行走的步长满足一个重尾的稳定分布。 式（１）本质为随机行走方程，一般情况下，一个随机 行走为一个马尔可夫链，其未来位置取决于当前位 置（式（１）的第 １ 项）和转移概率（第 ２ 项） ［１１］ 。 基本布谷鸟搜索算法，按照更新式（１） 对下一 代的鸟窝位置进行更新，并且计算目标函数的适应 度值，如果优于上一代适应度值，则保留到下一代， 否则保持原来位置不变。 随机产生的数值 ｒ 服从 ０ 到 １ 均匀分布，并将其与鸟巢主人发现外来鸟蛋的 概率 Ｐａ 相比较，若 ｒ＞Ｐａ ，则重新产生一组初始解向 量，否则保持不变。 ２ 具有动态惯性权重的布谷鸟搜索算法 ２．１ 动态惯性权重的选择 动态惯性改进策略是一种控制种群探索能力和 开发能力的机制，能够有效提高算法的搜索能力，平 衡局部搜索和全局搜索之间的关系。 Ｓｈｉ 和 Ｅｂｅｒ⁃ ｈａｒｔ ［１２］将惯性权重引入粒子群算法，作为一种取代 速度钳制操作的控制机制，通过惯性权重的调整来 控制算法的局部和全局寻优能力。 动态变化惯性权重主要有以下几类： 线性递减 ｗ 的取值从较大值线性递减到一个 较小的值［１３］ ： ｗ（ｔ） ＝ （ｗ（０） － ｗ（ｎｔ）） ｎｔ － ｔ ｎｔ ＋ ｗ（ｎｔ）， ｗ（０） ＞ ｗ（ｎｔ） 式中：ｎｔ为最大迭代次数，ｗ（０）为初始惯性权重值， ｗ（ｎｔ）为最终惯性权重值，ｗ（ｔ）为第 ｔ 次的惯性权重 值，线性权重值一般从 ０．９ 递减为 ０．４。 非线性递减 ｗ 从较大值非线性递减到一个较 小值［１４］ ： ｗ（ｔ ＋ １） ＝ （ｗ（ｔ） － ０．４）（ｎｔ － ｔ） ｎｔ ＋ ０．４ 模糊调整 由 Ｅｂｅｒｈａｒｔ 和 Ｓｈｉ（１９９８）采用模糊系 统提出的具有动态调整特征的自适应惯性权重［１５］ ， 但其参数较多，增加了算法的复杂度和实现难度。 随机调整 Ｅｂｅｒｈａｒｔ 等［１６］ 提出一种动态惯性权 重的方法，每次迭代都随机选取高斯分布中的一个 惯性权重值，较大的惯性权重和较小的惯性权重随 机出现。 较大的惯性权重可以避免算法在初期陷入 局部最优，同时较小的惯性权重可以解决后期收敛 精度不高等问题［１７］ 。 基于以上分析，本文选取动态惯性权重中的随 机调整惯性权重对布谷鸟算法进行改进。 随机调整 的惯性权重服从高斯分布即：ｗ ～ Ｎ（ θ ， σ ）。 较大 的惯性权重和较小的惯性权重都会随机出现，使得 算法能够实现局部搜索和全局搜索的平衡。 随机惯 性策略 ｗ 的更新公式为 ｗ ＝ ｒｍｉｎ ＋ （ｒｍａｘ － ｒｍｉｎ ）·ｎｏｒｍｒｎｄ （） ＋ σｒａｎｄｎ（） 式中： ｒｍｉｎ 表示惯性权重的最小值， ｒｍａｘ 表示惯性权 重的最大值，ｎｏｒｍｒｎｄ（ ）为服从均匀分布的随机数， ｒａｎｄｎ（ ） 为服从正态分布的随机数， σ 用来控制惯 性权重与期望值之间的偏差程度。 因此，具有动态惯性权重的布谷鸟搜索算法采 用动态惯性权重中的随机调整的惯性权重改进鸟窝 位置更新方式，ＷＣＳ 算法实现流程如下： １）确定目标函数 ｆ（Ｘ），设置优化函数的定义域 ［－Ｌ，Ｌ］，维度 ｄ，发现概率 Ｐａ 和种群数量 ｎ。 初始 化 种 群， 随 机 并 产 生 ｄ 维 向 量， 即 Ｘ ＝ （ｘ１ ，ｘ２ ，…，ｘｄ ） Ｔ ， ｎ 个鸟窝的初始位置为： Ｘｉ （ ｉ ＝ １，２，…，ｎ ）； ２）计算每个鸟窝的目标函数值，并记录当前鸟 窝位置的最优解； ３）保留上代最优鸟窝位置，产生随机动态惯性 ·６４６· 智 能 系 统 学 报 第 １０ 卷
第4期 李煜，等：具有动态惯性权重的布谷鸟搜索算法 ·647. 权重w~N(9,σ)，采用加入动态惯性权重策略的 f(n))。在第2个新解阶段，生成新解的执行时间为 位置更新公式(2)对一代鸟窝位置进行更新： 专5，时间复杂度为O(N(专5n+f(n)+专3+专4n)= X)=w·xo+a①Ley(A) (2) O(n+f(n))。记录最优鸟巢位置的时间复杂度为 4)将现有鸟窝位置与上一代鸟窝位置进行比 O(N(3+专n)=O(n),则对于每一代找到最优解 较，若现在位置较好，则将其作为当前的最优位置， 的总的时间复杂度为T(n)=3O(n+f(n))+ 否则最优位置不变： 0(n)=0(n+f(n)【 5)用一个随机数r,作为鸟窝主人发现外来鸟 同理，分析改进布谷鸟算法的流程，位置更新公 蛋的可能性，与发现概率P进行比较，若r≤P,则 式中加入动态惯性权重，设产生动态惯性权重的 记录当前最优值：若>P。,则返回2)，随机改变鸟窝 执行时间为专，种群数量、目标函数和最大迭代次数 位置，得到一组新的鸟窝位置： 不变。在第1个新解阶段，时间复杂度为 6)输出全局最优值。 O(N(,n+52n+f(n)+ξ3+4n))=O(n+f八n)), 2.2动态惯性权重的变化范围对优化效果的影响 第2个新解阶段，时间复杂度为O(N(5:n+sn+ 本文参考文献[18]对动态惯性权重范围的划 f(n)+专3+4n))=O(n+f(n))。因此，更新下一 分进行取值，使用表2中函数f和函数f2观察不同 代鸟窝位置的最终时间复杂度不变，仍为T(n)= 惯性权重的变化范围对优化效果的影响。参数设 O(n+f(n),与基本布谷鸟算法一致，改进后的算 置：种群大小为25，每次运行最大迭代次数为50，对 法没有增加时间复杂度。 每个函数优化50次。实验结果如表1所示。表中， 1表示惯性权重范围0~0.2,2表示0.2~0.9,3表示 3WCS算法的收敛性分析 0.9~1.2。实验结果表明，当取值在0.9~1.2时，算 标准布谷鸟算法是一种随机算法，文献[20]通 法找到最优结果的次数较少：当取值在0.2~0.9之 过建立Markov链模型，利用随机算法收敛的条件证 间时，算法能够找到最优结果，但是找到最优解的概 明了标准CS算法的收敛性，为CS算法全局收敛提 率不稳定：当取值在0~0.2时，算法能够找到最优 供了理论依据。 结果，准确率较高。因此，随机调整的惯性权重服从 文献[21]和[22]利用差分方程分别对蝙蝠算 高斯分布，且0取值为0~0.2，σ取值足够小以确保 法和粒子群算法的收敛性进行了深入分析，本文采 w不会显著大于1。 取同样的方法，通过建立差分方程对改进的布谷鸟 表1不同变化范围的惯性权重的优化效果 算法进行收敛性分析。改进布谷鸟算法采用式(2) Table 1 Optimization effect of inertia weight with 进行下一代鸟窝位置更新，式(2)表示第i个鸟巢在 different changing ranges t+1时刻的位置，a为步长控制量，Levy(入)是随机 惯性权重范围 1 2 3 搜索步长，即 平均迭代次数 2.4 3.414.9 准确率 1 12% 平均迭代次数2.68.5 Ly(）-0.01×1i5x(g-x0)(3) 2.9 准确率 16% 0 式中：u和v服从均匀分布，u~N(0,o),v~N(0, 2.3算法的时间复杂度分析 σ)，a通常取值为1，为简化计算，设0.01× 算法的时间复杂性可以从侧面反映算法收敛速 118 度的快慢，如果一个算法收敛，但需要无穷的迭代时 为一常量r1,g为第t代个体鸟巢最优位置，记为 间，那么这个算法不具有有效性。基本布谷鸟算法输 g6,第+1代鸟巢最优位置记为P6,式(2)可化为 入的种群规模为N,求解目标函数为f(x),最大迭代 X+)=0·Xo+r1·(g6-X0) (4) 次数为，根据基本布谷鸟算法的流程，假设产生均 X0+2)=0·X+》+1·(p6-X+) (5) 匀分布随机数的时间为专，下一代鸟窝位置由上代鸟 由式(4)和式(5)可得： 窝位置和Levy飞行机制得到，计算目标函数的时间 X+2)+(1+r1-0)·X+0+ 复杂度为O(N(,n+f(n)))=O(n+f(n)),更新式 (1-w)·X=rP6+r1g6 (6) (1)产生一组新解的时间为2，新的位置与上代位置 式(6)是一个二阶的常系数非齐次差分方程，求解 进行比较的执行时间为，若新位置较好，替换上代 其差分方程的特征方程得： 位置的执行时间为4，在第1个新解产生阶段，时间 A2+(1+0-r1)入+0-T1=0 复杂度为O(N(52n+f(n)+5+4n))=O(n+ 求解特征方程，得到△=(1+w-r1)2-4(w-r1)
权重 ｗ～Ｎ（ θ ， σ ），采用加入动态惯性权重策略的 位置更新公式（２）对一代鸟窝位置进行更新； Ｘ （ｔ＋１） ｉ ＝ ｗ·Ｘ （ｔ） ｉ ＋ α Ｌｅｖｙ（λ） （２） ４）将现有鸟窝位置与上一代鸟窝位置进行比 较，若现在位置较好，则将其作为当前的最优位置， 否则最优位置不变； ５）用一个随机数 ｒ，作为鸟窝主人发现外来鸟 蛋的可能性，与发现概率 Ｐａ 进行比较，若 ｒ≤ Ｐａ ，则 记录当前最优值；若 ｒ＞Ｐａ ，则返回 ２），随机改变鸟窝 位置，得到一组新的鸟窝位置； ６）输出全局最优值。 ２．２ 动态惯性权重的变化范围对优化效果的影响 本文参考文献［１８］ 对动态惯性权重范围的划 分进行取值，使用表 ２ 中函数 ｆ １和函数 ｆ ２观察不同 惯性权重的变化范围对优化效果的影响。 参数设 置：种群大小为 ２５，每次运行最大迭代次数为 ５０，对 每个函数优化 ５０ 次。 实验结果如表 １ 所示。 表中， １ 表示惯性权重范围 ０ ～ ０．２，２ 表示０．２～ ０．９，３ 表示 ０．９～１．２。 实验结果表明，当取值在 ０．９ ～ １．２ 时，算 法找到最优结果的次数较少；当取值在 ０．２ ～ ０．９ 之 间时，算法能够找到最优结果，但是找到最优解的概 率不稳定；当取值在 ０ ～ ０．２ 时，算法能够找到最优 结果，准确率较高。 因此，随机调整的惯性权重服从 高斯分布，且 θ 取值为 ０～０．２， σ 取值足够小以确保 ｗ 不会显著大于 １。 表 １ 不同变化范围的惯性权重的优化效果 Ｔａｂｌｅ １ Ｏｐｔｉｍｉｚａｔｉｏｎ ｅｆｆｅｃｔ ｏｆ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｃｈａｎｇｉｎｇ ｒａｎｇｅｓ ｆ 惯性权重范围 １ ２ ３ ｆ １ 平均迭代次数 ２．４ ３．４ １４．９ 准确率 １ １ ２％ ｆ ２ 平均迭代次数 ２．６ ８．５ ２．９ 准确率 １ ６％ ０ ２．３ 算法的时间复杂度分析 算法的时间复杂性可以从侧面反映算法收敛速 度的快慢，如果一个算法收敛，但需要无穷的迭代时 间，那么这个算法不具有有效性。 基本布谷鸟算法输 入的种群规模为 Ｎ，求解目标函数为 ｆ（ｘ），最大迭代 次数为 ｎ，根据基本布谷鸟算法的流程，假设产生均 匀分布随机数的时间为 ξ１ ，下一代鸟窝位置由上代鸟 窝位置和 Ｌｅｖｙ 飞行机制得到，计算目标函数的时间 复杂度为Ｏ（Ｎ（ξ１ ｎ ＋ ｆ（ｎ）））＝ Ｏ（ｎ ＋ ｆ（ｎ）），更新式 （１） 产生一组新解的时间为 ξ２ ，新的位置与上代位置 进行比较的执行时间为 ξ３ ，若新位置较好，替换上代 位置的执行时间为 ξ４ ，在第 １ 个新解产生阶段，时间 复 杂 度 为 Ｏ（Ｎ（ξ２ ｎ ＋ ｆ（ｎ） ＋ ξ３ ＋ ξ４ ｎ） ） ＝Ｏ（ｎ ＋ ｆ（ｎ））。 在第 ２ 个新解阶段，生成新解的执行时间为 ξ５ ，时间复杂度为 Ｏ（Ｎ（ξ５ ｎ ＋ ｆ（ｎ） ＋ ξ３ ＋ ξ４ ｎ） ＝ Ｏ（ｎ ＋ｆ（ｎ））。 记录最优鸟巢位置的时间复杂度为 Ｏ（Ｎ（ξ３ ＋ ξ４ ｎ） ＝ Ｏ（ｎ），则对于每一代找到最优解 的总 的 时 间 复 杂 度 为 Ｔ（ｎ） ＝ ３Ｏ（ｎ ＋ ｆ（ｎ）） ＋ Ｏ（ｎ） ＝Ｏ（ｎ ＋ ｆ （ｎ）） ［１９］ 。 同理，分析改进布谷鸟算法的流程，位置更新公 式中加入动态惯性权重，设产生动态惯性权重 ｗ 的 执行时间为 ξ，种群数量、目标函数和最大迭代次数 不变。 在 第 １ 个 新 解 阶 段， 时 间 复 杂 度 为 Ｏ（Ｎ（ ξ１ ｎ ＋ξ２ ｎ ＋ ｆ（ｎ） ＋ ξ３ ＋ ξ４ ｎ）） ＝ Ｏ（ｎ ＋ ｆ（ｎ））， 第 ２ 个新解阶段，时间复杂度为 Ｏ（Ｎ（ξ１ ｎ ＋ ξ５ ｎ ＋ ｆ（ｎ） ＋ ξ３ ＋ ξ４ ｎ）） ＝ Ｏ（ｎ ＋ ｆ（ｎ））。 因此，更新下一 代鸟窝位置的最终时间复杂度不变， 仍为 Ｔ（ｎ） ＝ Ｏ（ｎ ＋ ｆ（ｎ）），与基本布谷鸟算法一致，改进后的算 法没有增加时间复杂度。 ３ ＷＣＳ 算法的收敛性分析 标准布谷鸟算法是一种随机算法，文献［２０］通 过建立 Ｍａｒｋｏｖ 链模型，利用随机算法收敛的条件证 明了标准 ＣＳ 算法的收敛性，为 ＣＳ 算法全局收敛提 供了理论依据。 文献［２１］和［２２］利用差分方程分别对蝙蝠算 法和粒子群算法的收敛性进行了深入分析，本文采 取同样的方法，通过建立差分方程对改进的布谷鸟 算法进行收敛性分析。 改进布谷鸟算法采用式（２） 进行下一代鸟窝位置更新，式（２）表示第 ｉ 个鸟巢在 ｔ＋１ 时刻的位置， α 为步长控制量，Ｌｅｖｙ（ λ ）是随机 搜索步长，即 Ｌｅｖｙ（λ） ～ ０．０１ × ｕ ｜ ｖ ｜ １／ β × （ｇｂｅｓｔ － Ｘ （ｔ） ｉ ） （３） 式中：ｕ 和 ｖ 服从均匀分布，ｕ ～ Ｎ（０， σ ２ ｕ ），ｖ ～ Ｎ（０， σ ２ ｖ ）， α 通常取值为 １，为简化计算，设 ０．０１ × ｕ ｜ ｖ ｜ １／ β 为一常量 ｒ １ ， ｇｂｅｓｔ 为第 ｔ 代个体鸟巢最优位置，记为 ｇｂ，第 ｔ＋１ 代鸟巢最优位置记为 ｐｂ，式（２）可化为 Ｘ （ｔ＋１） ＝ ｗ·Ｘ （ｔ） ＋ ｒ１·（ｇｂ － Ｘ （ｔ） ） （４） Ｘ （ｔ＋２） ＝ ｗ·Ｘ （ｔ＋１） ＋ ｒ１·（ｐｂ － Ｘ （ｔ＋１） ） （５） 由式（４）和式（５）可得： Ｘ （ｔ＋２） ＋ （１ ＋ ｒ１ － ｗ）·Ｘ （ｔ＋１） ＋ （ｒ１ － ｗ）·Ｘ （ｔ） ＝ ｒ１ ｐｂ ＋ ｒ１ ｇｂ （６） 式（６）是一个二阶的常系数非齐次差分方程，求解 其差分方程的特征方程得： λ ２ ＋ （１ ＋ ｗ － ｒ１ ）λ ＋ ｗ － ｒ１ ＝ ０ 求解特征方程，得到 △ ＝ （１ ＋ ｗ － ｒ１ ） ２ － ４（ｗ － ｒ１ ）， 第 ４ 期 李煜，等：具有动态惯性权重的布谷鸟搜索算法 ·６４７·
·648: 智能系统学报 第10卷 因为△=(w-1-1)2≥0，所以只需要考虑以下2 3x2-14y+6xy+3y2)][30+(2x- 种情况： 3y)2(18-32x+12x2+48-36xy+27y2)] (a)当△=(w-r1-1)2=0时，即0-1-1=0。 x,y∈[-2,2] 入，和入2为特征方程的2个根，若入，和入2为实数， 4.1WCS算法与CS算法的比较 ‖A,‖、‖入2I分别表示入和入，的绝对值，若为 算法参数设置为：种群规模n=25,发现概率 复数，则表示入，和入2的模值。 P,=0.25。惯性权重从高斯分布中取值并随机调 由△=0得：入，=入2=-1。此时Xo=(A。+A1 整。每个函数分别进行30次独立仿真实验，平均时 t)入‘，A。、A1为待定系数，计算可得： 间为算法找到最优解所用时间的平均值，其单位为 A0=x(0) 秒。平均迭代次数为算法收敛到最优解的代数的平 41=(1-0-1)x(0)-r186 均值。进化代数为算法找到最优解的最大迭代次数 (b)当△>0时，此时X0=A。+A1+A23, 的最小值。准确率为算法找到最优解的次数与运行 A。A,和A2为待定系数，计算得到： 总次数的百分比。WCS算法与CS算法比较，如图 -(1+0-r1)+√△ 1~6所示，仿真运算结果如表2所示。 A,= 1.0m 0.8 12= -（1+0-r)-√△ 2 0.6 当t→0时，有极限且趋向于有限值，表示迭代 0.4 0.2 收敛，由此可知，若上面2种情况中X0收敛，则需满 足条件1入，‖0时，收敛区域需要满足：-1<r1-w<1。综合 g0.995 ----CS 上面2种情况，收敛区域为-1≤T1-w<1。 0.990 WCS 4 仿真实验 m0.985 0.980 为评估WCS算法的性能，采用5个典型的测试 函数进行验证。运行环境：CPU为B940@2.00GHz, 0.975 2345678910 内存2GB,Matlab R2013a编程环境。其中，函数f~ 迭代次数 ,的最优值分别为1、3600、00和-3，测试函数~ 图2方算法收敛状态对比图 ,的数学表达式和自变量的取值范围如下： Fig.2 Convergence state of CS and WCS onf f=0.5- sin√2+y-0.5 4.0r×10 1-0.001(x2+y2) x,y∈[-4,4] 3.5 0 3 万=[a05+2++(+9 3.0 ----CS WCS x,y∈[-5.12,5.12] 2.5 f5=10cos(2Tx)-10cos(2my）-x2-y2-20 2.0 x,y∈[-5.12,5.12] 1.5 i=402re-Tco-(停）+1 1.0 .0 2.0 3.04.05.06.0 迭代次数 x∈[-600,600] 图32算法收敛对比图 5=-[1+(x+y+1)2(19-14x+ Fig.3 Convergence state of CS and WCS onf
因为 △ ＝ （ｗ － ｒ１ － １） ２ ≥ ０，所以只需要考虑以下 ２ 种情况： （ａ）当 △ ＝ （ｗ － ｒ１ － １） ２ ＝ ０ 时，即 ｗ－ｒ１ －１ ＝ ０。 λ１ 和 λ２ 为特征方程的 ２ 个根，若 λ１ 和 λ２ 为实数， ‖ λ１‖、‖ λ２‖分别表示 λ １和 λ ２的绝对值，若为 复数，则表示 λ １和 λ２ 的模值。 由△ ＝ ０ 得： λ１ ＝ λ２ ＝ －１。 此时 Ｘ （ｔ） ＝ （ Ａ０ ＋Ａ１ ｔ） λ ｔ ， Ａ０ 、 Ａ１ 为待定系数，计算可得： Ａ０ ＝ ｘ（０） Ａ１ ＝ （ｒ１ － ｗ － １）ｘ（０） － ｒ１ ｇｂ { （ｂ）当△＞０ 时，此时 Ｘ （ｔ） ＝ Ａ０ ＋ Ａ１λ ｔ １ ＋ Ａ２λ ｔ ２ ， Ａ０ 、Ａ１ 和 Ａ２ 为待定系数，计算得到： λ１ ＝ － （１ ＋ ｗ － ｒ１ ） ＋ △ ２ λ２ ＝ － （１ ＋ ｗ － ｒ１ ） － △ ２ ì î í ï ï ï ï ïï 当 ｔ → ∞ 时，有极限且趋向于有限值，表示迭代 收敛，由此可知，若上面 ２ 种情况中 Ｘ （ｔ） 收敛，则需满 足条件 ‖λ１‖ ＜ １，‖λ２‖ ＜１ ［１９］ 。 当 ｍａｘ（‖ λ１‖， ‖ λ２‖）＝ １，则有： ｌｉｍ ｔ→∞ Ｘ （ｔ） ＝ Ａ０ ＋ Ａ１ ＋ Ａ３ ， ｌｉｍ ｔ→∞ Ｘ （ｔ） ＝ Ａ０ ＋ Ａ３ 或者ｌｉｍ ｔ→∞ Ｘ （ｔ） ＝ Ａ０ ＋ Ａ２ ， 粒子的轨迹收敛［２０］ 。 因此，当△＝ ０ 时，收敛区域为 ｗ － ｒ１ －１ ＝ ０；当 △＞０ 时，收敛区域需要满足： －１＜ ｒ １ － ｗ ＜１。 综合 上面 ２ 种情况，收敛区域为－１≤ ｒ１ － ｗ ＜１。 ４ 仿真实验 为评估 ＷＣＳ 算法的性能，采用 ５ 个典型的测试 函数进行验证。 运行环境：ＣＰＵ 为 Ｂ９４０＠ ２．００ ＧＨｚ， 内存 ２ ＧＢ，Ｍａｔｌａｂ Ｒ２０１３ａ 编程环境。 其中，函数ｆ １ ～ ｆ ５的最优值分别为 １、３ ６００、０、０ 和－３，测试函数 ｆ １ ～ ｆ ５的数学表达式和自变量的取值范围如下： ｆ １ ＝ ０．５ － ｓｉｎ ｘ ２ ＋ ｙ ２ － ０．５ １ － ０．００１（ｘ ２ ＋ ｙ ２ ） ｘ，ｙ ∈ ［ － ４，４］ ｆ ２ ＝ ［ ３ ０．０５ ＋ （ｘ ２ ＋ ｙ ２ ） ］ ２ ＋ （ｘ ２ ＋ ｙ ２ ） ２ ｘ，ｙ ∈ ［ － ５．１２，５．１２］ ｆ ３ ＝ １０ｃｏｓ（２πｘ） － １０ｃｏｓ（２πｙ） － ｘ ２ － ｙ ２ － ２０ ｘ，ｙ ∈ ［ － ５．１２，５．１２］ ｆ ４ ＝ １ ４ ０００∑ Ｄ ｉ ＝ １ ｘ ２ ｉ － ∏ Ｄ ｉ ＝ １ ｃｏｓ（ ｘｉ ｉ ） ＋ １ ｘ ∈ ［ － ６００，６００］ ｆ ５ ＝ － ［１ ＋ （ｘ ＋ ｙ ＋ １） ２ （１９ － １４ｘ ＋ ３ｘ ２ － １４ｙ ＋ ６ｘｙ ＋ ３ｙ ２ ）］［３０ ＋ （２ｘ － ３ｙ） ２ （１８ － ３２ｘ ＋ １２ｘ ２ ＋ ４８ － ３６ｘｙ ＋ ２７ｙ ２ ）］ ｘ，ｙ ∈ ［ － ２，２］ ４．１ ＷＣＳ 算法与 ＣＳ 算法的比较 算法参数设置为：种群规模 ｎ ＝ ２５，发现概率 Ｐａ ＝ ０．２５。 惯性权重从高斯分布中取值并随机调 整。 每个函数分别进行 ３０ 次独立仿真实验，平均时 间为算法找到最优解所用时间的平均值，其单位为 秒。 平均迭代次数为算法收敛到最优解的代数的平 均值。 进化代数为算法找到最优解的最大迭代次数 的最小值。 准确率为算法找到最优解的次数与运行 总次数的百分比。 ＷＣＳ 算法与 ＣＳ 算法比较，如图 １～６ 所示，仿真运算结果如表 ２ 所示。 图 １ ｆ １图像 Ｆｉｇ．１ Ｉｍａｇｅ ｏｆ ｆ １ 图 ２ ｆ １ 算法收敛状态对比图 Ｆｉｇ．２ Ｃｏｎｖｅｒｇｅｎｃｅ ｓｔａｔｅ ｏｆ ＣＳ ａｎｄ ＷＣＳ ｏｎ ｆ １ 图 ３ ｆ ２ 算法收敛对比图 Ｆｉｇ．３ Ｃｏｎｖｅｒｇｅｎｃｅ ｓｔａｔｅ ｏｆ ＣＳ ａｎｄ ＷＣＳ ｏｎ ｆ ２ ·６４８· 智 能 系 统 学 报 第 １０ 卷
第4期 李煜，等：具有动态惯性权重的布谷鸟搜索算法 ·649 其中，x,y∈[-5.12,5.12]，该函数是多峰函数，有 4个局部极值点分别为：(-5.12,5.12)、(-5.12， -2 -5.12)、(5.12,5.12)和(5.12，-5.12)，函数的全局 ---CS A WCS 最优值3600，最优解位置为(0,0)。运行WCS算 法很快就可以收敛到最优解，函数方，收敛性状态对 -6 比如图3所示，其余函数方~∫5的收敛对比见图4~ 6,运算结果见表2。 -8 以上函数收敛图表明，改进后的算法和基本算 -9 0 8 1012 法相比，迭代次数更少，收敛速度更快，收敛精度更 迭代次数 高，具有更好的优化性能。 图4方算法收敛对比图 表2WCS算法与CS算法结果比较测试函数 Fig.4 Convergence state of CS and WCS onf Table 2 Comparison of WCS with CS 平均 平均迭 009-000 进化 函数 准确率/% 时间/s 代次数 代数 -2 CS CS 9.996411.23332500 83.33 3 WCS WCS0.17024.73333 50 100.00 CS 1.02164.96667 300 13.33 分 WCS0.09353.6666720 90.00 -6 CS 2.218912.7667 600 30.00 -8 WCS0.3154 7.9 70 83.33 CS3.951519.96671100 33.33 0 68101214 f 迭代次数 WCS0.84869.43333200 93.33 CS0.04524.466750 100 图54算法收敛对比图 WCS0.04335.9666740 100 Fig.5 Convergence state of CS and WCS onf 表2运算结果表明，对于5个测试函数，改进后 -3 20809000000-000000 的算法找到最优解的次数更多，时间更短，相比于基 =4 CS 本算法找到最优解的准确率更高。当基本CS算法 -WCS -5 面对较为复杂的函数优化问题时，如，增加迭代次 坦 -6 数为2500，基本算法运行时间是改进后算法的58.7 倍，收敛到最优解的迭代次数是改进后算法的2.4 -8 中 倍，准确率只有改进后算法的83%。因此，改进后 9 的算法可以更好地解决函数优化问题。 100 4.2WCS算法与其他算法的比较 1015 2025 迭代次数 用以上函数对WCS算法与CS算法、粒子群算法 图6方5算法收敛对比图 (PSO)、蚁群算法(ACO)、引力搜索算法(GSA)和蝙 Fig.6 Convergence state of CS and WCS onfs 蝠算法(BA)进行性能测试，运算结果如表3所示。 其中，为了更加公平地测试算法性能，每个算法 1)Schaffer函数 独立运行50次，种群数量都为50，迭代次数1000。 f(x,y）=0.5-sin+-0.5 CS算法和WCS算法参数设置为：发现概率P,=0.25。 1+0.001(x2+y2) PS0参数设置为w=0.729,c,=c2=1.494452)。蚁群 其中，x,y∈[-4,4]，函数最优解为1，最优解位置 算法参数设置为：a=B=1,r=0.5,p=0.7,Q= 为(0,0)，运行WCS算法很快找到最优解1。函数 12]。引力搜索算法参数设置为：T=1000,G= 图像如图1所示，算法收敛状态对比见图2，函数运 100,a=50。蝙蝠算法参数设置为：A=0.25,T:= 算结果见表2。 0.5,a=y=0.9251。 2)Needle--in-haystack函数 实验结果表明，对于函数~5，相比于其他算 法，WCS算法能够很快找到最优解。蚁群算法表现 f(x,y)=[ 0.05+(x2+y2) +(x2+y2)2 次之，对于∫~可以收敛到最优解，但对∫求解精度
图 ４ ｆ ３ 算法收敛对比图 Ｆｉｇ．４ Ｃｏｎｖｅｒｇｅｎｃｅ ｓｔａｔｅ ｏｆ ＣＳ ａｎｄ ＷＣＳ ｏｎ ｆ ３ 图 ５ ｆ ４ 算法收敛对比图 Ｆｉｇ．５ Ｃｏｎｖｅｒｇｅｎｃｅ ｓｔａｔｅ ｏｆ ＣＳ ａｎｄ ＷＣＳ ｏｎ ｆ ４ 图 ６ ｆ ５ 算法收敛对比图 Ｆｉｇ．６ Ｃｏｎｖｅｒｇｅｎｃｅ ｓｔａｔｅ ｏｆ ＣＳ ａｎｄ ＷＣＳ ｏｎ ｆ ５ １）Ｓｃｈａｆｆｅｒ 函数 ｆ １（ｘ，ｙ） ＝ ０．５ － ｓｉｎ ｘ ２ ＋ ｙ ２ － ０．５ １ ＋ ０．００１（ｘ ２ ＋ ｙ ２ ） 其中， ｘ， ｙ ∈ ［－４，４］，函数最优解为 １，最优解位置 为（０，０），运行 ＷＣＳ 算法很快找到最优解 １。 函数 图像如图 １ 所示，算法收敛状态对比见图 ２，函数运 算结果见表 ２。 ２）Ｎｅｅｄｌｅ－ｉｎ－ｈａｙｓｔａｃｋ 函数 ｆ １（ｘ，ｙ） ＝ ［ ３ ０．０５ ＋ （ｘ ２ ＋ ｙ ２ ） ］ ２ ＋ （ｘ ２ ＋ ｙ ２ ） ２ 其中， ｘ， ｙ ∈［－５．１２，５．１２］，该函数是多峰函数，有 ４ 个局部极值点分别为：（ － ５． １２， ５． １２）、（ － ５． １２， －５．１２） 、（５．１２，５．１２）和（５．１２，－５．１２），函数的全局 最优值 ３ ６００，最优解位置为（０，０）。 运行 ＷＣＳ 算 法很快就可以收敛到最优解，函数 ｆ ２ 收敛性状态对 比如图 ３ 所示，其余函数 ｆ ３ ～ ｆ ５ 的收敛对比见图 ４～ ６，运算结果见表 ２。 以上函数收敛图表明，改进后的算法和基本算 法相比，迭代次数更少，收敛速度更快，收敛精度更 高，具有更好的优化性能。 表 ２ ＷＣＳ 算法与 ＣＳ 算法结果比较测试函数 Ｔａｂｌｅ ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ＷＣＳ ｗｉｔｈ ＣＳ 函数 平均 时间／ ｓ 平均迭 代次数 进化 代数 准确率／ ％ ｆ １ ＣＳ ９．９９６ ４ １１．２３３ ３ ２ ５００ ８３．３３ ＷＣＳ ０．１７０ ２ ４．７３３ ３３ ５０ １００．００ ｆ ２ ＣＳ １．０２１ ６ ４．９６６ ６７ ３００ １３．３３ ＷＣＳ ０．０９３ ５ ３．６６６ ６７ ２０ ９０．００ ｆ ３ ＣＳ ２．２１８ ９ １２．７６６ ７ ６００ ３０．００ ＷＣＳ ０．３１５ ４ ７．９ ７０ ８３．３３ ｆ ４ ＣＳ ３．９５１ ５ １９．９６６ ７ １ １００ ３３．３３ ＷＣＳ ０．８４８ ６ ９．４３３ ３３ ２００ ９３．３３ ｆ ５ ＣＳ ０．０４５ ２ ４．４６６ ７ ５０ １００ ＷＣＳ ０．０４３ ３ ５．９６６ ６７ ４０ １００ 表 ２ 运算结果表明，对于 ５ 个测试函数，改进后 的算法找到最优解的次数更多，时间更短，相比于基 本算法找到最优解的准确率更高。 当基本 ＣＳ 算法 面对较为复杂的函数优化问题时，如 ｆ １ ，增加迭代次 数为 ２ ５００，基本算法运行时间是改进后算法的 ５８．７ 倍，收敛到最优解的迭代次数是改进后算法的 ２．４ 倍，准确率只有改进后算法的 ８３％。 因此，改进后 的算法可以更好地解决函数优化问题。 ４．２ ＷＣＳ 算法与其他算法的比较 用以上函数对 ＷＣＳ 算法与 ＣＳ 算法、粒子群算法 （ＰＳＯ）、蚁群算法（ＡＣＯ）、引力搜索算法（ＧＳＡ）和蝙 蝠算法（ＢＡ）进行性能测试，运算结果如表 ３ 所示。 其中，为了更加公平地测试算法性能，每个算法 独立运行 ５０ 次，种群数量都为 ５０，迭代次数 １ ０００。 ＣＳ 算法和 ＷＣＳ 算法参数设置为：发现概率 Ｐａ ＝ ０．２５。 ＰＳＯ 参数设置为 ｗ＝ ０．７２９，ｃ１ ＝ｃ２ ＝ １．４９４ ４５ ［２３］ 。 蚁群 算法参数设置为： α ＝ β ＝ １， ｒ ＝ ０．５， ρ ＝ ０．７， Ｑ ＝ １ ［２４］ 。 引力搜索算法参数设置为：Ｔ ＝ １ ０００，Ｇ０ ＝ １００， α ＝ ５０。 蝙蝠算法参数设置为：Ａｉ ＝ ０．２５，ｒｉ ＝ ０．５， α ＝ g＝ ０．９ ［２５］ 。 实验结果表明，对于函数 ｆ １ ～ ｆ ５ ，相比于其他算 法，ＷＣＳ 算法能够很快找到最优解。 蚁群算法表现 次之，对于 ｆ １ ～ｆ ４可以收敛到最优解，但对 ｆ ５求解精度 第 ４ 期 李煜，等：具有动态惯性权重的布谷鸟搜索算法 ·６４９·
·650 智能系统学报 第10卷 不够。CS算法求解的稳定性不高。对于函数f和 能基本不变，函数2在种群规模增大后的达优率甚 2,WCS算法和蚁群算法都有很好的收敛性，能快速 至出现减少的情况：惯性权重范围在0.2~0.9和 找到最优解：对于函数f,WCS算法和蚁群算法性能 0.9~1.2两个区间的算法优化性能并没有得到明显 明显优于其他算法；对于函数f,WCS算法和蚁群算 改善，最佳惯性权重范围仍然是0~0.2，说明种群规 法能够收敛到最优解：对于函数f,CS算法、WCS算 模的改变，对算法收敛效果的影响不显著。 法和新型蝙蝠算法优化性能明显优于其他算法。 表4不同种群下算法优化效果 表3WCS算法与其他算法性能比较 Table 4 Optimization effect of CS on different populations Table 3 Performance comparison of WCS with other algorithms f 23 4 25 1 0.9 0 0 f 算法最优值 平均值 最差值 标准差 100 1 1 0 0 CS 0.9999740.9972230.9902840.003559 10.040.12 WCS 1 1 1 0 100 1 1 0.080.08 PSO 1 -0.99987-0.996870.000619 f 25 11 00 ACO 1 1 0 100 1 1 0 0 GSA 1 0.9931670.9902840.003921 BA 1 0.9976670.9902800.004193 5 结束语 CS 3.60x103 3.55x10 2.75×10 194.7101 WCS 3600 3600 3600 0 针对布谷鸟算法在求解函数最优化问题中存在 PSO 3.60x10 3.60x103 3.59x10 0.000162 的收敛度不高、收敛速度慢等问题，本文提出了一种 ACO 3600 3600 3600 0 改进方法：通过引入动态惯性权重改进鸟窝位置的 GSA 3.58×10 3.14×103 2.71×103 325.5879 更新方式，对动态惯性权重的取值范围进行分析，找 BA 3600 3600 3600 0 到求解最优的惯性权重取值范围。并利用差分方程 CS -0.000890-0.202307-1.0418480.274363 对改进算法进行了收敛性分析。研究发现改进后的 WCS 0 0 0 0 算法通过动态惯性权重控制种群探索能力和开发能 PSO 0 -1.69x105-5.08x1040.000077 力，能够有效平衡局部搜索能力和全局搜索能力之 ACO 0 0 0 0 间的关系。仿真实验结果表明，与基本布谷鸟算法 GSA 0 -0.047840-0.8538090.127847 相比，WCS算法可以显著减少迭代次数，缩短运行 BA 0 -2.82x102-4.64×1066.62×107 CS -6.67×10°-2.52×10-6.28x1030.000989 时间：与其他算法相比，WCS算法也有较强的收敛 WCS 0 0 0 0 性和鲁棒性。最后，对算法参数进行了讨论，当种群 PS0-2.36×10B5.43×1011-5.18×1007.99×10 规模增大后，仍需惯性权重的调节，且惯性权重的选 ACO 0 0 0 0 择范围不变，进一步说明，加入动态惯性权重后的算 GSA 0 -0.006084-0.029799.0.00614 法具有更好的优化性能。 BA-3.58x102-3.99x100-1.41×1093.98×1010 CS -3 -3 -3 0 参考文献： WCS -3 -3 -3 0 [1]YANG Xinshe,DEB S.Cuckoo search via Levy flights PS0-3.0000001-3.000004-3.0000194.98×10 [C]//World Congress on Nature Biologically Inspired ACO -3 -3.167406-3.6656940.176342 Computing.Coimbatore,India,2009:210-214. GSA -3 -3.010484-3.39170.058115 [2]李煜，马良.新型元启发式布谷鸟搜索算法[J].系统工 BA -3 -3 -3 0 程，2012,30(8)：64-69. LI Yu,MA Liang.A new metaheuristic cuckoo search algo- 4.3种群大小对惯性权重选择的影响 rithm[J].Systems Engineering,2012,30(8):64-69. 算法参数的选择可能对算法性能产生重要影响， [3]陈乐，龙文.求解工程结构优化问题的改进布谷鸟搜索 本文重点讨论种群大小对算法性能的影响。种群规 算法[J].计算机应用研究，2014,31(3)：679-683. CHEN Le,LONG Wen.Modified cuckoo search algorithm for 模由25增加至100，最大迭代次数为300，其他参数 solving engineering structural optimization problem[J].Ap- 设置不变，每个函数独立运行50次，1、2和3分别表 plication Research of Computers,2014,31(3):679-683. 示惯性权重的取值范围0~0.2、0.2~0.9和0.9~1.2,4 [4]OUAARAB A,AHIOD B,YANG Xinshe.Discrete cuckoo 表示基本布谷鸟算法。在n为25和100两种情况 search algorithm for the travelling salesman problem[J].Neu- ral Computing and Applications,2014,24(7/8):1659-1669. 下，函数f~f找到最优解的达优率如表4所示。 [5]SETHI R,PANDA S,SAHOO B P.Cuckoo search algo- 由表4可得，种群规模增大后，CS算法优化性 rithm based optimal tuning of PID structured TCSC control-
不够。 ＣＳ 算法求解的稳定性不高。 对于函数 ｆ １ 和 ｆ ２ ，ＷＣＳ 算法和蚁群算法都有很好的收敛性，能快速 找到最优解；对于函数 ｆ ３ ，ＷＣＳ 算法和蚁群算法性能 明显优于其他算法；对于函数 ｆ ４ ，ＷＣＳ 算法和蚁群算 法能够收敛到最优解；对于函数 ｆ ５ ，ＣＳ 算法、ＷＣＳ 算 法和新型蝙蝠算法优化性能明显优于其他算法。 表 ３ ＷＣＳ 算法与其他算法性能比较 Ｔａｂｌｅ ３ Ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＷＣＳ ｗｉｔｈ ｏｔｈｅｒ ａｌｇｏｒｉｔｈｍｓ ｆ 算法 最优值 平均值 最差值 标准差 ｆ １ ＣＳ ０．９９９ ９７４ ０．９９７ ２２３ ０．９９０ ２８４ ０．００３ ５５９ ＷＣＳ １ １ １ ０ ＰＳＯ １ －０．９９９ ８７ －０．９９６ ８７ ０．０００ ６１９ ＡＣＯ １ １ １ ０ ＧＳＡ １ ０．９９３ １６７ ０．９９０ ２８４ ０．００３ ９２１ ＢＡ １ ０．９９７ ６６７ ０．９９０ ２８０ ０．００４ １９３ ｆ ２ ＣＳ ３．６０×１０ ３ ３．５５×１０ ３ ２．７５×１０ ３ １９４．７１０ １ ＷＣＳ ３ ６００ ３ ６００ ３ ６００ ０ ＰＳＯ ３．６０×１０ ３ ３．６０×１０ ３ ３．５９×１０ ３ ０．０００ １６２ ＡＣＯ ３ ６００ ３ ６００ ３ ６００ ０ ＧＳＡ ３．５８×１０ ３ ３．１４×１０ ３ ２．７１×１０ ３ ３２５．５８７ ９ ＢＡ ３ ６００ ３ ６００ ３ ６００ ０ ｆ ３ ＣＳ －０．０００ ８９０ －０．２０２ ３０７ －１．０４１ ８４８ ０．２７４ ３６３ ＷＣＳ ０ ０ ０ ０ ＰＳＯ ０ －１．６９×１０ －５ －５．０８×１０ －４ ０．０００ ０７７ ＡＣＯ ０ ０ ０ ０ ＧＳＡ ０ －０．０４７ ８４０ －０．８５３ ８０９ ０．１２７ ８４７ ＢＡ ０ －２．８２×１０ －７ －４．６４×１０ －６ ６．６２×１０ －７ ｆ ４ ＣＳ －６．６７×１０ －９ －２．５２×１０ －４ －６．２８×１０ －３ ０．０００ ９８９ ＷＣＳ ０ ０ ０ ０ ＰＳＯ －２．３６×１０ －１３ ５．４３×１０ －１１ －５．１８×１０ －１０ ７．９９×１０ －１１ ＡＣＯ ０ ０ ０ ０ ＧＳＡ ０ －０．００６ ０８４ －０．０２９ ７９９ ０．００６ １４ ＢＡ －３．５８×１０ －１２ －３．９９×１０ －１０ －１．４１×１０ －９ ３．９８×１０ －１０ ｆ ５ ＣＳ －３ －３ －３ ０ ＷＣＳ －３ －３ －３ ０ ＰＳＯ －３．０００ ０００ １－３．０００ ００４ －３．０００ ０１９ ４．９８×１０ －８ ＡＣＯ －３ －３．１６７ ４０６ －３．６６５ ６９４ ０．１７６ ３４２ ＧＳＡ －３ －３．０１０ ４８４ －３．３９１ ７ ０．０５８ １１５ ＢＡ －３ －３ －３ ０ ４．３ 种群大小对惯性权重选择的影响 算法参数的选择可能对算法性能产生重要影响， 本文重点讨论种群大小对算法性能的影响。 种群规 模由 ２５ 增加至 １００，最大迭代次数为 ３００，其他参数 设置不变，每个函数独立运行 ５０ 次，１、２ 和 ３ 分别表 示惯性权重的取值范围 ０ ～ ０．２、０．２ ～ ０．９ 和０．９ ～ １．２，４ 表示基本布谷鸟算法。 在 ｎ 为 ２５ 和 １００ 两种情况 下，函数 ｆ １ ～ｆ ３找到最优解的达优率如表 ４ 所示。 由表 ４ 可得，种群规模增大后，ＣＳ 算法优化性 能基本不变，函数 ２ 在种群规模增大后的达优率甚 至出现减少的情况；惯性权重范围在 ０． ２ ～ ０． ９ 和 ０．９～１．２ 两个区间的算法优化性能并没有得到明显 改善，最佳惯性权重范围仍然是 ０ ～ ０．２，说明种群规 模的改变，对算法收敛效果的影响不显著。 表 ４ 不同种群下算法优化效果 Ｔａｂｌｅ ４ Ｏｐｔｉｍｉｚａｔｉｏｎ ｅｆｆｅｃｔ ｏｆ ＣＳ ｏｎ ｄｉｆｆｅｒｅｎｔ ｐｏｐｕｌａｔｉｏｎｓ ｆ ｎ １ ２ ３ ４ ｆ １ ２５ １ ０．９ ０ ０ １００ １ １ ０ ０ ｆ ２ ２５ １ １ ０．０４ ０．１２ １００ １ １ ０．０８ ０．０８ ｆ ３ ２５ １ １ ０ ０ １００ １ １ ０ ０ ５ 结束语 针对布谷鸟算法在求解函数最优化问题中存在 的收敛度不高、收敛速度慢等问题，本文提出了一种 改进方法：通过引入动态惯性权重改进鸟窝位置的 更新方式，对动态惯性权重的取值范围进行分析，找 到求解最优的惯性权重取值范围。 并利用差分方程 对改进算法进行了收敛性分析。 研究发现改进后的 算法通过动态惯性权重控制种群探索能力和开发能 力，能够有效平衡局部搜索能力和全局搜索能力之 间的关系。 仿真实验结果表明，与基本布谷鸟算法 相比，ＷＣＳ 算法可以显著减少迭代次数，缩短运行 时间；与其他算法相比，ＷＣＳ 算法也有较强的收敛 性和鲁棒性。 最后，对算法参数进行了讨论，当种群 规模增大后，仍需惯性权重的调节，且惯性权重的选 择范围不变，进一步说明，加入动态惯性权重后的算 法具有更好的优化性能。 参考文献： ［１］ ＹＡＮＧ Ｘｉｎｓｈｅ， ＤＥＢ Ｓ． Ｃｕｃｋｏｏ ｓｅａｒｃｈ ｖｉａ Ｌéｖｙ ｆｌｉｇｈｔｓ ［Ｃ］ ／ ／ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｎａｔｕｒｅ ＆ Ｂｉｏｌｏｇｉｃａｌｌｙ Ｉｎｓｐｉｒｅｄ Ｃｏｍｐｕｔｉｎｇ． Ｃｏｉｍｂａｔｏｒｅ， Ｉｎｄｉａ， ２００９： ２１０⁃２１４． ［２］李煜， 马良． 新型元启发式布谷鸟搜索算法［ Ｊ］． 系统工 程， ２０１２， ３０（８）： ６４⁃６９． ＬＩ Ｙｕ， ＭＡ Ｌｉａｎｇ． Ａ ｎｅｗ ｍｅｔａｈｅｕｒｉｓｔｉｃ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏ⁃ ｒｉｔｈｍ［Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， ３０（８）： ６４⁃６９． ［３］陈乐， 龙文． 求解工程结构优化问题的改进布谷鸟搜索 算法［Ｊ］． 计算机应用研究， ２０１４， ３１（３）： ６７９⁃６８３． ＣＨＥＮ Ｌｅ， ＬＯＮＧ Ｗｅｎ． Ｍｏｄｉｆｉｅｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｅｎｇｉｎｅｅｒｉｎｇ ｓｔｒｕｃｔｕｒａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ［ Ｊ］． Ａｐ⁃ ｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２０１４， ３１（３）： ６７９⁃６８３． ［４］ ＯＵＡＡＲＡＢ Ａ， ＡＨＩＯＤ Ｂ， ＹＡＮＧ Ｘｉｎｓｈｅ． Ｄｉｓｃｒｅｔｅ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｔｒａｖｅｌｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｊ］． Ｎｅｕ⁃ ｒａｌ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ２４（７／ ８）： １６５９⁃１６６９． ［５］ ＳＥＴＨＩ Ｒ， ＰＡＮＤＡ Ｓ， ＳＡＨＯＯ Ｂ Ｐ． Ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏ⁃ ｒｉｔｈｍ ｂａｓｅｄ ｏｐｔｉｍａｌ ｔｕｎｉｎｇ ｏｆ ＰＩＤ ｓｔｒｕｃｔｕｒｅｄ ＴＣＳＣ ｃｏｎｔｒｏｌ⁃ ·６５０· 智 能 系 统 学 报 第 １０ 卷
第4期 李煜，等：具有动态惯性权重的布谷鸟搜索算法 ·651. ler[M]//JAIN L C,BEHERA H S,MANDAL J K,et al. [J].系统工程学报，2005,20(2)：194-198 Computational Intelligence in Data Mining-Volume 1.Odis- WANG Junwei,WANG Dingwei.Experiments and analysis ha:Springer,2015:251-263. on inertia weight in particle swarm optimization[].Jour- [6]WALTON S,HASSAN O,MORGAN K,et al.Modified nal of Systems Engineering,2005,20(2):194-198. cuckoo search:a new gradient free optimisation algorithm [19]张永韡，汪镭，吴启迪.动态适应布谷鸟搜索算法[J] [J].Chaos,Solitons and Fractals,2011,44(9):710-718. 控制与决策，2014,29(4)：617-622. [7 ZHENG Hongqing,ZHOU Yongquan.A novel cuckoo ZHANG Yongwei,WANG Lei,WU Qidi.Dynamic adapta- search optimization algorithm based on Gauss distribution tion cuckoo search algorithm[J].Control and Decision, [J].Journal of Computational Information Systems,2012, 2014,29(4):617-622 8(10):4193-4200. [20]王凡，贺兴时，王燕，等.基于CS算法的Markov模型 [8]苏芙华，刘云连，伍铁斌.求解无约束优化问题的改进 及收敛性分析[J].计算机工程，2012,38(11)：180- 布谷鸟搜索算法[J].计算机工程，2014,40(5)：224 182,185. 227,233. WANG Fan,HE Xingshi,WANG Yan,et al.Markov SU Fuhua,LIU Yunlian,WU Tiebin.Modified cuckoo search model and convergence analysis based on cuckoo search al- algorithm for solving unconstrained optimization problem[J] gorithm[J].Computer Engineering,2012,38(11):180- Computer Engineering,2014,40(5):224-227,233. 182,185. [9]龙文，陈乐.求解约束化工优化问题的混合布谷鸟搜索 [21]李枝勇，马良，张惠珍.骗蝠算法收敛性分析[J刀]数学 算法[J].计算机应用，2014,34(2)：523-527. 的实践与认识，2013,43(12)：182-190. LONG Wen,CHEN Le.Hybrid cuckoo search algorithm for LI Zhiyong,MA Liang,ZHANG Huizhen.Convergence a- solving constrained chemical engineering optimization prob- nalysis of bat algorithm[J].Mathematics in Practice and lems[J].Journal of Computer Applications,2014,34(2): Theory,2013,43(12):182-190. 523-527. [22]刘洪波，王秀坤，谭国真.粒子群优化算法的收敛性分 [10]VISWANATHAN G M,AFANASYEV V,BULDYREV S 析及其混沌改进算法[J].控制与决策，2006,21(6)： V,et al.Levy flights in random searches[]].Physica A: 636-640. Statistical Mechanics and its Applications,2000,282(1/ LIU Hongbo,WANG Xiukun,TAN Guozhen.Convergence 2):1-12. analysis of particle swarm optimization and its improved al- [11]邓鑫洋，邓勇，章雅娟，等.一种信度马尔科夫模型及 gorithm based on chaos[].Control and Decision,2006, 应用[J].自动化学报，2012,38(4)：666-672. 21(6):636-640. DENG Xinyang,DENG Yong,ZHANG Yajuan,et al.A 23]EBERHART R C.SHI Y.Comparing inertia weights and belief Markov model and its application[J].Acta Automat- constriction factors in particle swarm optimization[C]// ica Sinica,2012,38(4):666-672. Proceedings of the 2000 Congress on Evolutionary Compu- [12]SHI Yuhui,EBERHART R.A modified particle swarm op- tation.La Jolla,Germany,2000:84-88. timizer[C]//IEEE World Congress on Computational In- [24]马良.基于蚂蚁算法的函数优化[J].控制与决策， telligence,The 1998 IEEE International Conference on Ev- 2002,17(增刊)：719-722. olutionary Computation Proceedings.Anchorage,USA, MA Liang.Ant algorithm based function optimization[J]. 1998:69-73. Control and Decision,2002,17(S):719-722. [13]SHI Yuhui,EBERHART R C.Empirical study of particle [25]李枝勇，马良，张惠珍.多目标0-1规划问题的蝙蝠算 swarm optimization C//Proceedings of the 1999 Congress 法[J].智能系统学报，2014,9(6)：672-676. on Evolutionary Computation.Washington DC,USA, LI Zhiyong,MA Liang,ZHANG Huizhen.Bat algorithm for 1999,3:1945-1949. the multi-objective 0-1 programming problem [J].CAAI [14]PERAM T,VEERAMACHANENI K,MOHAN C K.Fit- Transactions on Intelligent Systems,2014,9(6):672-676. ness-distance-ratio based particle swarmoptimization[C]/ 作者简介： Proceedings of the 2003 IEEE Swarm Intelligence Symposi- 周欢，1990年生，女，硕士研究生 um.Indianapolis,USA,2003:174-181. 主要研究方向为智能优化、电子商务。 [15]SHI Yuhui,EBERHART R C.Fuzzy adaptive particle swarm optimization [C]//Proceedings of the 2001 Con- gress on Evolutionary Computation.Seoul,Korea,2001: 101-106. [16]EBERHART R C,SHI Yuhui.Tracking and optimizing dy- namic systems with particle swarms[C]//Proceedings of 李煜，1969年生，女，教授，博士，主 the 2001 Congress on Evolutionary Computation.Seoul, 要研究方向为智能优化、电子商务、物 Korea,2001:94-100. 流管理。 [17]ZHANG Liping,YU Huanjun,HU Shangxu.A new ap- proach to improve particle swarm Optimization[C]//Ge- netic and Evolutionary Computation-GECCO 2003.Berlin Heidelberg,Germany,2003:134-139. [责任编辑：孟玮] [18]王俊伟，汪定伟.粒子群算法中惯性权重的实验与分析
ｌｅｒ［Ｍ］ ／ ／ ＪＡＩＮ Ｌ Ｃ， ＢＥＨＥＲＡ Ｈ Ｓ， ＭＡＮＤＡＬ Ｊ Ｋ， ｅｔ ａｌ． Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ｉｎ Ｄａｔａ Ｍｉｎｉｎｇ⁃Ｖｏｌｕｍｅ １． Ｏｄｉｓ⁃ ｈａ： Ｓｐｒｉｎｇｅｒ， ２０１５： ２５１⁃２６３． ［６］ ＷＡＬＴＯＮ Ｓ， ＨＡＳＳＡＮ Ｏ， ＭＯＲＧＡＮ Ｋ， ｅｔ ａｌ． Ｍｏｄｉｆｉｅｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ： ａ ｎｅｗ ｇｒａｄｉｅｎｔ ｆｒｅｅ ｏｐｔｉｍｉｓａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ［Ｊ］． Ｃｈａｏｓ， Ｓｏｌｉｔｏｎｓ ａｎｄ Ｆｒａｃｔａｌｓ， ２０１１， ４４（９）： ７１０⁃７１８． ［ ７ ］ ＺＨＥＮＧ Ｈｏｎｇｑｉｎｇ， ＺＨＯＵ Ｙｏｎｇｑｕａｎ． Ａ ｎｏｖｅｌ ｃｕｃｋｏｏ ｓｅａｒｃｈ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｇａｕｓｓ ｄｉｓｔｒｉｂｕｔｉｏｎ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， ２０１２， ８（１０）： ４１９３⁃４２００． ［８］苏芙华， 刘云连， 伍铁斌． 求解无约束优化问题的改进 布谷鸟搜索算法［ Ｊ］． 计算机工程， ２０１４， ４０（ ５）： ２２４⁃ ２２７， ２３３． ＳＵ Ｆｕｈｕａ， ＬＩＵ Ｙｕｎｌｉａｎ， ＷＵ Ｔｉｅｂｉｎ． Ｍｏｄｉｆｉｅｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｕｎｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１４， ４０（５）： ２２４⁃２２７， ２３３． ［９］龙文， 陈乐． 求解约束化工优化问题的混合布谷鸟搜索 算法［Ｊ］． 计算机应用， ２０１４， ３４（２）： ５２３⁃５２７． ＬＯＮＧ Ｗｅｎ， ＣＨＥＮ Ｌｅ． Ｈｙｂｒｉｄ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｃｏｎｓｔｒａｉｎｅｄ ｃｈｅｍｉｃａｌ ｅｎｇｉｎｅｅｒｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂ⁃ ｌｅｍｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ３４（２）： ５２３⁃５２７． ［１０］ ＶＩＳＷＡＮＡＴＨＡＮ Ｇ Ｍ， ＡＦＡＮＡＳＹＥＶ Ｖ， ＢＵＬＤＹＲＥＶ Ｓ Ｖ， ｅｔ ａｌ． Ｌéｖｙ ｆｌｉｇｈｔｓ ｉｎ ｒａｎｄｏｍ ｓｅａｒｃｈｅｓ［Ｊ］． Ｐｈｙｓｉｃａ Ａ： Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０００， ２８２（１ ／ ２）： １⁃１２． ［１１］邓鑫洋， 邓勇， 章雅娟， 等． 一种信度马尔科夫模型及 应用［Ｊ］． 自动化学报， ２０１２， ３８（４）： ６６６⁃６７２． ＤＥＮＧ Ｘｉｎｙａｎｇ， ＤＥＮＧ Ｙｏｎｇ， ＺＨＡＮＧ Ｙａｊｕａｎ， ｅｔ ａｌ． Ａ ｂｅｌｉｅｆ Ｍａｒｋｏｖ ｍｏｄｅｌ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ［Ｊ］． Ａｃｔａ Ａｕｔｏｍａｔ⁃ ｉｃａ Ｓｉｎｉｃａ， ２０１２， ３８（４）： ６６６⁃６７２． ［１２］ＳＨＩ Ｙｕｈｕｉ， ＥＢＥＲＨＡＲＴ Ｒ． Ａ ｍｏｄｉｆｉｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐ⁃ ｔｉｍｉｚｅｒ［Ｃ］ ／ ／ ＩＥＥＥ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｃｅ， Ｔｈｅ １９９８ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｖ⁃ ｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ Ｐｒｏｃｅｅｄｉｎｇｓ． Ａｎｃｈｏｒａｇｅ， ＵＳＡ， １９９８： ６９⁃７３． ［１３］ＳＨＩ Ｙｕｈｕｉ， ＥＢＥＲＨＡＲＴ Ｒ Ｃ． Ｅｍｐｉｒｉｃａｌ ｓｔｕｄｙ ｏｆ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９９９ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ， ＵＳＡ， １９９９， ３： １９４５⁃１９４９． ［１４］ ＰＥＲＡＭ Ｔ， ＶＥＥＲＡＭＡＣＨＡＮＥＮＩ Ｋ， ＭＯＨＡＮ Ｃ Ｋ． Ｆｉｔ⁃ ｎｅｓｓ⁃ｄｉｓｔａｎｃｅ⁃ｒａｔｉｏ ｂａｓｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００３ ＩＥＥＥ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｙｍｐｏｓｉ⁃ ｕｍ． Ｉｎｄｉａｎａｐｏｌｉｓ， ＵＳＡ， ２００３： １７４⁃１８１． ［１５］ ＳＨＩ Ｙｕｈｕｉ， ＥＢＥＲＨＡＲＴ Ｒ Ｃ． Ｆｕｚｚｙ ａｄａｐｔｉｖｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００１ Ｃｏｎ⁃ ｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ． Ｓｅｏｕｌ， Ｋｏｒｅａ， ２００１： １０１⁃１０６． ［１６］ＥＢＥＲＨＡＲＴ Ｒ Ｃ， ＳＨＩ Ｙｕｈｕｉ． Ｔｒａｃｋｉｎｇ ａｎｄ ｏｐｔｉｍｉｚｉｎｇ ｄｙ⁃ ｎａｍｉｃ ｓｙｓｔｅｍｓ ｗｉｔｈ ｐａｒｔｉｃｌｅ ｓｗａｒｍｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００１ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ． Ｓｅｏｕｌ， Ｋｏｒｅａ， ２００１： ９４⁃１００． ［１７］ ＺＨＡＮＧ Ｌｉｐｉｎｇ， ＹＵ Ｈｕａｎｊｕｎ， ＨＵ Ｓｈａｎｇｘｕ． Ａ ｎｅｗ ａｐ⁃ ｐｒｏａｃｈ ｔｏ ｉｍｐｒｏｖｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｃ］ ／ ／ Ｇｅ⁃ ｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ—ＧＥＣＣＯ ２００３． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ， Ｇｅｒｍａｎｙ， ２００３： １３４⁃１３９． ［１８］王俊伟， 汪定伟． 粒子群算法中惯性权重的实验与分析 ［Ｊ］． 系统工程学报， ２００５， ２０（２）： １９４⁃１９８． ＷＡＮＧ Ｊｕｎｗｅｉ， ＷＡＮＧ Ｄｉｎｇｗｅｉ． Ｅｘｐｅｒｉｍｅｎｔｓ ａｎｄ ａｎａｌｙｓｉｓ ｏｎ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ ｉｎ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． Ｊｏｕｒ⁃ ｎａｌ ｏｆ Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００５， ２０（２）： １９４⁃１９８． ［１９］张永韡， 汪镭， 吴启迪． 动态适应布谷鸟搜索算法［ Ｊ］． 控制与决策， ２０１４， ２９（４）： ６１７⁃６２２． ＺＨＡＮＧ Ｙｏｎｇｗｅｉ， ＷＡＮＧ Ｌｅｉ， ＷＵ Ｑｉｄｉ． Ｄｙｎａｍｉｃ ａｄａｐｔａ⁃ ｔｉｏｎ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２０１４， ２９（４）： ６１７⁃６２２． ［２０］王凡， 贺兴时， 王燕， 等． 基于 ＣＳ 算法的 Ｍａｒｋｏｖ 模型 及收敛性分析［ Ｊ］． 计算机工程， ２０１２， ３８（ １１）： １８０⁃ １８２， １８５． ＷＡＮＧ Ｆａｎ， ＨＥ Ｘｉｎｇｓｈｉ， ＷＡＮＧ Ｙａｎ， ｅｔ ａｌ． Ｍａｒｋｏｖ ｍｏｄｅｌ ａｎｄ ｃｏｎｖｅｒｇｅｎｃｅ ａｎａｌｙｓｉｓ ｂａｓｅｄ ｏｎ ｃｕｃｋｏｏ ｓｅａｒｃｈ ａｌ⁃ ｇｏｒｉｔｈｍ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， ３８（１１）： １８０⁃ １８２， １８５． ［２１］李枝勇， 马良， 张惠珍． 蝙蝠算法收敛性分析［Ｊ］． 数学 的实践与认识， ２０１３， ４３（１２）： １８２⁃１９０． ＬＩ Ｚｈｉｙｏｎｇ， ＭＡ Ｌｉａｎｇ， ＺＨＡＮＧ Ｈｕｉｚｈｅｎ． Ｃｏｎｖｅｒｇｅｎｃｅ ａ⁃ ｎａｌｙｓｉｓ ｏｆ ｂａｔ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｍａｔｈｅｍａｔｉｃｓ ｉｎ Ｐｒａｃｔｉｃｅ ａｎｄ Ｔｈｅｏｒｙ， ２０１３， ４３（１２）： １８２⁃１９０． ［２２］刘洪波， 王秀坤， 谭国真． 粒子群优化算法的收敛性分 析及其混沌改进算法［ Ｊ］． 控制与决策， ２００６， ２１（６）： ６３６⁃６４０． ＬＩＵ Ｈｏｎｇｂｏ， ＷＡＮＧ Ｘｉｕｋｕｎ， ＴＡＮ Ｇｕｏｚｈｅｎ． Ｃｏｎｖｅｒｇｅｎｃｅ ａｎａｌｙｓｉｓ ｏｆ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｉｔｓ ｉｍｐｒｏｖｅｄ ａｌ⁃ ｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｈａｏｓ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２００６， ２１（６）： ６３６⁃６４０． ［２３］ＥＢＥＲＨＡＲＴ Ｒ Ｃ， ＳＨＩ Ｙ． Ｃｏｍｐａｒｉｎｇ ｉｎｅｒｔｉａ ｗｅｉｇｈｔｓ ａｎｄ ｃｏｎｓｔｒｉｃｔｉｏｎ ｆａｃｔｏｒｓ ｉｎ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０００ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕ⁃ ｔａｔｉｏｎ． Ｌａ Ｊｏｌｌａ， Ｇｅｒｍａｎｙ， ２０００： ８４⁃８８． ［２４］马良． 基于蚂蚁算法的函数优化［ Ｊ］． 控制与决 策， ２００２， １７（增刊）： ７１９⁃７２２． ＭＡ Ｌｉａｎｇ． Ａｎｔ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｆｕｎｃｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２００２， １７（Ｓ）： ７１９⁃７２２． ［２５］李枝勇， 马良， 张惠珍． 多目标 ０⁃１ 规划问题的蝙蝠算 法［Ｊ］． 智能系统学报， ２０１４， ９（６）： ６７２ ⁃６７６． ＬＩ Ｚｈｉｙｏｎｇ， ＭＡ Ｌｉａｎｇ， ＺＨＡＮＧ Ｈｕｉｚｈｅｎ． Ｂａｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅ ０⁃１ ｐｒｏｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍ ［ Ｊ ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（６）： ６７２⁃６７６． 作者简介： 周欢，１９９０ 年生，女，硕士研究生， 主要研究方向为智能优化、电子商务。 李煜，１９６９ 年生，女，教授，博士，主 要研究方向为智能优化、电子商务、物 流管理。 ［责任编辑：孟玮］ 第 ４ 期 李煜，等：具有动态惯性权重的布谷鸟搜索算法 ·６５１·