均勻局部搜索和高斯變異的布谷鳥搜索算法

黃海燕，彭 虎，鄧長壽，王曉靜，張 艷，譚旭杰

(九江學院 信息科學與技術學院，江西 九江 332005)

1 引 言

布谷鳥搜索 (Cuckoo Search，CS)算法是由Yang等人[1]提出的，它是模擬布谷鳥借巢產卵的繁殖原理及結合Levy飛行特征發展起來的智能算法.CS算法具有參數少，易實現、全局搜索能力強等優點，并已成功解決了工程科學技術領域中的一些復雜優化問題.

CS算法在迭代過程中主要采用兩種方式對原鳥巢進行更新，第一種是基于Levy分布的方式生成新解，以平衡CS算法的局部搜索，第二種是采用偏好隨機游走的方式生成新解，以平衡算法的全局搜索.國內外學者針對Levy飛行和偏好隨機游走中的步長、自適應步長、自適應發現概率以及混合策略對CS算法進行改進研究.如 Walton等人[2]提出讓Levy隨機步長的控制量隨著鳥巢后代的增加而減小，實驗結果表明這種方法提高了CS算法的優化性能.Wang 等人[3]提出在偏好隨機游走中引入逐維更新評價策略，以避免維間相互干擾，實驗結果表明這種方法提高了算法的收斂速度并改善了解的質量.Ma等人[4]提出采用退火時機的判斷準則解決算法陷入局部最優的問題，實驗結果表明這種方法提高了算法的尋優精度和收斂速度.

CS算法存在局部搜索能力弱、收斂速度慢、求解精度不高等問題.有研究人員針對算法的局部開采能力不足、易于停滯等問題做了一些改進.如Peng等人[5]在DE算法中引入均勻局部搜索策略增強算法的局部開采能力，并已成功提高了DE算法的優化性能.如Qu等人[6]提出加入高斯變異算子克服算法陷入局部最優值的缺陷，并有效地提高了算法的收斂精度和收斂能力.

受以上方法的啟發.本文提出了均勻局部搜索和高斯變異的布谷鳥搜索(cuckoo search algorithm of uniform local search and gauss mutation，UGCS) 算法.該算法主要做了兩方面的改進：1)算法在基于Levy飛行產生新解后，任意選擇兩個個體執行均勻局部搜索，從而產生一個新的最優個體進行迭代，通過這種方法加強算法的局部開采能力；2)對被宿主發現的鳥巢采用高斯變異進行更新，加強原鳥巢鄰域內的搜索，從而提高算法的收斂能力.最后選擇了13個測試函數驗證UGCS算法的性能，實驗結果表明本文所提出的算法尋優精度較高，具有較好的收斂速度.

2 標準布谷鳥搜索算法

布谷鳥搜索算法是模擬布谷鳥借窩產蛋的繁殖原理來有效地求解最優化問題.根據昆蟲學家長期觀察研究發現，有一部分布谷鳥自己不筑巢，趁著宿主離巢的時候快速將蛋下在其巢中，讓這些宿主替它孵化，在某些情況下，宿主也會發現巢穴中的外來蛋，此時宿主就會選擇放棄該巢穴并重新筑巢[7].為了模擬布谷鳥尋窩的方式，布谷鳥搜索算法需要設定以下三個理想規則[8]：

規則1. 每一只布谷鳥1次只能產一顆蛋，并隨機選擇一個鳥巢存放；

規則2. 每一個放有蛋的鳥巢就是一個可行解，存放最好蛋的鳥巢就是一個最優解，最優解將會被記錄到下一代；

規則3. 可用的鳥巢數量是固定不變的，并且鳥巢中外來蛋發現的概率為Pa∈[0，1].

基于以上三個理想的假設，CS算法在迭代過程中采用Levy fights隨機游走和偏好隨機游走這兩種方式更新鳥巢位置.

(1)

Levy(β)～u=t-β(1<β≤3)

(2)

第二種更新公式是當宿主發現外來蛋放棄該鳥巢重新筑巢時，采用公式(3)移動并產生新的鳥巢.

(3)

算法1.標準CS算法

Step1. 設置各參數值：包括種群規模N，維數D，外來蛋發現概率Pa，最大函數評價次數nfevalmax等參數；

Step2. 初始化種群，隨機產生包含N個D維向量Xi=(Xi，1，Xi，2，…，Xi，D)初始鳥巢種群，一個鳥巢就是一個可行解，計算每個鳥巢的適應度值，且保留適應度值最優的鳥巢；

