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

關(guān)鍵詞：進(jìn)化計(jì)算 微粒群算法 微粒狀態(tài)

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

一、標(biāo)準(zhǔn)微粒群算法

（一）算法流程

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

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

（二）參數(shù)分析

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

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

二、微粒群算法的改進(jìn)

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

（一）增加收斂因子

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

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

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

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

（三）與智能進(jìn)化算法的結(jié)合

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

（四）新的群體組織結(jié)構(gòu)

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

三、微粒群算法的應(yīng)用

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

四、結(jié)論

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

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

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

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

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

參考文獻(xiàn)：

[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].計(jì)算機(jī)研究與發(fā)展，200643（1）：96～100.

（責(zé)編 張景賢）