微粒群算法研究與應用分析

（甘肅省莊浪縣職業(yè)教育中心744699）

微粒群算法研究與應用分析

李新春 吳曉峰

（甘肅省莊浪縣職業(yè)教育中心744699）

微粒群優(yōu)化算法（PSO）是一種進化計算技術，通過微粒間的相互作用發(fā)現(xiàn)復雜搜索空間中的最優(yōu)區(qū)域。本文介紹了微粒群算法的產(chǎn)生，標準微粒群算法及流程，算法參數(shù).圍繞微粒群算法的改進形式，算法的應用等方面對微粒群算法的研究現(xiàn)狀進行綜述。

進化計算微粒群算法微粒狀態(tài)

微粒群算法是一種基于群體的、自適應的搜索優(yōu)化方法，是在1995年由美國心理學家James Kennedy和電氣工程師Russell Eberhart共同提出的，其基本思想是受他們早期對鳥類群體行為研究結果的啟發(fā)，并利用了生物學家Frank Heppner的生物群體模型。目前，微粒群算法已成功的應用于函數(shù)優(yōu)化、約束優(yōu)化、極大極小問題、多目標優(yōu)化以及人工神經(jīng)網(wǎng)絡等問題中，與其他智能方法相結合來提高算法的性能，如結合遺傳思想、模擬退火算法等。

一、標準微粒群算法

（一）算法流程

微粒群算法與其他進化算法相類似，其基本思想是：將所優(yōu)化問題的每一個解稱為一個微粒，每個微粒在n維搜索空間中以一定的速度飛行，通過適應度函數(shù)來衡量微粒的優(yōu)劣，微粒根據(jù)自己的飛行經(jīng)驗以及其他微粒的飛行經(jīng)驗，來動態(tài)調整飛行速度，以期向群體中最好微粒位置飛行，從而使所優(yōu)化問題得到最優(yōu)解。

微粒群算法的具體實現(xiàn)步驟如下：第一步：初始化一群微粒，包括微粒的隨機位置和速度。第二步：根據(jù)適應度函數(shù)計算每個微粒的適應值。第三步：對每個微粒xi，將其適應值與所經(jīng)歷過的最好位置pi作比較，如果較好，則將其作為當前的最好位置pi。第四步：對每個微粒，將其適應值與全局所經(jīng)歷的最好位置pg作比較，如果較好，則將其作為當前的全局最好位置。第五步：根據(jù)方程（1）（2）對微粒的速度和位置進行進化。第六步：如未達到結束條件（通常為足夠好的適應值或達到一個預設最大代數(shù)Gmax），則返回第二步，達到要求結束迭代過程，輸出結果。

（二）參數(shù)分析

1.慣性權重w。w對PSO能否收斂起重要作用，它使微粒保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。文獻中首次提出了慣性權重w的概念，并對基本算法中的粒速度更新公式進行了修正，如式（1）所示，以獲得更佳的全局優(yōu)化效果.其后的研究者普遍采用這種方式作為系統(tǒng)粒子速度更新的基本方式，并在大量的應用問題中充分驗證了其合理性，文獻中還提出了采用隨時間遞減的動態(tài)慣性權值設置方法以提高算法的有效性和可靠性。

2.加速常數(shù)c1和c2。在公式（1）中，若c1= c2=0，微粒將一直以當前的速度飛行，直到最優(yōu)值為止，它只能搜索有限的區(qū)域，很難找到最好解；若c1=0，則微粒沒有認知能力，只有社會認知，在微粒的相互作用下，有能力達到新的搜索空間，它的收斂速度比標準微粒群更快，但對復雜問題，則更容易陷入局部最優(yōu)解；若c2=0，則微粒之間沒有社會信息共享，只有認知部分，此時個體間沒有信息交流，所以得到最優(yōu)解的機率很小。

二、微粒群算法的改進

對微粒群優(yōu)化算法的改進主要體現(xiàn)在對參數(shù)的調整，結構的重新定義，和其他智能算法的融合。目前主要改進工作是增加了收斂因子，依據(jù)一定的標準為整個群體或某些微粒的狀態(tài)量重新賦值、與智能進化算法的結合、使用新的位置和速度更新等式和新的群體組織結構。

（一）增加收斂因子

