基于柯西分布的粒子群優(yōu)化算法改進

黎紅玲,羅　林,蒲冬梅,劉好斌

(內(nèi)江師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院,四川 內(nèi)江　641112)

基于柯西分布的粒子群優(yōu)化算法改進

黎紅玲,羅林,蒲冬梅,劉好斌

(內(nèi)江師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院,四川 內(nèi)江641112)

摘要針對傳統(tǒng)粒子群算法具有易陷入局部最優(yōu),收斂速度慢的特點,文中采用柯西密度函數(shù)和分布函數(shù)分別對慣性權(quán)重和位置更新公式作出改進。與標準PSO算法和利用柯西分布對慣性權(quán)重的改進相比,改進后的算法能快速地收斂到全局最優(yōu)解。且對4個經(jīng)典的測試函數(shù)進行仿真實驗,結(jié)果顯示改進算法求解精度高、解的穩(wěn)定性優(yōu)良,尤其是在多峰值函數(shù)中表現(xiàn)優(yōu)越。

關(guān)鍵詞粒子群優(yōu)化;慣性權(quán)重;位置更新;多峰函數(shù);柯西分布

Improved Particle Swarm Optimization Algorithm Based on Cauchy Distribution

LI Hongling,LUO Lin,PU Dongmei,LIU Haobin

(School of Mathematics and Information Science,Neijiang Normal College,Neijiang 641112,China)

AbstractThis article uses the Cauchy distribution function and density function respectively to improve the inertia weight and location update figure in view of the local optimal characteristics and slow convergence of traditional particle swarm optimization algorithms.Compared with the standard PSO algorithm and the Cauchy distribution improved inertia weight,the improved algorithm can converge to the global optimal solution quickly.Simulation of four classic test functions shows that the improved algorithm has high precision and good stability of the solution,especially in solving multimodal functions.

Keywordsparticle swarm optimization;inertia weight;location update;multi peak function;Cauchy distribution

粒子群算法[1](Particle Swarm Optimization,PSO)是由Kennedy和Eberhart 于1995年提出的一種進化計算技術(shù),其是基于一定假設(shè)條件,對鳥類捕食行為模擬的一種仿生優(yōu)化算法。該算法具有簡單易懂,容易實現(xiàn),收斂速度快等優(yōu)點,同時存在早熟收斂現(xiàn)象,易陷入局部最優(yōu)。

眾多學(xué)者為提高粒子群優(yōu)化算法的求解質(zhì)量,對算法作出了大量的改進,例如:利用余弦函數(shù)的對稱性[2]對學(xué)習(xí)因子進行改進,增強了局部搜索能力;Shi等[3]人首次將慣性權(quán)重引入PSO算法后,采用遞減指數(shù)和迭代閾值[4]對慣性權(quán)重進行了改進,使得結(jié)果在搜優(yōu)精度、收斂速度以及穩(wěn)定性等方面有明顯優(yōu)勢;基于粒子群自適應(yīng)[5]對慣性權(quán)重做出了改進。采用基于高斯概率分布和柯西概率分布的改進算法[6-7],提高了算法的速度,取得了良好的實驗效果;在服從柯西分布的假設(shè)下,利用個體分布的中位數(shù)和尺度參數(shù)[8]來自適應(yīng)的調(diào)整搜索范圍,從而提高收斂速度,有效地克服早熟現(xiàn)象;對粒子的全局極值進行柯西變異[9],以此增加種群的多樣性。各種不同的改進均在不同程度上促進了粒子群優(yōu)化算法的研究與發(fā)展。

本文針對粒子群優(yōu)化算法的早熟收斂現(xiàn)象以及后期局部搜索能力弱的缺點,利用柯西密度函數(shù)的單調(diào)遞減和分布函數(shù)的單調(diào)遞增分別對慣性權(quán)重和位置更新公式進行了改進,從而避免了算法的早熟收斂并增強了算法的局部尋優(yōu)能力。

1標準PSO算法

在標準PSO算法中,群體中每個粒子表示問題的一個可行解,并具有與目標函數(shù)相關(guān)的適應(yīng)度值。粒子在搜索空間中以一定的速度飛行,根據(jù)自身的飛行經(jīng)驗及當(dāng)前最優(yōu)粒子的狀態(tài)進行調(diào)整,個體之間在協(xié)作與競爭中實現(xiàn)對問題最優(yōu)解的搜索。

假設(shè)在一個D維的目標搜索空間中,有m個粒子組成,其中第i個粒子表示為一個D維向量xi=(xi1,xi2,…,xiD),i=1,2,3,…,m,即第i個粒子在D維搜索空間中的位置是xi,第i個粒子的速度是vi=(vi1,vi2,…,viD)。記第i個粒子搜索到最好的位置為pi=(pi1,pi2,…,piD),整個群體搜索到最好的位置pg=(pg1,pg2,…,pgD)。

在標準PSO算法中,粒子的速度-位置方程描述為

(1)

(2)

