粒子群優化算法的邊界變異策略比較研究

宋 莉,鄧長壽,曹良林

(九江學院信息科學與技術學院,江西九江332005)

粒子群優化算法的邊界變異策略比較研究

宋 莉,鄧長壽,曹良林

(九江學院信息科學與技術學院,江西九江332005)

為解決粒子群優化(PSO)算法中粒子越界和早熟收斂等問題,在比較國內外學者提出的邊界變異策略基礎上,提出一種新的邊界變異策略——雙重限制變異策略。針對粒子越界時速度和位置變異方向的不同情形,通過同時限制粒子的更新位置和更新速度,將粒子控制在搜索空間范圍內。利用5種測試函數進行實驗,結果表明,與其他4種邊界變異策略相比,雙重變異策略收斂速度快,在解決粒子越界問題上具有較好的效果。此外,通過實驗測試顯示粒子的最大速度和最大位置的比值與變異策略的好壞程度成反比,為邊界變異策略的研究提供了一定依據。

粒子群優化;邊界變異;雙重限制;搜索空間;越界;早熟收斂

1 概述

粒子群優化(Particle Swarm Optimization,PSO)算法作為群智能(Swarm Intelligence,SI)領域中的一種重要方法,由Kennedy博士和Eberhart教授于1995年提出［1］,其核心思想源于對鳥類捕食行為的模擬,它將社會學中有關相互作用或信息交換的概念引入到問題求解方法中,目前被廣泛應用于各種優化問題中。

通常在處理最優化問題中都假設搜索空間有

限,而待優化問題的最優解一般位于搜索空間內。文獻［2］通過比較多種不同的PSO算法發現,粒子在飛行尋求最優解過程中都或多或少的飛越邊界,從而難以獲取最優解。如何采用有效的方法將粒子限定在搜索空間內成為了眾學者研究的方向之一。

目前,不斷有學者提出各種邊界變異策略用以解決粒子越界問題。文獻［3］提出了當粒子的位置或速度超出可行域時將其重新均勻分布在可行區間內;文獻［4］提出了吸收墻、反射墻和隱匿墻;文獻［5］結合吸收墻和隱匿墻,提出了衰弱墻;文獻［6］通過最小值變異有效地限制了粒子位置或速度的幅值,并保持了粒子的飛行方向;文獻［7］列舉了9種典型的邊界變異情形。而文獻［8-9］提出的最大位置限制和最大速度限制是最常用的方法,上述策略中大部分都是對這種方法的改進算法。該方法是當粒子的位置或速度超出最大值時,直接將其置為最大值,易造成多個粒子在邊界聚集,降低粒子的尋優能力,如果邊界附近存在局部最優,這些粒子很容易陷入這個局部最優點,導致算法早熟收斂。因此,采取有效的邊界變異方法將粒子控制在搜索空間內成為必須要解決的問題。

本文提出雙重變異策略,根據粒子速度和位置變異方向的4種不同情形,通過同時限制粒子的飛行速度和位置,以期解決粒子的越界問題。

2 標準粒子群算法

標準PSO算法隨機初始化一群沒有體積和質量的粒子,將每個粒子視為優化問題的一個可行解,粒子的好壞由一個事先設定的適應度函數來確定。每個粒子在可行解空間中運動,其速度通過最優解和整個粒子群最優解動態調整。在每次迭代中,粒子根據式(1)和式(2)來調節速度和位置:

其中,ω為慣性權重;c1,c2學習因子;rand為(0,1)上的隨機數;Pi,d為個體最優位置;Pg,d為粒子群迄今最優位置。

3 粒子邊界變異策略比較

根據粒子邊界變異的情形,本文列舉了以下4種邊界變異情形與本文策略進行對比:

(1)No confinement［7］,即沒有約束,在這種情形下,粒子的變異根據下面的偽代碼進行計算:

其中,V(t)為粒子在D維空間的變化速度;X(t)為粒子在D維空間中的當前位置;p(t)為粒子在D維空間中的歷史最優位置;pg(t)為粒子群的所有p(t)中的最優位置;rand為(0,1)上的隨機數;c為(0,2)上的常數,稱為加速因子;w為慣性權重。

