李海濱，王 勇,張呈志

(廣西民族大學 信息科學與工程學院，廣西 南寧 530006)

?

一種新的變異粒子群算法*

李海濱，王 勇,張呈志

(廣西民族大學 信息科學與工程學院，廣西 南寧 530006)

基于對現(xiàn)實中鳥的飛行方式的模擬，提出了一種新的變異粒子群優(yōu)化算法(VPSO).該算法增加了粒子的飛行(搜索)模式,粒子具有隨時調(diào)整其飛行(搜索)方式的能力.實驗結果表明:筆者算法在一定程度上改善了標準PSO存在的易陷入局部最優(yōu)之不足，具有比標準PSO更強的跳出局部最優(yōu)的能力和更好的全局優(yōu)化能力，可用于求解高維復雜優(yōu)化問題.

算法粒子群算法(PSO)；變異的粒子群算法(VPSO)；飛行方式；吸引度

粒子群算法(PSO)[1]是Kennedy和Eberhart于1995年提出的一種群智能隨機搜索算法.該算法利用粒子群體的當前最優(yōu)位置信息和粒子個體的歷史最優(yōu)位置信息來指導粒子個體下一步的搜索行為，屬于有導向的隨機性啟發(fā)式算法.PSO具有理論方法簡單、設置參數(shù)少、易于編碼實現(xiàn)的特點.然而，PSO仍存在早熟收斂現(xiàn)象，特別在解決比較復雜的多峰優(yōu)化問題時，早熟收斂現(xiàn)象尤為明顯.針對PSO存在的不足，不少研究者已經(jīng)提出了多個版本的PSO改進算法[2-15].例如，文[3]提出了一種自適應的粒子群算法；文[4]提出了一種協(xié)同粒子群算法；文[5-6]則在標準PSO中引入慣性權重并使之線性遞減；文[7]提出了一種自適應變異的粒子群算法；文[8-9]則提出將其他算法與PSO相融合的混合算法；文[10]提出了一種具有時變加速率的自組織粒子群算法；文[11]提出了一種具有綜合學習能力的粒子群算法，等等.這些版本的PSO改進算法歸納起來主要有：1)控制慣性權重、學習因子、飛行速度等參數(shù)，以平衡算法的全局搜索與局部搜索能力；2)引入一些使算法能跳出局部極值的機制，以期提高算法的搜索效率；3)粒子的搜索方式與標準PSO的完全相同.文[2-15]提出的各種改進算法與標準PSO算法相比，改善了PSO算法的優(yōu)化性能，但仍存在一些不足.

針對標準PSO算法存在的早熟收斂問題，筆者基于對現(xiàn)實中鳥的飛行(搜索)方式的模擬，提出了一種新的變異粒子群優(yōu)化算法(A new variant particle swarm optimization,VPSO)，并通過數(shù)值仿真實驗對算法性能進行了驗證.

1 分析標準PSO存在的一些不足

設t時刻第i粒子在搜索空間中的位置和飛行速度分別表示為Xi(t)=(xi1(t),…，XiD(t))和Vi(t)=(vi1(t),…,viD(t)),第i粒子經(jīng)歷過的最優(yōu)位置記為Pbest(t)=(pi1(t),…,piD(t))；所有粒子當前找到的最優(yōu)位置記為Gbest(t)=(g1(t),…,gD(t)).第i粒子則按公式(1)和(2)來更新其飛行速度和位置：

vid(t+1)=wvid(t)+c1r1(pid(t)-xid(t))+c2r2(gd(t)-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1),d=1,…,D

(2)

其中w為慣性權因子,c1和c2為正的加速常數(shù),r1和r2為[0,1]中的均勻隨機數(shù).式(1)由三部分組成，第一部分wvid(t)為“慣性”，反映了粒子的運動“習慣”，代表粒子有維持自己先前速度的趨勢；第二部分c1r1(pid(t)-xid(t))為“認知”部分,反映了粒子對自身歷史經(jīng)驗的記憶，代表粒子有向自身歷史最優(yōu)位置逼近的趨勢；第三部分c2r2(gid(t)-xid(t))為“社會”部分，反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，代表粒子有向群體歷史最優(yōu)位置逼近的趨勢.可用圖1刻畫標準PSO算法中粒子的粗略飛行方向和搜索范圍.

