粒子群算法的改進(jìn)策略述評(píng)

摘要： 首先介紹了基本粒子群算法。其次分析出四類粒子群算法改進(jìn)策略即混沌優(yōu)化策略﹑調(diào)整參數(shù)取值策略﹑混合啟發(fā)式算法策略﹑保持種群多樣性策略；同時(shí)，對(duì)算法各種改進(jìn)策略實(shí)現(xiàn)原理及實(shí)現(xiàn)方法進(jìn)行介紹。第三對(duì)粒子群算法四類改進(jìn)策略性能進(jìn)行分析。最后對(duì)粒子群算法改進(jìn)策略進(jìn)行展望。

關(guān)鍵詞： 粒子群算法（PSO）； 混沌優(yōu)化； 調(diào)整參數(shù)取值； 混合啟發(fā)式算法； 保持種群多樣性

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228(2012)10-01-03

0 引言

粒子群（Particle Swarm Optimization，PSO）算法是由美國(guó)的心理學(xué)家J.Kennedy和工程師R.C.Eberhart于1995年提出的群體智能進(jìn)化算法[1-2]。該算法具有概念簡(jiǎn)單、參數(shù)較少、易于實(shí)現(xiàn)等特點(diǎn)，所以問(wèn)世以來(lái)受到了很大的關(guān)注。目前，PSO算法廣泛應(yīng)用于多目標(biāo)優(yōu)化、預(yù)測(cè)系統(tǒng)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、智能控制等方面[3-5]。但傳統(tǒng)的PSO算法具有局部搜索能力較差，易陷入局部最優(yōu)，搜索性能對(duì)參數(shù)具有依賴性等缺點(diǎn)。

因此，研究者們從各種角度出發(fā)對(duì)算法進(jìn)行改進(jìn)。目前改進(jìn)算法的研究方向主要有混沌優(yōu)化策略﹑調(diào)整參數(shù)取值策略﹑混合各種啟發(fā)式算法策略﹑保持種群多樣性策略。然而，各種粒子群算法改進(jìn)策略分析的文獻(xiàn)尚未見(jiàn)報(bào)道?；诖耍疚膶?duì)代表性較強(qiáng)的四類改進(jìn)策略進(jìn)行分析研究。

1 基本粒子群優(yōu)化算法

在粒子群算法中，搜索空間中每個(gè)“粒子”的狀態(tài)都代表優(yōu)化問(wèn)題的解。每個(gè)粒子都有一個(gè)適應(yīng)值(fitness value)由被優(yōu)化函數(shù)決定，同時(shí)粒子飛行的方向和距離由速度決定。粒子通過(guò)跟蹤兩個(gè)位置來(lái)更新自身，一個(gè)是粒子自身所找到的最優(yōu)解pbest，即個(gè)體最優(yōu)位置；另一個(gè)是整個(gè)種群當(dāng)前找到的最優(yōu)解gbest，即全局最優(yōu)位置。

PSO算法計(jì)算過(guò)程中，隨機(jī)產(chǎn)生一個(gè)初始種群，同時(shí)賦予每個(gè)粒子一個(gè)隨機(jī)速度，并根據(jù)公式⑴和⑵來(lái)更新粒子的速度和位置[1]。

其中，vid是粒子的速度，w是慣性因子，c1、c2是學(xué)習(xí)因子，φ1、φ2是介于(0，1)之間的隨機(jī)數(shù)，xid是粒子當(dāng)前位置，pid代表粒子當(dāng)前最優(yōu)位置，pgd代表種群當(dāng)前最優(yōu)位置，也就是全局最優(yōu)。根據(jù)式⑴、⑵對(duì)粒子的速度、位置不斷更新進(jìn)化，直至達(dá)到最大迭代的次數(shù)或者達(dá)到所要求的精度停止迭代。在式⑴中，第一項(xiàng)是粒子先前速度的繼承，依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)；第二項(xiàng)是“認(rèn)知”部分，結(jié)合自身以往的經(jīng)驗(yàn)實(shí)現(xiàn)下一步行為決策；第三項(xiàng)是“社會(huì)”部分，表示粒子間的信息共享與合作。

2 粒子群算法的改進(jìn)策略

2.1 混沌優(yōu)化策略

