一種多樣性反饋高斯粒子群算法

黃明，張春蕾,武耀旭,郝倩

(大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028)

一種多樣性反饋高斯粒子群算法

黃明，張春蕾,武耀旭,郝倩

(大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028)

針對(duì)粒子群算法在算法迭代后期因多樣性減少而容易陷入局部最優(yōu)的缺陷,引入種群多樣性反饋(群活性反饋)和高斯正態(tài)慣性權(quán)重變異算子對(duì)粒子群算法進(jìn)行改進(jìn)，當(dāng)粒子群的多樣性減少時(shí)，通過改變粒子的慣性權(quán)重調(diào)節(jié)粒子速度和位置，從而跳出局部最優(yōu)解.與標(biāo)準(zhǔn)粒子群算法對(duì)比仿真結(jié)果表明：多樣性反饋高斯粒子群算法在全局搜索能力和尋優(yōu)性能上有很大提高,多樣性提高近一倍，迭代時(shí)間縮短近3/4.

粒子群算法；慣性權(quán)重；多樣性反饋；高斯算子

0 引言

近年來，群體智能優(yōu)化算法在現(xiàn)代工業(yè)中的應(yīng)用越來越廣泛，為了進(jìn)一步提高智能算法的性能，人們對(duì)其進(jìn)行了大量的研究，群體智能優(yōu)化算法也由最原始的遺傳算法、蟻群算法和粒子群算法等發(fā)展為現(xiàn)在模擬退火遺傳算法、改進(jìn)蟻群算法和改進(jìn)粒子群算法等.同其他智能優(yōu)化算法相比，粒子群算法因參數(shù)少、步驟簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)使其在工業(yè)問題應(yīng)用更廣泛，當(dāng)然，粒子群算法迭代后期種群的群活性減少而使其容易陷入局部最優(yōu)解.

針對(duì)粒子群算法的缺陷，許多國內(nèi)外學(xué)者對(duì)其進(jìn)行了改進(jìn)，主要可以分為兩類：一種是針對(duì)粒子群算法的迭代后期缺陷和迭代過程中種群多樣性減少采用的慣性權(quán)重w改進(jìn)[1- 8]；另一種則是混合算法[9- 10].但是大多數(shù)的改進(jìn)仍然存在問題：①不能夠很好的對(duì)粒子群多樣性進(jìn)行檢測(cè)控制，而直接使用慣性權(quán)重算子改進(jìn)慣性權(quán)重，有一些慣性權(quán)重算法的計(jì)算公式復(fù)雜難理解；②粒子群混合算法由于混合多個(gè)算法的優(yōu)點(diǎn)，彌補(bǔ)了各個(gè)算法的不足,故在問題的解決上優(yōu)于單純的慣性權(quán)重改進(jìn).然而，混合算法的復(fù)雜度和計(jì)算量大大提高，在應(yīng)用中難實(shí)現(xiàn)，并不能滿足現(xiàn)在工業(yè)中對(duì)效率的需求.

因此，本文提出了基于多樣性反饋(群活性反饋)的高斯粒子群算法(SAF-GPSO)，該算法不僅繼承了粒子群算法的優(yōu)點(diǎn)，而且改進(jìn)算子簡(jiǎn)單易實(shí)現(xiàn)，與原始粒子群算法相比性能大大的提高.

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

粒子群優(yōu)化算法(particleswarmoptimization，簡(jiǎn)稱PSO)是一種進(jìn)化計(jì)算技術(shù)，源于對(duì)鳥群覓食行為的研究，由Eberhart博士和Kennedy博士在1995年提出的[11].粒子的各個(gè)屬性都是由各個(gè)維數(shù)的分量進(jìn)行表示，每個(gè)粒子的位置按如下公式進(jìn)行變化：

為了提高基本粒子群算法的收斂性和全局搜索能力(避免陷入局部最優(yōu)解)，Y.Shi和R.C.Eberhan提出了慣性權(quán)重的概念[1],將粒子群算法的速度迭代式(1)進(jìn)行改進(jìn)，加入固定慣性權(quán)重w(一般取0.3～0.8)，改進(jìn)后的公式如下：

(3)

式中：i表示第粒子；d表示維數(shù)；P表示粒子個(gè)體極值；g表示粒子全局極值；t表示粒子的迭代次數(shù).

2 改進(jìn)粒子群算法