由于不同問題對算法的全局或局部搜索能力會有不同要求，所以算法的全局搜索能力和局部搜索能力之間的平衡關系最好可以調整。文獻提出了一種統(tǒng)一模型，并對模型的進化行為進行理論分析，同時給出了保證PSO算法具有全局收斂性的參數(shù)自適應方案，給不同的參數(shù)賦予不同的值得到不同的微粒群算法模型，適應解決不同問題的要求。

（二）迭代過程中微粒狀態(tài)的調整

為微粒重新賦值微粒的狀態(tài)量包括微粒的位置、速度和搜索空間，為了刺激群體持續(xù)進化，避免群體的早熟收斂和停滯現(xiàn)象，很多研究者指出依據(jù)一定的標準為整個群體或某些微粒的狀態(tài)量重新賦值，以維持群體的多樣性，使算法可持續(xù)進化。

研究者提出了多種動態(tài)調整的自適應微粒群算法，通過分析基本微粒群算法，給出了基于動態(tài)圓形的動態(tài)調整微粒群算法，實例仿真說明該方法不僅具有較快的收斂速度，而且跳出局部最優(yōu)點的能力也大為提高。另有提出了一種改進的自適應微粒群算法.該算法通過引入活性因數(shù)，利用分布式處理模式以及使所有微粒均具有檢測環(huán)境變化的能力的方式，提高了算法在復雜環(huán)境中檢測環(huán)境變化的能力，尤其是在動態(tài)環(huán)境中存在某些靜止的極點，而微粒群收斂于此暫時靜止的極點時，IAPSO算法更能凸現(xiàn)其優(yōu)勢。

（三）與智能進化算法的結合

微粒群算法有其優(yōu)點，也有其缺陷，近年來有很多研究將微粒群和遺傳算法，模擬退火，蟻群算法等只能算法相結合提出了不同的優(yōu)化方法取得了很好的效果，這些研究表明和其他進化算法的結合是微粒群算法的一個重要方向。

（四）新的群體組織結構

社會心理學研究表明：人們的態(tài)度、信仰和行為傾向于朝同伴的方向變化，他們會根據(jù)自己所處群體的規(guī)范選擇自己的意見和行為，而不是某個特定個體的行為，有研究者根據(jù)不同的使用環(huán)境構造了不同的微粒群模型，為微粒群的新結構建立做了大量的工作，也是個重要的研究領域。

三、微粒群算法的應用

目前，已經(jīng)出現(xiàn)了用算法解決整數(shù)規(guī)劃、非線性規(guī)劃、多目標優(yōu)化問題等優(yōu)化問題的文章.此外，該算法在系統(tǒng)辨識、神經(jīng)網(wǎng)絡訓練等方面，也有著廣泛的應用。主要應用于優(yōu)化問題的求解、機器人領域、電力系統(tǒng)領域、交通運輸領域、工程設計與優(yōu)化領域、工業(yè)生產(chǎn)優(yōu)化領域、計算機領域、通訊領域、生物信息領域，微粒群算法的應用范圍和深度都在不斷的加強，隨著算法理論研究的成熟和應用的廣泛進行，為一些NP問題的解決提供更好的算法支持。

四、結論

對微粒群優(yōu)化算法的研究還不是很成熟，許多問題有待解決。具體而言，有以下幾點。

①算法理論：微粒群優(yōu)化算法并沒有能給出嚴格的數(shù)學證明，理論基礎較弱，需要進一步研究，

②算法結構：算法結構包括算法基本形式和各種改進形式，還可以根據(jù)最新的技術和應用提出更好的模式。尤其最近用微粒群思想改進的細菌趨藥性算法取得了較好的效果，得到越來越多的研究者關注。

③算法應用：目前，PSO的應用大量局限于連續(xù)、單目標、無約束的確定性優(yōu)化問題.因此，如何將PSO算法應用于離散、多目標、約束、不確定、動態(tài)等優(yōu)化問題，將是微粒群算法的主要研究方向。

PSO算法作為一種新的智能算法已經(jīng)得到了廣泛的應用，并取得很好的效果，隨著智能計算的不斷發(fā)展，會有更多的改進和應用，尤其算法的應用研究將促進我國高新技術的迅速發(fā)展。

[1]Y Shi R C Eberhart A Modified Particle Swarm Optimizer[A]Proceedings of the IEEE International Conference on Evolutionary computation.Piscataway，N.IEEE Press，1998，69-73．

[2]曾建潮，崔志華.微粒群算法的統(tǒng)一模型及分析[J].計算機研究與發(fā)展，200643（1）：96~100.

（責編 張景賢）