基于混合概率的新型小波變異量子粒子群算法

胡 皞,常 軍,鞏文龍，劉文波

(蘇州科技學院，江蘇 蘇州 215011)

基于混合概率的新型小波變異量子粒子群算法

胡 皞,常 軍,鞏文龍，劉文波

(蘇州科技學院，江蘇 蘇州 215011)

量子粒子群算法(QPSO)具有全局尋優能力不強，且容易陷入局部最優的缺陷，因此，針對這個問題，提出了一種基于混合概率的新型小波變異量子粒子群(M-WMQPSO)算法的改進算法。該算法首先在粒子進化方程中引入高斯分布，采用混合概率分布進化方程取代標準QPSO進化方程，以此來提高算法的尋優能力。接著，為了更好地提高算法的全局尋優能力，改善算法容易陷入局部最優的缺陷，在粒子進化過程中以一定的概率對粒子進行新型小波變異處理，增加粒子種群的多樣性，避免了粒子在尋優過程中陷入局部最優，從而實現算法全局尋優的目的。最后，采用六個典型測試函數對該改進算法的性能進行驗證。測試結果表明，改進算法的尋優能力和避免局部最優能力都有很大提高。

量子粒子群算法；混合概率；小波；局部最優；全局最優

0 引 言

粒子群算法(Particle Swarm Optimization，PSO)[1]是一種群智能優化算法，其思想來源于對鳥群覓食過程的模擬，通過個體間的競爭與合作，產生群體智能指導優化搜索。該算法具有無需導數信息，計算簡單，且易于實現等優點，可用于解決大量非線性、不可微和多峰值的復雜問題優化，因而已在軟件開發、通信技術、資源分配等眾多領域得到了廣泛應用[2-7]。但是，由于在粒子群算法中，粒子的運動狀態由速度和位置所決定，并且隨著不斷的演化，粒子的運動軌跡是固定不變的,同時,粒子的移動速度在演化中也會受到一定的約束，這些導致粒子的搜索范圍是一個有限的并且逐漸縮小的區域，不能覆蓋整個可行解空間，這就可能越過目標全局最優位置，而陷入局部最優。分析也證明PSO算法并不能以全概率1收斂到全局最優位置[8]。

于是，孫俊[9]根據量子物理基本理論，從量子力學的角度提出了一種具有量子行為的粒子群算法(Quantum-behaved Particle Swarm Optimization，QPSO)[10]。QPSO算法具有控制參數少，操作簡便，能保證粒子概率1全局收斂，并且尋優性能大大優于標準PSO算法。但是，與大多數算法一樣，在迭代后期由于粒子的聚集性，QPSO算法也存在早熟收斂現象。

針對這個問題，文中提出一種基于混合概率分布的,并在粒子進化過程中加入小波變異處理的改進QPSO算法。通過測試函數仿真結果表明，提出的改進算法的尋優能力和計算效率都取得了令人滿意的結果，并且由于加入變異處理，算法的全局尋優能力也得到了增強，有效地避免了粒子陷入局部最優問題。

1 QPSO算法原理

在孫俊等提出的QPSO算法中，粒子的狀態不再由粒子的位置和速度決定，而是通過粒子運動的波函數描述，建立δ勢阱，并求解對應的定態薛定諤方程[11]，得到粒子在空間某一位置的概率密度函數，進而確定位置的分布函數，應用蒙特卡洛方法，得到粒子狀態進化方程：

pi,j(t)=φj(t)·Pi,j(t)+[1-φj(t)]·Gj(t)

(1)

(2)

其中

(3)

式中，p為粒子在進化迭代過程中的吸引子；P為粒子當前最優值；G為粒子全局最優值；X為粒子的當前位置；C為平均最優位置；M為粒子群體數；φ和u均為(0,1)上均勻分布的隨機數；參數α為壓縮-擴張因子[12-13]；t為粒子當前迭代次數。

盡管量子粒子群算法的各方面性能均優于粒子群算法，但是量子粒子群算法與粒子群算法具有相同弊病，就是在迭代搜索尋優過程中全局搜索能力降低的同時群體多樣性也不斷減少，粒子密集堆積，搜索空間變得越來越小，粒子失去活力只會在小范圍內來回徘徊，進化停滯，粒子群最終搜尋的最優解很有可能是局部最優，出現早熟的趨勢。因此如何增強粒子群在進化搜索中后期的全局搜索能力，成為改進量子粒子群算法的關鍵。

