周海芳，楊秋翔，楊 劍

（中北大學 計算機與控制工程學院，山西 太原030051）

0 引 言

數(shù)字散斑相關方法 （digital speckle correlation method，DSCM）研究的核心內容是相關搜索方法［1］，早期的相關搜索方法主要有兩種類型［2］：一種是將位移和位移導數(shù)同時搜索，如粗－細相關法；另一種是認為位移導數(shù)值對相關系數(shù)的貢獻遠小于位移值，為了節(jié)省時間只進行位移搜索，如十字搜索法。為了提高搜索的速度，將相關搜索用數(shù)學手段轉化為迭代格式求解，如Newton－Rapson 迭代算法，但迭代算法嚴重依賴初值的選取。若將上述相關搜索方法用于多峰值搜索就很容易陷入局部最優(yōu)，從而導致搜索結果不準確，為此一些學者將新的數(shù)學理論 （如頻域傅里葉方法、神經網絡方法、小波變換方法等）引入到DSCM 方法中，給相關搜索帶來了新的途徑，不僅使得搜索精度有了數(shù)量級的提高，而且算法更加智能化。

布谷鳥搜索 （cuckoo search，CS）算法［3，4］是一種新穎的群體智能優(yōu)化算法，其優(yōu)勢主要是模擬鳥類及果蠅特殊的Lévy飛行模式進行搜索，算法簡單、參數(shù)少，易于實現(xiàn)。然而CS算法是一種新興的仿生算法，其收斂速度和求精能力仍需要進一步改善。Valian等研究了步長因子對算法性能的影響，采用動態(tài)調整的策略增加了算法的性能［5］；鄭洪清等給出了基于最佳鳥巢位置的自適應調整步長的策略［6］；王凡等提出將高斯分布引入CS算法［7］。本文通過引入非均勻變異算子和最優(yōu)鳥巢擾動策略對CS算法進行改進，并用4個標準測試函數(shù)進行驗證，最后將改進后的CS算法應用到了數(shù)字散斑相關方法中。

1 數(shù)字散斑相關方法基本原理

數(shù)字散斑相關方法基本原理請參見文獻 ［8］。相關系數(shù)公式是目標子區(qū)與樣本子區(qū)相互關系的定量描述，表示匹配時的相似程度［8］。相關系數(shù)公式有很多種，本文采用以下公式

式中：C—— 相關系數(shù)，C 越大表示越相關，C ＝1時完全相關。f＝f（i，j）、g＝g（i＋u，j＋v）表示分別為以源點和目標點為中心的散斑圖的灰度值函數(shù)；f′、g′分別為所在標記區(qū)域的平均灰度。

2 基本的CS算法

布谷鳥搜索算法是模擬自然界中布谷鳥種群寄生繁衍的生物行為而衍生出的搜索算法，同時結合了鳥類及果蠅特殊的Lévy飛行模式，全局搜索能力很強，適合用于多目標優(yōu)化問題求解。該算法的構建基于3個理想規(guī)則，具體規(guī)則請參見文獻 ［4］。在3個理想規(guī)則的基礎上，布谷鳥按Lévy飛行模式搜索鳥巢的路徑和位置更新公式如下

式中：x（t）i——第t代的第i 個鳥巢位置；——點對點乘法；——步長信息；Lévy（λ）——隨機搜索路徑。

在按一定的發(fā)現(xiàn)概率Pa丟棄部分鳥巢之后采用隨機游動重新生成相同數(shù)量的新鳥巢，位置更新公式如下

式中：r 是 （0，1）區(qū)間均勻分布的隨機數(shù)，x（t）j、x（t）k是第t代的兩個隨機鳥巢位置。

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

3.1 非均勻變異算子

