粒子群算法中慣性權(quán)重參數(shù)

王澤儒, 李芬田, 王紅梅

(長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院， 吉林 長春 130012)

粒子群算法中慣性權(quán)重參數(shù)

王澤儒, 李芬田, 王紅梅*

(長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院， 吉林 長春 130012)

研究粒子群算法慣性權(quán)重與種群規(guī)模大小、空間維度以及慣性權(quán)重遞減率的關(guān)系,對多個具有代表性的函數(shù)進行實驗研究。結(jié)果表明，適當改變慣性權(quán)重可以快速收斂、提高搜索效率以及避免陷入局部最優(yōu)。

粒子群； 種群； 空間維度； 慣性權(quán)重； 遞減率

0 引 言

粒子群算法[1-2]是一種進化仿生算法，1995年由Eberhart 和Kennedy[2-3]提出，源于對鳥群捕食的行為研究。粒子群算法是模擬群體智能所建立起來的一種優(yōu)化算法，粒子群算法可以用鳥類在一個空間內(nèi)隨機覓食為例，所有的鳥都不知道食物具體的位置和方向，但是它們知道距離食物大約有多遠，最簡單快速的辦法就是搜尋當前距離食物位置最近的鳥的周圍區(qū)域。所以，粒子群算法就是把鳥看成一個個粒子，并且它們擁有位置和速度這兩個屬性，然后根據(jù)自身已經(jīng)找到的離食物最近的解和參考整個共享于整個集群中找到的最近的解去改變自己的飛行方向，最后會發(fā)現(xiàn)，整個集群大致向同一個地方聚集。而這個地方是離食物最近的區(qū)域，條件好的話就會找到食物，這就是粒子群算法。粒子群算法相對于其他優(yōu)化算法的優(yōu)勢在于容易實現(xiàn)，過程簡單，并且沒有很多參數(shù)需要調(diào)整。目前.粒子群算法已廣泛應(yīng)用于模糊系統(tǒng)控制[4]、函數(shù)優(yōu)化[5]、電網(wǎng)規(guī)劃和建筑結(jié)構(gòu)損傷中的應(yīng)用[6]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練[7]、Web應(yīng)用[8]、電路系統(tǒng)應(yīng)用[9]、數(shù)據(jù)聚類[10]等。

目前階段對于粒子群算法的研究主要集中在3個方面：

1)算法改進研究;

2)算法性能分析;

3)算法應(yīng)用領(lǐng)域研究。

而對于算法性能分析研究主要集中在算法中各個參數(shù)的不同取值組合對算法性能的影響。在粒子群算法中，慣性權(quán)重是最重要的并且可以調(diào)整的參數(shù)之一。文獻[11]指出，當慣性權(quán)重較大，算法的全局搜索能力較強，找到全局較優(yōu)解的概率較大;反之，算法的局部搜索能力較強，收斂速度較快。若想平衡好全局搜索能力和局部搜索能力，慣性權(quán)重選取的方法是問題的關(guān)鍵所在。

文中研究了粒子群算法中慣性權(quán)重的選取與種群規(guī)模大小、空間維度與慣性權(quán)重遞減率三者的關(guān)系。在迭代過程中，慣性權(quán)重是以線性遞減率來線性遞減，這種線性遞減慣性權(quán)重稱為可變慣性權(quán)重。這種可變慣性權(quán)重在每次迭代后提高了收斂速度，局部搜索能力越來越強。通過三個具有代表性函數(shù)進行實驗研究表明，可變慣性權(quán)重具有很好的優(yōu)化效率。

1 粒子群算法

1.1粒子算法一般框架[12]

假設(shè)存在一個D維空間的目標搜索空間，搜索空間中有m個粒子組成的一個種群，其中第i個粒子在D維搜索空間中的位置xi= (xi1,xi2,…,xid),第i維的飛行速度Vi= (vi1,vi2,…,vid),記第i個粒子的當前搜索到的最好位置為pi= (pi1,pi2,…,pid),整個粒子群目前在搜索空間中搜索到的最好的位置為g=(g1,g2,…,gd),則根據(jù)下式進行更新其速度和位置為

