求解多峰函數的聚類布谷鳥算法的研究

汪峰坤，張婷婷

安徽機電職業技術學院信息工程系，蕪湖，241000

多峰函數的求解是指求解函數的多個全局或局部的最優解，在工程應用中被廣泛使用[1,2]。通過求解的多個局部最優解，為使用者提供更多的決策選擇。當前針對多峰函數求解和優化常用的方法有基于小生境的遺傳算法、基于引路蜂的人工蜂群算法和多種群的粒子群算法等[3-5]。

數據聚類分析是廣泛用于數據挖掘、模式識別和機器學習等領域的一類重要算法。聚類分析算法與遺傳算法、粒子群算法等智能算法相結合，通過聚類將搜索重點放到各聚類中心附近，可以快速收斂到各聚類的最優值，如果聚類較為合理，則可以求解多峰函數的解[6,7]。

布谷鳥算法是一種常用的函數尋優算法，以其快速的收斂和較大的搜索范圍，廣泛應用于最優解求解中。當前尚未有將布谷鳥算法用于多峰函數求解方面的研究。本文提出了基于最大最小距離法(Max-Min Distance)的鳥巢快速聚類，針對每個聚類使用布谷鳥算法搜索，得到每個聚類的局部最優值的多峰函數求解方法。

1 布谷鳥算法基本算法

楊新社等2009年提出了針對函數最優值求解的布谷鳥算法[8]。布谷鳥算法是模擬自然界中布谷鳥寄生育雛的行為來求解函數最優值問題。布谷鳥算法核心思路有：使用Lèvy飛行進行鳥巢新址的選擇，使用偏好隨機游走策略進行隨機大范圍跳轉。

2 改進算法

2.1 聚類方法的改進

聚類是指把性質相近的對象分在一起作為同一種類別。大部分聚類算法基于歐幾里得距離來決定聚類。基于這種距離的算法可以發現球形簇或相近距離的簇。聚類算法判斷聚類優劣性的通用原則是：類內距離最小，類間距離最大[9]。

對聚類中心判斷的通用方法是：

(1)以適應度最小的值作為第一個聚類中心。

(2)計算其余結點到當前所有已知的聚類中心的距離之和。

(3)以距離最大的值作為新的聚類中心。

(4)重復(2)-(4)步驟，直到找到所有的聚類中心。

經過理論證明和實驗仿真，此方法并不能找到最好的聚類中心。

本文提出了計算聚類中心的新算法，名稱為最大最小距離法,求解聚類中心的過程如下：

(1)以適應度最小的值作為第一個聚類中心。

(2)計算其余結點距已知聚類中心的距離，選擇最小的距離作為此結點到已知聚類中心的距離值。

(3)查找到聚類中心的最大距離值的結點，以此結點作為新的聚類中心。

(4)重復(2)-(3)步驟，直到找到所有的聚類中心。

設鳥巢總數為N，要求峰數為K，則最大最小距離法求解聚類中心的時間復雜度為：O(KN)。

2.2 各聚類的布谷鳥算法的改進

對于各聚類中鳥巢的最優值求解，本文采用基于聚類精英策略的小生境布谷鳥算法，流程如下：

(1)查找到類中最優鳥巢(適應度最小)。

(2)循環遍歷聚類中其他鳥巢，由原來的鳥巢生成新鳥巢。

(3)各鳥巢的Lèvy飛行中的基本步長值定義為當前鳥巢與當前聚類中最優鳥巢之間的距離。

(4)使用隨機游走策略生成新的鳥巢。

對于多峰函數解的搜索過程，本文針對布谷鳥算法改進如下：

使用基于各聚類的精英策略，保留了各聚類中最優解，最優解不進行Lèvy飛行，從而保證進化過程中，各聚類最優解不減少。對于各聚類內部，使用了小生境和向最優靠近策略，使各類中鳥巢在最優值附近進行Lèvy飛行搜索，增加局部收斂速度。通過隨機游走策略增加搜索范圍。

2.3 算法總體流程

本文提出針對多峰問題求解的整體流程如下：

(1)隨機生成所有鳥巢，計算各鳥巢的適應度。

(2)通過最大最小算法求出所有的聚類中心。

(3)計算所有鳥巢距各聚類中心的距離，將各鳥巢歸類到距離最近的聚類中。

(4)使用改進的布谷鳥算法對各聚類進行搜索最優值。

(5)循環(2)-(4)步驟，直到滿足退出條件。

(6)輸出各聚類的最優值。

3 算法實驗與分析

3.1 實驗采用的多峰函數

本文求解多峰函數的最小值，參考其他相關文獻，選擇仿真的多峰函數如下：

(1)函數f1：

f1(x)=-sin6(5π(x0.75-0.05))，函數定義域為：[0,1]。存在著5個非均勻等值分布的峰，峰值為-1，自變量為：0.08,0.247,0.451,0.681和0.934。

(2)函數f2：

(3)函數f3：

3.2 算法性能分析

算法參數設置為：鳥巢個數N=100，迭代次數M=100,K為函數實際峰值個數，根據函數特點取值。運行10次，取平均值作為計算結果。

3.2.1 選擇聚類中心算法

以函數f1為例進行實驗仿真，下圖為某次初始化后鳥巢分布和兩種算法求解的5個聚類中心，結果如圖1。

由圖1可知，使用最大距離算法求得的聚類中心遠沒有本文提出的最大最小距離算法計算的聚類中心分布均勻。

3.2.2 不同多峰函數求解

本文使用峰值誤差比率和距離誤差比率來衡量算法的準確程度。峰值誤差比率定義為所求出的所有峰值與真實峰值之間差距的平均值與真實峰值平均值的比值的絕對值。距離誤差值定義為所求出的所有峰值與真實峰值的坐標之間距離的平均值。峰值誤差比率和距離誤差值為非負數，越小越好。

由表1可得，本文所提出的算法可以搜索到所有峰值。函數f1較簡單，峰值誤差比率和距離誤差值效果都非常好。函數f3較為復雜，本算法準確地找到4個局部最優解，全局最優解有一定的誤差，也在可接受范圍內。由于函數f3對自變量參數比較敏感，所以距離誤差值小于函數f2時，函數f3峰值誤差比率仍然比函數f2大。

圖1 最大距離算法和最大最小距離算法求解聚類中心的比較

表1 不同多峰函數求解

3.2.3 算法收斂速度

圖2和圖3為從第1代到第100代函數f2和函數f3每一代求解的所有峰值的平均值。由圖2和圖3可知，本算法在前期快速收斂到函數各峰值附近，在后期收斂速度變慢，但仍有可能找到更好的解。在搜索過程上，由于Lèvy飛行和隨機游走策略有一定的隨機性，可能會小概率出現平均峰值變壞的情況，如圖2中間13-20代，但不影響總體變化趨勢。

4 結 語

本文提出求解多峰函數的聚類布谷鳥算法，針對常用的最大距離法的不足，提出了效果更好的最大最小距離方法，該方法求出的聚類中心分布更加均勻。對于各聚類中的鳥巢使用布谷鳥算法進行局部尋優，布谷鳥算法可以快速收斂到局部最優解，并且利用Lèvy飛行的重尾特性和小概率的偏好隨機游動，可以提高搜索的范圍。通過實驗仿真表明，本算法有一定的實用價值。