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

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

關(guān)鍵詞：粒子群算法； 量子行為； 全局收斂； 早熟

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

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

James Kennedy和Eberhart在1995年的IEEE國(guó)際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會(huì)議上正式發(fā)表了題為“Particle Swarm Optimization”(PSO)的文章，標(biāo)志著微粒群算法的誕生。在經(jīng)典的PSO粒子群系統(tǒng)中，粒子的收斂是以軌道形式實(shí)現(xiàn)的；并且由于粒子的速度總是有限的，在搜索過(guò)程中粒子的搜索空間是一個(gè)有限的區(qū)域，不能覆蓋整個(gè)可行空間。一般的PSO算法不能保證以概率1搜索到全局最優(yōu)解，這正是一般PSO算法的最大缺陷。而在量子空間中粒子滿足聚集態(tài)的性質(zhì)則完全不同，它可以在整個(gè)可行解空間中進(jìn)行搜索，因而量子PSO算法(Sun等人提出的QPSO)的全局搜索性能遠(yuǎn)遠(yuǎn)優(yōu)于一般PSO算法。但是與標(biāo)準(zhǔn)的PSO算法一樣，在量子PSO算法中同樣存在早熟的趨勢(shì)，也就是當(dāng)群體進(jìn)化時(shí)，群體的多樣性不可避免地減少。這是因?yàn)楫?dāng)粒子群進(jìn)化時(shí)，有一部分粒子由于速度越來(lái)越小而變得沒(méi)有活力，這樣在下一輪進(jìn)化中它們將失去局部搜索能力和全局搜索能力。

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

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

PSO算法最早是在1995年由美國(guó)社會(huì)心理學(xué)家James Kennedy和電氣工程師Russell Eberhart共同提出的。其基本思想是受他們?cè)缙趯?duì)鳥(niǎo)類群體行為研究結(jié)果的啟發(fā)，并利用了生物學(xué)家Frank Heppner的生物群體模型。微粒群算法不像其他進(jìn)化算法那樣對(duì)個(gè)體使用進(jìn)化算子，而是將每個(gè)個(gè)體看作是在n維搜索空間中的一個(gè)沒(méi)有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。

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

目前，有關(guān)PSO算法的研究大多數(shù)以帶慣性權(quán)重的PSO算法為基礎(chǔ)進(jìn)行擴(kuò)展和修正。為此，大多數(shù)文獻(xiàn)將帶慣性權(quán)重的PSO算法稱之為標(biāo)準(zhǔn)PSO算法(SPSO)。

2 QPSO算法

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

其中，β被稱為收縮擴(kuò)張系數(shù)，調(diào)節(jié)它的值能控制算法的收斂速度。一般而言，β值在算法運(yùn)行是從1.0線性減小到0.5時(shí)，可以達(dá)到比較好的效果，即

在QPSO中，粒子的狀態(tài)只需用位置向量來(lái)描述，并且算法中只有一個(gè)收縮擴(kuò)張系數(shù)β，對(duì)這個(gè)參數(shù)的選擇和控制是非常重要的，它關(guān)系到整個(gè)算法的收斂性能。

3 MQPSO算法

與標(biāo)準(zhǔn)的PSO一樣，QPSO同樣存在早熟的趨勢(shì)。對(duì)于單個(gè)粒子來(lái)講，失去全局搜索能力意味著它只能在一個(gè)相當(dāng)小的空間中運(yùn)動(dòng)，這種情況總是發(fā)生在當(dāng)單個(gè)粒子所經(jīng)歷的最佳位置pbest和群體的最佳位置gbest非常接近時(shí)。在標(biāo)準(zhǔn)的PSO中，從它的進(jìn)化方程中可以看出當(dāng)pbest和gbest之間的距離接近0時(shí)，粒子的速度也將接近0。在QPSO系統(tǒng)中，pbest和gbest很接近意味著粒子的參數(shù)L很小，于是粒子的搜索范圍也變得很小;而局部搜索能力的失去意味著粒子的運(yùn)行對(duì)適應(yīng)值產(chǎn)生的影響根本無(wú)法觀測(cè)。這樣，粒子群的進(jìn)化就會(huì)停滯。如果這個(gè)時(shí)候粒子群的當(dāng)前最佳位置gbest處于一個(gè)局部最優(yōu)解，那么由于所有的粒子變得越來(lái)越失去活力，整個(gè)粒子群就會(huì)趨于早熟收斂。

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

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

表3—6分別記錄了算法運(yùn)行每一個(gè)測(cè)試函數(shù)50次的平均最好適應(yīng)值。

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

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

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

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。