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

1、實(shí)用標(biāo)準(zhǔn)文案計算機(jī)輔助工藝課程作業(yè)精彩文檔實(shí)用標(biāo)準(zhǔn)文案學(xué) 生：趙 華 琳學(xué) 號 : s308070072時 間： 09 年 6 月粒子群優(yōu)化算法概述0. 前 言優(yōu)化是科學(xué)研究、 工程技術(shù)和經(jīng)濟(jì)管理等領(lǐng)域的重要研究工具。 它所研究的問題是討論 在眾多的方案中尋找最優(yōu)方案。 例如， 工程設(shè)計中怎樣選擇設(shè)計參數(shù)， 使設(shè)計方案既滿足設(shè) 計要求又能降低成本； 資源分配中， 怎樣分配有限資源， 使分配方案既能滿足各方面的基本 要求，又能獲得好的經(jīng)濟(jì)效益。在人類活動的各個領(lǐng)域中，諸如此類，不勝枚舉。優(yōu)化這一 技術(shù)， 正是為這些問題的解決， 提供理論基礎(chǔ)和求解方法，它是一門應(yīng)用廣泛、實(shí)用性很強(qiáng) 的科學(xué)。近十余

2、年來， 粒子群優(yōu)化算法作為群體智能算法的一個重要分支得到了廣泛深入的 研究，在路徑規(guī)劃等許多領(lǐng)域都有應(yīng)用。 本文主要結(jié)合現(xiàn)階段的研究概況對粒子群優(yōu)化算法 進(jìn)行初步介紹。1.粒子群優(yōu)化算法的基本原理1.1 粒子群優(yōu)化算法的起源粒子群優(yōu)化（ PSO）算法是由 Kennedy 和 Eberhart 于 1995 年用計算機(jī)模擬鳥群覓 食這一簡單的社會行為時，受到啟發(fā)，簡化之后而提出的 12 。精彩文檔實(shí)用標(biāo)準(zhǔn)文案設(shè)想這樣一個場景： 一群鳥隨機(jī)的分布在一個區(qū)域中， 在這個區(qū)域里只有一塊食物。 所 有的鳥都不知道食物在哪里。 但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。 那么找到食物的最 優(yōu)策略是什么呢。 最

3、簡單有效的方法就是追尋自己視野中目前離食物最近的鳥。 如果把食物 當(dāng)作最優(yōu)點(diǎn)， 而把鳥離食物的距離當(dāng)作函數(shù)的適應(yīng)度， 那么鳥尋覓食物的過程就可以當(dāng)作一 個函數(shù)尋優(yōu)的過程。 魚群和鳥群的社會行為一直引起科學(xué)家的興趣。 他們以特殊的方式移動、 同步，不會相互碰撞，整體行為看上去非常優(yōu)美。生物學(xué)家 CargiReynolds 提出了一個非 常有影響的鳥群聚集模型。在他的模擬模型 boids 中，每一個個體遵循：避免與鄰域個體 相沖撞、 匹配鄰域個體的速度、 試圖飛向感知到的鳥群中心這三條規(guī)則形成簡單的非集中控 制算法驅(qū)動鳥群的聚集，在一系列模擬實(shí)驗(yàn)中突現(xiàn)出了非常接近現(xiàn)實(shí)鳥群聚集行為的現(xiàn)象。 該結(jié)果顯

4、示了在空中回旋的鳥組成輪廓清晰的群體， 以及遇到障礙物時鳥群的分裂和再度匯 合過程。由此受到啟發(fā)，經(jīng)過簡化提出了粒子群優(yōu)化算法。1.2 粒子群優(yōu)化算法的原理在粒子群優(yōu)化算法中， 每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥， 稱之為“粒子”。 所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值， 每個粒子還有一個速度決定他們飛翔的 方向和距離。 然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。 優(yōu)化開始時先初始化為一 群隨機(jī)粒子（隨機(jī)解） 。然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極 值來更新自己。 第一個極值就是整個種群目前找到的最優(yōu)解。 這個極值是全局極值。 另外也 可以不用整個種群