在這種策略下,粒子不受邊界約束,使得在算法進化過程中大量飛出邊界的粒子,僅通過粒子本身及粒子間的相互作用回到搜索空間內,大大降低了粒子的尋優能力。

(2)No confinement+artificial landscape［7］,即通過添加一個人工參數,對粒子的飛行進行控制,fitness為一個線性增長函數,偽代碼描述如下:

其中,fitness為適應度函數

這種策略通過在搜索空間外定義一個適應度函數的方式,對速度的范圍沒有限制,但通過構造人工適應度函數值,使越界粒子的適應度函數值比在邊界上的函數值還要大,從而使粒子距離最優值更遠,也就更容易被拋離,降低了算法的優化性能。

(3)Standard,即標準形式下的粒子偏移。將理論上偏移出去的粒子,通過將偏移速度置0,將當前位置拉回邊界上來控制粒子的越界。偽代碼描述如下:

粒子的飛行軌跡如圖1所示。

圖1 粒子的飛行軌跡

該方法將粒子位置重置與邊界上,如果邊界附近存在局部最優解,很容易使粒子陷入局部最優,導致算法早熟收斂,此外容易造成大量粒子的聚集,降低粒子的尋優能力。并且粒子經過再次迭代,并不能保證其限制在搜索空間內。

(4)SzAPso算法［10］,即基于空間縮放和吸引子的粒子群算法,它是為了解決粒子群算法中粒子越界、算法進化后期收斂速度慢和早熟收斂問題而提出的。算法中加入了吸引子和縮放因子,按吸引子和空間縮放方法對粒子的位置進行更新。具體核心算法可數學描述為:

其中,%是求模運算符;sl=Pa-Xmin;sr=Xmax-Pa。

該算法利用對搜索空間進行縮放的邊界變異策略有效地將粒子控制在了搜索空間內,解決了粒子越界問題,保證了算法的全局探測能力,提高了算法的收斂速度和精度。

4 雙重限制變異策略

4.1 雙重限制變異策略的提出

當粒子越界時,采用某種策略,將粒子從邊界上拉回搜索空間,成為了各種變異策略必須要解決的問題。目前,大部分策略都只考慮到限定粒子的位置或減慢粒子飛行的速度。這樣就產生了一個問題,當粒子越界時,粒子的位置飛越了搜索空間,但是粒子的速度如果很大,如果只限定位置而不限定速度的話,粒子還是會越界,反之亦然?；谶@一點,本文提出了一種新的變異策略——雙重限制變異策略(Double Restrictions)。這一策略主要是通過同時限制粒子的更新位置和更新速度來實現。根據粒子的速度和位置的變異方向,分為了4種情形:粒子的變異速度和位置同向和反向。具體的解決辦法為:當粒子飛出搜索空間時,限定粒子的位置,將粒子拉回搜索空間,如果發現粒子的速度超越最大速度限制時,限定粒子的速度,減慢粒子的飛行速度;反之,當粒子沒有飛出搜索空間,但是發現粒子的速度超越最大速度限制時,限制粒子的飛行速度。通過這種策略,就把飛行出邊界的粒子拉回了搜索空間,把沒有越界但是飛行速度異常的粒子限定在正常的飛行范圍之內。

4.2 雙重限制變異策略的基本原理

考慮到粒子速度和位置的各種情形這里只列舉出粒子正方向飛越邊界的情形。

(1)粒子的位置變異,但速度保持不變,具體偽代碼如下:

(2)粒子的速度變異,但位置保持不變,具體偽代碼如下:

(3)粒子的速度與位置同時變異,具體偽代碼如下:

速度:

位置:

根據上述前2種情形不難看出,粒子不斷被置于邊界上,很容易陷入局部最優,從而使算法產生停滯。粒子的不斷聚集,容易使得粒子的飛行軌跡趨于相同,從而降低整個粒子群的效率?；谶@一點,本文提出了通過限制粒子的更新位置和更新速度來實現邊界變異的雙重限制變異策略(Double Restrictions)。

根據粒子的速度和位置的變異方向,分為以下情形:

(1)當粒子的位置向正方向變異時,粒子的速度變異可以分為2種情形:正方向和反方向。正方向變異時,這時粒子飛越邊界的概率非常大,就要把粒子拉回邊界內;反方向變異時,是最好的情況,這時不需要做處理。同理,當粒子的位置向反方向變異時,粒子的速度變異可以分為2種情形:正方向和反方向。反方向變異時,這時粒子飛越邊界的概率非常大,就要把粒子拉回邊界內;正方向變異時,是最好的情況,這時不需要做處理。具體偽代碼如下:

