周海芳，杨秋翔，杨 剑

（中北大学 计算机与控制工程学院，山西 太原030051）

0 引 言

数字散斑相关方法 （digital speckle correlation method，DSCM）研究的核心内容是相关搜索方法［1］，早期的相关搜索方法主要有两种类型［2］：一种是将位移和位移导数同时搜索，如粗－细相关法；另一种是认为位移导数值对相关系数的贡献远小于位移值，为了节省时间只进行位移搜索，如十字搜索法。为了提高搜索的速度，将相关搜索用数学手段转化为迭代格式求解，如Newton－Rapson 迭代算法，但迭代算法严重依赖初值的选取。若将上述相关搜索方法用于多峰值搜索就很容易陷入局部最优，从而导致搜索结果不准确，为此一些学者将新的数学理论 （如频域傅里叶方法、神经网络方法、小波变换方法等）引入到DSCM 方法中，给相关搜索带来了新的途径，不仅使得搜索精度有了数量级的提高，而且算法更加智能化。

布谷鸟搜索 （cuckoo search，CS）算法［3，4］是一种新颖的群体智能优化算法，其优势主要是模拟鸟类及果蝇特殊的Lévy飞行模式进行搜索，算法简单、参数少，易于实现。然而CS算法是一种新兴的仿生算法，其收敛速度和求精能力仍需要进一步改善。Valian等研究了步长因子对算法性能的影响，采用动态调整的策略增加了算法的性能［5］；郑洪清等给出了基于最佳鸟巢位置的自适应调整步长的策略［6］；王凡等提出将高斯分布引入CS算法［7］。本文通过引入非均匀变异算子和最优鸟巢扰动策略对CS算法进行改进，并用4个标准测试函数进行验证，最后将改进后的CS算法应用到了数字散斑相关方法中。

1 数字散斑相关方法基本原理

数字散斑相关方法基本原理请参见文献 ［8］。相关系数公式是目标子区与样本子区相互关系的定量描述，表示匹配时的相似程度［8］。相关系数公式有很多种，本文采用以下公式

式中：C—— 相关系数，C 越大表示越相关，C ＝1时完全相关。f＝f（i，j）、g＝g（i＋u，j＋v）表示分别为以源点和目标点为中心的散斑图的灰度值函数；f′、g′分别为所在标记区域的平均灰度。

2 基本的CS算法

布谷鸟搜索算法是模拟自然界中布谷鸟种群寄生繁衍的生物行为而衍生出的搜索算法，同时结合了鸟类及果蝇特殊的Lévy飞行模式，全局搜索能力很强，适合用于多目标优化问题求解。该算法的构建基于3个理想规则，具体规则请参见文献 ［4］。在3个理想规则的基础上，布谷鸟按Lévy飞行模式搜索鸟巢的路径和位置更新公式如下

式中：x（t）i——第t代的第i 个鸟巢位置；——点对点乘法；——步长信息；Lévy（λ）——随机搜索路径。

在按一定的发现概率Pa丢弃部分鸟巢之后采用随机游动重新生成相同数量的新鸟巢，位置更新公式如下

式中：r 是 （0，1）区间均匀分布的随机数，x（t）j、x（t）k是第t代的两个随机鸟巢位置。

3 改进后的CS算法 （ICS算法）

3.1 非均匀变异算子

布谷鸟每次寻巢过程中的随机搜索路径即Lévy（λ）的长度和方向都是髙度随机改变的，具有非常大的盲目性。虽然算法在迭代初期很利于全局搜索，但在迭代后期就很容易跳过最优解，出现震荡现象，造成算法收敛速度和寻优精度大大降低。本文引入非均匀变异算子［9］，自适应调节步长使得算法在迭代前期可以在整个定义域中大范围搜索，尽可能发现潜在的区域，随着迭代的进行，步长逐渐减小，到迭代临近结束时，步长趋于零，此时布谷鸟可以在当前最优鸟巢位置的狭小邻域中精细搜索，从而准确定位最优鸟巢位置。

