具有多種群框架的pso演算法

『壹』 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演算法的性能，也是一個活躍的研究方向。
既然是研究拓撲結構，一定會涉及到鄰域的概念。鄰域可以是靜態的，也可以是動態確定的。鄰域的確定有兩種方式，一種為根據微粒的標志（或索引）來確定，與距離無關；而另一種為根據微粒之間的拓撲距離來確定。顯然，按照拓撲距離動態確定鄰域的計算量會比較大。
大多數研究針對靜態拓撲來展開。Kennedy分析了各種各樣的靜態鄰域結構以及它們對演算法性能的影響，認為星形、環形和Von Neumann拓撲適用性最好，並宣稱小鄰域的PSO演算法在復雜問題上性能較好，但是大鄰域的PSO演算法在簡單問題上性能會更好。Kennedy還基於K均值聚類演算法提出混合空間鄰域和環形拓撲方法的另一個局部PSO演算法版本，稱為社會趨同法，不用每個微粒的經驗而是用它所屬空間聚類的共同經驗來更新自己。Engelbrecht研究了基本的PSO演算法定位並維持多個最優點的能力，發現全局鄰域PSO（gBest PSO）演算法對此根本無能為力，而局部鄰域PSO（nBest PSO）演算法則是效率很低。
Peram發展了一種基於適應值距離比的PSO演算法（FDR-PSO），使用近鄰的交互。在更新速度的每一維分量時，FDR-PSO演算法選擇一個其他微粒的nBest，該微粒應具有更高的適應值，並且與待更新的微粒距離更近。該演算法在每一維速度更新中選取不同鄰域微粒，比在所有速度維只選取一個鄰域微粒更有效。Peer用不同的鄰域拓撲來研究保證收斂PSO（GCPSO）演算法的性能。Parsopoulos將全局版本和局部版本組合在一起，構建了一個統一微粒群演算法（Unified ParticleSwarm Optimizer, UPSO）。與此有異曲同工之效的是Xu提出的擴展PSO演算法，同時使用個體最優、全局最優以及鄰域中的局部最優來更新速度。Mendes介紹了一種完全通知（Fully informed）的PSO演算法，使用微粒的所有鄰居信息來更新速度，每個微粒對其鄰居的影響基於它的適應值大小和鄰域大小進行加權。在此基礎上，方峻發展出一種基於加權有向拓撲的的改進演算法，體現微粒之間影響的不平衡性。
也有少部分研究工作是關於動態拓撲的。Suganthan使用了一個動態調整的鄰域，微粒的鄰域逐漸增大，直到包含所有的微粒為止。Hu研究了一種動態鄰域，在每一代的性能空間中m個最近的微粒被選作新的鄰居。Mohais研究了兩種隨機動態鄰域拓撲。Binkley提出一種帶影響范圍的PSO演算法，最優微粒對其餘各微粒的影響能力取決於它們之間的距離。分層PSO演算法使用基於種群中每個微粒的性能得到的動態樹分層概念來定義鄰域結構。
上述鄰域拓撲均用於確定群體經驗gBest，而Jian使用鄰域拓撲來確定個體經驗pBest。

『叄』 pso的並行演算法

與大多數隨機優化演算法相似，當適應值評價函數的計算量比較大時，PSO演算法的計算量會很大。為了解決該問題，研究者提出了並行PSO演算法。與並行遺傳演算法類似，並行PSO演算法也可以有三種並行群體模型：主從並行模型、島嶼群體模型和鄰接模型。
Schutte採用同步實現方式，在計算完一代中所有點的適應值之後才進入下一代。這種並行方法雖然實現簡單，但常常會導致並行效率很差。故而有人提出非同步方式的並行演算法，可以在對數值精度影響不大的條件下提高PSO演算法的並行性能。這兩種方式採用的都是主從並行模型，其中非同步方式在求解上耦合性更高，更容易產生通信瓶頸。
Baskar提出一種兩個子種群並行演化的並發PSO演算法，其中一個子種群採用原始的PSO演算法，另一個子種群採用基於適應值距離比的PSO演算法（FDR-PSO）；兩個子種群之間頻繁地進行信息交換。而El-Abd研究了在子種群中採用局部鄰域版本的協作PSO演算法，並研究了多種信息交換的方式及其對演算法性能的影響。黃芳提出一種基於島嶼群體模型的並行PSO演算法，並引入一種集中式遷移策略，提高了求解效率，同時改善了早收斂現象。
Li提出延遲交換信息的並行演算法屬於鄰接模型，該演算法可以提高速度，但可能使得解的質量變差。

