Artificial glow w orm sw arm optimization algorithm is a new research orientation in the field of sw arm intelligence recently． The algorithm has been achieved success in the complex function optimization but it is easy to fall into local optimization and having the low speed of convergence and so on in the late． Hooke-Jeeves algorithm has excellent local search ability how ever its search re- ， ; ; ， 小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems 2011 年 10 月 第 10 期 Vol. 32 No． 10 2011 一种基于模式搜索算子的人工萤火虫优化算法 刘洪霞，周永权 : ) yongquangzhou@ 126． com ( 广西民族大学 数学与计算机科学学院，南宁 530006 E-mail 摘 要: 人工萤火虫算法是群智能领域近年出现的一个新的研究方向，该算法已在复杂函数优化方面取得了成功，但也存在着 易陷入局部极小且进化后期收敛速度慢等问题． 而模式搜索具有很强的搜索能力，但其搜索结果的好坏在很大程度上依赖于初 始点的选择． 结合两者的优缺点，提出一种基于搜索算子的人工萤火虫算法． 该算法在人工萤火虫算法全局搜索过程中融入模 式搜索法，改进人工萤火虫算法全局搜索和局部搜索能力． 仿真实验结果表明，该算法收敛速度和解的精度显著地提高，是求解 函数优化问题的一种可行和有效的方法． 关 键 词: 人工萤火虫算法; 模式搜索; 函数优化 中图分类号: TP183 文 章 编 号:1000-1220(2011)10-2130-04 文献标识码:A A Glowworm Swarm Optimization Algorithm Based on Pattern Search Operator LIU Hong-xia，ZHOU Yong-quan ( College of mathematics and Computer Science ， G uangxi University for Nationalities ， Nanning 530006 ， China ) : Abstract sult mostly depends on the initial point． Combining their advantages and disadvantages a glow w orm sw arm optimization algorithm w as proposed based on Hooke-Jeeves operator． In the process of glow w orm sw arm optimization algorithm integrates into the Hooke- Jeeves algorithm it is improving the global and local searching ability of glow w orm sw arm optimization algorithm． Simulation results ; show that this method increased the accuracy of solution and the speed of convergence significantly and is a feasible and effective method to solve function optimization． Key words glow w orm sw arm optimization : ( ) ; GSO hooke-jeeves ( ) ; HJ function optimization 1 引 言 2 人工萤火虫算法和模式搜索算法的原理 1-2 人 工 萤 火 虫 算 法 ( ) ［ ， Glow w orm Sw arm Optimization ］是由 K． N． Krishnanad 和 D． Ghose 于 2005 年提出 GSO 的一种仿生新型群智能优化算法，该算法已在复杂函数优化 方面取得了成功． 人工萤火虫算法越来越引起人们的关注，已 经成为计算智能研究领域一个新的研究热点． 随着研究的不 断深入，该算法已成功应用于传感器的噪声测试［ ］和模拟机 ］一样，模式 器人［ 搜索算法［ ］是一种直接优化方法． 它不需要目标函数与约束 函数的导数相关信息，只需要通过函数值的比较来选取新的 迭代点． 与其它确定性局部优化技术相比，有优化速度快、计 算量小、抗干扰能力强等优点． ］等领域． 与遗传算法［ ］和模拟退火算法［ 4 5 6 7 8 为了 进 一 步 提 高 GSO 收 敛 速 度 和 计 算 精 度，本 文 在 GSO 算法中融入模式搜索算子，在充分利用 GSO 的寻找多 峰函数的全局搜索能力的基础上，利用模式搜索算法 加 强 GSO 局部搜索能力，给出一种基于模式搜索算子的人工萤火 虫优化算法． 2． 1 人工萤火虫算法( GSO) i : ， 2 i = 1 ， n ， … 在 GSO 算法中，初始时，萤火虫实体{ } 被 认为是在目标函数空间中 Rm 随机分配的． 每一个实体通过 从邻居那里获得信号决定自己的移动方向． 这就类似于萤火 虫发出荧光素吸引他的同伴前来觅食或是配偶． 荧光素越亮 的地方，就越能吸引同伴向此方向移动． 从萤火虫的这种行为 中得到启发，得出一种函数优化的智能方法． 在 GSO 算法中， 每一迭代过程中，萤火虫被赋予这种行为机制( 自然界中的 萤火虫不具有的这种行为机制) : 萤火虫可以有选择的和他 们的邻居相互联系，并决定朝哪个方向移动． t ( ( ( ) ) 和此处的荧光素值 li 每一个萤火虫 i 在当前位置 xi xi ) 对应着一个目标函数 ，每一个萤火虫在它的邻居 值 J ) 是在决策域范围内那些具有 范围内传递信息． 邻居数 Ni 相对较高的荧光素值的萤火虫个数，初始决策范围根据目标 函数的定义域来确定，以后每次迭代按式( ( t t ) 进行更新． 1 决策域范围更新公式: 收稿日期: 2010-07-19 基金项目: 广西自然科学基金项目( 1962 年生，博士，教授，研究方向为计算智能、神经网络及应用． 0991086 周永权，男， ) 资助． 作者简介: 刘洪霞，女， 1983 年生，硕士，研究方向为计算智能; 

d ) t + 1 ( ( r i 其中， r i ( 即决策半径) ， r s 邻域阈值， t + 1 d ( ) ( { { 0 r s ， r i ， max ) = min 1 ) 为第 t 代第 i 个萤火虫第 t + 1 代的决策范围 为控制萤火虫邻居数目的 nt － | Ni ) } } ( 为感知范围， nt + β ( ) t t | d β 为控制邻居变化范围的常数． d j t t t t t ; : ( ( ( ) ( ) ( ) { li ) } － xi ‖xj ＜ lj ( t ‖ ＜ r i ) = t ) 为第 t 代第 j 个萤火虫的位置， lj 确定决策域范围内的萤火虫个数的公式为: ( ) ( 2 Ni ) 为第 t 代第 j 其中， xj 个萤火虫的荧光素值; 邻居数目被限制在动态决策域 r i 范围 内，动态决策域 r i ． 当萤火 ，且它们的距离差 虫 i 找到荧光素值比本身大的邻居萤火虫 j ) 选择邻居 j ，并且 在感知范围内，则萤火虫 i 以一定概率 p ij ( t ) 式进行位置更新，计算此处的目标函 向邻居方向移动，按( 数值，进一步的按式( ) 更新荧光素的值． 这种移动只取决于 萤火虫的局部信息，使萤火虫群体分为不相交的子群体，呈现 出一种自发的滑行行为，最后找出目标函数的最优值． 的上界为感知范围 r s 0 ＜ r i d ＜ r s 3 4 ( ) d d 位置更新公式: ( ( ) ) t t xj ‖xj ( ( ) ) t t － xi － xi ) ‖ ( ) 3 ( xi ) t + 1 ( ) t ( + s = xi 更新荧光素值的公式: ( ) ) t ( 其中， li 制荧光素值的参数， 度函数值． 2． 2 模式搜索算法( HJ) t ) ( li = 1 － ρ ( li ) 为第 t 代第 i 个萤火虫的荧光素值， ρ∈ ( ( xi γ 为衡量函数值的参数， J + γJ t － 1 ) ) xi ( ( t ( ) 4 ) 为控 ， 0 1 ) ) 为适应 ( t ( 8-9 HJ Hooke-Jeeves ) 局 部 搜 索 算 法［ ］ 是 由 Hooke 和 Jeeves 在 1961 年提出的一种直接搜索方法，它的每一次迭代 都是交替进行轴向移动和模式移动，轴向移动的目的是探测 下降的有利方向，而模式移动的目的则是沿着有利方向加速 移动． 为说明模式搜索的主要思想，假设目标模型为二维参数 模型，则可用数学方式表示如下: ， ］ ［ 0 1 ， ］ ［ 0 1 ［ X3 = Meshsizeδ ［ 0 X4 = Meshsizeδ ， ， 2 3 ［ + X0 1 V 1 = ［ + X0 0 V 2 = ， ］ ［ 0 V 3 = － 1 ］ ［ ， 0 V 4 = － 1 ) 为用矢量形式表示的 为给定当前点， ， 式中 X0 V i 4 模式搜索方向( 轴向) ， δ 为搜索步长并随迭代过程而变化． 图 1 为搜索过程的简单示意图，箭头的长度为 Meshsize ，箭头的 方向为搜索方向． ， ］ 0 X1 = Meshsizeδ ］ ， X2 = Meshsizeδ 1 ， ］ 0 ］ + X0 + X0 － 1 ， = 1 － 1 ， ， ( 10 期 刘洪霞 等: 一种基于模式搜索算子的人工萤火虫优化算法 1312 ， 2 ， … ， j = 1 Step 2． 令 y = xk; Step 3． 从 y 出发，依从作平行于单位矢量 e j ( ) 的轴向探测移动: n Step 3． 1． 正向探测: 若 f j e j ，否则做负向探测; + δk Step 3． 2． 负向探测: 若 f － δk j e j ，否则令 y = y Step 4． 令 xk + 1 = y ; ，若 f ( xk + 1 ) ( ＜ f ( ( y + δk j e j ) ＜ f y － δk j e j ) ≤f ( ( ) ，则令 y = y y ) ，则令 y = y y xk) ，则对 xk + 1 沿加速方 k = k δk + 1 = δk， 向 p k = xk + 1 － xk 作模式移动，令 y = xk + 1 + γp k， + 1 ，否则转 Step 5 ; ，转 Step 3 Step 5． 若 | δk | ＜ ε 时，令 y = xk + 1 ， y = xk + 1 ， δk + 1 = θδk， δk + 1 = δk， k = k + 1 ，转 Step 3． ，则停止迭代，输出 xk，否则当 xk + 1 ≠xk ，当 xk + 1 = xk 时，令 ，转 Step 3 k = k + 1 在算法的应用过程中，通常取加速系数 y = ∈ ［ 1 ， 2 ］，收 ［ ， 0． 5 ］ ． 0． 1 缩系数 θ∈ 3 基于模式搜索算子的人工萤火虫算法( HJGSO) 3． 1 算法思想 该文用人工萤火虫优化算法框架进行区域搜索，并通过 模式搜索算法实现进一步局部搜索，从而构建一种引入模式 搜索算子的混合算法． 算法的实现过程是: 首先在可行解空间 上随机分布( 初始化) 萤火虫的位置，并同时赋予一定量的荧 光素值． 算法中定义了感知范围( 根据函数的定义域确定其 大小) ，当两个萤火虫的距离在感知范围内且另一只萤火虫 的荧光素值较大时，此时萤火虫以一定步长向此方向移动． 当 个体到达目的区域后，进行单步模式搜索进一步改进解，并根 据改进解的目标函数值更新荧光素值，重复这些过程最终找 到问题的最优解． 3． 2 算法的实施步骤 算法的步骤如下: Step 1． 初始化各个参数: 控制萤火虫邻居数目的邻域阈 ，控制邻居变化 ，萤火虫移动的步长 s 值 nt ，衡量函数值的参数 γ ; 范围的参数 β 模式搜索的初始步长及加速因子等; 初始化萤火虫的位置; ，控制荧光素值的参数 ρ ，初始荧光素的值 l0 Step 2． 对每一个萤火虫 i 按( Step 3． 进入移动阶段，按( 2 Step 4． 用轮盘赌选择法选出目标函数值较大的萤火虫 j ) 选出符合条件的萤火虫; ) 式更新荧光素的值; 4 ( ( ) ) ; j∈Ni t 3 ) 更新萤火虫的位置; Step 5． 按式( Step 6． 进入模式搜索算法进一步改进解; Step 7． 按式( Step 8． 一次迭代完成，进入下一次迭代，判断是否满足 ) 更新决策半径; 1 结束条件，满足退出循环，否则转 Step 2． 图 1 模式搜索法示意图 Fig． 1 Hooke-jeeves schematic diagram 4 仿真实验与分析 用模式搜索法求无约束问题minf Step 1． 给定初始点 x ( 0 ) ，初始步长 δ0 = ，加速系数 γ ＞ 0 ，收缩系数 θ∈ ( 0 ， 1 0 ( ) ， x x∈Rn 的算法步骤如下: ＞ ; ， δ0 ) 及精度 ε ＞ 0 ， ) ， δ0 … ，置 k = 0 δ0 ( n 1 2 4． 1 测试平台 本算法用 M atlab2008 编程实现，试验平台是 Pentium IV 2． 61 GHZ 的内存为 1 GB 的 WINXP 系统的 PC 机． 

2312 小 型 微 型 计 算 机 系 统 2011 年 4． 2 参数设置 选为 5 ，最大迭代次数为 200 本算法中，萤火虫数目为 50 ，控制萤火虫邻居数目的邻域阈值 nt ，初始 为 ，控制荧光素值的参数 ρ 函数，移动的步长 ; 对于 f4 ，决 ; 模式搜索的初始步长为 0． 01 及加速因子 ，其它函数，移动的步长均为 20 荧光素的值 l0 ，控制邻居变化范围的参数 β 为 0． 8 5 ，衡量函数值的参数 γ 为 0． 6 为 0． 4 ，决策域范围为 5 s 定为 3 策域范围均为 30 为 0． 5． 4． 3 测试函数 ) 2 ， ( ) 2 + ，最优点为( 1 － x i n = 30 ， ， … 1 － 30≤x i ≤30 ) ，是非凸、病 ， 1 1 ， ( ) 1 Rosenbrock 函数 ( n － 1 f1 = ∑ i = 1 100 x 2 i + 1 － x i 该函数的全局最小值为 0 态单峰函数． ( ) 2 Shaffer'sf7 函数 ( ) 1 4 2 ( x2 1 + x2 sin2 ( ［ ］， f2 = ， 该函数的全局最小值为 0 … 数． 多个同心圆作为局部极值点，很难搜索到． x2 1 + x2 ，最优点为( + 1． 0 ， 0 ) 1 50 0 10 ) 2 － 100 ＜ xi ＜ 100 ， ) ，是多峰函 0 ( ) 3 Schaffer'sf6 f3 = 0． 5 + ［ x2 sin2 1． 0 + 0． 001 2 2 － 0． 5 1 + x槡 ( x2 1 + x2 2 ， ) ］ － 100 ＜ xi ＜ 100 ，在距全局最优点大约 3． 14 范围内 该函数的全局最小值为 0 存在无穷多个局部极小将其包围，且该函数强烈震荡，一般算 法难以得到最优解． ( ) 4 Freudenstein-Roth 函数 ( ( f4 = － 13 + x1 + ) ) ( ( x2 + 1 * x2 － 14 * x2 该函数的全局最小值为 0 * x2 － 2 ) 5 － x2 ) 2 ， ，最优点为( － 10≤xi ≤10 ， ) 4 5 ． ) ) 2 + ( * x2 － 29 + x1 + ( ) 5 n f5 = ∑ i = 1 Sphere 函数 ， ， n = 30 x2 i 该函数的全局最小值为 0 ( ) 6 Griew ank 函数 － 100 ＜ xi ＜ 100 ，最优点为( ， 0 ， … ， ) 0 0 ． f6 = 1 4000 n ∑ i = 1 n x2 i － Π i = 1 cos 该函数的全局最小值为 0． 4． 4 实验结果讨论 xi 槡i ， n = 30 + 1 ， － 100 ＜ xi ＜ 100 选用经典的测试函数进行测试本文算法的有效性 ． 为了 克服算法的偶然性带来的误差，对每个函数独立运行 20 次， 取其最优值、最差值、均值和方差，并与标准的 GSO 算法的进 行对比． 从表 1 可以看出，对于高维函数 f1 ，用 HJGSO 算法得 到的精度远远高于基本的 GSO 算法; 对于很难找到最优值的 表 1 f1 -f6 函数实验结果对比 Table 1 f1 -f6 functions comparison of experimental results 函数 算法 最优值 最差值 均值 标准差 f1 f2 f3 f4 f5 f6 GSO 0． 001 125 432 0． 001 897 443 0． 00 144 124 1． 489 966e-4 HJGSO 4． 903 630e-4 0． 004 531 810 0． 001 938 631 0． 001 921 044 GSO 0． 118 922 484 0． 245 708 291 0． 148 031 454 0． 055 112 457 HJGSO 0． 015 155 859 0． 079 507 173 0． 040 917 763 0． 028 838 757 GSO 0． 021 395 591 0． 063 294 590 0． 043 098 494 0． 017 009 322 HJGSO 0． 005 863 671 0． 034 197 385 0． 024 017 341 0． 017 393 279 GSO 0． 001 241 359 0． 008 257 313 0． 005 154 402 0． 003 228 941 HJGSO 9． 960 032e-5 6． 665 776e-4 4． 190 257e-4 GSO 5． 283 676e-9 1． 490 833 e-9 6． 176 546e-9 HJGSO 5． 981 376e-10 1． 175 150 e-9 2． 126 471e-9 3． 547 989e-4 6． 164 127e-9 2． 109 345e-9 GSO 0． 072 927 978 0． 072 928 344 0． 072 927 803 4． 476 258 e-7 HJGSO 0． 072 927 925 0． 072 927 926 0． 072 927 926 1． 537 713e-9 函数，新的算法得到的解也更接近于理论最优值，且 HJG- f2 SO 算法的比 GSO 算法的所得的标准差小，这说明 HJGSO 对 图 2-图7是本文算法和GSO算法的收敛曲线，直观地看出 图 2 Rosenbrock 函数的收敛对比曲线 Fig． 2 Rosenbrock comparison of convergence curve 初值具有更强的鲁棒性． 图 3 Schaffer'sf7 函数的收敛对比曲线 Fig． 3 Schaffer'sf7 comparison of convergence curve HJGSO 算法收敛速度更快，迭代次数少，而且能收敛到复杂 多极值点函数的全局最优解． 

刘洪霞 等: 一种基于模式搜索算子的人工萤火虫优化算法 3312 10 期 5 结束语 本文提出了一种人工萤火虫算法和模式搜索的混合优化 算法，该方法充分利用模式搜索的强大的局部搜索能力，融入 ］ ［ 2 图 4 Freudenstein 函数的 收敛对比曲线 图 5 Schaffer'sf6 函数的 收敛对比曲线 Fig． 4 Freudenstein comparison Fig． 5 of convergence curve Schaffer'sf6 comp- arison of convergence curve 图 6 Sphere 函数的 收敛对比曲线 图 7 Griew ank 函数的 收敛对比曲线 Fig． 6 Sphere comparison Fig． 7 Griew ank comparison of convergence curve of convergence curve 到萤火虫算法中去，提高萤火虫寻优过程中的全局搜索和局 部搜索能力． 实验结果表明，该算法具有收敛速度快、计算精 度高等特点． References: ［ 1 Ghose D． Glow w orm sw arm optimization Krishnanand K N D ］ ， a : ］ ［ 3 ］ ［ 4 ］ ［ 5 ］ ［ 6 ］ ［ 7 ］ ［ 8 new method for optimizing multi-modal functions ． Computa- tional Intelligence Studies 2009 ， ( ， 1 1 ) : 93-119． Krishnanand K N． Glow w orm sw arm optimization : a multimodal ［ ］ J function optimization paradigm w ith applications to multiple signal source localization tasks ． Indian ［ ］ D : ， Department of Aerospace En- ， gineering Indian Institute of Science 2007． Krishnanand K N ， Ghose D． Theoretical foundations for rendezvous of glow w orm-inspired agent sw arms at multiple locations botics and Autonomous Systems 2008 ， ( ， 7 56 ) : 549-569． ［ ］ J ． Ro- ， ， Krishnanand K N Ghose D． A glow w orm sw arm optimization based multi-robot system for signal source localization M ． Design and Control of Intelligent Robotic Systems 2009． ， Krishnanand K N Ghose D． Chasing multiple mobile signal sources a glow w orm sw arm optimization approach ． In Third : Indian International Conference on Artificial Intelligence IICAI ［ ］ ［ ］ C ( ) ， 07 Indian ， ， 2007． Ha Q P Nguyen Q H trollers w ith applications ， ( ) : 2001 48 1 38-46． ， ， ， Rye D C ［ ］ J et al． Fuzzy sliding-mode con- ， ． IEEE Trans on Industrial Electronics M etropolis N Rosenbluth A． Rosenbluth metal equation of state calculations by fast computing machines ． Journal of Chemical ［ ］ J ， ( 56 21 ) : 1087-1092． Physics ， 1953 ， Gong Chun ［ calculation M Wang Zheng-lin． Proficient in M ATLAB optimization ］ ， Publishing House of Electronics Industry ． Beijing : 2009． Li Pei ］ ［ 9 ， Tang Hong-zhi ， Wang Hui-bo ， et al． Inversion of w are im- pedance w ide-band restrition model base on pattern search algorithm ［ ) : ］ J ． Journal of East China Institute of Technology ， 2008 ， 3 31 ( 169-275． 附中文参考文献: ［ 8 业出版社， 2009． ］ 龚 纯，王正林． 精通 M ATLAB 最优化计算［ M ］ ． 北京: 电子工 ［ 9 ］ 李 培，汤洪志，王会波，等． 基于模式搜索算法的波阻抗宽带约 ］ 束模型反演［ ． 东华理工大学学报， J 2008 ( ， 3 ) : 31 169-275．