模式識別與智能計算

楊淑瑩天津理工大學(xué)計算機科學(xué)與工程學(xué)院第十二章粒子群算法聚類分析12.1粒子群算法的基本原理12.2全局模式和局部模式12.3粒子群算法的實現(xiàn)方法與步驟

粒子群算法的概述粒子群算法(ParticleSwarmOptimization,PS)是一種有效的全局尋優(yōu)算法，最早由美國的Kennedy和Cberhart于1995年提出。它是基于群體智能理論的優(yōu)化算法，通過群休中粒子間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。與傳統(tǒng)的進化算法相比，粒子群算法保留了基于種樣的全局搜索策略，但是其采用的速度一位移模型，操作簡單，避免了復(fù)雜的遺傳操作，它特有的記憶使其可以動態(tài)跟蹤當(dāng)前的搜索情況調(diào)整其搜索策略。由于每代種群中的解具有“自我”學(xué)習(xí)提高和向“他人”學(xué)習(xí)的雙重優(yōu)點，從而能在較少的迭代次數(shù)內(nèi)找到最優(yōu)解。目前已廣泛應(yīng)用于函數(shù)優(yōu)化、數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)訓(xùn)練等應(yīng)用領(lǐng)域。12.1粒子群算法的基本原理粒子群算法的思想源于對鳥群覓食行為的研究，鳥群通過集體的信息共享使群體找到最優(yōu)的目的地。設(shè)想這樣一個場景：鳥群在森林中隨機搜索食物，它們想要找到食物量最多的位置。但是所有的鳥都不知道食物具體在哪個位置，只能感受到食物大概在哪個方向。每只鳥沿著自己判定的方向進行搜索，并在搜索的過程中記錄自己曾經(jīng)找到過食物且量最多的位置，同時所有的鳥都共享自己每一次發(fā)現(xiàn)食物的位置以及食物的量，這樣鳥群就知道當(dāng)前在哪個位置食物的量最多。在搜索的過程中每只鳥都會根據(jù)自己記憶中食物量最多的位置和當(dāng)前鳥群記錄的食物量最多的位置調(diào)整自己接下來搜索的方向。鳥群經(jīng)過一段時間的搜索后就可以找到森林中哪個位置的食物量最多（全局最優(yōu)解）。12.1.1鳥類覓食鳥群覓食粒子群算法鳥粒子森林求解空間食物的量目標(biāo)函數(shù)值每只鳥所處的位置空間中的一個解（粒子位置）食物量最多的位置全局最優(yōu)解12.1.2初始粒子群代碼實現(xiàn)%生產(chǎn)初始粒子群

fori=1:particleNum

forj=1:patternNum

m_pattern(j).category=ptDitrib(i,j);

end

forj=1:centerNum

m_center(j)=CalCenter(m_center(j),m_pattern,patternNum);

end

Particle(i).location=m_center;

end

%初始化參數(shù)

w_max=1;

w_min=0;

h1=2;

h2=2;

foriter=1:iterNum在生成初始粒子群部分，首先生成一組包含多個粒子的粒子群，其中每個粒子包含多個特征，即每個特征表示一個樣本的類別。ptDitrib是一個1xparticleNum的矩陣，表示每個粒子的初始類別分布，可以根據(jù)實際問題進行設(shè)置。然后根據(jù)每個粒子的類別分布，計算每個類別的中心點m_center，用于初始化粒子的位置。在初始化參數(shù)部分，設(shè)置了慣性因子w的最大值和最小值，以及加速因子h1和h2的值，用于控制粒子的速度和位置更新。iterNum表示算法的迭代次數(shù)，用于控制算法的收斂性。12.1.3粒子群算法的描述

12.1.4加權(quán)求和示意圖粒子下一步迭代的移動方向=慣性方向+個體最優(yōu)方向+群體最優(yōu)方向12.1.5粒子移動方向的決定因素12.1.6速度和位置更新代碼實現(xiàn)%更新粒子速度，位置

