自然計(jì)算模型系列之 粒子群( 魚群鳥群) 算法

先進(jìn)計(jì)算模型（2）自然計(jì)算模型系列之

粒子群（

魚群/鳥群）算法四川大學(xué)計(jì)算機(jī)學(xué)院2009博士生課程（遺傳算法，基因表達(dá)式編程，粒子群算法(PSO)，蟻群算法，魚群算法，….)唐常杰

四川大學(xué)計(jì)算機(jī)學(xué)院2023/9/271目錄，大致計(jì)劃第一次自然計(jì)算模型系列1：概述篇自然計(jì)算模型系列2粒子群（

魚群/鳥群）算法自然計(jì)算模型系列3基因表達(dá)式編程第二次自然計(jì)算模型系列4：模擬退火算法自然計(jì)算模型系列5：蟻群算法自然計(jì)算模型系列6：免疫計(jì)算模型（思路和比喻）下載URL:校園網(wǎng)和學(xué)院網(wǎng)

/~chjtang/teach/tang_teaching.htm7/~tangchangjie/teach/tang_teaching.htm2023/9/272今天

自然計(jì)算模型（NatureComputing)概述GEP基因表達(dá)式編程PSO

粒子群算法魚群鳥群算法下一次蟻群算法模擬退火算法人工免疫思想（比喻）

……

歡迎同學(xué)在下次發(fā)言（5-30分鐘均可）（如A先講，可跳至32頁）提綱2023/9/273資料出處和致謝參考資料：本PPT僅作和同學(xué)們?cè)谟懻摪鎯?nèi)交流之用參考了若干教科書，文獻(xiàn)和論文和報(bào)告。在末尾列出50多篇，但參考的文獻(xiàn)不只這些,主要是遺傳算法、基因表達(dá)式編程、粒子群算法的相關(guān)作者等等，包括國內(nèi)外，校內(nèi)外專家和本實(shí)驗(yàn)室成員的工作對(duì)未列出的文獻(xiàn)作者也在此一并致謝。參考文獻(xiàn)可能有遺漏，歡迎未列出的文獻(xiàn)作者及時(shí)指出，，以便即時(shí)在參考文獻(xiàn)中補(bǔ)充。作PPT類似于把小說改編為劇本，有重新創(chuàng)作的成分，也希望其它引用本PPT材料的標(biāo)注本PPT2023/9/274歡迎指正我們?cè)赑SO方面的工作不多，難免疏漏：我們?cè)赑SO方面的工作不多，可能有疏漏，歡迎指正：

1張培頌，唐常杰，丁鑫鑫，徐開闊,“基于劃分和重分布的粒子群算法及優(yōu)化策略”，四川大學(xué)學(xué)報(bào)（自然科學(xué)版）Vol.44,No.2pp312-315,2007.4，ZHANGPei-song,TANGChang-jie,DINGXin-xin,XUKai-kuo，“AnImprovedParticleSwarmOptimizationBasedonDivisionandRedistribution”，JournalofSichuanUniversity(NaturalScienceEdition),Vol.44,No.2pp312-315,2007.42蘇輝，唐常杰，喬少杰，徐開闊,張培頌，宋美嬌“基于搜索空間劃分和Sharing函數(shù)的粒子群優(yōu)化算法”，四川大學(xué)學(xué)報(bào)（自然科學(xué)版）Vol.44,No.5pp985-989,2007.10，SUHui,TANGChang-jie,QiaoShao-jie,XUKai-kuo，ZHANGPei-song,SongMei-jiao“AnImprovedParticleSwarmOptimizationBasedonSearchSpaceDivisionandSharingFunction”，JournalofSichuanUniversity(NaturalScienceEdition),Vol.44,No.5pp985-989,2007.103倪勝巧，唐常杰，曾旭晟，喬少杰,曾春秋，"EAMode:一種新的基于引擎粒子系統(tǒng)的圖像渲染模式",Vol.44No.6，Dec.2007.p1220-1224；NISheng-qiao，TANGChang-jie，ZENGXu-sheng，QIAOShao-jie，ZENGChun-qiu,"E&AMode:ANewModeforImageRomancingBasedonEngineParticlesSystem"，JournalofSichuanUniversity(NaturalScienceEdition),Vol.44No.6，Dec.2007.p1220-12244QihongLiu,TiandeLi,ChangjieTang,QiweiLiu,JunZhu,XinxinDing,JiangWu:TwoPhaseParallelParticleSwarmAlgorithmbasedonRegionalandSocialStudyofObjectOptimization.ThirdInternationalConferenceonNaturalComputation,ICNC2007,Vol.3,Aug.2007,p:827~831.EI5丁鑫鑫唐常杰曾濤張培頌徐開闊劉齊宏,基于最佳粒子共享和分層搜索的并行粒子群優(yōu)化算法tobepublished.2023/9/275課程計(jì)劃和特點(diǎn)有多位（7-8位）博士生導(dǎo)師作專題講座，每個(gè)老師講課8小時(shí)（大約需要準(zhǔn)備40—60小時(shí)）特點(diǎn)廣---N位導(dǎo)師，N=8~9,N+