混沌是一種非周期運(yùn)動(dòng)現(xiàn)象普遍存在于非線性系統(tǒng)中，其表現(xiàn)出介于隨機(jī)與規(guī)則之間的運(yùn)動(dòng)行為，具有遍歷性、隨機(jī)性和規(guī)則性特征?；煦鐑?yōu)化是利用混沌運(yùn)動(dòng)的上述特征來(lái)提高隨機(jī)優(yōu)化算法的效率[6-8]。其基本思想是:通過(guò)混沌映射規(guī)則將優(yōu)化變量映射到混沌變量空間的取值范圍內(nèi)，利用混沌序列可以在一個(gè)特定區(qū)域內(nèi)遍歷所有狀態(tài)的特征進(jìn)行尋優(yōu)搜索，最后將獲得的優(yōu)化解線性轉(zhuǎn)換到優(yōu)化空間。

文獻(xiàn)[9]采用邏輯自映射函數(shù)Logistic映射產(chǎn)生混沌序列，在已搜索到的精英粒子周圍嘗試搜索更優(yōu)解并動(dòng)態(tài)調(diào)整搜索范圍，在防止算法陷入局部最優(yōu)的同時(shí)還提高了算法搜索的精度。文獻(xiàn)[10]應(yīng)用Tent映射初始化均勻分布的粒群，并以目前整個(gè)粒子群搜索到的最優(yōu)位置為基礎(chǔ)產(chǎn)生Tent混沌序列，混沌序列的搜索范圍采用自適應(yīng)調(diào)整的方法。該方法可以有效避免計(jì)算的盲目性，還能夠提高搜尋最優(yōu)解的速度。文獻(xiàn)[11]使用Sobol序列映射決策變量初始值，使得初始解集均勻的分布在全決策空間范圍。仿真結(jié)果表明該算法能夠在滿足優(yōu)化解收斂性的同時(shí)獲得更好的種群多樣性。

2.2 調(diào)整參數(shù)取值策略

2.2.1 加速系數(shù)調(diào)整策略

在標(biāo)準(zhǔn)粒子群優(yōu)化算法中，加速系數(shù)c1控制著個(gè)體的“認(rèn)知”能力，加速系數(shù)c2控制著群體的“社會(huì)引導(dǎo)”能力。理想的加速系數(shù)調(diào)整策略是：進(jìn)化的初期應(yīng)該具有較大的c1和較小的c2，這樣利于算法在整個(gè)空間進(jìn)行搜索；進(jìn)化的末期應(yīng)該具有較小的c1和較大的c2，這樣有利于算法收斂到全局最優(yōu)解，從而提高算法的收斂速度和精度。

文獻(xiàn)[12]提出了一種自適應(yīng)擴(kuò)展的簡(jiǎn)化粒子群優(yōu)化算法。該算法采用除去速度項(xiàng)的簡(jiǎn)化算法結(jié)構(gòu)，自適應(yīng)動(dòng)態(tài)調(diào)整加速系數(shù)。實(shí)驗(yàn)結(jié)果顯示，算法能夠有效避免早熟收斂現(xiàn)象，其全局收斂性能明顯提高，收斂速度增快。文獻(xiàn)[13]提出了一種振蕩參數(shù)策略，用以提高粒子群優(yōu)化算法在進(jìn)化后期的收斂性能。在整個(gè)搜索過(guò)程中通過(guò)加速度系數(shù)值的變化交替進(jìn)行全局搜索和局部挖掘。加速度系數(shù)振蕩變化既能提高初期的全局搜索能力，又克服早熟收斂，并使粒子最終趨于全局最優(yōu)。文獻(xiàn)[14]提出了一種帶極值抖動(dòng)的變尺度粒子群優(yōu)化算法，該算法在粒子進(jìn)化過(guò)程中通過(guò)動(dòng)態(tài)調(diào)整學(xué)習(xí)因子來(lái)改善粒子的搜索性能，采用極值抖動(dòng)方法使粒子逃離局部最優(yōu)解。實(shí)驗(yàn)表明，該算法優(yōu)化效率及優(yōu)化精度均優(yōu)于典型粒子群改進(jìn)算法。

2.2.2 慣性權(quán)重調(diào)整策略

