王金永, 董玉民
(1.青島理工大學 計算機工程學院,山東 青島 266033;2.青島理工大學 網(wǎng)絡中心,山東 青島 266033)
1995年,Eberhart和Kennedy在長期觀察鳥群、魚群覓食行為規(guī)律的啟發(fā)下,提出了粒子群算法(Particle Swarm Optimization,PSO),該算法是一種基于群智能(Swarm Intelligence)的優(yōu)化算法[1]。鳥群在覓食行為遇到危險信號時,每一只鳥通過合作與競爭產(chǎn)生強大的力量來盡快地取得食物、避開危險。該算法可以根據(jù)當前的搜索情況,動態(tài)調(diào)整其搜索策略。由于算法收斂速度快,全局搜索能力強,需要設(shè)置參數(shù)少,近年來提出了許多改進算法來增強跳出局部極值的能力,受到學術(shù)界的廣泛重視[2]。
由于粒子群算法的優(yōu)良特性,在很多相關(guān)領(lǐng)域引起了對這一新生事物的迅速關(guān)注。首先是在1997年,由Eberhart R C[3]等提出了二進制粒子群算 法。隨 后,Shi Y[4-5]和Eberhart R C[6]在1998年對速度項引入了慣性權(quán)重參數(shù),提高了算法的收斂性,并在程序運行過程中不斷動態(tài)地調(diào)整慣性權(quán)重來調(diào)節(jié)算法的收斂速度,該方程被稱之為標準的PSO算法[7]。為了改善算法的收斂性,1999年,Clerc等引入了收縮因子,提出了帶收縮因子的CF-PSO算法[8-9]。
聚類分析(cluster analysis)簡稱聚類(clustering),是將數(shù)據(jù)觀測對象逐步劃分成子集的過程,每個子集是一個簇(cluster),通過聚類,結(jié)果是每一個簇中的對象彼此相似,并且與其他簇中的對象不相似。由于簇是數(shù)據(jù)對象的集合,因此數(shù)據(jù)對象的簇可以看作隱含的類。在這種意義下,聚類有時又稱為自動分類。聚類可以自動地發(fā)現(xiàn)大量數(shù)據(jù)的分組,這是聚類分析的突出優(yōu)點。對聚類分析的算法研究也就成為研究的熱點。為了很好地處理分類屬性數(shù)據(jù),文獻[10]提出一種加權(quán)粗糙聚類算法,該算法聚類結(jié)果不受數(shù)據(jù)樣本輸入順序的影響,根據(jù)粗糙集理論中的信息增益概念自適應地更新聚類過程,來獲取全局最優(yōu)的聚類權(quán)重和聚類劃分。近幾年對數(shù)據(jù)聚類的研究越來越多,出現(xiàn)了一些新型聚類算法,如張莉[11]等提出了基于樣本預處理的核聚類算法,王順久[12]等提出了基于樣本的投影尋蹤聚類算法,王娜[13]等提出了基于流行距離的迭代優(yōu)化聚類算法等。
粒子群算法的基本思想來源于自然界中的鳥群覓食行為,在算法中,每一個優(yōu)化問題的解看作搜索空間中的一只鳥,即“粒子”。算法開始時,首先在可行解空間中隨機初始化一群粒子,即隨機生成初始種群,并且根據(jù)目標函數(shù)計算出每一個粒子的適應度值。每個粒子在空間中飛行的方向和距離由運動的速度決定,一般情況下,就像鳥兒追隨離食物最近的鳥群一樣,粒子也會追隨離最優(yōu)粒子距離最近的粒子群周圍搜索。在每一次的迭代中,粒子將根據(jù)兩個極值來不斷更新迭代,一個是粒子自身經(jīng)歷過的最優(yōu)位置,也就是自身最優(yōu)解,另外一個是整個種群經(jīng)歷過的最優(yōu)位置,也就是全局極值。
為了將粒子群算法實現(xiàn),需先將算法用數(shù)學形式描述:假設(shè)由n個粒子組成的種群Z={Z1,Z2,…,Zn},其中問題的一個解用每一個粒子的位置Zi={zi1,zi2,…,ziD}來表示,D表示粒子的空間搜索維數(shù)。種群中的每一個粒子通過不斷調(diào)整自己的位置Zi來搜索更新解。在搜索過程中,每一個粒子都能記住自己經(jīng)歷過的最好位置,即搜索到的自身最好解,記做pid,以及整個粒子群經(jīng)歷過的最好的位置,即目前搜索到的群體最優(yōu)解,記做pgd。除了用位置表示粒子信息外,用速度來表示粒子的運動方向,記做Vi={vi1,vi2,…,viD},當pid和pgd都找到后,粒子的速度更新情況見式(1),位置更新情況見式(2)[14]。
式中:vid(t+1)——第i個粒子在第t+1次迭代中第d維上的速度;
ω——粒子運動的慣性權(quán)重;
η1,η2——加速常數(shù);
rand()——0~1之間的隨機數(shù)。
搜索運動過程中,為了防止粒子的運動速度過大,即算法收斂速度過快,可以設(shè)速度上限vmax,當vid(t+1)≥vmax時,vid(t+1)=vmax;當vid(t+1)≤-vmax時,vid(t+1)=-vmax。
從粒子速度更新式(1)和位置更新式(2)可以看出,粒子的運動方向由3部分影響因素決定:自己原有的速度vid(t)、粒子當前位置與自身最佳位置的距離pid-zid(t)、粒子當前位置與群體最佳位置的距離pgd-zid(t),并分別設(shè)置每一部分的權(quán)重來表示相對重要性,分別由權(quán)重系數(shù)ω,η1,η2表示,當找到足夠好的最優(yōu)解或達到最大迭代次數(shù)時,算法結(jié)束。影響粒子運動方向的3部分影響因素的加權(quán)求和示意圖如圖1所示。
圖1 3種移動方向的加權(quán)求和示意圖
經(jīng)過了解粒子群算法的概念、基本原理和數(shù)學描述,下面介紹粒子群算法的基本流程,如圖2所示。
圖2 算法流程圖
從粒子群算法流程圖可以看出,粒子群算法參數(shù)相對較少,數(shù)學原理簡單,迭代循環(huán)簡單易懂,算法易于實現(xiàn)。為了描述算法流程,需要先定義幾個參數(shù)和函數(shù),先假定粒子群種群規(guī)模為n。
設(shè)Zi={zi1,zi2,…,ziD}表示第i個粒子的位置;
fitness(Zi)表示求第i個粒子的解,也就是適應度函數(shù);
Vi={vi1,vi2,…,viD}表示第i個粒子的速度向量;
pid表示自身搜索到的最優(yōu)解,即第i個粒子經(jīng)歷到的最優(yōu)位置;
pgd表示全局搜索到的最優(yōu)解,即種群中適應度最高的最優(yōu)位置。
下面對算法流程圖2做詳細說明:
第1步:初始化粒子群。
1):隨機初始化種群,隨機初始化粒子位置Zi={zi1,zi2,…,ziD};
2)隨機初始化粒子速度Vi={vi1,vi2,…,viD};
3)計算適應度函數(shù)fitness(Zi),并令pid=zid,i=1,2,…,n;d=1,2,…,D;
4)初始化全局最優(yōu)解pgd,選擇種群中的適應度函數(shù)值最高的粒子的位置向量初始化pgd,i=1,2,…,n。
第2步:按照下面步驟算法循環(huán)迭代,直到滿足算法結(jié)束的條件為止。
1)選擇恰當?shù)乃俣葢T性因子ω;
2)計算群體中所有粒子的適應度函數(shù)值fitness(Zi),當出現(xiàn)個體適應度函數(shù)值大于當前個體最優(yōu)適應度函數(shù)值時,即fitness(zid)>fitness(pid),令pid=zid;
3)當種群中個體最優(yōu)值pid大于當前群體最優(yōu)值 時,則 更 新pgd的 值,即fitness(pid)>fitness(pgd),令pgd=pid;
4)依據(jù)式(1)和式(2)不斷更新每一個粒子的速度和位置,即更新vid和zid的值。
在基本粒子群算法的數(shù)學描述中(見式(1)和式(2)),主要有3個影響決定粒子速度和位置的參數(shù),分別是速度慣性權(quán)重ω、速度調(diào)節(jié)參數(shù)η1,η2,參數(shù)的選擇對粒子群算法的性能和效率有很大的影響,ω表示粒子從當前時刻到下一時刻保持的運動慣性,η1,η2表示粒子向自身當前最優(yōu)位置pid和群體當前最優(yōu)位置pgd運動的加速權(quán)重。下面分析3個系數(shù)表示的意義:如果慣性權(quán)重ω=0,那么說明粒子的運動速度沒有慣性,不受當前運動速度的影響,粒子群將收斂到當前的全局最優(yōu)位置,不會再去搜索更優(yōu)解。如果參數(shù)η1=0,那么說明不會追隨自身最優(yōu)位置,粒子失去“自我認知”能力,只具有“社會認知”能力,此時粒子群收斂速度很快,同時容易陷入局部極值。如果參數(shù)η2=0,那么說明粒子失去“社會認知”能力,只具有“自我認知”能力,這時候相當于多個粒子各自獨立搜索,很難搜索收斂到全局最優(yōu)解。通過分析得知,3個參數(shù)都會影響算法的搜索效率,針對不同的問題,選擇適合的參數(shù)才能取得更好的收斂速度和穩(wěn)定性,根據(jù)大量實踐經(jīng)驗,令ω取0~1之間的隨機數(shù),η1,η2分別取2,可以取得較好的效果。
設(shè)N個樣品構(gòu)成的樣品集X={Xi,i=1,2,…,N},其中Xi為n維特征向量,用表示第j個聚類的中心,用表示樣品Xi到對應的聚類中心的歐氏距離,聚類問題就是要找到一個劃分ω={ω1,ω2,…,ωM},使得總的類內(nèi)離散度和J達到最?。?5]:
聚類準則函數(shù)J即為各類樣品到對應聚類中心的距離的總和。
當聚類中心確定時,可以由最近鄰法則決定聚類的劃分。即對樣品Xi,若第j類的聚類中心滿足,就是樣品Xi與聚類中心之間的距離是所有樣品與聚類中心距離的最小值,見式(4),則樣品Xi屬于聚類ωj。
在用粒子群優(yōu)化算法求解聚類問題時,每一個粒子就是問題的一個可行解,所有的粒子組成粒子群(也就是解集)。根據(jù)對聚類結(jié)果理解的不同,對解集的描述可以有兩種形式:第1種是類ω1,ω2,…ωM為解集,也就是聚類結(jié)果;第2種是以中心集合(j=1,2,…,M)為解集,即聚類結(jié)果。論文中采用第2種形式,用基于聚類中心集合作為聚類問題的對應解,也就是說解集是由M個聚類中心組成的,M是已知的聚類數(shù)目。
根據(jù)粒子群算法的數(shù)學描述式(1)和式(2),可以得到粒子i的速度和位置更新公式:
根據(jù)已經(jīng)定義好的粒子群結(jié)構(gòu),采用粒子群聚類算法便可以求得聚類問題的最優(yōu)解。通過剛才介紹粒子群聚類算法的原理、算法描述和算法實現(xiàn)步驟,通過編寫程序,并且在MATLABR2013a編程環(huán)境寫運行,可以觀察分析粒子群算法的具體應用。首先給出粒子群聚類算法的核心代碼,第一大模塊是根據(jù)式(5)和式(6)更新粒子的位置和速度代碼[16]:
第二大模塊是利用距離的平方和的平方根來度量粒子之間的距離,具體代碼如下:
第三大模塊是求粒子的適應度,根據(jù)粒子群聚類算法的粒子適應度更新條件,適應度取歐式聚類的倒數(shù),程序代碼如下:
下面對某地區(qū)的煤層地質(zhì)條件數(shù)據(jù),應用粒子群優(yōu)化算法進行聚類分析,根據(jù)不同煤層塊段的特征:平均厚度、煤層傾角、離差系數(shù)、煤層合格標準、含矸系數(shù)等進行分類,聚類后的數(shù)據(jù)可以用于指導煤礦的開采,提高煤礦開采的安全性和效率。
各煤層塊段的特性指標值見表1。
表1 各煤層塊段的特性指標值
程序中設(shè)定樣本數(shù)據(jù)的聚類數(shù)目為K=3,維數(shù)D=5,通過運行程序,pso聚類的全局最優(yōu)位置、函數(shù)適應度如下,并且繪制了函數(shù)適應度曲線。
實驗目的:對上述實驗數(shù)據(jù)應用粒子群聚類算法,在MATLABR2013a編程環(huán)境下運行聚類算法程序,觀察聚類效果。
實驗的適應度函數(shù)是:result=dis;%適應度函數(shù)。
粒子群聚類算法中“函數(shù)適應度-迭代次數(shù)”曲線如圖3所示。
圖3 粒子群聚類算法中“函數(shù)適應度-迭代次數(shù)”曲線
1)當?shù)螖?shù)MaxDT=100時,迭代次數(shù)-適應度值曲線見圖3(a)。
最后結(jié)果是:ans=3.240801487577032e-04。
2)當?shù)螖?shù)MaxDT=200時,迭代次數(shù)-適應度值曲線見圖3(b)。
最后結(jié)果是:ans=1.617915530278782e-04。
3)當?shù)螖?shù)MaxDT=500時,迭代次數(shù)-適應度值曲線見圖3(c)。
最后結(jié)果是:ans=6.465458242701003e-05。
實驗結(jié)果分析:由于“w=1-t/MaxDT”,即慣性因子與迭代次數(shù)有關(guān),進而影響粒子速度更新公式“v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));”,也就影響了粒子的位置“pos(i,:)=x(i,:)+v(i,:)”,最終也會影響粒子之間的歐氏距離,也就是實驗的適應度函數(shù)是:“result=dis;%適應度函數(shù)”,所以圖3中的3幅圖像的初始適應度有差別,但是隨著迭代次數(shù)的增加,都在不斷的減小。從3次(迭代次數(shù)分別是100、200、500)程序運行情況可以得出:適應度ans即result代表樣品和聚類中心的歐氏距離,隨著迭代次數(shù)越大,函數(shù)的適應度ans越小,最終趨于零。說明樣品與聚類中心的距離不斷減小,當?shù)螖?shù)大約為500時,適應度測量函數(shù)歐式距離趨于零,數(shù)據(jù)的聚類效果越好。
粒子群優(yōu)化算法的缺點是易陷入局部極值點;全局搜索能力強,但是搜索精度不高;PSO算法同時記憶位置和速度信息,高效的信息共享機制可能導致粒子尋優(yōu)時都移向某個全局最優(yōu)點。粒子群算法的優(yōu)點是收斂速度較快;全局搜索能力強,能夠有效避免早熟;粒子群中多個粒子同時搜索,具有并行性;需要設(shè)置的參數(shù)較少,因此算法簡單,易于實現(xiàn)。
K-均值算法思想簡單易行,是一種傳統(tǒng)的聚類分析方法,但是當數(shù)據(jù)中存在離群點時,K-均值聚類效果會更不理想,K-均值的聚類結(jié)果受初始聚類中心的選擇影響較大,如果初始聚類中心選擇不當,算法可能收斂于一般結(jié)果。認識到粒子群算法和K-均值聚類算法各自的優(yōu)缺點之后,可以設(shè)想將兩種算法都進行改進結(jié)合,充分利用各自的優(yōu)點,避開兩種算法的缺點,融合并利用全局搜索能力較強的粒子群優(yōu)化算法和局部尋優(yōu)能力較強的K-均值聚類算法,提出了一種基于K-均值的粒子群優(yōu)化聚類算法,該算法充分優(yōu)化了K-均值聚類算法,提高了局部搜索和全局搜索的能力,加快了算法的收斂速度[17]。
K-均值聚類基本思想是:首先初始化數(shù)據(jù),隨機選擇K個聚類中心,然后按照歐氏距離緊鄰原則,根據(jù)每一個樣品與初始聚類中心的相似程度重新劃分聚類;計算該類所有元素的平均值,重新確定新的聚類中心;逐步依次迭代,直到聚類中心不再變化。假設(shè)模式樣本集為X={Xi,i=1,2,…,n},其中Xi為D維模式向量,聚類問題就是要找到一個劃分ω={ω1,ω2,…,ωm},滿足下式
并且使得總的類間離散度和式(8)達到最?。?/p>
J——各類樣本到對應聚類中心的歐氏距離的總和。
算法首先需要根據(jù)近鄰法則,確定粒子的位置編碼和各類的聚類中心;然后根據(jù)聚類劃分,按照式(8)計算類內(nèi)離散度和J;最后計算粒子的適應度函數(shù)之和fitness,當適應度越大,說明聚類效果越好。所以基于K-均值的粒子群聚類算法描述如下:
1)初始化種群。在初始化粒子群時,現(xiàn)將每一個樣品隨機對應于某一類,并作為初始劃分,計算初始粒子的位置編碼,即計算各類的聚類中心;初始化粒子的速度;計算粒子的適應度;反復進行N次,生成N個初始化的粒子群。
2)將粒子現(xiàn)在的適應度值和經(jīng)歷過的最好位置pid的適應度值進行比較,及時更新pid的信息。
3)將粒子現(xiàn)在的適應度值和種群經(jīng)歷過的最好位置pgd的適應度值進行比較,及時更新pgd的信息。
4)根據(jù)式(1)和式(2)不斷調(diào)整粒子的速度和位置。
5)對新個體進行K-均值聚類優(yōu)化,按照下面兩步進行K-均值優(yōu)化:
①根據(jù)最近鄰法則,按照粒子的聚類中心編碼,確定對應粒子的聚類劃分;
②更新粒子的適應度值,計算新的聚類中心,更新原來的粒子編碼。由于K-均值聚類具有較強的局部搜素能力,此時引入K-均值優(yōu)化后的粒子群聚類算法可以得到很好的改善,提高了算法的收斂速度和搜索效率。
6)不斷迭代,如果達到最大迭代次數(shù)或者聚類中心不再發(fā)生變化,則算法結(jié)束,否則轉(zhuǎn)到步驟2)繼續(xù)迭代。
基于K-均值粒子群優(yōu)化算法的核心代碼如下[16]:
%更新粒子的速度和位置
對表1中的數(shù)據(jù),輸出的適應度-迭代次數(shù)可以形象的表示隨著迭代次數(shù)的增加,聚類效果的變化過程如圖4所示。
圖4 基于K-均值粒子群優(yōu)化算法運行圖
實驗結(jié)果:
1)當?shù)螖?shù)為50次時(見圖4(a)),實驗結(jié)果如下:
fpclu=3 2 1 3 3 1 1 1 1 3 1 3 1 3 1 3 1 3 1 1
說明在s20×5數(shù)據(jù)中,第1、4、5、10、12、14、16、18行數(shù)據(jù)歸為一類;第2行數(shù)據(jù)歸為一類;第3、6、7、8、9、11、13、15、17、19、20行數(shù)據(jù)歸為一類。輸出的適應度值為:
kfitness=2.158006918671278e-04。
2)當?shù)螖?shù)為200次時(見圖4(b)),實驗結(jié)果如下:
fpclu=2 2 3 2 2 3 3 3 3 2 3 2 3 2 3 2 1 2 1 3
說明在s20×5數(shù)據(jù)中,第1、2、4、5、10、12、14、16、18行數(shù)據(jù)歸為一類;第3、6、7、8、9、11、13、15、20行數(shù)據(jù)歸為一類;第17、19行數(shù)據(jù)歸為一類。輸出的適應度值為:
kfitness=1.412634231439157e-04。
3)迭代次數(shù)為300次時(見圖4(c)),結(jié)果如下:
kpclu=1 1 2 1 1 2 3 3 3 1 2 3 2 1 2 1 2 1 2 3
說明在s20×5數(shù)據(jù)中,第1、2、4、5、10、14、16、18行數(shù)據(jù)歸為一類;第3、6、11、13、15、17、19行數(shù)據(jù)歸為一類;第7、8、9、12、20行數(shù)據(jù)歸為一類。輸出的適應度值為:
kfitness=5.077943793714523e-05。
從圖4可以看出,輸出的適應度-迭代次數(shù)的增加,聚類結(jié)果不斷得到優(yōu)化,但是相對于粒子群聚類,改進后的聚類算法能夠在較少的迭代次數(shù)內(nèi)完成聚類,說明基于K-均值的粒子群聚類算法更加優(yōu)秀。在前面介紹的粒子群聚類算法中(見圖3),需要經(jīng)過大約500次的迭代,聚類結(jié)果相對穩(wěn)定,才滿足程序結(jié)束條件;而在基于K-均值的粒子群聚類算法中,在較少的迭代次數(shù)內(nèi)(大約300次)就達到聚類結(jié)果的穩(wěn)定,程序結(jié)束,較好地完成了數(shù)據(jù)聚類。
闡述了粒子群算法的原理,以及在數(shù)據(jù)聚類中的應用。通過分析和論述,可以看到雖然粒子群算法出現(xiàn)的相對較晚,在短短的20年發(fā)展歷程中,展現(xiàn)出強大的生命力和研究潛力,但是算法自身存在一些缺點,比如容易陷入局部極值、對離散的問題處理不佳等原因,后期出現(xiàn)了很多對基本粒子群算法的改進。粒子群算法是一種仿生算法,自身具備的一些優(yōu)秀的進化特點使其成為智能優(yōu)化領(lǐng)域的一個研究熱點。但是由于粒子群算法的數(shù)學基礎(chǔ)相對薄弱,對這個新興的智能優(yōu)化算法的研究需要長期的不斷完善的過程。
[1] 趙志剛,常成.簡化的自適應粒子群優(yōu)化算法[J].廣西大學學報:自然科學版,2010,5(5):793-798.
[2] 段曉東,王存睿,劉向東.粒子群算法及其應用[M].沈陽:遼寧大學出版社,2007.
[3] Eberhart R C,Kennedy J.A discrete binary version of particle swarm algorithm[C]//Proceedings of the IEEE International Conference on System,Man,and Cybernetics,1997:4104-4108.
[4] Shi Y,Eberhart R C.A modified particle swarm optimizaerf[C]//Proceedings of the IEEE International Conference on Evolutionary Computation,1998:69-73.
[5] Shi Y,Eberhart R C.Fuzzy adaptive particle swarm optimization[C]//Proceedings of the Congress on Evolutionary Computation,2001:101-106.
[6] Eberhart R C,Kennedy J.Swarm intelligence[M].[S.l.]:Morgan Kaufmanns,2001.
[7] Shi Y,Eberhart R C.Parameter Selection in Particle Swarm Optirnization[C]//Proceedings of Annual Conference on Evolutionary Programming,1998:591-600.
[8] Clerc M,Kennedy J.The particle swarm optimization:Explosion,stability,and convergence in multi-dimensional complex space[J].IEEE Transaction on Evolutionary Computation,2002,6(1):58-73.
[9] Shi Y,Eberhart R C.A modified particle swarm optimization[C]//Proceedings of IEEE International Conference on Evolutionary Computation,1998:69-73.
[10] Jian Fu,Jian Yin.Weighted Rough Clustering on Categorical Data[C]//International Conference on Computer Science and Service System(CSSS),Nanjing,2011:939-944.
[11] 張莉,周偉達,焦李成.核聚類算法[J].計算機學報,2002,25(6):587-590.
[12] 王順久,倪長健.投影尋蹤動態(tài)聚類模型及其應用[J].哈爾濱工業(yè)大學學報,2009,41(1):178-181.
[13] 王娜,杜海峰,王孫安.一種基于流形距離的迭代優(yōu)化聚類算法[J].西安交通大學學報,2009,43(5):76-79.
[14] 黃太安,生佳根,徐紅洋,等.一種改進的簡化粒子群算法[J].計算機仿真,2013,2(2):327-330.
[15] 楊淑瑩.模式識別與智能計算[M].北京:電子工業(yè)出版社,2008:337-346.
[16] 程序員聯(lián)合開發(fā)網(wǎng)(programmers united develop net)[EB/OL].[2015-08-15].http://www.pudn.com.
[17] 陳小全,張繼紅.基于改進粒子群算法的聚類算法[C]//.2011年第17屆全國信息存儲技術(shù)大會(IST),2011.