圖1 粒子搜索范圍示意圖

分析公式(1)、(2)及圖1，我們不難看出，標準PSO設計的粒子位置移動方程，有可能產(chǎn)生以下問題：1)粒子任何時候都要受到當前群體最優(yōu)位置和自己找到的個體歷史最優(yōu)位置的雙重吸引，且沒有使粒子跳出局部最優(yōu)的機制.這促使粒子只能向由個體當前位置、個體歷史最優(yōu)位置與群體當前最優(yōu)位置所構成的扇形區(qū)域內(nèi)移動，粒子由于被這兩個位置的吸引而聚集到群體當前最優(yōu)位置的附近，使個體的搜索范圍得不到有效擴散，種群的多樣性也得不到有效保持.如果這兩個位置都不是全局最優(yōu)的，而只不過是局部最優(yōu)的，則算法搜索終將由于粒子的早熟而停止.2)粒子的飛行(搜索)方式單一，都只會用一種飛行(搜索)方式(即按式(1)和(2))在搜索空間中搜索目標.這使得粒子失去了飛行(搜索)的機動性，從而降低了粒子躲避障礙物或天敵的能力(即跳出局部最優(yōu)的能力)、降低了粒子的搜索能力，最終降低了粒子跳出局部最優(yōu)的能力.3)粒子在搜索中缺乏獨立性，使粒子群過早聚集到群體當前最優(yōu)位置的附近，從而使算法搜索的多樣性得不到有效保持.

2 一種新的變異粒子群算法

2.1 算法基本思想

鳥通常具有較好的飛行(搜索)技能，可使用多種飛行(搜索)方式在空間中搜索目標，可根據(jù)自身狀態(tài)隨時調(diào)整飛行方式.鳥為了搜尋到更多的食物或者保護自己不受傷害，通常會通過調(diào)整飛行方式來逃脫天敵的攻擊、躲避障礙物，或者對目標發(fā)起攻擊，確保自己不陷入困境(即不陷入局部最優(yōu)).鳥的飛行(搜索)方式主要有兩種：一種是鳥正在搜索目標時，采用比較平穩(wěn)的飛行(搜索)方式；一種是鳥逃脫天敵的攻擊、躲避障礙物、攻擊目標(如果實，獵物等)時，采用的變向飛行方式.鳥群中的每一個體都是獨立開展搜索活動的，其使用哪種飛行方式完全由其自主選擇.

為了不使算法描述過于復雜，作如下理想化假設：1)鳥的飛行(搜索)方式只有兩種：一種是平穩(wěn)的飛行(搜索)方式，一種是變向的飛行方式.2)鳥在搜索目標時，使用平穩(wěn)的飛行(搜索)方式；鳥攻擊目標(如果實、獵物等)時，使用變向的飛行方式.3)群體中的每一個體均可自主選擇其飛行(搜索)方式.

2.2 粒子位置變更方程設計

基于以上基本思想，我們設計粒子的飛行(搜索)方式、位置移動方程如下：

設第i粒子的位置和飛行速度分別表示為Xi(t)=(xi1(t),…,xiD(t))和Vi(t)=(vi1(t),…,viD(t))，其經(jīng)過的歷史最優(yōu)位置為Pbest(t)=(pi1(t),…,piD(t)).群體所有粒子當前找到的最優(yōu)位置記為Gbest(t)=(g1(t),…,gD(t)).