布谷鳥每次尋巢過程中的隨機搜索路徑即Lévy（λ）的長度和方向都是髙度隨機改變的，具有非常大的盲目性。雖然算法在迭代初期很利于全局搜索，但在迭代后期就很容易跳過最優(yōu)解，出現(xiàn)震蕩現(xiàn)象，造成算法收斂速度和尋優(yōu)精度大大降低。本文引入非均勻變異算子［9］，自適應調節(jié)步長使得算法在迭代前期可以在整個定義域中大范圍搜索，盡可能發(fā)現(xiàn)潛在的區(qū)域，隨著迭代的進行，步長逐漸減小，到迭代臨近結束時，步長趨于零，此時布谷鳥可以在當前最優(yōu)鳥巢位置的狹小鄰域中精細搜索，從而準確定位最優(yōu)鳥巢位置。

假 設 第t 代 的 第i 個 鳥 巢 的 位 置 為xi（t）＝｛xi（1t），xi（2t），…，xi（dt）｝T，對鳥 巢的第j維 位 置 執(zhí) 行 變 異，則 變異后的分量為

在Δ（t，y）＝y(tǒng)·（1－y（1－Tt）b）中，t是當前迭代次數(shù)，T是最大迭代次數(shù)，r 是服從 （0，1）區(qū)間均勻分布的隨機數(shù)，b為決定變異非均勻度的系統(tǒng)參數(shù)，［LB，UB］為搜索空 間 的 范 圍， 則 更 新 后 的 鳥 巢 位 置 為 yi（t＋1）＝｛yi（1t＋1），yi（2t＋1），…，yi（dt＋1）｝T。

3.2 鳥巢位置更新策略

在標準CS算法中，各個布谷鳥都是按照自己的方式盲目飛行，相互之間并沒有進行交流，這并沒有充分顯示出智能算法的優(yōu)點。本文借鑒粒子群算法的飛行速度和位置更新機制，令通過隨機游動得到的新鳥巢位置由兩部分組成，其中一部分信息繼承于自身的位置，另一部分吸收于上一代的最優(yōu)鳥巢位置信息，從而加快整個算法的收斂速度。具體公式如下

式中：r是（0，1）區(qū)間均勻分布的隨機數(shù)，y（t＋1）i是通過非均勻變異因子更新得到的鳥巢位置，bestnest是第t代的最優(yōu)鳥巢位置。

3.3 最優(yōu)鳥巢擾動策略

在鳥巢主人發(fā)現(xiàn)外來布谷鳥蛋步驟后，不是直接進入下一次迭代而是引入最優(yōu)鳥巢擾動策略。在多維函數(shù)的尋優(yōu)過程中，對不同維數(shù)采用相同范圍的擾動顯然不能滿足求解需求，本文將最優(yōu)鳥巢位置依據(jù)方差可調的正態(tài)隨機分布進行逐維擾動，該變異操作不但能有效避免CS算法陷入局部最優(yōu)，而且可以增加整個種群的多樣性

3.4 ICS算法的基本步驟

步驟1 初始化參數(shù)：將不同的求解問題按照相應的要求初始化鳥巢個數(shù)n，解空間維數(shù)d，最大迭代次數(shù)T，搜索空間范圍 ［LB，UB］，發(fā)現(xiàn)概率Pa，適應度函數(shù)fit（x）。

步驟2 初始化種群：在 ［LB，UB］空間范圍內隨機生成n個鳥巢，令t＝1，其中第i個鳥巢的位置為xi（1）＝｛xi（11），xi（21）…，xij（1）…xi（d1）｝T，計 算 各 個 鳥 巢 的 適 應 度 函 數(shù)值，求出最優(yōu)鳥巢bestnest。

步驟3 鳥巢位置進行隨機游動操作：將每個鳥巢按式（4）方式隨機游走，式 （5）確定鳥巢按游走方式得到的最終位置并計算適應度函數(shù)值，與更新前的比較后保留較優(yōu)鳥巢位置。