個(gè)領(lǐng)域，M個(gè)課題，(M>N).“N家講座”，不敢比百家…新

---要求報(bào)告新技術(shù)前沿淺

–因?yàn)闀r(shí)間短，主要將思想，方法，介紹成果。不可能深入到公式和算法細(xì)節(jié)實(shí)---結(jié)合實(shí)際，結(jié)合博士生可能的選題2023/9/276

啟發(fā)式搜索的方法，用于解決那些屬于NP的比較困難的計(jì)算方法。對(duì)簡單問題，可以確定算法解決的（如解一元二次方程）不要用這些方法。下面看一個(gè)實(shí)例任務(wù)請(qǐng)兩同學(xué)去電腦城買一款性能價(jià)格比高的電腦啟發(fā)式規(guī)則：人多力量大，三個(gè)臭皮匠，賽過諸葛亮帶上上手機(jī)啟發(fā)式搜索及示例2023/9/277

啟發(fā)式搜索的方法，用于解決那些屬于NP的比較困難的計(jì)算方法。對(duì)簡單問題，可以確定算法解決的（如解一元二次方程）不要用這些方法。實(shí)例

請(qǐng)兩同學(xué)

去電腦海洋城

買一款指定性能，價(jià)格低的電腦啟發(fā)式規(guī)則：人多力量大，三個(gè)臭皮匠，賽過諸葛亮。

帶上上手機(jī)，互通消息啟發(fā)式搜索及示例2023/9/278“人多力量大”規(guī)則的啟發(fā)下搜索比喻：兩人帶手機(jī)到電腦海洋城選購機(jī)器，貨比多家

縱坐標(biāo)價(jià)格這樣搜索比窮舉搜索快，不一定最好，（沒有窮舉）但比較快，比較好實(shí)際上這是是N=2的PSO，有見廉思齊的機(jī)制2023/9/279鳥群算法其他應(yīng)用例子并發(fā)地搜山抓嫌疑人，并發(fā)地排查嫌疑人比喻，事件不同哲理同2023/9/2710

書歸正傳今天內(nèi)容PSO之一：ParticleSwarmOptimization

PSO算法國際網(wǎng)站http:///2023/9/2711PSO:特點(diǎn)

1可看成是遺傳算法家族的成員（或親戚）sharesmanysimilaritieswithevolutionarycomputationsuchasGeneticAlgorithms(GA).