『肆』 粒子群優化演算法（PSO）的應用

這個屬於多目標優化問題，你可以把參考價格、外觀樣式、網路類型、屏幕參數和攝像頭像素等分別給予不同的權重值，作為一個目標函數，目標函數值就是綜合評價得分，然後用微粒群演算法求解。

『伍』 粒子群優化演算法

姓名：楊晶晶  學號：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的多目標優化

在多目標優化問題中，每個目標函數可以分別獨立進行優化，然後為每個目標找到最優值。但是，很少能找到對所有目標都是最優的完美解，因為目標之間經常是互相沖突的，只能找到Pareto最優解。
PSO演算法中的信息共享機制與其他基於種群的優化工具有很大的不同。在遺傳演算法（GA）中，染色體通過交叉互相交換信息，是一種雙向信息共享機制。但是在PSO演算法中，只有gBest（或nBest）給其他微粒提供信息，是一種單向信息共享機制。由於點吸引特性，傳統的PSO演算法不能同時定位構成Pareto前鋒的多個最優點。雖然通過對所有目標函數賦予不同的權重將其組合起來並進行多次運行，可以獲得多個最優解，但是還是希望有方法能夠一次同時找到一組Pareto最優解。
在PSO演算法中，一個微粒是一個獨立的智能體，基於其自身和同伴的經驗來搜索問題空間。前者為微粒更新公式中的認知部分，後者為社會部分，這二者在引導微粒的搜索方面都有關鍵的作用。因此，選擇適當的社會和認知引導者（gBest和pBest）就是MO-PSO演算法的關鍵點。認知引導者的選擇和傳統PSO演算法應遵循相同的規則，唯一的區別在於引導者應按照Pareto支配性來確定。社會引導者的選擇包括兩個步驟。第一步是建立一個從中選取引導者的候選池。在傳統PSO演算法中，引導者從鄰居的pBest之中選取。而在MO-PSO演算法中更常用的方法是使用一個外部池來存儲更多的Pareto最優解。第二步就是選擇引導者。gBest的選擇應滿足如下兩個標准：首先，它應該能為微粒提供有效的引導來獲得更好的收斂速度；第二，它還需要沿Pareo前鋒來提供平衡的搜索，以維持種群的多樣性。文獻中通常使用兩種典型的方法：（1）輪盤選擇模式，該方式按照某種標准進行隨機選擇，其目的是維持種群的多樣性；（2）數量標准：按照某種不涉及隨機選擇的過程來確定社會引導者。
Moore最早研究了PSO演算法在多目標優化中的應用，強調了個體和群體搜索二者的重要性，但是沒有採用任何維持多樣性的方法。Coello在非劣最優概念的基礎上應用了一個外部「容器」來記錄已找到的非支配向量，並用這些解來指導其它微粒的飛行。Fieldsend採用一種稱為支配樹的數據結構來對最優微粒進行排序。Parsopoulos應用了權重聚合的方法。Hu應用了動態鄰域，並在此基礎上利用擴展記憶，按詞典順序依次優化各個目標。Ray使用聚集機制來維持多樣性，並用一個多水平篩來處理約束。Lu使用了動態種群策略。Bartz-Beielstein採用歸檔技術來提高演算法性能。Li在PSO演算法中採用NSGA-II演算法中的主要機制，在局部最優微粒及其後代微粒之間確定局部最優微粒；並此基礎上又提出一種新的演算法，在適應值函數中使用最大最小策略來確定Pareto支配性。張利彪使用多個目標函數下各最優位置的均值來指導微粒飛行。Pulido使用多個子種群並採用聚類技術來求解多目標規劃問題。Mahfouf採用加權聚合方法來計算微粒的適應值，並據此確定引導微粒的搜索。Salazar-Lechuga使用適應值共享技術來引導微粒的搜索。Gong提出微粒角度的概念，並使用最小微粒角度和微粒密度來確定局部最優和全局最優微粒。基於AER模型，Zhang提出一種新的智能PSO模型，來將種群驅向Pareto最優解集。Ho提出一種新的適應值分配機制，並使用壽命（Age）變數來保存和選擇最優歷史記錄。Huang將CLPSO演算法應用到多目標規劃中。Ho提出另一種基於Pareto的與尺度無關的適應值函數，並使用一種基於正交試驗設計的智能運動機制（IMM）來確定微粒的下一步運動。Branke系統研究了多種個體最優微粒的選擇方法對MOPSO演算法性能的影響。張勇考慮儲備集更新策略在多目標PSO演算法中的關鍵作用，提出一種兩階段儲備集更新策略。
原萍提出一種分布式PSO演算法—分割域多目標PSO演算法（DRMPSO），並將其應用到基站優化問題。向量評價PSO演算法（VEPSO）是一種受向量評價遺傳演算法（VEGA）的啟發提出的一種演算法，在VEPSO演算法中，每個種群僅使用多個目標函數之一來進行評價，同時各種群之間互相交互經驗。將每個種群分配到一台網路PC上，即可直接使VEPSO演算法並行化，以加速收斂。Vlachogiannis應用並行VEPSO演算法來確定發電機對輸電系統的貢獻。熊盛武利用PSO演算法的信息傳遞機制，在PSO演算法中引入多目標演化演算法常用的歸檔技術，並採用環境選擇和配對選擇策略，使得整個群體在保持適當的選擇壓力的情況下收斂於Pareto最優解集。
由於適應值的計算非常消耗計算資源，為了減少計算量，需要減少適應值評價的次數。Reyes-Sierra採用適應值繼承和估計技術來實現該目標，並比較了十五種適應值繼承技術和四種估計技術應用於多目標PSO演算法時的效果。
保持MOPSO中的多樣性的方法主要有兩種：sigma方法和ε-支配方法。Villalobos-Arias在目標函數空間中引入條塊劃分來形成聚類，從而保持多樣性。