Step3. 開始搜索，利用公式(1)對所有鳥巢進行更新產生下一代鳥巢，計算新一代鳥巢的的函數適應度值，如果適應度值優于上一代，則替代；

Step4. 判斷，對所有鳥巢產生均勻分布隨機數r，將r和Pa進行比較，如果r>Pa，則采用公式(3)進行更新，反之則不變；

Step5. 記錄適應度值最優的鳥巢，若不滿足迭代停止條件，則返回Step 3.

3 均勻局部搜索和高斯變異的布谷鳥搜索算法

標準CS算法基于Levy飛行隨機產生新解，但這種方式會導致算法局部搜索能力弱，收斂精度不高的問題.因此在第一次更新后任意選擇兩個個體執行均勻局部搜索，產生新的最優個體進行迭代，從而提高算法的收斂精度，但是引用ULS算子后，在進化后期會導致算法易于陷入局部最優值，因此在算法進行二次更新的時候，采用高斯變異更新個體，則可有效地抑制算法過早收斂，從而提高算法的收斂能力.

3.1 均勻局部搜索

我國方開泰和王元[12]兩位數學家于1978年提出了均勻設計試驗方法，它是一種科學的高質量試驗設計工具，和另外一種流行的功能強大的正交設計相比較，均勻設計的試驗次數減少了很多.Peng 等人[5]基于均勻設計提出了均勻局部搜索(Uniform local search，ULS)，并將之用于增強DE算法的局部開采能力，實驗結果證明了ULS優異的局部搜索性能.同樣地，針對CS算法局部搜索能力弱的缺陷，本文提出利用ULS來提高CS算法的局部開采能力，也就是在每一代種群中任意選擇2個個體基于ULS產生一個新的最優個體.表1 顯示的是一個U7(76)均勻設計表，本文所提出的UGCS算法使用的均勻設計表U6(66)是通過在U7(76)中刪除最后一行構造的.

表1 均勻設計表 U7(76)Table 1 Uniform design table U7(76)

如圖1所示，在均勻局部搜索中，在第t代任意選擇2個個體Xi和Xj來完成一組試驗，在這組試驗中基于均勻設計表U6(66)產生6個試驗個體，計算這6個試驗個體的目標函數值，從中選擇函數值最好的個體Z，如果Z的函數值是優于Xi和Xj中的任意一個，則用Z來替代Xi或Xj.圖1顯示了在二維空間以U6(66)表第1列和第3列為基礎所產生的6個試驗個體，假設Z點就是這6個試驗個體中最好的一個，個體Z由第一維的水平4和第二維的水平5組成.

圖1 二維搜索空間中兩個隨機個體的均勻局部尋優示意圖[5]Fig.1 Illustration of the uniform local search with two randomly chosen individuals in the two-dimensional search space[5]

算法2[5]描述了ULS的步驟，在ULS中，如果問題規模D小于6，就直接執行ULS，如果問題規模D大于6，那么將D隨機分成6組.

算法2.均勻局部搜索

Step1. 輸入參數值：種群P，評價次數N_iter；

Step4. 計算這6個試驗個體目標函數值f(Y1)……f(Y6)；

Step5. 從Y0和Y6中選擇一個最優個體Z；

Step7. N_iter=N_iter+6；

Step8. 返回更新后的種群和函數評價次數.

3.2 高斯變異算子

引入ULS后，在進化后期可能會忽略領域內的一些有效信息，造成算法易于陷入局部收斂的現象，因此當放有外來蛋的鳥巢被宿主發現后，采用高斯變異算子更新該鳥巢，從而加強原鳥巢鄰域內的搜索.

高斯變異的思想為：每次迭代計算的時候通過高斯分布函數產生一個均值為0，標準差為1的高斯變異矩陣，將得到的結果點乘原鳥巢的每一維作為更新步長.由于高斯分布曲線的高峰位于均值所在的位置，根據這個特性可知，高斯變異會重點搜索原鳥巢附近的局部區域，通過高斯變異策略提高了算法的收斂能力.UGCS算法高斯變異公式：

stepsize=normrnd(0，1，N，D)

(4)

(5)

其中stepsize為步長，normrnd ()為高斯分布函數，N為種群規模，D為維數.

3.3 UGCS算法

