一種帶有二維擾動(dòng)和自適應(yīng)學(xué)習(xí)因子的粒子群算法

王 磊，王行甫，苗付友，

(中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 合肥 230027)

1 引 言

粒子群算法(Particle Swarm Optimization，PSO)是1995年由Kennedy等人[1]提出的一種模擬鳥類覓食行為過程的隨機(jī)智能優(yōu)化算法，該算法結(jié)構(gòu)簡單，運(yùn)行速度快且所調(diào)整的參數(shù)少，被廣泛地應(yīng)用于函數(shù)優(yōu)化和工程實(shí)踐等諸多領(lǐng)域，已經(jīng)成為一種重要的優(yōu)化工具.但由于基本PSO算法在優(yōu)化復(fù)雜的多峰問題時(shí)存在收斂速度慢、容易陷入局部最優(yōu)等問題，使得基本PSO算法在實(shí)際應(yīng)用中受到限制.在近幾年的研究中，許多關(guān)于PSO算法的改進(jìn)和應(yīng)用逐步涌現(xiàn).文獻(xiàn)[2]提出了一種慣性權(quán)重線性遞減的PSO算法.文獻(xiàn)[3]引入模糊方法非線性的調(diào)整慣性權(quán)重.文獻(xiàn)[4]根據(jù)適應(yīng)度值距離比優(yōu)化了PSO算法，改善了算法容易陷入早熟的問題.文獻(xiàn)[5]使用其他粒子的最優(yōu)歷史信息更新粒子的速度，在避免陷入早熟上具有很好的效果.文獻(xiàn)[6]在更新慣性權(quán)重時(shí)引入了貝葉斯定理論.文獻(xiàn)[7]提出了一種基于三角函數(shù)的動(dòng)態(tài)參數(shù)選擇的PSO算法，提高了算法的收斂速度和魯棒性.文獻(xiàn)[8]引入具有周期振蕩性的正弦函數(shù)因子，使得每個(gè)粒子位置獲得周期性振蕩，擴(kuò)大了搜索空間，避免了算法陷入早熟.這些算法對于PSO算法性能的提高有比較好的改善，但大部分算法在后期存在收斂速度慢、容易陷入局部最優(yōu)以及精度不足的問題，特別是在復(fù)雜的高峰多維函數(shù)問題上尤其明顯.

為了解決這些問題，本文提出了一種帶有二維擾動(dòng)和自適應(yīng)學(xué)習(xí)因子的粒子群算法(Particle Swarm Optimization algorithm with Two Dimensional Disturbance and Adaptive Learning Factor，TDDALFPSO).

2 PSO算法

PSO算法是從鳥類覓食過程得到啟發(fā)而提出的一種優(yōu)化方法，在算法中每個(gè)優(yōu)化問題的解對應(yīng)搜索空間的一個(gè)粒子，每個(gè)粒子具有一定的速度來決定其運(yùn)動(dòng)的距離和方向.每個(gè)粒子通過被優(yōu)化的函數(shù)計(jì)算其適應(yīng)度值.整個(gè)問題優(yōu)化過程就是通過粒子尋找在搜索空間中滿足問題需求并具有最優(yōu)適應(yīng)度值對應(yīng)的空間位置.

在D維空間中，初始時(shí)PSO有一群大小為N的隨機(jī)粒子，其中第i個(gè)粒子的位置為xi=(xi1,xi2,…,xiD)，速度為vi=(vi1,vi2,…,viD)，然后每個(gè)粒子通過兩個(gè)最優(yōu)位置來更新自己的速度和位置，一個(gè)是自己的歷史最優(yōu)位置pbesti=(pbesti1,pbesti2,…,pbestiD)，另一個(gè)是所有粒子的歷史最優(yōu)位置gbestd=(gbestd1,gbestd2,…,gbestdD)，具體公式如下：