5、而只是用其中一部分作為粒子的鄰居， 那么在所有鄰居中的極值就是局部 極值。 第二個極值是粒子本身所找到的最優(yōu)解， 稱為個體極值。 這是因?yàn)榱Ｗ觾H僅通過跟蹤 全局極值或者局部極值來更新位置， 不可能總是獲得較好的解。 這樣在優(yōu)化過程中， 粒子在 追隨全局極值或局部極值的同時追隨個體極值則圓滿的解決了這個問題。 這就是粒子群優(yōu)化 算法的原理。精彩文檔實(shí)用標(biāo)準(zhǔn)文案在算法開始時， 隨機(jī)初始化粒子的位置和速度構(gòu)成初始種群， 初始種群在解空間中為均 勻分布。 其中第 i 個粒子在 n 維解空間的位置和速度可分別表示為 Xi=(xi1,xi2,xid)和 Vi= (v i1,v i2,v id )，然后通過

6、迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更 新自己的速度和位置。 一個極值是粒子本身到目前為止所找到的最優(yōu)解， 這個極值稱為個體 極值 Pb i= ( Pb i1,Pb i2 ,Pb id)。另一個極值是該粒子的鄰域到目前為止找到的最優(yōu)解，這個極值稱為整個鄰域的最優(yōu)粒子Nbest i=(Nbest i1 ,Nbest i2,Nbest id )。粒子根據(jù)如下的式(2-1) 和式 (2-2) 來更新自己的速度和位置：Vi=V i+c 1rand() (Pbest i-X i )+c 2rand() (Nbest i-Xi) (2-1)Xi= Xi+ V i(2-2)式中 c1和 c

7、2 是加速常量，分別調(diào)節(jié)向全局最好粒子和個體最好粒子方向飛行的最大步 長，若太小，則粒子可能遠(yuǎn)離目標(biāo)區(qū)域,若太大則會導(dǎo)致突然向目標(biāo)區(qū)域飛去，或飛過目標(biāo)區(qū)域。合適的 c1，c2可以加快收斂且不易陷入局部最優(yōu)。 rand() 是0 到 1 之間的隨機(jī)數(shù)。 粒子在每一維飛行的速度不能超過算法設(shè)定的最大速度Vmax 。設(shè)置較大的 Vmax 可以保證粒子種群的全局搜索能力， Vmax 較小則粒子種群優(yōu)化算法的局部搜索能力加強(qiáng)。粒子群優(yōu)化算法是在模擬鳥群覓食時受到啟發(fā)提出的。 提出之后卻發(fā)現(xiàn)用動物或人的認(rèn) 知來解釋算法的原理更加完美。 在速度更新公式 (2-1) 中由 3 個部分構(gòu)成。 第 1 個部分是

8、Vi， 表示粒子在解空間有按照原有方向和速度進(jìn)行搜索的趨勢， 這可以用人在認(rèn)知事物時總是用 固有的習(xí)慣來解釋。第 2 個部分是 c1rand() (Pbest i-X i)，表示粒子在解空間有朝著過去曾 碰到的最優(yōu)解進(jìn)行搜索的趨勢，這可以用人在認(rèn)知事物時總是用過去的經(jīng)驗(yàn)來解釋。第 3 部分是 c2rand() (Nbest i-X i)，表示粒子在解空間有朝著整個鄰域過去曾碰到的最優(yōu)解進(jìn)行 搜索的趨勢， 這可以用人在認(rèn)知事物時總可以通過學(xué)習(xí)其他人的知識， 也就是分享別人的經(jīng) 驗(yàn)來解釋。 因此，粒子群優(yōu)化算法實(shí)際上是借用了人或動物認(rèn)知事物時的習(xí)慣，經(jīng)驗(yàn)， 及學(xué)精彩文檔實(shí)用標(biāo)準(zhǔn)文案習(xí)過程來進(jìn)行尋優(yōu)

9、的。粒子在優(yōu)化過程中的運(yùn)動軌跡見圖1 。圖 1 粒子群算法優(yōu)化搜索示意圖1.3 粒子群優(yōu)化算法的優(yōu)點(diǎn)粒子群優(yōu)化算法具有以下主要優(yōu)點(diǎn)： (1)易于描述； (2)便于實(shí)現(xiàn)； (3) 要調(diào)整的參數(shù)很 少； (4)使用規(guī)模相對較少的群體； (5)收斂需要評估函數(shù)的次數(shù)少； (6)收斂速度快粒子群優(yōu) 化算法很容易實(shí)現(xiàn)，計算代價低，由于其內(nèi)存和 CPU 速度要求都很低。而且，它不需要目 標(biāo)函數(shù)的梯度信息， 只依靠函數(shù)值。 粒子群優(yōu)化算法已被證明是解決許多全局優(yōu)化問題的有 效方法。2.粒子群優(yōu)化算法的實(shí)現(xiàn)粒子群優(yōu)化算法具有編程簡單，易實(shí)現(xiàn)的特點(diǎn)，粒子群優(yōu)化算法的流程如圖 2 所示。 下面給出其實(shí)現(xiàn)的具體步驟