2 基于混合概率的QPSO原理

從標準QPSO算法的粒子進化方程可以看出，原來的進化方程中使用單一的概率分布函數，現在考慮使用混合概率分布函數。一維的時候，QPSO算法的粒子進化方程為：

(4)

式中，第二項是一個雙指數分布的隨機項。將該式表示成更一般的形式：

X(t+1)=p(t)±A(t)

(5)

式中，A(t)為一隨機序列，并且收斂到0，這樣，便可以保證X(t)能依概率收斂到p(t)。QPSO算法中，A(t)是服從雙指數分布的。

現將A(t)假定為以下形式：

A(t)=a(t)+b(t)

(6)

式中，a(t)和b(t)是兩個服從不同概率分布的隨機序列。孫俊等曾提出，令a(t)和b(t)分別服從高斯分布和雙指數分布。具體地，分別規定：

(7)

(8)

式中，u(t)服從區間(0,1)內的均勻分布；Rn(t)服從標準高斯分布；參數α和β稱為收縮-擴張系數。

這樣粒子的進化方程便可以寫成:

(9)

而擴展到N維搜索空間中，粒子的進化方程為:

(10)

上式即為基于混合概率的QPSO算法(Mixed-probabilitybasedQuantum-behavedParticleSwarmOptimization，M-QPSO)的粒子進化方程，通過測試函數表明，M-QPSO算法提高了粒子的尋優能力，收斂速度相對于標準QPSO也得到了提高。但是同標準QPSO算法一樣，算法仍容易出現早熟，粒子容易停滯在一些局部極值點，局部收斂問題仍沒有得到很好的改善。

3 新型小波變異原理

由于小波具有變化幅度小、有波動的特性，微調能力強；其兩個控制參數平移因子和尺度因子可以根據不同情況將小波進行平移和縮張，適應性和可變性強。LingSH等[14]將突變小波函數因子用于改進粒子群算法，提出一種混合小波變異粒子群算法。高東慧等[15]改進了突變粒子的吸引中心，提出一種改進小波變異粒子群算法。上述對粒子群算法的改進收到了一定效果，但依然無法避免粒子群算法自身軌道式進化，搜索空間受限的缺陷。盡管如此，小波變異改進粒子群算法為小波變異用于量子粒子群算法提供了可能。于是，文中提出一種新型小波變異方法，即利用小波變異代替收縮-擴張系數α來提高搜索進化進程中的全局搜索能力，增加粒子群的多樣性，幫助粒子群跳出局部最優。

文中將采用復Morlet小波[16]實部作為變異因子，復Morlet小波函數實部的時域表達式為：

(11)

式中，c為尺度因子；b為平移因子；ω0為小波中心圓頻率，一般取ω0=5。

由于變異不涉及時頻轉化，故令b=0，則公式(11)簡化為：

(12)

定義尺度c的計算公式為：

(13)

式中，σ為c的上限最大值；τ為形狀參數。

小波變異進程如下，設在每次迭代更新中每個粒子以概率q突變，q∈(0,1)，變異公式為：

(14)

式中，x取-2.5c到2.5c的均勻分布隨機數，即x∈U(-2.5c,2.5c)。

小波函數的小幅值波動使得在變異公式中可以同時扮演收縮-擴張系數α和勢阱δ的角色，且不定向的隨機波動能增大粒子群全局搜索能力，有利于避免陷入局部最優，優化算法收斂于全局最優。

4 基于混合概率的新型小波變異量子粒子群算法

為了提高QPSO算法的尋優性能，并改善QPSO算法全局搜索能力差，容易陷入局部最優的缺陷，文中提出基于混合概率的新型小波變異量子粒子群算法(Mixed-probabilitybasedNewWaveletMutationQuantum-behavedParticleSwarmOptimization,M-WMQPSO)，也就是在采用混合概率分布進化方程替代標準QPSO進化方程的基礎上，再在粒子進化過程中加入新型小波變異，以一定的概率對粒子進行變異處理。通過變異，可以改變粒子群的前進方向，使粒子進入其他新的區域進行搜索，增加粒子種群的多樣性,避免粒子停留在一些局部極值點，從而增強粒子的全局搜索能力。M-WMQPSO算法的具體步驟如下：