2.1 改進(jìn)粒子群算法步驟

本文將種群的多樣性作為群活性[8]，多樣性反饋又稱為群活性反饋(swarmactivityfeedback-SAF)是指通過種群多樣性算子對(duì)群活性進(jìn)行量化分析，當(dāng)群活性減少時(shí)，采用高斯慣性權(quán)重改進(jìn)操作產(chǎn)生新的慣性權(quán)重.算法步驟描述如下：

步驟1：初始化粒子群.粒子群的大小N，搜索空間維數(shù)D，最大迭代次數(shù)t，尋優(yōu)目標(biāo)函數(shù)，慣性權(quán)重w，社會(huì)參數(shù)，c1,c1及r1，r2；

步驟2：計(jì)算當(dāng)前代粒子位置的適應(yīng)度函數(shù)值，比較更新局部最優(yōu)和全局最優(yōu)；

步驟3：判斷當(dāng)前迭代次數(shù)是否達(dá)到最大或者適應(yīng)度函數(shù)為0，若滿足則直接跳到步驟7，否則執(zhí)行步驟4；

步驟4：將當(dāng)前粒子的位置和速度帶入式(2)、(3)計(jì)算下一代粒子的速度和位置，并將迭代次數(shù)加1；

步驟5：計(jì)算當(dāng)前粒子的平均粒子距(種群多樣性計(jì)算)；

步驟6：判斷群活性是否降低，若降低則進(jìn)行高斯慣性權(quán)重改進(jìn)操作產(chǎn)生新的慣性權(quán)重，然后使用新得到的慣性權(quán)重，若沒有降低則執(zhí)行步驟2；

步驟7：輸出顯示尋到的最優(yōu)位置(也可以輸出迭代次數(shù)等)；

粒子群算法在一定的范圍區(qū)間內(nèi)尋找函數(shù)的最優(yōu)(最大值或最小值等)，若想找到全局最優(yōu)，則希望所有粒子分布在這個(gè)搜索區(qū)間.由于鎖定慣性權(quán)重時(shí)，粒子后期迭代速度主要由粒子的歷史和全局最優(yōu)位置引導(dǎo)，不能有效的跳出局部范圍.如當(dāng)?shù)絫次時(shí)，粒子群算法中的每個(gè)粒子由原來在每個(gè)粒子位置為中心10為半徑的鄰域，縮減到了2為半徑的鄰域，而不能跳出10以外的鄰域，這樣種群群活性減少而陷入局部最優(yōu).通過高斯變異調(diào)節(jié)到適當(dāng)?shù)膽T性權(quán)重，可以使粒子跳出局部，有效的分布到整個(gè)區(qū)間.實(shí)驗(yàn)分析，本文的慣性算子比于其他的改進(jìn)慣性算子簡(jiǎn)單且產(chǎn)生的慣性權(quán)重分布[0.2,0.8]內(nèi)，能夠很好的涵蓋整個(gè)區(qū)間.

2.2 多樣性反饋機(jī)制

本文采用所有粒子的平均粒子距變化直接反應(yīng)粒子的群活性，根據(jù)二維空間距離的求解推廣到D維，得到第t+1次迭代后，粒子的平均粒子距公式為：

(4)

所有粒子的平均變化率公式為：

(5)

由式(2)、(5)化簡(jiǎn)后得到所有粒子的平均變化率公式為：

(6)

由式(6)可以看出，使用迭代粒子的平均粒子距表示粒子群活性可以通過調(diào)節(jié)粒子的速度來實(shí)現(xiàn)，對(duì)于粒子群速度的調(diào)節(jié)方法有很多，有些直接對(duì)速度初始化，有些則通過慣性權(quán)重對(duì)速度進(jìn)行改進(jìn)，由于通過對(duì)速度初始化操作的效果不夠好，本文采用慣性權(quán)重調(diào)節(jié)的方式對(duì)速度進(jìn)行改進(jìn)，在2.3節(jié)會(huì)介紹.

2.3 改進(jìn)慣性權(quán)重算子

