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

1、粒子群優(yōu)化算法粒子群優(yōu)化算法 背景背景 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv l人工生命：研究具有某些生命基本特征的人 l 工系統(tǒng)。包括兩方面的內(nèi)容： l1、研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象； l2、 研究如何利用生物技術(shù)研究計(jì)算問(wèn)題。 l 我們關(guān)注的是第二點(diǎn)。 l已有很多源于生物現(xiàn)象的計(jì)算技巧，例如神 l經(jīng)網(wǎng)絡(luò)和遺傳算法。 l現(xiàn)在討論另一種生物系統(tǒng)-社會(huì)系統(tǒng)：由簡(jiǎn) l單個(gè)體組成的群落和環(huán)境及個(gè)體之間的相互 l行為。 l 算法介紹算法介紹 iii xxv 12 () ()() () iiii

2、ii vvcrandpbestxcrandgbestx iii xxv l群智能(swarm intelligence) l 模擬系統(tǒng)利用局部信息從而可以產(chǎn)生不可 預(yù)測(cè)的群行為。 l 我們經(jīng)常能夠看到成群的鳥(niǎo)、魚(yú)或者浮游 生物。這些生物的聚集行為有利于它們覓食 和逃避捕食者。它們的群落動(dòng)輒以十、百、 千甚至萬(wàn)計(jì)，并且經(jīng)常不存在一個(gè)統(tǒng)一的指 揮者。它們是如何完成聚集、移動(dòng)這些功能 呢？ l 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv l millonas在開(kāi)發(fā)人工生命算法時(shí)(1994年) ，提出群體

3、智能概念并提出五點(diǎn)原則： l 1、接近性原則：群體應(yīng)能夠?qū)崿F(xiàn)簡(jiǎn)單的時(shí)空計(jì)算； l 2、優(yōu)質(zhì)性原則：群體能夠響應(yīng)環(huán)境要素； l 3、變化相應(yīng)原則：群體不應(yīng)把自己的活動(dòng)限制在一狹 l 小范圍； l 4、穩(wěn)定性原則：群體不應(yīng)每次隨環(huán)境改變自己的模 l 式； l 5、適應(yīng)性原則：群體的模式應(yīng)在計(jì)算代價(jià)值得的時(shí)候 l 改變。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv l 社會(huì)組織的全局群行為是由群內(nèi)個(gè)體行為以非 線(xiàn)性方式出現(xiàn)的。個(gè)體間的交互作用在構(gòu)建群行 為中起到重要的作用。 l 從不同的群研究得到不同的

4、應(yīng)用。最引人注目 的是對(duì)蟻群和鳥(niǎo)群的研究。 l 其中粒群優(yōu)化方法就是模擬鳥(niǎo)群的社會(huì)行為發(fā) 展而來(lái)。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 對(duì)鳥(niǎo)群行為的模擬：對(duì)鳥(niǎo)群行為的模擬： reynoldsreynolds、heppnerheppner和和grenadergrenader提出鳥(niǎo)群行為的提出鳥(niǎo)群行為的 模擬。他們發(fā)現(xiàn)，鳥(niǎo)群在行進(jìn)中會(huì)突然同步的改模擬。他們發(fā)現(xiàn)，鳥(niǎo)群在行進(jìn)中會(huì)突然同步的改 變方向，散開(kāi)或者聚集等。那么一定有某種潛在變方向，散開(kāi)或者聚集等。那么一定有某種潛在 的能力或規(guī)則保證了這

5、些同步的行為。這些科學(xué)的能力或規(guī)則保證了這些同步的行為。這些科學(xué) 家都認(rèn)為上述行為是基于不可預(yù)知的鳥(niǎo)類(lèi)社會(huì)行家都認(rèn)為上述行為是基于不可預(yù)知的鳥(niǎo)類(lèi)社會(huì)行 為中的群體動(dòng)態(tài)學(xué)。為中的群體動(dòng)態(tài)學(xué)。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 對(duì)魚(yú)群行為的研究：對(duì)魚(yú)群行為的研究： 生物社會(huì)學(xué)家生物社會(huì)學(xué)家e.o.wilsone.o.wilson對(duì)魚(yú)群進(jìn)行了研究。對(duì)魚(yú)群進(jìn)行了研究。 提出：提出：“至少在理論上至少在理論上，魚(yú)群的個(gè)體成員能夠魚(yú)群的個(gè)體成員能夠 受益于群體中其他個(gè)體在尋找食物的過(guò)程中的受益于群體