initializedwithapopulationofrandomsolutionssearchesforoptimabyupdatinggenerations.愚公移山2PSO=GA–(交叉+簡單變異）+（見賢思齊的變異）unlikeGA,PSOhasnoevolutionoperatorssuchascrossoverandmutation.Solutions=particles,flythroughtheproblemspace

Byfollowingthecurrentoptimumparticles..緊跟頭鳥

2一種說法

：PSO是GA的特例，簡化,

后面看：是不是這樣？PSO

2023/9/2712簡介ParticleSwarmOptimization

解決優(yōu)化問題的方法

傳統(tǒng)搜尋方法如果問題是可計(jì)算，且是多項(xiàng)式復(fù)雜度的確定圖靈機(jī)，確定算法，（參見可計(jì)算理論課程）保證能找到最佳解HeuristicSearch

啟發(fā)性規(guī)則：有道理，不保證100%成功，可能含矛盾。三思而行（哪三思？危、變、退）當(dāng)斷不斷反受其亂如森林中下山沿小溪

兩條規(guī)則似乎矛盾2023/9/2713一種說法：一種說法：PSO=GA–(變異+交叉

)PSO是GA的特例，簡化在遺傳算法或GEP中去掉變異和交叉

后面看：是不是這樣？2023/9/2714PSO先驅(qū)

RussellEberhart

（羅素愛伯罕？）RussEberhartRussellEberharteberhart@2023/9/2715PSO先驅(qū)

JamesKennedy

（詹姆斯，肯尼迪？）JamesKennedyJamesKennedyKennedy_Jim@2023/9/2716PSO外師物化（啟發(fā)），內(nèi)得心源（靈感）生物學(xué)家對(duì)鳥(魚)群覓食的行為研究社會(huì)行為(Social-OnlyModel)認(rèn)知模型(Cognition-OnlyModel)什么行為？且看下頁分解2023/9/2717觀察家里魚缸：一條魚（當(dāng)前的帶頭魚，通常是老魚）發(fā)現(xiàn)食物

，其他的（通常是新魚）同伴能感知聲波,..養(yǎng)魚能發(fā)現(xiàn)算法，不是玩物喪志!

2023/9/2718問題魚群鳥群都是低智能動(dòng)物，人比魚群、鳥群高了很多層次，人群中高智能的計(jì)算機(jī)科學(xué)家去模擬低智能動(dòng)物，不是見賢思齊，而是，見低思齊，禮賢下”物“，值得嗎，有用嗎？答案值得?？聪旅婕?xì)細(xì)道來。2023/9/2719問題魚群鳥群都是低智能動(dòng)物，人比魚群、鳥群高了很多層次，人群中高智能的計(jì)算機(jī)科學(xué)家去模擬低智能動(dòng)物，不是見賢思齊，而是，見低思齊，禮賢下”物“，值得嗎，有用嗎？答案：值得。且看下面細(xì)細(xì)道來。2023/9/2720你們把觀察的現(xiàn)象形式化嗎？建立模型，抽象化，粒子群特性看看現(xiàn)象，你們把觀察的現(xiàn)象形式化嗎？提示：一群鳥在覓食2023/9/2721尋優(yōu)問題

解

想象成一只鳥(魚)，稱Particle每個(gè)Particle都有記憶性所有的Particle都透過FitnessFunction以判斷目前的位置之好壞每個(gè)Particle透過Velocity（速度）Function以決定移動(dòng)的距離與方向建立模型，抽象化，2023/9/2722鳥（魚）有記憶鳥（魚）能比較鳥（魚）可通訊（廣播）鳥（魚）會(huì)學(xué)習(xí)

向好鳥（魚）學(xué)習(xí)，見異思遷（有點(diǎn)貶義）見賢思齊從善如流

（褒義）

追尾行為，一條魚發(fā)現(xiàn)食物時(shí)，伙伴會(huì)尾隨算法思想：模擬鳥（魚）覓食、聚群和追尾行為寫論文時(shí)，寫觀察不需要證明，大多數(shù)情況下成立，能解決問題，就有用幾個(gè)觀察或假定2023/9/2723鳥（魚）有記憶鳥（魚）能比較鳥（魚）可通訊（廣播）鳥（魚）會(huì)學(xué)習(xí)

向好鳥（魚）學(xué)習(xí)，見異思遷（有點(diǎn)貶義）見賢思齊從善如流

（褒義）

追尾行為，一條魚發(fā)現(xiàn)食物時(shí)，伙伴會(huì)尾隨算法思想：模擬鳥（魚）覓食、聚群和追尾行為寫論文時(shí)，寫觀察不需要證明，大多數(shù)情況下成立，能解決問題，就有用幾個(gè)觀察或假定2023/9/2724算法思想模擬鳥（魚）覓食、聚群和追尾行為找食不如找?guī)ь^鳥（動(dòng)態(tài)帶頭鳥，可罷免、重選），追隨領(lǐng)袖（或鄰域中領(lǐng)袖，部落酋長）跟蹤兩個(gè)“極值”來更新自己。

自己的經(jīng)驗(yàn)：自己歷史上最優(yōu)解個(gè)體極值pBest.

