pso

來源背景

為了說明粒子群最佳化算法的發展和形成背景，首先介紹一下早期的簡單模型，即Boid（Bird-oid）模型。這個模型是為了模擬鳥群的行為而設計的，它也是粒子群最佳化算法的直接來源。

一個最簡單的模型是這樣的：每一個鳥的個體用直角坐標繫上的點表示，隨機地給它們賦一個初速度和初位置，程式運行的每一步都按照“最近鄰速度匹配”規則，很快就會使得所有點的速度變得一樣。因為這個模擬太簡單而且遠離真實情況，於是在速度項中增加了一個隨機變數，即在疊代的每一步，除了滿足“最近鄰速度匹配”之外，每一步速度還要添加一個隨機變化的量，這樣使得整個模擬看起來更為真實。

Heppner設計了一個“谷地模型”來模擬鳥群的覓食行為。假設在平面上存在一個“谷地”，即食物所在地，鳥群開始時隨機地分散在平面上，為了尋覓食物所在地，它們按照如下規則運動：

pso

首先假設谷地的位置坐標為，單個鳥的位置和速度坐標分別為和，用當前位置到谷地的距離：

來衡量當前位置和速度的“好壞程度”，離谷地的距離越近，則越“好”，反之越“壞”。假設每一個鳥具有記憶能力，能夠記住曾經達到的最好位置，記作pBest，並記a為系統規定的速度調節常數，rand為一個[0,1]間的隨機數，設定速度項按照下述規則變化：

然後假設群體之間可以以某種方式通訊，每個個體能夠知道並記住到當前為止整個群體的最好位置，記為gBest，記b為系統規定的速度調節常數，Rand為一個[0,1]間的隨機數，則速度項在經過以上調整後，還必須按照下述規則變化：

pso

在計算機上模擬的結果顯示：當a/b較大時，所有的個體很快地聚集到“谷地”上；反之，粒子緩慢地搖擺著聚集到“谷地”的四周。通過這個簡單的模擬，發現群體能很快地找到一個簡單函式（2-1）的最優點。受該模型啟發，Kennedy和Eberhart設計出了一種演化最佳化算法，並通過不斷的試驗和試錯，最後將此算法的基本型固定為：

pso

其中符號的意義同上。研究者認為每個個體被抽象為沒有質量和體積，而僅僅具有速度和位置的微粒，故將此方法稱為“粒子群”最佳化算法。

據此，可對粒子群算法小結如下：粒子群算法是一種基於種群的搜尋過程，其中每個個體稱作微粒，定義為在D維搜尋空間中待最佳化問題的潛在解，保存有其歷史最優位置和所有粒子的最優位置的記憶，以及速度。在每一演化代，微粒的信息被組合起來調整速度關於每一維上的分量，繼而被用來計算新的微粒位置。微粒在多維搜尋空間中不斷改變它們的狀態，直到到達平衡或最優狀態，或者超過了計算限制為止。問題空間的不同維度之間唯一的聯繫是通過目標函式引入的。很多經驗證據已經顯示該算法是一個非常有效的最佳化工具。微粒群最佳化算法的流程圖見圖2-1。

以下給出微粒群算法的比較完整的形式化表述。在連續空間坐標系中，微粒群算法的數學描述如下：設微粒群體規模為N，其中每個微粒在D維空間中的坐標位置向量表示為，速度向量表示為，微粒個體最優位置（即該微粒經歷過的最優位置）記為，群體最優位置（即該微粒群中任意個體經歷過的最優位置）記為。不失一般性，以最小化問題為例，在最初版本的微粒群算法中，個體最優位置的疊代公式為：

pso

群體最優位置為個體最優位置中最好的位置。速度和位置疊代公式分別為：

pso

由於初始版本在最佳化問題中套用時效果並不太好，所以初始算法提出不久之後就出現了一種改進算法，在速度疊代公式中引入了慣性權重ω，速度疊代公式變為：

