(完整)粒子群算法與遺傳算法的比較粒子群算法介紹優(yōu)化問題是工業(yè)設計中經常遇到的問題，許多問題最后都可以歸結為優(yōu)化問題.為了解決各種各樣的優(yōu)化問題，人們提出了許多優(yōu)化算法，比較著名的有爬山法、遺傳算法等.優(yōu)化問題有兩個主要問題:一是要求尋找全局最小點，二是要求有較高的收斂速度。爬山法精度較高，但是易于陷入局部極小。遺傳算法屬于進化算法(EvolutionaryAlgorithms)的一種，它通過模仿自然界的選擇與遺傳的機理來尋找最優(yōu)解.遺傳算法有三個基本算子:選擇、交叉和變異.但是遺傳算法的編程實現比較復雜，首先需要對問題進行編碼，找到最優(yōu)解之后還需要對問題進行解碼，另外三個算子的實現也有許多參數，如交叉率和變異率,并且這些參數的選擇嚴重影響解的品質，而目前這些參數的選擇大部分是依靠經驗.1995年Eberhart博士和kennedy博士提出了一種新的算法;粒子群優(yōu)化(ParticleSwarmOptimizationPSO)算法。這種算法以其實現容易、精度高、收斂快等優(yōu)點引起了學術界的重視，并且在解決實際問題中展示了其優(yōu)越性。粒子群優(yōu)化(ParticleSwarmOptimization-PSO)算法是近年來發(fā)展起來的一種新的進化算法(EvolutionaryAlgorithm-EA)。PSO算法屬于進化算法的一種，和遺傳算法相似,它也是從隨機解出發(fā),通過迭代尋找最優(yōu)解,它也是通過適應度來評價解的品質.但是它比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的交叉”(Crossover)和變異(Mutation)操作。它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。.引言粒子群優(yōu)化算法(PSO)是一種進化計算技術(evolutionarycomputation),由Eberhart博士和kennedy博士提出。源于對鳥群捕食的行為研究。PSO同遺傳算法類似，是一種基于迭代的優(yōu)化算法。系統(tǒng)初始化為一組隨機解，通過迭代搜尋最優(yōu)值。但是它沒有遺傳算法用的交叉(crossover)以及變異(mutation)，而是粒子在解空間追隨最優(yōu)的粒子進行搜索.同遺傳算法比較，PSO的優(yōu)勢在于簡單容易實現并且沒有許多參數需要調整。目前已廣泛應用于函數優(yōu)化,神經網絡訓練，模糊系統(tǒng)控制以及其他遺傳算法的應用領域.背景：人工生命"人工生命”是來研究具有某些生命基本特征的人工系統(tǒng)。人工生命包括兩方面的內容：.研究如何利用計算技術研究生物現象.研究如何利用生物技術研究計算問題我們現在關注的是第二部分的內容?，F在已經有很多源于生物現象的計算技巧.例如，人工神經網絡是簡化的大腦模型.遺傳算法是模擬基因進化過程的.現在我們討論另一種生物系統(tǒng)一社會系統(tǒng).更確切的是，在由簡單個體組成的群落與環(huán)境以及個體之間的互動行為。也可稱做"群智能"卜325intelligence).這些模擬系統(tǒng)利用局部信息從而可能產生不可預測的群體行為例如floys和boids，他們都用來模擬魚群和鳥群的運動規(guī)律，主要用于計算機視覺和計算機輔助設計.在計算智能(computationalintelligence)領域有兩種基于群智能的算法.蟻群算法(antcolonyoptimization)和粒子群算法(particleswarmoptimization)o前者是對螞蟻群落食物采集過程的模擬.已經成功運用在很多離散優(yōu)化問題上。粒子群優(yōu)化算法(PSO)也是起源對簡單社會系統(tǒng)的模擬。最初設想是模擬鳥群覓食的過程.但后來發(fā)現PSO是一種很好的優(yōu)化工具..算法介紹如前所述，「50模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物.在這個區(qū)域里只有一塊食物.所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域.PSO從這種模型中得到啟示并用于解決優(yōu)化問題.PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥.我們稱之為“粒子”.所有的粒子都有一個由被優(yōu)化的函數決定的適應值(fitnessvalue),每個粒子還有一個速度決定他們飛翔的方向和距離.然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩(完整)粒子群算法與遺傳算法的比較個"極值”來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居,那么在所有鄰居中的極值就是局部極值。在找到這兩個最優(yōu)值時，粒子根據如下的公式來更新自己的速度和新的位置：v[]=w*v[]+cl*rand()*(pbest[]—present[])+c2*rand()*(gbest[]—present口)(a)present口=persent[]+v□(b)v口是粒子的速度，w是慣性權重，persent[]是當前粒子的位置.pbest口andgbest[]如前定義rand()是介于(0,1)之間的隨機數。c1,c2是學習因子。通常cl=c2=2。程序的偽代碼如下ForeachparticleInitializeparticleENDDoForeachparticleCalculatefitnessvalueIfthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistorysetcurrentvalueasthenewpBestEndChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBestForeachparticleCalculateparticlevelocityaccordingequation(a)Updateparticlepositionaccordingequation(b)EndWhilemaximumiterationsorminimumerrorcriteriaisnotattained在每一維粒子的速度都會被限制在一個最大速度Vmax,如果某一維更新后的速度超過用戶設定的Vmax,那么這一維的速度就被限定為Vmax4。遺傳算法和PSO的比較大多數演化計算技術都是用同樣的過程：1。種群隨機初始化.對種群內的每一個個體計算適應值(fitnessvalue).適應值與最優(yōu)解的距離直接有關.種群根據適應值進行復制4。如果終止條件滿足的話，就停止，否則轉步驟2從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機初始化種群，而且都使用適應值來評價系統(tǒng)，而且都根據適應值來進行一定的隨機搜索。兩個系統(tǒng)都不是保證一定找到最優(yōu)解。但是，PSO沒有遺傳操作如交叉(crossover)和變異(mutation)。而是根據自己的速度來決定搜索。粒子還有一個重要的特點，就是有記憶.與遺傳算法比較，PSO的信息共享機制是很不同的。在遺傳算法中，染色體(chromosomes)互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動。在PSO中，只有gBest(orlBest)給出信息給其他的粒子，這是單向的信息流動.整個搜索更新過程是跟隨當前最優(yōu)解的過程。與遺傳算法比較，在大多數的情況下，所有的粒子可能更快的收斂于最優(yōu)解5。人工神經網絡和PSO人工神經網絡(ANN)是模擬大腦分析過程的簡單數學模型，反向轉播算法是最流行的神經網絡訓練算法。進來也有很多研究開始利用演化計算(evolutionarycomputation)技術來研究人工神經網絡的各個方面。演化計算可以用來研究神經網絡的三個方面：網絡連接權重，網絡結構(網絡拓撲結構，傳遞函數)，網絡學習算法。(完整)粒子群算法與遺傳算法的比較不過大多數這方面的工作都集中在網絡連接權重，和網絡拓撲結構上。在GA中，網絡權重和/或拓撲結構一般編碼為染色體(Chromosome),適應函數(456$$function)的選擇一般根據研究目的確定。例如在分類問題中，錯誤分類的比率可以用來作為適應值演化計算的優(yōu)勢在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導的節(jié)點傳遞函數或者沒有梯度信息存在。但是缺點在于：在某些問題上性能并不是特別好。2。網絡權重的編碼而且遺傳算子的選擇有時比較麻煩最近已經有一些利用PSO來代替反向傳播算法來訓練神經網絡的論文。研究表明PSO是一種很有潛力的神經網絡算法。PSO速度比較快而且可以得到比較好的結果。而且還沒有遺傳算法碰到的問題這里用一個簡單的例子說明PSO訓練神經網絡的過程。這個例子使用分類問題的基準函數(Benchmarkfunction)出6數據集。(Iris是一種鳶尾屬植物)在數據記錄中，每組數據包含Iris花的四種屬性：萼片長度，萼片寬度,花瓣長度，和花瓣寬度，三種不同的花各有50組數據。這樣總共有150組數據或模式。我們用3層的神經網絡來做分類.現在有四個輸入和三個輸出。所以神經網絡的輸入層有4個節(jié)點，輸出層有3個節(jié)點我們也可以動態(tài)調節(jié)隱含層節(jié)點的數目，不過這里我們假定隱含層有6個節(jié)點。我們也可以訓練神經網絡中其他的參數。不過這里我們只是來確定網絡權重。粒子就表示神經網絡的一組權重，應該是4*6+6*3=42個參數。權重的范圍設定為[一100，100](這只是一個例子，在實際情況中可能需要試驗調整).在完成編碼以后，我們需要確定適應函數。對于分類問題，我們把所有的數據送入神經網絡，網絡的權重有粒子的參數決定。然后記錄所有的錯誤分類的數目作為那個粒子的適應值.現在我們就利用PSO來訓練神經網絡來獲得盡可能低的錯誤分類數目?！?。本身并沒有很多的參數需要調整.所以在實驗中只需要調整隱含層的節(jié)點數目和權重的范圍以取得較好的分類效果。6。PSO的參數設置從上面的例子我們可以看到應用PSO解決優(yōu)化問題的過程中有兩個重要的步驟：問題解的編碼和適應度函數PSO的一個優(yōu)勢就是采用實數編碼，不需要像遺傳算法一樣是二進制編碼(或者采用針對實數的遺傳操作。例如對于問題f(x)=x/2+x2八2+x3八2求解，粒子可以直接編碼為(x1,x2,x3),而適應度函數就是f(x)。接著我們就可以利用前面的過程去尋優(yōu)。這個尋優(yōu)過程是一個疊代過程，中止條件一般為設置為達到最大循環(huán)數或者最小錯誤PSO中并沒有許多需要調節(jié)的參數，下面列出了這些參數以及經驗設置粒子數：一般取20—40.其實對于大部分的問題10個粒子已經足夠可以取得好的結果，不過對于比較難的問題或者特定類別的問題，粒子數可以取到100或200粒子的長度：這是由優(yōu)化問題決定，就是問題解的長度粒子的范圍：由優(yōu)化問題決定，每一維可是設定不同的范圍Vmax:最大速度，決定粒子在一個循環(huán)中最大的移動距離，通常設定為粒子的范圍寬度,例如上面的例子里，粒子(x1,x2,x3)x1屬于[-10,10],那么Vmax的大小就是20學習因子：c1和c2通常等于2。不過在文獻中也有其他的取值。但是一般c1等于c2并且范圍在0和4之間中止條件：最大循環(huán)數以及最小錯誤要求。例如，在上面的神經網絡訓練例子中，最小錯誤可以設定為1個錯誤分類，最大循環(huán)設定為2000,這個中止條件由具體的問題確定.全局PSO和局部PSO：我們介紹了兩種版本的粒子群優(yōu)化算法：全局版和局部版.前者速度快不過有時會陷入局部最優(yōu)。后者收斂速度慢一點不過很難陷入局部最優(yōu).在實際應用中，可以先用全局PSO找到大致的結果，再有局部PSO進行搜索.另外的一個參數是慣性權重，Shi和Eberhart指出6modifiedparticleswarmoptimizer,1998):當Vmax很小時(對schaffer的f6函數”印2乂<=2),使用接近于1的慣性權重;當Vmax不是很小時(對schaffer的f6函數，Vmax>=3)，使用權重w=0。8較好.如果沒有Vmax的信息，使用0。8作為權重也是一種很好的選擇。另外，對于使用時變的權重，結果不清楚，但是預計結果應比較好.附上'一■個C++實現的C++代碼：代碼來自2008年數學建模東北賽區(qū)B題，原題描述http://www.ivanblogocn/post/18.html（完整）粒子群算法與遺傳算法的比較（完整）粒子群算法與遺傳算法的比較（完整）粒子群算法與遺傳算法的比較（完整）粒子群算法與遺傳算法的比較#include"stdafx。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；//最優(yōu)粒子索引doublea=0。6;〃適應度調整因子doubleb=0。5;〃適應度調整因子intXup[Dim];〃粒子位置上界數組intXdown[Dim]=;〃粒子位置下界數組intValue[Dim]；//初始急需度數組intVmax[Dim];〃最大速度數組classPARTICLE;//申明粒子節(jié)點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("dataotxt”);〃關聯(lián)輸入文件inf>〉GdsCnt;//輸入物資總數Input(inf);Initial();Run(outf,100);system("pause”)；return0;}count物資數量voidCheck(PARTICLE&p,intcount)〃參數卬粒子對象，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){X=Xup；}elseif(p.X<Xdown){X=Xdown；}if(p。V>Vmax){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));//初始化隨機函數發(fā)生器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(Par1;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()//粒子飛行尋找最優(yōu)解{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])+(int)(c1*rand()/(double)RAND_MAX*(Parr。XBest[j]-Parr.X[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=ParrFit;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)〃令粒子以規(guī)定次數num飛行{for(inti=0；i<num;i++){BirdsFly()；outf<〈(i+1)〈〈ends<for(intj=0;j<Dim；j++){outf<}outf<<endl;}cout〈〈”Done!”<〈endl；}既然有個目標函數，那么多目標可以在目標函數那里表示，我最近也在做這個粒子群算法，下面是我的vc++6.0代碼，改造了一下基本粒子群，求路徑的。。#include〈math.h>#include<time。h〉#include〈iostream〉usingnamespacestd；doublec1=0。7；doublec2=0.2;doublew=1。0;doubleWmax=1。0；doubleWmin=0.6；intKmax=50；intconstDim=7；intconstPNum=4;intFB=200；intFC=5；intGBIndex=0;classPARTICLE；voidInitial。；voidUpdate(int*x,int*v);voidGetDifferent(int*p1,int*p2,int*v);intGetFit(PARTICLE&);voidCalculateFit();voidBirdsFly();voidRun(intnum);doubleGetRandm();intA[7][7]={{0,2,1000,4,1000,1000,1000},{2,0,3,1000,1000,1000,1000},