『柒』 pso的來源背景

為了說明粒子群優化演算法的發展和形成背景，首先介紹一下早期的簡單模型，即Boid（Bird-oid）模型。這個模型是為了模擬鳥群的行為而設計的，它也是粒子群優化演算法的直接來源。
一個最簡單的模型是這樣的：每一個鳥的個體用直角坐標繫上的點表示，隨機地給它們賦一個初速度和初位置，程序運行的每一步都按照「最近鄰速度匹配」規則，很快就會使得所有點的速度變得一樣。因為這個模擬太簡單而且遠離真實情況，於是在速度項中增加了一個隨機變數，即在迭代的每一步，除了滿足「最近鄰速度匹配」之外，每一步速度還要添加一個隨機變化的量，這樣使得整個模擬看起來更為真實。
Heppner設計了一個「谷地模型」來模擬鳥群的覓食行為。假設在平面上存在一個「谷地」，即食物所在地，鳥群開始時隨機地分散在平面上，為了尋覓食物所在地，它們按照如下規則運動：
首先假設谷地的位置坐標為(x0,y0)，單個鳥的位置和速度坐標分別為和(x,y)，用當前位置到谷地的距離s：來衡量當前位置和速度的「好壞程度」，離谷地的距離越近，則越「好」，反之越「壞」。假設每一個鳥具有記憶能力，能夠記住曾經達到的最好位置，記作pBest，並記a為系統規定的速度調節常數，rand為一個[0,1]間的隨機數，設定速度項按照下述規則變化：
然後假設群體之間可以以某種方式通訊，每個個體能夠知道並記住到當前為止整個群體的最好位置，記為gBest，記b為系統規定的速度調節常數，Rand為一個[0,1]間的隨機數，則速度項在經過以上調整後，還必須按照下述規則變化：
在計算機上模擬的結果顯示：當a/b較大時，所有的個體很快地聚集到「谷地」上；反之，粒子緩慢地搖擺著聚集到「谷地」的四周。通過這個簡單的模擬，發現群體能很快地找到一個簡單函數（2-1）的最優點。受該模型啟發，Kennedy和Eberhart設計出了一種演化優化演算法，並通過不斷的試驗和試錯，最後將此演算法的基本型固定為：
其中符號的意義同上。研究者認為每個個體被抽象為沒有質量和體積，而僅僅具有速度和位置的微粒，故將此方法稱為「粒子群」優化演算法。
據此，可對粒子群演算法小結如下：粒子群演算法是一種基於種群的搜索過程，其中每個個體稱作微粒，定義為在D維搜索空間中待優化問題的潛在解，保存有其歷史最優位置和所有粒子的最優位置的記憶，以及速度。在每一演化代，微粒的信息被組合起來調整速度關於每一維上的分量，繼而被用來計算新的微粒位置。微粒在多維搜索空間中不斷改變它們的狀態，直到到達平衡或最優狀態，或者超過了計算限制為止。問題空間的不同維度之間唯一的聯系是通過目標函數引入的。很多經驗證據已經顯示該演算法是一個非常有效的優化工具。微粒群優化演算法的流程圖見圖2-1。
以下給出微粒群演算法的比較完整的形式化表述。在連續空間坐標系中，微粒群演算法的數學描述如下：設微粒群體規模為N，其中每個微粒在D維空間中的坐標位置向量表示為，速度向量表示為，微粒個體最優位置（即該微粒經歷過的最優位置）記為，群體最優位置（即該微粒群中任意個體經歷過的最優位置）記為。不失一般性，以最小化問題為例，在最初版本的微粒群演算法中，個體最優位置的迭代公式為：
群體最優位置為個體最優位置中最好的位置。速度和位置迭代公式分別為：
由於初始版本在優化問題中應用時效果並不太好，所以初始演算法提出不久之後就出現了一種改進演算法，在速度迭代公式中引入了慣性權重ω，速度迭代公式變為：
雖然該改進演算法與初始版本相比復雜程度並沒有太大的增加，但是性能卻有了很大的提升，因而被廣泛使用。一般的，將該改進演算法稱為標准微粒群演算法，而將初始版本的演算法稱為原始微粒群演算法。
通過分析PSO演算法的收斂行為，Clerc介紹了一種帶收縮因子的PSO演算法變種，收縮因子保證了收斂性並提高了收斂速度。此時的速度迭代公式為：
顯然，迭代公式（2-7）和（2-8）並無本質區別，只要適當選取參數，二者完全相同。
微粒群演算法有兩種版本，分別稱為全局版本和局部版本。在全局版本中，微粒跟蹤的兩個極值為自身最優位置pBest和種群最優位置gBest。對應的，在局部版本中，微粒除了追隨自身最優位置pBest之外，不跟蹤種群最優位置gBest，而是跟蹤拓撲鄰域中的所有微粒的最優位置nBest。對於局部版本，速度更新公式（2-7）變為：
其中為局部鄰域中的最優位置。
每一代中任意微粒迭代的過程見圖2-2所示。從社會學的角度來看速度迭代公式，其中第一部分為微粒先前速度的影響，表示微粒對當前自身運動狀態的信任，依據自身的速度進行慣性運動，因此參數ω稱為慣性權重（Inertia Weight）；第二部分取決於微粒當前位置與自身最優位置之間的距離，為「認知（Cognition）」部分，表示微粒本身的思考，即微粒的運動來源於自己經驗的部分，因此參數c1稱為認知學習因子（也可稱為認知加速因子）；第三部分取決於微粒當前位置與群體中全局（或局部）最優位置之間的距離，為「社會（Social）」部分，表示微粒間的信息共享與相互合作，即微粒的運動來源於群體中其他微粒經驗的部分，它通過認知模擬了較好同伴的運動，因此參數c2稱為社會學習因子（也可稱為社會加速因子）。
自從PSO演算法被提出以來，由於它直觀的背景，簡單而容易實現的特點，以及對於不同類型函數廣泛的適應性，逐漸得到研究者的注意。十餘年來，PSO演算法的理論與應用研究都取得了很大的進展，對於演算法的原理已經有了初步的了解，演算法的應用也已經在不同學科中得以實現。
PSO演算法是一種隨機的、並行的優化演算法。它的優點是：不要求被優化函數具有可微、可導、連續等性質，收斂速度較快，演算法簡單，容易編程實現。然而，PSO演算法的缺點在於：（1）對於有多個局部極值點的函數，容易陷入到局部極值點中，得不到正確的結果。造成這種現象的原因有兩種，其一是由於待優化函數的性質；其二是由於微粒群演算法中微粒的多樣性迅速消失，造成早熟收斂。這兩個因素通常密不可分地糾纏在一起。（2）由於缺乏精密搜索方法的配合，PSO演算法往往不能得到精確的結果。造成這種問題的原因是PSO演算法並沒有很充分地利用計算過程中獲得的信息，在每一步迭代中，僅僅利用了群體最優和個體最優的信息。（3）PSO演算法雖然提供了全局搜索的可能，但是並不能保證收斂到全局最優點上。（4）PSO演算法是一種啟發式的仿生優化演算法，當前還沒有嚴格的理論基礎，僅僅是通過對某種群體搜索現象的簡化模擬而設計的，但並沒有從原理上說明這種演算法為什麼有效，以及它適用的范圍。因此，PSO演算法一般適用於一類高維的、存在多個局部極值點而並不需要得到很高精度解的優化問題。
當前針對PSO演算法開展的研究工作種類繁多，經歸納整理分為如下八個大類：（1）對PSO演算法進行理論分析，試圖理解其工作機理；（2）改變PSO演算法的結構，試圖獲得性能更好的演算法；（3）研究各種參數配置對PSO演算法的影響；（4）研究各種拓撲結構對PSO演算法的影響；（5）研究離散版本的PSO演算法；（6）研究PSO演算法的並行演算法；（7）利用PSO演算法對多種情況下的優化問題進行求解；（8）將PSO演算法應用到各個不同的工程領域。以下從這八大類別著手，對PSO演算法的研究現狀作一梳理。由於文獻太多，無法面面俱到，僅撿有代表性的加以綜述。

