汪峰坤，張婷婷

安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系，蕪湖，241000

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

數(shù)據(jù)聚類(lèi)分析是廣泛用于數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)等領(lǐng)域的一類(lèi)重要算法。聚類(lèi)分析算法與遺傳算法、粒子群算法等智能算法相結(jié)合，通過(guò)聚類(lèi)將搜索重點(diǎn)放到各聚類(lèi)中心附近，可以快速收斂到各聚類(lèi)的最優(yōu)值，如果聚類(lèi)較為合理，則可以求解多峰函數(shù)的解[6,7]。

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

1 布谷鳥(niǎo)算法基本算法

楊新社等2009年提出了針對(duì)函數(shù)最優(yōu)值求解的布谷鳥(niǎo)算法[8]。布谷鳥(niǎo)算法是模擬自然界中布谷鳥(niǎo)寄生育雛的行為來(lái)求解函數(shù)最優(yōu)值問(wèn)題。布谷鳥(niǎo)算法核心思路有：使用Lèvy飛行進(jìn)行鳥(niǎo)巢新址的選擇，使用偏好隨機(jī)游走策略進(jìn)行隨機(jī)大范圍跳轉(zhuǎn)。

2 改進(jìn)算法

2.1 聚類(lèi)方法的改進(jìn)

聚類(lèi)是指把性質(zhì)相近的對(duì)象分在一起作為同一種類(lèi)別。大部分聚類(lèi)算法基于歐幾里得距離來(lái)決定聚類(lèi)。基于這種距離的算法可以發(fā)現(xiàn)球形簇或相近距離的簇。聚類(lèi)算法判斷聚類(lèi)優(yōu)劣性的通用原則是：類(lèi)內(nèi)距離最小，類(lèi)間距離最大[9]。

對(duì)聚類(lèi)中心判斷的通用方法是：

(1)以適應(yīng)度最小的值作為第一個(gè)聚類(lèi)中心。

(2)計(jì)算其余結(jié)點(diǎn)到當(dāng)前所有已知的聚類(lèi)中心的距離之和。

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

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

經(jīng)過(guò)理論證明和實(shí)驗(yàn)仿真，此方法并不能找到最好的聚類(lèi)中心。

本文提出了計(jì)算聚類(lèi)中心的新算法，名稱(chēng)為最大最小距離法,求解聚類(lèi)中心的過(guò)程如下：

(1)以適應(yīng)度最小的值作為第一個(gè)聚類(lèi)中心。

(2)計(jì)算其余結(jié)點(diǎn)距已知聚類(lèi)中心的距離，選擇最小的距離作為此結(jié)點(diǎn)到已知聚類(lèi)中心的距離值。

(3)查找到聚類(lèi)中心的最大距離值的結(jié)點(diǎn)，以此結(jié)點(diǎn)作為新的聚類(lèi)中心。

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

設(shè)鳥(niǎo)巢總數(shù)為N，要求峰數(shù)為K，則最大最小距離法求解聚類(lèi)中心的時(shí)間復(fù)雜度為：O(KN)。

2.2 各聚類(lèi)的布谷鳥(niǎo)算法的改進(jìn)

對(duì)于各聚類(lèi)中鳥(niǎo)巢的最優(yōu)值求解，本文采用基于聚類(lèi)精英策略的小生境布谷鳥(niǎo)算法，流程如下：

(1)查找到類(lèi)中最優(yōu)鳥(niǎo)巢(適應(yīng)度最小)。

(2)循環(huán)遍歷聚類(lèi)中其他鳥(niǎo)巢，由原來(lái)的鳥(niǎo)巢生成新鳥(niǎo)巢。

(3)各鳥(niǎo)巢的Lèvy飛行中的基本步長(zhǎng)值定義為當(dāng)前鳥(niǎo)巢與當(dāng)前聚類(lèi)中最優(yōu)鳥(niǎo)巢之間的距離。

(4)使用隨機(jī)游走策略生成新的鳥(niǎo)巢。

對(duì)于多峰函數(shù)解的搜索過(guò)程，本文針對(duì)布谷鳥(niǎo)算法改進(jìn)如下：

使用基于各聚類(lèi)的精英策略，保留了各聚類(lèi)中最優(yōu)解，最優(yōu)解不進(jìn)行Lèvy飛行，從而保證進(jìn)化過(guò)程中，各聚類(lèi)最優(yōu)解不減少。對(duì)于各聚類(lèi)內(nèi)部，使用了小生境和向最優(yōu)靠近策略，使各類(lèi)中鳥(niǎo)巢在最優(yōu)值附近進(jìn)行Lèvy飛行搜索，增加局部收斂速度。通過(guò)隨機(jī)游走策略增加搜索范圍。

2.3 算法總體流程

本文提出針對(duì)多峰問(wèn)題求解的整體流程如下：

(1)隨機(jī)生成所有鳥(niǎo)巢，計(jì)算各鳥(niǎo)巢的適應(yīng)度。

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

(3)計(jì)算所有鳥(niǎo)巢距各聚類(lèi)中心的距離，將各鳥(niǎo)巢歸類(lèi)到距離最近的聚類(lèi)中。

(4)使用改進(jìn)的布谷鳥(niǎo)算法對(duì)各聚類(lèi)進(jìn)行搜索最優(yōu)值。

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

(6)輸出各聚類(lèi)的最優(yōu)值。

3 算法實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)采用的多峰函數(shù)

本文求解多峰函數(shù)的最小值，參考其他相關(guān)文獻(xiàn)，選擇仿真的多峰函數(shù)如下：

(1)函數(shù)f1：

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

(2)函數(shù)f2：

(3)函數(shù)f3：

3.2 算法性能分析

算法參數(shù)設(shè)置為：鳥(niǎo)巢個(gè)數(shù)N=100，迭代次數(shù)M=100,K為函數(shù)實(shí)際峰值個(gè)數(shù)，根據(jù)函數(shù)特點(diǎn)取值。運(yùn)行10次，取平均值作為計(jì)算結(jié)果。

3.2.1 選擇聚類(lèi)中心算法

以函數(shù)f1為例進(jìn)行實(shí)驗(yàn)仿真，下圖為某次初始化后鳥(niǎo)巢分布和兩種算法求解的5個(gè)聚類(lèi)中心，結(jié)果如圖1。

由圖1可知，使用最大距離算法求得的聚類(lèi)中心遠(yuǎn)沒(méi)有本文提出的最大最小距離算法計(jì)算的聚類(lèi)中心分布均勻。

3.2.2 不同多峰函數(shù)求解

本文使用峰值誤差比率和距離誤差比率來(lái)衡量算法的準(zhǔn)確程度。峰值誤差比率定義為所求出的所有峰值與真實(shí)峰值之間差距的平均值與真實(shí)峰值平均值的比值的絕對(duì)值。距離誤差值定義為所求出的所有峰值與真實(shí)峰值的坐標(biāo)之間距離的平均值。峰值誤差比率和距離誤差值為非負(fù)數(shù)，越小越好。

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

圖1 最大距離算法和最大最小距離算法求解聚類(lèi)中心的比較

表1 不同多峰函數(shù)求解

3.2.3 算法收斂速度

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

4 結(jié) 語(yǔ)

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