群體智能第二講

群體智能第二講第1頁，共46頁，2023年，2月20日，星期六粒子群優(yōu)化

第2頁，共46頁，2023年，2月20日，星期六粒子群優(yōu)化粒子群優(yōu)化（ParticleSwarmOptimization,簡稱PSO）[1]，又稱為微粒群算法，是由美國的心理學家J.Kennedy和電氣工程師R.Eberhart于1995年提出的一種算法。[1]J.KennedyandR.Eberhart.“ParticleSwarmOptimization,”ProceedingsofIEEEInternationalConferenceonNeuralNetworks,Perth,WA,1995,pp.1942-1948.PSO是模擬鳥群飛行覓食行為的一種隨機優(yōu)化算法。第3頁，共46頁，2023年，2月20日，星期六Kennedy和Eberhart的初衷是研究鳥的覓食行為，建立一個模型來模擬鳥群尋找食源的現(xiàn)象。Kennedy和Eberhart在實驗中發(fā)現(xiàn)，這個模型有很強的優(yōu)化能力。第4頁，共46頁，2023年，2月20日，星期六PSO原理將問題的搜索空間類比于鳥類的飛行空間。將每一只鳥抽象為一個無質量無體積的微粒（Particle)，用于表征每個候選解。

優(yōu)化尋求最優(yōu)解等同于鳥群尋找食物。PSO為每個微粒制定了類似于鳥類運動的簡單行為規(guī)則，從而使整個微粒群的運動表現(xiàn)出與鳥類覓食類似的特性，用于求解復雜優(yōu)化問題。第5頁，共46頁，2023年，2月20日，星期六PSO原理單個微粒，代表一個解微粒群體微粒位置和速度的更新策略PSO單個鳥整個鳥群鳥群尋找食物的飛行策略鳥群行為PSO是對鳥群尋找食物這種群體行為的模擬第6頁，共46頁，2023年，2月20日，星期六PSO算法每個粒子有一個位置和一個速度。粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優(yōu)解，即pBest；另一個是整個種群的最優(yōu)解，即gBest。鳥群怎樣盡量快的找到食物？一個有效的方法就是搜尋目前離食物最近同伴的位置。第7頁，共46頁，2023年，2月20日，星期六PSO算法假設搜索空間為d維，群體（Swarm）中的粒子數(shù)為n。在第t次迭代中，群體中第i個粒子的位置表示為：第i個粒子在飛行中所經(jīng)過的最佳位置為：群體中所有粒子的中最佳位置為：第i個粒子的位置變化速度為：第8頁，共46頁，2023年，2月20日，星期六PSO算法每個粒子的位置按如下公式變化：其中和為[0,1]間的隨機數(shù)；和為加速系數(shù)，用來控制和對粒子飛行方向的影響。若粒子i的位置的第j維超過范圍，則取邊界值。若粒子i的速度的第j維超過范圍，則取邊界值。第9頁，共46頁，2023年，2月20日，星期六PSO算法速度沖量認知項社會項微粒速度更新公式包括三項:速度沖量：指引微粒繼續(xù)飛行的先前微粒速度。認知項：微粒重新返回其所經(jīng)過的最好位置的趨勢，既微粒本身記憶的影響。社會項：微粒被當前最好位置吸引的趨勢，既群體信息的影響。在三部分的共同作用下，微粒根據(jù)歷史經(jīng)驗并利用全局信息，不斷調(diào)整自己的位置，以期找到最優(yōu)解。第10頁，共46頁，2023年，2月20日，星期六1.在搜索空間中隨機生成n個微粒，組成微粒群;2.重復下列步驟：for(i=1ton)計算微粒i的適應值；ifthenfor(j=1tod)//d為決策變量維數(shù)按公式更新微粒i的第j個分量；endend3.如果滿足終止條件，那么終止算法，并輸出結果.

取值為適應值最高的;//更新微粒全局最優(yōu)點PSO算法第11頁，共46頁，2023年，2月20日，星期六PSO算法慣性權重速度沖量導致微粒按照先前速度方向繼續(xù)移動。YuhuiShi[1]提出一個慣性權重w來控制先前微粒速度的影響。[1]Y.Shi,R.Eberhart.“Amodifiedparticleswarmoptimizer,”ProceedingsofIEEEWorldCongressonComputationalIntelligence,Anchorage,AK,1998,pp.69-73.慣性權重第12頁，共46頁，2023年，2月20日，星期六PSO算法通過調(diào)節(jié)w值，可以控制PSO的全局探索和局部開發(fā)能力：

