粒子群優(yōu)化算法

1、什么是粒子群優(yōu)化算法粒子群優(yōu)化算法(Particle Swarm optimization,PSO)又翻譯為粒子群算法、微粒群算法、或 微粒群優(yōu)化算法。是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機搜索算法。通 常認為它是群集智能(Swarm intelligence, SI)的一種。它可以被納入多主體優(yōu)化系統(tǒng) (Multiagent Optimization System, MAOS).是由 Eberhart 博士和 kennedy 博士發(fā)明。PSO模擬鳥群的捕食行為。一群鳥在隨機搜索食物，在這個區(qū)域里只有一塊食物。所有的 鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠

2、那么找到食物的最優(yōu)策略是 什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的解都是搜索空 間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值 (fitnessvalue)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最 優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解)，然后通過疊代找到最優(yōu)解，在每一次疊代中，粒子通 過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解叫做個體極值 pBest，另一個極值是整個種群目前找到的最優(yōu)解，這個極值

3、是全局極值gBest。另外也可以不 用整個種群而只是用其中一部分最優(yōu)粒子的鄰居，那么在所有鄰居中的極值就是局部極值。編輯PSO算法介紹1如前所述，PSO模擬鳥群的捕食行為。設(shè)想這樣一個場景：一群鳥在隨機搜索食物。在這 個區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多 遠那么找到食物的最優(yōu)策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的解都是搜索空 間中的一只鳥。我們稱之為“粒子”。所有的例子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness value)，每個粒子還有一個速

4、度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子 在解空間中搜索PSO初始化為一群隨機粒子(隨機解)。然后通過疊代找到最優(yōu)解。在每一次疊代中，粒子通 過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優(yōu)解。這個解叫做個體極值pBest. 另一個極值是整個種群目前找到的最優(yōu)解。這個極值是全局極值gBest。另外也可以不用整個種 群而只是用其中一部分最為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式來更新自己的速度和新的位置 TOC o 1-5 h z v = v + cl * rand() * (pbest - present) + c2

5、* rand() * (gbest 1I-present) (a) present = persent口 + v (b) IIIIv是粒子的速度，persent是當前粒子的位置.pbest and gbest | 如前定義rand ()是介于(0, 1)之間的隨機數(shù).cl, c2是學(xué)習因子.通常cl =c2 = 2.程序的偽代碼如下For each particleInitialize particleENDDoFor each particle 1ICalculate fitness valueIf the fitness value is better than the best fitn

6、ess value (pBest)in historyset current value as the new pBestEnd TOC o 1-5 h z IIIIIIChoose the particle with the best fitness value of all the particlesas the gBest liFor each particleCalculate particle velocity according equation (a)Update particle position according equation (b)EndWhile maximum i

7、terations or minimum error criteria is not attainedIII_I在每一維粒子的速度都會被限制在一個最大速度Vmax,如果某一維更新后的速度超過用戶設(shè)定的Vmax，那么這一維的速度就被限定為Vmax.編輯遺傳算法和PSO的比較1種群隨機初始化。對種群內(nèi)的每一個個體計算適應(yīng)值(fitness value)。適應(yīng)值與最優(yōu)解的距離直接有關(guān)。種群根據(jù)適應(yīng)值進行復(fù)制。如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟。從以上步驟，我們可以看到PSO和遺傳算法有很多共同之處。兩者都隨機初始化種群，而 且都使用適應(yīng)值來評價系統(tǒng)，而且都根據(jù)適應(yīng)值來進行一定的隨機搜索。兩個系

8、統(tǒng)都不是保證一 定找到最優(yōu)解。但是，PSO沒有遺傳操作如交叉(crossover)和變異(mutation)，而是根據(jù)自己的 速度來決定搜索。粒子還有一個重要的特點，就是有記憶。與遺傳算法比較，PSO的信息共享機制是很不同的。在遺傳算法中，染色體(chromosomes) 互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動。在PSO中，只有g(shù)Best (orlBest)給出信息給其他的粒子，這是單向的信息流動。整個搜索更新過程是跟隨當前最優(yōu)解 的過程。與遺傳算法比較，在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解。編輯人工神經(jīng)網(wǎng)絡(luò)和PSO1人工神經(jīng)網(wǎng)絡(luò)(ANN)是模擬大腦分析過程的

9、簡單數(shù)學(xué)模型，反向轉(zhuǎn)播算法是最流行的神經(jīng)網(wǎng) 絡(luò)訓(xùn)練算法。進來也有很多研究開始利用演化計算(evolutionary computation)技術(shù)來研究人工神 經(jīng)網(wǎng)絡(luò)的各個方面。演化計算可以用來研究神經(jīng)網(wǎng)絡(luò)的三個方面：網(wǎng)絡(luò)連接權(quán)重，網(wǎng)絡(luò)結(jié)構(gòu)(網(wǎng)絡(luò)拓撲結(jié)構(gòu)，傳 遞函數(shù))，網(wǎng)絡(luò)學(xué)習算法。不過大多數(shù)這方面的工作都集中在網(wǎng)絡(luò)連接權(quán)重，和網(wǎng)絡(luò)拓撲結(jié)構(gòu)上。在GA中，網(wǎng)絡(luò)權(quán)重 和/或拓撲結(jié)構(gòu)一般編碼為染色體(Chromosome)，適應(yīng)函數(shù)(fitness function)的選擇一般根據(jù)研 究目的確定。例如在分類問題中，錯誤分類的比率可以用來作為適應(yīng)值演化計算的優(yōu)勢在于可以處理一些傳統(tǒng)方法不能處理的例子例如