pso

雖然該改進算法與初始版本相比複雜程度並沒有太大的增加，但是性能卻有了很大的提升，因而被廣泛使用。一般的，將該改進算法稱為標準微粒群算法，而將初始版本的算法稱為原始微粒群算法。

通過分析PSO算法的收斂行為，Clerc介紹了一種帶收縮因子的PSO算法變種，收縮因子保證了收斂性並提高了收斂速度。此時的速度疊代公式為：

pso

顯然，疊代公式（2-7）和（2-8）並無本質區別，只要適當選取參數，二者完全相同。

微粒群算法有兩種版本，分別稱為全局版本和局部版本。在全局版本中，微粒跟蹤的兩個極值為自身最優位置pBest和種群最優位置gBest。對應的，在局部版本中，微粒除了追隨自身最優位置pBest之外，不跟蹤種群最優位置gBest，而是跟蹤拓撲鄰域中的所有微粒的最優位置nBest。對於局部版本，速度更新公式（2-7）變為：

pso

其中為局部鄰域中的最優位置。

pso

每一代中任意微粒疊代的過程見圖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算法的研究現狀作一梳理。由於文獻太多，無法面面俱到，僅撿有代表性的加以綜述。

理論分析

當前對微粒群算法開展的理論研究主要集中在微粒群算法的原理方面，即微粒之間是如何相互作用的，為什麼微粒群算法對於很多最佳化問題是有效的，而對於有些問題則效果不是很明顯。具體來說，這個問題的研究又分為三個方面，其一是單個微粒的運動軌跡；其二是收斂性問題；其三是整個微粒系統隨時間的演化和分布。

對簡化微粒行為的第一個分析由Kennedy給出，通過仿真給出了一系列設計選擇的情況下不同的微粒軌跡。對簡化微粒群算法的第一個理論分析由Ozcan給出，作者在文中指出，在一個簡化的一維PSO系統中，微粒沿著一條由正弦波定義的路徑前進，隨機確定其幅度和頻率。但是，他們的分析僅限於沒有慣性權重的簡單PSO模型，並且假定Pid和Pgd保持不變。事實上，Pid和Pgd會頻繁變化，於是微粒軌跡由很多不同幅度和頻率的正弦波合成，整個軌跡看起來仍然是無序的。這使得他們的結論的有效性大打折扣。

對算法穩定性質的第一個形式化分析由Clerc給出，但是該分析需要將隨機係數視作常數，從而將標準隨機PSO算法簡化為一個確定型動態系統。這樣得到的系統是一個二階線性動態系統，其穩定性依賴於系統的極點或狀態矩陣的特徵根。van den Bergh對基於確定型版本的PSO算法進行了類似的分析，並確定了在參數空間中保證穩定性的區域。在文獻和中也提出了關於收斂性和參數選擇的內容，但是作者承認他們並沒有考慮算法的隨機特性，因此其結果有局限性。類似的還有對連續時間版本的PSO算法所作的分析。

Blackwell針對球形對稱局部鄰域的函式，對PSO算法中多樣性缺失的速度進行了理論分析和實驗驗證。Kennedy系統地研究了速度對PSO算法的影響，有助於理解速度對算法性能的貢獻。

Kadirkamanathan等採用李雅普諾夫穩定性分析和被動系統（Passive System）的概念，對微粒動力學的穩定性進行了分析。該分析中沒有假定所有參數均為非隨機的限制，得出了穩定的充分條件，並給出示例。仿真結果驗證了理論的預期，微粒動力學的穩定需要在慣性權重減小時，增大隨機參數的最大值。該分析是基於隨機微粒動力學的，將微粒動力學表達為一個非線性反饋控制系統。該系統有一個確定型線性部分和一個非線性部分，以及/或在反饋路徑上的時變增益。該文雖然考慮了隨機分量的影響，但是其穩定性分析是針對最優位置所進行的（群體最優和個體最優相同），其結論不能直接套用到非最優的微粒。

