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

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

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

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

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

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

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

粒子群算法；慣性權重；多樣性反饋；高斯算子

0 引言

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

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

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

1 標準粒子群算法

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

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

(3)

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

2 改進粒子群算法

2.1 改進粒子群算法步驟

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

步驟1：初始化粒子群.粒子群的大小N，搜索空間維數D，最大迭代次數t，尋優目標函數，慣性權重w，社會參數，c1,c1及r1，r2；

步驟2：計算當前代粒子位置的適應度函數值，比較更新局部最優和全局最優；

步驟3：判斷當前迭代次數是否達到最大或者適應度函數為0，若滿足則直接跳到步驟7，否則執行步驟4；

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

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

步驟6：判斷群活性是否降低，若降低則進行高斯慣性權重改進操作產生新的慣性權重，然后使用新得到的慣性權重，若沒有降低則執行步驟2；

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

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

2.2 多樣性反饋機制

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

(4)

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

(5)

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

(6)

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

2.3 改進慣性權重算子

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

(7)

式中:ε是在迭代過程中產生的隨機數.在迭代搜索過程中，當粒子群算法的群活性變化不大時，選取0.3～0.7之間的數并采用固定慣性權重求解策略；當粒子群算法的群活性降低時，采用調整策略計算新的w對位置、速度進行更新.

3 仿真實驗

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

圖1 粒子群活性變化圖

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

-5.12≤xi≤5.12

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

表1 算法的平均適應度值

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

(a)Sphere函數分析圖

(b)Sphere函數適應度函數值比較圖

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

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

(a)Rastrigrin函數分析圖

(b)Rastrigrin函數適應度函數比較圖

4 結論

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

[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]張頂學,廖銳全.一種基于種群速度的自適應粒子群算法[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].控制與決策,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]楊帆,胡春平,顏學峰.基于蟻群系統的參數自適應粒子群算法及其應用[J].控制理論與應用,2010,27(11):1479- 1488.

[8]左旭坤,蘇守寶.一種群活性反饋粒子群優化算法[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混沌粒子群算法及其在結構優化決策中的應用[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]田雨波,朱人杰,薛權祥.粒子群優化算法中慣性權重的研究進展[J].計算機工程與應用,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計劃課題資助項目(2012AA041402-4)；遼寧省高校優秀青年學者成長計劃資助項目(LJQ2013048)

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

E-mail:dlhm@263.net.

A