6、中其他個(gè)體在尋找食物的過(guò)程中的 發(fā)現(xiàn)和以前的經(jīng)驗(yàn)，這種受益超過(guò)了個(gè)體之間發(fā)現(xiàn)和以前的經(jīng)驗(yàn)，這種受益超過(guò)了個(gè)體之間 的競(jìng)爭(zhēng)所帶來(lái)的利益消耗，不管任何時(shí)候食物的競(jìng)爭(zhēng)所帶來(lái)的利益消耗，不管任何時(shí)候食物 資源不可預(yù)知的分散。資源不可預(yù)知的分散。”這說(shuō)明，同種生物之這說(shuō)明，同種生物之 間信息的社會(huì)共享能夠帶來(lái)好處。這是間信息的社會(huì)共享能夠帶來(lái)好處。這是psopso的的 基礎(chǔ)。基礎(chǔ)。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv l l 粒子群優(yōu)化算法（pso）是一種進(jìn)化計(jì)算技術(shù)（ evolutionary c

7、omputation）,由eberhart博士和 kennedy博士于1995年提出 (kennedy j，eberhart r l particle swarm optimizationproceedings of the ieee international conference on neural networks199519421948.) 。源于對(duì)鳥(niǎo)群捕食的行為研究。粒子群優(yōu)化算法的 基本思想是通過(guò)群體中個(gè)體之間的協(xié)作和信息共 享來(lái)尋找最優(yōu)解 l pso的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參 數(shù)的調(diào)節(jié)。目前已被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng) 網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng) 用領(lǐng)域

8、。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 算法介紹算法介紹 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 算法介紹算法介紹 iii xxv 12 ()

9、 ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcran

10、dgbestx 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx ( ) ()()/ t iniendkkend ggg 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv 算法介紹算法介紹 根據(jù)具體問(wèn)題一般選為最大迭代根據(jù)具體問(wèn)題一般選為最大迭代 次數(shù)次數(shù)g gk k或或( (和和) )微粒群迄今為止搜索到的最優(yōu)位置微粒群迄今為止搜索到的最優(yōu)位置 滿(mǎn)足預(yù)定最小適應(yīng)閾值滿(mǎn)足預(yù)定最小適應(yīng)閾值。 算法介紹算法介紹 ii

11、i xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 局部和全局最優(yōu)算法局部和全局最優(yōu)算法 2 () () iiii vvcrandgbestx 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 當(dāng)當(dāng)c20時(shí)，則粒子之間沒(méi)有社會(huì)信息，模型變?yōu)闀r(shí)，則粒子之間沒(méi)有社會(huì)信息，模型變?yōu)?只有認(rèn)知只有認(rèn)知(cognition-only)模型：模型： 被稱(chēng)為局部被稱(chēng)為局部pso算法。由于個(gè)體之間沒(méi)有信息的算法。由于個(gè)體之間沒(méi)有信息的 交流，整個(gè)群體相

12、當(dāng)于多個(gè)粒子進(jìn)行盲目的隨機(jī)交流，整個(gè)群體相當(dāng)于多個(gè)粒子進(jìn)行盲目的隨機(jī) 搜索，收斂速度慢，因而得到最優(yōu)解的可能性小。搜索，收斂速度慢，因而得到最優(yōu)解的可能性小。 局部和全局最優(yōu)算法局部和全局最優(yōu)算法 1 () () iiii vvcrandpbestx 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 參數(shù)分析參數(shù)分析 最大速度最大速度決定當(dāng)前位置與最好位置之間的區(qū)域的決定當(dāng)前位置與最好位置之間的區(qū)域的 分辨率分辨率( (或精度或精度) )。如果太快，則粒子有可能越過(guò)極小。如果太快，則粒子有可能越過(guò)極小

13、點(diǎn)點(diǎn); ;如果太慢，則粒子不能在局部極小點(diǎn)之外進(jìn)行足如果太慢，則粒子不能在局部極小點(diǎn)之外進(jìn)行足 夠的探索，會(huì)陷入到局部極值區(qū)域內(nèi)。這種限制可以夠的探索，會(huì)陷入到局部極值區(qū)域內(nèi)。這種限制可以 達(dá)到防止計(jì)算溢出、決定問(wèn)題空間搜索的粒度的目的。達(dá)到防止計(jì)算溢出、決定問(wèn)題空間搜索的粒度的目的。 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 權(quán)重因子權(quán)重因子 包括慣性因子包括慣性因子 和學(xué)習(xí)因子和學(xué)習(xí)因子c1c1和和c2c2。 使粒子使粒子 保持著運(yùn)動(dòng)慣性，使其具有擴(kuò)展搜索空間的趨勢(shì)，有保持著運(yùn)動(dòng)慣性，使其具

14、有擴(kuò)展搜索空間的趨勢(shì)，有 能力探索新的區(qū)域。能力探索新的區(qū)域。c1c1和和c2c2代表將每個(gè)粒子推向代表將每個(gè)粒子推向pbestpbest 和和gbestgbest位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)值。較低的值允許粒子位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)值。較低的值允許粒子 在被拉回之前可以在目標(biāo)區(qū)域外徘徊，較高的值導(dǎo)致粒在被拉回之前可以在目標(biāo)區(qū)域外徘徊，較高的值導(dǎo)致粒 子突然地沖向或越過(guò)目標(biāo)區(qū)域。子突然地沖向或越過(guò)目標(biāo)區(qū)域。 參數(shù)分析參數(shù)分析 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 參數(shù)分析參數(shù)分析 算法介紹算法介紹 i