Clerc研究了處於停滯階段的微粒群算法的疊代過程，對疊代過程中的各隨機係數進行了詳細的研究，給出了各隨機係數的機率密度函式。

Jiang將微粒群算法中每一演化步驟時的微粒位置量視作一個隨機向量，考查了微粒群算法中慣性權重ω和學習因子c1、c2等參數對算法收斂性的影響，並採用隨機過程理論分析了標準微粒群算法的隨機收斂性。

原始PSO算法即使能夠收斂，也只能收斂到群體所搜尋到的最好解，而不能保證該收斂解是最優解，甚至不能保證它是局部最優解。van den Bergh提出一種保證收斂的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在的基礎上，在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算法中的運動規則來替代演化算法中交叉運算元的功能。

參數選擇

微粒群算法中比較重要的幾個參數為：慣性權重ω（或壓縮因子χ）、學習因子c1和c2、速度限制Vmax、位置限制Xmax、種群大小和初始種群。有研究者固定其他參數，研究單個參數對算法的影響；也有研究者同時研究多個參數對算法的影響。Shi對PSO算法中的參數選擇進行了最早的討論。

當前的研究普遍認為慣性權重對微粒群算法性能的影響最大，因此這方面的研究最多。王俊偉對PSO算法中的慣性權重進行了系統的實驗，分析了固定權重與時變權重的選擇問題，並從問題依賴性、種群大小和拓撲結構等方面詳細分析了慣性權重對於算法性能的影響。結果表明，慣性權重的問題依賴性較小，隨著種群的增大，其取值應適當減小，局部版本下慣性權重的選擇具有更大的自由度。陳貴敏提出了開口向下拋物線、開口向上拋物線和指數曲線等非線性慣性權重遞減策略並與線性遞減策略進行比較，試驗結果表明，凹函式遞減策略優於線性策略，而線性策略優於凸函式策略。

一般認為，在微粒群算法中，慣性權重用於平衡全局和局部搜尋能力，較大的慣性權重更傾向於全局搜尋，而較小的慣性權重適於局部搜尋。因此慣性權重的取值應隨時間逐漸減小，而Zheng聲稱遞增的慣性權重性能更好，但是在該文中使用了一組不同於標準PSO算法的學習因子，並且在該文中沒有說明這對性能的影響。

由於固定的慣性權重往往無法獲得好的效果，因此出現了慣性權重在搜尋過程中隨疊代代數線性下降、模糊自適應變化、按非線性函式下降、按餘弦規律下降、按雙曲線規律下降、按Sugeno函式規律下降的PSO算法。與此同時，還有很多種慣性權重隨某種評價指標自適應變化的方法，如根據搜尋的成功歷史、微粒平均速度、種群多樣性、目標函式平整性的變化、微粒群進化速度和聚集程度、個體搜尋能力（ISA）來動態調整慣性權重。Liu根據Metropolis準則來確定是否接受慣性權重的變化。

也有人使用隨機慣性權重，如將其設定為[0.5+(Rnd/2.0)]、取為在[0,1]區間均勻分布的隨機數。Jiang在慣性權重的選取過程中引入混沌機制，使得慣性權重的取值能夠遍歷[0, 1]區間。