假 设 第t 代 的 第i 个 鸟 巢 的 位 置 为xi（t）＝｛xi（1t），xi（2t），…，xi（dt）｝T，对鸟 巢的第j维 位 置 执 行 变 异，则 变异后的分量为

在Δ（t，y）＝y·（1－y（1－Tt）b）中，t是当前迭代次数，T是最大迭代次数，r 是服从 （0，1）区间均匀分布的随机数，b为决定变异非均匀度的系统参数，［LB，UB］为搜索空 间 的 范 围， 则 更 新 后 的 鸟 巢 位 置 为 yi（t＋1）＝｛yi（1t＋1），yi（2t＋1），…，yi（dt＋1）｝T。

3.2 鸟巢位置更新策略

在标准CS算法中，各个布谷鸟都是按照自己的方式盲目飞行，相互之间并没有进行交流，这并没有充分显示出智能算法的优点。本文借鉴粒子群算法的飞行速度和位置更新机制，令通过随机游动得到的新鸟巢位置由两部分组成，其中一部分信息继承于自身的位置，另一部分吸收于上一代的最优鸟巢位置信息，从而加快整个算法的收敛速度。具体公式如下

式中：r是（0，1）区间均匀分布的随机数，y（t＋1）i是通过非均匀变异因子更新得到的鸟巢位置，bestnest是第t代的最优鸟巢位置。

3.3 最优鸟巢扰动策略

在鸟巢主人发现外来布谷鸟蛋步骤后，不是直接进入下一次迭代而是引入最优鸟巢扰动策略。在多维函数的寻优过程中，对不同维数采用相同范围的扰动显然不能满足求解需求，本文将最优鸟巢位置依据方差可调的正态随机分布进行逐维扰动，该变异操作不但能有效避免CS算法陷入局部最优，而且可以增加整个种群的多样性

3.4 ICS算法的基本步骤

步骤1 初始化参数：将不同的求解问题按照相应的要求初始化鸟巢个数n，解空间维数d，最大迭代次数T，搜索空间范围 ［LB，UB］，发现概率Pa，适应度函数fit（x）。

步骤2 初始化种群：在 ［LB，UB］空间范围内随机生成n个鸟巢，令t＝1，其中第i个鸟巢的位置为xi（1）＝｛xi（11），xi（21）…，xij（1）…xi（d1）｝T，计 算 各 个 鸟 巢 的 适 应 度 函 数值，求出最优鸟巢bestnest。

步骤3 鸟巢位置进行随机游动操作：将每个鸟巢按式（4）方式随机游走，式 （5）确定鸟巢按游走方式得到的最终位置并计算适应度函数值，与更新前的比较后保留较优鸟巢位置。

步骤4 鸟巢主人发现外来鸟蛋操作：产生服从 ［0，1］均匀分布的随机数r，若r ＞Pa，则按式 （3）更新鸟巢位置并计算适应度函数值，与更新前的比较后保留较优鸟巢位置同时更新bestnest。

步骤5 最优鸟巢扰动操作：将bestnest按式 （6）、式（7）进行扰动得到更新后的鸟巢并计算适应度函数值，与更新前的比较后保留较优鸟巢为bestnest。

步骤6 判断操作：若fit（bestnest）没有达到要求且t＜T，则令t＝t＋1，跳转到步骤3，否则循环结束，输出最优鸟巢位置及适应度函数值。

4 仿真实验

4.1 实验设计

本文通过寻找4个标准测试函数的最小值0为例，进行仿真实验来评估ICS算法的性能，标准测试函数及其相关参数设置见表1，测试平台为Matlab2013a、windows7，处理器CPUM370，主频2.4GHz，内存2G。

表1 测试函数及其参数设置

实验中种群规模n＝100，T＝500。为克服算法的偶然误差，对各测试函数独立运行50 次，取其最优值、最差值、平均值和标准偏差与基本CS算法进行比较。