{1000,3,0,1000,3,6,1000},{4,1000,1000,0,5,2,1000},{1000,1000,1000,5,0,1,2},{1000,1000,6,2,1,0,4},{1000,1000,1000,1000,2,4,0}｝；intB[7][7]={{0,2,1000,4,1000,1000,1000},{2,0,3,1000,1000,1000,1000},{1000,3,0,1000,3,6,1000},{4,1000,1000,0,5,2,1000},{1000,1000,1000,5,0,1,2),{1000,1000,6,2,1,0,4),{1000,1000,1000,1000,2,4,0}｝；intC[7][7]={{1000,20,1000,10,1000,1000,1000},{2C1,1000,5,1000,1000,1000,1000},{1,7,1000,1000,7,36,1000},{40,1000,2,1000,6,52,1000)1{3,1000,1000,9,1000,11,12},{20,1000,6,6,8,1000,14},{1000,1000,1000,1000,}；8,24,1000}intFirst[7]={0,1,2,3,4,5,6};intLast[7]={0,1,2,3,4,5,6};inthp1[7]={0,0,0,0,0,0,0};inthp2[7]={0,0,0,0,0,0,0};//ICA￡AaclassPARTICLE{public:intX[Dim]；intXBest[Dim]；intV[Dim]；doubleFit;doubleFitBest;}；PARTICLEPt[PNum]；intInp[4][7]={{0,6,2,4,1,3,5},{0,1,2,4,3,5,6},{0,3,6,5,4,2,1},{0,3,4,6,5,2,1}}；doubleGetRandm(){return(double)(rand()/(double)RAND_MAX)；}//3oE%?Ey%YvoidInitial(){GBIndex=0；for(inti=0;i<PNum;i++){Pt[i].X[0]=Inp[i][0];Pt[i].XBest[0]=Pt[i]。X[0]；Pt[i].V[0]=0;for(intj=1;j〈Dim；j++){Pt[i].X[j]=Inp[i][j];Pt[i].XBest[j]=Pt[i]。X[j]；//Pt[i].V[j]=0；Pt[i]。V[j]=(int)(10*GetRandm()+1)/1。5；//cout〈〈Pt[i].V[j]〈<ends;}Pt[i]。Fit=GetFit(Pt[i]);Pt[i]。FitBest=Pt[i].Fit;if(Pt[i].FitBest〈二Pt[GBIndex].FitBest){GBIndex二i;}}cout〈〈"GBIndex:"<<GBIndex〈〈endl；}intGetFit(PARTICLE&p){intsum=0；intfb=0;intfc=0；inti=0;do{sum+=A[p.X[i]][p.X[i+1]];fb+=B[p.X[i]][p.X[i+1]];if(C[p.X[i]][p.X[i+1]]<FC)fc=1000;//'0±HD。正i++;}while(i〈6&&p。X[i]!=6)；if(fb〉FB){fb=1000;}elsefb=0;sum+二(fb+fc);returnsum;}voidCalculateFit(){for(inti=0;i〈PNum;i++){Pt[i].Fit=GetFit(Pt[i])；}}//A￡XO?EDDN°00Xi0A^avoidBirdsFly(){staticintk=0;w=Wmax—k*(Wmax—Wmin)/Kmax;k++;cout<<”|iU"〈〈k〈<”，1口0，u￡°”<〈endl;for(inti=0;i〈PNum;i++){if(w>GetRandm()){Update(Last,Pt[i]。V);}for(intj=0;j<Dim;j++)Pt[i]。V[j]=O;if(c1〉GetRandm