全局經(jīng)驗(yàn)和部落經(jīng)驗(yàn)：gBest。另（鄰居極值）向領(lǐng)袖學(xué)習(xí)，見賢思齊，從善如流，不斷更新自己2023/9/2725鳥（魚）有記憶鳥（魚）能比較向好鳥（魚）學(xué)習(xí)，見異思遷，從善如流寫論文時(shí)，寫觀察不需要證明，觀察結(jié)論在大多數(shù)情況下成立，能解決以大批問題，有用從觀察到理論，是實(shí)驗(yàn)科學(xué)的研究方法三個(gè)觀察或假定2023/9/2726分隔規(guī)則，盡量避免與臨近伙伴過于擁擠對(duì)準(zhǔn)規(guī)則，盡量與臨近伙伴的平均方向一致；內(nèi)聚規(guī)則，盡量朝臨近伙伴的中心移動(dòng)。追尾行為當(dāng)魚群中的一條或幾條魚發(fā)現(xiàn)食物時(shí)，其臨近的伙伴會(huì)尾隨其快速到達(dá)食物點(diǎn)。更多的觀察或假定2023/9/2727PSO的主要步驟

遺傳算法-編譯-交叉Initialize

初始化Evaluation評(píng)價(jià)FindthePbest

單個(gè)粒子迄今最佳位置（有歷史觀）FindtheGbest

UpdatethePosition

更新回到Evaluation繼續(xù)執(zhí)行，符合終止條件成立2023/9/2728PSO的主要步驟

遺傳算法-編譯-交叉Initialize

初始化Evaluation評(píng)價(jià)FindthePbest

單個(gè)粒子迄今最佳位置（有歷史觀）FindtheGbest

UpdatethePosition

更新回到Evaluation繼續(xù)執(zhí)行，符合終止條件成立2023/9/2729PSO的主要步驟

遺傳算法-編譯-交叉Initialize

初始化Evaluation評(píng)價(jià)FindthePbest

單個(gè)粒子迄今最佳位置（有歷史觀）FindtheGbest

UpdatethePosition

更新回到Evaluation繼續(xù)執(zhí)行，符合終止條件成立2023/9/2730PSO的主要步驟

遺傳算法-編譯-交叉Initialize

初始化Evaluation評(píng)價(jià)FindthePbest

單個(gè)粒子迄今最佳位置（有歷史觀）FindtheGbest

UpdatethePosition

更新回到Evaluation繼續(xù)執(zhí)行，符合終止條件成立2023/9/2731PSO的主要步驟

遺傳算法-編譯-交叉Initialize

初始化Evaluation評(píng)價(jià)FindthePbest

單個(gè)粒子迄今最佳位（有歷史）FindtheGbest

UpdatethePosition

更新循環(huán)到Evaluation，知道符合終止條件成立2023/9/2732PSO的初始化隨機(jī)設(shè)置每Particle之初始位置與速度2023/9/2733PSO的適應(yīng)度評(píng)價(jià)用

FitnessFunction計(jì)算出其FitnessValue判斷每一Particle之好壞初步印象：技術(shù)比GEP簡單，功能能可能也差一些）2023/9/2734FindthePbest—單個(gè)粒子優(yōu)化找出每個(gè)Particle到目前為止的搜尋過程中最佳解（迄今的覓食的最佳速度和位置，鳥能記憶和比較），稱為PbestP--pastPastBestSolution注意這里局部優(yōu)化2023/9/2735FindtheGbest高度表示得分多少。山峰處得分高找出所有Particle到目前為止全局最優(yōu)解，記為GbestGlobalBestSolutionPastBestSolution注意這里2023/9/2736PSO更新