步驟1：確定粒子種群規模M，維數D，并初始化粒子的位置；

步驟2：計算每個粒子的適應值，并更新粒子當前最優位置Pi(t)和全局最優位置G(t)；

步驟3：根據公式(10)更新每個粒子的位置，產生新的粒子種群；

步驟4：生成隨機數r∈(0,1)，若r

步驟5:判斷算法是否滿足最大迭代數，若沒有返回步驟2；

步驟6：輸出全局最優位置G，算法結束。

5 測試函數分析

文中分別使用Sphere函數、Rosenbrock函數、Griewank函數、Ackley函數、Schwefel函數、Ellipse函數這六個具有代表性的測試函數進行測試(見圖1)。仿真中，采用種群規模20，維數分別取10，最大迭代次數為1 000，標準QPSO中收縮-擴張因子α的值隨迭代次數從1.0到0.5線性減小。對于M-WMQPSO中，參數α固定為0.6，參數β隨迭代次數從0.9到0.4線性減小，形狀參數τ取值為5，突變概率q設為0.05，σ取值為100 000。

分別運用標準QPSO算法、M-QPSO算法、WMQPSO算法和M-WMQPSO算法進行測試，粒子位置的搜索區間與初始化區間見表1，具體測試結果見表2。

文中所選測試函數中，Sphere函數為一非線性且圖像對稱的單峰函數，主要用與檢驗算法的尋優精度；Rosenbrock函數、Schwefel函數和Ellipse函數主要用于檢驗算法的尋優能力；Griewank函數和Ackley函數都為多峰函數，具有大量的局部最優點，所以算法很容易陷入局部最優，所以一般用于檢驗算法抵抗局部最優能力[17]。

從上述測試函數運算結果和算法的尋優曲線可以看出，M-WMQPSO算法的識別結果明顯優于標準QPSO算法、M-QPSO算法和WMQPSO算法。特別Griewank函數和Ackley函數兩個多峰函數的測試結果明顯優于其他算法，這說明改進算法的跳出局部最優能力得到了很大提高。而其余測試函數的結果也表明，M-WMQPSO算法的尋優性能和收斂精度也是最好的，因此，M-WMQPSO算法的性能均較QPSO算法、M-QPSO算法和WMQPSO算法有所改進。

6 結束語

文中在標準QPSO算法的基礎上，首先對進化方程進行改進，引入高斯變量，使QPSO算法進化方程從基于單一概率分布改進為基于混合概率分布，改進后算法的尋優性能得到了提高。

表1 測試函數相關信息

表2 測試函數的測試結果

圖1 測試函數尋優曲線

針對算法容易陷入局部最優的問題，接下來利用小波變異代替收縮-擴張系數α得到變異公式，在進化過程中，根據一定的概率，對粒子進行變異，通過改變粒子群的前進方向，使粒子進入其他新的區域進行搜索，避免粒子停留在一些局部極值點，從而提高搜索進化進程中的全局搜索能力，增加粒子種群的多樣性，幫助粒子群中陷入局部最優的粒子跳出局部最優。

通過典型測試函數的仿真結果分析表明，M-WMQPSO算法的尋優性能和避免局部最優能力都得到了提高，因此基于混合概率分布和小波變異的改進方法是有效的。

M-WMQPSO算法的不足之處是，由于加入了小波變異處理，這使得算法的控制參數過多，如何減少控制參數可成為進一步改進該算法的一個目標。

[1]KennedyJ,EberhartRC.Particleswarmoptimization[C]//ProceedingsofIEEEinternationalconferenceonneuralnetworks.[s.l.]:IEEE,1995:1942-1948.

[2] 溫 濤，盛國軍，郭 權,等.基于改進粒子群算法的Web服務組合[J].計算機學報，2013,36(5):1031-1046.

