⑴ pso的演算法結構
對微粒群演算法結構的改進方案有很多種,對其可分類為:採用多個子種群;改進微粒學習對象的選取策略;修改微粒更新迭代公式;修改速度更新策略;修改速度限制方法、位置限制方法和動態確定搜索空間;與其他搜索技術相結合;以及針對多模問題所作的改進。
第一類方案是採用多個子種群。柯晶考慮優化問題對收斂速度和尋優精度的雙重要求並借鑒多群體進化演算法的思想,將尋優微粒分成兩組,一組微粒採用壓縮因子的局部模式PSO演算法,另一組微粒採用慣性權重的全局模式PSO演算法,兩組微粒之間採用環形拓撲結構。對於高維優化問題,PSO演算法需要的微粒個數很多,導致計算復雜度常常很高,並且很難得到好的解。因此,出現了一種協作微粒群演算法(Cooperative ParticleSwarm Optimizer, CPSO-H),將輸入向量拆分成多個子向量,並對每個子向量使用一個微粒群來進行優化。雖然CPSO-H演算法使用一維群體來分別搜索每一維,但是這些搜索結果被一個全局群體集成起來之後,在多模問題上的性能與原始PSO演算法相比有很大的改進。Chow使用多個互相交互的子群,並引入相鄰群參考速度。馮奇峰提出將搜索區域分區,使用多個子群並通過微粒間的距離來保持多樣性。陳國初將微粒分成飛行方向不同的兩個分群,其中一分群朝最優微粒飛行,另一分群微粒朝相反方向飛行;飛行時,每一微粒不僅受到微粒本身飛行經驗和本分群最優微粒的影響,還受到全群最優微粒的影響。Niu在PSO演算法中引入主—從子群模式,提出一種多種群協作PSO演算法。Seo提出一種多組PSO演算法(Multigrouped PSO),使用N組微粒來同時搜索多模問題的N個峰。Selleri使用多個獨立的子群,在微粒速度的更新方程中添加了一些新項,分別使得微粒向子群歷史最優位置運動,或者遠離其他子群的重心。王俊年借鑒遞階編碼的思想,構造出一種多種群協同進化PSO演算法。高鷹借鑒生態學中環境和種群競爭的關系,提出一種基於種群密度的多種群PSO演算法。
第二類方案是改進微粒學習對象的選取策略。Al-kazemi提出多階段PSO演算法,將微粒按不同階段的臨時搜索目標分組,這些臨時目標允許微粒向著或背著它自己或全局最好位置移動。Ting對每個微粒的pBest進行操作,每一維從其他隨機確定的維度學習,之後如果新的pBest更好則替換原pBest;該文還比較了多種不同學習方式對應的PSO演算法的性能。Liang提出一種新穎的學習策略CLPSO,利用所有其他微粒的歷史最優信息來更新微粒的速度;每個微粒可以向不同的微粒學習,並且微粒的每一維可以向不同的微粒學習。該策略能夠保持群體的多樣性,防止早熟收斂,可以提高PSO演算法在多模問題上的性能;通過實驗將該演算法與其它幾種PSO演算法的變種進行比較,實驗結果表明該演算法在解決多模復雜問題時效果很好。Zhao在PSO演算法中使用適應值最好的n個值來代替速度更新公式中的gBest。Abdelbar提出一種模糊度量,從而使得每個鄰域中有多個適應值最好的微粒可以影響其它微粒。Wang也採用多個適應值最好的微粒信息來更新微粒速度,並提出一種模糊規則來自適應地確定參數。崔志華提出一種動態調整的改進PSO演算法,在運行過程中動態調整極限位置,使得每個微粒的極限位置在其所經歷的最好位置與整體最好位置所形成的動態圓中分布。與原始PSO演算法相反,有一類方法是遠離最差位置而非飛向最優位置。Yang提出在演算法中記錄最差位置而非最優位置,所有微粒都遠離這些最差位置。與此類似,Leontitsis在微粒群演算法中引入排斥子的概念,在使用個體最優位置和群體最優位置信息的同時,在演算法中記錄當前的個體最差位置和群體最差位置,並利用它們將微粒排斥到最優位置,從而讓微粒群更快地到達最優位置。孟建良提出一種改進的PSO演算法,在進化的初期,微粒以較大的概率向種群中其他微粒的個體最優學習;在進化後期,微粒以較大的概率向當前全局最優個體學習。Yang在PSO演算法中引入輪盤選擇技術來確定gBest,使得所有個體在進化早期都有機會引領搜索方向,從而避免早熟。
第三類方案是修改微粒更新公式。Hendtlass在速度更新方程中給每個微粒添加了記憶能力。He在速度更新方程中引入被動聚集機制。曾建潮通過對PSO演算法的速度進化迭代方程進行修正,提出一種保證全局收斂的隨機PSO演算法。Zeng在PSO演算法中引入加速度項,使得PSO演算法從一個二階隨機系統變為一個三階隨機系統,並使用PID控制器來控制演算法的演化。為了改進PSO演算法的全局搜索能力,Ho提出一種新的微粒速度和位置更新公式,並引入壽命(Age)變數。
第四類方案是修改速度更新策略。Liu認為過於頻繁的速度更新會弱化微粒的局部開采能力並減慢收斂,因此提出一種鬆弛速度更新(RVU)策略,僅當微粒使用原速度不能進一步提高適應值時才更新速度,並通過試驗證明該策略可以大大減小計算量並加速收斂。羅建宏對同步模式和非同步模式的PSO演算法進行了對比研究,試驗結果表明非同步模式收斂速度顯著提高,同時尋優效果更好。Yang在微粒的更新規則中引入感情心理模型。Liu採用一個最小速度閾值來控制微粒的速度,並使用一個模糊邏輯控制器來自適應地調節該最小速度閾值。張利彪提出了對PSO演算法增加更新概率,對一定比例的微粒並不按照原更新公式更新,而是再次隨機初始化。Dioan利用遺傳演算法(GA)來演化PSO演算法的結構,即微粒群中各微粒更新的順序和頻率。
第五類方案是修改速度限制方法、位置限制方法和動態確定搜索空間。Stacey提出一種重新隨機化速度的速度限制和一種重新隨機化位置的位置限制。Liu在[76]的基礎上,在PSO演算法中引入動量因子,來將微粒位置限制在可行范圍內。陳炳瑞提出一種根據微粒群的最佳適應值動態壓縮微粒群的搜索空間與微粒群飛行速度范圍的改進PSO演算法。
第六類方案是通過將PSO演算法與一些其他的搜索技術進行結合來提高PSO演算法的性能,主要目的有二,其一是提高種群多樣性,避免早熟;其二是提高演算法局部搜索能力。這些混合演算法包括將各種遺傳運算元如選擇、交叉、變異引入PSO演算法,來增加種群的多樣性並提高逃離局部最小的能力。Krink通過解決微粒間的沖突和聚集來增強種群多樣性,提出一種空間擴展PSO演算法(Spatial ExtensionPSO,SEPSO);但是SEPSO演算法的參數比較難以調節,為此Monson提出一種自適應調節參數的方法。用以提高種群多樣性的其他方法或模型還包括「吸引—排斥」、捕食—被捕食模型、耗散模型、自組織模型、生命周期模型(LifeCycle model)、貝葉斯優化模型、避免沖突機制、擁擠迴避(Crowd Avoidance)、層次化公平競爭(HFC)、外部記憶、梯度下降技術、線性搜索、單純形法運算元、爬山法、勞動分工、主成分分析技術、卡爾曼濾波、遺傳演算法、隨機搜索演算法、模擬退火、禁忌搜索、蟻群演算法(ACO)、人工免疫演算法、混沌演算法、微分演化、遺傳規劃等。還有人將PSO演算法在量子空間進行了擴展。Zhao將多主體系統(MAS)與PSO演算法集成起來,提出MAPSO演算法。Medasani借鑒概率C均值和概率論中的思想對PSO演算法進行擴展,提出一種概率PSO演算法,讓演算法分勘探和開發兩個階段運行。
第七類方案專門針對多模問題,希望能夠找到多個較優解。為了能使PSO演算法一次獲得待優化問題的多個較優解,Parsopoulos使用了偏轉(Deflection)、拉伸(Stretching)和排斥(Repulsion)等技術,通過防止微粒運動到之前已經發現的最小區域,來找到盡可能多的最小點。但是這種方法會在檢測到的局部最優點兩端產生一些新的局部最優點,可能會導致優化演算法陷入這些局部最小點。為此,Jin提出一種新的函數變換形式,可以避免該缺點。基於類似思想,熊勇提出一種旋轉曲面變換方法。
保持種群多樣性最簡單的方法,是在多樣性過小的時候,重置某些微粒或整個微粒群。Lvbjerg在PSO演算法中採用自組織臨界性作為一種度量,來描述微粒群中微粒相互之間的接近程度,來確定是否需要重新初始化微粒的位置。Clerc提出了一種「Re-Hope」方法,當搜索空間變得相當小但是仍未找到解時(No-Hope),重置微粒群。Fu提出一種帶C-Pg變異的PSO演算法,微粒按照一定概率飛向擾動點而非Pg。赫然提出了一種自適應逃逸微粒群演算法,限制微粒在搜索空間內的飛行速度並給出速度的自適應策略。
另一種變種是小生境PSO演算法,同時使用多個子種群來定位和跟蹤多個最優解。Brits還研究了一種通過調整適應值計算方式的方法來同時找到多個最優解。Li在PSO演算法中引入適應值共享技術來求解多模問題。Zhang在PSO演算法中採用順序生境(SequentialNiching)技術。在小生境PSO演算法的基礎上,還可以使用向量點積運算來確定各個小生境中的候選解及其邊界,並使該過程並行化,以獲得更好的結果。但是,各種小生境PSO演算法存在一個共同的問題,即需要確定一個小生境半徑,且演算法性能對該參數很敏感。為解決該問題,Bird提出一種自適應確定niching參數的方法。
Hendtlass在PSO演算法中引入短程力的概念,並基於此提出一種WoSP演算法,可以同時確定多個最優點。劉宇提出一種多模態PSO演算法,用聚類演算法對微粒進行聚類,動態地將種群劃分成幾個類,並且使用微粒所屬類的最優微粒而非整個種群的最好微粒來更新微粒的速度,從而可以同時得到多個近似最優解。Li在PSO演算法中引入物種的概念,但是由於其使用的物種間距是固定的,該方法只適用於均勻分布的多模問題;為此,Yuan對該演算法進行擴展,採用多尺度搜索方法對物種間距加以自適應的調整。
此外,也有研究者將PSO演算法的思想引入其他演算法中,如將PSO演算法中微粒的運動規則嵌入到進化規劃中,用PSO演算法中的運動規則來替代演化演算法中交叉運算元的功能。
⑵ pso的並行演算法
與大多數隨機優化演算法相似,當適應值評價函數的計算量比較大時,PSO演算法的計算量會很大。為了解決該問題,研究者提出了並行PSO演算法。與並行遺傳演算法類似,並行PSO演算法也可以有三種並行群體模型:主從並行模型、島嶼群體模型和鄰接模型。
Schutte採用同步實現方式,在計算完一代中所有點的適應值之後才進入下一代。這種並行方法雖然實現簡單,但常常會導致並行效率很差。故而有人提出非同步方式的並行演算法,可以在對數值精度影響不大的條件下提高PSO演算法的並行性能。這兩種方式採用的都是主從並行模型,其中非同步方式在求解上耦合性更高,更容易產生通信瓶頸。
Baskar提出一種兩個子種群並行演化的並發PSO演算法,其中一個子種群採用原始的PSO演算法,另一個子種群採用基於適應值距離比的PSO演算法(FDR-PSO);兩個子種群之間頻繁地進行信息交換。而El-Abd研究了在子種群中採用局部鄰域版本的協作PSO演算法,並研究了多種信息交換的方式及其對演算法性能的影響。黃芳提出一種基於島嶼群體模型的並行PSO演算法,並引入一種集中式遷移策略,提高了求解效率,同時改善了早收斂現象。
Li提出延遲交換信息的並行演算法屬於鄰接模型,該演算法可以提高速度,但可能使得解的質量變差。
⑶ 粒子群優化演算法
姓名:楊晶晶 學號:21011210420 學院:通信工程學院
【嵌牛導讀】
傳統的多目標優化方法是將多目標問題通過加權求和轉化為單目標問題來處理的,而粒子演算法主要是解決一些多目標優化問題的(例如機械零件的多目標設計優化),其優點是容易實現,精度高,收斂速度快。
【嵌牛鼻子】粒子群演算法的概念、公式、調參以及與遺傳演算法的比較。
【嵌牛提問】什麼是粒子群演算法?它的計算流程是什麼?與遺傳演算法相比呢?
【嵌牛正文】
1. 概念
粒子群優化演算法(PSO:Particle swarm optimization) 是一種進化計算技術(evolutionary computation),源於對鳥群捕食的行為研究。
粒子群優化演算法的基本思想:是通過群體中個體之間的協作和信息共享來尋找最優解。
PSO的優勢:在於簡單容易實現並且沒有許多參數的調節。目前已被廣泛應用於函數優化、神經網路訓練、模糊系統控制以及其他遺傳演算法的應用領域。
2. 演算法
2.1 問題抽象
鳥被抽象為沒有質量和體積的微粒(點),並延伸到N維空間,粒子i在N維空間的位置表示為矢量Xi=(x1,x2,…,xN),飛行速度表示為矢量Vi=(v1,v2,…,vN)。每個粒子都有一個由目標函數決定的適應值(fitness value),並且知道自己到目前為止發現的最好位置(pbest)和現在的位置Xi。這個可以看作是粒子自己的飛行經驗。除此之外,每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(gbest)(gbest是pbest中的最好值),這個可以看作是粒子同伴的經驗。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。
2.2 更新規則
PSO初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次的迭代中,粒子通過跟蹤兩個「極值」(pbest,gbest)來更新自己。在找到這兩個最優值後,粒子通過下面的公式來更新自己的速度和位置。
公式(1)的第一部分稱為【記憶項】,表示上次速度大小和方向的影響;公式(1)的第二部分稱為【自身認知項】,是從當前點指向粒子自身最好點的一個矢量,表示粒子的動作來源於自己經驗的部分;公式(1)的第三部分稱為【群體認知項】,是一個從當前點指向種群最好點的矢量,反映了粒子間的協同合作和知識共享。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。
以上面兩個公式為基礎,形成了PSO的標准形式。
公式(2)和 公式(3)被視為標准PSO演算法。
2.3 標准PSO演算法流程
標准PSO演算法的流程:
1)初始化一群微粒(群體規模為N),包括隨機位置和速度;
2)評價每個微粒的適應度;
3)對每個微粒,將其適應值與其經過的最好位置pbest作比較,如果較好,則將其作為當前的最好位置pbest;
4)對每個微粒,將其適應值與其經過的最好位置gbest作比較,如果較好,則將其作為當前的最好位置gbest;
5)根據公式(2)、(3)調整微粒速度和位置;
6)未達到結束條件則轉第2)步。
迭代終止條件根據具體問題一般選為最大迭代次數Gk或(和)微粒群迄今為止搜索到的最優位置滿足預定最小適應閾值。
公式(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優位置。
當C1=0時,則粒子沒有了認知能力,變為只有社會的模型(social-only):
被稱為全局PSO演算法。粒子有擴展搜索空間的能力,具有較快的收斂速度,但由於缺少局部搜索,對於復雜問題
比標准PSO 更易陷入局部最優。
當C2=0時,則粒子之間沒有社會信息,模型變為只有認知(cognition-only)模型:
被稱為局部PSO演算法。由於個體之間沒有信息的交流,整個群體相當於多個粒子進行盲目的隨機搜索,收斂速度慢,因而得到最優解的可能性小。
2.4 參數分析
參數:群體規模N,慣性因子 ,學習因子c1和c2,最大速度Vmax,最大迭代次數Gk。
群體規模N:一般取20~40,對較難或特定類別的問題可以取到100~200。
最大速度Vmax:決定當前位置與最好位置之間的區域的解析度(或精度)。如果太快,則粒子有可能越過極小點;如果太慢,則粒子不能在局部極小點之外進行足夠的探索,會陷入到局部極值區域內。這種限制可以達到防止計算溢出、決定問題空間搜索的粒度的目的。
權重因子:包括慣性因子和學習因子c1和c2。使粒子保持著運動慣性,使其具有擴展搜索空間的趨勢,有能力探索新的區域。c1和c2代表將每個粒子推向pbest和gbest位置的統計加速項的權值。較低的值允許粒子在被拉回之前可以在目標區域外徘徊,較高的值導致粒子突然地沖向或越過目標區域。
參數設置:
1)如果令c1=c2=0,粒子將一直以當前速度的飛行,直到邊界。很難找到最優解。
2)如果=0,則速度只取決於當前位置和歷史最好位置,速度本身沒有記憶性。假設一個粒子處在全局最好位置,它將保持靜止,其他粒子則飛向它的最好位置和全局最好位置的加權中心。粒子將收縮到當前全局最好位置。在加上第一部分後,粒子有擴展搜索空間的趨勢,這也使得的作用表現為針對不同的搜索問題,調整演算法的全局和局部搜索能力的平衡。較大時,具有較強的全局搜索能力;較小時,具有較強的局部搜索能力。
3)通常設c1=c2=2。Suganthan的實驗表明:c1和c2為常數時可以得到較好的解,但不一定必須等於2。Clerc引入收斂因子(constriction factor) K來保證收斂性。
通常取為4.1,則K=0.729.實驗表明,與使用慣性權重的PSO演算法相比,使用收斂因子的PSO有更快的收斂速度。其實只要恰當的選取和c1、c2,兩種演算法是一樣的。因此使用收斂因子的PSO可以看作使用慣性權重PSO的特例。
恰當的選取演算法的參數值可以改善演算法的性能。
3. PSO與其它演算法的比較
3.1 遺傳演算法和PSO的比較
1)共性:
(1)都屬於仿生演算法。
(2)都屬於全局優化方法。
(3)都屬於隨機搜索演算法。
(4)都隱含並行性。
(5)根據個體的適配信息進行搜索,因此不受函數約束條件的限制,如連續性、可導性等。
(6)對高維復雜問題,往往會遇到早熟收斂和收斂 性能差的缺點,都無法保證收斂到最優點。
2)差異:
(1)PSO有記憶,好的解的知識所有粒子都保 存,而GA(Genetic Algorithm),以前的知識隨著種群的改變被改變。
(2)PSO中的粒子僅僅通過當前搜索到最優點進行共享信息,所以很大程度上這是一種單共享項信息機制。而GA中,染色體之間相互共享信息,使得整個種群都向最優區域移動。
(3)GA的編碼技術和遺傳操作比較簡單,而PSO相對於GA,沒有交叉和變異操作,粒子只是通過內部速度進行更新,因此原理更簡單、參數更少、實現更容易。
(4)應用於人工神經網路(ANN)
GA可以用來研究NN的三個方面:網路連接權重、網路結構、學習演算法。優勢在於可處理傳統方法不能處理的問題,例如不可導的節點傳遞函數或沒有梯度信息。
GA缺點:在某些問題上性能不是特別好;網路權重的編碼和遺傳運算元的選擇有時較麻煩。
已有利用PSO來進行神經網路訓練。研究表明PSO是一種很有潛力的神經網路演算法。速度較快且有較好的結果。且沒有遺傳演算法碰到的問題。
⑷ 如何用粒子群優化(PSO)演算法實現多目標優化
粒子群演算法,也稱粒子群優化演算法(ParticleSwarmOptimization),縮寫為PSO,是近年來發展起來的一種新的進化演算法(EvolutionaryAlgorithm-EA)。PSO演算法屬於進化演算法的一種,和模擬退火演算法相似,它也是從隨機解出發,通過迭代尋找最優解,它也是通過適應度來評價解的品質,但它比遺傳演算法規則更為簡單,它沒有遺傳演算法的「交叉」(Crossover)和「變異」(Mutation)操作,它通過追隨當前搜索到的最優值來尋找全局最優。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視,並且在解決實際問題中展示了其優越性。粒子群演算法是一種並行演算法。
⑸ 怎樣用PSO演算法求解一個簡單的函數
約束優化
約束優化問題的目標是在滿足一組線性或非線性約束的條件下,找到使得適應值函數最優的解。對於約束優化問題,需要對原始PSO演算法進行改進來處理約束。 一種簡單的方法是,所有的微粒初始化時都從可行解開始,在更新過程中,僅需記住在可行空間中的位置,拋棄那些不可行解即可。該方法的缺點是對於某些問題,初始的可行解集很難找到。或者,當微粒位置超出可行范圍時,可將微粒位置重置為之前找到的最好位置,這種簡單的修正就能成功找到一系列Benchmark問題的最優解。Paquet讓微粒在運動過程中保持線性約束,從而得到一種可以解決線性約束優化問題的PSO演算法。Pulido引入擾動運算元和約束處理機制來處理約束優化問題。Park提出一種改進的PSO演算法來處理等式約束和不等式約束。 另一種簡單的方法是使用懲罰函數將約束優化問題轉變為無約束優化問題,之後再使用PSO演算法來進行求解。Shi將約束優化問題轉化為最小—最大問題,並使用兩個共同進化的微粒群來對其求解。譚瑛提出一種雙微粒群的PSO演算法,通過在微粒群間引入目標信息與約束信息項來解決在滿足約束條件下求解目標函數的最優化問題。Zavala在PSO演算法中引入兩個擾動運算元,用來解決單目標約束優化問題。 第三種方法是採用修復策略,將微粒發現的違反約束的解修復為滿足約束的解。
約束滿足問題
PSO演算法設計的初衷是用來求解連續問題,但近年來對於可滿足性問題PSO演算法的研究也不斷得到人們的重視。Schoofs提出用PSO演算法求解二元約束滿足問題,對微粒的位置和速度計算公式進行了重新定義,使用變數和它的關聯變數存在的沖突數作為微粒的適應度函數,並指出該演算法在求解約束滿足問題上具有一定優勢。Lin在Schoofs工作的基礎上研究了使用PSO演算法來求解通用的n元約束滿足問題。楊輕雲在Schoofs工作的基礎上對適應度函數進行了改進,把最大度靜態變數序列引入到適應度函數的計算中。
⑹ 如圖,如何用這個PSO演算法或遺傳演算法來求函數極值,用C語言編寫代碼
需要很多的子函數 %子程序:新物種交叉操作,函數名稱存儲為crossover.m function scro=crossover(population,seln,pc); BitLength=size(population,2); pcc=IfCroIfMut(pc);%根據交叉概率決定是否進行交叉操作,1則是,0則否 if pcc==1 chb=round(rand*(BitLength-2))+1;%在[1,BitLength-1]范圍內隨機產生一個交叉位 scro(1,:)=[population(seln(1),1:chb) population(seln(2),chb+1:BitLength)] scro(2,:)=[population(seln(2),1:chb) population(seln(1),chb+1:BitLength)] else scro(1,:)=population(seln(1),:); scro(2,:)=population(seln(2),:); end %子程序:計算適應度函數,函數名稱存儲為fitnessfun.m function [Fitvalue,cumsump]=fitnessfun(population); global BitLength global boundsbegin global boundsend popsize=size(population,1);%有popsize個個體 for i=1:popsize x=transform2to10(population(i,:));%將二進制轉換為十進制 %轉化為[-2,2]區間的實數 xx=boundsbegin+x*(boundsend-boundsbegin)/(power(2,BitLength)-1); Fitvalue(i)=targetfun(xx);%計算函數值,即適應度 end %給適...
望採納!
⑺ 二進制PSO演算法
PSO演算法中每一粒子都被看是潛在的最優解,具體實現思路是先將粒子初始化,對於每個粒子都有一個當前位置以及根據適應度值做粒子更新的速度(Kennedy et al.,1995),通過迭代計算得到最優解。PSO粒子速度計算和對應位置更新的原理如式(8.1)、式(8.2)所示:
高光譜遙感影像信息提取技術
式中:xid是粒子;c1,c2是學習因子;w是慣性因子,是粒子速度保持更新之前粒子速度的能力;pid是目前單個粒子最優位置;pgd是整個粒子群目前得到的最優位置;rand是0~1之間的隨機數。
二進制PSO首先將粒子初始化為0和1組成的序列。二進制PSO演算法是對式(8.2)作些改變,其位置更新如式(8.3)所示(程志剛等,2007):
高光譜遙感影像信息提取技術
式中: 是 Sigmoid 函數。