（相當(dāng)于遺傳算法的新的一代，進(jìn)化）更新位置(從善若流，與時(shí)俱進(jìn)，調(diào)整自己）依VelocityFunction更新每Particle的移動(dòng)方向與速度回Evaluation步驟繼續(xù)，直到符合終止條件2023/9/2737PSO流程（與遺傳算法相比，少了變異和交叉）比喻為遺傳算法的新生一代，相當(dāng)于鳳凰涅槃2023/9/2738PSOVelocityFunction

速度函數(shù)的構(gòu)成Cognition-OnlyModelPSOVelocityFunctionSocial-OnlyModel||+兩個(gè)分量主觀的客觀的2023/9/2739插曲：一個(gè)有趣的比喻三國時(shí)，群雄并起，很多粒子：曹操，孫權(quán)，類被，袁紹….，他們要覓食（地盤和資源）許邵評(píng)論曹操用了一個(gè)先天歧義的句子兩個(gè)分量都有a3許邵評(píng)曹操：亂世奸雄治世能臣

亂世奸雄治世能臣現(xiàn)在回到PSO現(xiàn)實(shí)中狀語：表達(dá)客觀條件（社會(huì)模型）決定人人生動(dòng)賓結(jié)構(gòu)：表達(dá)主觀愿望（認(rèn)知模型）決定人生2023/9/2740插曲：一個(gè)有趣的比喻三國時(shí)，群雄并起，很多粒子：曹操，孫權(quán)，類被，袁紹….，他們要覓食（地盤和資源）許邵評(píng)論曹操用了一個(gè)先天歧義的句子兩個(gè)分量都有a3許邵評(píng)曹操：亂世奸雄治世能臣

亂世奸雄治世能臣問題：能否用他描述或部分地描述三國群英？難，要簡化模型現(xiàn)在回到PSO現(xiàn)實(shí)中狀語：表達(dá)客觀條件（社會(huì)模型）決定人人生動(dòng)賓結(jié)構(gòu)：表達(dá)主觀愿望（認(rèn)知模型）決定人生2023/9/2741PSOVelocityFunction（后面有動(dòng)畫演示）認(rèn)知模型Cognition-OnlyModelVid：第i個(gè)particle(有d個(gè)維度)之速度Pid：該

particle到目前為止所出現(xiàn)的最佳位置Xid：該

particle目前之所在位置C1：學(xué)習(xí)常數(shù)rand()：0~1之間的隨機(jī)數(shù)速度的增量旨在彌補(bǔ)與先進(jìn)的差距與先進(jìn)的差距2023/9/2742社會(huì)模型Social-OnlyModelVid：第i個(gè)particle(有d個(gè)維度)之速度Pgd：所有

particle到目前為止所出現(xiàn)的最佳位置Xid：該

particle目前之所在位置C2：學(xué)習(xí)常數(shù)rand()：0~1之間的隨機(jī)數(shù)PSOVelocityFunction（后面有動(dòng)畫演示）速度的增量旨在彌補(bǔ)與先進(jìn)的差距與先進(jìn)的差距與上頁不同點(diǎn)2023/9/2743

Vid：第i個(gè)particle(d維)速度

Pid：每個(gè)particle迄今出現(xiàn)的最佳位置

Pgd：所有particle迄今最佳位置

Xid：每個(gè)particle目前位置 C1,C2：學(xué)習(xí)常數(shù)

w：慣性權(quán)重 rand()：0~1之間隨機(jī)數(shù)PSOVelocityFunction（后面有動(dòng)畫演示）個(gè)體認(rèn)知模型（主觀）社會(huì)模型（客觀）2023/9/2744區(qū)域最佳解全域最佳解運(yùn)動(dòng)向量慣性向量動(dòng)畫演示動(dòng)能向量

StudyFactorHereIam!ThebestpositionofteamMybestpositionxpgpivPBestgBest2023/9/2745鳥（魚）有記憶鳥（魚）能比較，會(huì)總結(jié)向好鳥（魚）學(xué)習(xí)，見賢思齊不但從善如流，還能統(tǒng)籌兼顧局部經(jīng)驗(yàn)和全局經(jīng)驗(yàn)上頁的演示確實(shí)說明了這三點(diǎn)（必要時(shí)重新演示一次）復(fù)習(xí)：三個(gè)觀察或假定2023/9/2746鳥（魚）有記憶鳥（魚）能比較，會(huì)總結(jié)向好鳥（魚）學(xué)習(xí)，從善如流不但從善如流，還能統(tǒng)籌兼顧局部經(jīng)驗(yàn)和全局經(jīng)驗(yàn)上頁的演示確實(shí)說明了這三點(diǎn)（必要時(shí)重新演示一次）復(fù)習(xí)：三個(gè)觀察或假定2023/9/2747PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebest fitness2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEnd

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

初始化計(jì)算個(gè)體適應(yīng)度總結(jié)，自己縱向比較2023/9/2748PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebest fitness2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEnd

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

吸取歷史經(jīng)驗(yàn)計(jì)算個(gè)體適應(yīng)度總結(jié)，自己縱向比較，2023/9/2749PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebestfitness

2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEnd

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

橫向比較，找適應(yīng)度最好的鄰居或部落領(lǐng)袖見賢思齊2023/9/2750PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebestfitness

2)Calculate

particlevelocityaccordingtothevelocityfunction

3)Updateparticlepositionaccordingtot