vi(t+1)=wvi(t)+c1r1(pbcsti-xi(t))+
c2r2(gbestd-xi(t))

(1)

xi(t+1)=vi(t+1)+xi(t)

(2)

公式中t為當(dāng)前迭代次數(shù)；w為慣性權(quán)重；c1和c2分別為認(rèn)知系數(shù)和社會(huì)系數(shù)(學(xué)習(xí)因子)，其作用是使粒子具有自我總結(jié)和向群體中優(yōu)秀粒子學(xué)習(xí)的能力，向兩個(gè)歷史最優(yōu)位置學(xué)習(xí)；r1和r2為0～1間的隨機(jī)數(shù)；為了防止粒子沖出搜索空間并獲得較好的效果，粒子位置限制在[xmin,xmax]范圍內(nèi)，速度限制在[vmin,vmax]范圍內(nèi).

3 TDDALFPSO算法

PSO算法之所以會(huì)有收斂速度慢、容易陷入局部最優(yōu)等問題主要原因有兩個(gè)：

1)算法無法很好地平衡全局搜索能力和局部搜索能力；

2)搜索過程中粒子需要通過自身歷史最優(yōu)位置和全局歷史最優(yōu)位置來調(diào)整自己，隨著搜索的深入，粒子群的多樣性會(huì)減少，另外如果全局歷史最優(yōu)位置離真正的最優(yōu)位置很遠(yuǎn)的話，算法很容易陷入局部最優(yōu)；

針對這些問題本文提出了TDDALFPSO，并從三個(gè)方面進(jìn)行改進(jìn)：

1)為了平衡好全局搜索能力和局部搜索能力，提高算法的效果，本文提出了一種自適應(yīng)調(diào)節(jié)慣性權(quán)重和學(xué)習(xí)因子的算法來調(diào)節(jié)式(1)中的慣性權(quán)重w和學(xué)習(xí)因子c1、c2；

2)為了避免離種群最優(yōu)位置較遠(yuǎn)的全局歷史最優(yōu)位置對搜索的影響，本文提出了一種基于位置、速度二維擾動(dòng)的算法來更新粒子的位置；

3)為了增加粒子群的多樣性，在每次迭代過程中變異一些適應(yīng)度值比較差的粒子，讓它們來搜索空間的其他領(lǐng)域.

3.1 自適應(yīng)慣性權(quán)重和學(xué)習(xí)因子調(diào)節(jié)算法

為了獲得更好的效果，PSO算法需要平衡好全局搜索能力和局部搜索能力.在迭代初期，慣性權(quán)重w應(yīng)該具有更快的下降速度，增加粒子更新的步長，使得群體能夠較快的搜索到可行解區(qū)域；在迭代后期，慣性權(quán)重w應(yīng)該具有較慢的下降速度，減小粒子更新速度的步長，使得粒子群在可行解區(qū)域里微調(diào)搜索到全局最優(yōu)解；并且在迭代的初期，群體應(yīng)該具有比較強(qiáng)的自我學(xué)習(xí)能力，隨著迭代的繼續(xù)，自我的學(xué)習(xí)能力應(yīng)該減弱，社會(huì)學(xué)習(xí)能力不斷的增加.

基于上述思想本文提出了一種自適應(yīng)慣性權(quán)重和學(xué)習(xí)因子調(diào)節(jié)算法：

(3)

(4)

(5)

w(t)=wmin+α(wmax-wmin)

(6)

c1(t)=c1max-α(c1max-c1min)

(7)

c2(t)=c2min+α(c2max-c2min)

(8)

