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

馮 浩，李現(xiàn)偉

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

1 引言

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

本文在上述改進算法的基礎(chǔ)上，提出一種學習因子的非線性異步變化策略，通過在搜索過程中對學習因子進行異步動態(tài)調(diào)節(jié)，提升算法的全局尋優(yōu)能力，提高算法收斂精度。

2 標準粒子群優(yōu)化(PSO）算法

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

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

3 算法改進策略

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

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

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

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

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

3.2 算法實現(xiàn)流程

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

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

步驟2計算種群中每個粒子的適應(yīng)度函數(shù)值，更新個體最優(yōu)和全局最優(yōu)。

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

步驟4將個體最優(yōu)位置對應(yīng)的適應(yīng)度函數(shù)值與種群最優(yōu)位置的適應(yīng)度函數(shù)值進行比較，若更好，則進行更新。

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

步驟6判斷是否滿足結(jié)束條件，若達到最大迭代次數(shù)，算法結(jié)束并輸出全局最優(yōu)值。否則，繼續(xù)迭代。

4 實驗分析

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

(1）Sphere函數(shù)

(3）Rastrigin函數(shù)

三種基準函數(shù)的參數(shù)設(shè)置及期望值見表1。

表1 基準函數(shù)參數(shù)設(shè)置

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

表2 四種算法測試結(jié)果比較

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

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

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

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

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

5 結(jié)束語

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

［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］任偉建，武璇.一種動態(tài)改變學習因子的簡化粒子群算法［J］.自動化技術(shù)與應(yīng)用，2012(10）:9 －11，37.

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

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

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

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