粒子演算法

⑴ 粒子群演算法中的適應度

粒子群演算法，也稱粒子群優化演算法(Particle Swarm Optimization)，縮寫為 PSO， 是近年來發展起來的一種新的進化演算法(Evolutionary Algorithm - EA)。PSO 演算法屬於進化演算法的一種，和模擬退火演算法相似，它也是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，但它比遺傳演算法規則更為簡單，它沒有遺傳演算法的"交叉"(Crossover) 和"變異"(Mutation) 操作，它通過追隨當前搜索到的最優值來尋找全局最優。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。粒子群演算法是一種並行演算法。

⑵ 我還是不懂粒子群演算法中的粒子到底代表什麼

若把最優粒子理解為自變數x，問題的解就是函數y~~~而粒子就是求解過程中出現的可能解的」自變數「

⑶ 粒子群中的粒子個數和粒子長度有啥區別，哪個是演算法的解的個數謝謝

粒子個數可以理解為問題可能的解的個數，長度是根據問題需要設計的，和演算法解無關~~~另外粒子群求出的結果是適應值函數的最優值，所以不存在什麼接的個數問題，一般就一個最優解，某些問題則是有限個極值點

⑷ 粒子群演算法的參數設置

從上面的例子我們可以看到應用PSO解決優化問題的過程中有兩個重要的步驟: 問題解的編碼和適應度函數 不需要像遺傳演算法一樣是二進制編碼(或者採用針對實數的遺傳操作.例如對於問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應度函數就是f(x). 接著我們就可以利用前面的過程去尋優.這個尋優過程是一個疊代過程, 中止條件一般為設置為達到最大循環數或者最小錯誤
PSO中並沒有許多需要調節的參數,下面列出了這些參數以及經驗設置
粒子數: 一般取 20 – 40. 其實對於大部分的問題10個粒子已經足夠可以取得好的結果, 不過對於比較難的問題或者特定類別的問題, 粒子數可以取到100 或 200
粒子的長度: 這是由優化問題決定, 就是問題解的長度
粒子的范圍: 由優化問題決定,每一維可以設定不同的范圍
Vmax: 最大速度,決定粒子在一個循環中最大的移動距離,通常設定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2, x3) x1 屬於 [-10, 10], 那麼 Vmax 的大小就是 20
學習因子: c1 和 c2 通常等於 2. 不過在文獻中也有其他的取值. 但是一般 c1 等於 c2 並且范圍在0和4之間
中止條件: 最大循環數以及最小錯誤要求. 例如, 在上面的神經網路訓練例子中, 最小錯誤可以設定為1個錯誤分類, 最大循環設定為2000, 這個中止條件由具體的問題確定.
全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優化演算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優. 後者收斂速度慢一點不過很難陷入局部最優. 在實際應用中, 可以先用全局PSO找到大致的結果,再用局部PSO進行搜索. 代碼來自2008年數學建模東北賽區B題， #includestdafx.h#include<math.h>#include<time.h>#include<iostream>#include<fstream>usingnamespacestd;intc1=2;//加速因子intc2=2;//加速因子doublew=1;//慣性權重doubleWmax=1;//最大慣性權重doubleWmin=0.6;//最小慣性權重intKmax=110;//迭代次數intGdsCnt;//物資總數intconstDim=10;//粒子維數intconstPNum=50;//粒子個數intGBIndex=0;//最優粒子索引doublea=0.6;//適應度調整因子doubleb=0.5;//適應度調整因子intXup[Dim];//粒子位置上界數組intXdown[Dim]=;//粒子位置下界數組intValue[Dim];//初始急需度數組intVmax[Dim];//最大速度數組classPARTICLE;//申明粒子節點voidCheck(PARTICLE&,int);//約束函數voidInput(ifstream&);//輸入變數voidInitial();//初始化相關變數doubleGetFit(PARTICLE&);//計算適應度voidCalculateFit();//計算適應度voidBirdsFly();//粒子飛翔voidRun(ofstream&,int=2000);//運行函數classPARTICLE//微粒類{public:intX[Dim];//微粒的坐標數組intXBest[Dim];//微粒的最好位置數組intV[Dim];//粒子速度數組doubleFit;//微粒適合度doubleFitBest;//微粒最好位置適合度};PARTICLEParr[PNum];//粒子數組intmain()//主函數{ofstreamoutf(out.txt);ifstreaminf(data.txt);//關聯輸入文件inf>>GdsCnt;//輸入物資總數Input(inf);Initial();Run(outf,100);system(pause);return0;}voidCheck(PARTICLE&p,intcount)//參數:p粒子對象,count物資數量{srand((unsigned)time(NULL));intsum=0;for(inti=0;i<Dim;i++){if(p.X>Xup)p.X=Xup;elseif(p.X<Xdown)p.X=Xdown;if(p.V>Vmax)p.V=Vmax;elseif(p.V<0)p.V=0;sum+=p.X;}while(sum>count){p.X[rand()%Dim]--;sum=0;for(inti=0;i<Dim;i++){if(p.X>Xup)p.X=Xup;elseif(p.X<Xdown)p.X=Xdown;if(p.V>Vmax)p.V=Vmax;elseif(p.V<0)p.V=0;sum+=p.X;}}voidInput(ifstream&inf)//以inf為對象輸入數據{for(inti=0;i<Dim;i++)inf>>Xup;for(inti=0;i<Dim;i++)inf>>Value;}voidInitial()//初始化數據{GBIndex=0;srand((unsigned)time(NULL));//初始化隨機函數發生器for(inti=0;i<Dim;i++)Vmax=(int)((Xup-Xdown)*0.035);for(inti=0;i{for(intj=0;j<Dim;j++){Parr.X[j]=(int)(rand()/(double)RAND_MAX*(Xup[j]-Xdown[j])-Xdown[j]+0.5);Parr.XBest[j]=Parr.X[j];Parr.V[j]=(int)(rand()/(double)RAND_MAX*(Vmax[j]-Vmax[j]/2));}Parr.Fit=GetFit(Parr);Parr.FitBest=Parr.Fit;if(Parr.Fit>Parr[GBIndex].Fit)GBIndex=i;}}doubleGetFit(PARTICLE&p)//計算對象適應度{doublesum=0;for(inti=0;i<Dim;i++)for(intj=1;j<=p.X;j++)sum+=(1-(j-1)*a/(Xup-b))*Value;returnsum;}voidCalculateFit()//計算數組內各粒子的適應度{for(inti=0;i{Parr.Fit=GetFit(Parr);}}voidBirdsFly()//粒子飛行尋找最優解{srand((unsigned)time(NULL));staticintk=10;w=Wmax-k*(Wmax-Wmin)/Kmax;k++;for(inti=0;i{for(intj=0;j<Dim;j++){Parr.V[j]=(int)(w*Parr.V[j]);Parr.V[j]+=(int)(c1*rand()/(double)RAND_MAX*(Parr.XBest[j]-Parr.X[j]);Parr.V[j]+=c2*rand()/(double)RAND_MAX*(Parr[GBIndex].XBest[j]-Parr.X[j]));}}Check(Parr,GdsCnt);for(intj=0;j<Dim;j++){Parr.X[j]+=Parr.V[j];Check(Parr,GdsCnt);}CalculateFit();for(inti=0;i{if(Parr.Fit>=Parr.FitBest){Parr.FitBest=Parr.Fit;for(intj=0;j<Dim;j++)Parr.XBest[j]=Parr.X[j];}}GBIndex=0;for(inti=0;i{if(Parr.FitBest>Parr[GBIndex].FitBest&&i!=GBIndex)GBIndex=i;}}voidRun(ofstream&outf,intnum)//令粒子以規定次數num飛行{for(inti=0;i<num;i++){BirdsFly();outf<<(i+1)<<ends<for(intj=0;j<Dim;j++)outf<outf<<endl;}cout<<Done!<<endl;}

