雙心擾動量子粒子群優(yōu)化算法研究

王安龍，何建華，陳 松，劉懷遠(yuǎn)

(西北工業(yè)大學(xué)電子信息學(xué)院，西安 710000)

1 概述

標(biāo)準(zhǔn)粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法無法以概率1收斂于全局最優(yōu)解[1-2]，容易陷入局部最優(yōu)。受微觀世界概率隨機(jī)性的啟發(fā)，Sun J等人[3]于2004年在標(biāo)準(zhǔn)PSO的基礎(chǔ)上，提出了量子粒子群優(yōu)化算法(Quantum PSO,QPSO)。QPSO打破了標(biāo)準(zhǔn)PSO以軌道來描述粒子運(yùn)動的模式，采用波函數(shù)來描述粒子的狀態(tài)，增加了粒子在搜索空間內(nèi)的概率隨機(jī)性。隨后，研究人員[4-9]對QPSO進(jìn)行了改進(jìn)，將遺傳算法中的變異機(jī)制引入到QPSO中，實(shí)驗(yàn)證明，這是一種非常有效的方式。

針對QPSO的變異位置主要有：勢能中心，重心和全局最好位置。粒子的勢能中心能夠吸引粒子在其鄰域內(nèi)探索新知識，對勢能中心的變異能夠產(chǎn)生新的個(gè)體結(jié)構(gòu)[10-11]；粒子群重心代表了粒子群的主流思想[4]，對重心變異能夠相對增加部分粒子的創(chuàng)造能力。為充分挖掘變異機(jī)制對算法的優(yōu)化能力，本文提出了在2個(gè)位置協(xié)同變異的量子粒子群優(yōu)化算法(BCD-QPSO)，進(jìn)化前期以較小概率對勢能中心和重心變異，發(fā)揮QPSO的全局搜索能力；進(jìn)化后期以較大概率對勢能中心和重心變異，保證粒子群的開拓能力。

2 標(biāo)準(zhǔn)QPSO算法

與標(biāo)準(zhǔn)PSO不同，在量子空間中，粒子的動量和位置不能同時(shí)具有確定的值，運(yùn)動軌道不確定，在空間中的運(yùn)動具有極大的隨機(jī)性，這種隨機(jī)性保證了QPSO的全局搜索能力。QPSO位置更新方程[4]為：

其中，xi(t)為第i個(gè)粒子的位置；Pi(t)和Pgb(t)為粒子i的歷史最優(yōu)位置和粒子群的全局最優(yōu)位置；pi(t)和G(t)為粒子i的勢能中心和粒子群的重心；β為收縮擴(kuò)張系數(shù)。

3 雙心擾動量子粒子群優(yōu)化算法

3.1 變異算子

變異是粒子群多樣性的產(chǎn)生機(jī)制，常用的變異方式有隨機(jī)變異、高斯變異、柯西變異、混沌變異等[4]。高斯分布在變異點(diǎn)鄰域產(chǎn)生小擾動的概率大而大擾動的概率小，而柯西分布正好相反，故選擇柯西變異更能跳出局部最優(yōu)。

柯西分布的密度函數(shù)為：

其中，α為尺度參數(shù)[10]，當(dāng)α值較小時(shí)，概率曲線較凸，小尺度變異概率相對較大；當(dāng)α值較大時(shí)，概率曲線較扁平，大尺度變異概率相對較大。本文采用文獻(xiàn)[7]中的取值，即α=2.0。

3.2 變異概率自適應(yīng)調(diào)整

到目前為止，在智能算法中采取的變異多數(shù)都是分階段變異，迭代次數(shù)以離散序列增加決定了變異量自適應(yīng)調(diào)整的非線性。設(shè)最大迭代次數(shù)為G，階段數(shù)為S，則進(jìn)化階段可定義為G/S，特別地，當(dāng)G=S時(shí)，分階段變異退化為普通的自適應(yīng)變異。

針對QPSO，有研究者[5-7]認(rèn)為，前期較大的變異概率有利于產(chǎn)生新的個(gè)體結(jié)構(gòu)，后期較小的變異概率有利于局部搜索。這種處理方式在一定程度上能提高算法的求解能力，但在進(jìn)化后期對種群的引導(dǎo)力不足，使得粒子后期的創(chuàng)造能力有限。而本文采用的勢能中心和重心協(xié)同變異，卻能更保證進(jìn)化后期粒子群的創(chuàng)造能力，對勢能中心的變異，有利于提升單個(gè)粒子的創(chuàng)造力，而對重心的變異有利于提升整個(gè)粒子群的創(chuàng)造力。下面引入等差數(shù)列來描述變異概率逐步減小和變異概率逐步增大2種截然相反的變異策略。

變異概率約束條件：

其中，Pm(tk)表示第tk個(gè)進(jìn)化階段的變異概率。

等差數(shù)列法[12]：

3.3 BCD-QPSO步驟

BCD-QPSO步驟如下：

步驟1參數(shù)設(shè)置。設(shè)置最大迭代次數(shù)Gmax，搜索空間維數(shù)D，粒子群個(gè)體數(shù)目N。