設群體規(guī)模是M.第t次迭代結束后，將群體粒子按各自所處位置的優(yōu)劣(依適應度值)按升序排列，位置最優(yōu)者排在第1位，次優(yōu)者排在第2位，依次類推，位置最差者排在第M′位，這里M′≤M(注：若群體中每個粒子的適應度值均不相同，則M′=M；若有若干個粒子具有相同的適應度值，則M′

先給出吸引度(Attract degree)的概念.定義:

(3)

式(3)說明，在第t次迭代結束后，當前群體最優(yōu)位置Gbest(t)對處于最優(yōu)位置的個體(即si(t)=1的個體)吸引度最小，而對處于最差位置的個體(即si(t)=M′的個體)吸引度最大.

●本文設計粒子使用平穩(wěn)的飛行(搜索)方式時，其飛行速度和位置變更方程按式(4)和(5)進行：

(4)

xij(t+1)=xij(t)+vij(t+1),j=1,…,D

(5)

其中w(t)為關于時間t的遞減函數(shù),r1為(0,1]中的隨機數(shù),c1,c2為正的常數(shù).本文在仿真實驗中，選取w(t)=wmax-(wmax-wmin)t/T，其中T為最大搜索時間,0

●由于鳥(粒子)攻擊目標時，使用變向的飛行方式?jīng)_向目標Gbest(t)所在地的周圍.因此，本文設計鳥(粒子)使用變向的飛行方式飛行時，其位置變更方程按如下公式(6)進行：

xij(t+1)=gk(t),j=1,…,D

(6)

其中k為{1,…,D}中一個隨機數(shù).

方程(6)表示群體中有一部分粒子受Gbest(t)的吸引而飛到Gbest(t)所在地的附近搜索，而有一部分粒子則不受目標Gbest(t)的吸引而飛到別的區(qū)域去覓食.其目的是防止過多的粒子聚集到群體當前最優(yōu)位置的附近覓食，使種群的多樣性得到有效保持.

2.3 粒子位置變更方程切換規(guī)則

由于群體中每一個體的搜索活動均是獨立開展的.因此，粒子使用哪一種飛行(搜索)方式，完全由其視不同情況選擇不同的飛行(搜索)方式：當其所處的位置比較有利于對目標發(fā)起攻擊時，則使用變向飛行方式對目標發(fā)起攻擊；當其所處的位置還不利于對目標發(fā)起攻擊時，則使用平穩(wěn)的飛行(搜索)方式在空間中開展搜索活動.因此，在同一時刻，可能有一部分粒子使用平穩(wěn)的飛行(搜索)方式在搜索空間中開展搜索活動，也可能有一部分粒子使用變向飛行方式對目標發(fā)起攻擊.而粒子使用平穩(wěn)的飛行(搜索)方式，還是變向的飛行方式，則具有一定的隨機性.因此，本文設計粒子位置變更方程切換規(guī)則如下：

其中δ為(0,1)中的均勻隨機數(shù),k為{1,…,D}中的一個隨機整數(shù),j=1,…,D.

3 數(shù)值實驗和算法比較

我們分析了參考文獻[2-15]的相關實驗結果和進化(收斂)曲線仿真圖，從中選擇比較有代表性的PSO-w[4]、CLPSO[11]、UPSO[13]，及標準PSO與本文算法(VPSO)進行算法性能比較.

3.1 測試函數(shù)

為了測試本文算法(VPSO)的性能，在本文實驗中，我們選用了8個經(jīng)典的基準函數(shù)，這些基準函數(shù)經(jīng)常被國內(nèi)外很多學者用來測試算法的優(yōu)化性能和穩(wěn)定性.所選用的基準函數(shù)如下(其中n=50)：

a)Schwefel′s function

b)Rastrigin′s function

c)Step function

d)Schwefel′s function

e)Sphere function

f)Griewank′s function

g)Rotated hyper-ellipsoid function

h)Zakharov′s function

-5≤xi≤10.該函數(shù)為單模函數(shù)，在點(0,…,0)處取得全局極小值0.

3.2 參數(shù)設置與實驗結果