『捌』 如何用粒子群優化（PSO）演算法實現多目標優化

粒子群演算法，也稱粒子群優化演算法（ParticleSwarmOptimization），縮寫為PSO，是近年來發展起來的一種新的進化演算法(EvolutionaryAlgorithm-EA)。PSO演算法屬於進化演算法的一種，和模擬退火演算法相似，它也是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，但它比遺傳演算法規則更為簡單，它沒有遺傳演算法的「交叉」(Crossover)和「變異」(Mutation)操作，它通過追隨當前搜索到的最優值來尋找全局最優。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。粒子群演算法是一種並行演算法。

『玖』 PSO優化方向

1. PSO收斂快，特別是在演算法的早期，但存在著精度較低，易發散等缺點。加速系數、最大速度等參數太大，粒子可能錯過最優解--------------->不收斂； 收斂的情況下，由於所有粒子都向最優的方向飛去，所有粒子趨向同一化（失去多樣性）--------->使得 後期收斂速度明顯變慢，搜索能力變弱 ，同時演算法收斂到一定精度時，無法繼續優化。

2. 缺乏數學理論支持，PSO演算法本質上是一種隨機搜索演算法，因此可靠性上讓人存疑；

3. 尋找一種好的拓撲結構，加強PSO演算法的泛化能力；