為了改善基本PSO算法容易早熟收斂陷入局部最優(yōu)的缺點(diǎn)，Y.Shi和R.C. Eberhart將慣量權(quán)重引入算法的速度進(jìn)化方程中[15]。慣量權(quán)重使得粒子能夠保持運(yùn)動(dòng)慣性，增強(qiáng)了粒子對(duì)新區(qū)域的搜索能力。Shi和R.C.Eberhart的研究表明，慣量權(quán)重較大時(shí)，粒子具有較好的全局搜索能力，而慣量權(quán)重較小時(shí)，粒子則具有較好的局部搜索能力?；谏鲜鲅芯浚麄冞M(jìn)一步提出了慣量權(quán)重線性遞減(linearly decreasing weight，LDW)[16]的調(diào)整方法。LDW方法比基本的PSO算法在性能上有顯著的提高，所以該策略至今仍被眾多研究者所使用。

文獻(xiàn)[17]提出了動(dòng)態(tài)慣性權(quán)重和維變異的改進(jìn)粒子群優(yōu)化算法。算法根據(jù)維多樣性動(dòng)態(tài)地調(diào)整慣性權(quán)重。仿真實(shí)驗(yàn)說(shuō)明該算法能增強(qiáng)粒子全局搜索能力，并且能提高粒子收斂速度。文獻(xiàn)[18]提出了一種全局粒子群優(yōu)化(GPSO)算法。算法中慣性權(quán)重被定義為一個(gè)隨機(jī)數(shù)與一個(gè)指數(shù)型函數(shù)的乘積，這有利于均衡算法的全局搜索和局部搜索。仿真實(shí)驗(yàn)說(shuō)明，算法具有更快的收斂速度和更強(qiáng)的逃離局部最優(yōu)的能力。文獻(xiàn)[19]提出基于正切曲線、正弦曲線和對(duì)數(shù)曲線的非線性慣性權(quán)值調(diào)整策略。實(shí)驗(yàn)結(jié)果顯示，針對(duì)連續(xù)函數(shù)優(yōu)化問(wèn)題，正弦曲線和對(duì)數(shù)曲線方法優(yōu)于傳統(tǒng)的線性調(diào)整策略，而傳統(tǒng)的線性調(diào)整方法又優(yōu)于正切曲線策略。

2.3 混合各種啟發(fā)式算法策略

很多研究者將基本PSO算法與其他智能算法相混合，目的是利用其他智能優(yōu)化算法的優(yōu)勢(shì)來(lái)彌補(bǔ)基本PSO算法的不足。

當(dāng)整個(gè)種群陷入局部最優(yōu)的時(shí)候，PSO算法難以從局部最優(yōu)中跳出。為此，將遺傳算法中的交叉和變異操作引入粒子群算法，以保持種群的多樣性，避免陷入局部最優(yōu)，最終搜索到最優(yōu)解。針對(duì)粒子群算法處理復(fù)雜優(yōu)化問(wèn)題時(shí)可能出現(xiàn)早熟收斂現(xiàn)象，將蟻群算法中信息素表的選擇機(jī)制引入粒子群算法。通過(guò)構(gòu)造單個(gè)粒子的多個(gè)進(jìn)化方向，提高了粒子間的多樣性差異，從而改善算法性能。

文獻(xiàn)[20]集成蟻群算法和PSO算法，并將其應(yīng)用于生物數(shù)據(jù)集的層次分類。文獻(xiàn)[21]在PSO算法中引入選擇機(jī)制對(duì)算法進(jìn)行改進(jìn)，實(shí)驗(yàn)結(jié)果表明對(duì)某些復(fù)雜的測(cè)試函數(shù)效果比較好。文獻(xiàn)[22]在PSO算法中引入變異機(jī)制改進(jìn)算法性能，提高了算法收斂性能。文獻(xiàn)[23] 將遺傳算法中的雜交思想引入標(biāo)準(zhǔn)粒子群優(yōu)化算法中，提出了基于繁殖粒子群優(yōu)化算法的負(fù)荷優(yōu)化分配方法，克服了標(biāo)準(zhǔn)粒子群算法易陷入局部最優(yōu)及遺傳算法優(yōu)化計(jì)算時(shí)間長(zhǎng)的缺陷。文獻(xiàn)[24]提出了一種混合的粒子群優(yōu)化算法（Hybrid Particle Swarm Algorithm，HPSA），將粒子群算法、局部搜索策略以及遺傳操作有效地結(jié)合在一起。實(shí)驗(yàn)結(jié)果表明：HPSA通過(guò)改進(jìn)種群選取方法和擴(kuò)大搜索范圍提高了解的質(zhì)量，在性能上均優(yōu)于目前較有效的混合禁忌搜索算法和啟發(fā)式算法。