通過學(xué)者們對(duì)于固定慣性權(quán)重w的取值(一般在[0,1.0])和非固定取值進(jìn)行了大量的研究總結(jié)出：采用固定取值時(shí)，w的值在[0.3,0.7]之間時(shí)，算法的收斂速度較快，當(dāng)w時(shí)，算法容易陷入局部最優(yōu)[12].w采用非固定值時(shí)，通過遞減或自適應(yīng)調(diào)節(jié)算法進(jìn)行計(jì)算，使其在0～1.0之間變換，粒子群算法在收斂速度和全局搜索能力上取得不錯(cuò)的結(jié)果.本算法采用高斯分布算子，相對(duì)于其他慣性權(quán)重算子，本算子優(yōu)點(diǎn)如下：①算子更為簡(jiǎn)單，直接使w服從正態(tài)分布模型，一定有效范圍內(nèi)變化，便于算法收斂;②實(shí)驗(yàn)表明本算子對(duì)慣性權(quán)重的調(diào)節(jié)正好處于[0.3,0.7]最優(yōu)范圍內(nèi).數(shù)學(xué)期望為μ、方差為σ，則w的計(jì)算公式為：

(7)

式中:ε是在迭代過程中產(chǎn)生的隨機(jī)數(shù).在迭代搜索過程中，當(dāng)粒子群算法的群活性變化不大時(shí)，選取0.3～0.7之間的數(shù)并采用固定慣性權(quán)重求解策略；當(dāng)粒子群算法的群活性降低時(shí)，采用調(diào)整策略計(jì)算新的w對(duì)位置、速度進(jìn)行更新.

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

在實(shí)驗(yàn)時(shí)，粒子群算法的參數(shù)設(shè)置為：c1=c2=2，原始ω=0.8,最大迭代次數(shù)為400，每個(gè)粒子維數(shù)為10，種群大小為50，精度為10-6，高斯變異算子參數(shù)為：μ=0,σ=0.5.首先對(duì)改進(jìn)算子進(jìn)行實(shí)驗(yàn)，群活性算子和高斯變異慣性權(quán)重進(jìn)行Matlab仿真實(shí)驗(yàn).群活性測(cè)量采用經(jīng)典函數(shù)進(jìn)行，對(duì)群活性值進(jìn)行了一定的縮放，這種縮放不會(huì)影響群活性的變化曲線，形成的曲線如圖1所示.

圖1 粒子群活性變化圖

從粒子群活性圖中可以看出，SAF-GPSO算法相對(duì)于最基本的粒子群算法(PSO算法)在群活性變化上存在起伏波動(dòng)，SAF-GPSO算法在迭代到100次群活性降到最低，而PSO算法迭代到50次就降到最低，延長了近一倍的迭代時(shí)間. 對(duì)于尋優(yōu)性能比較，使用經(jīng)典的測(cè)試函數(shù)Sphere函數(shù)和Rastrigrin函數(shù)，公式如下:

-5.12≤xi≤5.12

算法的性能隨粒子維數(shù)變化使用遺傳算法(GA)，PSO和SAF-GPSO算法比較如表1所示.

表1 算法的平均適應(yīng)度值

由表1可以看出本文改進(jìn)算法在函數(shù)求解精度上隨著維數(shù)的增加優(yōu)于PSO和GA算法，在函數(shù)上隨著維數(shù)的增加，優(yōu)于PSO算法，但當(dāng)維數(shù)增加一定程度就沒有遺傳算法(GA)的求解精度好.對(duì)于求解效率，優(yōu)于PSO收斂快，故使用SAF-GPSO算法和PSO算法進(jìn)行比較.經(jīng)過400次迭代后取的Sphere函數(shù)最優(yōu)位置各維分量和適應(yīng)度函數(shù)值變化分布如圖2所示.

(a)Sphere函數(shù)分析圖

(b)Sphere函數(shù)適應(yīng)度函數(shù)值比較圖

實(shí)驗(yàn)表明SAF-GPSO算法與PSO算法相比在單峰函數(shù)Sphere求解尋優(yōu)性能和迭代次數(shù)上取得了很大的提高.對(duì)于多峰函數(shù)及分散性求解的SAF-GPSO尋優(yōu)性能使用Rastrigrin函數(shù)，經(jīng)過400次迭代后去的函數(shù)最優(yōu)位置各維分量和適應(yīng)度函數(shù)值變化分布如圖3所示.

