1、粒子群算法的慣性權重調整策略李麗1薛冰2牛奔31深圳大學管理學院信管系，廣東深圳（518060 ）2深圳大學管理學院信管系，廣東深圳（518060）3深圳大學管理學院信管系，廣東深圳（518060）E-mail （小五， Times New Roman ）摘 要：慣性權重是粒子群算法改進的一個重要出發(fā)點，通過調整慣性權重可以大大提高算法的性能。本文在介紹粒子群算法原理、流程的基礎上，分析了慣性權重在算法尋優(yōu)過程中的重要作用，然后歸納了運用不冋方法對慣性權重的改進，進行了間單的討論，并對下一步工作進行了展望。關鍵詞：粒子群算法慣性權重改進策略1引言粒子群優(yōu)化算法（Particle SwarmOp

2、timization , PSO是 1995 年由 Eberhant 和 Kennedy 在文獻1中提出的一種基于群體智能、自適應的搜索優(yōu)化方法。其基本思想源于對魚類、鳥 類等群體社會行為的觀察研究。粒子群算法提出以后，由于其算法概念簡單、需要調整的參數(shù)較少、容易實現(xiàn)和快速收斂能力，已被廣泛地用在科學和工程領域，如電力系統(tǒng)優(yōu)化（文 獻31 33 ）、TSP問題（文獻海）、神經(jīng)網(wǎng)絡訓練（文獻昭）、函數(shù)優(yōu)化（文獻何、昭）等。粒子群算法在應用過程中體現(xiàn)出了很強的尋優(yōu)能力，但與其他全局優(yōu)化算法相同，粒子群算法也存在早熟局部收斂和后期震蕩現(xiàn)象。針對這些問題，國內(nèi)外學者經(jīng)過大量研究工作，提出了多種改進方法

3、，包括參數(shù)改進，拓撲結構改進和混合算法等。其中慣性權重是最重要的可調整參數(shù)，慣性權重由于其概念簡單、容易理解、改進的方法較多、改進的空間較大且 容易實現(xiàn)等特點，成為很多學者研究的焦點。通過調整慣性權重的值可以實現(xiàn)全局搜索和局 部搜索之間的平衡：較大的權值有利于提高全局搜索能力，而較小的權會提高局部搜索能力。諸多研究者運用線性遞減、非線性遞減等方法對慣性權重進行調整，實現(xiàn)了算法在不同方面和不同程度上的改進。本文通過對國內(nèi)外研究人員所提出的調整慣性權重策略進行歸納總 結，討論了各種策略的優(yōu)缺點，并在此基礎上提出了下一步工作方向及需要解決的問題。2基本粒子群算法在粒子群算法中，每個尋優(yōu)的問題解都被想

4、像成一只“鳥”，也稱為一個沒有重量和體積的粒子，每個的粒子在n維搜索空間里飛行，并有一個速度決定其飛行的距離與方向，所有粒子都有一個適應值函數(shù)來判斷其目前位置的好壞， 具有記憶性的，能記得所搜尋到的最佳位置。因此，在飛行過程中，每一代都能找出兩個“極值” 程中最優(yōu)解，代表粒子自身認知水平，稱之為個體極值且在飛行過程中，每一個粒子都是:每一個粒子到目前為止的搜尋過Pbest ;所有群體中的最優(yōu)解，代表社會認知水平，稱之為全局極值Gbest。粒子群算法首先初始化一群隨機粒子，然后根據(jù)兩個“極值”通過更新迭代找到最優(yōu)解，其基本迭代方程如下：Vid (t1) Vid(t)C1 rand () (pid

5、Xid(t) C2 rand () (PgdXid (t)( 1)其中，Vid表示粒子表示迭代到第t代時粒子Xi (t 1) Xi(t)i在第d維的速度，nVi(t 1)(2)維向量 (t)(Xi1,Xi2i的位置，n維向量vi (t)(vi1, vi2,xin )，V in )表示粒子i的速度。C1、C2是學習因子，rand ()是均勻分布于0,1之間的隨機數(shù)，Pid表示個體極值Pbest，pgd表示全局極值Gbest。為了防止x/t)溢出，設置Vmax來控制v/t)的范圍:Vi (t)Vi (t)Vmax .Vi (t)VmaxVi (t)Vmax(3)具體算法流程如下:(1) 初始化所有