1)粒子的位置正方向變異并且粒子的速度也朝正方向變異:

2)粒子的位置反方向變異并且粒子的速度也朝反方向變異:

粒子的變異如圖2所示。

圖2 粒子的速度和位置都向正方向變異的情形

(2)當粒子的速度向正方向變異時,粒子的位置變異可以分為2種情形:正方向和反方向。正方向變異時,這時粒子飛越邊界的概率非常大,就要把粒子拉回邊界內;反方向變異時,是最好的情況,這時不需要做處理。同理,當粒子的速度向反方向變

異時,粒子的位置變異可以分為兩種情形:正方向和反方向。反方向變異時,這時粒子飛越邊界的概率非常大,就要把粒子拉回邊界內;正方向變異時,是最好的情況,這時不需要做處理。具體偽代碼如下:

1)粒子的速度正方向變異并且粒子的位置也朝正方向變異:

2)粒子的速度反方向變異并且粒子的位置也朝反方向變異:

粒子的變異如圖3所示?？梢钥闯?當粒子的速度朝正方向變異但粒子的位置朝反方向變異時粒子是否飛出邊界取決與這粒子的速度與位置之間的關系。本文直接限制粒子的變異速度,如果粒子的位置值比速度大,粒子肯定會在邊界之中,不需做任何處理;如果粒子的速度值比位置值大,論文由于限制了粒子的速度,所以粒子還是會處于邊界之內。

圖3 速度朝正方向、粒子位置朝反方向變異的情況

粒子的速度和位置都反方向變異和粒子的速度反方向變異但粒子的位置正方向變異的情形與上面的2種情形一樣,只是方向不同而已,此處不再贅述。

5 實驗分析

5.1 實驗設計

根據粒子的變異狀況,本文采用5種測試函數進行實驗:Sphere,Quadric,Rastrigin,Rosenbrock, Step［11］,見表1,對上述4種變異策略及本文提出的雙重限制變異策略進行比較研究。其中,Sphere為非線性對稱單峰函數,主要用來測試算法的尋優精度;Quadric為帶噪音的四次方程,主要用來衡量算法在處理大量噪聲的單峰測試函數的性能;Rastrigin是一個典型的具有大量局部最優點的復雜多峰函數,主要用來測試算法是否容易陷入局部最優; Rosenbrock為很難極小化的典型病態二次函數,主要用來評價算法的執行性能;Step函數只有一個極小值且不連續,對于需要梯度信息來指導搜索方向的函數很難解決這一函數。

具體實驗參數為:實驗粒子迭代次數根據測試函數的收斂情況不同有所差別,分別為100次、100次、200次、100次、20次;實驗次數分別為10次、30次、30次、30次、10次。粒子維數為30維,但Rosenbrock函數由于適應度值比較高,因此論文把這個測試函數的維數定為了5維,種群規模為100,學習因子c1和c2為1.494 45,慣性權重為0.792 0。

表1 基準測試函數及參數

為更好地研究粒子的變異策略,本文引進了Clerc M提出的限定因子χ［12］,限定因子χ的公式為:

本文取φ=4.5,這樣χ的值限定在0.5,可以解決由于加入過多隨機性帶來的算法收斂速度和收斂精度不足的問題。

為方便研究,各種變異策略縮寫為Noconfinement(NC),Artificiallandscape(AL), Standard(S.),SzAPso(SP),Double Restrictions (DR)。

5.2 實驗結果及分析

表2為粒子在5種測試函數下5種變異策略的粒子的最好值、最差值、中間值、平均值、標準方差的測試數據。

表2 5種測試函數下5變異策略的測試數據

從表2的測試數據可以看出,在取得最好值方面,DR策略除了在Rastrigin測試函數排行第二外,在其他4種函數中均處于第一;在最差值、中間值、平均值、標準方差方面,DR策略效果也很好?？梢钥闯?在這5種策略里,DR策略在對粒子的越界問題處理上具有良好的性能。

由于收斂曲線較多,因此本文只列舉有代表性的用于結果分析。收斂曲線如圖4～圖12所示。