10、不可導(dǎo)的節(jié)點傳遞函數(shù)或 者沒有梯度信息存在。但是缺點在于：1、在某些問題上性能并不是特別好。2.網(wǎng)絡(luò)權(quán)重的編碼 而且遺傳算子的選擇有時比較麻煩。最近已經(jīng)有一些利用PSO來代替反向傳播算法來訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論文。研究表明PSO是 一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒有遺傳 算法碰到的問題。這里用一個簡單的例子說明PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)的過程。這個例子使用分類問題的基準函數(shù) (Benchmark functionRIS數(shù)據(jù)集。(Iris是一種鶯尾屬植物)在數(shù)據(jù)記錄中，每組數(shù)據(jù)包含Iris 花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有0

11、組數(shù)據(jù).這 樣總共有150組數(shù)據(jù)或模式。我們用3層的神經(jīng)網(wǎng)絡(luò)來做分類?，F(xiàn)在有四個輸入和三個輸出。所以神經(jīng)網(wǎng)絡(luò)的輸入層有4 個節(jié)點，輸出層有3個節(jié)點我們也可以動態(tài)調(diào)節(jié)隱含層節(jié)點的數(shù)目，不過這里我們假定隱含層 有6個節(jié)點。我們也可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)中其他的參數(shù)。不過這里我們只是來確定網(wǎng)絡(luò)權(quán)重。粒 子就表示神經(jīng)網(wǎng)絡(luò)的一組權(quán)重，應(yīng)該是4*6+6*3=42個參數(shù)。權(quán)重的范圍設(shè)定為-100，100(這 只是一個例子，在實際情況中可能需要試驗調(diào)整).在完成編碼以后，我們需要確定適應(yīng)函數(shù)。對 于分類問題，我們把所有的數(shù)據(jù)送入神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的權(quán)重有粒子的參數(shù)決定。然后記錄所有的 錯誤分類的數(shù)目作為那個粒子的適應(yīng)值。

12、現(xiàn)在我們就利用PSO來訓(xùn)練神經(jīng)網(wǎng)絡(luò)來獲得盡可能低 的錯誤分類數(shù)目。PSO本身并沒有很多的參數(shù)需要調(diào)整。所以在實驗中只需要調(diào)整隱含層的節(jié) 點數(shù)目和權(quán)重的范圍以取得較好的分類效果。編輯PSO的參數(shù)設(shè)置1從上面的例子我們可以看到應(yīng)用PSO解決優(yōu)化問題的過程中有兩個重要的步驟：問題解的 編碼和適應(yīng)度函數(shù)PSO的一個優(yōu)勢就是采用實數(shù)編碼，不需要像遺傳算法一樣是二進制編碼 (或者采用針對實數(shù)的遺傳操作.例如對于問題f(x) = x2 + X2A2+X3A2求解，粒子可以直接編 碼為(x1, x2, x3),而適應(yīng)度函數(shù)就是f(x).接著我們就可以利用前面的過程去尋優(yōu).這個尋優(yōu)過 程是一個疊代過程，中止條件

13、一般為設(shè)置為達到最大循環(huán)數(shù)或者最小錯誤PSO中并沒有許多需要調(diào)節(jié)的參數(shù)，下面列出了這些參數(shù)以及經(jīng)驗設(shè)置粒子數(shù)：一般取20 40.其實對于大部分的問題10個粒子已經(jīng)足夠可以取得好的結(jié)果，不 過對于比較難的問題或者特定類別的問題，粒子數(shù)可以取到100或200粒子的長度：這是由優(yōu)化問題決定，就是問題解的長度粒子的范圍：由優(yōu)化問題決定,每一維可是設(shè)定不同的范圍Vmax:最大速度，決定粒子在一個循環(huán)中最大的移動距離，通常設(shè)定為粒子的范圍寬度，例如 上面的例子里，粒子(x1, x2, x3) x1屬于-10, 10,那么Vmax的大小就是20學(xué)習因子:c1和c2通常等于2.不過在文獻中也有其他的取值.但是一般c1等于c2 并且范圍在0和4之間中止條件：最大循環(huán)數(shù)以及最小錯誤要求.例如，在上面的神經(jīng)網(wǎng)絡(luò)訓(xùn)練例子中，最小錯誤 可以設(shè)定為1個錯誤分類，最大循環(huán)設(shè)定為2000,這個中止條件由