15、ii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 參數(shù)分析參數(shù)分析 12 ()()()() iiiiii vk vrandpbestxrandgbestx 12 2 2 ,4. 24 k 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 參數(shù)分析參數(shù)分析 算法介紹算法介紹 iii xxv iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx 離散二進(jìn)制離散二進(jìn)制pso 12 ()

16、 ()() () iiiiii vvcrandpbestxcrandgbestx 1 i x 0 i x 其中其中 1 ( ) 1 exp() i i s v v 為為sigmoid函數(shù)函數(shù) 2 ()( ) i if rands v 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv psopso和其他算法和其他算法 1、遺傳算法和、遺傳算法和pso的比較的比較 共性共性: (1) 都屬于仿生算法。都屬于仿生算法。 (2) 都屬于全局優(yōu)化方法。都屬于全局優(yōu)化方法。 (3) 都屬于隨機(jī)搜索算法。都屬于隨機(jī)搜

17、索算法。 (4) 都隱含并行性。都隱含并行性。 (5) 根據(jù)個(gè)體的適配信息進(jìn)行搜索，因此不受函數(shù)根據(jù)個(gè)體的適配信息進(jìn)行搜索，因此不受函數(shù) 約束條件的限制，如連續(xù)性、可導(dǎo)性等。約束條件的限制，如連續(xù)性、可導(dǎo)性等。 (6) 對(duì)高維復(fù)雜問(wèn)題，往往會(huì)遇到早熟收斂和收斂對(duì)高維復(fù)雜問(wèn)題，往往會(huì)遇到早熟收斂和收斂 性能差的缺點(diǎn)，都無(wú)法保證收斂到最優(yōu)點(diǎn)。性能差的缺點(diǎn)，都無(wú)法保證收斂到最優(yōu)點(diǎn)。 pso和其他算法和其他算法 l差異： l(1) pso有記憶，好的解的知識(shí)所有粒子都保 存，而ga，以前的知識(shí)隨著種群的改變被改變 。 l(2) pso中的粒子僅僅通過(guò)當(dāng)前搜索到最優(yōu)點(diǎn)進(jìn) 行共享信息，所以很大程度上這是一

18、種單共享 項(xiàng)信息機(jī)制。而ga中，染色體之間相互共享信 息，使得整個(gè)種群都向最優(yōu)區(qū)域移動(dòng)。 l(3) ga的編碼技術(shù)和遺傳操作比較簡(jiǎn)單，而 pso l 相對(duì)于ga，沒(méi)有交叉和變異操作，粒子只 是通過(guò)內(nèi)部速度進(jìn)行更新，因此原理更簡(jiǎn)單、 參數(shù)更少、實(shí)現(xiàn)更容易。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv psopso和其他算法和其他算法 ga可以用來(lái)研究可以用來(lái)研究nn的三個(gè)方面：網(wǎng)絡(luò)連接權(quán)重、網(wǎng)絡(luò)的三個(gè)方面：網(wǎng)絡(luò)連接權(quán)重、網(wǎng)絡(luò) 結(jié)構(gòu)、學(xué)習(xí)算法。優(yōu)勢(shì)在于可處理傳統(tǒng)方法不能處理的結(jié)構(gòu)、學(xué)習(xí)算法。優(yōu)勢(shì)在于可

19、處理傳統(tǒng)方法不能處理的 問(wèn)題，例如不可導(dǎo)的節(jié)點(diǎn)傳遞函數(shù)或沒(méi)有梯度信息。問(wèn)題，例如不可導(dǎo)的節(jié)點(diǎn)傳遞函數(shù)或沒(méi)有梯度信息。 缺點(diǎn)缺點(diǎn):在某些問(wèn)題上性能不是特別好；網(wǎng)絡(luò)權(quán)重的編碼和在某些問(wèn)題上性能不是特別好；網(wǎng)絡(luò)權(quán)重的編碼和 遺傳算子的選擇有時(shí)較麻煩。遺傳算子的選擇有時(shí)較麻煩。 已有利用已有利用pso來(lái)進(jìn)行神經(jīng)網(wǎng)絡(luò)訓(xùn)練。研究表明來(lái)進(jìn)行神經(jīng)網(wǎng)絡(luò)訓(xùn)練。研究表明pso是一是一 種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。速度較快且有較好的結(jié)果。種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。速度較快且有較好的結(jié)果。 且沒(méi)有遺傳算法碰到的問(wèn)題。且沒(méi)有遺傳算法碰到的問(wèn)題。 算法介紹算法介紹 iii xxv 12 () ()() () iiiiii vvcrandpbestxcrandgbestx iii xxv l有關(guān)的國(guó)際會(huì)議 lants l international workshop on ant colony optimization and swarm intelligenc