基于區(qū)域均衡和壓縮因子的混合粒子群算法的研究

陳　欣,劉　朔

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023)

?

基于區(qū)域均衡和壓縮因子的混合粒子群算法的研究

陳欣,劉朔

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023)

摘要：針對(duì)傳統(tǒng)粒子群算法容易陷入局部最優(yōu)解的問題，提出一種在采用全局最優(yōu)和區(qū)域均衡最優(yōu)相結(jié)合來共同更新粒子速度的基礎(chǔ)上，融合壓縮因子的混合算法。將粒子的局部區(qū)域均衡的信息加入到速度更新公式，使得粒子的速度同時(shí)受到全局最優(yōu)和區(qū)域平衡最優(yōu)的作用，提高了粒子的尋優(yōu)性能，平衡粒子的全局尋優(yōu)能力和局部尋優(yōu)能力。通過選取幾個(gè)多峰值的測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，表明該算法粒子的尋優(yōu)性能有較大優(yōu)勢(shì)。

關(guān)鍵詞：混合粒子群算法;區(qū)域均衡;壓縮因子

1引言

在眾多群體智能算法中，粒子群算法的結(jié)構(gòu)簡單，易于實(shí)現(xiàn)，并有著非常廣泛的應(yīng)用。但是，粒子群算法和其他的智能算法一樣，也存在陷入局部最優(yōu)解的弱點(diǎn)。為了克服這些弱點(diǎn)，很多學(xué)者提出了不同的改進(jìn)方案。馬國慶等[1]提出了利用慣性權(quán)重線性遞減的策略。任圓圓[2]給出非線性的動(dòng)態(tài)慣性權(quán)重設(shè)置即自適應(yīng)權(quán)重的公式。Shi Y等[3]則從控制微粒的飛行速度入手，構(gòu)造了設(shè)置壓縮因子的改進(jìn)粒子群算法，都取得了一定的效果。以上這些算法，粒子速度的更新仍然極大取決于自身最優(yōu)解和全局最優(yōu)解，容易出現(xiàn)早熟的現(xiàn)象。本文提出一種混合粒子群算法，在微粒的速度更新公式中引入?yún)^(qū)域均衡最優(yōu)解和飛行速度控制的壓縮因子，使得粒子速度的更新更為合理，使混合粒子群算法的搜索能力和收斂精確度進(jìn)一步增強(qiáng)。

2標(biāo)準(zhǔn)的粒子群算法

(1)

而第i個(gè)粒子的速度和位置更新見式(2)和式(3)：

Vi(t+1)=Vi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pg(t)-xi(t)).

(2)

xi(t+1)=xi(t)+Vi(t+1).

(3)

其中c1,c2是非負(fù)常數(shù)，r1,r2是相互獨(dú)立的隨機(jī)數(shù)，Vi∈[-vmax,vmax]，其中vmax由用戶根據(jù)實(shí)際問題具體設(shè)定。迭代的終止條件一般選定為最大迭代次數(shù)T。

3引入?yún)^(qū)域均衡最優(yōu)解和壓縮因子的混合粒子群算法

3.1融合區(qū)域均衡的最優(yōu)解

傳統(tǒng)粒子群算法中，種群中的每一個(gè)粒子的速度更新都是依賴于該粒子本身的歷史最優(yōu)解和整個(gè)種群的最優(yōu)解。在傳統(tǒng)粒子群算法的前期搜尋階段，很有可能會(huì)出現(xiàn)粒子搜尋過快，與最優(yōu)解擦肩而過的情況，這樣接下來的搜尋就很容易陷入局部最優(yōu)的陷阱。陳群林等[5]為了提高算法搜尋的準(zhǔn)確度，針對(duì)粒子群算法局部搜尋能力引入了粒子加速和變異的機(jī)制。張水平等[4]就提出一種用每個(gè)粒子的鄰居的當(dāng)前最優(yōu)解代替全局最優(yōu)解來平衡局部搜索能力的方案，但是這種做法仍然具有一定的局限性，特別是每個(gè)粒子之間的距離的計(jì)算和存儲(chǔ)將會(huì)使得算法的運(yùn)算時(shí)間和存儲(chǔ)空間的花銷大大增加。本文把該粒子作為一個(gè)局部區(qū)域的中心，設(shè)定一個(gè)圓形的鄰域，以該鄰域內(nèi)部所有粒子的當(dāng)前最優(yōu)位置的幾何中心Pn作為該區(qū)域內(nèi)的全局最優(yōu)位置，這樣，每個(gè)粒子周圍的局部信息將得到更加高效和準(zhǔn)確的傳遞。即使在最極端的情況下，可能出現(xiàn)在所給鄰域內(nèi)并沒有出現(xiàn)其他的粒子，這樣鄰域的范圍就也應(yīng)該做出相應(yīng)的擴(kuò)大調(diào)整。鄰域擴(kuò)大過程如下：