4.2 实验结果分析

表2描述了标准CS和ICS算法对以上4个测试函数的测试结果，对于低维函数Schaffe和Rosenbrock，ICS比CS算法的平均搜索精度分别提高4和9个数量级，最优值分别提高8个数量级，ICS的最差值比CS算法的最优值还要分别提高3和5个数量级。在高维函数Sphere中，ICS比CS算法的平均搜索精度提高7个数量级，且成功找到最优值，最差值要比CS算法的最优值还要提高6个数量级。在高维函数Rastigrin中，ICS比CS算法的平均搜索精度提高1个数量级，最优值提高7个数量级。纵观整个数据表，无论是解的质量上 （最优值、平均值和最差值），还是算法稳定性方面 （标准偏差），ICS算法都要优于CS算法。

从图1 （a）～ （d）的ICS和CS算法的收敛曲线可以看出，ICS算法的收敛速度有明显提高且迭代次数远小于CS算法。

表2 两种优化算法的计算结果

图1 相关测试函数收敛曲线

5 ICS算法在数字散斑相关方法中的应用

5.1 ICS算法测量散斑图像位移的流程

基于以上讨论，用改进的布谷鸟搜索算法对散斑图平移后的位移进行整像素的相关搜索，流程如图2所示。

图2 ICS算法流程

5.2 ICS算法测量模拟散斑图位移

先制作模拟散斑图，图3（a）为源图片，将源图片向右平移17个像素，向下5个像素，得到移动后的图片图3（b）。

图3 模拟散斑

以模拟散斑图为研究对象，取移动前某一点的位移进行相关搜索。以该点为中心选取边长为21像素的正方形区域作为样本子区［10］，在移动后的图片上以相同的点为中心取边长为80像素的正方形区域作为搜索区域，相关系数C在搜索区域内的分布如图4所示。可以发现，图4的中央有一个最高峰，在最高峰附近还有多个较高的局部峰。

ICS算法测量模拟散斑图位移时初始参数设置为：Tmax为30，鸟巢个数为15，样本子区为21×21 像素，搜索区域为80×80像素，Pa.max＝0.95，Pa.min＝0.15。

图5 （a）～ （c）分别给出了迭代次数N＝1、5、15时各个鸟巢在相关系数水平等势线上所处的位置。可以发现，第1代鸟巢的分布是杂乱无章的，而第5代鸟巢整体上向最优解靠拢，在第15代时绝大数鸟巢与最优解重合。

图4 相关系数分布

5.3 ICS算法与CS、PSO （particle swarm optimization）算法比较

用3种算法测量相同的散斑图位移，固定迭代次数为30，种群个数为15，样本子区尺寸为21×21像素，搜索域尺寸为60×60像素，各算法分别进行100次的独立实验，表3列出了适应度C 的最差值，最优值，平均值，寻优成功率和各算法独立运行一次所用的平均时间。

从表3可以看出，3种算法在100次独立试验中都找到过最优值，但综合C 最差值、平均值、寻优成功率可以看出PSO 算法最容易陷入局部最优，并且在100次独立实验中陷入局部最优的次数最多；ICS算法相对PSO、CS算法寻优成功率分别提高29.3%、18.3%，平均误差分别降低了294%、85.8%。说明ICS算法与CS算法在计算时间相差不大的情况下拥有更强的跳出局部最优的能力，搜索精度更高，寻优成功的概率更大。

为了进一步分析各算法在测量散斑图位移的收敛性能，图6给出了各算法在测量散斑图位移时的迭代过程。图中标记点的适应度函数值都是取在100次独立实验中迭代次数对应的适应度平均值。

图5 鸟巢运动轨迹

表3 各算法的计算结果

图6 各算法迭代过程

从图6可以看出：在迭代初期，ICS算法全局寻优能力最强，在锁定最优值范围后，局部收敛能力最强并且求精能力最优。而CS算法在收敛速度和求精能力上都比粒子群算法略优。