式中：c1,c2----學(xué)習因子，取值范圍是非負數(shù)，通常取值為2；

r1,r2----[0，1]之間的隨機數(shù)；

w----慣性權(quán)重,其大小決定了粒子對當前速度改變的大小，合適的選擇可以提高粒子群算法的效率。粒子速度被限定在一個最大速度V_max的范圍內(nèi)。

算法過程如下:

1)設(shè)置種群規(guī)模為P_num，初始化粒子群，包括每個粒子的隨機位置和速度;

2)重復(fù)下述操作，直到滿足終止條件。

①計算每個粒子的適應(yīng)值；

②根據(jù)粒子的適應(yīng)值來更新粒子i的最好位置pi和粒子群的最好位置gfit；

a)如果該粒子的適應(yīng)值比pi好，則將其作為當前的最好位置p；

b)如果該粒子的適應(yīng)值比gfit好，則重新設(shè)置gfit。

③根據(jù)式(1)和式(2)改變粒子的速度和位置；

④輸出粒子群的最好位置gfit。

1.2慣性權(quán)重

慣性權(quán)重是在粒子群算法中調(diào)整全局搜索與局部搜索中可控的重要參數(shù)。文獻[13]指出，比較大的慣性權(quán)重有利于全局搜索，但是搜索效率低，算法開銷較大;較小的慣性權(quán)重可以增加算法的收斂速度，但是很容易陷入局部最優(yōu)。設(shè)置合理的慣性權(quán)重，可以避免陷入局部最優(yōu)并且是高效搜索的關(guān)鍵。

在現(xiàn)實問題的背景下，慣性權(quán)重需要怎么去設(shè)置，要同時分析的因素有很多。其中，對當前搜索狀態(tài)影響最大的參數(shù)是種群規(guī)模大小、搜索空間維度以及慣性權(quán)重遞減率，這三者與粒子群算法慣性權(quán)重有著密切的關(guān)系。下面分別對種群規(guī)模、搜索空間維度以及慣性權(quán)重遞減率進行分析。

種群規(guī)模的大小是決定粒子對搜索空間分散密集重要因素。當種群規(guī)模較大時，粒子分散較廣，粒子所在區(qū)域覆蓋較大，同時找到全局最優(yōu)解的概率較大，應(yīng)該減小慣性權(quán)重，提高局部搜索能力，以實現(xiàn)快速收斂與全局較優(yōu);種群規(guī)模較小時，特別對于多峰函數(shù)，粒子不能有效地分散在整個搜索空間，則應(yīng)該增大慣性權(quán)重，提高全局搜索能力，避免陷入局部最優(yōu)。

由文獻[14]可知，當搜索空間維度較大時，粒子群算法常常收斂過早，很容易陷入局部最優(yōu)。在復(fù)雜程度不同的問題背景下，搜索效率與尋優(yōu)能力之間尋求較好平衡極為重要。對于高維度的搜索空間的復(fù)雜問題，應(yīng)該通過減小慣性權(quán)重值的方法來提高全局搜索能力，盡可能地避免過早的收斂導(dǎo)致優(yōu)化陷入局部最優(yōu)。相反，當搜索空間維度較小時，應(yīng)該增大慣性權(quán)重值實現(xiàn)快速收斂來提高效率。

通常，在全局優(yōu)化算法中，我們總是希望在優(yōu)化前期具有較好的全局搜索能力，以便快速地找到合適的優(yōu)化點，而后在優(yōu)化后期具有較好的局部搜索能力，以便來加快收斂的速度，所以，粒子群算法的慣性權(quán)重值應(yīng)該是變化的，并且是遞減的。

由以上分析可知，慣性權(quán)重與種群規(guī)模大小、搜索空間維度與慣性權(quán)重遞減率有著密切關(guān)系，慣性權(quán)重的取值將會影響粒子群算法的優(yōu)化效果。

1.3關(guān)于慣性權(quán)重的分析與實驗