學習因子c1和c2代表了將每個微粒拉向pBest和gBest（或nBest）位置的隨機加速項的權重。從心理學的角度而言，認知項（Cognition term）代表了個體複製已被證明是成功的過去行為的趨勢，而社會項（Social term）代表了追從他人成功經驗的趨勢。c1和c2很多時候被設定為2.0，顯而易見的原因是它將使得搜尋復蓋以pBest和gBest為中心的區域。另一個常用的值為1.49445，它可以確保PSO算法的收斂。Carlisle通過大量實驗，提出一套比較好的參數設定為將c1和c2分別設定為2.8和1.3，且該參數設定的性能在中得到進一步肯定。受時變慣性權重的思想啟發，出現了多種學習因子隨時間變化的PSO算法變種，如學習因子隨時間線性下降、根據微粒的演化狀態動態調整、根據適應值持續變差的次數和種群的分散程度來動態調整。高鷹建立了學習因子和微粒群中所有微粒的平均適應度與整體最優位置適應度之差的一種非線性函式關係，通過非線性時變的學習因子自適應地調整“認知”部分和“社會”部分對微粒的影響，從而提高算法的收斂速度和精度。

在大多數情況下，兩個學習因子的取值相同，從而使得社會搜尋和認知搜尋有相同的權重。Kennedy研究了兩個極端情況：只有社會項的模型和只有認知項的模型，結論是這兩個部分對微粒群搜尋的成功而言都很關鍵，對非對稱的學習因子尚無確定的結論報告。Depuy等分析了最大速度、社會學習因子和認知學習因子對微粒群算法在搜尋空間中找到最優點的能力的影響，但是分析過於簡單。

還有的研究同時確定慣性權重和學習因子。有很多研究者採用各種最佳化技術來動態確定慣性權重和學習因子，如遺傳算法、混沌尋優方法、演化算法、微分演化算法、自適應校正設計（Adaptive CriticDesign）技術。Silva基於共生機制，使用另外一個PSO算法來動態確定原算法的參數。Krohling將慣性權重設定為零，同時用兩個服從分布的隨機變數來取代c1r1和c2r2，其中為期望為0、方差為1的高斯分布。Arumugam根據一個由pBest和gBest確定的函式來動態地確定慣性權重和學習因子。Breaban將速度更新公式中的各項解釋為運算元的操作，並引入了一些新的運算元，據此來同時自適應地確定慣性權重和學習因子。Ueno對微粒採用多組參數值，並利用微粒速度的平均值來動態確定慣性權重和學習因子。Khosla使用Taguchi方法來確定算法參數。Kuo採用十七個低維函式最佳化問題，針對單個極小和多個極小的情況研究了慣性權重和學習因子的取值範圍。

微粒的速度可以受一個最大速度Vmax的限制，由此作為一種約束來控制微粒群的全局探索能力。在最初的原始PSO算法中，採用的參數為，，微粒的速度經常會快速地增長到非常大的值，這樣會影響算法的性能，所以需要對微粒速度進行限制。後來，Clerc指出速度限制並非必須的，引入收縮因子同樣可以實現限制微粒速度的目的。不過，即便採用收縮因子，試驗表明如果同時加以速度限制能夠獲得更好的結果，因此速度限制一直被保留下來。一般而言，Vmax被設定為每個變數的動態範圍的值，一般為固定值，但也可以隨時間線性遞減或者根據搜尋的成功歷史來動態減小。

微粒的位置可以受最大位置Xmax的限制，避免微粒飛出有物理意義的解空間之外。Zhang提出一種周期性模式的邊界處理方法。Robinson提出了三種控制技術，分別為吸引牆、反射牆和不可見牆。一旦微粒的某一維碰到解空間的邊界，則吸引牆方法將速度設為零，反射牆方法改變速度方向，由此這兩種方法最終都可以將微粒拉回到允許的解空間範圍內。而不可見牆方法對飛出邊界的微粒不計算適應值，以節約計算時間並避免影響其它微粒的運動。但是，這三種邊界條件下PSO算法的性能受問題的維度以及全局最優點與搜尋空間邊界的相對位置影響很大。為解決這一問題，Huang綜合吸收牆和反射牆的特點，在其基礎上提出一種混合的阻尼邊界，以獲得魯棒且一貫的性能。而Mikki將硬位置限制和吸引牆、反射牆技術結合起來，試驗表明能夠獲得更好的效果。