UGCS算法的基本思路：首先是在對所有鳥巢采用公式(1)更新后，任意選擇兩個鳥巢執行均勻局部搜索ULS，然后在第二次更新的時候，采用高斯變異重新產生新的鳥巢.UGCS算法框架和標準CS算法基本相似，區別是在Step3后執行ULS操作，在Step5中利用公式(5)進行二次更新.

算法3. UGCS算法

Step1. 設置各參數值；

Step2. 隨機初始化種群產生N個鳥巢Xi(i=1，2，…，N)，計算每個鳥巢適應度值：fi(i=1，2，…，N)；

Step3. 利用公式(1)生成新解Xnew，計算新解Xnew的適應度值fnew，如果(fi>fnew)，用Xnew替代之前的解；

Step4. 執行均勻局部搜索(算法2)；

Step5. 判斷，產生一個隨機數r∈(0，1)，如果r大于發現鳥蛋概率Pa，利用公式 (5)更新該鳥巢；

Step6. 記錄最好的解，若不滿足迭代停止條件，則返回Step 3.

4 實驗結果分析

4.1 測試函數和參數設置

為了驗證UGCS算法的有效性，實驗選取了13個測試函數進行測試，具體如表1所示.其中f1～f7是單峰函數[13]，f8～f13是多峰函數[13]，在實驗中參數設置為：維數D=30，外來蛋發現概率Pa=0.25，種群規模N=100，最大函數評價次數N_iter=10000*D，每個測試函數獨立運行30次.實驗環境：64位Windows 7操作系統，Matlab R2010b編譯軟件，處理器主頻3.4GHZ，內存8GB.

表2 基準測試函數Table 2 Benchmark functions

為了更加客觀公正的驗證UGCS算法的實驗結果，采用了統計學中的Wilcoxon秩和檢驗與Friedman檢驗對實驗結果進行分析.Wilcoxon秩和檢驗[14]是用來決定兩個獨立樣本是否來自相同或相等的總體，所以本文通過Wilcoxon秩和檢驗的方法來檢驗各算法在每個測試函數上的結果和UGCS實驗結果檢驗是否存在明顯差異，Friedman檢驗[15]是一種利用秩實現對多個總體分布是否存在顯著差異的非參數檢驗方法，Friedman檢驗結果中的秩均值越小表明該算法性能就越好.

4.2 UGCS算法解的質量分析

UGCS算法同時引入了均勻局部搜索和高斯變異兩種策略來提高算法的尋優性能，所以我們不僅僅和CS算法進行對比分析，還和算法的兩個簡化版UCS算法和GCS算法進行比較來驗證新算法的質量.UCS算法是在CS算法中引入了均勻局部搜索策略，GCS算法是在CS算法中引入了高斯變異策略進行計算.為了客觀公正的評價UGCS、CS、UCS、GCS算法性能，采用同樣的參數設置.表3顯示的是各算法30維的實驗結果，并給出了0.05顯著水平下的Wilcoxon秩和檢驗結果，在表3的底部，符號“ -”，“+”，“≈”分別表示相對應的算法劣于、優于、相似于UGCS算法的結果，各算法的Friedman檢驗結果排名如表4所示.CS、UGCS、UCS、GCS算法的收斂曲線如圖2所示，各算法的各函數收斂曲線數據來源于各測試函數獨立運行30次的平均值.

表3 各算法的平均誤差值、標準差和Wilcoxon秩和檢驗結果(D=30)Table 3 Mean error value and standard deviation of algorithms and comparison results based on wilcoxon′s rank sum test

圖2 各算法求解f1～f13函數的收斂曲線Fig.2 Convergence curve of algorithms in solving f1～f13 function

對表3的實驗結果分析可以發現，UGCS算法的尋優精度得到了較大提升，從表3最后三行統計結果可以很直觀的看出UGCS算法比其他所比較的算法性能明顯要好.

對于單峰函數f1～f7，UGCS算法在f1，f2，f4，f7優勢比較明顯，但在f3上劣于GCS、UCS，在f5上劣于UCS；對于多峰函數f8～f13，UGCS算法基本上都相似于或優于其他比較的各算法，并且f6，f9，f10，f11收斂于0，但在f13上要劣于CS算法和UCS算法，f8上劣于CS算法.

表4 各算法的Friedman檢驗排名Table 4 Average rankings achieved by friedman test