慣性權(quán)重作為粒子群算法中重要的參數(shù)，其主要分為兩類：固定慣性權(quán)重和可變慣性權(quán)重。固定慣性權(quán)重就是選擇某一個常數(shù)作為權(quán)重值，在優(yōu)化的過程中權(quán)重值保持不變。而可變慣性權(quán)重就是選擇某一個變化的范圍，在迭代的過程中按照某一個線性遞減率線性的減小，所以，可變慣性權(quán)重的選擇包括變化的范圍和遞減率的選擇。

測試函數(shù)見表1。

表1 測試函數(shù)

Rastrigin函數(shù)對優(yōu)化算法具有很強的欺騙性，因為它有很多的局部最小值點和局部最大值點，很容易使算法陷入局部最優(yōu)，而不能得到全局最優(yōu)解。

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

圖1 Rastrigin函數(shù)圖像

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

圖2 Rosenbrock函數(shù)圖像

測試環(huán)境如下:

操作系統(tǒng):ubuntu 15.04×64；

編程軟件:Code::Blocks。

電腦配置如下:

處理器：AMD A10-5745M APU with Radeon(tm) HD Graphics×4；

運存：4 GB。

程序設(shè)計:

文中測試代碼使用C語言編寫代碼進行測試，主要的函數(shù)有main( ),initial( ),fitness(double a[]), renew_particle( ),renew_var( )，見表2。

表2 函數(shù)功能表

2 固定慣性權(quán)重和可變慣性權(quán)重選擇

固定慣性權(quán)重使粒子始終具有相同的搜索能力，可變慣性權(quán)重使粒子在不同的時期具有不同的搜索能力,設(shè)置種群規(guī)模為30進行實驗。

參數(shù)設(shè)置[14]如下：

1)w=0.6,c1=c2=1.7；

2)w=0.729,c1=c2=1.494；

3)可變慣性權(quán)重范圍[0.2 - 0.9],遞減率:(0.9-0.2)/4 000,c1=c2=2；

4)可變慣性權(quán)重范圍[0.2 - 0.9]，遞減率:(0.9-0.2)/1 000,c1=c2=2。

在4個參數(shù)的設(shè)置下，進行20次優(yōu)化測試函數(shù)實驗,實驗結(jié)果見表3。

表3 固定權(quán)重與時變權(quán)重在PSO中的表現(xiàn)

表3結(jié)果表明，文獻推薦的慣性權(quán)重(包括學(xué)習因子)具有較好的收斂性，但是，可變慣性權(quán)重沒有取得比慣性權(quán)重較好的效果。主要原因是文獻推薦的慣性權(quán)重是經(jīng)過實驗詳細的選擇，而實驗中的可變慣性權(quán)重只是簡單的改變，調(diào)整遞減率之后，收斂速度明顯提升，說明經(jīng)過精細的選擇，將會有很大的進步空間。

3 可變慣性權(quán)重范圍對收斂速度的影響

使用Rosenbrock函數(shù)對可變慣性權(quán)重范圍及收斂速度的影響。參數(shù)設(shè)置種群規(guī)模為30,維度為30，每次運行最大迭代次數(shù)為4 000次，對函數(shù)進行優(yōu)化20次，權(quán)重的變化率均定義為(w_max - w_min)/1 000,實驗結(jié)果見表4。

表4 不同慣性權(quán)重變化范圍對優(yōu)化的影響

由表4可知,較小的慣性權(quán)重對Rosenbrock函數(shù)的影響比較大，有較強的優(yōu)化效果，說明這個函數(shù)需要局部搜索的能力，即需要局部最優(yōu)解。特別是在0.4～0.2這個范圍內(nèi)，全部達到了最優(yōu)解。

遞減率的選擇應(yīng)該考慮到對優(yōu)化效果的影響，最好使平均迭代次數(shù)與遞減率相匹配。通過表4可以看出,當慣性權(quán)重的范圍在[0.4 -0.2]與[0.7 -0.2]之間優(yōu)化比較好?，F(xiàn)在繼續(xù)選擇Rosenbrock函數(shù)做實驗，參數(shù)設(shè)置種群規(guī)模為30,維度大小設(shè)置為30，每次運行最大迭代次數(shù)為4 000次，對函數(shù)進行優(yōu)化20次，改變可變慣性權(quán)重的遞減率，實驗結(jié)果見表5。

