樊偉萍 李秦
(蘭州交通大學數理學院,甘肅 蘭州 730070)
粒子群優化算法(PSO)是由Kennedy和Eberhart于1995年通過觀察鳥群尋找棲息地的行為而簡化出的群體智能優化算法[1],具有設置參數少、易于實現、收斂速度快等優點而備受學者的青睞,但是PSO算法易陷入局部最優值.為了改善這一問題,學者們先后提出了各種應對策略,張迅等[2]人根據高斯函數分布特征設置慣性權重變化策略,文獻[3]基于文獻[2]提出了慣性權重對數遞減的粒子群算法,并引入對數調整因子α ,有助于粒子跳出局部極值,提高了算法的全局收斂性.Clerc 提出了帶有收縮因子的PSO算法[4],整體上具有比標準PSO算法更加高效地收斂性能,但在算法后期的精度比標準PSO算法性能差.總結來說,針對粒子群算法的改進大體上分為參數設置的改進[5-9]和算法融合改進[10-13],這些策略一定程度上優化了算法性能,提高了PSO 算法的尋優效率,但時間和空間消耗比較高,且無法避免粒子易陷入局部最優,易早熟的問題.本文在Shi和Eberhart提出的粒子群優化算法[2]慣性權重線性遞減的基礎上,添加了隨迭代次數線性遞增的調節因子p,使算法在局部搜索能力和全局搜索能力之間得到更好的平衡,同時針對粒子群算法搜索后期易陷入局部最優,影響算法優化性能的問題,在每次迭代時,對種群中的粒子進行突變操作,從而增強粒子跳出局部最優的能力,最后對測試函數進行尋優操作來驗證改進后粒子群優化算法(XWPSO)的有效性.
粒子群算法的主要思想是將需要尋優的問題的解想象成一只鳥,稱為一個“粒子”,然后讓所有粒子在D 維的搜索空間進行搜索,粒子位置的好壞由定義的適應度函數評價,并且給每個粒子賦予記憶功能,能夠記憶粒子搜索過程中尋到的最佳位置,同時,各個粒子之間也可以進行信息共享,通過粒子自身經驗和同伴的經驗來動態調整粒子位置.
粒子群算法中,粒子之間是相互合作,信息互通的,速度更新公式(1)由三部分組成,第一部分是粒子先前的速度,代表粒子的狀態;第二部分是粒子的“自我認知”部分,體現粒子的自我思考;第三部分是“社會”部分,體現粒子之間信息共享合作.
Shi 和Eberhart 提出了粒子群優化算法[14]慣性權重線性遞減的策略,對粒子群算法進行了修改,引入了慣性權重w.速度公式更改如下:
一定程度上優化了文獻[1]粒子的尋優性能,但線性遞減的慣性權重并不能如實的反映粒子復雜的搜索過程,尋到的最優解精度也不高,為了更進一步優化算法性能,文獻[15]在文獻[2]的基礎上將慣性權重w 修改為
考慮了正弦函數的周期性,又添加了rand(0~1之間)隨機數,來增加粒子搜索過程的隨機性,但時間損耗較大.
為了進一步提高算法的尋優性能和收斂精度,將慣性權重w 調整為
(1)Rastrigin函數:具有大量極值的多峰函數,其全局最優解和最優位置分別為
(2)Griewank函數:多峰函數,且其局部極小值均勻分布,全局最優解和最優位置分別為
(3)Ackley函數:復雜的多峰函數,有無數個極小值點,其全局最優解和最優位置分別為
為了驗證本文提出的XWPSO算法的有效性,采用XWPSO、PSO[1]、LPSO[14]、NXPSO[15]四種優化算法分別對Rastrigin、Griewank、Ackley三種經典函數進行優化,其中在PSO、LPSO、NXPSO優化算法中,2=2=1 cc,而在XWPSO 優化算法中05.2=2=1 cc,四種算法維度2=D,粒子數目40=N,搜索范圍[-5,5],慣性權重w 的變化范圍[0.4,0.9], 1r , 2r 在[0,1]之間服從均勻分布的隨機數,在Matble2016a環境中運行20次,實驗結果如表1所示
表1 尋優結果對比
由表1可以看出,在對Rastrigin函數優化時,基本粒子群算法PSO最優值8.0912e-04,平均值為0.036055456;LPSO算法最優值1.9263e-05,平均值為0.038160856;NXPSO算法最優值1.4231e-05,平均值為8.0043445e-04.而改變慣性權重的XWPSO算法最優值6.6352e-07,平均值為2.52246296e-04,在Rastrigin函數極值的優化方面明顯優于其他三種算法,更貼近函數最優解0,所以改進的粒子群優化算法較其他三種方法更優.同時對多峰函數Griewank、Ackley 的優化結果可以看到,從得到的最優值結果的平均值上來看,XWPSO算法也是明顯優于其他算法的,從而驗證了算法的有效性.
圖1 Rastrigin函數在優化算法下的適應度曲線
圖2 Griewank函數在優化算法下的適應度曲線
圖3 Ackley函數在優化算法下的適應度曲線
Rastrigin、Griewank、Ackley 函數在PSO、LPSO、NXPSO、XWPSO 優化算法下的適應度曲線圖如圖1~3所示,XWPSO算法的適應度函數選用的是測試函數表達式本身,所以算法尋找到的適應度值就是要尋找的測試函數極值,從圖中可看出,改進的粒子群算法較其他三種優化算法更早地收斂于函數的最優值,并且收斂精度也更高.在Rastrigin函數優化時,PSO算法在第17次迭代時趨于測試函數最優值,LPSO算法在第10次迭代時趨于測試函數最優值,NXPSO算法在第4次迭代時趨于測試函數最優值,XWPSO算法在第3次迭代時就趨于測試函數最優值;在Griewank函數優化時,PSO算法在第12次迭代時趨于測試函數最優值,LPSO算法在第18次迭代時趨于測試函數最優值,NXPSO算法在第11次迭代時趨于測試函數最優值,XWPSO算法在第3次迭代時趨于測試函數最優值;在Ackley函數優化時,PSO算法在第8次迭代時趨于測試函數最優值,LPSO算法在第4次迭代時趨于測試函數最優值,NXPSO 算法在第16 次迭代時趨于測試函數最優值,XWPSO 算法在第5次迭代時趨于測試函數最優值.
從實驗結果可知,改進的粒子群優化算法XWPSO較其他幾種優化算法具有較強的收斂性和收斂精度,尤其在Rastrigin、Ackley函數的優化效果更明顯,從而也驗證了XWPSO算法的有效性.
本文應用的改進粒子群慣性權重的XWPSO在Shi和Eberhart提出的慣性權重線性遞減的基礎上添加了隨迭代次數線性遞增的調節因子p,使得改進之后的XWPSO在尋優能力和收斂精度上都有所提高,同時將XWPSO 算法與經典的PSO、LPSO、NXPSO 算法進行比較,該算法具有更快跳出局部極值,且收斂點更貼近函數最優解,與傳統的PSO、LPSO、NXPSO算法相比較,XWPSO算法在測試函數維度2=n時尋優能力和收斂精度更高.