從圖2可以看出UCS算法在求解f3、f4、f7、f9、f10、f11、f12、f13這8個函數最優值的時候都過早的收斂，陷入了局部最優值.除在f4上劣于CS算法外，在其他12個函數上收斂能力都要優于CS算法.UGCS算法在求解f3、f5、f7、f8、f12、f13這6個函數最優值的時候陷入了局部最優值，但在f1、f2、f4、f6、f7、f9、f10、f11、f12上收斂能力優于UCS算法.從表4的Friedman檢驗排名可以看出UGCS的秩均值是最小的，從統計學上說明UGCS算法是所有參與比較的算法中最優的.

綜合以上所有實驗分析可以發現，UCS算法中的ULS算子和GCS算法中的高斯變異算子確實都提高了算法的收斂精度和收斂能力，整體性能上都優于標準CS算法.UGCS算法結合這兩種算法的優點，通過均勻局部搜索提高算法的局部搜索能力，高斯變異策略則有效地抑制了算法過早收斂，提高了算法的收斂能力.

表5 CS、UGCS算法5維和10維的平均誤差值、標準差和Wilcoxon秩和檢驗結果Table 5 Mean error value and standard deviation of cs and ugcs algorithm and comparison results based on wilcoxon′s rank sum test

4.3 維數變化分析

為了觀察UGCS算法對不同問題維數的性能，進一步驗證算法的有效性和可靠性，針對13個測試函數分別做了5維、10維、15維、20維、50維和100維的實驗.表5至表7分別列出了CS算法、UGCS算法在5維、10維、15維、20維、50維和100維上的實驗結果，其他參數設置： N=100，Pa=0.25，N_iter=10000*D，每個算法獨立運行30次.

表6 CS、UGCS算法15維和20維的平均誤差值、標準差和Wilcoxon秩和檢驗結果Table 6 Mean error value and standard deviation of cs and ugcs algorithm and comparison results based on wilcoxon′s rank sum test

對表5和表7分析可以發現，在5維、10維、15維和20維上，對于單峰函數，UGCS算法在f1、f2、f3、f4、f7上與CS算法相比要好，f6上結果相似，僅僅在f5上劣于CS算法，對于多峰函數，UGCS算法在f9～f12上與CS算法相比都要好，在f8，f13上與CS算法相比較弱，但在20維上f13要優于CS算法.在50維上，對于單峰函數，UGCS算法在f1、f2、f3、f4、f7上與CS算法相比要好，f6上結果相似，僅僅在f5上劣于CS算法，對于多峰函數，在f8、f13上劣于CS算法；在100維上，對于單峰函數，在f1、f3、f7上優于CS算法，f2、f6上相似，在f4、f5上劣于CS算法，對于多峰函數，在f9～f12上優于CS算法，f8、f13上劣于CS算法.

表8列出了UGCS算法和CS算法在不同維數上的Friedman檢驗結果，對表8分析可以發現，隨著維數從5維增加到20維，秩均值越來越小，意味著UGCS算法性能越來越好，并且都優于CS算法，當維數從30維增加到100維時，UGCS算法尋優效果有所下降，但仍然優于CS算法.

表7 CS、UGCS算法50維和100維的平均誤差值、標準差和Wilcoxon秩和檢驗結果Table 7 Mean error value and standard deviation of cs and ugcs algorithm and comparison results based on wilcoxon′s rank sum test

表8 CS算法和UGCS算法在不同維數上的Friedman檢驗結果Table 8 Friedman test results of CS and UGCS algorithm on different dimension

實驗結果分析表明：在低維的時候，UGCS算法不受維數變化的影響，但是從30維變化到100維，UGCS算法的性能受維數變化的影響，收斂精度有所下降，但整體而言還是要優于CS算法的性能.

4.4 種群變化分析

為了觀察UGCS算法不同種群規模對算法性能的影響，針對13個測試函數做了種群規模分別為30和50的實驗，其他實驗參數為： D=30，Pa=0.25，N_iter =10000*D，每個算法獨立運行30次.表9列出了CS算法、UGCS算法種群規模為30和50的實驗結果.