w≥1：微粒速度隨迭代次數(shù)的增加而增加，微粒發(fā)散。0<w<1：微粒減速，算法的收斂性依靠慣性權重和。

w<0：微粒速度隨迭代次數(shù)的增加而減小，最后趨近0，算法收斂。實驗表明，w=0.7298和時算法具有較好的收斂性能。

自適應或動態(tài)慣性權重值：Eberhart和Shi：w的線性遞減策略；Shi和Eberhart：以當前慣性權重值和當前算法最優(yōu)值為模糊系統(tǒng)的輸入，給出一種慣性權重的模糊控制方法。第13頁，共46頁，2023年，2月20日，星期六加速度系數(shù)加速度系數(shù)，又稱學習因子，用來控制和對微粒飛行方向的影響。每個微粒執(zhí)行局部搜索；微粒群轉化為一個隨機爬山法；微粒逐漸移向和的加權均值；算法比較適合于單峰優(yōu)化問題；算法比較適合于多峰優(yōu)化問題。加速度系數(shù)加速度系數(shù)第14頁，共46頁，2023年，2月20日，星期六PSO算法PSO中粒子的位置更新第15頁，共46頁，2023年，2月20日，星期六壓縮因子Clerc和Kennedy[1]建議把壓縮因子引入微粒速度更新公式：壓縮因子其中，通常，，壓縮因子。[1]M.ClercandJ.Kennedy,“Theparticleswarm—explosion,stability,andconvergenceinamultidimensionalcomplexspace,”IEEETransactionsonEvolutionaryComputation,2002,vol.6,no.1,pp.58-73.第16頁，共46頁，2023年，2月20日，星期六PSO的拓撲結構

全局PSO：群體中每個微粒跟蹤的兩個極值為自身最佳位置（pbest與群體最佳位置gbest。

局部PSO：每個微粒跟蹤自身最佳位置pbest，不跟蹤群體的最佳位置，而是跟蹤其拓撲鄰域中所有K個微粒的最佳位置lbest，其速度更新如下：為局部鄰域最佳位置。有兩類PSO：第17頁，共46頁，2023年，2月20日，星期六拓撲結構：全連接拓撲，即受gbest影響環(huán)形拓撲，K=2,僅受與其緊鄰的兩個粒子的影響第18頁，共46頁，2023年，2月20日，星期六拓撲結構：星狀拓撲(star)VonNeumann拓撲錐形拓撲(pyramid)四聚類拓撲(clusters)第19頁，共46頁，2023年，2月20日，星期六全連接拓撲信息傳輸速度快，相應地，PSO算法收斂速度快，但是易于早熟收斂。環(huán)形拓撲信息傳輸速度最慢，相應地，PSO算法收斂速度慢，但是微粒有更多的機會發(fā)現(xiàn)最優(yōu)解。Mendes和Kennedy(2002)在對比不同拓撲結構時發(fā)現(xiàn)：VonNeumann拓撲優(yōu)于其它拓撲。

Suganthan(1999)在PSO算法初期采用局部PSO,后期采用全局版PSO;

Hu和Eberhart(2002)提出了動態(tài)拓撲結構的概念。每次迭代時選擇與當前微粒最近的m個微粒作為它的新鄰域。第20頁，共46頁，2023年，2月20日，星期六PSO的收斂性

VandenBergh(2002)、Trelea(2003)以及Bergh和Engelbrecht(2006)已經(jīng)證明PSO能夠收斂到一個平衡狀態(tài)。那么，對于全局版PSO算法，如果這意味著隨著迭代次數(shù)的增加所有微粒將收斂到一個點。但是，這不意味著微粒個體最優(yōu)點和全局最優(yōu)點的加權和就是問題的最優(yōu)解。第21頁，共46頁，2023年，2月20日，星期六PSO的收斂性如果式中，那么，微粒僅依靠更新其位置。進一步，如果上述狀態(tài)持續(xù)足夠代數(shù)后,那么