10、：步驟 1：初始化。初始搜索點(diǎn)的位置 X0i 及其速度 V0i通常是 在允許的范圍內(nèi)隨機(jī)產(chǎn)生的， 每個粒子的 Pbest 坐標(biāo)設(shè)置為其當(dāng) 前位置，且計算出其相應(yīng)的個體極值(即個體極值點(diǎn) 的適應(yīng)度值)，而整個鄰域的最優(yōu)粒子就是該粒子鄰域中個體極 值中最好的，記錄該最好值的粒子序號，并將 Nbest i 設(shè)置為該 最好粒子的當(dāng)前位置。精彩文檔實(shí)用標(biāo)準(zhǔn)文案步驟 2：評價每一個粒子。 計算粒子的適應(yīng)度值 ,如果好于該 粒子當(dāng)前的個體極值， 則將 Pbest 設(shè)置為該粒子的位置， 且更新 個體極值。如果在該粒子的鄰域內(nèi)所有粒子的個體極值中最好的 好于當(dāng)前的 Nbest i，則將 Nbest i 設(shè)置為該

11、粒子的位置，記錄該 粒子的序號，且更新 Nbest i 的函數(shù)值。步驟 3：粒子的更新。用式 (2-1) 和式 (2-2) 對每一個粒子的 速度和位置進(jìn)行更新。步驟 4：檢驗(yàn)是否符合結(jié)束條件。如果當(dāng)前的迭代次數(shù)達(dá)到 了預(yù)先設(shè)定的最大次數(shù)，則停止迭代，輸出最優(yōu)解，否則轉(zhuǎn)到步 驟 2 。精彩文檔實(shí)用標(biāo)準(zhǔn)文案圖 2 粒子群算法優(yōu)化算法流程圖3粒子群優(yōu)化算法的兩種模式Kennedy 等人在觀察鳥群覓食的過程中注意到，通常飛鳥并不一定看到鳥群中其他所 有飛鳥的位置和動向， 往往只是看到相鄰的飛鳥的位置和動向。 因此他在研究粒子群算法時， 同時開發(fā)了兩種模式：全局最優(yōu) (Gbest) 和局部最優(yōu) (Lbe

12、st) 。基本粒子群優(yōu)化算法就是全局最優(yōu)的具體實(shí)現(xiàn)。 在全局最優(yōu)中每個個體被吸引到由種群 任何個體發(fā)現(xiàn)的最優(yōu)解。 該結(jié)構(gòu)相當(dāng)于一個完全連接的社會網(wǎng)絡(luò)； 每一個個體能夠跟種群中 所有其他個體進(jìn)行比較性能， 模仿真正最好的個體。 每個粒子的軌跡受粒子群中所有粒子的精彩文檔實(shí)用標(biāo)準(zhǔn)文案所有的經(jīng)驗(yàn)和意識的影響。全局模式有較快的收斂速度，但容易陷入局部極值。而在局部模式中，粒子總根據(jù)它自己的信息和鄰域內(nèi)的最優(yōu)值信息來調(diào)整它的運(yùn)動軌 跡，而不是群體粒子的最優(yōu)值信息，粒子的軌跡只受自身的認(rèn)知和鄰近的粒子狀態(tài)的影響， 而不是被所有粒子的狀態(tài)影響。 這樣， 粒子就不是向全局最優(yōu)值移動， 而是向鄰域內(nèi)的最優(yōu) 值移