⑸ 我在研究粒子群演算法，請問什麼叫粒子的適應度值啊

粒子的適應度就是指目標函數的值。一般來說，目標函數的選擇由具體問題來決定，假如是求最大值問題，適應度就是函數的大小，適應度當然越大越好。如果是TSP問題，路徑的距離就是粒子的適應度。

⑹ 粒子群演算法中的「粒子的維數」指什麼

不是，是類比解的某一維特徵或屬性，即數據集的特徵。

⑺ 粒子群演算法中，影響每個粒子的參數有哪些

慣性參數 w,
記憶參數 c1,
共享參數 c2,
也即，粒子群演算法中速度迭代更新公式里對應的參數。

⑻ 粒子濾波演算法的具體流程是怎樣的

粒子濾波(PF: Particle Filter)演算法起源於20世紀50年代Poor Man's Monte Carlo問題的研究，但第一個具有應用性的粒子濾波演算法於1993年由Gordon等提出（「A novel Approach to nonlinear/non-Gaussian Bayesian State estimation」）。它是利用粒子集來表示概率，可以用在任何形式的狀態空間模型上。其核心思想是通過從後驗概率中抽取的隨機狀態粒子來表示其分布情況，是一種順序重要性采樣法(Sequential Importance Sampling)。

粒子濾波的應用非常廣泛，尤其是在目標跟蹤（「A probabilistic framework for matching temporal trajectories」）等視覺任務方面。粒子濾波演算法有許多不同的改進方式。針對不同的問題，PF演算法被改造以適應更好的問題。本文主要側重於目標跟蹤方面的應用。以人臉跟蹤為例，下圖展示了粒子濾波的跟蹤結果。下面介紹下粒子濾波的基本過程：初始化、概率轉移、權重重計算和重采樣四個階段。

1.初始化階段