4. 平衡全局搜索和局部搜索能力；

（1）粒子群初始化：粒子群初始化對演算法性能有一定的影響，分為粒子位置初始化和速度初始化。

         粒子群 位置 初始化的理想效果：初始種群盡可能 均勻覆蓋整個 搜索空間。

         一、不推薦的初始化 ：a. 均勻分布隨機數

                                          缺點：1. 對搜索空間的覆蓋不夠好；

                                                     2. 當維度D增大時候，所有的粒子都傾向於靠近搜索空間的邊緣：

                                     b. 偽隨機數初始化：造成粒子在參數空間的不均勻分布和聚集效應；

          二、推薦的初始化 ：a. 基於centroidal voronoi tessellations (CVTs)的種群初始化方法（這東西是啥沒搞懂）；

                                   b. 採用正交設計方法對種群進行初始化；

                                   c. 類隨機采樣方法中的sobol序列：使得粒子群在參數空間更加均勻；

                                   d. Hammersley方法：感覺這個類似於類隨機采樣方法（具體我也沒搞清楚）；

                                   e. 將粒子建立為帶電（positive charged）的模型，通過建立一個平衡方程，求解該方程的最小解獲得粒子初始化位置；

                                   f. 設置偏向的隨機分布（推薦） ：即：我們通過對評價函數等一系列先驗信息進行分析，得出最優解的可能存在空間范圍，然後在這些范圍內，著重撒點。就算再不濟，也可以根據評價函數遵循Nearer is Better class（最優解更加可能在搜索空間的中心位置准則），在搜索空間的中心位置著重撒點。比如：