13、動。 而最終的全局最優(yōu)值從鄰域最優(yōu)值內(nèi)選出， 即鄰域最優(yōu)之中適應(yīng)值最高的值。 在算 法中，相鄰兩鄰域內(nèi)部分粒子重疊，這樣兩相鄰鄰域內(nèi)公共粒子可在兩個鄰域間交換信息， 從而有助于粒子跳出局部最優(yōu)，達(dá)到全局最優(yōu)。局部模式本身存在著兩種不同的方式。一種方式是由兩個粒子空間位置決定“鄰居” ， 它們的遠(yuǎn)近用粒子間距離來度量； 局部最優(yōu)的另一種方式是編號方法， 粒子群中的粒子在搜 索之前就被編以不同的號碼， 形成環(huán)狀拓?fù)渖鐣Y(jié)構(gòu)。 對于第一種方式， 在每次迭代之后都 需要計算每個粒子與其他粒子間的距離來確定鄰居中包括哪些粒子， 這導(dǎo)致算法的復(fù)雜度增 強(qiáng)，算法運(yùn)行效率降低； 而第二種方式由于事先對粒子進(jìn)行

14、了編號， 因而在迭代中粒子的鄰 域不會改變，這導(dǎo)致在搜索過程中，當(dāng)前粒子與指定的“鄰居”粒子迅速聚集，而整個粒子 群就被分成幾個小塊，表面上看似乎是增大了搜索的范圍，實(shí)際上則大大降低了收斂速度。 局部最優(yōu)模式收斂速度較慢，但卻具有較強(qiáng)的全局搜索能力。例如在環(huán)形拓?fù)渲?1 號與最 后一個粒子和 2 號相鄰， 2 號粒子則與 1 號、 3 號相鄰，這種定義方式被稱為拓?fù)湟饬x下的 鄰居。根據(jù)社會學(xué)家的研究，這兩種鄰居的概念都是有社會背景的。全局模式的拓?fù)浣Y(jié)構(gòu)如圖 3 中的 (a)所示，環(huán)形局部模式的拓?fù)浣Y(jié)構(gòu)如圖 3 中的 (b)所示。精彩文檔實(shí)用標(biāo)準(zhǔn)文案圖 3 粒子群算法的兩種模型： (a) 全局模

15、型； (b) 環(huán)形局部模型Suganthan 提出帶有鄰域操作的 PSO 模型，用每個粒子所定義的當(dāng)前鄰域極值代替粒 子群的當(dāng)前全局極值。 在優(yōu)化的初始階段， 將鄰域定義為每個粒子自身， 隨著迭代次數(shù)的增 加，將鄰域范圍逐步擴(kuò)展到包含所有粒子， 則此時的鄰域極值即為全局極值。 這種模型在一 定程度上克服了 PSO 模型在優(yōu)化搜索后期，隨迭代次數(shù)增加搜索結(jié)果無明顯該進(jìn)的缺點(diǎn)。 4.粒子群算法的應(yīng)用PSO 算法的優(yōu)勢在于算法的簡潔性，易于實(shí)現(xiàn)，沒有很多參數(shù)需要調(diào)整，需要梯度信 息。 PSO 算法是非線性連續(xù)優(yōu)化問題、組合優(yōu)化問題和混合整數(shù)非線性優(yōu)化問題的有效優(yōu) 化工具。1函數(shù)優(yōu)化第三章粒子群算法原

16、理與收斂性分析大量的問題最終可歸結(jié)為函數(shù)的優(yōu)化問題， 通常這 些函數(shù)是非常復(fù)雜的，主要表現(xiàn)為規(guī)模大、維數(shù)高、非線性、非凸和不可微等特性，而且有 的函數(shù)存在大量局部極小。 許多傳統(tǒng)確定性優(yōu)化算法收斂速度較快， 計算精度高， 但對初值 敏感，易陷入局部最小。而一些具有全局性的優(yōu)化算法，如遺傳算法、模擬退火算法、進(jìn)化 規(guī)劃等，受限于各自的機(jī)理和單一結(jié)構(gòu)，對于高維復(fù)雜函數(shù)難以實(shí)現(xiàn)高效優(yōu)化。 PSO 算法 通過改進(jìn)或結(jié)合其它算法，對高維復(fù)雜函數(shù)可以實(shí)現(xiàn)高效優(yōu)化。2神經(jīng)網(wǎng)絡(luò)的訓(xùn)練PSO 算法用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練中，主要包含3 個方面 :連接權(quán)重、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及傳遞精彩文檔實(shí)用標(biāo)準(zhǔn)文案函數(shù)、 學(xué)習(xí)算法。每個粒