種群大小的選擇與問題相關，但是對問題並不十分敏感。20-50是比較常見的選擇。在某些情況下，可能會使用較大的種群來適應特殊需要。

種群的初始化也是一個很重要的問題。一般情況下初始種群都是隨機產生，但是也有多種智慧型化的種群初始化方法，如使用非線性單純形法（NSM），重心Voronoi劃分、正交設計、均勻設計等方法來確定PSO算法的初始種群，以使得初始種群的分布儘可能均勻，幫助算法更有效地探索搜尋空間並找到更好的解。Robinson指出PSO算法和GA算法可以順序使用，將PSO算法完成最佳化之後的種群作為GA算法的初始種群，或者反之，將GA算法完成最佳化之後的種群作為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算法的更新公式和過程是面向連續空間並為其設計的，因此需要做一些修改使之適應離散空間的情況。編碼的修改可能很簡單，難點在於定義速度的意義和確定軌跡的變化。

Kennedy定義了第一個離散二進制版本的PSO算法。微粒使用二進制字元串進行編碼。通過使用sigmoid函式，速度被限制在[0, 1]區間之內，並被解釋為“機率的變化”。Yang對該方法在量子空間進行了擴展。

Mohan提出了幾種二進制方法（直接方法、量子方法、正則方法、偏差向量方法以及混合方法），但是從有限的實驗中沒有得出什麼結論。Clerc對一些專用於某些約束最佳化問題如TSP問題的PSO算法變種進行了試驗，結果顯示該方法比較有前途。Pang使用模糊矩陣來表示微粒的位置和速度，對PSO算法的算符進行了重定義，並將其套用到TSP問題的求解。Pampara將PSO算法與信號處理中的角調製技術結合起來，將高維二進制問題降維為一個在連續空間中定義的四維問題，並通過求解該四維問題來獲得原問題的解。Afshinmanesh重新定義了離散PSO算法中的加法與乘法，並使用人工免疫系統中的陰性選擇來實現速度限制Vmax。

Hu提出了一種改進PSO算法來處理排列問題。微粒被定義為一組特定值的排列，速度基於兩個微粒的相似度重新定義，微粒根據由它們的速度所定義的隨機率來變換到一個新的排列。引入了一個變異因子來防止當前的pBest陷入局部最小。在n皇后問題上的初步研究顯示改進的PSO算法在解決約束滿意問題方面很有前途。

Migliore對原始的二進制PSO算法進行了一些改進，提出了可變行為二進制微粒群算法（VB-BPSO）和可變動態特性二進制微粒群算法（VD-BPSO）。VB-BPSO算法按照連續PSO算法的速度更新公式的思想設計了一個新的速度更新公式，用來確定微粒位置向量每一位為1的機率。而VD-BPSO算法則是根據一定規則在兩組不同參數確定的VB-BPSO算法之間切換。Migliore套用該算法設計出一種簡單魯棒的自適應無源天線。

Parsopoulos以標準函式為例測試微粒群最佳化算法解決整數規劃問題的能力。Salman將任務分配問題抽象為整數規劃模型並提出基於微粒群最佳化算法的解決方法。兩者對疊代產生的連續解均進行舍尾取整後評價其質量。但是PSO算法生成的連續解與整數規劃問題的目標函式評價值之間存在多對一的映射，以整型變數表示的目標函式不能準確反映算法中連續解的質量，而由此導致的冗餘解空間與相應的冗餘搜尋降低了算法的收斂效率。

高尚採用交叉策略和變異策略，將PSO算法用來解決集合劃分問題。趙傳信重新定義了微粒群位置和速度的加法與乘法操作，並將PSO算法套用到0/1背包問題求解中。EL-Gallad在PSO算法中引入探索和勘探兩個運算元，用於求解排序問題。Firpi提出了BPSO算法的一種保證收斂的版本（但是並未證明其保證收斂性），並將其套用到特徵選擇問題。