為了可比性，在算法數(shù)值實驗測試中，讓5種算法的參數(shù)設置盡可能保持一致.具體參數(shù)設置如下：種群規(guī)模設置為30，加速常數(shù)設置為c1=c2=2，最大迭代次數(shù)設置為T=2000；對于標準PSO、CLPSO及UPSO 這3種算法，設置w(t)=w=0.628；對于PSO-w算法，則w從0.9線性下降到0.4，并限定粒子的最大速度vmax≤20%(bj-aj),其中aj和bj分別為第j維搜索域的下界和上界；對于本文算法(VPSO)，取w(t)=0.9-(0.9-0.4)t/T.

在實驗中，我們對算法運行作了如下設置：若算法搜索到精確解,或者算法搜索到的最優(yōu)解與精確解之差的絕對值小于a·10-32(0

為了避免隨機性對實驗結果的影響，每種算法對每個優(yōu)化問題均獨立運行30次.我們記錄了最優(yōu)值、最差值、平均值、標準差、平均迭代次數(shù)等評價指標實驗數(shù)據(jù)(見表1).這些評價指標既能反映算法優(yōu)化能力的強弱，又能反映算法計算代價的高低.

表1 實驗結果

為了能明顯對比出5種算法的收斂速度，我們給出了5種算法各自獨立運行30次所得到的函數(shù)最優(yōu)(適應度)值的平均值的進化(收斂)曲線仿真圖.圖2中的(a)至(h)為上述5種算法各自獨立運行30次所得到的最優(yōu)(適應度)值的平均值進化(收斂)曲線仿真圖.

(a)Schwefel′s function

(b)Rastrigin′s function

(c)Step function

(d)Schwefel′s function

(e)Sphere function

(f)Griewank′s function

(g)Rotated hyper- ellipsoid function

(h)Zakharov′s function

3.3 對比分析

分析表1中的實驗數(shù)據(jù)以及各測試函數(shù)進化(收斂)曲線仿真圖2，我們可以看出：本文算法(VPSO)在f1，f2，f3，f5，f6，f8這6個基準函數(shù)的優(yōu)化問題上，都具有比標準PSO、PSO-w、CLPSO、UPSO這4種算法更快的全局收斂速度、更好的優(yōu)化精度；對于f4和f7，本文算法(VPSO)在優(yōu)化精度、全局收斂速度不如CLPSO好，但與標準PSO、PSO-w、UPSO這3種算法處于同一個數(shù)量級，優(yōu)化性能相當.

據(jù)此，可以得出：本文算法(VPSO)在一定程度上克服了標準PSO易陷入局部極值的缺點，具有較強的跳出局部最優(yōu)的能力，總體上比標準PSO、PSO-w、UPSO這3種算法具有更快的全局收斂速度、更好的優(yōu)化精度、更強的全局搜索能力；本文算法(VPSO)的優(yōu)化性能總體上也比CLPSO優(yōu).

4 結語

針對標準PSO存在的早熟收斂問題，本文通過增加粒子的飛行(搜索)方式來增強粒子跳出局部最優(yōu)的能力、給予粒子隨時調(diào)整其飛行(搜索)方式來增加算法搜索的多樣性.本文在數(shù)值實驗中選擇了幾個比較典型的基準函數(shù)，用來測試本文算法的性能.仿真結果表明：本文算法具有比標準PSO、PSO-w、UPSO三種算法更快的全局收斂速度、更強的跳出局部最優(yōu)的能力和更好的全局優(yōu)化能力，優(yōu)化性能總體上也比CLPSO優(yōu).從實驗結果上看，本文算法(VPSO)仍存在早熟收斂問題，下一步，我們的研究工作重點將是如何克服VPSO算法存在的早熟收斂問題.

[1] J.Kennedy,R.C.Eberhart.Particle swarm optimization[C]∥ Proc.of the IEEE International conference on Neural Networks.1995,4:1942-1948.

[2] Kazemi BAL,Mohan CK.Multi-Phase generation of the particle swarm optimization algorithm[C]∥ In:Proc.of the IEEE Int'l Conf.on Evolutionary Computation.Honolulu:IEEE Inc.,2002：489-494.

[3] Hu XH,Eberhart RC.Adaptive particle swarm optimization:Detection and response to dynamic system[C]∥In:Proc.of the IEEE Inter.Conf.on Evolutonary Compututation.Honolulu:IEEE Inc.，2002：1666-1670.

[4] Van den Bergh F,Engelbrecht A P.A Cooperative Approach to Particle Swarm Optimization[J].IEEE.Trans on Evolutionary Computation,2004,8(3):225-239.

[5] Y.Shi.R.Eberhart.Parameter selection in particle swarm optimization[C]∥Proc.Of 7th Annual Conf.on Evolutionary Computation.1999:591-601.

[6] Y.Shi.R.Eberhart.Empirical study of particle swarm optimization[C]∥ Proc.of the Congress on Evolutionary Computation.1999,3:1945-1950.

[7] 呂振肅,侯志榮.自適應變異的粒子群優(yōu)化算法[J].電子學報,2004,32(3):416-420.

[8] Liu B,Wang L,Jin Y H,et al.Improved particle swarm optimization combined with chaos[J].Chaos Solitions & Fractals,2005,25:1261-1271.

[9] Sheloker P S,Jayaraman V K,Kulkarni B D.Particle swarm and ant colony algorithms hybridized for improved continuous optimization[J].Applied Mathematics and Computation,2007,188:129-142.

[10] Ratnaweera A,Halgamuge S K,Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J].IEEE Transaction on Evolutionary Computation,2004,8 (3):240-255.