6、微粒(群體規(guī)模為 N ,在允許范圍內(nèi)隨機設置微粒的初始位置和速度并將各微粒的pid設為初始位置，取pgd為pid中的最優(yōu)值。(2) 評價每個微粒的適應值，即分別計算每個微粒的目標函數(shù)值。(3) 對于每個微粒，將其適應值與所經(jīng)歷過的最好位置pid的適應值進行比較，若較好,則將其作為當前的最優(yōu)位置。Pgd的適應值進行比較，若(4) 對于每個微粒，將其適應值與群體所經(jīng)歷過的最好位置較好，則將其作為當前的全局最優(yōu)位置。(5) 根據(jù)速度和位置更新方程對微粒的速度和位置進行更新。(6) 如未達到結束條件，通常為足夠好的適應值或是達到一個預設的最大迭代代數(shù) 返回第(2)步。具體算法流程圖如下:微粒群體初始化

7、微粒適度值評價計算個體歷史最優(yōu)值和全局最優(yōu)值根據(jù)速度和位置更新方程更新微粒速度和3 慣性權重的提出經(jīng)過大量的研究試驗，為了提高基本粒子群算法的收斂性能和避免算法陷入局部最優(yōu)，Y.Shi 和 R.C.Eberhant 于 1998 年在 A modified particle swarm optimizer (文獻 2 )一文中提 出了慣性權重這一概念，在進化方程( 1)中引入慣性權重因子 w ，即：Vid (t1)wVid(t)c1rand ()(pidxid (t)c2rand ()(pgdxid (t)(4)等式右邊的結構和( 1)式一樣，第一部分是粒子先前的自身速度，用來保證算法的全 局

8、收斂性； 第二和第三部分是引起微粒速度變化的社會因素， 使算法具有局部搜索能力。 所 以 w 起到了一個平衡全局搜索能力和局部搜索能力的作用， w 值較大時全局搜索能力強， 局部搜索能力弱； w 值較小時，反之。恰當?shù)?w 值可以提高算法性能，提高尋優(yōu)能力， 減少迭代次數(shù)。慣性權重的引入， 對粒子群算法的發(fā)展起到了很大推動作用， 大大拓展了算法改進的空 間。但是要達到算法性能最優(yōu)還存在很多缺陷，因為當 w 值較大時，有利于全局搜索，雖 收斂速度快，但不易得到精確解； w 值較小時有利于局部搜索和得到更為精確的解，但收 斂速度慢且有時會陷入局部極值。如何尋找合適的 w 值使之在搜索精度和搜索速度

9、方面起 恰當?shù)膮f(xié)調作用， 成為很多學者研究的一個新方向， 通過幾年的發(fā)展， 已有了不少研究成果。4 慣性權重調整策略基于研究各種問題的復雜性和慣性權重在算法迭代過程中所起到的平衡作用， 除了固定 慣性權重以外， 學者們還提出了很多種慣性權重調整策略， 主要有線性遞減策略、 非線性遞 減策略和自適應調整策略等以下幾種：4.1 線性遞減策略 由于在一般的全局優(yōu)化算法中，總希望前期有較高的全局搜索能力以找到合適的種子， 而在后期有較高的開發(fā)能力， 以加快收斂速度， 所以慣性權重的值應該是遞減的。 其中的線 性遞減策略主要有以下幾種：4.1.1 典型線性遞減策略Y.Shi 和 R.C.Eberhant

10、 在文獻 2 還中提到了 w 應是隨著進化線性遞減的。這是首次提 出的慣性權重遞減策略，我們稱之為典型線性遞減策略， w 的計算公式如下：W(t)WmaxWmaxWmin(5)max其中Wmax、Wmin分別是W的最大值和最小值；t、t m ax分別是當前迭代次數(shù)和最大迭代次數(shù)(全文中符號表示意義相同)。文獻【9試驗了將W設置為從0.9到0.4的線性下降，使得PSO在開始時探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置，隨著W逐漸減小，粒子速度減慢，開始精細的局部搜索。該方法使PSO更好地控制全局搜索能力和局部搜索能力，加快了收斂速度，提高了算法的性能。這種典型的慣性權重線性遞減策略在目前是應用最

11、為廣泛，但是由于這種策略下， 迭代初期全局搜索能力較強，如果在初期搜索不到最好點，那么隨著W的減小，局部搜索能力加強，就易陷入局部極值。4.1.2線性微分遞減策略為了克服典型線性遞減策略的局限性，文獻14中提出了一種線性微分遞減策略，慣性權重的計算公式如下：dwdt2 ( W m ax W m in )t2m ax(6)W(t) Wmax(WmaxWmin )2m axt2(7)通過對W變化方程及實驗結果進行分析，由于在算法進化初期 W的減小趨勢緩慢， 全局搜索能力很強，有利于找到很好的優(yōu)化種子，在算法進化后期， W的減小趨勢加快, 因此一旦在前期找到合適的種子， 可以使得算法收斂速度加快，在

12、一定程度上減弱了典型線 性遞減策略的局限性，相應地在算法性能提高上有了很大改善。4.2非線性遞減策略4.2.1帶閥值的非線性遞減策略慣性權重線性遞減策略經(jīng)過不斷改進，已經(jīng)比原始的慣性策略有了很大改善。但是由于其線性遞減的特征，對于很多問題，在迭代過程中，算法一旦進入局部極值點鄰域內(nèi)就很難跳出來，為了克服這種不足，文獻18在典型線性遞減策略的基礎上引入了遞減指數(shù)和迭代閥值To ,提出了一種慣性權重的非線性遞減策略，即：t 1w(t)Wmax() (WmaxWmin)( 8)T01此時參數(shù)集變?yōu)椋琖max、Wmin、T。，當?shù)螖?shù)到達 T。時，令 W(t) Wmax，并保持到搜索結束，整個迭代過

