模式識(shí)別與智能計(jì)算

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

粒子群算法的概述粒子群算法(ParticleSwarmOptimization,PS)是一種有效的全局尋優(yōu)算法，最早由美國(guó)的Kennedy和Cberhart于1995年提出。它是基于群體智能理論的優(yōu)化算法，通過(guò)群休中粒子間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。與傳統(tǒng)的進(jìn)化算法相比，粒子群算法保留了基于種樣的全局搜索策略，但是其采用的速度一位移模型，操作簡(jiǎn)單，避免了復(fù)雜的遺傳操作，它特有的記憶使其可以動(dòng)態(tài)跟蹤當(dāng)前的搜索情況調(diào)整其搜索策略。由于每代種群中的解具有“自我”學(xué)習(xí)提高和向“他人”學(xué)習(xí)的雙重優(yōu)點(diǎn)，從而能在較少的迭代次數(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粒子群算法的基本原理粒子群算法的思想源于對(duì)鳥(niǎo)群覓食行為的研究，鳥(niǎo)群通過(guò)集體的信息共享使群體找到最優(yōu)的目的地。設(shè)想這樣一個(gè)場(chǎng)景：鳥(niǎo)群在森林中隨機(jī)搜索食物，它們想要找到食物量最多的位置。但是所有的鳥(niǎo)都不知道食物具體在哪個(gè)位置，只能感受到食物大概在哪個(gè)方向。每只鳥(niǎo)沿著自己判定的方向進(jìn)行搜索，并在搜索的過(guò)程中記錄自己曾經(jīng)找到過(guò)食物且量最多的位置，同時(shí)所有的鳥(niǎo)都共享自己每一次發(fā)現(xiàn)食物的位置以及食物的量，這樣鳥(niǎo)群就知道當(dāng)前在哪個(gè)位置食物的量最多。在搜索的過(guò)程中每只鳥(niǎo)都會(huì)根據(jù)自己記憶中食物量最多的位置和當(dāng)前鳥(niǎo)群記錄的食物量最多的位置調(diào)整自己接下來(lái)搜索的方向。鳥(niǎo)群經(jīng)過(guò)一段時(shí)間的搜索后就可以找到森林中哪個(gè)位置的食物量最多（全局最優(yōu)解）。12.1.1鳥(niǎo)類(lèi)覓食鳥(niǎo)群覓食粒子群算法鳥(niǎo)粒子森林求解空間食物的量目標(biāo)函數(shù)值每只鳥(niǎo)所處的位置空間中的一個(gè)解（粒子位置）食物量最多的位置全局最優(yōu)解12.1.2初始粒子群代碼實(shí)現(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在生成初始粒子群部分，首先生成一組包含多個(gè)粒子的粒子群，其中每個(gè)粒子包含多個(gè)特征，即每個(gè)特征表示一個(gè)樣本的類(lèi)別。ptDitrib是一個(gè)1xparticleNum的矩陣，表示每個(gè)粒子的初始類(lèi)別分布，可以根據(jù)實(shí)際問(wèn)題進(jìn)行設(shè)置。然后根據(jù)每個(gè)粒子的類(lèi)別分布，計(jì)算每個(gè)類(lèi)別的中心點(diǎn)m_center，用于初始化粒子的位置。在初始化參數(shù)部分，設(shè)置了慣性因子w的最大值和最小值，以及加速因子h1和h2的值，用于控制粒子的速度和位置更新。iterNum表示算法的迭代次數(shù)，用于控制算法的收斂性。12.1.3粒子群算法的描述

12.1.4加權(quán)求和示意圖粒子下一步迭代的移動(dòng)方向=慣性方向+個(gè)體最優(yōu)方向+群體最優(yōu)方向12.1.5粒子移動(dòng)方向的決定因素12.1.6速度和位置更新代碼實(shí)現(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等在對(duì)鳥(niǎo)群覓食的觀察過(guò)程巾發(fā)現(xiàn)，每只鳥(niǎo)并不總是能看到鳥(niǎo)群中其他所有鳥(niǎo)的位置和運(yùn)動(dòng)方向，而往往只是看到相鄰的鳥(niǎo)的位置和運(yùn)動(dòng)方向。因此提出了兩種粒子群算法模式：全局模式(globalversionPS)和局部模式(localversionPSO）.12.2.1全局模式與局部模式對(duì)比

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

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

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

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

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

12.3.5粒子群算法求解聚類(lèi)問(wèn)題

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

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

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

%重新計(jì)算聚類(lèi)中心

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)前粒子的位置信息重新對(duì)樣本進(jìn)行聚類(lèi)，并計(jì)算新的聚類(lèi)中心。在最近鄰聚類(lèi)部分，首先遍歷每個(gè)粒子和每個(gè)樣本點(diǎn)。對(duì)于每個(gè)樣本點(diǎn)，遍歷當(dāng)前粒子的每個(gè)聚類(lèi)