r=k;

search=1;

while count==0 or search!=3;

r=1.5*r;

search=search+1.

如果三次調(diào)整后，周圍仍然沒有其余粒子出現(xiàn)，恰好說明該粒子周圍局部信息不足，無需平衡，此時(shí)直接應(yīng)用原始的速度更新公式即可。綜合以上的討論，本文提出一個(gè)基于局部范圍內(nèi)區(qū)最優(yōu)解的速度更新公式為：

Vi(t+1)=Vi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pn(t)-xi(t)).

以往的研究表明，傳統(tǒng)的全局PSO算法收斂速度快，但容易陷入局部最優(yōu)的陷阱[6]。而結(jié)合區(qū)域均衡最優(yōu)解的搜索算法可以搜索到相對(duì)更優(yōu)更精確的解，但是搜索速度會(huì)更慢一些。因此，本文采用一種采用全局最優(yōu)和區(qū)域均衡最優(yōu)相結(jié)合來共同更新粒子速度的混合算法，公式如下：

Hi(t+1)=u1Mi(t+1)+u2Ni(t+1).

其中：

Mi(t+1)=Vi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pn(t)-xi(t))是針對(duì)局部均衡尋優(yōu)。

Ni(t+1)=Vi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pg(t)-xi(t))是針對(duì)全局均衡尋優(yōu)。

并且u1=t/T,u2=1-u1的設(shè)置可以保證算法在兼顧了局部尋優(yōu)和全局尋優(yōu)的情況下，前期粒子的速度不會(huì)太快以至于錯(cuò)過最優(yōu)解，在算法后期也會(huì)更具有精確性。

3.2壓縮因子

在速度更新的公式中，c1,c2這兩個(gè)非負(fù)常數(shù)的值決定了微粒本身的經(jīng)驗(yàn)和其他微粒的經(jīng)驗(yàn)信息對(duì)運(yùn)動(dòng)軌跡的影響，反映了微粒之間的信息交流[7]。設(shè)置c1較大，會(huì)使微粒更多地在局部徘徊，而設(shè)置c2較大，又會(huì)使微粒過早收斂，為了達(dá)到全局探測和局部開采的兩者間的平衡，Shi Y等[3]提出了設(shè)置收縮因子的策略，速度更新公式如下：

Vi(t+1)=φ{(diào)Vi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pg(t)-xi(t))}.

其中

文獻(xiàn)[3]提出的相比文獻(xiàn)[1],[2]提出的針對(duì)權(quán)重的優(yōu)化，設(shè)置壓縮因子比權(quán)重系數(shù)，更能有效地控制約束微粒的飛行速度，同時(shí)增強(qiáng)了算法的局部搜索能力。本文對(duì)壓縮因子的設(shè)置做了一定的改進(jìn)，在控制了微粒飛行的速度的情況下，完整地保留對(duì)微粒間個(gè)體最佳適應(yīng)值和全局最佳適應(yīng)值信息的傳遞，更新后的速度更新公式如下：

Vi(t+1)=φVi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pg(t)-xi(t)).

其中

3.3區(qū)域均衡最優(yōu)解和壓縮因子的混合

本文在引入?yún)^(qū)域均衡最優(yōu)解和設(shè)定壓縮因子這兩個(gè)方面，改進(jìn)了粒子的更新公式和位置更新公式，提出了一種混合粒子群算法。新的速度和位置更新公式如下：

Mi(t+1)=φVi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pn(t)-xi(t)).

Ni(t+1)=φVi(t)+c1r1(Pi(t)-xi(t))+

c2r2(Pg(t)-xi(t)).

Hi(t+1)=u1Mi(t+1)+u2Ni(t+1).

Xi(t+1)=Xi(t)+Hi(t+1).

4仿真實(shí)驗(yàn)

為了測試本文算法的實(shí)際性能效果，將其與文獻(xiàn)[1]提出的慣性權(quán)重線性遞減算法與文獻(xiàn)[2]提出的自適應(yīng)權(quán)重算法經(jīng)行實(shí)驗(yàn)比較，采用三個(gè)多峰值測試函數(shù)進(jìn)行測試比較每個(gè)函數(shù)的參數(shù)設(shè)置如表1,表2,表3所示，算法測試結(jié)果如表4,表5,表6所示。

表1Ackley函數(shù)的初始參數(shù)設(shè)置

種群C1C2初始區(qū)間目標(biāo)值迭代數(shù)401.51.5[-32,32]0100

表2Rastrigrin函數(shù)的初始參數(shù)設(shè)置

種群C1C2初始區(qū)間目標(biāo)值迭代數(shù)401.51.5[-5.12,5.12]0100

表3Schaffer函數(shù)的初始參數(shù)設(shè)置

種群C1C2初始區(qū)間目標(biāo)值迭代數(shù)401.51.5[-10,10]0100

三個(gè)多峰測試函數(shù)[8]如下。