粒子群 速度 初始化：主要有如下五種方式：（根據實驗表明，One-rand的效果最好。喂！！！這里One-rand的表達式是不是寫錯了啊？）

（2）領域拓撲：粒子的拓撲，決定了粒子所接受到的信息來源。

         一、全局模型gbest：最早的粒子群優化版本是全局PSO，使用全局拓撲結構，社會 只能 通過種群中， 最優的那個粒子 ，對每個粒子施加影響。

                                   1. 優點：具有較快的收斂速度。

                                   2. 缺點：粒子間的交流不夠充分，但更容易陷入局部極值。

         二、局部模型lbest：採用每個粒子僅在一定的鄰域內進行信息交換，，粒子之間的交流相對比較緩慢。

                                   1. 優點：粒子更容易搜索問題空間中的不同地區。

                                   2. 缺點：信息傳遞緩慢，設計相對復雜。

                                   3. 分類：被動模型：微觀領域、宏觀領域、維度劃分；主動模型。

                                   （1）微觀鄰域：細分到每個粒子。空間鄰域(spatial neighborhood)、性能空間(performance space)鄰域、社會關系鄰域(sociometric neighborhood)。

                                            a. 空間鄰域：直接在搜索空間按粒子間的距離(如歐式距離)進行劃分。在搜索初始階段，將鄰域定義為每個粒子自身；隨著迭代次數的增加，將鄰域范圍逐漸擴展到整個種群。

                                            b. 性能空間領域：根據性能指標(如適應度、目標函數值)劃分的鄰域，如：適應度距離比值(fitness-distance-ratio)來選擇粒子的相鄰粒子。

                                            c. 社會關系鄰域： 按粒子存儲陣列的索引編號進行劃分，主要有：環形拓撲(ring or circle topology)、輪形拓撲(wheel topology)或星形拓撲(star topology)、塔形拓撲(pyramid topology)、馮－諾以曼拓撲(Von Neumann topology)以及隨機拓撲(random topology)等。（隨機拓撲往往對大多數問題能表現出較好的性能，其次是馮－諾以曼拓撲。）

                                   （2）宏觀鄰域：對群體進行劃分。比如：使用簇分析將整個粒子群劃分為多個簇，然後用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置；根據粒子相似性動態地將粒子群體按種類劃分為多個子種群，再以每個子種群的最佳個體作為每個粒子的鄰域最佳位置；劃分一個主群體，多個仆群體，仆群體進行獨立的搜索，主群體在仆群體提供的最佳位置基礎上開展搜索；每間隔一定代數將整個群體隨機地重新劃分；每個粒子除了自身和鄰域最佳歷史位置外，還學習鄰域內其他粒子的 成功經驗（只學好的，不學壞的） 等等；

                                   （3）維度劃分：想法源自於：搜索空間維數較高時往往容易遭受「維數災」的困擾。假設粒子群的整體維度為D，則可以將D劃分成不同的部分，比如劃分成k份，使用不同的群體，分別優化不同的維度。

                                   （4）主動模型：主動改變粒子鄰域空間，避免碰撞和擁擠。比如：將粒子分為帶電粒子和自然粒子，帶電粒子接近會產生排斥；為每個粒子引入與鄰近粒子距離成反比的自組織危險度，距離越近危險度越高，當危險度達到一定閾值，對粒子進行重新初始化，或者彈開；為粒子賦一個半徑，以檢測兩個粒子是否會發生碰撞，並且採取碰撞-彈開方式將其分離。