其中,w為慣性權(quán)重,是[0.4,0.9]之間的隨機數(shù);c1和c2為學(xué)習(xí)因子;r1,r2為介于[0,1]之間的隨機數(shù);且vid∈[-vmax,vmax]。w是對自身運動狀態(tài)的信任;c1是“認知部分”權(quán)重;c2是對粒子自身的思考。是“社會認知”權(quán)重,是粒子間的信息共享,來源于群體中各個優(yōu)秀粒子的經(jīng)驗。

2柯西分布的特征

柯西分布是一個連續(xù)型的分布函數(shù),具有較長兩翼的特點。其中滿足分布函數(shù)和密度函數(shù)的稱為標準柯西分布,分布函數(shù)(x>0)是嚴格單調(diào)遞增的函數(shù),密度函數(shù)是嚴格單調(diào)遞減的函數(shù)。其中分布函數(shù)表達式為

(3)

密度函數(shù)表達式為

(4)

函數(shù)圖像如圖1和圖2所示。

圖1　分布函數(shù)圖

圖2　密度函數(shù)圖

3算法的改進

3.1　慣性權(quán)重的調(diào)整

在粒子群算法的所有參數(shù)中,慣性權(quán)重是重要的參數(shù),可調(diào)整算法的全局搜索能力與局部搜索能力之間的平衡。w值較大時,全局搜索能力較強,局部搜索能力弱,w值較小時,全局搜索能力較弱,局部搜索能力較強[10]。為克服算法缺點,許多學(xué)者提出了多種慣性權(quán)重的改進策略,總結(jié)出:慣性權(quán)重w滿足線性或非線性遞減規(guī)律[11]時,算法的性能較好。

根據(jù)圖2的觀察可得出:當(dāng)x>0時,密度函數(shù)圖像呈遞減趨勢。滿足粒子群算法取得較好性能時,慣性權(quán)重呈遞減的規(guī)律。據(jù)此將慣性權(quán)重公式調(diào)整為

w=p(t)

(5)

其中,t為當(dāng)前迭代次數(shù)。w隨著迭代次數(shù)的增加而遞減,使算法在初期具有較強的全局搜索能力,迅速遍歷整個搜索空間后,局部搜索能力不斷增強,在可能的最優(yōu)解領(lǐng)域內(nèi)進行搜索,在提高算法收斂性的同時,有效地避免陷入局部最優(yōu)。

3.2　位置更新公式的改進

基于文獻[12]中,對位置公式加權(quán)改進,粒子的前一次位置對新位置的選擇所占的權(quán)重加大,使得粒子在選擇新位置的過程中有了參考點,減少了粒子位置選擇的盲目性。因此,收斂速度會逐漸提高,但當(dāng)權(quán)重過大時,粒子由于受前一次位置的影響過大,則通常陷入局部最優(yōu)。因此,算法中權(quán)重的取值是影響算法收斂速度的關(guān)鍵因素。

由以上的分布函數(shù)圖像可知:當(dāng)x>0時,函數(shù)圖像是先迅速增長,后緩慢增加。本文針對此函數(shù)圖像特點及文獻[10]中位置公式的加權(quán)改進,提出以下位置公式的改進算法

(6)

其中,t表示當(dāng)前迭代次數(shù);γ表示調(diào)整參數(shù),取值在區(qū)間。通過仿真實驗,可得出:位置更新公式的改進能有效地避免在搜索過程中由于步長過長而錯過全局極值,減少了在搜索過程中的盲目性。因此能提高算法的搜索效率。

綜合以上算法的改進,在標準粒子群的基礎(chǔ)上,可分為以下3種策略對粒子群算法進行調(diào)整:

策略1只采用式(5)對慣性權(quán)重進行調(diào)整;

策略2只采用式(6)對位置更新公式進行調(diào)整;

策略3結(jié)合式(5)和式(6)對粒子群優(yōu)化算法算法進行調(diào)整。

4仿真實驗

4.1　測試函數(shù)

對于上述策略,通過4個典型測試函數(shù)來測試:f1:Rosenbrock函數(shù),單峰,最優(yōu)值為0。

(7)

f2:Sphere函數(shù),單峰,最優(yōu)值為0。

(8)

f3:Griewank函數(shù),多峰,最優(yōu)值為0。

(9)

f4:Rastrigin函數(shù),多峰,最優(yōu)值為0。

(10)

4.2　位置更新公式調(diào)整參數(shù)的測試

本文利用Sphere函數(shù),在標準粒子群算法的基礎(chǔ)上,對式(5)中的調(diào)整參數(shù)γ進行實驗。對γ取不同的值,算法分別運行10次后取平均值和標準差,結(jié)果如表1所示。通過大量的實驗,結(jié)果證明:當(dāng)參數(shù)取0.2時,效果較好。

表1　調(diào)整參數(shù)γ對算法性能的影響分析

4.3　改進策略的比較實驗

本文利用Sphere函數(shù),在標準粒子群算法的基礎(chǔ)上,對策略1、策略2、策略3以及標準PSO進行測試,分別運行算法各10次后取平均值以及標準差,結(jié)果如表2所示。通過對表2的觀察比較可看出,策略3效果最佳。