跟蹤區域初始化。在使用粒子濾波演算法進行目標跟蹤前需要選擇要跟蹤的目標物體。這個過程可以用人工劃定方法和自動識別方法。使用人工的方法可以通過滑鼠在圖像區域標記出一個感興趣矩形；使用自動的方法就是利用自動的目標檢測技術，初步檢測出圖像中要跟蹤物體的大致位置。以人臉跟蹤為例，人工方法就是滑鼠劃定視頻第一幀中人臉的區域；自動方法就是可以使用人臉檢測演算法檢測出人臉的初始位置。

粒子初始化。對於本文人臉檢測的示例，粒子就是圖像中的矩形區域，主要由矩形中心(x,y)和寬高(w,h)四個變數表示。粒子初始化的步驟，就是在圖像中選擇指定數量的粒子（矩形），比如N=100個粒子。粒子初始化過程就是在圖像中隨機或指定方式放粒子。比如說，我們可以指定100個粒子初始狀態和跟蹤區域一致，即粒子參數和跟蹤區域的(x,y,w,h)相等。

2.狀態轉移階段

使用粒子濾波演算法來對目標進行跟蹤，即是通過前一次的先驗概率來估算出當前環境下的後驗概率密度，這個過程也是由粒子來完成的。具體來說，即根據上一幀中粒子的狀態(x,y,w,h)t-1，來估計出本幀中各個粒子的狀態(x,y,w,h)t。從上一幀圖像的粒子狀態轉變為當前幀粒子的狀態，這個變異過程就叫作轉移（transmission）。粒子濾波的轉移方程跟Kalman濾波的差不多：

上面的是狀態轉移方程，下面的為觀測方程，wk和vk是高斯雜訊。在本文示例中，xk=(x,y,w,h)t。變數x,y,w,h可以依據公式（1）分別更新。在不同的演算法中，f採用的函數也不相同。如果xk=xk-1+wk，則狀態轉移方程其實是隨機遊走過程；如果xk=Axk-1+wk，狀態轉移方程則為一階自回歸方程；如果xk=A1xk-1+A2xk-2+wk，則狀態轉移方程為二階自回歸方程。

3.權重重計算階段

轉移階段將上一幀中粒子的位置進行了轉移，得到當前幀中新的位置。但並不是所有粒子的作用都有用。也就是有些粒子並不是跟蹤區域所要所移動的位置。因此，在此階段，粒子濾波演算法將對每個粒子進行打分，將得分較低的粒子刪除，將得分多的粒子生成更多的粒子（重采樣過程完成）。具體打分的方法根據不同的需求會不同，例如人臉跟蹤方法中使用距離作為衡量的標准。將每個粒子與跟蹤區域進行相似度計算（在這里，分別提取粒子和跟蹤區域的視覺特徵進行計算，比如顏色直方圖），使用相似度作為相應粒子的權重。每一個粒子都需要計算其權重，並且需要將其歸一化。該階段其實也是後驗概率進行更新的過程。

4.重采樣階段

粒子濾波演算法會淘汰權值低的粒子，讓權值高的粒子來產生出更多的粒子，這就使得演算法朝著權值高的地方收斂。假設有100個粒子，1號粒子的權重為0.02而2號粒子的權重為0.003。於是在重采樣階段，1號粒子生孩子的指標是0.02×100=2，2號粒子的指標是0.003×100=0.3，可以發現，1號粒子除了剛產生的粒子外還要再額外的產生一個粒子，而2號粒子就被鏟除了。如此，最後得到的100個粒子即為所求，然後取個加權平均就得到了目標的狀態值。

⑼ 粒子群演算法和離散粒子群演算法有什麼不同主要差別體現在哪裡

一般就是在跟新粒子位置後，對粒子進行離散點處理。
比如：
你的粒子的離散點是0到9的整數。
那麼對每個粒子更新位置後，比如是在（0,1）范圍內的隨機數。那麼就（0，0.1）范圍令其值為0；（0.1,0.2）范圍令其值為1；............（0.9.1）范圍令其值為9。
當然初始位置值也需要這樣處理。

⑽ 粒子群演算法的優缺點

優點：PSO同遺傳演算法類似，是一種基於迭代的優化演算法。系統初始化為一組隨機解，通過迭代搜尋最優值。同遺傳演算法比較，PSO的優勢在於簡單容易實現，並且沒有許多參數需要調整。

缺點：在某些問題上性能並不是特別好。網路權重的編碼而且遺傳運算元的選擇有時比較麻煩。最近已經有一些利用PSO來代替反向傳播演算法來訓練神經網路的論文。

(10)粒子演算法擴展閱讀：

注意事項：

基礎粒子群演算法步驟較為簡單。粒子群優化演算法是由一組粒子在搜索空間中運動，受其自身的最佳過去位置pbest和整個群或近鄰的最佳過去位置gbest的影響。

對於有些改進演算法，在速度更新公式最後一項會加入一個隨機項，來平衡收斂速度與避免早熟。並且根據位置更新公式的特點，粒子群演算法更適合求解連續優化問題。