對表9分析可以發現，在種群規模為30的時候，UGCS算法在f1、f2、f4、f7、f9、f10、f11上與CS算法相比要好，在f3、f5、f8、f12、f13上要劣于CS算法，f6上和CS算法相似，整體而言UGCS算法性能要優于CS算法.在種群規模為50的時候，在f1、f2、f4、f7、f9、f10、f11、f12上與CS算法相比要好，在f3、f5、f8、f13上劣于CS算法，f6上和CS算法相似.從種群規模為30、50和100的實驗結果中可以發現，隨著種群規模的增加，CS算法的性能在f1、f2、f3、f5、f8、f9、f10、f11、f12、f13上惡化嚴重，但UGCS算法只在f1、f2、f4上惡化嚴重，在其他函數上的性能反而有所提高.

表9 CS、UGCS算法30種群規模和50種群規模的平均誤差值、標準差和Wilcoxon秩和檢驗結果Table 9 Mean error value and standard deviation of cs and ugcs algorithm and comparison results based on wilcoxon′s rank sum test

4.5 不同均勻設計表對UGCS算法的影響

UGCS算法中的ULS是基于均勻設計提出的，而均勻設計又是通過一套精心設計的表來進行試驗設計的，經常用Un(ns)來表示一個均勻設計表，其中U表示均勻設計，在這個均勻設計表中共有n行(也就是要完成n次試驗)和s列(也就是所選擇的最大因素)，每個因素包含n個水平.

表10 不同均勻設計表平均誤差值結果(D=30)Tabe 10 Mean error value of different uniform design tables(D=30)

表11 UGCS算法和其他演化算法的平均誤差值和Wilcoxon秩和檢驗結果Table 11 Mean error value of ugcs and the other algorithms and comparison results based on wilcoxon′s rank sum test

4.6 與其他演化算法比較

為了進一步驗證UGCS算法的尋優性能，選擇了和DDIC算法[3]、ODE算法[16]、MGBDE算法[17]、GABC算法[18]、VSSFA算法[19]這幾種演化算法進行實驗比較.其中 DDICS算法是對CS算采用逐維更新評價策略進行改進從而提高了解的質量；ODE算法和MGBDE算法是對標準DE算法的改進，ODE算法是將反向學習用于種群初始化和后代移動中，從而改善算法性能，MGBDE算法是在種群初始化期間隨機分布變異策略的方式初始化解向量，從而提高算法性能；GABC算法是對ABC算法的改進，它是將全局最優信息引入食物源的搜索策略中，從而提高算法的收斂精度及速度；VSSFA算法是對FA算法的改進，它是通過動態調整步長因子的方式提高算法的收斂精度.表11列出了各比較算法在30維的實驗結果，UGCS算法和DDICS算法的其他參數設置為： N=100，Pa=0.25，N_iter=10000*D，而ODE算法、MGBDE算法、GABC算法、VSSFA算法除了維數、種群規模、評價次數的參數是相同的外，這些算法的其他詳細參數見文獻[16-19]，每個算法都獨立運行30次.

從表11中底部的統計結果可知，VSSFA算法性能是最差的，對于單峰函數，UGCS算法在f1、f2、f4、f7上與其他比較算法相比要好，在f3上要遜色于DDICS算法、ODE算法、MGBDE算法，但是要優于GABC算法、VSSFA算法，f5上劣于ODE算法、MGBDE算法、GABC算法，但要優于DDICS算法.對于多峰函數，在f7、f9、f10、f11上與其他比較的各算法相比要好或相似，在f8上劣于GABC算法，但比其他幾個算法都要好，在f12、f13上遜色于ODE算法、GABC算法，但比DDICS算法和VSSFA算法性能要好，在f6上幾個算法性能基本都是相似的.實驗結果表明UGCS算法性能要優于DDICS算法、ODE算法、MGBDE算法、GABC算法、VSSFA算法，UGCS算法是一種具有競爭力的算法.

5 總 結

布谷鳥搜索算法是一種簡單高效的群智能算法，并已成功解決了工程中的一些復雜優化問題.由于CS算法的局部搜索能力弱，導致算法的尋優精度不高，收斂速度慢.UGCS算法通過引入均勻局部搜索策略加強了CS算法的局部開采能力，通過引入高斯變異策略增加解的多樣性，進一步加強了算法的局部搜索能力.本文從不同維數、不同種群、不同的均勻設計表多方面多角度進行了大量的實驗，實驗結果表明：UGCS算法對于單峰函數、多峰函數都能提高尋優精度和收斂速度，隨著維數的增加，UGCS算法也能很好的改善CS算法解的質量.后續工作將考慮將均勻局部搜索策略應用到其他的群智能算法中，此外還需要在一些工程優化等實際問題中應用該算法進行分析驗證.