fori=1:particleNum

forj=1:centerNum

Particle(i).velocity(j).feature=

w*Particle(i).velocity(j).feature+h1*rand(Nwidth,Nwidth).*

(P_id(i).location(j).feature-Particle(i).location(j).feature)

+h2*rand(Nwidth,Nwidth).*(P_gd.location(j).feature

-Particle(i).location(j).feature);

Particle(i).location(j).feature=Particle(i).location(j).feature

+Particle(i).velocity(j).feature;

end

end

12.1.7粒子群算法的基本流程12.2全局模式與局部模式Kennedy等在對鳥群覓食的觀察過程巾發(fā)現(xiàn)，每只鳥并不總是能看到鳥群中其他所有鳥的位置和運動方向，而往往只是看到相鄰的鳥的位置和運動方向。因此提出了兩種粒子群算法模式：全局模式(globalversionPS)和局部模式(localversionPSO）.12.2.1全局模式與局部模式對比

速度更新公式：全局模式具有較快的收斂速度，但是魯棒性較差。相反，局部模式具有較高的魯棒性而收斂速度相對較慢，因此在運用粒子群算法解決不同的優(yōu)化問題時，應(yīng)針對具體情況采用相應(yīng)的模式。

12.2.2參數(shù)選取12.2.3參數(shù)選取規(guī)則

①粒子群算法和其他進化算法都基于“種群”概念，用于表示一組解空間中的個體集合。它們都隨機初始化種群，使用適應(yīng)度值來評價個體，而且都根據(jù)適應(yīng)度值來進行一定的隨機搜索，并且不能保證一定能找到最優(yōu)解。②種群進化過程中通過子代與父代競爭，若子代具有更好的適應(yīng)度值，則子代將替換父代，因此都具有一定的選擇機制。③算法都具有并行性，即搜索過程是從一個解集合開始的，而不是從單個個體開始的，不容易陷入局部極小值。并且這種并行性易于在并行計算機上實現(xiàn)，提高算法的性能和效率。12.2.4粒子群算法與其他進化算法的相同點①粒子群算法在進化過程中同時記憶位置和速度信息，而遺傳算法和蟻群算法通常只記憶位置信息。②粒子群算法的信息通信機制與其他進化算法不同。遺傳算法中染色體互相通過交叉等操作進行通信，蟻群算法中每只螞蟻以蟻群全體構(gòu)成的信息素軌跡作為通信機制，因此整個種群比較均勻地向最優(yōu)區(qū)域移動。在全局模式的粒子群算法中，只有全局最優(yōu)粒子提供信息給其他的粒子，整個搜索更新過程是跟隨當(dāng)前最優(yōu)解的過程，因此所有的粒子很可能更快地收斂于最優(yōu)解。12.2.5粒子群算法與其他進化算法的不同點12.3粒子群算法的實現(xiàn)方法與步驟

理論基礎(chǔ)：是第j個聚類的中心，為樣品到對應(yīng)聚類中心距離，聚類準(zhǔn)則函數(shù)j即為各類樣品到對應(yīng)聚類中心距離的總和。12.3.1理論基礎(chǔ)

12.3.2粒子群算法求解聚類問題在粒子群算法求解聚類問題中，每個粒子作為一個可行解組成粒子群（即解集）。根據(jù)解的含義不同，通?？梢苑譃閮煞N方法：一種是以聚類結(jié)果為解；一種是以聚類中心集合為解。采用的是基于聚類中心集合作為粒子對應(yīng)解，也就是每個粒子的位置是由M個聚類中心組成，M為已知的聚類數(shù)目。一個具有M個聚類中心，樣品向量維數(shù)為n的聚類問題中，每個粒子i由三部分組成，即粒子位置、速度和適應(yīng)度值。粒子結(jié)構(gòu)i表示為：12.3.3粒子群算法求解聚類問題粒子的位置編碼結(jié)構(gòu)表示為：每個粒子還有一個速度：粒子適應(yīng)度值Particle.fitness為一實數(shù)，表示粒子的適應(yīng)度，可以采用以下方法計算其適應(yīng)度。①按照最近鄰法式確定該粒子的聚類劃分。②根據(jù)聚類劃分，重新計算聚類中心，按照計算總的類內(nèi)離散度J。③粒子的適應(yīng)度可表示為式：J為總的類內(nèi)離散度和，k為常數(shù)，根據(jù)具體情況而定。即粒子所代表的聚類劃分的總類間離散度越小，粒子的適應(yīng)度越大。12.3.4編碼格式粒子編碼

12.3.5粒子群算法求解聚類問題

根據(jù)左邊二式，可以得到粒子i的速度和位置更新公式：12.3.6實現(xiàn)步驟12.3.7ω的取值

12.3.8粒子適應(yīng)度代碼實現(xiàn)%計算粒子適應(yīng)度

fori=1:particleNum

temp=0;

forj=1:patternNum

temp=temp+GetDistance(m_pattern(j),Particle(i).location(ptDitrib(i,j)),disType);

end

if(temp==0)%最優(yōu)解，直接退出

iter=iterNum+1;

break;

end

Particle(i).fitness=1/temp;

end

if(iter>iterNum)

break;

end

w=w_max-iter*(w_max-w_min)/iterNum;%更新權(quán)重系數(shù)

fori=1:particleNum%更新P_id,P_gd

if(Particle(i).fitness>P_id(i).fitness)

P_id(i).fitness=Particle(i).fitness;

P_id(i).location=Particle(i).location;

P_id(i).velocity=Particle(i).velocity;

if(Particle(i).fitness>P_gd(i).fitness)

P_gd(i).fitness=Particle(i).fitness;

P_gd(i).location=Particle(i).location;

P_gd(i).velocity=Particle(i).velocity;

P_gd.string=ptDitrib(i,:);

end

end

end首先遍歷每個粒子，并計算該粒子的適應(yīng)度。適應(yīng)度的計算是通過計算每個樣本點到該粒子所屬的類別中心點的距離來實現(xiàn)的。如果該粒子的適應(yīng)度達到最優(yōu)解，則直接退出迭代過程。在更新部分，首先根據(jù)當(dāng)前迭代次數(shù)更新慣性因子w的值。然后，使用循環(huán)語句遍歷每個粒子，根據(jù)當(dāng)前適應(yīng)度更新個體最優(yōu)解P_id和全局最優(yōu)解P_gd，并記錄最優(yōu)解的字符串ptDitrib。具體來說，如果該粒子的適應(yīng)度大于個體最優(yōu)解的適應(yīng)度，則更新個體最優(yōu)解；如果該粒子的適應(yīng)度大于全局最優(yōu)解的適應(yīng)度，則更新全局最優(yōu)解。最后，將最優(yōu)解的字符串ptDitrib保存到P_gd中。這樣，隨著粒子群迭代的進行，不斷計算粒子的適應(yīng)度并更新最優(yōu)解，最終找到最佳解。12.3.9聚類中心代碼實現(xiàn)%最近鄰聚類

fori=1:particleNum

forj=1:patternNum

min=inf;

fork=1:centerNum

tempDis=GetDistance(m_pattern(j),Particle(i).location(k),disType);

if(tempDis<min)

min=tempDis;

m_pattern(j).category=k;

ptDitrib(i,j)=k;

end

end

end

%重新計算聚類中心

forj=1:centerNum

Particle(i).location(j)=CalCenter(Particle(i).location(j),m_pattern,patternNum);

end

end

fori=1:patternNum

m_pattern(i).category=P_gd.string(1,i);

end根據(jù)當(dāng)前粒子的位置信息重新對樣本進行聚類，并計算新的聚類中心。在最近鄰聚類部分，首先遍歷每個粒子和每個樣本點。對于每個樣本點，遍歷當(dāng)前粒子的每個聚類