（3）參數選擇：三種參數：慣性權重或收斂因子、最大速度、兩個加速因子。

         一、慣性權重：

                     a. 慣性權重大：加強PSO 全局 搜索能力；慣性權重小：加強PSO 局部 搜索能力；

                     b. 矛盾點：初始慣性權重大，局部搜索能力差，可能錯過最優點；後期，慣性權重小，全局搜索能力不行，導致整個粒子群就陷入局部最優解。

                     c. 優化方向：在適當的時候降低權重w，平衡全局和局部搜索能力；

                     d. 優化建議：w隨著更新代數的增加從0.9線性遞減到0.4；

         二、壓縮因子：

                     a. 優勢：慣性常數方法通常採用慣性權值隨更新代數增加而遞減的策略，演算法後期由於慣性權值過小，會失去探索新區域的能力，而收縮因子方法則不存在此不足

                     b. 優化建議：通常φ取4.1，χ得0.729。

         三、最大速度的選擇：為了抑制粒子更新的無規律的跳動，速度往往被限制在[-Vm,Vm]

                     a. Vm增大，有利於全局 探索（exploration） ，但可能越過全局最優解；Vm減小，有利於局部 開發（exploitation） ，但可能陷入局部最優；

                     b. 優化建議：一般設定為問題空間的10%~20%；或者動態調整Vm，比如：根據群體最佳適應和最差適應來進行調整；

         四、兩個加速常數：加速常數C1和C2分別用於控制粒子指向自身或鄰域最佳位置的運動。

                     a. C1增大，粒子全局搜索能力好；C2增大，粒子向著最優靠攏局部能力好，但粒子會過早收斂；

                     b. 優化建議：C1 = C2 = 2.0，並且C1+C2 <= 4.0;或者根據自適應調整，比如隨著迭代次數增加，減小C1增大C2；

（4）混合法：PSO與其他方法結合。

                     這點我覺得，主要根據個人的學習積累來操作。考慮方向：增加粒子群的局部搜索能力。

『拾』 粒子群優化演算法的PSO

演化計算可以用來研究神經網路的三個方面：網路連接權重，網路結構(網路拓撲結構，傳遞函數)，網路學習演算法。
不過大多數這方面的工作都集中在網路連接權重，和網路拓撲結構上。在GA中，網路權重和/或拓撲結構一般編碼為染色體(Chromosome)，適應函數(fitness function)的選擇一般根據研究目的確定。例如在分類問題中，錯誤分類的比率可以用來作為適應值。 這里用一個簡單的例子說明PSO訓練神經網路的過程。這個例子使用分類問題的基準函數 (Benchmark function)IRIS數據集。(Iris 是一種鳶尾屬植物) 在數據記錄中，每組數據包含Iris花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有50組數據. 這樣總共有150組數據或模式。
我們用3層的神經網路來做分類。現在有四個輸入和三個輸出。所以神經網路的輸入層有4個節點，輸出層有3個節點我們也可以動態調節隱含層節點的數目，不過這里我們假定隱含層有6個節點。我們也可以訓練神經網路中其他的參數。不過這里我們只是來確定網路權重。粒子就表示神經網路的一組權重，應該是4*6+6*3=42個參數。權重的范圍設定為[-100，100] (這只是一個例子，在實際情況中可能需要試驗調整).在完成編碼以後，我們需要確定適應函數。對於分類問題，我們把所有的數據送入神經網路，網路的權重有粒子的參數決定。然後記錄所有的錯誤分類的數目作為那個粒子的適應值。現在我們就利用PSO來訓練神經網路來獲得盡可能低的錯誤分類數目。PSO本身並沒有很多的參數需要調整。所以在實驗中只需要調整隱含層的節點數目和權重的范圍以取得較好的分類效果。