因此，有進一步解釋：事實上，存在微粒群收斂到局部穩(wěn)定點的可能。該局部穩(wěn)定點不是問題的全局最優(yōu)點，甚至不是問題的局部最優(yōu)點。第22頁，共46頁，2023年，2月20日，星期六PSO的收斂性部分典型方法:DissipativePSO(Xie,etal.,2002)----增加微粒群的多樣性;PSOwithmutation(Stacey,etal.,2004)----重新初始化已經(jīng)收斂的微粒;PSOwithpassivecongregation(Heetal.,2004)----提高微粒群的多樣性;Speciation-basedPSO(Lietal.,2006)----根據(jù)微粒之間相似程度，把整個微粒群劃分為若干類。Self-organizingPSO(Ratnaweera,etal.2004)----改進算法的控制參數(shù);Multi-swarmparallelPSO,MPPSO(BelalMetal.,2004)-----利用多種群思想。防止所有或者部分微粒長期接近微粒的全局最優(yōu)點，即第23頁，共46頁，2023年，2月20日，星期六PSO的收斂性一些方法：差分算法(DifferentialEvolution,DE)(ZhangandXie,2003)遺傳算法(Geneticalgorithm,GA)(Matthewetal.,2005);爬山法;模擬退火(Simulatedannealing,SA)(NasserSadatietal.,2006);單純形法(Simplexmethod,SM)(FanSKetal.,2007).利用具有較強局部搜索能力的算法進一步細化/開發(fā)PSO所得結果。第24頁，共46頁，2023年，2月20日，星期六二進制PSO最初的PSO算法是從處理連續(xù)優(yōu)化問題中發(fā)展起來的。Kennedy和Eberhart[1]首次將實數(shù)PSO擴展為二進制PSO。微粒位置為二進制向量，微粒速度仍為浮點向量；微粒速度被邏輯函數(shù)s(v)轉化為判斷位置項選擇0還是1的概率。[1]J.Kennedy,R.C.Eberhart.“Adiscretebinaryversionoftheparticleswarmalgorithm,”ProceedingsofInternationalConferenceonSystem,Man,andCybernetics,1997,Orlando,FL,pp.4104-4109.第25頁，共46頁，2023年，2月20日，星期六二進制PSO為了防止s(v)飽和，Kennedy等建議將限制在[-4,4]之間。其中更新公式如下：第26頁，共46頁，2023年，2月20日，星期六PSO與遺傳算法的區(qū)別遺傳算法強調(diào)“適者生存”，不好的個體在競爭中被淘汰；PSO強調(diào)“協(xié)同合作”，不好的個體通過學習向好的方向轉變。遺傳算法中最好的個體通過產(chǎn)生更多的后代來傳播基因；PSO中的最好個體通過吸引其它個體向它靠近來施加影響。遺傳算法的選擇概率只與上一代群體相關，而與歷史無關，群體的信息變化過程是一個Markov鏈過程；而PSO中的個體除了有位置和速度外，還有著過去的歷史信息（pBest、gBest）。第27頁，共46頁，2023年，2月20日，星期六PSO的優(yōu)點和缺點優(yōu)點：易于實現(xiàn)；可調(diào)參數(shù)較少；所需種群或微粒群規(guī)模較??；計算效率高，收斂速度快。缺點：基本PSO雖然收斂速度快，但有時會陷入局部最優(yōu)。第28頁，共46頁，2023年，2月20日，星期六PSO改進研究位置和速度更新公式多種群PSO種群拓撲結構與其他智能優(yōu)化算法的混合拓展PSO算法用于：多目標優(yōu)化約束優(yōu)化離散優(yōu)化動態(tài)優(yōu)化第29頁，共46頁，2023年，2月20日，星期六所用的測試函數(shù)（幾個例子）SchafferGriewankAckleyRastrigin第30頁，共46頁，2023年，2月20日，星期六函數(shù)優(yōu)化——數(shù)值函數(shù)優(yōu)化，動態(tài)、多峰值、多目標優(yōu)化組合優(yōu)化——旅行商問題、車輛路由問題、布局優(yōu)化問題等生產(chǎn)調(diào)度——工件加工問題自動控制——智能控制器優(yōu)化、最優(yōu)控制器的設計機器人學——路徑規(guī)劃、協(xié)調(diào)控制機器學習——分類、聚類、數(shù)據(jù)挖掘圖像處理——圖像識別、檢測機械設計——形狀、結構、參數(shù)的設計神經(jīng)網(wǎng)絡訓練系統(tǒng)參數(shù)辨識等PSO應用研究第31頁，共46頁，2023年，2月20日，星期六PSO用于交通事故分析提出一種基于K-mean聚類全局引導的多目標PSO用于交通事故分析。

用該PSO來發(fā)現(xiàn)關聯(lián)規(guī)則，以此尋求與交通事故嚴重程度相關聯(lián)的因素。文獻：ChenyeQiu,ChunluWang,BinxingFang,XingquanZuo.Amulti-objectiveparticleswarmoptimizationbasedpartialclassificationforaccidentseverityanalysis.AppliedArtificialIntelligence,2014,28(6):555-576.第32頁，共46頁，2023年，2月20日，星期六基于K-mean聚類的全局引導粒子選擇方法第33