第10卷第3期 智能系统学报 Vol.10 No.3 2015年6月 CAAI Transactions on Intelligent Systems Jun.2015 D0:10.3969/j.issn.1673-4785.201403025 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150407.1107.001.html 一种改进的自适应步长的人工萤火虫算法 唐少虎2，刘小明2 (1.北方工业大学电气与控制工程学院，北京100144：2.北方工业大学城市道路交通智能控制技术北京市重点实验 室，北京100144) 摘要：在基本的人工莹火虫算法(G0)中，莹火虫的固定移动步长导致算法容易陷入局部最优并可能出现函数适 应值的震荡现象。在一些自适应步长的人工萤火虫算法(A-GS0)中，算法迭代过程中会出现一些萤火虫的邻域集 合为空集的现象，这将导致算法收敛速度降低并陷入局部最优值。为此，设计了改进的自适应步长的人工萤火虫算 法(FA-GS0),改进的算法针对邻域无同伴的萤火虫引入觅食行为寻找优化方向并自适应调整移动步长，进一步提 高求解精度和稳定性，并给出了算法的收敛性分析，结合GS0、A-GS02种算法对多个标准测试函数进行寻优并提取 相关指标。通过指标对照，验证了FA-GS0算法的有效性，表明算法可以改善函数寻优的精度并提高迭代速度。 关键词：人工萤火虫算法：自适应步长：觅食行为：全局收敛性 中图分类号：TP183文献标志码：A文章编号：1673-4785(2015)03-0470-06 中文引用格式：唐少虎，刘小明.一种改进的自适应步长的人工萤火虫算法[J].智能系统学报，2015,10(3)：470475. 英文引用格式：TANG Shaohu,LIU Xiaoming.An improved adaptive step glowworm swarm optimization algorithm[J】.CAAI Transactions on Intelligent Systems,2015,10(3):470-475. An improved adaptive step glowworm swarm optimization algorithm TANG Shaohu2,LIU Xiaoming' (1.College of Electrical and Control Engineering,North China University of Technology,Beijing 100144,China;2.Beijing Key Lab of Urban Intelligent Traffic Control Technology,North China University of Technology,Beijing 100144,China) Abstract:In the basic glowworm swarm optimization (GSO),it is easy to fall into local optimum and the oscillation phenomenon of function adaptive values may occur because of the fixed step length.In some adaptive-step glowworm swarm optimization(A-GSO)algorithms,neighborhood sets of some fireflies may be empty in the iterative process of the algorithm,which leads to lower convergence speed and falls into local optimal value.Therefore,an improved foraging-behavior adaptive-step GSO(FA-GSO)algorithm was designed.The foraging behavior of the fireflies with- out neighborhood peer and adaptive step is introduced in order to find the optimization direction in the improved al- gorithm.The precision,stability,and global convergence analysis of FA-GSO is presented.After extracting and comparing the relevant optimization indicators of GSO,A-GSO and FA-GSO by several standard test functions,the effectiveness of the FA-GSO algorithm was verified,which indicates that the improved algorithm can improve the accuracy of function optimization and the iteration speed. Keywords:glowworm swarm optimization;adaptive step;foraging behavior;global convergence 大自然中的萤火虫种类多种多样，萤火虫通过 身体发光来达到各种生存目的。一般说来，萤火虫 的荧光素亮度越大越能找到其他萤火虫或越容易找 收稿日期：2014-03-09.网络出版日期：2015-04-07. 到食物。最后，由于寻找同伴或者食物的原因导致 基金项目：国家自然科学基金资助项目(61374191)：国家“863”计划 资助项目(2012AA112401):“十二五”国家科技支撑计划 许多萤火虫汇聚在一起。以此为启发，K.N.Kish- 课题专项经费资助项目(2014BAG03B01). nanad和D.Ghose总结形成了基本的人工萤火虫算 通信作者：唐少虎.E-mail:tshaohu@163.com
第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０３０２５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０４０７．１１０７．００１．ｈｔｍｌ 一种改进的自适应步长的人工萤火虫算法 唐少虎１，２ ，刘小明１，２ （１．北方工业大学 电气与控制工程学院，北京 １００１４４；２．北方工业大学 城市道路交通智能控制技术北京市重点实验 室，北京 １００１４４） 摘 要：在基本的人工萤火虫算法（ＧＳＯ）中，萤火虫的固定移动步长导致算法容易陷入局部最优并可能出现函数适 应值的震荡现象。 在一些自适应步长的人工萤火虫算法（Ａ⁃ＧＳＯ）中，算法迭代过程中会出现一些萤火虫的邻域集 合为空集的现象，这将导致算法收敛速度降低并陷入局部最优值。 为此，设计了改进的自适应步长的人工萤火虫算 法（ＦＡ⁃ＧＳＯ），改进的算法针对邻域无同伴的萤火虫引入觅食行为寻找优化方向并自适应调整移动步长，进一步提 高求解精度和稳定性，并给出了算法的收敛性分析，结合 ＧＳＯ、Ａ⁃ＧＳＯ ２ 种算法对多个标准测试函数进行寻优并提取 相关指标。 通过指标对照，验证了 ＦＡ⁃ＧＳＯ 算法的有效性，表明算法可以改善函数寻优的精度并提高迭代速度。 关键词：人工萤火虫算法；自适应步长；觅食行为；全局收敛性 中图分类号：ＴＰ１８３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０４７０⁃０６ 中文引用格式：唐少虎，刘小明． 一种改进的自适应步长的人工萤火虫算法［Ｊ］． 智能系统学报， ２０１５， １０（３）： ４７０⁃４７５． 英文引用格式：ＴＡＮＧ Ｓｈａｏｈｕ， ＬＩＵ Ｘｉａｏｍｉｎｇ． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ｓｔｅｐ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ４７０⁃４７５． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ｓｔｅｐ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ＴＡＮＧ Ｓｈａｏｈｕ １，２ ， ＬＩＵ Ｘｉａｏｍｉｎｇ １，２ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎｏｒｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｂｅｉｊｉｎｇ １００１４４， Ｃｈｉｎａ； ２． Ｂｅｉｊｉｎｇ Ｋｅｙ Ｌａｂ ｏｆ Ｕｒｂａｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｒａｆｆｉｃ Ｃｏｎｔｒｏｌ Ｔｅｃｈｎｏｌｏｇｙ， Ｎｏｒｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｂｅｉｊｉｎｇ １００１４４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｂａｓｉｃ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ＧＳＯ）， ｉｔ ｉｓ ｅａｓｙ ｔｏ ｆａｌｌ ｉｎｔｏ ｌｏｃａｌ ｏｐｔｉｍｕｍ ａｎｄ ｔｈｅ ｏｓｃｉｌｌａｔｉｏｎ ｐｈｅｎｏｍｅｎｏｎ ｏｆ ｆｕｎｃｔｉｏｎ ａｄａｐｔｉｖｅ ｖａｌｕｅｓ ｍａｙ ｏｃｃｕｒ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｆｉｘｅｄ ｓｔｅｐ ｌｅｎｇｔｈ． Ｉｎ ｓｏｍｅ ａｄａｐｔｉｖｅ⁃ｓｔｅｐ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （Ａ⁃ＧＳＯ） ａｌｇｏｒｉｔｈｍｓ， ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅｔｓ ｏｆ ｓｏｍｅ ｆｉｒｅｆｌｉｅｓ ｍａｙ ｂｅ ｅｍｐｔｙ ｉｎ ｔｈｅ ｉｔｅｒａｔｉｖｅ ｐｒｏｃｅｓｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ， ｗｈｉｃｈ ｌｅａｄｓ ｔｏ ｌｏｗｅｒ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ ａｎｄ ｆａｌｌｓ ｉｎｔｏ ｌｏｃａｌ ｏｐｔｉｍａｌ ｖａｌｕｅ． Ｔｈｅｒｅｆｏｒｅ， ａｎ ｉｍｐｒｏｖｅｄ ｆｏｒａｇｉｎｇ⁃ｂｅｈａｖｉｏｒ ａｄａｐｔｉｖｅ⁃ｓｔｅｐ ＧＳＯ （ＦＡ⁃ＧＳＯ） ａｌｇｏｒｉｔｈｍ ｗａｓ ｄｅｓｉｇｎｅｄ． Ｔｈｅ ｆｏｒａｇｉｎｇ ｂｅｈａｖｉｏｒ ｏｆ ｔｈｅ ｆｉｒｅｆｌｉｅｓ ｗｉｔｈ⁃ ｏｕｔ ｎｅｉｇｈｂｏｒｈｏｏｄ ｐｅｅｒ ａｎｄ ａｄａｐｔｉｖｅ ｓｔｅｐ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｏｒｄｅｒ ｔｏ ｆｉｎｄ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｄｉｒｅｃｔｉｏｎ ｉｎ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌ⁃ ｇｏｒｉｔｈｍ． Ｔｈｅ ｐｒｅｃｉｓｉｏｎ， ｓｔａｂｉｌｉｔｙ， ａｎｄ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ａｎａｌｙｓｉｓ ｏｆ ＦＡ⁃ＧＳＯ ｉｓ ｐｒｅｓｅｎｔｅｄ． Ａｆｔｅｒ ｅｘｔｒａｃｔｉｎｇ ａｎｄ ｃｏｍｐａｒｉｎｇ ｔｈｅ ｒｅｌｅｖａｎｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎｄｉｃａｔｏｒｓ ｏｆ ＧＳＯ， Ａ⁃ＧＳＯ ａｎｄ ＦＡ⁃ＧＳＯ ｂｙ ｓｅｖｅｒａｌ ｓｔａｎｄａｒｄ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ， ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ＦＡ⁃ＧＳＯ ａｌｇｏｒｉｔｈｍ ｗａｓ ｖｅｒｉｆｉｅｄ， ｗｈｉｃｈ ｉｎｄｉｃａｔｅｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｆｕｎｃｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｔｈｅ ｉｔｅｒａｔｉｏｎ ｓｐｅｅｄ． Ｋｅｙｗｏｒｄｓ：ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ； ａｄａｐｔｉｖｅ ｓｔｅｐ； ｆｏｒａｇｉｎｇ ｂｅｈａｖｉｏｒ； ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ 收稿日期：２０１４⁃０３⁃０９． 网络出版日期：２０１５⁃０４⁃０７． 基金项目：国家自然科学基金资助项目（６１３７４１９１）；国家“８６３”计划 资助项目（２０１２ＡＡ１１２４０１）；“十二五” 国家科技支撑计划 课题专项经费资助项目（２０１４ＢＡＧ０３Ｂ０１）． 通信作者：唐少虎． Ｅ⁃ｍａｉｌ： ｔｓｈａｏｈｕ＠ １６３．ｃｏｍ． 大自然中的萤火虫种类多种多样，萤火虫通过 身体发光来达到各种生存目的。 一般说来，萤火虫 的荧光素亮度越大越能找到其他萤火虫或越容易找 到食物。 最后，由于寻找同伴或者食物的原因导致 许多萤火虫汇聚在一起。 以此为启发，Ｋ． Ｎ． Ｋｒｉｓｈ⁃ ｎａｎａｄ 和 Ｄ． Ｇｈｏｓｅ 总结形成了基本的人工萤火虫算
第3期 唐少虎，等：一种改进的自适应步长的人工萤火虫算法 ·471. 法(glowworm swarm optimization,GSO),萤火虫最终 次迭代中萤火虫i的荧光素值，J,(t+1)是在第t+1 会聚集成多个群体从而找到多个局部最优值，算法 次迭代中萤火虫i的评价值。 设计的迭代机制不仅有利于求解局部最优解，而且 3)位置移动阶段。 能够有助于快速求解全局最优值。所以，算法的优 算法每次迭代后萤火虫会在搜索空间中更新自 点是在搜索局部和全局最优解上具有速度快、效率 己的位置，即位置移动。在萤火虫i位置移动之前 高的特点，尤其在多模态函数求解问题等优化方面 必须先找到一个符合条件的同伴，这个同伴必须满 有着广泛的应用，如模拟机器人、多信号源追踪和定 足以下2个条件：a)要在萤火虫i的感知范围内：b) 位、传感器的噪声测试等方面1)。但另一方面，该 携带的荧光素值要大于萤火虫i的荧光素值。 算法也存在着一些问题，如算法全局最优解的搜索 在全部满足以上2个条件的萤火虫中，根据式 受到约束，存在陷入局部最优的风险。由于算法设 (2)计算选择每个同伴萤火虫的概率大小： 计的萤火虫移动步长是固定的，不利于算法后期求 l(t)-l:(t) 解局部最优值，而步长自适应调整有利于提高求解 P防= (2) 的精度和收敛速度。周正新)和欧阳喆等6)通过 ∑l()-() keN(） 自适应调整算法不同阶段的移动步长，算法初期采 式中：j∈N(t),N:(t)={j:d,(t)<(t):l,(t)< 取较大的步长有助于快速找到全局最优邻域，而后 ,(t)}是在第t次迭代中萤火虫i的邻域集，(t) 期较小的步长有利于精确求解局部最优和加快收敛 是在第t次迭代中萤火虫i的决策半径，d(t)是在 速度。 第t次迭代中萤火虫i、j的空间距离。按照轮盘赌 自适应步长提高了算法的性能，但是在寻优的 法则，选出同伴萤火虫j,将依据式(3)更新位置： 精度和稳定性方面还存在不足。本文针对基本和自 x(1)-x;(t) 适应步长的算法在迭代过程中出现的萤火虫邻域集 x(t+1)=x,(t)+s( 合为空集时，导致算法收敛速度降低并很快陷入局 0-0T）(3) 式中：s是萤火虫的移动步长，‖·Ⅱ是萤火虫i和 部最优的问题，提出了一种改进的自适应步长的人 j的欧式空间距离。 工萤火虫算法，即基于觅食行为的自适应步长人工 4)动态感知范围更新阶段。 萤火虫算法。 萤火虫位置更新后，会动态调整自身感知范围， 1人工萤火虫算法原理 调整的大小是基于感知范围内同伴的数量多少。具 体根据式(4)进行计算： 1.1基本的人工萤火虫算法 人工萤火虫算法(Gs0)[71是在2005年由K. r(t+1)= N.Krishnanad和D.Ghose提出的一种新的群智能 min{r,max{0,ra(t)+B(n,-|N:(t))}}(4) 式中：n,是调整萤火虫邻域集合大小的参数，B是 仿生优化算法。算法模拟了自然界中萤火虫求偶行 为或者说是觅食行为。 调整萤火虫动态感知范围大小的参数。 GS0算法主要有4个阶段：萤火虫初始化阶 开始 段、荧光素更新阶段、位置移动阶段以及动态感知范 围更新阶段。算法流程如图1所示。 GSO算法参数初始化 1)初始化阶段。 更新萤火虫的荧光素 初始化算法各个参数、各萤火虫的位置。萤火 虫随机分布在目标可行域中，每只萤火虫携带的初 更新决策范围内的同伴 始荧光素。和感知半径r。是相同的。 2)荧光素更新阶段。 轮盘赌法则选择同伴萤火虫 萤火虫的荧光素大小与其所在搜索空间中的位 置有直接关系，萤火虫所在空间位置的评价值越高， 更新移动位置 则荧光素更新后的增长就越大，即萤火虫的发光强 更新决策域半径 度也越大。另外，萤火虫的发光强度的强弱除了受 所在空间值的影响，还和萤火虫上一次迭代的荧光 素大小以及挥发速度的快慢有关联，萤火虫位置更 最大迭代次数 新完成后，下一次迭代开始前，所有萤火虫的荧光素 TY 都会更新，荧光素根据式(1)更新： 输出最优解 l.(t+1)=(1-p)l,(t)+yJ,(t+1)(1) (结束 式中：p(0<p<1)是萤火虫的荧光素挥发速度参 图1基本的GS0算法流程 数，y是萤火虫的萤火素更新率参数，l,(t)是在第t Fig.1 Flow chart of basic GSO algorithm
法（ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＧＳＯ），萤火虫最终 会聚集成多个群体从而找到多个局部最优值，算法 设计的迭代机制不仅有利于求解局部最优解，而且 能够有助于快速求解全局最优值。 所以，算法的优 点是在搜索局部和全局最优解上具有速度快、效率 高的特点，尤其在多模态函数求解问题等优化方面 有着广泛的应用，如模拟机器人、多信号源追踪和定 位、传感器的噪声测试等方面［１－４］ 。 但另一方面，该 算法也存在着一些问题，如算法全局最优解的搜索 受到约束，存在陷入局部最优的风险。 由于算法设 计的萤火虫移动步长是固定的，不利于算法后期求 解局部最优值，而步长自适应调整有利于提高求解 的精度和收敛速度。 周正新［５］ 和欧阳喆等［６］ 通过 自适应调整算法不同阶段的移动步长，算法初期采 取较大的步长有助于快速找到全局最优邻域，而后 期较小的步长有利于精确求解局部最优和加快收敛 速度。 自适应步长提高了算法的性能，但是在寻优的 精度和稳定性方面还存在不足。 本文针对基本和自 适应步长的算法在迭代过程中出现的萤火虫邻域集 合为空集时，导致算法收敛速度降低并很快陷入局 部最优的问题，提出了一种改进的自适应步长的人 工萤火虫算法，即基于觅食行为的自适应步长人工 萤火虫算法。 １ 人工萤火虫算法原理 １．１ 基本的人工萤火虫算法 人工萤火虫算法（ＧＳＯ） ［ ７ ］ 是在 ２００５ 年由 Ｋ． Ｎ． Ｋｒｉｓｈｎａｎａｄ 和 Ｄ． Ｇｈｏｓｅ 提出的一种新的群智能 仿生优化算法。 算法模拟了自然界中萤火虫求偶行 为或者说是觅食行为。 ＧＳＯ 算法主要有 ４ 个阶段：萤火虫初始化阶 段、荧光素更新阶段、位置移动阶段以及动态感知范 围更新阶段。 算法流程如图 １ 所示。 １）初始化阶段。 初始化算法各个参数、各萤火虫的位置。 萤火 虫随机分布在目标可行域中，每只萤火虫携带的初 始荧光素 ｌ ０ 和感知半径 ｒ０ 是相同的。 ２）荧光素更新阶段。 萤火虫的荧光素大小与其所在搜索空间中的位 置有直接关系，萤火虫所在空间位置的评价值越高， 则荧光素更新后的增长就越大，即萤火虫的发光强 度也越大。 另外，萤火虫的发光强度的强弱除了受 所在空间值的影响，还和萤火虫上一次迭代的荧光 素大小以及挥发速度的快慢有关联，萤火虫位置更 新完成后，下一次迭代开始前，所有萤火虫的荧光素 都会更新，荧光素根据式（１）更新： ｌ ｉ（ｔ ＋ １） ＝ （１ － ρ）ｌ ｉ（ｔ） ＋ γＪｉ（ｔ ＋ １） （１） 式中： ρ（０ ＜ ρ ＜ １） 是萤火虫的荧光素挥发速度参 数， γ 是萤火虫的萤火素更新率参数， ｌ ｉ（ｔ） 是在第 ｔ 次迭代中萤火虫 ｉ 的荧光素值， Ｊｉ（ｔ ＋ １） 是在第 ｔ＋１ 次迭代中萤火虫 ｉ 的评价值。 ３）位置移动阶段。 算法每次迭代后萤火虫会在搜索空间中更新自 己的位置，即位置移动。 在萤火虫 ｉ 位置移动之前 必须先找到一个符合条件的同伴，这个同伴必须满 足以下 ２ 个条件：ａ）要在萤火虫 ｉ 的感知范围内；ｂ） 携带的荧光素值要大于萤火虫 ｉ 的荧光素值。 在全部满足以上 ２ 个条件的萤火虫中，根据式 （２）计算选择每个同伴萤火虫的概率大小： ｐｉｊ ＝ ｌ ｊ（ｔ） － ｌ ｉ（ｔ） ｋ∈∑Ｎｉ （ｔ） ｌ ｋ（ｔ） － ｌ ｉ（ｔ） （２） 式中： ｊ ∈ Ｎｉ（ｔ），Ｎｉ（ｔ） ＝ ｛ｊ：ｄｉ，ｊ（ｔ） ＜ ｒ ｉ ｄ（ｔ）；ｌ ｉ（ｔ） ＜ ｌ ｊ（ｔ）｝ 是在第 ｔ 次迭代中萤火虫 ｉ 的邻域集， ｒ ｉ ｄ（ｔ） 是在第 ｔ 次迭代中萤火虫 ｉ 的决策半径， ｄｉ，ｊ（ｔ） 是在 第 ｔ 次迭代中萤火虫 ｉ 、 ｊ 的空间距离。 按照轮盘赌 法则，选出同伴萤火虫 ｊ ，将依据式（３）更新位置： ｘｉ（ｔ ＋ １） ＝ ｘｉ（ｔ） ＋ ｓ（ ｘｊ（ｔ） － ｘｉ（ｔ） ‖ ｘｊ（ｔ） － ｘｉ（ｔ）‖ ） （３） 式中： ｓ 是萤火虫的移动步长， ‖·‖ 是萤火虫 ｉ 和 ｊ 的欧式空间距离。 ４）动态感知范围更新阶段。 萤火虫位置更新后，会动态调整自身感知范围， 调整的大小是基于感知范围内同伴的数量多少。 具 体根据式（４）进行计算： ｒ ｉ ｄ（ｔ ＋ １） ＝ ｍｉｎ｛ｒｓ，ｍａｘ｛０，ｒ ｉ ｄ（ｔ） ＋ β（ｎｔ － Ｎｉ（ｔ） ）｝｝ （４） 式中： ｎｔ 是调整萤火虫邻域集合大小的参数， β 是 调整萤火虫动态感知范围大小的参数。 图 １ 基本的 ＧＳＯ 算法流程 Ｆｉｇ． １ Ｆｌｏｗ ｃｈａｒｔ ｏｆ ｂａｓｉｃ ＧＳＯ ａｌｇｏｒｉｔｈｍ 第 ３ 期 唐少虎，等：一种改进的自适应步长的人工萤火虫算法 ·４７１·
·472· 智能系统学报 第10卷 1.2自适应步长人工萤火虫算法 萤火虫j的所在位置，符合条件j:d(t)<(t); 2011年欧阳喆等[6]提出了一种自适应步长算 l(t)<,(t),则确定找到食物（同伴），依据确定的 法(adaptive-step GSO,A-GSO),引入荧光因子概念 食物（同伴）可得出更新后的荧光素浓度，如果不能 以在算法搜索过程中动态改变萤火虫移动步长，使 保证l,(t+1)≤，(t),则认为先前位置已是最好觅 算法避免陷入局部最优，提高寻优速度和精度。 食地，萤火虫位置不移动：如果觅食次数超过N次， 荧光因子为 没有找到符合条件的食物（同伴），则认定当前位置 月=1x-x1 已是最好的觅食地，位置不再移动。当N,(t)为非 (5) 空集：萤火虫依据概率P(t)在集合N,(t)内选择萤 式中：H代表荧光因子，X是第i只萤火虫所在空 火虫j,得出调整后的移动步长和新的移动位置，然 间位置，X.是此次迭代中萤光素浓度最大的萤火 后判断，(t+1)≤l,(t)是否成立，如果是则进行位 虫所在的空间位置，d是此次迭代中的最优萤火 置移动，否则不移动。 虫到其余全部萤火虫的空间距离的最大值。 为了测试觅食次数N对算法性能的影响，本文 基于荧光因子的自适应移动步长按照式(6)进 把该值分别设置为5个不同的值对同一函数的迭代 行调整。 值进行对比。测试函数如下： s:=smin+（sams-smin）Hg (6) 式中：s,代表调整后的萤光虫移动步长，5、sn代 F,()=立(0.2X+0.1xsin(2x) =1 表萤火虫移动步长的最大值和最小值，H代表荧光 测试结果如图2所示，从图中可知，该值越小越 因子。 易陷入局部最优，但是该值增大后并不能保证提高 算法搜索精度，如图2(a)中觅食次数N=10时算法 2改进的人工萤火虫算法原理 对函数的迭代精度最高，而图2(b)中觅食次数N= 2.1基于觅食行为的自适应步长人工萤火虫算法 10、15和30时，算法对函数的迭代精度相当，其中 在GS0以及A-GS0算法中，算法运行过程中 精度最高是觅食次数为N=10时，因此在下面算法 可能出现一些萤火虫的邻域萤火虫集合N,(t)为空 试验对比分析中，将觅食次数设置为10。 集的现象，对这些萤火虫的在算法迭代过程中将会 0.7 出现位置不移动的情况，这将导致算法收敛速度降 0.6 低并易陷入局部最优值。2011年张军丽等8)提出 0.5 了利用人工鱼群的觅食行为选择下一个移动的位 置，但是没有考虑步长的自适应调整。本文借鉴觅 罩04 食行为，设计了邻域集合为空集的萤火虫自适应步 0.3 长移动策略，提出一种改进的基于觅食行为的自适 0.2 V=3N=6 应步长的人工萤火虫算法(foraging-behavior adap- 5N=30 0.1 N=10 tive-step GSO,FA-GSO),算法改进的基本思想是在 0 100 200 300 400 邻居集合N:(t)为空集的萤火虫位置更新前，先在 迭代次数 其动态决策范围N:(t)内执行觅食行为，将该位置 (a)对比实验1 作为萤火虫在下一时刻移动的方向，计算荧光因子 0.7l 得出动态调整的移动步长（自适应步长），然后进行 0.6 位置的移动，接着更新萤火虫的感知范围，最后计算 萤火虫的荧光素。这样在不影响算法整体求解效率 0.5 的基础上能够进一步精确、快速求解最优值。 画0.4 具体改进如下，当N,(t)为空集：萤火虫在其动 90.3 态决策半径t(t)内执行觅食行为，设定觅食次数 W=3 0.2 最大值为N次，该值的大小将影响算法迭代的精度 N=6 0.1 N-15 N-30 和效率，如何设定合理的觅食次数使得算法在搜索 N=10 精度和迭代效率2个方面得到较好的性能平衡，对 100 200 300 400 迭代次数 于改进的算法有着重要的意义。具体在实现中，有 多种设计方法，可以将该值设置为固定值，也可以在 (b)对比实验2 图2觅食次数为不同值时函数迭代值对比 一定范围内进行随机设置。萤火虫每次觅食意味着 Fig.2 Iterative value contrast of different foraging times 寻找下次迭代移动方向，如果存在食物假定为一个
１．２ 自适应步长人工萤火虫算法 ２０１１ 年欧阳喆等［ ６ ］ 提出了一种自适应步长算 法（ａｄａｐｔｉｖｅ⁃ｓｔｅｐ ＧＳＯ， Ａ⁃ＧＳＯ），引入荧光因子概念 以在算法搜索过程中动态改变萤火虫移动步长，使 算法避免陷入局部最优，提高寻优速度和精度。 荧光因子为 Ｈｉ ＝ ‖ Ｘｉ － Ｘｍ‖ ｄｍａｘ （５） 式中： Ｈｉ 代表荧光因子， Ｘｉ 是第 ｉ 只萤火虫所在空 间位置， Ｘｍ 是此次迭代中萤光素浓度最大的萤火 虫所在的空间位置， ｄｍａｘ 是此次迭代中的最优萤火 虫到其余全部萤火虫的空间距离的最大值。 基于荧光因子的自适应移动步长按照式（６）进 行调整。 ｓｉ ＝ ｓｍｉｎ ＋ （ｓｍａｘ － ｓｍｉｎ ）Ｈｉ （６） 式中： ｓｉ 代表调整后的萤光虫移动步长， ｓｍａｘ 、 ｓｍｉｎ 代 表萤火虫移动步长的最大值和最小值， Ｈｉ 代表荧光 因子。 ２ 改进的人工萤火虫算法原理 ２．１ 基于觅食行为的自适应步长人工萤火虫算法 在 ＧＳＯ 以及 Ａ⁃ＧＳＯ 算法中，算法运行过程中 可能出现一些萤火虫的邻域萤火虫集合 Ｎｉ（ｔ） 为空 集的现象，对这些萤火虫的在算法迭代过程中将会 出现位置不移动的情况，这将导致算法收敛速度降 低并易陷入局部最优值。 ２０１１ 年张军丽等［８］ 提出 了利用人工鱼群的觅食行为选择下一个移动的位 置，但是没有考虑步长的自适应调整。 本文借鉴觅 食行为，设计了邻域集合为空集的萤火虫自适应步 长移动策略，提出一种改进的基于觅食行为的自适 应步长的人工萤火虫算法（ ｆｏｒａｇｉｎｇ⁃ｂｅｈａｖｉｏｒ ａｄａｐ⁃ ｔｉｖｅ⁃ｓｔｅｐ ＧＳＯ， ＦＡ－ＧＳＯ），算法改进的基本思想是在 邻居集合 Ｎｉ（ｔ） 为空集的萤火虫位置更新前，先在 其动态决策范围 Ｎｉ（ｔ） 内执行觅食行为，将该位置 作为萤火虫在下一时刻移动的方向，计算荧光因子 得出动态调整的移动步长（自适应步长），然后进行 位置的移动，接着更新萤火虫的感知范围，最后计算 萤火虫的荧光素。 这样在不影响算法整体求解效率 的基础上能够进一步精确、快速求解最优值。 具体改进如下，当 Ｎｉ（ｔ） 为空集：萤火虫在其动 态决策半径 ｒ ｉ ｄ（ｔ） 内执行觅食行为，设定觅食次数 最大值为 Ｎ 次，该值的大小将影响算法迭代的精度 和效率，如何设定合理的觅食次数使得算法在搜索 精度和迭代效率 ２ 个方面得到较好的性能平衡，对 于改进的算法有着重要的意义。 具体在实现中，有 多种设计方法，可以将该值设置为固定值，也可以在 一定范围内进行随机设置。 萤火虫每次觅食意味着 寻找下次迭代移动方向，如果存在食物假定为一个 萤火虫 ｊ 的所在位置，符合条件 ｊ：ｄｉ，ｊ（ｔ） ＜ ｒ ｉ ｄ（ｔ）； ｌ ｉ（ｔ） ＜ ｌ ｊ（ｔ） ，则确定找到食物（同伴），依据确定的 食物（同伴）可得出更新后的荧光素浓度，如果不能 保证 ｌ ｉ（ｔ ＋ １） ≤ ｌ ｉ（ｔ） ，则认为先前位置已是最好觅 食地，萤火虫位置不移动；如果觅食次数超过 Ｎ 次， 没有找到符合条件的食物（同伴），则认定当前位置 已是最好的觅食地，位置不再移动。 当 Ｎｉ（ｔ） 为非 空集：萤火虫依据概率 ｐｉｊ（ｔ） 在集合 Ｎｉ（ｔ） 内选择萤 火虫 ｊ ，得出调整后的移动步长和新的移动位置，然 后判断 ｌ ｉ（ｔ ＋ １） ≤ ｌ ｉ（ｔ） 是否成立，如果是则进行位 置移动，否则不移动。 为了测试觅食次数 Ｎ 对算法性能的影响，本文 把该值分别设置为 ５ 个不同的值对同一函数的迭代 值进行对比。 测试函数如下： Ｆ１（ｘ） ＝ ∑ ｎ ｉ ＝ １ （０．２ｘ ２ ｉ ＋ ０．１ｘ ２ ｉ ｓｉｎ(２ｘ) ） 测试结果如图 ２ 所示，从图中可知，该值越小越 易陷入局部最优，但是该值增大后并不能保证提高 算法搜索精度，如图 ２（ａ）中觅食次数 Ｎ＝ １０ 时算法 对函数的迭代精度最高，而图 ２（ｂ）中觅食次数 Ｎ ＝ １０、１５ 和 ３０ 时，算法对函数的迭代精度相当，其中 精度最高是觅食次数为 Ｎ ＝ １０ 时，因此在下面算法 试验对比分析中，将觅食次数设置为 １０。 （ａ） 对比实验 １ （ｂ） 对比实验 ２ 图 ２ 觅食次数为不同值时函数迭代值对比 Ｆｉｇ． ２ Ｉｔｅｒａｔｉｖｅ ｖａｌｕｅ ｃｏｎｔｒａｓｔ ｏｆ ｄｉｆｆｅｒｅｎｔ ｆｏｒａｇｉｎｇ ｔｉｍｅｓ ·４７２· 智 能 系 统 学 报 第 １０ 卷
第3期 唐少虎，等：一种改进的自适应步长的人工萤火虫算法 ·473. 2.2FA-GS0算法收敛性分析 p,觅食次数N,萤光素更新率y以及设定迭代次数 GS0算法、PS0算法（粒子群算法）都属于随机 N等，形成初始萤火虫群： 优化算法，刘洲洲等]和张慧斌等[0]分别对2种算 2)执行FA-GS0算法搜索。 法的收敛性给出了分析证明，他们依据的是Solis!山 对初始化的萤火虫个体，分别执行以下操作： 给出的随机优化算法收敛性判定标准。 a)对每一个萤火虫i按式(1)更新荧光素的值， 为了分析FA-GSO算法的收敛性，本文参考So 判断l(t+1)≤：(t)是否成立，如果是则转向b), s提出的判定标准，给出分析证明。 否则在转向b)前，令x,(t+1)=x(t)。 条件1f(D(x,))≤f(x),并且如果专∈S, b)在动态决策域半径r(t)内，求萤火虫i的邻 则有f(D(x,))≤f代)。其中，f和S分别为目标 域集合N(t)o 函数和可行解空间，D(x,)为算法第t+1次的迭 c)选择t+1时刻移动的方向： 代结果。 若N,(t)不为空集，利用式(2)计算向邻域内萤 条件2如果D∈S,x(D)>0,并且 Π(1- 火虫j的移动概率P,(t),其中0<(t)<r,为萤 火虫个体的感知半径，并采用轮盘赌法则选择邻域内 u(D))=0。其中，(D)为D的勒贝格测度， 萤火虫个体，确定为下一时刻莹火虫的移动方向： u(D)为算法第k次迭代解的概率测度。 若N,(t)为空集，在其动态决策半径(t)内执 收敛判定定理设函数f可测，搜索空间S是 行觅食行为，设定觅食次数最大值为N次，每次觅 R”上的可测度子集，如果算法满足条件1和条件2， 食意味着寻找下次迭代移动方向，如果存在食物假 则有imp(x∈S·)=1,即算法以概率1收敛于全 定为一个萤火虫j的所在位置，符合条件j:d,(t)< 局最优值。其中S·是全局最优点集合，x是算法 t(t);l.(t)<,(t),则确定找到食物（同伴）：如果 迭代过程中的数列。 觅食次数超过N次，没有找到符合条件的食物（同 定理FA-GS0算法以概率1收敛于全局最优解。 伴)，则认定当前位置已是最好的觅食地，位置不再 证明根据1.2和2.1小节的描述，由于算法 移动。 的步长是自适应调整的，依据是式(5)、(6)，并且保 d)根据式(5)计算每个萤火虫的荧光因子，并 证了无同伴萤火虫的优化搜索，通过判断萤火虫前 用式(6)计算动态移动步长。 后2次的荧光素大小确定位置是否移动，依据是式 e)萤火虫进行位置移动，根据式(3)更新位置： (3)和觅食策略，所以可以得出对于专∈S,有 )根据式(4)更新萤火虫的动态感知范围。 f八D(x,))≤f(x),即满足条件1。 3)判断是否达到指定的迭代次数，如果达到则 假设L为萤火虫i在第t次迭代过程中搜索解支 转向步骤4)，否则转向2)。 撑集，随着算法迭代次数的增加，出现萤火虫的聚集 4)输出结果，程序结束。 现象并且也可能出现萤火虫“不动”的现象，(L)逐 3 实验结果与分析 渐变小，使的(UL∩S)<v(S),即不满足条件2。 为了验证所设计的算法的有效性。选取4个标 另改进的算法使得萤火虫都可以执行觅食行为， 准测试函数进行验证，并与GS0算法以及自适应步 当觅食次数N→o,则有0< 2a(D)≤1,9L=s 长GS0算法(A-GS0)进行比较。这4个常用的测 i=1 试函数如下。 进一步可得limD(x)=D(S)}=1,即Π(1- k=0 44(D)=0,所以满足条件2。 F()=202+01m2).P)=店 综上可得：imp(x”∈S)=1,由收敛判定定理 F3(x)= （1m(-+,-) =1 可知FA-GS0算法以概率1收敛于全局最优解，证毕。 2.3FA-GS0实现步骤 F.(x)=∑(x,2-10c0s(2mx,)+10) 综上，基于觅食行为的自适应步长人工萤火虫 实验的程序运行环境为：处理器Intel3CPU 算法步骤描述如下： M380,主频为2.53GHz,内存2GB,操作系统为 1)初始化萤火虫群体和参数。将n只萤火虫随 Windows XP,集成开发环境为Visual Studio2O05,算 机地分布在搜索空间m维中，同时为每只萤火虫初 法用VB.NET编写。 始化以相同的荧光素。和感应半径r。,初始化最大 算法参数初始化为萤火虫数量n为50，荧光素 移动步长s,最小移动步长s。,萤光素挥发系数 更新率r为0.6，荧光素挥发系数p为0.4，初始荧光
２．２ ＦＡ⁃ＧＳＯ 算法收敛性分析 ＧＳＯ 算法、ＰＳＯ 算法（粒子群算法）都属于随机 优化算法，刘洲洲等［９］和张慧斌等［１０］分别对 ２ 种算 法的收敛性给出了分析证明，他们依据的是 Ｓｏｌｉｓ ［１１］ 给出的随机优化算法收敛性判定标准。 为了分析 ＦＡ⁃ＧＳＯ 算法的收敛性，本文参考 Ｓｏ⁃ ｌｉｓ 提出的判定标准，给出分析证明。 条件 １ ｆ（Ｄ（ｘ，ξ）） ≤ ｆ（ｘ） ，并且如果 ξ ∈ Ｓ ， 则有 ｆ（Ｄ（ｘ，ξ）） ≤ ｆ（ξ） 。 其中， ｆ 和 Ｓ 分别为目标 函数和可行解空间， Ｄ（ｘ，ξ） 为算法第 ｔ＋１ 次的迭 代结果。 条件 ２ 如果 ∀Ｄ ∈ Ｓ，ｖ（Ｄ） ＞ ０，并且 ∏ ¥ ｋ ＝ ０ （１ － μｋ（Ｄ）） ＝ ０。 其 中， ｖ（Ｄ） 为 Ｄ 的 勒 贝 格 测 度， μｋ（Ｄ） 为算法第 ｋ 次迭代解的概率测度。 收敛判定定理 设函数 ｆ 可测，搜索空间 Ｓ 是 Ｒ ｎ 上的可测度子集，如果算法满足条件 １ 和条件 ２， 则有 ｌｉｍ ｋ→¥ ｐ（ｘ ｋ ∈ Ｓ ∗ ） ＝ １，即算法以概率 １ 收敛于全 局最优值。 其中 Ｓ ∗ 是全局最优点集合， ｘ ｋ 是算法 迭代过程中的数列。 定理 ＦＡ⁃ＧＳＯ 算法以概率１ 收敛于全局最优解。 证明 根据 １．２ 和 ２．１ 小节的描述，由于算法 的步长是自适应调整的，依据是式（５）、（６），并且保 证了无同伴萤火虫的优化搜索，通过判断萤火虫前 后 ２ 次的荧光素大小确定位置是否移动，依据是式 （３） 和觅食策略， 所以可以得出对于 ξ ∈ Ｓ ， 有 ｆ（Ｄ（ｘ，ξ）） ≤ ｆ（ｘ） ，即满足条件 １。 假设 Ｌ 为萤火虫 ｉ 在第 ｔ 次迭代过程中搜索解支 撑集，随着算法迭代次数的增加，出现萤火虫的聚集 现象并且也可能出现萤火虫“不动”的现象， ｖ（Ｌ） 逐 渐变小，使的 ｖ（∪ ｎ ｉ ＝ １ Ｌ ∩ Ｓ） ＜ ｖ（Ｓ） ，即不满足条件 ２。 另改进的算法使得萤火虫都可以执行觅食行为， 当觅食次数 Ｎ →¥，则有０ ＜ ∑ ｎ ｉ ＝ １ μ（Ｄ） ≤１， ∪ ｎ ｉ ＝ １ Ｌ ＝ Ｓ， 进一步可得 μ｛ｌｉｍ ｎ→¥ Ｄ（ｘ ｎ ） ＝ Ｄ（Ｓ ∗ ）｝ ＝ １，即 ∏ ¥ ｋ ＝ ０ （１ － μｋ（Ｄ）） ＝ ０，所以满足条件 ２。 综上可得： ｌｉｍ ｎ→¥ ｐ（ｘ ｎ ∈ Ｓ ∗ ） ＝ １，由收敛判定定理 可知 ＦＡ⁃ＧＳＯ 算法以概率 １ 收敛于全局最优解，证毕。 ２．３ ＦＡ⁃ＧＳＯ 实现步骤 综上，基于觅食行为的自适应步长人工萤火虫 算法步骤描述如下： １）初始化萤火虫群体和参数。 将 ｎ 只萤火虫随 机地分布在搜索空间 ｍ 维中，同时为每只萤火虫初 始化以相同的荧光素 ｌ ０ 和感应半径 ｒ０ ，初始化最大 移动步长 ｓｍａｘ ，最小移动步长 ｓｍｉｎ ，萤光素挥发系数 ρ ，觅食次数 Ｎ，萤光素更新率 γ 以及设定迭代次数 Ｎｍａｘ 等，形成初始萤火虫群； ２）执行 ＦＡ⁃ＧＳＯ 算法搜索。 对初始化的萤火虫个体，分别执行以下操作： ａ）对每一个萤火虫 ｉ 按式（１）更新荧光素的值， 判断 ｌ ｉ（ｔ ＋ １） ≤ ｌ ｉ（ｔ） 是否成立，如果是则转向 ｂ）， 否则在转向 ｂ）前，令 ｘｉ（ｔ ＋ １） ＝ ｘｉ（ｔ） 。 ｂ）在动态决策域半径 ｒ ｉ ｄ（ｔ） 内，求萤火虫 ｉ 的邻 域集合 Ｎｉ（ｔ） 。 ｃ）选择 ｔ＋１ 时刻移动的方向： 若 Ｎｉ（ｔ） 不为空集，利用式（２）计算向邻域内萤 火虫 ｊ 的移动概率 ｐｉｊ（ｔ） ，其中 ０ ＜ ｒ ｉ ｄ（ｔ） ＜ ｒｓ，ｒｓ 为萤 火虫个体的感知半径，并采用轮盘赌法则选择邻域内 萤火虫个体，确定为下一时刻萤火虫的移动方向； 若 Ｎｉ（ｔ） 为空集，在其动态决策半径 ｒ ｉ ｄ（ｔ） 内执 行觅食行为，设定觅食次数最大值为 Ｎ 次，每次觅 食意味着寻找下次迭代移动方向，如果存在食物假 定为一个萤火虫 ｊ 的所在位置，符合条件 ｊ：ｄｉ，ｊ（ｔ） ＜ ｒ ｉ ｄ（ｔ）；ｌ ｉ（ｔ） ＜ ｌ ｊ（ｔ） ，则确定找到食物（同伴）；如果 觅食次数超过 Ｎ 次，没有找到符合条件的食物（同 伴），则认定当前位置已是最好的觅食地，位置不再 移动。 ｄ）根据式（５）计算每个萤火虫的荧光因子，并 用式（６）计算动态移动步长。 ｅ）萤火虫进行位置移动，根据式（３）更新位置； ｆ）根据式（４）更新萤火虫的动态感知范围。 ３）判断是否达到指定的迭代次数，如果达到则 转向步骤 ４），否则转向 ２）。 ４）输出结果，程序结束。 ３ 实验结果与分析 为了验证所设计的算法的有效性。 选取 ４ 个标 准测试函数进行验证，并与 ＧＳＯ 算法以及自适应步 长 ＧＳＯ 算法（Ａ⁃ＧＳＯ）进行比较。 这 ４ 个常用的测 试函数如下。 Ｆ１（ｘ） ＝ ∑ ｎ ｉ ＝ １ （０．２ｘ ２ ｉ ＋ ０．１ｘ ２ ｉ ｓｉｎ ２ｘ），Ｆ２（ｘ） ＝ ∑ ｎ ｉ ＝ １ ｘ ２ ｉ Ｆ３（ｘ） ＝ ∑ ｎ－１ ｉ ＝ １ （１００ （ｘｉ＋１ － ｘ ２ ｉ ） ２ ＋ （ｘｉ － １） ２ ） Ｆ４（ｘ） ＝ ∑ ｎ ｉ ＝ １ （ｘｉ ２ － １０ｃｏｓ（２πｘｉ） ＋ １０） 实验的程序运行环境为：处理器 Ｉｎｔｅｌ ｉ３ ＣＰＵ Ｍ３８０，主频为 ２． ５３ ＧＨｚ，内存 ２ ＧＢ，操作系统为 Ｗｉｎｄｏｗｓ ＸＰ，集成开发环境为 Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２００５，算 法用 ＶＢ．ＮＥＴ 编写。 算法参数初始化为萤火虫数量 ｎ 为 ５０，荧光素 更新率 ｒ 为 ０．６，荧光素挥发系数 ｐ 为 ０．４，初始荧光 第 ３ 期 唐少虎，等：一种改进的自适应步长的人工萤火虫算法 ·４７３·
.474. 智能系统学报 第10卷 素大小为5，感知范围为10，初始最小步长为0.01， 索的最优解并没有好于GS0,但是FA-GS0的最优 最大步长为1，b=0.08,n,=5,觅食次数为10，最大 解还是三者中精度最高的，说明搜寻机制改进后的 迭代次数为300。对于上述4个标准测试函数进行 算法在寻优精度方面有着较高的稳定性。从图中可 试验，维数为10。 以看出FA-GSO算法寻优比较稳定和快速。综上所 表1列出4个算法对选定的标准测试函数求解 述，FA-GS0算法在函数搜索精度以及速度2个关 所得到的最优值、最差值、平均值和平均迭代次数比 键方面的性能有着明显的改进，从而有助于提高寻 较，表中的平均迭代次数为10次独立实验所得到的 优问题的求解效率。 迭代次数平均值。从表1中的数据对比中可以看到， 3.5 FA-GS0算法平均通过42次迭代就找到了函数 3.0 F,(x)最小值，而其他2种算法都没有找到最小值， 把2.5 而A-GS0的最优解要好于GS0迭代的最优解。对比 22.0 3种算法搜索其他3个函数的最优解看，FA-GS0的 最优解也是最接近最小值，A-GS0的最优解好于GS0 搜索的最优解，观察另外2个指标，即最差解和平均 解的数据对照，也可以得出类似的结论。所以可以看 0.5 GSO A-GSO 出FA-GSO算法在搜索函数极值的最优解、最差解以 FA-GSO 0 100 200 300 400 及平均解都要比另外3种算法有了一定程度上的提 迭代次数 高，表明FA-GS0算法在收敛精度上要优于其他2种 图3F,(x)函数值随3个算法迭代曲线 算法。观察表中的平均迭代次数，对比3个算法分别 Fig.3 Iterative values graph of F (x)tested by the 迭代给定的每个函数，可以看到FA-GS0算法平均迭 three algorithms 代次数要少于其他2个算法，表明FA-GS0算法在收 3.5m 敛速度上要优于另外2种算法。 3.0 表1GSO、A-GS0和FA-GS0算法函数测试指标 过2.5h Table 1 Function test indexes comparison of GSO, A-GSO and FA-GSO algorithm 平均 ☒1.5 测试函数算法 最优解最差解平均解 迭代次数 是1o GSO 0.235 3.360 2.370 ® 0.5 GSO F,(x)A-GS00.081 2.760 1.640 72 A-GSOFA-GSO FA-GS00.000 0.524 0.065 42 0 100 200 300 400 迭代次数 GS00.256 3.5602.130 75 图4F,(x)函数值随3个算法迭代曲线 F2(x)A-GS00.102 1.5600.850 56 FA-GS00.014 0.096 0.067 53 Fig.4 Iterative values graph of F2(x)tested by the three algorithms GSO 1.9510.586.54 106 3.5m F(x)A-GS00.41 3.57 2.65 80 FA-GS00.15 1.56 0.89 61 3.0 GS00.16 2.672.130 81 细2.5 F.(x)A-GS00.12 2.921.360 77 FA-Gs00.030.830.482 46 从图3~6中看到，4个函数的FA-GS0算法迭 代曲线很接近横轴，即函数适应值很接近最小值，迭 GSO 0.5 代精度要好于另外2种算法，而且算法能够找到最 A-GSO FA-GSO 优解前的迭代次数也是最少的。此外，观察GS0算 100 200 300 400 法在迭代函数F,(x)和F,(x)时都发生了适应值曲 迭代次数 线的震荡现象，验证了固定步长带来的寻优缺陷，而 图5F,(x)函数值随3个算法迭代曲线 A-GS0和FA-GS0算法曲线都相对稳定。从图6中 Fig.5 Iterative values graph of F(x)tested by the 还可以看到A-GS0算法在迭代函数F,(x)时所搜 three algorithms
素大小为 ５，感知范围为 １０，初始最小步长为 ０．０１， 最大步长为 １，ｂ ＝ ０．０８， ｎｔ ＝ ５，觅食次数为 １０，最大 迭代次数为 ３００。 对于上述 ４ 个标准测试函数进行 试验，维数为 １０。 表 １ 列出 ４ 个算法对选定的标准测试函数求解 所得到的最优值、最差值、平均值和平均迭代次数比 较，表中的平均迭代次数为 １０ 次独立实验所得到的 迭代次数平均值。 从表 １ 中的数据对比中可以看到， ＦＡ⁃ＧＳＯ 算法平均通过 ４２ 次迭代就找到了函数 Ｆ１（ｘ） 最小值，而其他 ２ 种算法都没有找到最小值， 而 Ａ⁃ＧＳＯ 的最优解要好于 ＧＳＯ 迭代的最优解。 对比 ３ 种算法搜索其他 ３ 个函数的最优解看，ＦＡ⁃ＧＳＯ 的 最优解也是最接近最小值，Ａ⁃ＧＳＯ 的最优解好于 ＧＳＯ 搜索的最优解，观察另外 ２ 个指标，即最差解和平均 解的数据对照，也可以得出类似的结论。 所以可以看 出 ＦＡ⁃ＧＳＯ 算法在搜索函数极值的最优解、最差解以 及平均解都要比另外 ３ 种算法有了一定程度上的提 高，表明 ＦＡ⁃ＧＳＯ 算法在收敛精度上要优于其他 ２ 种 算法。 观察表中的平均迭代次数，对比 ３ 个算法分别 迭代给定的每个函数，可以看到 ＦＡ⁃ＧＳＯ 算法平均迭 代次数要少于其他 ２ 个算法，表明 ＦＡ⁃ＧＳＯ 算法在收 敛速度上要优于另外 ２ 种算法。 表 １ ＧＳＯ、Ａ⁃ＧＳＯ 和 ＦＡ⁃ＧＳＯ 算法函数测试指标 Ｔａｂｌｅ １ Ｆｕｎｃｔｉｏｎ ｔｅｓｔ ｉｎｄｅｘｅｓ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＧＳＯ， Ａ⁃ＧＳＯ ａｎｄ ＦＡ⁃ＧＳＯ ａｌｇｏｒｉｔｈｍ 测试函数 算法 最优解 最差解 平均解 平均 迭代次数 Ｆ１（ｘ） ＧＳＯ ０．２３５ ３．３６０ ２．３７０ ８５ Ａ⁃ＧＳＯ ０．０８１ ２．７６０ １．６４０ ７２ ＦＡ⁃ＧＳＯ ０．０００ ０．５２４ ０．０６５ ４２ Ｆ２（ｘ） ＧＳＯ ０．２５６ ３．５６０ ２．１３０ ７５ Ａ⁃ＧＳＯ ０．１０２ １．５６０ ０．８５０ ５６ ＦＡ⁃ＧＳＯ ０．０１４ ０．０９６ ０．０６７ ５３ Ｆ３（ｘ） ＧＳＯ １．９５ １０．５８ ６．５４ １０６ Ａ⁃ＧＳＯ ０．４１ ３．５７ ２．６５ ８０ ＦＡ⁃ＧＳＯ ０．１５ １．５６ ０．８９ ６１ Ｆ４（ｘ） ＧＳＯ ０．１６ ２．６７ ２．１３０ ８１ Ａ⁃ＧＳＯ ０．１２ ２．９２ １．３６０ ７７ ＦＡ⁃ＧＳＯ ０．０３ ０．８３ ０．４８２ ４６ 从图 ３～ ６ 中看到，４ 个函数的 ＦＡ⁃ＧＳＯ 算法迭 代曲线很接近横轴，即函数适应值很接近最小值，迭 代精度要好于另外 ２ 种算法，而且算法能够找到最 优解前的迭代次数也是最少的。 此外，观察 ＧＳＯ 算 法在迭代函数 Ｆ１（ｘ） 和 Ｆ２（ｘ） 时都发生了适应值曲 线的震荡现象，验证了固定步长带来的寻优缺陷，而 Ａ⁃ＧＳＯ 和 ＦＡ⁃ＧＳＯ 算法曲线都相对稳定。 从图 ６ 中 还可以看到 Ａ⁃ＧＳＯ 算法在迭代函数 Ｆ４（ｘ） 时所搜 索的最优解并没有好于 ＧＳＯ，但是 ＦＡ⁃ＧＳＯ 的最优 解还是三者中精度最高的，说明搜寻机制改进后的 算法在寻优精度方面有着较高的稳定性。 从图中可 以看出 ＦＡ⁃ＧＳＯ 算法寻优比较稳定和快速。 综上所 述，ＦＡ⁃ＧＳＯ 算法在函数搜索精度以及速度 ２ 个关 键方面的性能有着明显的改进，从而有助于提高寻 优问题的求解效率。 图 ３ Ｆ１（ｘ）函数值随 ３ 个算法迭代曲线 Ｆｉｇ． ３ Ｉｔｅｒａｔｉｖｅ ｖａｌｕｅｓ ｇｒａｐｈ ｏｆ Ｆ１（ｘ） ｔｅｓｔｅｄ ｂｙ ｔｈｅ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ 图 ４ Ｆ２（ｘ）函数值随 ３ 个算法迭代曲线 Ｆｉｇ． ４ Ｉｔｅｒａｔｉｖｅ ｖａｌｕｅｓ ｇｒａｐｈ ｏｆ Ｆ２（ｘ） ｔｅｓｔｅｄ ｂｙ ｔｈｅ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ 图 ５ Ｆ３（ｘ）函数值随 ３ 个算法迭代曲线 Ｆｉｇ． ５ Ｉｔｅｒａｔｉｖｅ ｖａｌｕｅｓ ｇｒａｐｈ ｏｆ Ｆ３（ｘ） ｔｅｓｔｅｄ ｂｙ ｔｈｅ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ·４７４· 智 能 系 统 学 报 第 １０ 卷
第3期 唐少虎，等：一种改进的自适应步长的人工萤火虫算法 .475. 3.5m modal functions J].Computer Science,2011,38(7): 3.0 220-224. [6]欧阳喆，周永权.自适应步长萤火虫优化算法[J].计算 坦2.5 机应用，2011,31(7)：1804-1807. 2.0 OUYANG Zhe,ZHOU Yongquan.Self-adaptive step glow- worm swarm optimization algorithm[].Journal of Computer Applications,2011,31(7):1804-1807. A-GSO [7]KRISHNANAND K N D,GHOSE D.Glowworm swarm opti- 0.5 GSO FA-GSO mization:a new method for optimizing multi-modal functions 0 100 200 300 400 [J].Computational Intelligence Studies,2009,1(1):93- 迭代次数 119 图6F,(x)函数值随3个算法迭代曲线 [8]张军丽，周永权.人工萤火虫与差分进化混合优化算法 Fig.6 Iterative values graph of F(x)tested by the [J刀.信息与控制，2011,40(5)：608-613. three algorithms ZHANG Junli,ZHOU Yongquan.A hybrid optimization al- gorithm based on artificial glowworm swarm and differential 结束语 evolution[J].Information and Control,2011,40(5):608- 613. 针对GS0和A-GS0算法存在的不足，为了有 [9]刘洲洲，王福豹，张克旺.基于改进萤火虫优化算法的 效避免算法过快陷入局部最优和寻优值的震荡现 WSN覆盖优化分析[J].传感技术学报，2013,26(5)： 象，通过改进算法的迭代机制，在提出的FA-GSO算 675-682. 法中引入觅食行为并自适应调整移动步长进一步改 LIU Zhouzhou,WANG Fubao,ZHANG Kewang.Perform- 善了局部搜索能力。本文采用3种算法对标准测试 ance analysis of improved glowworm swarm optimization al- 函数的试验，对照相关迭代指标并分析后得出FA- gorithm and the application in coverage optimization of WSNs[J].Chinese Journal of Sensors and Actuators,2013, GS0算法寻优结果优于GS0和A-GS0算法，改进 26(5):675-682. 的算法是有效的，提高了寻优稳定性、收敛速度和求 [10]张慧斌，王鸿斌，胡志军.PS0算法全局收敛性分析 解精度，从而改善了算法的迭代效率。未来将要做 [J].计算机工程与应用，2011,47(34)：61-63. 的工作内容，可以在算法参数的优化分析及算法的 ZHANG Huibin,WANG Hongbin,HU Zhijun.Analysis of 应用（如交通信号和交通模型的优化等）做进一步 particle swarm optimization algorithm global convergence 研究和探索。 method J].Computer Engineering and Applications, 2011,47(34):61-63. 参考文献： [11]SOLIS F J,WETS R J B.Minimization by random search [1]LIAO Wenhua,KAO Yucheng,LI Yingshan.A sensor de- techniques [J].Mathematics of Operations Research, ployment approach using glowworm swarm optimization algo- 1981,6(1):19-30. rithm in wireless sensor networks[J].Expert Systems with 作者简介： Applications,38(10):12180-12188. 唐少虎，男，1986年生，博士研究 [2]KRISHNANAND K N D,GHOSE D.Glowworm swarm 生，主要研究方向为交通控制、群智能 based optimization algorithm for multimodal functions with 算法。 collective robotics applications [J].Multiagent and Grid Systems,2006,2(3)209-222. [3]KRISHNANAND K N,GHOSE D.Glowworm swarm optimi- zation for simultaneous capture of multiple local optima of multimodal functions[J].Swarm Intelligence,2009,3(2): 刘小明.男，1974年生，教授博士 87-124 主要研究方向为交通控制、交通流理 [4]YANG Yan,ZHOU Yongquan,GONG Qiaoqiao.Hybrid ar- 论。近年来主持国家级、省部级科研项 tificial glowworm swarm optimization algorithm for solving 目8项，获大连市科学技术一等奖1 system of nonlinear equations[].Journal of Computational 项，北京市科学技术成果二、三等奖各1 Information Systems,2010,6(10)3431-3438. 项，中国智能交通协会科学技术奖二等 [5]黄正新，周永权.自适应步长萤火虫群多模态函数优化 奖1项。申请发明专利3项，授权发明专利1项，授权实用 算法[J].计算机科学，2011,38(7)：220-224. 新型专利1项，获软件著作权4项。发表学术论文40余篇， HUANG Zhengxin,ZHOU Yongquan.Self-adaptive step 出版专著1部、译著1部。 glowworm swarm optimization algorithm for optimizing multi-
图 ６ Ｆ４（ｘ）函数值随 ３ 个算法迭代曲线 Ｆｉｇ． ６ Ｉｔｅｒａｔｉｖｅ ｖａｌｕｅｓ ｇｒａｐｈ ｏｆ Ｆ４（ｘ） ｔｅｓｔｅｄ ｂｙ ｔｈｅ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ４ 结束语 针对 ＧＳＯ 和 Ａ⁃ＧＳＯ 算法存在的不足，为了有 效避免算法过快陷入局部最优和寻优值的震荡现 象，通过改进算法的迭代机制，在提出的 ＦＡ⁃ＧＳＯ 算 法中引入觅食行为并自适应调整移动步长进一步改 善了局部搜索能力。 本文采用 ３ 种算法对标准测试 函数的试验，对照相关迭代指标并分析后得出 ＦＡ⁃ ＧＳＯ 算法寻优结果优于 ＧＳＯ 和 Ａ⁃ＧＳＯ 算法，改进 的算法是有效的，提高了寻优稳定性、收敛速度和求 解精度，从而改善了算法的迭代效率。 未来将要做 的工作内容，可以在算法参数的优化分析及算法的 应用（如交通信号和交通模型的优化等）做进一步 研究和探索。 参考文献： ［１］ＬＩＡＯ Ｗｅｎｈｕａ， ＫＡＯ Ｙｕｃｈｅｎｇ， ＬＩ Ｙｉｎｇｓｈａｎ． Ａ ｓｅｎｓｏｒ ｄｅ⁃ ｐｌｏｙｍｅｎｔ ａｐｐｒｏａｃｈ ｕｓｉｎｇ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ， ３８（１０）： １２１８０⁃１２１８８． ［２］ ＫＲＩＳＨＮＡＮＡＮＤ Ｋ Ｎ Ｄ， ＧＨＯＳＥ Ｄ． Ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｂａｓｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ ｗｉｔｈ ｃｏｌｌｅｃｔｉｖｅ ｒｏｂｏｔｉｃｓ ａｐｐｌｉｃａｔｉｏｎｓ ［ Ｊ ］． Ｍｕｌｔｉａｇｅｎｔ ａｎｄ Ｇｒｉｄ Ｓｙｓｔｅｍｓ， ２００６， ２（３） ２０９⁃２２２． ［３］ＫＲＩＳＨＮＡＮＡＮＤ Ｋ Ｎ， ＧＨＯＳＥ Ｄ． Ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉ⁃ ｚａｔｉｏｎ ｆｏｒ ｓｉｍｕｌｔａｎｅｏｕｓ ｃａｐｔｕｒｅ ｏｆ ｍｕｌｔｉｐｌｅ ｌｏｃａｌ ｏｐｔｉｍａ ｏｆ ｍｕｌｔｉｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ［Ｊ］． Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００９， ３（２）： ８７⁃１２４． ［４］ＹＡＮＧ Ｙａｎ， ＺＨＯＵ Ｙｏｎｇｑｕａｎ， ＧＯＮＧ Ｑｉａｏｑｉａｏ． Ｈｙｂｒｉｄ ａｒ⁃ ｔｉｆｉｃｉａｌ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｓｙｓｔｅｍ ｏｆ ｎｏｎｌｉｎｅａｒ ｅｑｕａｔｉｏｎｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ， ２０１０， ６（１０） ３４３１⁃３４３８． ［５］黄正新， 周永权． 自适应步长萤火虫群多模态函数优化 算法［Ｊ］． 计算机科学， ２０１１， ３８（７）： ２２０⁃２２４． ＨＵＡＮＧ Ｚｈｅｎｇｘｉｎ， ＺＨＯＵ Ｙｏｎｇｑｕａｎ． Ｓｅｌｆ⁃ａｄａｐｔｉｖｅ ｓｔｅｐ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｐｔｉｍｉｚｉｎｇ ｍｕｌｔｉ⁃ ｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２０１１， ３８ （ ７ ）： ２２０⁃２２４． ［６］欧阳喆， 周永权． 自适应步长萤火虫优化算法［ Ｊ］． 计算 机应用， ２０１１， ３１（７）： １８０４⁃１８０７． ＯＵＹＡＮＧ Ｚｈｅ， ＺＨＯＵ Ｙｏｎｇｑｕａｎ． Ｓｅｌｆ⁃ａｄａｐｔｉｖｅ ｓｔｅｐ ｇｌｏｗ⁃ ｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ３１（７）： １８０４⁃１８０７． ［７］ＫＲＩＳＨＮＡＮＡＮＤ Ｋ Ｎ Ｄ， ＧＨＯＳＥ Ｄ． Ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉ⁃ ｍｉｚａｔｉｏｎ： ａ ｎｅｗ ｍｅｔｈｏｄ ｆｏｒ ｏｐｔｉｍｉｚｉｎｇ ｍｕｌｔｉ⁃ｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ ［Ｊ］． Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｔｕｄｉｅｓ， ２００９， １（１）： ９３⁃ １１９ ［８］张军丽， 周永权． 人工萤火虫与差分进化混合优化算法 ［Ｊ］． 信息与控制， ２０１１， ４０（５）： ６０８⁃６１３． ＺＨＡＮＧ Ｊｕｎｌｉ， ＺＨＯＵ Ｙｏｎｇｑｕａｎ． Ａ ｈｙｂｒｉｄ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌ⁃ ｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａｒｔｉｆｉｃｉａｌ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ａｎｄ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ， ２０１１， ４０（５）： ６０８⁃ ６１３． ［９］刘洲洲， 王福豹， 张克旺． 基于改进萤火虫优化算法的 ＷＳＮ 覆盖优化分析［ Ｊ］． 传感技术学报， ２０１３， ２６（５）： ６７５⁃６８２． ＬＩＵ Ｚｈｏｕｚｈｏｕ， ＷＡＮＧ Ｆｕｂａｏ， ＺＨＡＮＧ Ｋｅｗａｎｇ． Ｐｅｒｆｏｒｍ⁃ ａｎｃｅ ａｎａｌｙｓｉｓ ｏｆ ｉｍｐｒｏｖｅｄ ｇｌｏｗｗｏｒｍ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌ⁃ ｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｃｏｖｅｒａｇｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ＷＳＮｓ［Ｊ］． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｓｅｎｓｏｒｓ ａｎｄ Ａｃｔｕａｔｏｒｓ， ２０１３， ２６（５）： ６７５⁃６８２． ［１０］张慧斌， 王鸿斌， 胡志军． ＰＳＯ 算法全局收敛性分析 ［Ｊ］． 计算机工程与应用， ２０１１， ４７（３４）： ６１⁃６３． ＺＨＡＮＧ Ｈｕｉｂｉｎ， ＷＡＮＧ Ｈｏｎｇｂｉｎ， ＨＵ Ｚｈｉｊｕｎ． Ａｎａｌｙｓｉｓ ｏｆ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｍｅｔｈｏｄ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ４７（３４）： ６１⁃６３． ［１１］ＳＯＬＩＳ Ｆ Ｊ， ＷＥＴＳ Ｒ Ｊ Ｂ． Ｍｉｎｉｍｉｚａｔｉｏｎ ｂｙ ｒａｎｄｏｍ ｓｅａｒｃｈ ｔｅｃｈｎｉｑｕｅｓ ［ Ｊ ］． Ｍａｔｈｅｍａｔｉｃｓ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， １９８１， ６（１）： １９⁃３０． 作者简介： 唐少虎，男，１９８６ 年生，博士研究 生，主要研究方向为交通控制、群智能 算法。 刘小明，男，１９７４ 年生，教授，博士， 主要研究方向为交通控制、交通流理 论。 近年来主持国家级、省部级科研项 目 ８ 项，获大连市科学技术一等奖 １ 项，北京市科学技术成果二、三等奖各 １ 项，中国智能交通协会科学技术奖二等 奖 １ 项。 申请发明专利 ３ 项，授权发明专利 １ 项，授权实用 新型专利 １ 项，获软件著作权 ４ 项。 发表学术论文 ４０ 余篇， 出版专著 １ 部、译著 １ 部。 第 ３ 期 唐少虎，等：一种改进的自适应步长的人工萤火虫算法 ·４７５·