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

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

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

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

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

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

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

量子粒子群算法；混合概率；小波；局部最優(yōu)；全局最優(yōu)

0 引 言

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

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

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

1 QPSO算法原理

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

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

(1)

(2)

其中

(3)

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

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

2 基于混合概率的QPSO原理

從標(biāo)準(zhǔn)QPSO算法的粒子進(jìn)化方程可以看出，原來的進(jìn)化方程中使用單一的概率分布函數(shù)，現(xiàn)在考慮使用混合概率分布函數(shù)。一維的時(shí)候，QPSO算法的粒子進(jìn)化方程為：

(4)

式中，第二項(xiàng)是一個(gè)雙指數(shù)分布的隨機(jī)項(xiàng)。將該式表示成更一般的形式：

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

(5)

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

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

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

(6)

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

(7)

(8)

式中，u(t)服從區(qū)間(0,1)內(nèi)的均勻分布；Rn(t)服從標(biāo)準(zhǔn)高斯分布；參數(shù)α和β稱為收縮-擴(kuò)張系數(shù)。

這樣粒子的進(jìn)化方程便可以寫成:

(9)

而擴(kuò)展到N維搜索空間中，粒子的進(jìn)化方程為:

(10)

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

3 新型小波變異原理

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

文中將采用復(fù)Morlet小波[16]實(shí)部作為變異因子，復(fù)Morlet小波函數(shù)實(shí)部的時(shí)域表達(dá)式為：

(11)

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

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

(12)

定義尺度c的計(jì)算公式為：

(13)

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

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

(14)

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

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

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

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

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

步驟2：計(jì)算每個(gè)粒子的適應(yīng)值，并更新粒子當(dāng)前最優(yōu)位置Pi(t)和全局最優(yōu)位置G(t)；

步驟3：根據(jù)公式(10)更新每個(gè)粒子的位置，產(chǎn)生新的粒子種群；

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

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

步驟6：輸出全局最優(yōu)位置G，算法結(jié)束。

5 測試函數(shù)分析

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

分別運(yùn)用標(biāo)準(zhǔn)QPSO算法、M-QPSO算法、WMQPSO算法和M-WMQPSO算法進(jìn)行測試，粒子位置的搜索區(qū)間與初始化區(qū)間見表1，具體測試結(jié)果見表2。

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

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

6 結(jié)束語

文中在標(biāo)準(zhǔn)QPSO算法的基礎(chǔ)上，首先對進(jìn)化方程進(jìn)行改進(jìn)，引入高斯變量，使QPSO算法進(jìn)化方程從基于單一概率分布改進(jìn)為基于混合概率分布，改進(jìn)后算法的尋優(yōu)性能得到了提高。

表1 測試函數(shù)相關(guān)信息

表2 測試函數(shù)的測試結(jié)果

圖1 測試函數(shù)尋優(yōu)曲線

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

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

M-WMQPSO算法的不足之處是，由于加入了小波變異處理，這使得算法的控制參數(shù)過多，如何減少控制參數(shù)可成為進(jìn)一步改進(jìn)該算法的一個(gè)目標(biāo)。

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

[2] 溫 濤，盛國軍，郭 權(quán),等.基于改進(jìn)粒子群算法的Web服務(wù)組合[J].計(jì)算機(jī)學(xué)報(bào)，2013,36(5):1031-1046.

[3] 溫 勇，王 美.基于粒子群算法的無線傳感網(wǎng)絡(luò)部署的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013,23(4):202-205.

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

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

[6] 顧曉燕,孫力娟,郭劍,肖甫.一種有向傳感器網(wǎng)絡(luò)改進(jìn)粒子群覆蓋增強(qiáng)算法[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版,2011,23(2):214-219.

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

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

[9] 孫 俊.量子行為粒子群優(yōu)化算法研究[D].無錫：江南大學(xué),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ìn)的小波變異粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2012,38(21):145-147.

[16] 羅光坤.Morlet小波變換理論與應(yīng)用研究及軟件實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，2007.

[17] 丁 穎.量子粒子群算法的改進(jìn)及其在認(rèn)知無線電頻譜分配中的應(yīng)用[D].南京：南京郵電大學(xué)，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

時(shí)間：2016-01-04

江蘇省自然科學(xué)基金項(xiàng)目(BK20141180)；江蘇省結(jié)構(gòu)工程重點(diǎn)實(shí)驗(yàn)室開放課題(ZD1405)

胡 皞(1989-)，男，碩士研究生，研究方向?yàn)闃蛄航】当O(jiān)測、人工智能優(yōu)化算法；常 軍，博士，碩士生導(dǎo)師,研究方向?yàn)闃蛄航】当O(jiān)測、智能優(yōu)化技術(shù)。

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