上述離散PSO算法都是間接的最佳化策略，根據機率而非算法本身確定二進制變數，未能充分利用PSO算法的性能。在處理整數變數時，PSO算法有時候很容易陷入局部最小。原始PSO算法的思想是從個體和同伴的經驗進行學習，離散PSO算法也應該借鑑該思想。高海兵基於傳統算法的速度—位移更新操作，在分析微粒群最佳化機理的基礎上提出了廣義微粒群最佳化模型（GPSO），使其適用於解決離散及組合最佳化問題。GPSO 模型本質仍然符合微粒群最佳化機理，但是其微粒更新策略既可根據最佳化問題的特點設計，也可實現與已有方法的融合。基於類似的想法，Goldbarg將局部搜尋和路徑重連過程定義為速度運算元，來求解TSP問題。

並行算法

與大多數隨機最佳化算法相似，當適應值評價函式的計算量比較大時，PSO算法的計算量會很大。為了解決該問題，研究者提出了並行PSO算法。與並行遺傳算法類似，並行PSO算法也可以有三種並行群體模型：主從並行模型、島嶼群體模型和鄰接模型。

Schutte採用同步實現方式，在計算完一代中所有點的適應值之後才進入下一代。這種並行方法雖然實現簡單，但常常會導致並行效率很差。故而有人提出異步方式的並行算法，可以在對數值精度影響不大的條件下提高PSO算法的並行性能。這兩種方式採用的都是主從並行模型，其中異步方式在求解上耦合性更高，更容易產生通信瓶頸。

Baskar提出一種兩個子種群並行演化的並發PSO算法，其中一個子種群採用原始的PSO算法，另一個子種群採用基於適應值距離比的PSO算法（FDR-PSO）；兩個子種群之間頻繁地進行信息交換。而El-Abd研究了在子種群中採用局部鄰域版本的協作PSO算法，並研究了多種信息交換的方式及其對算法性能的影響。黃芳提出一種基於島嶼群體模型的並行PSO算法，並引入一種集中式遷移策略，提高了求解效率，同時改善了早收斂現象。

Li提出延遲交換信息的並行算法屬於鄰接模型，該算法可以提高速度，但可能使得解的質量變差。

最佳化求解

PSO算法被廣泛套用於各種最佳化問題，並且已經成為最佳化領域中的一個有效算法。除了普通函式最佳化之外，還包括如下方面。

很多求解整數規劃的算法是在採用實數域的算法進行最佳化後，再將結果取整作為整數規劃的近似解。這種做法常常導致不滿足約束或遠離最優解。譚瑛提出一種在整數空間中直接進行進化計算的PSO算法。劉釗針對混合整數非線性規劃中可行解產生代價較高的問題，建立了保證都是合法解的備用微粒庫，並提出微粒遷移策略，幫助微粒跳出局部最優。

動態系統的狀態會經常改變，甚至可能會連續變化。許多實際系統都會涉及到動態環境。例如，由於顧客的優先權、意外的設備維護等導致的變化，調度系統中大多數計算時間都被用來進行重新調度。在實際套用中，這些系統狀態的變化就需要經常進行重新最佳化。

最初使用微粒群算法跟蹤動態系統的工作由Carlisle提出，通過周期性地重置所有微粒的記憶來跟蹤動態系統。Eberhart也採用類似想法；之後Hu提出一種自適應PSO算法，能夠自動跟蹤動態系統中的不同變化，並在拋物線benchmark函式上對不同的環境檢測和回響技術進行了實驗，其中使用的檢測方法是監控種群中最優微粒的行為。後來Carlisle使用搜尋空間中的一個隨機點來確定環境是否發生變化，但是這需要集中控制，與PSO算法的分散式處理模型不符。為此Cui提出TDPSO算法，讓最優歷史位置的適應值隨著時間減小，從而不再需要集中控制。Blackwell在微粒的更新公式中添加了一項懲罰項，來保持微粒處於一個擴展的群中，以應對快速變化的動態環境，該方法中不需要檢測最優點是否發生變化。