2.4 保持種群多樣性策略

保持種群多樣性方法很多，最常見(jiàn)的是使用變異算子增強(qiáng)種群的多樣性。該操作增強(qiáng)了粒子在全局最優(yōu)解附近進(jìn)行隨機(jī)搜索的能力，可以有效避免算法早熟。該策略的關(guān)鍵問(wèn)題是變異概率的選取。過(guò)大的變異概率導(dǎo)致盲目地?cái)U(kuò)大搜索范圍，這會(huì)降低算法的收斂性；而過(guò)小的變異概率則導(dǎo)致粒子被局限在一個(gè)較小搜索范圍內(nèi)，這會(huì)減弱算法跳出局部最優(yōu)的能力，也不足以維持種群的多樣性。

文獻(xiàn)[25]將魚(yú)群算法中擁擠度因子的概念引入粒子群算法，提出了前饋擾動(dòng)粒子群算法，以當(dāng)前最優(yōu)值為圓心擁擠度因子為半徑的圓域內(nèi)計(jì)算粒子的數(shù)量，當(dāng)粒子數(shù)量超過(guò)某一常數(shù)時(shí)，給種群加入適當(dāng)擾動(dòng)避免種群陷入局部最優(yōu)。仿真實(shí)驗(yàn)驗(yàn)證了理論及所提出算法的有效性。文獻(xiàn)[26]提出一種自適應(yīng)指導(dǎo)的文化粒子群算法。算法根據(jù)群體適應(yīng)度方差的值判斷群體空間狀態(tài)，一旦算法陷入局優(yōu)，利用影響函數(shù)自適應(yīng)地對(duì)群體空間進(jìn)行變異更新，實(shí)驗(yàn)結(jié)果表明該算法不僅具有較好的全局收斂性，而且算法收斂速度和穩(wěn)定性也都有顯著提高。文獻(xiàn)[27]借鑒群體位置方差的早熟判斷機(jī)制，將變異算子和基因換位引入到算法中，構(gòu)造出新的個(gè)體及個(gè)體基因的適應(yīng)值函數(shù)，并對(duì)適應(yīng)值最差的基因進(jìn)行變異。實(shí)驗(yàn)表明，該算法具有更快的收斂速度且具有很強(qiáng)的避免陷入局優(yōu)的能力。文獻(xiàn)[28]提出一種基因變異粒子群算法成功的應(yīng)用于在線參數(shù)識(shí)別系統(tǒng)。

3 四類改進(jìn)策略性能分析

PSO常見(jiàn)的缺點(diǎn)是算法后期收斂速度慢、收斂精度差、易陷入局優(yōu)，其根本原因是在進(jìn)化過(guò)程中未能很好保持種群多樣性，這與PSO自身的運(yùn)作機(jī)制有很大關(guān)系。改進(jìn)策略的目的就是改善PSO的這些缺點(diǎn)，從而提升算法的優(yōu)化性能。

3.1 混沌優(yōu)化策略

混沌系統(tǒng)對(duì)初值極其敏感，初始條件的細(xì)微變化會(huì)引起輸出結(jié)果巨大的差異；混沌是確定性系統(tǒng)本身產(chǎn)生的不穩(wěn)定現(xiàn)象，使系統(tǒng)在動(dòng)力性持久性上表現(xiàn)出相似隨機(jī)的復(fù)雜行為，這種性質(zhì)被稱為內(nèi)在隨機(jī)性；在進(jìn)行混沌優(yōu)化搜索時(shí)，由于混沌序列可以在一個(gè)特定區(qū)域內(nèi)不重復(fù)地遍歷所有狀態(tài)，所以混沌搜索已成為一種有效的優(yōu)化工具。

利用混沌序列特征進(jìn)行粒子群的初始化分布，能擴(kuò)大粒子搜索范圍，大大增強(qiáng)算法的搜索多樣性，為找到更優(yōu)解和提高收斂速度奠定堅(jiān)實(shí)的基礎(chǔ)。該策略雖然對(duì)算法性能有一定改善，但同樣存在缺陷：一是不能從根本上克服早熟收斂現(xiàn)象；二是會(huì)導(dǎo)致算法的運(yùn)算量增加。

3.2 調(diào)整參數(shù)取值策略