Rastrigrin函數(shù)：

Schaffer函數(shù):

表4對(duì)于Ackley測試函數(shù)的不同算法運(yùn)行結(jié)果

項(xiàng)目慣性權(quán)重遞減的PSO算法自適應(yīng)權(quán)重調(diào)整的PSO算法本文算法算法運(yùn)行次數(shù)303030算法平均運(yùn)行時(shí)間/s0.07600.07860.2323最佳平均適應(yīng)度/10-6-0.525-0.539-0.255

表5對(duì)于Rastrigrin測試函數(shù)的不同算法運(yùn)行結(jié)果

表6對(duì)于Schaffer測試函數(shù)的不同算法運(yùn)行結(jié)果

項(xiàng)目慣性權(quán)重遞減的PSO算法自適應(yīng)權(quán)重調(diào)整的PSO算法本文算法算法運(yùn)行次數(shù)303030算法平均運(yùn)行時(shí)間/s0.06920.06670.2011最佳平均適應(yīng)度/10-6-0.423-0.512-0.105

本文選取的三個(gè)測試函數(shù)都是經(jīng)典的多峰值測試函數(shù)，既可以對(duì)算法的準(zhǔn)確度進(jìn)行測試，也可以對(duì)算法的尋優(yōu)精度進(jìn)行評(píng)價(jià)。從圖1，圖2，圖3可以看出，本文算法的收斂速度和尋優(yōu)精度都是優(yōu)于文獻(xiàn)[1,2]提出的針對(duì)權(quán)重調(diào)整的算法。而且本算法的魯棒性較好，不容易掉入局部最優(yōu)的陷阱。

圖1　 Ackley函數(shù)測試圖

圖2　Rastrigrin函數(shù)測試圖

圖3　Schaffer函數(shù)測試圖

5結(jié)束語

針對(duì)傳統(tǒng)粒子群算法容易陷入局部最優(yōu)的問題，提出一種混合粒子群算法，在微粒的速度更新公式中引入?yún)^(qū)域均衡最優(yōu)解和飛行速度控制的壓縮因子，將全局最優(yōu)解和區(qū)域平衡最優(yōu)解的影響因素同時(shí)用于更新粒子的速度。實(shí)驗(yàn)表明，本文算法在優(yōu)化能力和性能上都有了很大的提高,但是算法的運(yùn)行速度和穩(wěn)定性還有待于進(jìn)一步提高。

參考文獻(xiàn)：

[1]馬國慶，李瑞峰，劉麗.學(xué)習(xí)因子和時(shí)間因子隨權(quán)重調(diào)整的粒子群算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31(11)：3291-3294.

[2]任圓圓，劉培玉，薛素芝.一種新的自適應(yīng)動(dòng)態(tài)文化粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30(11)：3240-3243.

[3]Shi Y，Eberhart R C.Empirical Study of Particle Swarm Optimization[C]//Proc of Congress on Evolutionary Computation.1999.

[4]張水平，仲偉彪.改進(jìn)學(xué)習(xí)因子和約束因子的混合粒子群算法[J].計(jì)算機(jī)應(yīng)用研究, 2015,32(12)：3626-3628.

[5]陳群林,高岳林,郭祥.一種帶有加速策略和變異策略的粒子群算法[J].蘭州文理學(xué)院學(xué)報(bào)(自然科學(xué)版),2015,29(6)：41-47.

[6]孫振龍,李曉曄,王穎.一種改進(jìn)的簡化粒子群優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2015,42(11A)：86-88.

[7]馮浩,李現(xiàn)偉.一種改進(jìn)的粒子群優(yōu)化算法慣性權(quán)值遞減策略[J].蚌埠學(xué)院學(xué)報(bào),2015,4(6)：21-24.

[8]宋錦,高浩.基于雙重更新策略的粒子群算法[J].南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,35(6)：84-88.

Hybrid particle swarm optimization algorithm of regional equilibrium and compression factor

CHENXin,LIUShuo

(School of Mathematics and Computer Science, Wuhan Polytechnic University, Wuhan 430023,China)

Abstract：In order to avoid traditional PSO algorithm converging too fast and easily falling into local optimum value, the PSO algorithm is proposed with regional equilibrium and global optimal value, adding the regional equilibrium optimum value into the updating formula of particle speed, and improving the search ability of the particle.Compared three classic test function, the algorithm can greatly improve the search ability of the particle.

Key words：hybrid particle swarm optimization; regional equilibrium; compression factor

收稿日期:2016-03-04.修回日期:2016-03-31.

作者簡介:陳欣(1978-),男,講師,E-mail:2924892402@qq.com.

文章編號(hào)：2095-7386(2016)02-0083-04

DOI:10.3969/j.issn.2095-7386.2016.02.015

中圖分類號(hào)：TP 301.6

文獻(xiàn)標(biāo)識(shí)碼：A