13、程由于的引入，w(t)隨著t的增大而非線性遞減，有利最優(yōu)值的大概范圍，隨著迭代的進行w非線性減小，大部分粒子的搜索空間逐漸減小，并且集中在最優(yōu)值的鄰域范圍內(nèi)；在迭代末期當達到迭代閥值時，將慣性權重限定為wmax粒子以近乎不變的飛行速度在最優(yōu)值鄰域范圍內(nèi)找到全局最優(yōu)解，有利于提高算法的收斂速度，尤其對于低維測試函數(shù)， 無論在搜索最優(yōu)值精度、 收斂速度還是在穩(wěn)定性方面都有明顯 的優(yōu)勢。422先增后減策略針對遞減策略中仍然存在的不足，文獻16提出了一種具有先增后減慣性權重的微粒群算 法，W的慣性權重計算方程如下：W(t)tt max0.4tt max0.5ttmax1.40.5Lt max(9)在前

14、期有較快的收斂速度， 而后期的文獻16經(jīng)過試驗研究，這種先增后減的慣性權重, 局部搜索能力也不錯，在一定程度上保持了遞減和遞增策略的優(yōu)點，同時克服了一些缺點，相對提高了算法性能。此外，國內(nèi)還有人提出了其他的非線性動態(tài)遞減慣性權重，如文獻19中提出依據(jù)下式來計算慣性權重的方法：W(t) (Wmax Wmindje1 d2t/tmax(10)其中d1， d 2為控制因子，目的是為了控制w在Wmax和W m in之間。經(jīng)過大量實驗證明當d!0.2，d20.7時算法的性能會大大提高。4.3自適應動態(tài)改變慣性權重4.3.1依據(jù)早熟收斂程度和適應值進行調整以上的慣性權重調整策略都是依據(jù)迭代次數(shù)的遞增而遞減

15、的，文獻20提出了一中自適應調整策略，根據(jù)群體早熟收斂程度和個體適應值的來確定慣性權重的變化。設粒子pi的適1 "應值為fi，最優(yōu)粒子的適應值是fm粒子群的平均適應值是favgfi ；將優(yōu)于favg的n i 1適應值求平均得到favg'；且定義fmf'avg。依據(jù)fj、favg'和favg將群體分為3個子群，分別進行不同的自適應操作。則其慣性權重的調整如下：（1）fi 優(yōu)于 favg'則W(t) w (w Wmin )fi 11avg1m1f avg(11)（2）fi優(yōu)于favg但次于favg，則慣性權重不變;（3） fi次于favg則w(t) 1.5

16、1k1 exp( k2(12)其中第一類子群是群體中較優(yōu)秀的粒子，已經(jīng)接近全局最優(yōu)解，賦予其較小的慣性權重,從而強化了局部搜索能力；第二類粒子為一般粒子，具有較好的全局搜索能力和局部搜索能 力，不需要改變其慣性權重； 第三類粒子為群體中較差粒子，借鑒自適應調整遺傳算法控制參數(shù)的方法對其進行調整。k1、k2為控制參數(shù)，k1用來控制w的上限（一般為大于 1的常數(shù)），k2主要用來控制上式的調節(jié)能力。當算法停止時，若粒子分布較為分散，則 較大，由上式來降低粒子的w，加強局部搜索能力，以使群體趨于收斂，若粒子分布較為聚集，則較小，由上式增加粒子的w，使粒子具有較強的探查能力，從而有效地跳出局部最優(yōu)。4.

17、3.2根據(jù)距全局最優(yōu)點的距離進行調整國內(nèi)一些學者認為慣性權重的大小還應該和其距全局最優(yōu)點的距離有關。文獻21 中提出各不同粒子的慣性權重w的值不僅隨迭代次數(shù)的增加而遞減，并且應該隨其距全局最優(yōu)點距離增加而遞增，即權重w根據(jù)粒子的位置不同而動態(tài)變化：w(t)wmax(lig lmin)(w maxwmin )t(1 max1 min )tmax(13)其中l(wèi)ig為第i個粒子到最優(yōu)粒子的距離，丨max和l min分別是預先設的最大距離和最小距離參數(shù)。根據(jù)上式，當 |ig |max 時，w Wmax ； 當 1 ig 1 min 時，WWmin ；當 1 min 1 ig lmax時，w隨著lig單

18、調遞增。仿真實驗結果表明在這種策略下算法在收斂速度和迭代次數(shù)方面 都有了改進，特別是對于多峰函數(shù)效果提高的更明顯。4.4其他的慣性權重調整策略4.4.1模糊調整w的策略Shi等認為粒子群算法搜索過程是一個非線性的復雜過程，讓w線性下降的方法不能正確的反映真實的搜索過程。因而，提出用模糊推理機來動態(tài)地調整慣性權重的技術。模糊w法的優(yōu)缺點如下：模糊推理機能預測合適的w，動態(tài)地平衡全局和局部搜索能力，大為提高了平均適應值；但是其參數(shù)比較多，增加了算法的復雜度，使得其實現(xiàn)較為困難。442隨機調整 W的策略目前的研究中，很多學者認為w應為一組隨機值，如：Eberhart7等提出一種動態(tài)慣性權重法以試圖解

19、決優(yōu)化目標變化顯著的問題，該方法令0.5 rand ()w(t)( 14)2.0能產(chǎn)生一個在0.5, 1之間的W值。通過使用函數(shù)測試性能，顯示這種策略下的粒子群算法能跟隨非靜態(tài)目標函數(shù)，比進化規(guī)劃和進化策略得到的結果精度更高，收斂速度更快8。國內(nèi)也有很多學者在這方面有所研究，提出了 W服從均勻分布、正態(tài)分布等隨機策略，使算法性能較線性遞減策略都有明顯提高。5結論綜上所述可以看出，慣性權重作為粒子群算法中的一個重要參數(shù)，是算法改進的一個重要途徑，可改進的方向和方法有很多種，已經(jīng)有很多學者經(jīng)過長期研究提出了不同的改進策略，本文通過對各種改進策略的歸納總結，分類說明了各種策略的優(yōu)缺點，為使用者提供了

20、方便。作者的進一步工作有兩個方面：1.通過仿真試驗對各種算法進行更深層次的分析對比，找出適合不同問題的最優(yōu)改進算法；2結合各種問題和各種測試函數(shù)，提出效果更優(yōu)的慣性權重調整策略。參考文獻1 J.Kennedy,R.C. Eberhart. Particle swarm optimizationA.Proceedings of the IEEEIn ternatio nal Conference on Neural Networks C. 1995:194219482 ShiYuhui,Eberhart,R.A modified particle swarm optimizerA.Proc IE

21、EE Int Confon Evolu- tio nal Computatio nC.A nchorage,1998.69-733 Kennedy J.The particle swarm Sociala adaptation knowledge A.Proc IEEE Int ConfonEvolutio nal Computatio nC .In diamapolis,1997.303-3084 J.Ke nn edy,R.C.Eberhart.ADiscrete Bi nary Versio n of the Particle Swarm Algorithm.Proceedings of

22、 the World Multi conference on Systemic, Cybernetics and Informatics C. Piscataway, NJ: IEEE Service Ce nter, 1997:4104410Kennedy J,EberhartRC.Particle Swarm Optimization C.Proc IEEE Int Conf Neural Networks P iscataway,NJ:IEEEServiceCe nter,1995:1942-19486 Y . H. Shi, R. C. Fuzzy Adaptive Particle

23、Swarm Optimization A. Proceedings of the Congresson Evoluti on ary Computatio n C. Seoul, Korea, 2001:1011067 R. C. Eberhart,. H. Shi. Tracking and Optimizing Dynamic Systems with Particle Swarms A.Proceedings of the 2001 Congress on Evolutionary Computation C. Piscataway, NJ: IEEEPress, 2001:941008

24、 Van den Bergh F. An Analysis of Particle Swarm Optimizer D. South Africa: Department ofComputer Science, University of Pretoria,20029 Y. H. Shi,R. C. Eberhart. Empirical Study of Particle Swarm Optimization A. Proceeding ofCongress on Evolutionary Computation C. Piscataway,NJ:IEEE Service Center, 1

25、999:1945194910 Elegbede C.Structural reliability assessment based on particles swarm optimizationJ Structural Safety2005.27(10)1 171-18611 Robinson J,Rahmat-Samii Y Particle swarm optimization in electromagneticJ IEEE Transactions on Antennas and Propagation,2004,52(2):397 40612 Salman A。 Ahmad I,A1

26、 一 Madani S Particle swarm optimization for task assignmentproblem FJ Microprocessors and Microsystems, 2002,26 (8):363 37113 謝曉鋒，張文俊，楊之廉 . 微粒群算法綜述 J. 控制與決策 . 2003，18(2):129)13314 胡建秀 曾建潮 . 微粒群算法中慣性權重的調整策略 J. 計算機工程 , 2007.615 肖人彬，陶振武 .群體智能研究進展 J. 管理科學學報 , 200716 崔紅梅，朱慶保 .微粒群算法的參數(shù)選擇及收斂性分析 J. 計算機工程與應用

27、 , 200717 曾建潮，崔志華.一種保證全局收斂的PSO算法J.計算機研究與發(fā)展，2004, ( 8):1333133818 王麗，王曉凱 .一種非線性改變慣性權重的粒子群算法 J. 計算機工程與應用 ，2007.4319 李會榮，高岳林，李濟民 . 一種非線性遞減慣性權重策略的粒子群優(yōu)化算法 J. 商洛學院學報 2007.1220 韓江洪，李正榮，魏振春 . 一種自適應粒子群優(yōu)化算法及其仿真研究 J. 系統(tǒng)仿真學報， 2006.1021 劉建華，樊曉平 . 一種慣性權重動態(tài)調整的新型粒子群算法 J. 計算機工程與應用，2007.43( 7)22 胡建秀，曾建潮.具有隨機慣性權重的PSO算

28、法J.計算機仿真，2006.823 郭文忠. 粒子群優(yōu)化算法中慣性調整的一種新策略 J. 計算機工程與科學 ，2007.1024 王伯成，施錦丹，王凱 . 粒子群優(yōu)化算法的研究現(xiàn)狀與發(fā)展概述 J. 電視技術 ，2008.525 唐岑琦， 周有人 . 具有綜合學習機制的粒子群算法 J. 計算機工程與應用 ， 2007， 43(31)26 陳貴敏 . 粒子群優(yōu)化算法的慣性權值遞減策略研究 J. 西安交通大學學報 ，2006.27 王啟付，王戰(zhàn)江 .一種改變慣性權重的粒子群優(yōu)化算法 J. 中國機械工程 ，2005.16(11)28 王俊偉，汪定偉 .粒子群算法中慣性權重的實驗與分析 J. 系統(tǒng)工程學報 ， 2005.20(2) :194-19829 張選平，杜玉平 .秦國強，覃征 .一種動態(tài)改變慣性權重的自適應粒子群算法 J. 西安交通大學學報 ， 2005.1030 張麗平，俞歡軍.粒子群優(yōu)化算法的分析與改進 J. 信息與控制 ，2004.33(5) :513-51731 張振宇.粒子群優(yōu)化算法及其在電力系統(tǒng)優(yōu)化運行中的應用D.天津：天津大學，200732 李丹,高立群 .電力系統(tǒng)機組組合問題的動態(tài)雙種群粒子群算法 J. 計算機應用 , 200833