圖4 DR策略在Sphere函數下的收斂曲線

圖5 NC策略在Step函數下的收斂曲線

圖6 DR策略在Step函數下的收斂曲線

圖7 DR策略在Quadric函數下的收斂曲線

圖8 SP策略在Quadric函數下的收斂曲線

圖9 DR策略在Rastrigin函數下的收斂曲線

圖10 DR策略在Rosenbrock函數下的收斂曲線

圖11 SP策略在Rosenbrock函數下的收斂曲線1

圖12 SP策略在Rosenbrock函數下的收斂曲線2

在使用Rosenbrock函數測試過程中,由于SP策略在迭代100次還沒有收斂,經過測試,在1 300次左右收斂,因此該策略測試了2次。

從收斂曲線來看,在Sphere和Rastrigin測試函數下5種策略收斂曲線都比較平緩,設定精度的話,收斂效果都很好;在Step測試函數下5種策略都能收斂到0,設定精度的話,收斂效果都很好,NC策略相對收斂較慢;在Quadric測試函數下D.R策略和SP策略收斂效果比較理想,設定精度為0.01時,收斂效果都很好,其他3種策略效果相對不太理想;在Rosenbrock測試函數下,除了SP.策略收斂速度相對較慢外,其他策略收斂曲線比較平滑,都在60次左右收斂到0,均表現了比較好的收斂效果。

綜上所述,本文提出的雙重限制變異策略在這5個測試函數里面的收斂效果和收斂曲線都表現得比較好,并且沒有局限在幾個測試函數里面,總體來看,無論在最差值、平均值、中間值、標準方差的數據來看,對粒子越界問題的處理上具有良好的性能。

為更好地對比文中提到的幾種策略,本文對每種策略的邊界越界處理進行時間復雜度分析:

設D為維數,Np為種群大小,T為迭代次數。

(1)NC策略:在粒子越界時未對粒子進行處理故時間復雜度為0。

(2)AL策略、S.策略及SP.策略:算法每迭代1次,每個粒子的每一維度對粒子位置要判斷2次,因此,每次迭代算法的時間復雜度為O(2DNp),T次迭代后算法總的時間復雜度為:O(2DNpT)。

(3)DR策略:算法每迭代一次,每個粒子的每一維度對粒子位置和速度均要判斷2次,因此,每次迭代算法的時間復雜度為O(4DNp),T次迭代后算法總的運算時間復雜度為:O(4DNpT)

從分析來看,雙重邊界變異算法的時間復雜度確實相比其他算法有所增加,但與AL策略、S策略及SP策略同階。綜合來看,雙重邊界變異策略具有較好的性能。

為研究比較Vmax與Xmax之間的關系是否對粒子

的邊界變異策略產生影響,本文選擇Step測試函數對5種策略通過5種情形進行測試。測試參數如下:測試50次,種群規模為100,粒子的維數為30,迭代次數為20次。

表3為Vmax=KXmax,K值分別為1/2,1/3,1/5, 1/7,1/10時的測試結果。

表3 K取5種值時的測試結果

從上面的測試數據可以看出,K的值越大,變異策略的最好值越小,從Vmax與Xmax的關系可以看出,Vmax的值越小,變異策略的最好值越大,從一定程度上可以說明,K值與變異策略的好壞程度成反比。從穩定性來看,在K=1/7時,測試中的5種策略的最好值都相差不大,表現的比較穩定。K=1/10時,每種策略的值相對其他情形來看比較大。

6 結束語

為進一步提高PSO算法的優化性能,本文在比較國內外學者提出的邊界變異策略的基礎上,提出了雙重限制邊界變異策略。通過實驗對比可以發現,本文提出的雙重限制變異策略在處理粒子越界問題的總體性能上具有優勢,為解決粒子的越界問題提供了算法依據。

根據文中的比較研究和實驗結果表明,邊界變異策略在改善PSO算法的性能上具有較廣闊的應用前景,將其引入到其他智能算法中是今后重要的研究方向。

［1]Kennedy J,Eberhart R C.Particle Swarm Optimization［C］//Proceedings of IEEE International Conference on Neural Network.Piscataway,USA:IEEE Service Center,1995:1942-1948.