步驟4 鳥巢主人發(fā)現(xiàn)外來鳥蛋操作：產生服從 ［0，1］均勻分布的隨機數(shù)r，若r ＞Pa，則按式 （3）更新鳥巢位置并計算適應度函數(shù)值，與更新前的比較后保留較優(yōu)鳥巢位置同時更新bestnest。

步驟5 最優(yōu)鳥巢擾動操作：將bestnest按式 （6）、式（7）進行擾動得到更新后的鳥巢并計算適應度函數(shù)值，與更新前的比較后保留較優(yōu)鳥巢為bestnest。

步驟6 判斷操作：若fit（bestnest）沒有達到要求且t＜T，則令t＝t＋1，跳轉到步驟3，否則循環(huán)結束，輸出最優(yōu)鳥巢位置及適應度函數(shù)值。

4 仿真實驗

4.1 實驗設計

本文通過尋找4個標準測試函數(shù)的最小值0為例，進行仿真實驗來評估ICS算法的性能，標準測試函數(shù)及其相關參數(shù)設置見表1，測試平臺為Matlab2013a、windows7，處理器CPUM370，主頻2.4GHz，內存2G。

表1 測試函數(shù)及其參數(shù)設置

實驗中種群規(guī)模n＝100，T＝500。為克服算法的偶然誤差，對各測試函數(shù)獨立運行50 次，取其最優(yōu)值、最差值、平均值和標準偏差與基本CS算法進行比較。

4.2 實驗結果分析

表2描述了標準CS和ICS算法對以上4個測試函數(shù)的測試結果，對于低維函數(shù)Schaffe和Rosenbrock，ICS比CS算法的平均搜索精度分別提高4和9個數(shù)量級，最優(yōu)值分別提高8個數(shù)量級，ICS的最差值比CS算法的最優(yōu)值還要分別提高3和5個數(shù)量級。在高維函數(shù)Sphere中，ICS比CS算法的平均搜索精度提高7個數(shù)量級，且成功找到最優(yōu)值，最差值要比CS算法的最優(yōu)值還要提高6個數(shù)量級。在高維函數(shù)Rastigrin中，ICS比CS算法的平均搜索精度提高1個數(shù)量級，最優(yōu)值提高7個數(shù)量級?？v觀整個數(shù)據(jù)表，無論是解的質量上 （最優(yōu)值、平均值和最差值），還是算法穩(wěn)定性方面 （標準偏差），ICS算法都要優(yōu)于CS算法。

從圖1 （a）～ （d）的ICS和CS算法的收斂曲線可以看出，ICS算法的收斂速度有明顯提高且迭代次數(shù)遠小于CS算法。

表2 兩種優(yōu)化算法的計算結果

圖1 相關測試函數(shù)收斂曲線

5 ICS算法在數(shù)字散斑相關方法中的應用

5.1 ICS算法測量散斑圖像位移的流程

基于以上討論，用改進的布谷鳥搜索算法對散斑圖平移后的位移進行整像素的相關搜索，流程如圖2所示。

圖2 ICS算法流程

5.2 ICS算法測量模擬散斑圖位移

先制作模擬散斑圖，圖3（a）為源圖片，將源圖片向右平移17個像素，向下5個像素，得到移動后的圖片圖3（b）。

圖3 模擬散斑

以模擬散斑圖為研究對象，取移動前某一點的位移進行相關搜索。以該點為中心選取邊長為21像素的正方形區(qū)域作為樣本子區(qū)［10］，在移動后的圖片上以相同的點為中心取邊長為80像素的正方形區(qū)域作為搜索區(qū)域，相關系數(shù)C在搜索區(qū)域內的分布如圖4所示?？梢园l(fā)現(xiàn)，圖4的中央有一個最高峰，在最高峰附近還有多個較高的局部峰。

ICS算法測量模擬散斑圖位移時初始參數(shù)設置為：Tmax為30，鳥巢個數(shù)為15，樣本子區(qū)為21×21 像素，搜索區(qū)域為80×80像素，Pa.max＝0.95，Pa.min＝0.15。