[3] 溫 勇，王 美.基于粒子群算法的無線傳感網絡部署的研究[J].計算機技術與發展，2013,23(4):202-205.

[4] 田宏偉，解 福，倪俊敏.云計算環境下基于粒子群算法的資源分配策略[J].計算機技術與發展,2011,21(12):22-25.

[5] 潘麗姣,吳紅英.混沌逃逸粒子群優化算法在WSN覆蓋優化中的應用[J].重慶郵電大學學報:自然科學版,2014,26(2):177-181.

[6] 顧曉燕,孫力娟,郭劍,肖甫.一種有向傳感器網絡改進粒子群覆蓋增強算法[J].重慶郵電大學學報:自然科學版,2011,23(2):214-219.

[7] 梁正友，支成秀．基于離散粒子群優化算法的網格資源分配研究[J]．計算機工程與科學，2007, 29(10) 77-78.

[8]ClercM,KennedyJ.Theparticleswarm-explosion,stability,andconvergenceinamultidimensionalcomplexspace[J].IEEETransactionsonEvolutionaryComputation,2002,6(1):58-73.

[9] 孫 俊.量子行為粒子群優化算法研究[D].無錫：江南大學,2009.

[10]YangSY,WangM,JiaoLC.Aquantumparticleswarmoptimization[C]//ProcofIEEEcongressonevolutionarycomputation.Portland,OR,US:IEEEPress,2004:320-324.

[11]Schr?dingerE.Anadulatorytheoryofthemechanicsofatomsandmolecules[J].PhysRev,1926,28(6):1049-1070.

[12]ShiYH,EberhartRC.Amodifiedparticleswarmoptimizer[C]//ProceedingsoftheIEEEinternationalconferenceonevolutionarycomputation.Piscataway,NJ:IEEEPress,1998:69-73.

[13]ShiYH,EberhartRC.Fuzzyadaptiveparticleswarmoptimization[C]//Procofcongressonevolutionarycomputation.Seoul,Korea:IEEEServiceCenter,2001:101-106.

[14]LingSH,IuHHC,ChanKY,etal.Hybridparticleswarmoptimizationwithwaveletmutationanditsindustrialapplications[J].IEEETransactionsonSystems,ManandCybernetics,PartB:Cybernetics,2008,38(3):743-763.

[15] 高東慧,董平平,田雨波,等.一種改進的小波變異粒子群優化算法[J].計算機工程,2012,38(21):145-147.

[16] 羅光坤.Morlet小波變換理論與應用研究及軟件實現[D].南京：南京航空航天大學，2007.

[17] 丁 穎.量子粒子群算法的改進及其在認知無線電頻譜分配中的應用[D].南京：南京郵電大學，2013.

A New Particle Swarm Optimization Algorithm of Wavelet Mutation Quantum-behaved Based on Mixed-probability

HU Hao,CHANG Jun,GONG Wen-long,LIU Wen-bo

(Suzhou University of Science and Technology,Suzhou 215011，China)

Quantum-behaved Particle Swarm Optimization (QPSO) algorithm has defects that the capability of global optimization is not strong and is easy to fall into the local optimum.To solve this problem,an improved quantum-behaved particle swarm optimization is presented by introducing Gaussian distribution into the evolution equation,and the evolution equation of QPSO is substituted by mixed probability distribution evolution equation,and some particles were mutated in a definite probability by wavelet during evolution to increase the diversity of the particle population,avoiding the optimization process into local optimization,and improve the capability of global optimization.Finally,six typical test functions are employed to verify the improved method.The results show that the optimization capability and the ability to avoid local optimum of improved algorithm have been improved effectively.

quantum-behaved particle swarm optimization;mixed probability;wavelet;local optimization;global optimization

2015-04-07

2015-07-10

時間：2016-01-04

江蘇省自然科學基金項目(BK20141180)；江蘇省結構工程重點實驗室開放課題(ZD1405)

胡 皞(1989-)，男，碩士研究生，研究方向為橋梁健康監測、人工智能優化算法；常 軍，博士，碩士生導師,研究方向為橋梁健康監測、智能優化技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1505.030.html

TP301

A

1673-629X(2016)01-0078-04

10.3969/j.issn.1673-629X.2016.01.016