一種帶有二維擾動和自適應學習因子的粒子群算法

王 磊，王行甫，苗付友，

(中國科學技術大學 計算機科學與技術學院， 合肥 230027)

1 引 言

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

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

2 PSO算法

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

在D維空間中，初始時PSO有一群大小為N的隨機粒子，其中第i個粒子的位置為xi=(xi1,xi2,…,xiD)，速度為vi=(vi1,vi2,…,viD)，然后每個粒子通過兩個最優(yōu)位置來更新自己的速度和位置，一個是自己的歷史最優(yōu)位置pbesti=(pbesti1,pbesti2,…,pbestiD)，另一個是所有粒子的歷史最優(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為當前迭代次數；w為慣性權重；c1和c2分別為認知系數和社會系數(學習因子)，其作用是使粒子具有自我總結和向群體中優(yōu)秀粒子學習的能力，向兩個歷史最優(yōu)位置學習；r1和r2為0～1間的隨機數；為了防止粒子沖出搜索空間并獲得較好的效果，粒子位置限制在[xmin,xmax]范圍內，速度限制在[vmin,vmax]范圍內.

3 TDDALFPSO算法

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

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

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

針對這些問題本文提出了TDDALFPSO，并從三個方面進行改進：

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

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

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

3.1 自適應慣性權重和學習因子調節(jié)算法

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

基于上述思想本文提出了一種自適應慣性權重和學習因子調節(jié)算法：

(3)

(4)

(5)

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

(6)

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

(7)

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

(8)

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

(9)

(10)

對式(3)求導獲得式(9)，因為β>1，所以α′<0，所以公式(3)是一個單調遞減函數.再對式(9)求導獲得式(10)，因為α″>0，所以式(9)單調遞增，導致|α′|單調遞減，證明式(3)變化速率越來越慢，得證.

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

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

3.2 基于位置、速度的二維擾動更新位置

因為PSO算法尋求最優(yōu)值的時候，所有的粒子都會向全局歷史最優(yōu)值學習，在每次迭代過程中通過簡單的對上一次迭代時的位置和當前迭代的速度進行求和來更新每個粒子的位置，如果全局歷史最優(yōu)值離種群最優(yōu)值所在區(qū)域比較遠的話，那么所有粒子就會向錯誤的方向學習，從而導致算法容易陷入局部最優(yōu).文獻[8]引入具有周期振蕩性的正弦函數因子，使得在每次迭代中每個粒子位置獲得周期性振蕩，擴大搜索空間，避免算法陷入局部最優(yōu)，更新速度函數如下：

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

(11)

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

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

(12)

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

3.3 隨機變異增加粒子群的多樣性

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

3.4 DDALFPSO算法流程

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

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

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

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

4)選取一些適應度值最差的粒子進行隨機的變異；

5)如果評估次數達到最大評估次數或者精度達到目標要求則輸出最優(yōu)適應度值和對應的位置；否則，轉向第3步，進入下一次尋優(yōu).

4 試驗與結果分析

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

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

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

4.2 測試函數

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

4.3 參數設置

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

表1 5個經典的測試函數

4.4 試驗結果分析和比較

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

表2 不同PSO改進算法性能比較

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

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

5 結 論

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

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