調(diào)整參數(shù)取值策略思想是算法前期具有較好的全局搜索能力，算法后期具有較好的局部尋優(yōu)能力。這種策略可以通過(guò)調(diào)整加速系數(shù)或者調(diào)整慣性權(quán)重的變化方式來(lái)實(shí)現(xiàn)。

慣性權(quán)重變化方式通常是隨著進(jìn)化代數(shù)的增加而線性變小，而實(shí)際搜索過(guò)程中是非線性的且具有高度復(fù)雜性，如果用這種單純線性遞減的策略來(lái)反映實(shí)際的優(yōu)化過(guò)程，一旦在進(jìn)化的初期搜索不到最優(yōu)點(diǎn)，隨著慣性權(quán)重的逐漸減小，容易使算法陷入局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象；而且對(duì)于不同問(wèn)題，每一代所需要的比例關(guān)系也不相同，所以，線性遞減關(guān)系只對(duì)某些問(wèn)題有效，對(duì)其他問(wèn)題顯然不一定合適。

3.3 混合各種啟發(fā)式算法策略

很多研究者將基本PSO算法與其他智能算法相混合，目的是利用其他智能優(yōu)化算法的優(yōu)勢(shì)來(lái)彌補(bǔ)基本PSO算法的不足。

例如，與遺傳算法混合就是將遺傳算法的基因交叉算子引入到基本 PSO中。通過(guò)對(duì)種群中的粒子兩兩實(shí)施基因操作形成新一代粒子。基因交叉能提高種群質(zhì)量，使得算法后期的收斂速度和精度明顯提高。這類混合粒子群算法能夠在一定程度上使算法保持種群的多樣性，避免陷入局部最優(yōu)；但是也不可避免的使得算法在每次進(jìn)化過(guò)程中的計(jì)算量增加，進(jìn)而影響了PSO的快速收斂能力。

3.4 保持種群多樣性策略

通過(guò)對(duì)粒子速度或位置引入隨機(jī)變異操作來(lái)增強(qiáng)種群多樣性，使算法能夠有效地進(jìn)行全局搜索。該方法的問(wèn)題是過(guò)大的變異率在增加種群多樣性的同時(shí)也將導(dǎo)致群體發(fā)生混亂，使種群不能進(jìn)行精確的局部搜索，同樣降低了算法的收斂速度。

使用變異算子增強(qiáng)種群的多樣性會(huì)破壞粒子結(jié)構(gòu)導(dǎo)致收斂速度慢；而且這種策略也會(huì)增加算法在每次進(jìn)化過(guò)程中的計(jì)算量，進(jìn)而影響了PSO的快速收斂能力。該方法是否合理需要對(duì)具體問(wèn)題進(jìn)行大量的仿真實(shí)驗(yàn)后方能確定。

4 粒子群算法改進(jìn)策略展望

隨著研究者對(duì)粒子群算法研究的不斷深入，算法未來(lái)的改進(jìn)方向總結(jié)如下：

⑴ 可以考慮從新的角度對(duì)PSO算法進(jìn)行改進(jìn)，例如統(tǒng)計(jì)物理和熱力學(xué)理論對(duì)于改進(jìn)粒子群優(yōu)化算法的性能有很大的促進(jìn)作用，又如耗散結(jié)構(gòu)理論和自組織臨界理論等；

⑵ PSO算法是一種基于種群的算法，具有并行性，可以從并行優(yōu)化的角度對(duì)算法進(jìn)行改進(jìn)；

⑶ 拓?fù)浣Y(jié)構(gòu)對(duì)搜索性能的影響較大，可以從分析粒子拓?fù)浣Y(jié)構(gòu)的思路來(lái)改進(jìn)算法。

5 結(jié)束語(yǔ)

本文敘述了粒子群算法的基本原理。對(duì)粒子群算法的各種改進(jìn)策略進(jìn)行了歸納總結(jié)，目前改進(jìn)算法的研究方向主要有混沌優(yōu)化策略﹑調(diào)整參數(shù)取值策略﹑混合各種啟發(fā)式算法策略﹑保持種群多樣性策略；介紹了各種改進(jìn)策略的實(shí)現(xiàn)方法；對(duì)各種改進(jìn)策略進(jìn)行了分析；對(duì)粒子群算法的改進(jìn)策略進(jìn)行了展望。希望本文能為從事粒子群算法研究的學(xué)者提供有價(jià)值的參考。