［2]Monson C K,Seppi K D.Exposing Origin-seeking Bias in PSO［C］//Proceedings of GECCO’05.Washington D.C., USA:IEEE Press,2005:241-248.

［3]付國江,王少梅,劉舒燕,等.含邊界變異的粒子群算法［J］.武漢理工學報,2005,27(9):101-104.

［4]Robinson J,Yahya R.Particle Swarm Optimization in Electromagnetic［J］.IEEE Transactions on Antennas Propagation,2004,52(2):397-407.

［5]Huang T,Mohan A S.A Hybrid Boundary Condition for Robust Particle Swarm Optimization［J］.IEEE Antennas and Wireless Propagation Letters,2005,4(1):112-117.［6]蔣紹先,孔 韜,魏瑞軒.粒子群算法的最小值邊界變異策略［J］.電光與控制,2007,14(3):94-97.

［7]Clerc M.Confinements and Biases in Particle Swarm Optimization［EB/OL］.(2006-03-02).http://clerc.maurice.free.fr/pso/.

［8]Eberhart R,Shi Y.Particle Swarm Optimization:Developments,Applications,and Resources［C］//Proceedings of IEEEInternationalConferenceonEvolu-tionary Computation.Piscataway,USA:IEEE Press,2001:81-86.

［9]Said M,Ahamed A.Hybrid Periodic Boundary Condition for Particle Swarm Optimization［J］.IEEE Transactions on Antennas and Propagation,2007,55(11):3251-3256.

［10]遲玉紅,孫富春,王維軍,等.基于空間縮放和吸引子的粒子群優化算法［J］.計算機學報,2011,34(1): 115-130.

［11]Yao Xin,LiuYong,LinGuangming.Evolutionary Programming Made Faster［J］.IEEE Transactions on Evolutionary Computation,1999,3(2):82-102.

［12]Clerc M.TheSwarmandtheQueen:Towardsa Deterministic and Adaptive Particle Swarm Optimization［C］//Proceedings of 1999 Congress on Evolutionary Computation.Piscataway,USA:IEEE Service Center,1999:1951-1957.

編輯 金胡考

Comparative Study of Boundary Mutation Strategy for Particle Swarm Optimization Algorithm

SONG Li,DENG Changshou,CAO Lianglin
(School of Information Science and Technology,Jiujiang University,Jiujiang 332005,China)

To control particles to fly inside search space and deal with the problems of premature convergence of Particle Swarm Optimization(PSO)algorithm,based on the comparative study of boundary mutation strategy proposed by scholars at home and abroad,this paper proposes an improved PSO algorithm,called double restriction mutation strategy.When particle tends to leave the search space,in view of the different situation for direction of velocity and position,the strategy controls the particle in the search space effectively,mainly by limiting to updating the position while updating the speed of the particle.This paper lists the performance comparison of four kinds of boundary mutation strategy and this strategy.Experimental studies through five test functions show that the double limit mutation strategy proposed in this paper has faster convergence speed.It is more effective to solve the problem of particle bound.Furthermore,this paper tests the relationship between maximum speed and position on the boundary mutation strategy by experiment.The result shows that the ratio of particles’maximum speed and position is inversely proportional to the good or bad degree of the mutation strategy.It provides a basis for the study of boundary mutation strategy.

Particle Swarm Optimization(PSO);boundary mutation;double restrictions;search space;out of bounds; premature convergence

宋 莉,鄧長壽,曹良林.粒子群優化算法的邊界變異策略比較研究［J］.計算機工程, 2015,41(3):191-197,210.

英文引用格式:Song Li,Deng Changshou,Cao Lianglin.Comparative Study of Boundary Mutation Strategy for Particle Swarm Optimization Algorithm［J］.Computer Engineering,2015,41(3):191-197,210.

1000-3428(2015)03-0191-07

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.037

國家自然科學基金資助項目(61364025);江西省教育廳科學技術基金資助項目(GJJ13729);武漢大學軟件工程國家重點實驗室開放基金資助項目(SKLSE2012-09-39);九江學院科研基金資助項目(2013KJ31)。

宋 莉(1982-),女,講師、碩士,主研方向:智能計算;鄧長壽,教授、博士、CCF會員;曹良林,講師、碩士。

2014-01-02

:2014-04-22E-mail:songli413@163.com