式(3)中x表示算法進(jìn)度，被映射到0～1，0表示算法開始，大于等于1表示算法結(jié)束，β是控制參數(shù)，用來控制收斂速度β>1.因?yàn)門DDALFPSO算法的運(yùn)行分為能夠確定的最大適應(yīng)度評估次數(shù)和沒法確定兩種情況，所以進(jìn)度x的計(jì)算需要分開討論，公式(4)用來計(jì)算能夠確定最大適應(yīng)度評估次數(shù)時(shí)算法的進(jìn)度，其中t是當(dāng)前迭代次數(shù)，T是全部的評估次數(shù).公式(5)用來計(jì)算無法確定最大適應(yīng)度評估次數(shù)時(shí)算法的進(jìn)度，其中δ表示算法要達(dá)到的精度，fitnessi和fitnessi+1分別代表第i、i+1次迭代中獲得的全局歷史最優(yōu)值.式(6)中wmax和wmax分別為慣性權(quán)重的上下界，根據(jù)文獻(xiàn)[2]分別為1.2和0.9.式(7)中,c1max和c1min是認(rèn)知系數(shù)的上下界，根據(jù)文獻(xiàn)[9]分別設(shè)置為2.5和0.1.式(8)中c2max和c2min是社會(huì)系數(shù)的上下界，根據(jù)文獻(xiàn)[9]分別設(shè)置為3.2和0.8.式(6)和式(8)是一個(gè)變化速率先快后慢的單調(diào)遞減函數(shù)，式(7)是一個(gè)變化速率先快后慢的單調(diào)遞增函數(shù).要想證明式(6)、式(8)是一個(gè)單調(diào)遞減函數(shù)，式(7)是一個(gè)單調(diào)遞增函數(shù)，并且速率是越來越慢，只需要證明式(3)是一個(gè)單調(diào)遞減函數(shù)，并且速率越來越慢就可以了，下面給出證明：

(9)

(10)

對式(3)求導(dǎo)獲得式(9)，因?yàn)棣?1，所以α′<0，所以公式(3)是一個(gè)單調(diào)遞減函數(shù).再對式(9)求導(dǎo)獲得式(10)，因?yàn)棣痢?0，所以式(9)單調(diào)遞增，導(dǎo)致|α′|單調(diào)遞減，證明式(3)變化速率越來越慢，得證.

通過圖1可以發(fā)現(xiàn)β對式(3)的變化曲線有著重要的影響，β越大式(3)前期的下降速度越快，后期下降速度越慢.因?yàn)槭?3)的變化速度影響著c1和c2的變化，所以β對于PSO自我學(xué)習(xí)能力和社會(huì)學(xué)習(xí)能力有著重要的作用.在PSO學(xué)習(xí)的過程中我們希望算法在前期能夠具有較好的自我學(xué)習(xí)能力，后期能夠具有較好社會(huì)學(xué)習(xí)能力，通過圖1可以發(fā)現(xiàn)β為10能夠比較好的滿足這個(gè)需求，當(dāng)β小于10的時(shí)候前期的變化速度比較慢，當(dāng)β大于10的時(shí)候，前期的變化速度又太快，所以在下面的實(shí)驗(yàn)中將β設(shè)置為10.

圖1 不同β值下公式(3)的變化曲線

3.2 基于位置、速度的二維擾動(dòng)更新位置

因?yàn)镻SO算法尋求最優(yōu)值的時(shí)候，所有的粒子都會(huì)向全局歷史最優(yōu)值學(xué)習(xí)，在每次迭代過程中通過簡單的對上一次迭代時(shí)的位置和當(dāng)前迭代的速度進(jìn)行求和來更新每個(gè)粒子的位置，如果全局歷史最優(yōu)值離種群最優(yōu)值所在區(qū)域比較遠(yuǎn)的話，那么所有粒子就會(huì)向錯(cuò)誤的方向?qū)W習(xí)，從而導(dǎo)致算法容易陷入局部最優(yōu).文獻(xiàn)[8]引入具有周期振蕩性的正弦函數(shù)因子，使得在每次迭代中每個(gè)粒子位置獲得周期性振蕩，擴(kuò)大搜索空間，避免算法陷入局部最優(yōu)，更新速度函數(shù)如下：

