粒子群算法中慣性權重參數

王澤儒, 李芬田, 王紅梅

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

粒子群算法中慣性權重參數

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

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

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

粒子群； 種群； 空間維度； 慣性權重； 遞減率

0 引 言

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

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

1)算法改進研究;

2)算法性能分析;

3)算法應用領域研究。

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

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

1 粒子群算法

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

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

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

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

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

算法過程如下:

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

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

①計算每個粒子的適應值；

②根據粒子的適應值來更新粒子i的最好位置pi和粒子群的最好位置gfit；

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

b)如果該粒子的適應值比gfit好，則重新設置gfit。

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

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

1.2慣性權重

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

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

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

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

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

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

1.3關于慣性權重的分析與實驗

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

測試函數見表1。

表1 測試函數

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

Rastrigin函數圖像如圖1所示。

圖1 Rastrigin函數圖像

Rosenbrock函數圖像如圖2所示。

圖2 Rosenbrock函數圖像

測試環境如下:

操作系統:ubuntu 15.04×64；

編程軟件:Code::Blocks。

電腦配置如下:

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

運存：4 GB。

程序設計:

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

表2 函數功能表

2 固定慣性權重和可變慣性權重選擇

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

參數設置[14]如下：

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

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

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

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

在4個參數的設置下，進行20次優化測試函數實驗,實驗結果見表3。

表3 固定權重與時變權重在PSO中的表現

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

3 可變慣性權重范圍對收斂速度的影響

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

表4 不同慣性權重變化范圍對優化的影響

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

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

表5 不同遞減率的可變慣性權重優化效果

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

4 慣性權重選擇的問題依賴性

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

表6 Rastrigin函數與Sphere函數的優化效果

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

5 種群大小對于慣性權重選擇的影響

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

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

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

通過表6、表7和表8可以看出，增加粒子的數目可以改善優化效果，在已經達到最優效果的函數，增加粒子數目對迭代次數并沒有很明顯的改變，所以應當調整慣性權重。

經過實驗和選擇，當慣性權重變為(0.375-0.2)/1 000所有函數將取得最優值，現在我們將慣性權重改變為(0.375-0.2)/1 000進行實驗，實驗結果見表9。

表9 可變慣性權重(0.375-0.2)/1 000下規模為100的優化效果的影響

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

6 結 語

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

[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] 劉志雄,梁華.粒子群算法中隨機數參數的設置與實驗分析[J].控制理論與應用,2010,27(11):1489-1496.

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

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

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

[7] 呂雪冬.基于粒子群優化BP神經網絡在電站鍋爐中的應用研究[D].合肥：安徽大學,2015.

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

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

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

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

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

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

[14] 李聰,宋文龍.一種基于適應值分析的智能粒子群算法[J].計算機與現代化,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

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

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

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