ＭＱＰＳＯ： 一種具有多群體與多階段的ＱＰＳＯ算法

摘 要：提出了一種改進的QPSO（Quantum—behaved Particle Swarm Optimization）算法，即一種具有多群體與多階段的具有量子行為的粒子群優化算法。在該算法中，粒子被分為多個群體，利用多個階段進行全局搜索，這樣可以有效地避免粒子群早熟，提高了算法的全局收斂性能。對幾個重要測試函數的測試結果證明，MQPSO算法的收斂性能優于標準粒子群算法（Standard Particle Swarm Optimization， SPSO）以及QPSO算法。

關鍵詞：粒子群算法； 量子行為； 全局收斂； 早熟

中圖分類號：TP311文獻標志碼：A

文章編號：1001—3695(2007)03—0100—03

James Kennedy和Eberhart在1995年的IEEE國際神經網絡學術會議上正式發表了題為“Particle Swarm Optimization”(PSO)的文章，標志著微粒群算法的誕生。在經典的PSO粒子群系統中，粒子的收斂是以軌道形式實現的；并且由于粒子的速度總是有限的，在搜索過程中粒子的搜索空間是一個有限的區域，不能覆蓋整個可行空間。一般的PSO算法不能保證以概率1搜索到全局最優解，這正是一般PSO算法的最大缺陷。而在量子空間中粒子滿足聚集態的性質則完全不同，它可以在整個可行解空間中進行搜索，因而量子PSO算法(Sun等人提出的QPSO)的全局搜索性能遠遠優于一般PSO算法。但是與標準的PSO算法一樣，在量子PSO算法中同樣存在早熟的趨勢，也就是當群體進化時，群體的多樣性不可避免地減少。這是因為當粒子群進化時，有一部分粒子由于速度越來越小而變得沒有活力，這樣在下一輪進化中它們將失去局部搜索能力和全局搜索能力。

為了提高算法的收斂性能，本文在QPSO的基礎上，提出了一種改進的QPSO算法，即MQPSO算法。在該算法中為了提高粒子群體的多樣性使群體能夠持續地進化發展，將粒子分為多個群體，在不同的階段進行全局搜索，算法的全局收斂能力大大提高了，避免了粒子群的早熟。

1 基本PSO算法及改進的PSO(SPSO)

PSO算法最早是在1995年由美國社會心理學家James Kennedy和電氣工程師Russell Eberhart共同提出的。其基本思想是受他們早期對鳥類群體行為研究結果的啟發，并利用了生物學家Frank Heppner的生物群體模型。微粒群算法不像其他進化算法那樣對個體使用進化算子，而是將每個個體看作是在n維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經驗和群體的飛行經驗進行動態調整。

當慣性權重w=1時，式(3)與基本粒子群算法的速度進化方程一樣。文獻[5]建議w的取值范圍為[0，1.4]。但實驗結果表明當w取[0.8，1.2]時，算法的收斂速度更快；而當w>1.2時算法則較多地陷入局部極值。

目前，有關PSO算法的研究大多數以帶慣性權重的PSO算法為基礎進行擴展和修正。為此，大多數文獻將帶慣性權重的PSO算法稱之為標準PSO算法(SPSO)。

2 QPSO算法

PSO是基于種群的進化搜索技術，但是所有基本的和改進的PSO算法不能保證算法的全局收斂。因為PSO的進化方程式使所有粒子在一個有限的樣本空間中搜索。根據粒子群的基本收斂性質，受量子物理基本理論的啟發，Sun等人提出的QPSO（Quantum—behaved Particle Swarm Optimization）[1，2]算法是對整個PSO算法進化搜索策略的改變，并且進化方程中不需要速度向量，而且進化方程的形式更簡單，參數更少且更容易控制。QPSO算法，在搜索能力上優于所有已開發的PSO算法。

其中，β被稱為收縮擴張系數，調節它的值能控制算法的收斂速度。一般而言，β值在算法運行是從1.0線性減小到0.5時，可以達到比較好的效果，即

在QPSO中，粒子的狀態只需用位置向量來描述，并且算法中只有一個收縮擴張系數β，對這個參數的選擇和控制是非常重要的，它關系到整個算法的收斂性能。

3 MQPSO算法

與標準的PSO一樣，QPSO同樣存在早熟的趨勢。對于單個粒子來講，失去全局搜索能力意味著它只能在一個相當小的空間中運動，這種情況總是發生在當單個粒子所經歷的最佳位置pbest和群體的最佳位置gbest非常接近時。在標準的PSO中，從它的進化方程中可以看出當pbest和gbest之間的距離接近0時，粒子的速度也將接近0。在QPSO系統中，pbest和gbest很接近意味著粒子的參數L很小，于是粒子的搜索范圍也變得很小;而局部搜索能力的失去意味著粒子的運行對適應值產生的影響根本無法觀測。這樣，粒子群的進化就會停滯。如果這個時候粒子群的當前最佳位置gbest處于一個局部最優解，那么由于所有的粒子變得越來越失去活力，整個粒子群就會趨于早熟收斂。

為了提高算法的收斂性能，本文在QPSO的基礎上，把粒子群分為多個群體，分多個階段進行搜索。理論上已經證明了當參數β<1.77時，粒子收斂，靠近粒子群的當前最佳位置gbest;當β>1.78時，粒子發散，遠離粒子群的當前最佳位置gbest。在本文中，將粒子群分成兩組，每一組又分成兩個階段，即在第一組里，階段1設置系數β=0.72，粒子收縮;階段2設置系數β=2，粒子擴張。在第二組里，階段1設置參數β=1.8，粒子擴張;階段2設置系數β=0.72，粒子收縮。所以在一組里，一階段的粒子擴張時，另一階段的粒子就收縮，避免了粒子趨于早熟收斂。

對每一個測試函數分別使用了不同的種群大小和不同的決策變量維數。其中前三個測試函數的種群大小分別是40、80，維數分別是10、20、30，最大迭代次數分別是1 000、1500、2000。最后一個測試函數的維數均為2，最大迭代次數都為2000。表1列出了算法對每一個測試函數的初始化區域。表2是算法對每個測試函數速度和位置的上限值V_max和X_max。

表3—6分別記錄了算法運行每一個測試函數50次的平均最好適應值。

通過比較測試結果，可以看到MQPSO的性能比SPSO以及QPSO有了很大的提高，因此在QPSO的基礎上引入將粒子群分成多粒子群和多階段的算法后，全局收斂能力大大地提高了。

5 結束語

本文提出了一種具有量子行為的新的粒子群算法QPSO，它能夠保證算法的全局收斂性，其進化方程與標準粒子群算法PSO的進化方程完全不同，并且算法中的參數較少，只有一個收縮擴張系數β，用來控制算法的收斂速度。QPSO也有其缺陷，即粒子群容易趨于早熟收斂。QPSO中引入把粒子群分成多粒子群和多階段的算法后，增強了QPSO的全局收斂能力。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。