馮 浩，李現(xiàn)偉

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

1 引言

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

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

2 標(biāo)準(zhǔn)粒子群優(yōu)化(PSO）算法

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

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

3 算法改進(jìn)策略

3.1 學(xué)習(xí)因子的非線性異步變化策略

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

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

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

實(shí)驗(yàn)證明，通過對(duì)學(xué)習(xí)因子上下限進(jìn)行隨機(jī)變化，可提升算法的收斂精度，當(dāng)學(xué)習(xí)因子上下限在2＜ 2.5以及0.2＜ 0.8范圍內(nèi)隨機(jī)變化時(shí)，算法可以達(dá)到更高的收斂精度。

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

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

(1）Sphere函數(shù)

(3）Rastrigin函數(shù)

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

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

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

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

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

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

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

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

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

5 結(jié)束語

針對(duì)PSO算法中學(xué)習(xí)因子的關(guān)鍵性作用，提出了一種學(xué)習(xí)因子的非線性異步變化策略，該算法使學(xué)習(xí)因子隨迭代過程進(jìn)行異步動(dòng)態(tài)調(diào)節(jié)，從而更好地平衡算法的局部和全局尋優(yōu)性能。實(shí)驗(yàn)仿真結(jié)果表明，該算法在收斂精度指標(biāo)上均優(yōu)于對(duì)比算法，可以較好地避免算法陷入局部最優(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］任偉建，武璇.一種動(dòng)態(tài)改變學(xué)習(xí)因子的簡化粒子群算法［J］.自動(dòng)化技術(shù)與應(yīng)用，2012(10）:9 －11，37.

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

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

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

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