[11] J.J.Liang,A.K.Qin,P.N.Suganthan,et al.Comprehensive learning particle swarm optimizers for global optimization of multimodal functions[J].IEEE Trans.on Evolutionary Computation,2006,10(3):67-82.

[12] 呂強,劉士榮.一種信息充分交流的粒子群優(yōu)化算法[J].電子學報,2010,38(3):664-667.

[13] 吳曉軍,楊戰(zhàn)中,趙 明.均勻搜索粒子群算法[J].電子學報,2011,39(6):1261-1266.

[14] 高 哲,廖曉鐘.基于平均速度的混合自適應粒子群算法[J].控制與決策,2012,27(1):152-155，160.

[15] 朱慶保,徐曉晴,朱世娟.一種新的求解動態(tài)連續(xù)優(yōu)化的分層粒子群算法[J].控制與決策,2013,28(10):1573-1577.

[責任編輯 蘇 琴]

[責任校對 黃招揚]

A New Variant Particle Swarm Optimization

LI Hai-bin,WANG Yong，ZHANG Cheng-zhi

(CollegeofInformationScienceandEngineering,GuangxiUniversityforNationalities,Nanning530006,China)

In this paper,a new optimization approach called variant particle swarm optimization (VPSO)is proposed based on simulating the real bird's flight modes.In the VPSO,every particle can use more than one flight (search)mode flying while it is searching for food,has the ability of adjusting its flight (search)modes at any time.In order to test the performance of the VPSO,numerical experiments were done on some typical high-dimensional and complex optimization problems,such as Schwefel's function,Rastrigin's function,Step function,Schwefel's function,Sphere function,Griewank's function,Rotated hyper-ellipsoid function,and Zakharov's function.The numerical experimental results indicate that the VPSO has,to a certain extent,improved the shortcoming of easy being fallen into local optimum which exists in the normal PSO,and has stronger ability to jump out of local optimum and better ability of global optimization than the normal PSO.The VPSO can be used to solve the complex and the high-dimensional optimization problems.

Particle swarm optimization(PSO);Variant particle swarm optimization(VPSO); Flight modes; Attract degree

2016-03-20.

2015年度廣西高等學?？茖W技術研究項目(KY2015YB078).

李海濱(1970-)，女(壯)，廣西民族大學副教授，研究方向：計算機應用、數(shù)據(jù)挖掘.

TP18

A

1673-8462(2016)03-0073-07