xi(t+1)=x1(t)(1-sin(h))+vi(t+1)sin(h)

(11)

但是這個(gè)方法有兩個(gè)缺點(diǎn)：第一，如果全局歷史最優(yōu)解已經(jīng)在最優(yōu)解附近的話，擾動(dòng)反而會(huì)導(dǎo)致搜索偏離最優(yōu)解；第二，式(11)第一項(xiàng)xi(t)(1-sin(h))的范圍在0和2xi(t)，振蕩后的位置可能和原來位置較遠(yuǎn).對于第一個(gè)問題，可以通過限定粒子振蕩的條件來解決，只有被判定陷入早熟的粒子才進(jìn)行振蕩.為了判斷粒子是否陷入早熟，引入一個(gè)精度ε，如果連續(xù)多次迭代中，鄰近兩次粒子歷史最優(yōu)值的差都小于ε，則判斷該粒子陷入早熟，然后對粒子進(jìn)行振蕩.對于次數(shù)的選擇，需要根據(jù)具體的問題來決定，在后面的實(shí)驗(yàn)中，通過將次數(shù)分別設(shè)置10、20、30、40和50進(jìn)行對比，發(fā)現(xiàn)將其設(shè)定為20效果最好.對于第二個(gè)問題，可以通過限制粒子的振動(dòng)幅度來解決.另外雖然粒子已經(jīng)陷入了早熟，但是一般陷入早熟的粒子的位置在一些維度上是靠近全局最優(yōu)解的，為了利用這些維度的優(yōu)勢，本文對粒子位置的每個(gè)維度進(jìn)行一定幅度的振蕩，同時(shí)為了避免粒子在振蕩幅度過大，導(dǎo)致大幅度偏離原來的位置，將振蕩的幅度限制在20%內(nèi).通過上面的想法對公式(2)進(jìn)行改造：

xij(t+1)=r1vij(t+1)+(1-0.2r2)xij(t)

(12)

式(12)中xij(t)和xij(t+1)分別表示第t次、t+1次迭代過程中第i個(gè)粒子位置的第j維，vij(t+1)表示第t+1次迭代過程中第i個(gè)粒子速度的第j維，r1和r2都是在-1～1范圍內(nèi)的隨機(jī)值.

3.3 隨機(jī)變異增加粒子群的多樣性

由于在PSO算法中，所有的粒子都要向全局歷史最優(yōu)值學(xué)習(xí)，從而導(dǎo)致算法在迭代的過程中粒子群的多樣性會(huì)越來越低.為了優(yōu)化這個(gè)問題，在每次迭代中選取一定數(shù)量適應(yīng)度值最差的粒子進(jìn)行隨機(jī)變異，這樣一方面可以增加粒子群的多樣性，另一個(gè)方面可以讓粒子群搜索更多的區(qū)域.對于選取多少粒子進(jìn)行變異，需要針對不同的問題進(jìn)行設(shè)置，如果選取的太多將會(huì)影響算法的性能，如果選取的太少無法很好的增加粒子的多樣性，根據(jù)2/8原則，在后面的實(shí)驗(yàn)中我們將這個(gè)值設(shè)置為粒子群數(shù)量的20%.

3.4 DDALFPSO算法流程

基于上面的理論和改進(jìn)方法，本文提出的TDDALFPSO算法的基本流程如下:

1)設(shè)置PSO算法中的各個(gè)參數(shù)，初始化粒子的位置和速度，并求出每個(gè)粒子的歷史最優(yōu)值pbesti和全局歷史最優(yōu)值gbestd；

2)首先通過式(1)、(3)～(8)更新粒子速度，然后判斷當(dāng)前粒子是否陷入早熟，如果陷入早熟用式(12)更新位置，否者通過式(2)更新位置.最后計(jì)算每個(gè)粒子當(dāng)前的適應(yīng)度值；

