1、粒子群算法介紹優(yōu)化問(wèn)題是工業(yè)設(shè)計(jì)中經(jīng)常遇到的問(wèn)題，許多問(wèn)題最后都可以歸結(jié)為優(yōu)化問(wèn)題.為了解 決各種各樣的優(yōu)化問(wèn)題，人們提出了許多優(yōu)化算法，比較著名的有爬山法、遺傳算法等.優(yōu)化問(wèn) 題有兩個(gè)主要問(wèn)題:一是要求尋找全局最小點(diǎn)，二是要求有較高的收斂速度.爬山法精度較高, 但是易于陷入局部極小.遺傳算法屬于進(jìn)化算法(Evolutionary Algorithms)的一種，它通過(guò)模 仿自然界的選擇與遺傳的機(jī)理來(lái)尋找最優(yōu)解.遺傳算法有三個(gè)基本算子:選擇、交叉和變異. 但是遺傳算法的編程實(shí)現(xiàn)比較復(fù)雜，首先需要對(duì)問(wèn)題進(jìn)行編碼，找到最優(yōu)解之后還需要對(duì)問(wèn)題 進(jìn)行解碼,另外三個(gè)算子的實(shí)現(xiàn)也有許多參數(shù)，如交叉率和變異率

2、，并且這些參數(shù)的選擇嚴(yán)重 影響解的品質(zhì)，而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗(yàn).1995年Eberhart博士和kennedy 博士提出了一種新的算法;粒子群優(yōu)化(Partical Swarm Optimization -PSO)算法.這種算法 以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問(wèn)題中展示了 其優(yōu)越性.粒子群優(yōu)化(Partical Swarm Optimization - PSO)算法是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化 算法(Evolu2tionary Algorithm - EA) .PSO算法屬于進(jìn)化算法的一種，和遺傳算法相似,它也是 從隨機(jī)解出發(fā)，通過(guò)迭代尋找

3、最優(yōu)解,它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì).但是它比遺傳算法 規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的“交叉”(Crossover)和“變異”(Mutation)操作.它通過(guò) 追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu).粒子群算法引言粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(evolutionary computation)，有Eberhart博士 和kennedy博士發(fā)明。源于對(duì)鳥群捕食的行為研究PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò) 疊代搜尋最優(yōu)值。但是并沒(méi)有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在 解空間追隨最優(yōu)的粒子進(jìn)行搜索。詳

4、細(xì)的步驟以后的章節(jié)介紹同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參數(shù)需要調(diào)整。目前已 廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域背景：人工生命”人工生命”是來(lái)研究具有某些生命基本特征的人工系統(tǒng).人工生命包括兩方面的內(nèi)容研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象研究如何利用生物技術(shù)研究計(jì)算問(wèn)題我們現(xiàn)在關(guān)注的是第二部分的內(nèi)容.現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計(jì)算技巧.例如, 人工神經(jīng)網(wǎng)絡(luò)是簡(jiǎn)化的大腦模型.遺傳算法是模擬基因進(jìn)化過(guò)程的.現(xiàn)在我們討論另一種生物系統(tǒng)-社會(huì)系統(tǒng).更確切的是，在由簡(jiǎn)單個(gè)體組成的群落與環(huán) 境以及個(gè)體之間的互動(dòng)行為.也可稱做群智能(swarm in

5、telligence).這些模擬系統(tǒng)利用局 部信息從而可能產(chǎn)生不可預(yù)測(cè)的群體行為例如floys和boids,他們都用來(lái)模擬魚群和鳥群的運(yùn)動(dòng)規(guī)律，主要用于計(jì)算機(jī)視覺(jué)和 計(jì)算機(jī)輔助設(shè)計(jì).在計(jì)算智能(computational intelligence)領(lǐng)域有兩種基于群智能的算法.蟻群算法(ant colony optimization)和粒子群算法(particle swarm optimization).前者是對(duì)螞蟻群落食物采集 過(guò)程的模擬.已經(jīng)成功運(yùn)用在很多離散優(yōu)化問(wèn)題上.粒子群優(yōu)化算法(PSO)也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬.最初設(shè)想是模擬鳥群覓食的 過(guò)程.但后來(lái)發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具