表5 不同遞減率的可變慣性權(quán)重優(yōu)化效果

從表5可以看出，在同一個變化范圍內(nèi)，隨著遞減率的減少，優(yōu)化的成功率增加。說明在種群規(guī)模覆蓋率較大的情況下，需要提高局部搜索能力，以達到快速收斂的目的。

4 慣性權(quán)重選擇的問題依賴性

從前面的實驗可以得出結(jié)論，Rosenbrock函數(shù)在使用可變慣性權(quán)重遞減率(0.4-0.2)/2 000能取得較好的優(yōu)化效果。對其他函數(shù)是否如此，這里我們做個實驗，設(shè)置維數(shù)均為30，參數(shù)設(shè)置：權(quán)重的變化率均定義為(w_max-w_min)/1 000。實驗結(jié)果見表6。

表6 Rastrigin函數(shù)與Sphere函數(shù)的優(yōu)化效果

由上述實驗可得，當可變慣性權(quán)重的遞減率取值在(0.4-0.2)/1 000都可以有很好的優(yōu)化效果。這說明慣性權(quán)重的取值對于問題有一定的依賴性，但不是很強。當可變慣性權(quán)重遞減率在(0.7-0.2)/1 000的時候，測試函數(shù)對于優(yōu)化效果都比較滿意。

5 種群大小對于慣性權(quán)重選擇的影響

增大種群，將會增加算法并行性，但是種群增大并不意味著慣性權(quán)重的選擇重要，由上述實驗可以得出，當可變慣性權(quán)重遞減率在(0.7-0.2)/1 000的時候，測試函數(shù)對于優(yōu)化效果都比較滿意。我們改變粒子的數(shù)目為60,100進行實驗，實驗結(jié)果見表7和表8。

表7可變慣性權(quán)重(0.7-0.2)/1 000下增加粒子數(shù)目為60對優(yōu)化效果的影響

表8 可變慣性權(quán)重(0.7-0.2)/1 000下增加粒子數(shù)目為100對優(yōu)化效果的影響

通過表6、表7和表8可以看出，增加粒子的數(shù)目可以改善優(yōu)化效果，在已經(jīng)達到最優(yōu)效果的函數(shù)，增加粒子數(shù)目對迭代次數(shù)并沒有很明顯的改變，所以應(yīng)當調(diào)整慣性權(quán)重。

經(jīng)過實驗和選擇，當慣性權(quán)重變?yōu)?0.375-0.2)/1 000所有函數(shù)將取得最優(yōu)值，現(xiàn)在我們將慣性權(quán)重改變?yōu)?0.375-0.2)/1 000進行實驗，實驗結(jié)果見表9。

表9 可變慣性權(quán)重(0.375-0.2)/1 000下規(guī)模為100的優(yōu)化效果的影響

由表9可以看出，當增加種群規(guī)模的時候，相對減小遞減率的取值范圍，可以取得較好的優(yōu)化，這是因為當增大種群規(guī)模的時候，粒子更加專注自己身邊小范圍的搜索，對于發(fā)展能力增強，全局搜索能力減弱。

6 結(jié) 語

綜上所述，在粒子群算法中，慣性權(quán)重的選擇是一個重要的問題，適當?shù)倪x擇將會提高優(yōu)化效率，同時，慣性權(quán)重對于問題的依賴不大，經(jīng)過詳細的選擇，很多問題都可以在相同的可變慣性權(quán)重下取得比較好的優(yōu)化效果。隨著種群規(guī)模大小的增大，粒子更加注重于自己身邊小范圍的搜索，所以應(yīng)當適當?shù)臏p少慣性權(quán)重的值。隨著搜索空間維度的增大，應(yīng)該減小慣性權(quán)重值以提高全局搜索能力，避免過早收斂而陷入局部最優(yōu)。相反，當搜索空間維度較小時，為提高搜索效率，應(yīng)該增大慣性權(quán)重值實現(xiàn)快速收斂。在一般的全局優(yōu)化中，前期有較高的全局搜索能力以找到合適的優(yōu)化點，慣性權(quán)重值應(yīng)該較大，而后期具有較高的局部搜索能力，以加快收斂速度，所以慣性權(quán)重值應(yīng)該是遞減的。

