PSO算法中學習因子的非線性異步策略研究

馮 浩，李現偉

(1.宿州學院機械與電子工程學院，安徽宿州 234000;2.早稻田大學 國際情報通信研究科，東京169－8050）

1 引言

粒子群優化(Particle Swarm Optimization，簡稱PSO）算法是由Kennedy和Eberhart兩位博士于1995年提出［1］，是一種群智能演化計算技術，主要是模擬鳥群在尋找食物過程中的遷移和聚集。與早期的智能算法相比，PSO算法具有實現簡單、搜索速度快以及優化能力強等優點，被廣泛應用于人工智能、神經網絡、模糊系統控制以及工程優化設計等領域［2］。目前，研究人員更多是針對PSO算法的理論研究、工程應用以及算法融合等方向進行研究。

本文在上述改進算法的基礎上，提出一種學習因子的非線性異步變化策略，通過在搜索過程中對學習因子進行異步動態調節，提升算法的全局尋優能力，提高算法收斂精度。

2 標準粒子群優化(PSO）算法

在標準PSO算法(簡稱s－PSO算法）中，優化問題的解表示搜索空間中的一個粒子，所有粒子所組成的種群N都是在一個D維空間中進行搜索，單個粒子i通過適應度函數判斷自身當前位置的好壞，粒子 i的位置為 xi=(xi1，xi2，…，xid）T，同時，粒子i在搜索空間中具有一定的飛行速度，其飛行速度為 vi=(vi1，vi2，…，vid）T，粒子通過自身以及其他粒子的飛行經驗進行速度調整;經過一次次迭代，粒子i通過兩個極值更新自身速度和位置，一是粒子個體經歷過的最優位置pi=(pi1，pi2，…，pid）T，另一個是整個粒子群所經歷的最優位置 pg=(pg1，pg2，…，pgd）T，速度及位置的更新公式如下［3］:

在式(1）中，w為慣性權重，用于平衡算法的局部和全局搜索能力，一般在［0.4，0.9］范圍內取值;c1、c2是學習因子，主要反映粒子的個體最優以及全局最優對后期狀態的影響;r1和r2為0和1之間相互獨立且均勻分布的隨機數;k表示粒子當前迭代次數;種群中的每個粒子通過相互合作和信息共享來搜索最優解。

3 算法改進策略

3.1 學習因子的非線性異步變化策略

在速度更新公式中，第一部分為粒子i在第k次迭代中第d維的速度;第二部分為“自我認知”部分，表示粒子在搜索過程中不斷向自身歷史最優和全局最優學習演進;第三部分為“社會經驗”部分，表示各個粒子之間的相互合作和信息共享［4］。其中，c1直接影響粒子的認知能力，c2直接影響粒子的群體協作和信息共享能力，若c1=0，表示粒子沒有認知能力，受到“社會經驗”影響，收斂速度加快，導致算法陷入局部最優;若c2=0，表示粒子沒有社會經驗，無法進行相互協作與信息共享，使得算法收斂精度降低。在標準PSO算法中，一般取學習因子c1=c2=2。大量實驗證明該算法在搜索初期收斂速度快，極易陷入局部極值，產生早熟收斂現象。根據PSO算法的收斂性分析，學習因子需在限定范圍內取值，算法才能夠收斂。因此選擇合適的學習因子直接關系到算法的全局尋優能力。

大量研究人員對PSO算法中的學習因子調節進行改進優化，任偉建等人在文獻［5］中提出一種動態改變學習因子的簡化粒子群算法(簡稱r－PSO算法），毛開富等人在文獻［6］中提出基于非對稱學習因子調節的粒子群優化算法(簡稱m－PSO算法），以及趙遠東等人在文獻［7］中提出帶有權重函數學習因子的PSO算法。上述文獻均證明，固定學習因子不能滿足實際優化問題的非線性要求。在此基礎上，本文構造了學習因子的非線性異步變化策略模型，使學習因子在算法迭代過程中進行動態調節，即在算法搜索初期，設置較大的c1值以及較小的c2值，在削弱粒子社會經驗的同時增強粒子的自我認知，從而增加種群多樣性;算法后期，c1隨迭代次數的增加呈非線性遞減，而c2呈非線性異步遞增，逐步增強算法的全局尋優能力。具體公式如下所示:

結合PSO算法的收斂性分析［8］，當慣性權重w從數值1到0.4進行線性遞減時，學習因子c=c1r1+c2r2的變化范圍為(0，4）。即有:0＜c1+c2＜4。在迭代過程中，時變學習因子c1(k）進行非線性遞減，而c2(k）進行非線性遞增。可知，若使得算法收斂，時變學習因子的上下限須滿足如下條件:

實驗證明，通過對學習因子上下限進行隨機變化，可提升算法的收斂精度，當學習因子上下限在2＜ 2.5以及0.2＜ 0.8范圍內隨機變化時，算法可以達到更高的收斂精度。

3.2 算法實現流程

本文將改進后的粒子群優化算法簡稱為NAA－PSO算法。該算法的具體實現步驟如下［9］:

步驟1對種群中每個粒子的位置和速度進行初始化，設定學習因子c1(k）的起始上限和終止下限，以及c2(k）的起始下限和終止上限。

步驟2計算種群中每個粒子的適應度函數值，更新個體最優和全局最優。

步驟3將種群中每個粒子當前位置的適應度函數值與個體最優適應度函數值進行比較，若更好，則進行更新。

步驟4將個體最優位置對應的適應度函數值與種群最優位置的適應度函數值進行比較，若更好，則進行更新。

步驟5根據式(3）、式(4）和式(5）生成時變學習因子c1(k）、c2(k），利用式(1）和式(2）對粒子的速度和位置進行更新。

步驟6判斷是否滿足結束條件，若達到最大迭代次數，算法結束并輸出全局最優值。否則，繼續迭代。

4 實驗分析

本文利用三個基準測試函數對改進算法的有效性進行測試，同時與標準PSO算法(s－PSO算法）、文獻［5］所提出的r－PSO算法以及文獻［6］中提出的m－PSO算法進行比較。三個基準測試函數分別為 Sphere函數、Ackley函數和Rastrigin函數。其中，Sphere函數為單峰函數，在xi=0時取得全局極值0;Ackley函數和Rastrigin函數均為多峰函數，兩個函數在搜索空間中含有大量局部極值，且均在xi=0時取得全局極值0。

(1）Sphere函數

(3）Rastrigin函數

三種基準函數的參數設置及期望值見表1。

表1 基準函數參數設置

在實驗中，種群規模N=30，最大迭代次數為1500;四種算法中的慣性權值w均選擇線性遞減策略，其中 wmax=0.9，wmin=0.4;在本文所設計的NAA－PSO算法中，設定時變學習因子上下限隨機取值大小為，，調節參數;活力釋放因子根據不同基準測試函數進行相應設置。實驗次數為50。具體實驗結果見表2所示。

表2 四種算法測試結果比較

可以看出，對于單峰函數Sphere函數，NAA－PSO算法的平均解、最優解以及成功率(達到期望值的百分比）遠遠優于其他三種算法，其收斂精度也優于對比算法。

對于連續型多峰函數 Ackley函數，NAAPSO算法在各個指標上均優于其他三種算法，成功率更高。

而對于含有大量局部極值點的多峰函數Rastrigin函數，NAA－PSO算法的平均解以及收斂精度也要優于其他三種算法。這也證明本文所設計的NAA－PSO算法具有跳出局部極值進行全局搜索的能力。

圖1、圖2和圖3分別給出了各基準函數中四種算法的平均最優適應度函數值收斂曲線。可以看出，s－PSO算法在迭代初期的收斂速度較快，但很快陷入局部極值;r－PSO算法的收斂精度高于s－PSO算法，但在收斂速度指標上略遜于s－PSO算法;m－PSO算法在收斂精度方面優于s－PSO算法和r－PSO算法，但其收斂速度表現一般，略遜于其他三種算法;而本文所設計的NAA－PSO算法在迭代初期具有較快的收斂速度，同時能夠跳出局部最小，表現出較強的全局尋優能力。

實驗證明，NAA－PSO算法在處理單峰和多峰函數的優化問題上明顯優于其他三種算法，在保證收斂速度的同時，可獲得更高的收斂精度。

5 結束語

針對PSO算法中學習因子的關鍵性作用，提出了一種學習因子的非線性異步變化策略，該算法使學習因子隨迭代過程進行異步動態調節，從而更好地平衡算法的局部和全局尋優性能。實驗仿真結果表明，該算法在收斂精度指標上均優于對比算法，可以較好地避免算法陷入局部最優，全局尋優能力突出。

［1］Kennedy J ，Eberhart R.Particle swarm optimization［C］//Proceedings of the 4th IEEE International Conference on Neural Networks.Piscataway，NJ:IEEE Service Center，1995:1942 －1948.

［2］Vanden Bergh F，Engelbrecht A P.Training Product Unit Networks Using Cooperative Particle Swarm Optimization［C］.IEEE International Joint Conference on Neural Networks，Washington DC，USA，2001:126 －131.

［3］Shi Y，Eberhart R.Empirical study of particle swarm optimization［C］//Proceedings of the IEEE Congress on Evolutionary Computation，Piscataway，NJ:IEEE press，1999:1945－1950.

［4］Clerc M.The swarm and the queen:towards a determinstic and adaptive particle swarm optimization［C］//Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway，NJ:IEEE Service Center，1999:1951 －1957.

［5］任偉建，武璇.一種動態改變學習因子的簡化粒子群算法［J］.自動化技術與應用，2012(10）:9 －11，37.

［6］毛開富，包廣清，徐馳.基于非對稱學習因子調節的粒子群優化算法［J］.計算機工程，2010，36(19）:182－184.

［7］趙遠東，方正華.帶有權重函數學習因子的粒子群算法［J］.計算機應用，2013，33(8）:2265－2268.

［8］張慧斌，王鴻斌，胡志軍.基于定常線性迭代法的PSO算法收斂性分析［J］.計算機工程與應用，2011，47(31）:35－37.

［9］姜長元，趙曙光，沈士根等.慣性權重正弦調整的粒子群算法［J］.計算機工程與應用，2012，48(8）:40 －42.