3)更新每個(gè)粒子歷史最優(yōu)位置和群體歷史最優(yōu)位置；

4)選取一些適應(yīng)度值最差的粒子進(jìn)行隨機(jī)的變異；

5)如果評估次數(shù)達(dá)到最大評估次數(shù)或者精度達(dá)到目標(biāo)要求則輸出最優(yōu)適應(yīng)度值和對應(yīng)的位置；否則，轉(zhuǎn)向第3步，進(jìn)入下一次尋優(yōu).

4 試驗(yàn)與結(jié)果分析

為了驗(yàn)證TDDALFPSO算法的性能，本文設(shè)計(jì)了TDDALFPSO算法和其他6個(gè)PSO算法的性能對比實(shí)驗(yàn)，其中包括1個(gè)基本PSO算法和5個(gè)已經(jīng)優(yōu)化了的PSO算法.

4.1 5個(gè)優(yōu)化的PSO算法

5個(gè)優(yōu)化的PSO算法分別為：文獻(xiàn)[2]提出的一種線性的慣性權(quán)重線性遞減的PSO算法(PSO-W)，文獻(xiàn)[4]提出一種基于適應(yīng)值距離比例的PSO算法(FDR-PSO)，文獻(xiàn)[5]提出的一種基于綜合學(xué)習(xí)PSO算法(CLPSO)，文獻(xiàn)[7]提出的基于三角函數(shù)的動(dòng)態(tài)參數(shù)選擇的PSO算法(TPSO)，文獻(xiàn)[8]提出的一種帶正弦函數(shù)因子的粒子群優(yōu)化算法(TFPSO).

4.2 測試函數(shù)

為了測試算法的尋優(yōu)性，本文選取了5個(gè)經(jīng)典的函數(shù)進(jìn)行測試.每一個(gè)函數(shù)都有自己的特征，如無峰性，單峰性、多維性和凹凸性等，根據(jù)這些特征本文將5個(gè)測試函數(shù)分為兩類：第一類，單峰函數(shù)(F1、F2)；第二類，多峰函數(shù)(F3、F4和F5).5個(gè)函數(shù)都是尋求極小化問題，每個(gè)函數(shù)的形式、維數(shù)、搜索空間、理論極值和函數(shù)峰值特征如表1所示.

4.3 參數(shù)設(shè)置

基本PSO算法的參數(shù)設(shè)置和文獻(xiàn)[1]一致；其他5個(gè)PSO算法的參數(shù)和對應(yīng)論文中的設(shè)置一致；通過文中的討論對TDDALFSO算法中的參數(shù)速度上限vmax設(shè)為空間上限的10%，速度下限vmin設(shè)置為空間的10%，式(3)中β的設(shè)為10，每次迭代過程中粒子變異數(shù)目設(shè)置為種群規(guī)模的20%，根據(jù)文獻(xiàn)[2]將慣性權(quán)重上限wmax設(shè)為1.2、下限wmin設(shè)為0.9，根據(jù)文獻(xiàn)[9]認(rèn)知系數(shù)上c1max限設(shè)為2.5、下限c1min設(shè)為0.1，社會(huì)系數(shù)上限c2max設(shè)為3.2、下限c2min設(shè)為0.8、早熟判定精度ε為1E-3、早熟判定次數(shù)l為20.所有算法種群規(guī)模N設(shè)置為50，維度為30，最大適應(yīng)度評估次數(shù)為5000，運(yùn)行次數(shù)為30，精度閾值δ為1E-8.

表1 5個(gè)經(jīng)典的測試函數(shù)

4.4 試驗(yàn)結(jié)果分析和比較