6、.算法介紹如前所述，PSO模擬鳥群的捕食行為。設(shè)想這樣一個(gè)場(chǎng)景：一群鳥在隨機(jī)搜索食物。 在這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當(dāng)前的位置離食 物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的 鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO中，每個(gè)優(yōu)化問(wèn)題的解都是搜 索空間中的一只鳥。我們稱之為“粒子”。所有的例子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng) 值(fitness value)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng) 前的最優(yōu)粒子在解空間中搜索PSO初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過(guò)

7、疊代找到最優(yōu)解。在每一次疊代中，粒 子通過(guò)跟蹤兩個(gè)”極值”來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體 極值pBest.另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值gBest。另外也 可以不用整個(gè)種群而只是用其中一部分最為粒子的鄰居，那么在所有鄰居中的極值就是局部 極值。在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式來(lái)更新自己的速度和新的位置v = v + cl * rand() * (pbest - present) + c2 * rand() * (gbest - present) (a)present = persent + v (b)v是粒子的速度,persent

8、是當(dāng)前粒子的位置.pbest and gbest如前定義rand ()是 介于(0，1)之間的隨機(jī)數(shù).c1, c2是學(xué)習(xí)因子.通常c1 = c2 = 2.程序的偽代碼如下For each particleInitialize particleENDDoFor each particleCalculate fitness valueIf the fitness value is better than the best fitness value (pBest) in historyset current value as the new pBestEndChoose the particle

9、with the best fitness value of all the particles as the gBestFor each particleCalculate particle velocity according equation (a)Update particle position according equation (b)EndWhile maximum iterations or minimum error criteria is not attained在每一維粒子的速度都會(huì)被限制在一個(gè)最大速度Vmax，如果某一維更新后的速度超過(guò) 用戶設(shè)定的Vmax，那么這一維的

10、速度就被限定為Vmax4.遺傳算法和PSO的比較大多數(shù)演化計(jì)算技術(shù)都是用同樣的過(guò)程1. 種群隨機(jī)初始化對(duì)種群內(nèi)的每一個(gè)個(gè)體計(jì)算適應(yīng)值(fitness value).適應(yīng)值與最優(yōu)解的距離直接有關(guān)種群根據(jù)適應(yīng)值進(jìn)行復(fù)制如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟2從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機(jī)初始化種群，而 且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保 證一定找到最優(yōu)解但是，PSO沒(méi)有遺傳操作如交叉(crossover)和變異(mutation).而是根據(jù)自己的速度來(lái)決 定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶。與遺傳算法比較，PS

11、O的信息共享機(jī)制是很不同的.在遺傳算法中，染色體 (chromosomes)互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng).在PSO 中，只有g(shù)Best (or lBest)給出信息給其他的粒子，這是單向的信息流動(dòng).整個(gè)搜索更新過(guò)程 是跟隨當(dāng)前最優(yōu)解的過(guò)程.與遺傳算法比較，在大多數(shù)的情況下，所有的粒子可能更快的收 斂于最優(yōu)解人工神經(jīng)網(wǎng)絡(luò)和PSO人工神經(jīng)網(wǎng)絡(luò)(ANN )是模擬大腦分析過(guò)程的簡(jiǎn)單數(shù)學(xué)模型，反向轉(zhuǎn)播算法是最流行的神 經(jīng)網(wǎng)絡(luò)訓(xùn)練算法。進(jìn)來(lái)也有很多研究開始利用演化計(jì)算(evolutionary computation)技術(shù)來(lái)研究 人工神經(jīng)網(wǎng)絡(luò)的各個(gè)方面。演化計(jì)算可以用來(lái)研究神