步驟2種群初始化，利用一維Logistic混沌映射隨機(jī)產(chǎn)生N個(gè)粒子。

步驟3計(jì)算每個(gè)粒子在解空間中適應(yīng)度值，計(jì)算各個(gè)粒子自身最優(yōu)適應(yīng)度值pbest和粒子群的全局最優(yōu)位置gbest。

步驟4進(jìn)入主循環(huán)，確定進(jìn)化階段數(shù)，根據(jù)式(6)～式(9)計(jì)算自適應(yīng)變異概率，并根據(jù)式(4)計(jì)算粒子群的重心，并對每個(gè)粒子按照式(3)構(gòu)造一個(gè)勢能中心。

步驟5根據(jù)自適應(yīng)變異概率，對粒子群的重心和每個(gè)粒子的勢能中心按照式(5)進(jìn)行自適應(yīng)柯西變異。

步驟6按照式(1)更新粒子群中每個(gè)粒子的位置。

步驟7更新每個(gè)粒子歷史最優(yōu)位置和粒子群的最優(yōu)位置。

步驟8判斷是否滿足循環(huán)結(jié)束條件，如果不滿足，則轉(zhuǎn)到步驟4；如果滿足循環(huán)結(jié)束條件，則輸出最優(yōu)解。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 測試函數(shù)描述

本文采用的測試函數(shù)：Sphere，Rotated，Rastrigin，Griewank，下面對4個(gè)函數(shù)特點(diǎn)作簡要闡述。

(1)Sphere函數(shù)

全局最優(yōu)位置：f(x)=0,x(i)=0,1≤i≤ n ；函數(shù)曲面單峰、連續(xù)、對稱。

(2)Rotated函數(shù)

全局最優(yōu)位置：f(x)=0,x(i)=0,1≤i≤ n ；函數(shù)曲面單峰、連續(xù)、對稱。

(3)Rastrigin函數(shù)

全局最優(yōu)位置：f(x)=0,x(i)=0,1≤i≤ n ；函數(shù)曲面高度多峰、連續(xù)。

(4)Griewank函數(shù)

全局最優(yōu)位置：f(x)=0,x(i)=0,1≤i≤ n ；函數(shù)曲面高度多峰、連續(xù)。

4.2 實(shí)驗(yàn)設(shè)計(jì)

本文以求4個(gè)函數(shù)的最小值為例，進(jìn)行仿真實(shí)驗(yàn)，測試平臺為Matlab R2011a，機(jī)器處理器為i3(2.13 GHz,3 MB L3 cache)，分別考慮6維和30維的情況，最大迭代次數(shù)設(shè)為1000，粒子數(shù)20，進(jìn)化階段為10，每種情況運(yùn)行20次。實(shí)驗(yàn)中，分別測試了基于勢能中心變異的量子粒子群優(yōu)化算法(MPIL-QPSO)、基于重心變異的量子粒子群優(yōu)化算法(MG-QPSO)、基于最優(yōu)位置變異的量子粒子群優(yōu)化算法(MGB-QPSO)和本文提出的雙心擾動的量子粒子群優(yōu)化算法(BCD-QPSO)。為更全面評價(jià)算法性能，采用2種截然相反的變異概率調(diào)整策略。策略1：取η=2.0，如圖1細(xì)劃線所示；策略2：取η=0.01，如圖1粗劃線所示。

圖1 變異概率調(diào)整

將數(shù)域(+∞,0]劃分成n個(gè)子區(qū)間，對每個(gè)子區(qū)間按其相對重要性進(jìn)行評分，并進(jìn)行歸一化處理，得到各子區(qū)間的區(qū)間權(quán)重w。本文設(shè)n=8，區(qū)間評分依次為1,2,3,4,5,6,7,8，歸一化處理結(jié)果如表1所示。

下面定義一個(gè)新的測試指標(biāo)：

定義 在N次獨(dú)立重復(fù)實(shí)驗(yàn)中，落在第i個(gè)子區(qū)間的最優(yōu)值數(shù)為ri，第i個(gè)子區(qū)間的區(qū)間權(quán)重為wi，則分布積分為：

分布積分越高，代表實(shí)驗(yàn)結(jié)果在高精度區(qū)間上的分布越多，算法性能越好，反之，算法性能越差。分布積分較好地反映了算法對目標(biāo)函數(shù)的優(yōu)化效果，區(qū)間劃分越細(xì)，評價(jià)結(jié)果越全面。

表1 區(qū)間權(quán)重

4種函數(shù)測試結(jié)果如表2～表5所示，其中，粗體數(shù)字表示不同測試條件下目標(biāo)函數(shù)的最優(yōu)值。從表2、表3可以得出，在策略2下，針對單峰優(yōu)化，3種單位置變異方式的最高分布積分為3.006,2.948,3.114,2.584，平均值為2.913；而BCD-QPSO的分布積分為4.216,4.020,4.049,3.612，平均值為：3.974，相對提高了36.42%。同理，從表4、表5可以得出，多峰優(yōu)化時(shí)BCD-QPSO的優(yōu)化效果比其他3種算法相對提高了32.84%。

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

表3 Rotated函數(shù)測試結(jié)果