6 结束语

针对基于传统DSCM 的计算结果容易陷入局部最优，求解精度不高，后期收敛速度慢等缺点，本文将基于群体智能的CS算法引入到DSCM 中，并对基本的CS算法进行了改进，将ICS，CS，PSO 这3种算法用于测量预制模拟散斑图平移后的整像素位移，实验结果表明CS 算法在DSCM 中是有效的，并且ICS 方法较CS，PSO 算法在DSCM 中跳出局部最优的能力最强，收敛速度最快和寻优精度最高。

［1］YANG Yuhang.Study of digital speckle correlation method［D］.Jilin：Changchun University of Science and Technology，2014：5－23 （in Chinese）. ［杨宇航.数字散斑相关方法的研究 ［D］.吉林：长春理工大学，2014：5－23.］

［2］LIANG Heng.Research on measurement techniques based on digital speckle correlation method ［D］.Anhui：Hefei University of Technology，2014：10－30 （in Chinese）. ［梁恒.基于数字散斑相关方法的测量技术研究 ［D］.安徽：合肥工业大学，2014：10－30.］

［3］LONG Wen，CHEN Le.Hybrid cuckoo search algorithm for solving constrained chemical engineering optimization problems［J］.Journal of Computer Applications，2014，34 （2）：523－527 （in Chinese）.［龙文，陈乐.求解约束化工优化问题的混合布 谷 鸟 搜 索 算 法 ［J］.计 算 机 应 用，2014，34 （2）：523－527.］

［4］Gandomt A，Yang X，Alavi A.Cuckoo search algorithm：Ameta－heuristic approach to solve structural optimization problems ［J］.Engineering with Computer，2013，29 （1）：17－35.

［5］Valian E，Mohanna S，Tavakoli S.Improved cuckoo search algorithm for global optimization ［J］.Int J Communications and Information Technology，2011，1 （1）：31－44.

［6］ZHENG Hongqing，ZHOU Yongquan.Self－adaptive step cuckoo search algorithm ［J］.Computer Engineering and Applications，2013，49 （10）：68－71 （in Chinese）. ［郑 洪 清，周永权.一种自适应步长布谷鸟搜索算法 ［J］.计算机工程与应用，2013，49 （10）：68－71.］

［7］WANG Fan，HE Xingshi，WANG Yan.The cuckoo search algorithm based on Gaussian disturbance［J］.Journal of Xi’an Polytechnic University，2011，25 （4）：566－569 （in Chinese）.［王凡，贺兴时，王燕.基于高斯扰动的布谷鸟搜索算法 ［J］.西安工程大学学报，2011，25 （4）：566－569.］

［8］CHEN Zhixin，LIANG Jin，GUO Cheng.Application of digital speckle correlation method to deformation measurement［J］.Optics and Precision Engineering，2011，19 （7）：1480－1485 （in Chinese）.［陈志新，梁晋，郭成.数字散斑相关法在变形测量中的应用 ［J］.光学精密工程，2011，19 （7）：1480－1485.］

［9］ZHAO Xinchao，LIU Guoli，LIU Huqiu，et al.Particle swarm optimization algorithm base on non－uniform mutation and multiple stages perturbation ［J］.Chinese Journal of Computers，2014，37 （9）：2058－2070 （in Chinese）. ［赵新超，刘国莅，刘虎球，等.基于非均匀变异和多阶段扰动的粒子群优化算法 ［J］.计算机学报，2014，37 （9）：2058－2070.］

［10］DU Yazhi，WANG Xuebin.Digital image correlation method based on particle swarm optimization algorithm without subpixel interpolation ［J］.Computer Engineering and Applications，2012，48 （6）：200－228 （in Chinese）.［杜亚志，王学滨.基于粒子群算法的整像素数字图像相关方法 ［J］.计算机工程与应用，2012，48 （6）：200－228.］