Parsopoulos等的試驗表明，基本PSO算法就可以有效而穩定地在噪聲環境中工作，且在很多情況下，噪聲的存在還可以幫助PSO算法避免陷入局部最優。Parsopoulos還通過試驗研究了UPSO算法在動態環境中的性能。Pugh提出一種抗噪聲的PSO算法。Pan將假設檢驗和最優計算預算分配（OCBA）技術引入微粒群算法，提出PSOOHT算法，來解決噪聲環境下的函式最佳化問題。

上述工作的研究對象都是簡單的動態系統，所採用的實驗函式是簡單的單模函式，並且所涉及的變化都是簡單環境下的均勻變化（即固定步長）。而事實上，實際的動態系統經常是非線性的，並在複雜的多模搜尋空間中非均勻變化。Li採用四個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

一是指工藝認證(Process Sign-Off)，此為客戶對供應商/代工廠進行的生產工藝流程的審核；

二是指微粒群最佳化算法。

工藝認證

英文名：Process Sign-Off

此為客戶對供應商/代工廠進行的生產工藝流程的審核， 旨在確定客戶對供應商/代工廠的要求，細化為證實和保證滿足客戶的質量系統要求所應具備的能力。

在產品或系統的有效期內任何產品或工藝需要更改，必須通過客戶產品團隊的評審以確定在風險值的基礎上是否需要重新進行PSO認證

PSO目的：在於驗證供應商工藝能力，是驗證供應商質量策划過程是否成功及在批量生產中是否具備批量生產合格產品的生產工藝的一種方法。

PSO是什麼：PSO是系統和連貫地對供應商策劃和實際實施的最高標定生產節拍下的生產工藝進行審核，包括人員、設施、設備、材料、方法、程式、軟體水平和工裝。客戶的驗證方法能確保供應商系統可接收並能生產出高質量的產品。

首先，檔案需確保操作的方法都已記錄並可供所有的員工參考。在培訓新員工時，還可幫助有經驗的員工解決一些不尋常的情況或變化。

其次，應親臨現場獲得第一手資料。所以，作為PSO工作的一部分就是審核者親臨生產現場，至少目睹使用生產正式工裝進行一批產品的生產。生產的節拍和質量必須滿足客戶的要求。

第三，對生產的產品進行測量和分析，親臨現場能看到生產過程中出現的特殊問題和生產效率的情況，收集數據並進行分析和歸納是獲取真實質量和生產效率情況的手段。通過測量可以得出生產節拍，FTC，單位產品所需淨生產時間及其它統計數據，從而證實供應商是否有能力生產出滿足客戶要求的產品。

最後，通過對產品的試驗來證實供應商的體系是否有效，並且通過數據來表明產品滿足了性能、工藝及材料技術條件中所包含的工程，質量，壽命和可靠性要求。

總而言之，PSO工作程式確保了供應商顯示其滿足PPAP要求的能力。

是誰：產品工作組（至少由供應商質量專家、工程師、供應商及其他合適的人員組成）。

何地：工藝認證的檔案審核的預備會議最好是在供應商生產所在現場進行。如果產品工作組認為有必要時，現場工藝認證也可以在一級分供應商的生產現場進行。

何時：當產品工作組在預備會議中確認如下條件都已滿足後，方可決定進行現場工藝認證的時間：

l 對供應商的檔案已全部審核完畢並接受。

l 生產工裝完成、定案並已在供應商現場安裝和調試完畢，並且供應商自己的生產準備評估已經全部完成並有檔案記錄。

l 生產工序已確定並調試完畢，前期操作情況已經確定，並準備好按預先確定的抽樣大小和生產節拍進行生產演示。

l 生產操作者已經培訓並能在標定最大和持續的生產節拍下進行生產。