圖5 （a）～ （c）分別給出了迭代次數(shù)N＝1、5、15時各個鳥巢在相關系數(shù)水平等勢線上所處的位置。可以發(fā)現(xiàn)，第1代鳥巢的分布是雜亂無章的，而第5代鳥巢整體上向最優(yōu)解靠攏，在第15代時絕大數(shù)鳥巢與最優(yōu)解重合。

圖4 相關系數(shù)分布

5.3 ICS算法與CS、PSO （particle swarm optimization）算法比較

用3種算法測量相同的散斑圖位移，固定迭代次數(shù)為30，種群個數(shù)為15，樣本子區(qū)尺寸為21×21像素，搜索域尺寸為60×60像素，各算法分別進行100次的獨立實驗，表3列出了適應度C 的最差值，最優(yōu)值，平均值，尋優(yōu)成功率和各算法獨立運行一次所用的平均時間。

從表3可以看出，3種算法在100次獨立試驗中都找到過最優(yōu)值，但綜合C 最差值、平均值、尋優(yōu)成功率可以看出PSO 算法最容易陷入局部最優(yōu)，并且在100次獨立實驗中陷入局部最優(yōu)的次數(shù)最多；ICS算法相對PSO、CS算法尋優(yōu)成功率分別提高29.3%、18.3%，平均誤差分別降低了294%、85.8%。說明ICS算法與CS算法在計算時間相差不大的情況下?lián)碛懈鼜姷奶鼍植孔顑?yōu)的能力，搜索精度更高，尋優(yōu)成功的概率更大。

為了進一步分析各算法在測量散斑圖位移的收斂性能，圖6給出了各算法在測量散斑圖位移時的迭代過程。圖中標記點的適應度函數(shù)值都是取在100次獨立實驗中迭代次數(shù)對應的適應度平均值。

圖5 鳥巢運動軌跡

表3 各算法的計算結果

圖6 各算法迭代過程

從圖6可以看出：在迭代初期，ICS算法全局尋優(yōu)能力最強，在鎖定最優(yōu)值范圍后，局部收斂能力最強并且求精能力最優(yōu)。而CS算法在收斂速度和求精能力上都比粒子群算法略優(yōu)。

6 結束語

針對基于傳統(tǒng)DSCM 的計算結果容易陷入局部最優(yōu)，求解精度不高，后期收斂速度慢等缺點，本文將基于群體智能的CS算法引入到DSCM 中，并對基本的CS算法進行了改進，將ICS，CS，PSO 這3種算法用于測量預制模擬散斑圖平移后的整像素位移，實驗結果表明CS 算法在DSCM 中是有效的，并且ICS 方法較CS，PSO 算法在DSCM 中跳出局部最優(yōu)的能力最強，收斂速度最快和尋優(yōu)精度最高。

［1］YANG Yuhang.Study of digital speckle correlation method［D］.Jilin：Changchun University of Science and Technology，2014：5－23 （in Chinese）. ［楊宇航.數(shù)字散斑相關方法的研究 ［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）. ［梁恒.基于數(shù)字散斑相關方法的測量技術研究 ［D］.安徽：合肥工業(yè)大學，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）.［龍文，陳樂.求解約束化工優(yōu)化問題的混合布 谷 鳥 搜 索 算 法 ［J］.計 算 機 應 用，2014，34 （2）：523－527.］

［4］Gandomt A，Yang X，Alavi A.Cuckoo search algorithm：Ameta－h(huán)euristic 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）.［陳志新，梁晉，郭成.數(shù)字散斑相關法在變形測量中的應用 ［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）. ［趙新超，劉國蒞，劉虎球，等.基于非均勻變異和多階段擾動的粒子群優(yōu)化算法 ［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）.［杜亞志，王學濱.基于粒子群算法的整像素數(shù)字圖像相關方法 ［J］.計算機工程與應用，2012，48 （6）：200－228.］