表2　改進策略比較實驗結(jié)果

4.4　改進算法的測試

改進算法采用式(5)和式(6)分別對慣性權(quán)重和位置更新公式進行調(diào)整,得到表2中的結(jié)果。在式(6)中調(diào)整參數(shù)γ取0.2,迭代次數(shù)為100次,學(xué)習(xí)因子均取2,維數(shù)為10。利用標準PSO、文獻[7]和改進算法對4個測試函數(shù)分別進行測試,算法分別運行10次后取平均值以及標準差,結(jié)果如表3所示。

表3　標準PSO與改進算法測試結(jié)果比較

通過對表3的觀察比較,可以從單峰、多峰等方面對仿真結(jié)果進行分析可得:(1)針對單峰函數(shù)f1和f2,改進算法后的最優(yōu)值比標準PSO和文獻[7]的最優(yōu)值要好,從標準差可看出,改進后算法的穩(wěn)定性更好。(2)針對多峰函數(shù)f3和f4,改進算法后的最優(yōu)值優(yōu)于標準PSO和文獻[7],且算法更加穩(wěn)定。

綜上所述,特別是對典型的多峰函數(shù),改進算法能找到最優(yōu)值,在收斂速度和收斂精度上都有明顯提高,避免了陷入局部最優(yōu)。同時,改進后的算法更優(yōu)于已有柯西分布對權(quán)重的改進。

5結(jié)束語

本文利用柯西密度函數(shù)和分布函數(shù)的相關(guān)性質(zhì),對慣性權(quán)重和位置更新公式分別進行了動態(tài)調(diào)整,并對其進行了3個策略的仿真實驗。由此可得出,策略3的仿真效果明顯優(yōu)于其余策略。同時,與文獻[7]相比,改進后的算法結(jié)果明顯優(yōu)于文獻[7]中對慣性權(quán)重的改進。仿真實驗結(jié)果表明,改進后的粒子群算法的求解質(zhì)量比改進前的粒子群算法的求解質(zhì)量更高,尤其是在多峰函數(shù)中表現(xiàn)明顯。

參考文獻

[1]Kennedy J,Eberhart R.Particle swarm ()ptimization[C].Perth.Australia.USA:Proceedings of the IEEE International Conference on Netural Network,IEEE Press,1995.

[2]張敏,黃強,許周釗,等.基于余弦函數(shù)改進的PSO算法及其仿真[J].計算機應(yīng)用,2013,33(2):319-322

[3]Shi Y,Eberhart R C.A modified particle swarm optimizer[C].NZ,USA:IEEE World Congress on Computational Intelligence:The 1998 IEEE International Conference on Evolutionary Conference on Evolutionary Computation Proceedings,Piscataway:IEEE,1998:69-73.

[4]王麗,王俊凱.一種非線性改變慣性權(quán)重的粒子群算法[J].計算機工程與應(yīng)用,2007,43(4):47-48.

[5]董平平,高東慧,田雨波,等.一種改進的自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法[J].計算機仿真,2012,29(12):283-284.

[6]高麗麗,劉弘,李同喜.基于文化粒子群算法的約束優(yōu)化問題求解[J].計算機工程,2008,34(5):179-181.

[7]趙輝,王明,王紅君,等.改進的粒子群算法在燒結(jié)配料中的應(yīng)用[J].微型機與應(yīng)用,2012,31(16):85-87.

[8]逯少華,張曉偉,鮑承強,等.柯西種群分布的自適應(yīng)范圍粒子群優(yōu)化算法[J].計算機應(yīng)用,2014,34(4):1070-1073,1079.

[9]馬立新,屈娜娜,單冠華,等.電力系統(tǒng)無功優(yōu)化的柯西粒子群算法[J].控制工程,2011,18(5):758-761.

[10]杜振鑫,王兆青.一種改進的動態(tài)改變慣性權(quán)重的粒子群算法[J].微電子學(xué)與計算機,2011,28(3):85-88.

[11]張訊,王平,邢建春,等.基于高斯函數(shù)遞減慣性權(quán)重的粒子群優(yōu)化算法[J].計算機應(yīng)用研究,2012,29(10):3710-3712,3724.

[12]朱童,李小凡,魯明文.位置加權(quán)的改進粒子群算法[J].計算機工程與應(yīng)用,2011,47(5):4-6.

通訊作者:劉好斌(1983—),男,碩士,講師。研究方向:智能計算。

作者簡介:黎紅玲(1994—),女,本科。研究方向:數(shù)學(xué)與信息科學(xué)。

基金項目:教育部數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)綜合改革基金資助項目(ZG0464);四川高校數(shù)值仿真與數(shù)學(xué)實驗教學(xué)示范中心(01247);內(nèi)江師范學(xué)院青年科研基金資助項目(2011NJZ-3)

收稿日期:2015- 05- 16

中圖分類號TP306.1

文獻標識碼A

文章編號1007-7820(2016)01-033-04

doi:10.16180/j.cnki.issn1007-7820.2016.01.009