為了盡量避免因隨機(jī)操作而造成比較結(jié)果的不公平性，對表1中的5個(gè)測試函數(shù)進(jìn)行30次獨(dú)立實(shí)驗(yàn)，每次實(shí)驗(yàn)最大適應(yīng)度評估次數(shù)為5000，然后求取平均值、方差和最優(yōu)值作為測試結(jié)果，具體測試結(jié)果詳細(xì)見表2(其中黑色加粗并加下劃線的表示對應(yīng)項(xiàng)的最好結(jié)果)和圖2.從表2中可以看出TDDALFPSO在所有函數(shù)測試中的性能表現(xiàn)都要優(yōu)于基本PSO，其中對于函數(shù)F1、F4函數(shù)的均值達(dá)到了全局最優(yōu)值0，對于函數(shù)F2、F3和F5的均值相對于基本PSO分別降低了5、30和2個(gè)數(shù)量級(jí)，且對于所有的函數(shù)的標(biāo)準(zhǔn)差都要比基本PSO要小，說明TDDALFPSO能夠顯著的提高尋優(yōu)效果和穩(wěn)定性.和其他5個(gè)優(yōu)化了的PSO相比，對于函數(shù)F3和F4，TDDALFPSO的平均值、方差和最優(yōu)值顯著小于其他5個(gè)PSO算法.對于函數(shù)F1，雖然TDDALFPSO和TFPSO的均值、方差都達(dá)到了全局最優(yōu)值0，但是仍顯著的優(yōu)于其他3個(gè)PSO算法.對于函數(shù)F2、F5，TDDALFPSO的均值、方差和最優(yōu)值都要優(yōu)于其他PSO算法，特別是對于函數(shù)F5，TDDALFPSO的最優(yōu)值和其他PSO算法相比要低7個(gè)數(shù)量級(jí)，說明對于F5，TDDALFPSO在避免陷入早熟的問題上具有更大的優(yōu)勢.由此可見TDDALFPSO和基本PSO以及其他5個(gè)優(yōu)化了的PSO算法相比它的尋優(yōu)效果和穩(wěn)定性具有極大的優(yōu)勢.

表2 不同PSO改進(jìn)算法性能比較

圖2是7個(gè)PSO算法對5個(gè)測試函數(shù)尋優(yōu)過程的曲線圖，由圖可以清楚的看出，TDDALPSO算法在5個(gè)測試函數(shù)上的收斂速度要好于其他PSO算法，特別是在函數(shù)F1(Sphere)、F4(Griewanks)和F5(Schwefel)上，TDDALPSO的最優(yōu)收斂曲線直線下降，說明和基本PSO算法以及其他5個(gè)優(yōu)化PSO相比TDDALPSO更容易跳出局部最優(yōu)值.

綜上所述，無論是在處理單峰函數(shù)還是處理多峰函數(shù)的問題上，和其他六個(gè)PSO算法相比，TDDALFPSO算法在精度、收斂速度和穩(wěn)定性上都有巨大的優(yōu)勢.

5 結(jié) 論

本文針對基本PSO算法在尋優(yōu)過程中容易陷入局部最優(yōu)值、后期收斂速度慢和收斂精度低等問題，提出了一種帶有二維擾動(dòng)和自適應(yīng)學(xué)習(xí)因子的粒子群算法(TDDALFPSO)，從三個(gè)方面對基本PSO算法進(jìn)行改進(jìn).通過與基本PSO算法其他5個(gè)已經(jīng)優(yōu)化了的PSO算法在5個(gè)經(jīng)典測試函數(shù)上進(jìn)行實(shí)驗(yàn)對比，可以看出本文提出的算法在收斂速度、精度和穩(wěn)定性方面和基本PSO算法相比有了顯著的提高，并且和其他5個(gè)PSO算法相比也有很大的優(yōu)勢，其中部分函數(shù)成功擺脫了局部最優(yōu)值的干擾，找到了全局最優(yōu)值.但是本文提出的算法仍沒有完全解決陷入早熟的問題，對于如何更加有效地跳出局部最優(yōu)仍有待近一步的解決.

圖2 函數(shù)尋優(yōu)曲線