17、子包含神經(jīng)網(wǎng)絡(luò)的所有參數(shù)，通過迭代來優(yōu)化這些參數(shù)，從而達(dá)到訓(xùn)練的目的。與 BP 算法相比，使用 PSO 算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)在于不使用梯度信息， 可使用一些不可微的傳遞函數(shù)。 多數(shù)情況下其訓(xùn)練結(jié)果優(yōu)于 BP 算法，而且訓(xùn)練速度非?？?。 3.參數(shù)優(yōu)化PSO 算法己廣泛應(yīng)用于各類連續(xù)問題和離散問題的參數(shù)優(yōu)化。例如，在模糊控制器的 設(shè)計、機(jī)器人路徑規(guī)劃、信號處理和模式識別等問題上均取得了不錯的效果。4、組合優(yōu)化許多組合優(yōu)化問題中存在序結(jié)構(gòu)如何表達(dá)以及約束條件如何處理等問題， 離散二進(jìn)制版PSO 算法不能完全適用。研究者們根據(jù)問題的不同，提出了相應(yīng)問題的粒子表達(dá)方式，或 通過重新定義算子來解決不同問

18、題。目前，已提出了多種解決TSP、VRP 以及車間調(diào)度等問題的方案。其他應(yīng)用 :除了以上領(lǐng)域外， PSO 算法的應(yīng)用包括系統(tǒng)設(shè)計、多目標(biāo)優(yōu)化、分 類、模式識別、調(diào)度、信號處理、決策、機(jī)器人應(yīng)用等。其中具體應(yīng)用實(shí)例有:模糊控制器設(shè)計、車間作業(yè)調(diào)度、機(jī)器人實(shí)時路徑規(guī)劃、自動目標(biāo)檢測、時頻分析等。4.粒子群優(yōu)化算法的發(fā)展方向目前，粒子群算法的發(fā)展趨勢主要有：(1) 粒子群優(yōu)化算法的改進(jìn)。粒子群優(yōu)化算法在解決空間函數(shù)的優(yōu)化問題和單目標(biāo)優(yōu)化 問題上應(yīng)用得比較多， 如何應(yīng)用于離散空間優(yōu)化問題和多目標(biāo)優(yōu)化問題將是粒子群優(yōu)化算法 的主要研究方向。 如何充分結(jié)合其他進(jìn)化類算法， 發(fā)揮優(yōu)勢， 改進(jìn)粒子群優(yōu)化算法的

19、不足也 是值得研究的。(2) 粒子群優(yōu)化算法的理論分析。粒子群優(yōu)化算法提出的時間不長，數(shù)學(xué)分析很不成熟 和系統(tǒng)，存在許多不完善和未涉及的問題，對算法運(yùn)行行為、 收斂性、 計算復(fù)雜性的分析比 較少。 如何知道參數(shù)的選擇和設(shè)計， 如何設(shè)計適應(yīng)值函數(shù)， 如何提高算法在解空間搜索的效精彩文檔實(shí)用標(biāo)準(zhǔn)文案率算法收斂以及對算法模型本身的研究都需要在理論上進(jìn)行更深入的研究。 這些都是粒子群 優(yōu)化算法的研究方向之一。(3) 粒子群算法的生物學(xué)基礎(chǔ)。如何根據(jù)群體進(jìn)行行為完善算法，將群體智能引入算法 中，借鑒生物群體進(jìn)化規(guī)則和進(jìn)化的智能性也是學(xué)者關(guān)注的問題。(4) 粒子群優(yōu)化算法與其他進(jìn)化類算法的比較研究。與其他

20、進(jìn)化算法的融合，如何讓將 其他進(jìn)化算法的優(yōu)點(diǎn)和粒子群優(yōu)化算法相結(jié)合， 構(gòu)造出有特色有實(shí)用價值的混合算法是當(dāng)前 算法改進(jìn)的一個重要方向。(5) 粒子群優(yōu)化算法的應(yīng)用。算法的有效性必須在應(yīng)用中才能體現(xiàn)，廣泛的開拓粒子群 優(yōu)化算法的應(yīng)用領(lǐng)域，也對深入研究粒子群優(yōu)化算法非常的有意義。參考文獻(xiàn)1 Kennedy J,Eberhart R.Particle Swarm optimizationC.In:IEEE Int 1 Conf on Neural Networks.Perth,Austraial,1995:1942-1948.2 Eberhart R,Kennedy J.A New Optimizer Using Particle Swarm TheoryC.In:Proc of t