由3可知，迭代400次后，Rastrigrin函數(shù)最優(yōu)位置各維分量和求解問題適應(yīng)度函數(shù)優(yōu)化效果沒有第Sphere函數(shù)優(yōu)化效果好，不過在整體的尋優(yōu)能力和時(shí)間上都比原始的粒子群算法更好.由第二個(gè)小圖的縮放圖可以看出，本文算法在迭代到45次左右時(shí)，適應(yīng)度函數(shù)就接近于0，而原始的粒子群算法則需要迭代到110次左右，故本文算法在Rastrigrin函數(shù)求解上也提高了近3/4的迭代次數(shù).

(a)Rastrigrin函數(shù)分析圖

(b)Rastrigrin函數(shù)適應(yīng)度函數(shù)比較圖

4 結(jié)論

本文提出了一種以種群多樣性作為群活性反饋的高斯粒子群優(yōu)化算法.通過算法改進(jìn)分析和函數(shù)實(shí)驗(yàn)結(jié)果表明:多樣性反饋能夠很好的增加群活性，提高近一倍；改進(jìn)慣性權(quán)重算子提高全局搜索，迭代時(shí)間縮短3/4；綜上可知，改進(jìn)算法能夠有效地調(diào)節(jié)PSO的早熟現(xiàn)象，搜索性能更優(yōu)化.

[1]EBERHART R C,SHI Y H.Comparing inertia weights and Constriction factors in particle swarm optimization[C].Proc of the 2000 Congress on Evolutionary Computation.San Diego: IEEE,2000:84- 88.

[2]JIAO B,LIAN Z G.A dynamic inertia weights particle swarm optimization algorithm[J].Chaos Solutions&Fractals,2008,37(3):698- 705.

[3]張頂學(xué),廖銳全.一種基于種群速度的自適應(yīng)粒子群算法[J].控制與決策,2009,24(8):1257- 1265.

[4]ZHAN Z,ZHANG J.Adaptive particle swarm optimization[J].IEEE Trans on Systems,Man and Cybernetics,Part B:Cybernetics,2009,39(6):1362- 1381.

[5]秦全德,李榮鈞.基于生物計(jì)生行為的雙種群粒子群算法[J].控制與決策,2011,26(4):548- 552.

[6]WANG Y,LI B,WEISE T,et al.Self-adaptive learning based particle swarm optimization [J].Applied Soft Computing,2011,11(1):574- 584.

[7]楊帆,胡春平,顏學(xué)峰.基于蟻群系統(tǒng)的參數(shù)自適應(yīng)粒子群算法及其應(yīng)用[J].控制理論與應(yīng)用,2010,27(11):1479- 1488.

[8]左旭坤,蘇守寶.一種群活性反饋粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2012,38(13):183- 184.

[9]LI PENG,QUAN HUIYUN.Improved hybrid particle swarm optimization algorithm[J].Computer EngineeringandApplication,2010,46(11):29- 31.

[10]張浩,張鐵男,沈繼紅，等.Tent混沌粒子群算法及其在結(jié)構(gòu)優(yōu)化決策中的應(yīng)用[J].控制與決策,2008,23(8):857- 863.

[11]EBERNART R C,KENNEDY J.Particle swarm optimization [C]// IEEE International Conference on Neural Networks.Perth,Australia,1995:1942- 1948.

[12]田雨波,朱人杰,薛權(quán)祥.粒子群優(yōu)化算法中慣性權(quán)重的研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2008，23:39- 41.

A Diversity of Feedback Gauss Particle Swarm Algorithm

HUANG Ming,ZHANG Chunlei,WU Yaoxu,HAO Qian

(Software Institute,Dalian Jiaotong University,Dalian 116028,China)

The diversity of the population feedback (swarm activity feedback) and Gauss normal inertia weight mutation operator is introduced to improve the particle swarm algorithm.When the particles swarm diversity is reduced,the inertia weight of particle is state calculation of regulation,and then adjust the particle velocity and position which could make the PSO jump out of local optimal solution. The standard function simulation results show that,compared with the standard particle swarm optimization algorithm,this algorithm is greatly improved in global search ability and search performance.

particle swarm optimization;inertia weight;diversity feedback;Gauss distribution

1673- 9590(2015)01- 0105- 04

2014- 02- 19

國家863計(jì)劃課題資助項(xiàng)目(2012AA041402-4)；遼寧省高校優(yōu)秀青年學(xué)者成長計(jì)劃資助項(xiàng)目(LJQ2013048)

黃明(1961-),男,教授，博士，主要從事計(jì)算機(jī)管理信息系統(tǒng)的研究

E-mail:dlhm@263.net.

A