表4 Rastrigin函數(shù)測試結(jié)果

表5 Griewank函數(shù)測試結(jié)果

圖2和圖3對比了不同策略下4種算法對不同測試函數(shù)的分布積分(量綱為1)，垂直柱狀圖中每組圖形，從左到右依次表示MLIP-QPSO(字母A)、MG-QPSO(字母B)、MGB-QPSO(字母C)和BCD-QPSO(字母D)對相應(yīng)測試函數(shù)優(yōu)化結(jié)果的分布積分。

圖2 策略1下的分布積分對比

圖3 策略2下的分布積分對比

為了更加直觀地反映BCD-QPSO的優(yōu)化效率，本文繪出MLIP-QPSO、MG-QPSO和BCD-QPSO在求解Rastrigin函數(shù)時(shí)，前500代的算法收斂曲線(粒子維數(shù)30)。

從表2～表5可以得出：采取策略1時(shí)，MGB-QPSO優(yōu)化效果不如其他3種算法；采取策略2時(shí)，算法后期震蕩嚴(yán)重，局部搜索能力弱，優(yōu)化效果不如標(biāo)準(zhǔn)QPSO。所以，圖4和圖5中沒有繪出MGB-QPSO的收斂曲線。

圖4 策略1各算法收斂曲線

圖5 策略2各算法收斂曲線

從以上4個(gè)函數(shù)的實(shí)驗(yàn)結(jié)果可以得出以下結(jié)論：

(1)不同的變異方式在不同的變異位置產(chǎn)生的效果不同。對全局最好位置和勢能中心而言，采用變異概率自適應(yīng)減小的變異策略，一定程度上抑制了早熟收斂，極大地提高了尋優(yōu)能力，反之，則破壞了QPSO進(jìn)化后期的局部搜索能力；對重心而言，采用變異概率自適應(yīng)增大的變異策略，有利于進(jìn)化后期粒子多樣性的維護(hù)。

(2)采用雙心擾動的變異方式產(chǎn)生蝴蝶效應(yīng)，對單峰和多峰函數(shù)的優(yōu)化能力都強(qiáng)于只采用單個(gè)位置變異的策略。

(3)無論是采取變異概率逐漸增大的變異概率調(diào)整策略，還是采取變異概率逐漸減小的變異概率調(diào)整策略，雙心擾動變異產(chǎn)生的優(yōu)化效果都好于單位置變異產(chǎn)生的優(yōu)化效果，且適當(dāng)?shù)淖儺惛怕收{(diào)整策略能大大提高算法的優(yōu)化能力。

(4)BCD-QPSO的尋優(yōu)能力和尋優(yōu)效率不隨變量維數(shù)的增加而明顯減弱，在工程實(shí)踐中有很好的應(yīng)用前景。

5 結(jié)束語

本文提出了一種雙心擾動量子粒子群優(yōu)化算法(BCDQPSO)，通過與只采用單位置變異的量子粒子群優(yōu)化算法仿真對比，證明了該算法具有收斂速度快、求解精度高的特點(diǎn)，同時(shí)適合于低維優(yōu)化和高維優(yōu)化，具有普適性。如何更好地挖掘組合變異機(jī)制的尋優(yōu)潛力，進(jìn)一步提高求解精度與效率，是今后的研究內(nèi)容。

[1]van Den,Bergh F,Engelbrecht A P.A New Locally Convergent Particle Swarm Optimizer[C]//Proc. of IEEE Conference on Systems,Man and Cybernetics.[S.1.]:IEEE Press,2002:94-99.

[2]Clere M,Kennedy J.Particle Swarm Optimization Explosion,Stability,and Convergence in a Multidimensional Complex Space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[3]Sun Jun,Feng Bin,Xu Wenbo.Particle Swarm Optimization with Particles Having Quantum Behavior[C]//Proc.of Conference on Evolutionary Computation.Piscataway,USA:[s.n.],2004:325-331.

[4]劉 靜.粒子群優(yōu)化算法研究及其在優(yōu)化理論中的應(yīng)用[D].無錫:江南大學(xué),2007.

[5]向 毅,鐘育彬.自適應(yīng)階段變異量子粒子群優(yōu)化算法研究[J].計(jì)算機(jī)應(yīng)用研究,2012,29(6):2035-2039.

[6]劉俊芳,高岳林.帶自適應(yīng)變異的量子粒子群優(yōu)化算[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(3):41-43.

[7]李紅嬋,朱顥東.并行自適應(yīng)量子粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2011,37(5):221-223.

[8]鐘文亮,王惠森,張 軍,等.帶啟發(fā)性變異的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(31):3402-3405.

[9]李 引,毛 力,須文波.量子粒子群優(yōu)化改進(jìn)的模糊C均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(35):151-155.

[10]孫 俊.量子行為粒子群優(yōu)化算法研究[D].無錫:江南大學(xué),2009.

[11]施 展.多目標(biāo)量子行為粒子群優(yōu)化算法研究[D].南京:南京理工大學(xué),2011.

[12]徐澤水.直覺模糊信息集成理論及應(yīng)用[M].北京:科學(xué)出版社,2008:187-197.