12、經(jīng)網(wǎng)絡(luò)的三個(gè)方面：網(wǎng)絡(luò)連接權(quán)重，網(wǎng)絡(luò)結(jié)構(gòu)(網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)， 傳遞函數(shù))，網(wǎng)絡(luò)學(xué)習(xí)算法。不過(guò)大多數(shù)這方面的工作都集中在網(wǎng)絡(luò)連接權(quán)重，和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上。在GA中，網(wǎng)絡(luò) 權(quán)重和/或拓?fù)浣Y(jié)構(gòu)一般編碼為染色體(Chromosome)，適應(yīng)函數(shù)(fitness function)的選擇一般 根據(jù)研究目的確定。例如在分類問(wèn)題中，錯(cuò)誤分類的比率可以用來(lái)作為適應(yīng)值演化計(jì)算的優(yōu)勢(shì)在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導(dǎo)的節(jié)點(diǎn)傳遞函 數(shù)或者沒(méi)有梯度信息存在。但是缺點(diǎn)在于：在某些問(wèn)題上性能并不是特別好。2.網(wǎng)絡(luò)權(quán)重 的編碼而且遺傳算子的選擇有時(shí)比較麻煩最近已經(jīng)有一些利用PSO來(lái)代替反向傳播算法來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論

13、文。研究表明PSO 是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒(méi) 有遺傳算法碰到的問(wèn)題這里用一個(gè)簡(jiǎn)單的例子說(shuō)明PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)的過(guò)程。這個(gè)例子使用分類問(wèn)題的基準(zhǔn) 函數(shù)(Benchmark function)IRIS數(shù)據(jù)集。(Iris是一種鶯尾屬植物)在數(shù)據(jù)記錄中，每組數(shù)據(jù)包 含Iris花的四種屬性：萼片長(zhǎng)度，萼片寬度，花瓣長(zhǎng)度，和花瓣寬度，三種不同的花各有 50組數(shù)據(jù).這樣總共有150組數(shù)據(jù)或模式。我們用3層的神經(jīng)網(wǎng)絡(luò)來(lái)做分類。現(xiàn)在有四個(gè)輸入和三個(gè)輸出。所以神經(jīng)網(wǎng)絡(luò)的輸入層 有4個(gè)節(jié)點(diǎn)，輸出層有3個(gè)節(jié)點(diǎn)我們也可以動(dòng)態(tài)調(diào)節(jié)隱含層節(jié)點(diǎn)的數(shù)目，不過(guò)這里我們假定

14、隱含層有6個(gè)節(jié)點(diǎn)。我們也可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)中其他的參數(shù)。不過(guò)這里我們只是來(lái)確定網(wǎng)絡(luò) 權(quán)重。粒子就表示神經(jīng)網(wǎng)絡(luò)的一組權(quán)重，應(yīng)該是4*6+6*3=42個(gè)參數(shù)。權(quán)重的范圍設(shè)定為-100， 100(這只是一個(gè)例子，在實(shí)際情況中可能需要試驗(yàn)調(diào)整).在完成編碼以后，我們需要確定適 應(yīng)函數(shù)。對(duì)于分類問(wèn)題，我們把所有的數(shù)據(jù)送入神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的權(quán)重有粒子的參數(shù)決定。 然后記錄所有的錯(cuò)誤分類的數(shù)目作為那個(gè)粒子的適應(yīng)值?，F(xiàn)在我們就利用PSO來(lái)訓(xùn)練神經(jīng) 網(wǎng)絡(luò)來(lái)獲得盡可能低的錯(cuò)誤分類數(shù)目。PSO本身并沒(méi)有很多的參數(shù)需要調(diào)整。所以在實(shí)驗(yàn) 中只需要調(diào)整隱含層的節(jié)點(diǎn)數(shù)目和權(quán)重的范圍以取得較好的分類效果。6. PSO的參數(shù)設(shè)置從

15、上面的例子我們可以看到應(yīng)用PSO解決優(yōu)化問(wèn)題的過(guò)程中有兩個(gè)重要的步驟：?jiǎn)栴} 解的編碼和適應(yīng)度函數(shù)PSO的一個(gè)優(yōu)勢(shì)就是采用實(shí)數(shù)編碼，不需要像遺傳算法一樣是二進(jìn)制編碼(或者采用針 對(duì)實(shí)數(shù)的遺傳操作.例如對(duì)于問(wèn)題f(x) = x1A2 + x2A2+x3A2求解，粒子可以直接編碼為(x1, x2, x3),而適應(yīng)度函數(shù)就是f(x).接著我們就可以利用前面的過(guò)程去尋優(yōu).這個(gè)尋優(yōu)過(guò)程是一 個(gè)疊代過(guò)程，中止條件一般為設(shè)置為達(dá)到最大循環(huán)數(shù)或者最小錯(cuò)誤PSO中并沒(méi)有許多需要調(diào)節(jié)的參數(shù)，下面列出了這些參數(shù)以及經(jīng)驗(yàn)設(shè)置粒子數(shù)：一般取20 - 40.其實(shí)對(duì)于大部分的問(wèn)題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié) 果，不過(guò)對(duì)于