[1] Kennedy J, Eberhart R. Particle swarm optimization[C]//IEEE lnt. Conf. on Neural Networks, Piscataway: IEEE Service Center,1995:1942-1948.

[2] Eberhart R, Kennedy J. A new optimizer using particle swarm theory[C]//Proc. on lnt. Symposium on Micro Machine and Human Science, Piscataway: IEEE Service Center,1995:39-43.

[3] 劉志雄,梁華.粒子群算法中隨機數(shù)參數(shù)的設(shè)置與實驗分析[J].控制理論與應(yīng)用,2010,27(11):1489-1496.

[4] 李維嘉,蘭秋華,彭勇,等.基于粒子群算法的滑閥節(jié)流槽優(yōu)化設(shè)計[J].中國機械工程,2015，26(8):995-999.

[5] 王建林,吳佳歡,張超然,等.基于自適應(yīng)進化學(xué)習的約束多目標粒子群優(yōu)化算法[J].控制與決策,2014(10):1765-1770.

[6] 丁帥偉,姜漢橋,周代余,等.基于改進粒子群算法的不規(guī)則井網(wǎng)自動優(yōu)化[J].中國海上油氣,2016,28(1):80-85.

[7] 呂雪冬.基于粒子群優(yōu)化BP神經(jīng)網(wǎng)絡(luò)在電站鍋爐中的應(yīng)用研究[D].合肥：安徽大學(xué),2015.

[8] 溫濤,盛國軍，郭權(quán),等.基于改進粒子群算法的Web服務(wù)組合[J].計算機學(xué)報,2013,36(5):1031-1046.

[9] 楊麗華.粒子群算法在電力系統(tǒng)中的應(yīng)用研究[J].科技與創(chuàng)新,2016(3):90-90.

[10] 王金永，董玉臣.改進料子群算法在數(shù)據(jù)聚類中應(yīng)用[J].長春工業(yè)大學(xué)學(xué)報，2015,36(6):664-672.

[11] 黃珍,潘穎,曹曉麗.粒子群算法的基本理論及其改進研究[J].硅谷,2014,7(5):37-39.

[12] 皮倩瑛,葉洪濤. 一種動態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法[J].廣西科技大學(xué)學(xué)報,2016,27(3):26-32.

[13] 黃太安,生佳根,徐紅洋,等.一種改進的簡化粒子群算法[J].計算機仿真,2013,30(2):327-330.

[14] 李聰,宋文龍.一種基于適應(yīng)值分析的智能粒子群算法[J].計算機與現(xiàn)代化,2015(5):21-24.

Inertiaweightparametersinparticleswarmalgorithm

WANG Zeru, LI Fentian, WANG Hongmei*

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012, China)

The relationship between Inertial weight parameters with population size, space dimension and decreasing rate of the inertia weight are studied for particle swarm algorithm. Experiments are made based on some typical functions. The results show that inertia weight variation can let the algorithm quickly converged, searching efficiently and local optimization avoided.

particle swarm； population size； space dimensions； inertia weight； decreasing rate.

TP 301

A

1674-1374(2017)04-0354-07

2017-03-21

吉林省科技廳發(fā)展計劃基金資助項目(20160415013JH)

王澤儒(1992-)，男，漢族，山東臨沂人，長春工業(yè)大學(xué)碩士研究生，主要從事數(shù)據(jù)挖掘技術(shù)方向研究,E-mail:rrwangzeru@163.com. *通訊作者：王紅梅(1968-)，女，漢族，吉林長春人，長春工業(yè)大學(xué)教授，博士，主要從事數(shù)據(jù)挖掘技術(shù)方向研究,E-mail:wanghm@ccut.edu.cn.

10.15923/j.cnki.cn22-1382/t.2017.4.07