16、比較難的問(wèn)題或者特定類別的問(wèn)題，粒子數(shù)可以取到100或200粒子的長(zhǎng)度：這是由優(yōu)化問(wèn)題決定，就是問(wèn)題解的長(zhǎng)度粒子的范圍：由優(yōu)化問(wèn)題決定,每一維可是設(shè)定不同的范圍Vmax:最大速度，決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)定為粒子的范圍寬度, 例如上面的例子里，粒子(x1, x2, x3) x1屬于-10, 10,那么Vmax的大小就是20學(xué)習(xí)因子：c1和c2通常等于2.不過(guò)在文獻(xiàn)中也有其他的取值.但是一般c1等于 c2并且范圍在0和4之間中止條件：最大循環(huán)數(shù)以及最小錯(cuò)誤要求.例如，在上面的神經(jīng)網(wǎng)絡(luò)訓(xùn)練例子中，最小 錯(cuò)誤可以設(shè)定為1個(gè)錯(cuò)誤分類，最大循環(huán)設(shè)定為2000,這個(gè)中止條件由具體的問(wèn)題確

17、定.全局PSO和局部PSO：我們介紹了兩種版本的粒子群優(yōu)化算法：全局版和局部版.前者 速度快不過(guò)有時(shí)會(huì)陷入局部最優(yōu).后者收斂速度慢一點(diǎn)不過(guò)很難陷入局部最優(yōu).在實(shí)際應(yīng)用 中，可以先用全局PSO找到大致的結(jié)果，再有局部PSO進(jìn)行搜索.另外的一個(gè)參數(shù)是慣性權(quán)重，由Shi和Eberhart提出，有興趣的可以參考他們1998年的 論文(題目：A modified particle swarm optimizer)7.PSO網(wǎng)上資源粒子群優(yōu)化算法的研究還處于初期階段，還有很多未知的領(lǐng)域需要研究，例如關(guān)于粒子 群理論的數(shù)學(xué)證明不過(guò)網(wǎng)上已經(jīng)由了很多的關(guān)于粒子群的資源，下面列出一些：http：/關(guān)于粒子群理論的

18、各方面資源http：/hux/PSO.shtml有一份比較全的文獻(xiàn)列表以及網(wǎng)上論文http：/可以搜索到關(guān)于PSO的很多論文及文獻(xiàn) 參考文獻(xiàn)http：/eberhart/http：/cathyk/jimk.htmlhttp：/http：/ HYPERLINK /cwr/boids/ /cwr/boids/ HYPERLINK http:/iridia.ulb.ac.be/mdorigo/ACO/ACO.html http:/iridia.ulb.ac.be/mdorigo/ACO/ACO.html HYPERLINK /shi/Coference/psopap4.html /shi/Cofer

19、ence/psopap4.htmlKennedy, J. and Eberhart, R. C. Particle swarm optimization. Proc. IEEE intl conf. on neural networks Vol. IV, pp. 1942-1948. IEEE service center, Piscataway, NJ, 1995.Eberhart, R. C. and Kennedy, J. A new optimizer using particle swarm theory. Proceedings of the sixth international

20、 symposium on micro machine and human science pp. 39-43. IEEE service center, Piscataway, NJ, Nagoya, Japan, 1995.Eberhart, R. C. and Shi, Y. Particle swarm optimization: developments, applications and resources. Proc. congress on evolutionary computation 2001 IEEE service center, Piscataway, NJ., Seoul, Korea., 2001.Eberhart, R. C. and Shi, Y. Evolving artificial neural