總結性自適應變異的粒子群算法

陳博文，鄒 海

安徽大學 計算機科學與技術學院，合肥 230601

粒子群優化算法（particle swarm optimization，PSO）作為進化計算的一個分支，是由Eberhart和Kennedy等[1]于1995年提出的一種全局搜索算法，通過模擬動物在群體活動中所表現出來的信息共享特性完成對目標問題的求解。相關的群智能算法應用廣泛，如文獻[2]中通過改進蟻群算法解決旅行商問題，文獻[3]中使用果蠅優化算法解決圖像分割問題。PSO最早是用來優化神經網絡的網絡連接權重的，現已涉及多目標優化[4]、信號控制[5]、資源調度[6]等各個領域。

需要合理地對PSO的參數進行配置，平衡算法在迭代過程中對全局和局部的搜索能力，來優化整個收斂過程。Shi和Eberhart[7-8]分析了慣性權重對粒子搜索能力的影響，在粒子的尋優過程中，慣性權重隨著迭代次數來線性遞減，在保證廣度和精度的基礎上提高了算法的收斂性。Ao等[9]提出的自適應慣性權重的改進粒子群算法，將適應度值較差的粒子的慣性權重因子置零，充分發揮全局最優的指向性，提高了算法的收斂性。郭巳秋等[10]通過控制粒子群的數量來驗證慣性權重對整個算法收斂的影響。周蓉等[11]提出的基于灰狼優化的反向學習粒子群算法中，引入余弦函數和貝塔分布來控制慣性權重的非線性變化，再次提高了算法的搜索效率。

目前，不同的改進策略對粒子群算法在求解問題時均有不同程度的提高，但仍然存在精度不高、收斂速度慢等缺陷。針對這些問題，本文新提出一種總結性自適應變異的粒子群算法，與相關變種算法對比，證明了該策略的穩定性、有效性。

1 基本粒子群算法

在PSO算法的模型中，每個粒子都代表著搜索空間的潛在解，并有可能成為群體的最優解，他們都以一個共同的全局最優作為自己的“標桿”。每個個體粒子在進化的過程中維護兩個向量，分別為速度向量V i，位置向量X i，其中i表示粒子的編號，D是求解問題的維數。粒子的速度向量控制著其運動的方向和速率，而位置則體現了粒子所代表的解在解空間中的位置，正是通過計算適應度的值來判定該解的質量。

開始尋優過程，對每個粒子i各維的速度和位置進行更新，其公式如下：

其中，d代表當前維度，t表示當前的迭代次數，r1和r2表示[0，1]之間的隨機數，c1和c2代表學習因子，w作為速度的系數，控制了前一次迭代的速度對當前速度的影響，即慣性權重，pBest為各個粒子自身維護的歷史最優位置向量，來確保粒子不會逆向尋找最優，gBest為整個群體維護的全局最優向量。因此粒子群算法在考慮了個體的自我認知和社會信息共享的基礎上也保證了粒子的隨機性。

2 SCVPSO算法

2.1 新的慣性權重自適應函數

在PSO算法中，慣性權重代表了前一次迭代各個維度的速度對當前速度的影響，因此慣性權重w的取值在整個收斂過程中會直接作用于各個粒子的尋優能力。本文截取logistic回歸曲線[-6,6]之間的圖像通過數學變換處理，提出新的非線性慣性權重衰減策略，其關于迭代次數的關系如式（3）所示：

其中，T為最大迭代次數，t表示當前的迭代次數。wmax、wmin分別為最大慣性權重和最小慣性權重。本文wmax=0.8,wmin=0,T=1 000，繪制其變化曲線如圖1所示。相關研究表明，w小于0.8時，能以更快的速度達到全局最優值[7]。在此基礎下，本文再將慣性權重變化分為下降、上升、再下降三個部分。這滿足在迭代初期，慣性權重取最大值并逐漸下降，便于提升粒子的全局搜索能力[12]，且下降呈凹函數趨勢，保證了尋優時的收斂效率[13]；在迭代中期，慣性權重轉折上升，即各個粒子前一次迭代速度的影響增大，則擴大了問題搜索空間，方便算法發揮其尋優性能；在迭代后期，隨著迭代次數增加，慣性權重逐漸減小到最小值，最大化粒子的局部開發能力[14]。從整體來看該策略呈現遞減趨勢，平衡了在迭代時全局與局部的搜索能力，這符合文獻[15]指出的應以較大的w值進行全局搜索，以較小的w值進行局部搜索。

圖1 SCVPSO算法慣性權重曲線Fig.1 Inertia weight curve of SCVPSO

2.2 局部粒子反向搜索處理

每個粒子在尋優過程中，雖然有著全局最優粒子的引導，但由于隨機參數r1和r2的存在，難免會出現部分粒子pbest值停滯的現象，對于這種超過規定次數后仍無pbest值更新的粒子，將其認定為局部粒子。由于尋優資源的有限性，局部粒子會影響種群的搜索效率。

為改善該情況，這里自定義了一種干預策略。如圖2為示例四種情況下，局部粒子在最近3次迭代過程①②③中位置發生了變化，若pbest值無提升即出現停滯現象，說明該粒子所在局部區域未搜索到更優解，且粒子速度過于發散會導致后期收斂速度慢[16]，此時在第4次干預其尋優的方向以及大小，該速度聚合了前三次速度矢量和，幫助局部粒子更快進入有效區域，在限定迭代次數中能夠提高種群的尋優能力。擬將被干預的粒子位置更新公式如下：

圖2 SCVPSO算法反向搜索示意圖Fig.2 Reverse search of SCVPSO

其中，i(t)表示第t次迭代中的粒子，count(i(t))表示第t次迭代時的粒子個體最優值是否與前一次迭代時個體最優值相等，1表示相等，0表示不等，以此來記錄是否連續三次粒子處于被動的局部狀態；表示連續三次的個體最優值未發生變化的次數。若，則該粒子被判定為局部粒子，并對個體當前速度更新策略進行調整；取-4/3作為系數，使當前速度與前三次速度矢量和相反。由于在前三次速度更新已經融合了隨機性，為提高計算效率這里無需添加隨機因子，個體位置更新后，將其count值重新設定為0。

2.3 劣勢粒子位置總結性變異

擬對各個粒子進行自我總結性觀察，引入新的參數scr（self-conclusion rate）自我總結率，該參數為近期各個粒子的尋優情況與全局最優粒子的變化比率，根據scr的值以對算法尋優進程進行分析，對篩選出的劣勢粒子作出相關處理，從而跳出當前的劣勢區域，有效防止其陷入局部最優。其中scr表達式如式（6）所示：

其中，scr(i,t)表示在第t次迭代中，第i個粒子在前n次迭代中的個體最優適應度值提升總量和全局最優粒子提升總量的比值。本文中n取5，因此式（6）中分子代表了個體粒子的近5次迭代提升，分母則代表了近5次全局粒子的提升效果。

在以下三種情況下，該粒子均判定為劣勢粒子：scr(i,t)為無窮大Inf時，表示全局最優粒子gbest近期尋優停滯不前；scr(i,t)為0時，表示個體最優粒子pbest近期無尋優提升；scr(i,t)為異常空值NaN時，表示整個種群陷入了局部最優值。在粒子出現上述三種情況時，本文認定該粒子符合變異條件。受遺傳算法[17]的思想啟發，將劣勢粒子和全局最優粒子進行位置單向變異，其基本步驟如圖3所示。

圖3 SCVPSO算法變異部分Fig.3 Variation part of SCVPSO

變異具體流程如下：

（1）初始化，設置粒子變異概率variation_rate，決定該粒子向最優粒子躍遷的幾率，設置維度變異概率change_rate，決定該維度是否需要變異為最優粒子對應維度值。

（2）總結變異條件，在第t次變異，取t-n至t-1次實驗為例，計算粒子的scr值，篩選出符合條件的劣勢粒子。

（3）記錄最優，采用異步刷新的方式來記錄最優粒子的位置gbest_position。

（4）單向變異，根據variation_rate選擇出執行變異的粒子，采用輪盤賭選擇算法思想，將生成[0，1]之間的隨機數與change_rate再比較，二次篩選出劣勢粒子的維度值并與當前最優粒子gbest_position進行交換，單向重置劣勢粒子位置。

（5）確認正確，檢查此次變異后的粒子是否符合既定條件，重新計算適應度值并放回種群。

如表1所示，為說明單向變異對粒子狀態的改進程度，選取了表2中的測試函數F3,D=30時部分粒子在迭代過程中scr參數值的變化，各個粒子在迭代中篩選判定為劣勢粒子后（粗體標出），通過概率單向變異策略及時在后續迭代中做出調整，使scr值回歸正常，說明粒子跳出當前區域改善了劣勢狀態。與文獻[18]通過引力系數讓粒子進行社會學習相比，本文中單向變異學習了最優粒子的位置優勢，且引入概率保證了粒子本身活性，在增加種群多樣性的基礎上提高了粒子尋優效率。

表1 迭代時部分粒子scr參數值變化表Table 1 Change of scr parameter value of some particles during iteration

表2 基準測試函數Table 2 Benchmark function

2.4 算法流程

綜合2.1～2.3節的相關改進分析，本文提出的總結性自適應變異粒子群算法具體步驟如下：

步驟1初始化所有的粒子，包括速度和位置，設置相關的參數T,wmax,wmin,c1,c2,variation_rate,change_rate等。

步驟2計算每個粒子的適應度值，初始化個體最優位置pbest和全局最優粒子適應度值gbest，為后續的迭代做準備。

步驟3迭代的同時來計算近n次的變化量，累計不變次數超過規定次數時對篩選的局部粒子做反向處理。

步驟4實現隊列來循環緩存近期的pbest和gbest值，并在每個粒子位置更新結束后計算出其自我總結率scr值，按既定條件篩選出劣勢粒子并實現2.3節中的單向變異。

步驟5與自身的歷史最優值pbest進行比較，較優的值作為個體的最優值，同時判斷并異步更新全局最優粒子值gbest。

步驟6在未達到結束條件時，轉到步驟2繼續向下執行，直到結束，找到規定迭代次數中的gbest值以及其對應的位置。

按照給定的參數設置以及限定條件來執行整個流程。

3 實驗及結果分析

3.1 實驗測試函數

為了檢驗改進后算法性能，選取了如表2中所示的15個基準測試函數進行測試，已確定各個函數搜索范圍和最優值，其中F1～F7為單峰測試函數，F8～F13為多峰測試函數，F14、F15為固定維度多峰測試函數。

3.2 慣性系數提升對比

為了直觀展示不同w對算法的影響，驗證本文方案的可行性，將其與一些其他的w慣性權重方案做比較。其中有文獻[8]中原始的線性遞減函數w1，文獻[19]中關于迭代次數差的1.2次冪下降方案w2，文獻[20]中關于0.98的冪函數w3，文獻[21]中使用的關于迭代次數的余弦函數w4，文獻[12]中使用的正態分布衰減策略的改進方案w5，本文提出的方案為w6，如圖4所示。

圖4 不同方案的慣性權重Fig.4 Inertia weight of different ideas

選取了表2中的部分測試函數，采用控制變量法設置其他相關參數均相同，種群規模為50，迭代優化次數T=1 000，維度D=30，加速系數c1=c2=2。不同慣性權重w的方案在相關測試函數中表現如圖5～圖8所示。

圖5 不同慣性權重在F 1、F 2、F 3上的效果Fig.5 Effect of different inertia weight on F 1,F 2,F 3

圖8 不同慣性權重在F12、F 13、F14上的效果Fig.8 Effect of different inertia weight on F 12,F 13,F 14

實驗結果分析：在F1、F2、F5、F6、F7、F9中，由于慣性系數w3曲線為冪函數驟降，在前期獲得了較快的收斂速度，但是在后期由于其系數值較小且接近于0，則在迭代中弱化了慣性影響帶來的優勢，逐漸失去了尋優能力最終效果較差。慣性系數w1、w2、w4、w5從收斂速度和最終結果來看較為普通，整體表現接近。而本文提出的非線性遞減方案w6綜合了w3的優勢，如在F3、F4測試中，前期系數值較大有利于提高算法的全局搜索能力[16]；在中期實現了慣性系數的轉折再上升，從F10、F12、F13中可以看出，改進算法增加了粒子的活性，跳躍出當前區域，并擴大了粒子的搜索范圍，有效避免了粒子在迭代中期的早熟現象；在后期繼續非線性減小提升局部搜索能力[16]，從F3、F6、F10中可以看出，算法仍然擁有良好的尋優精度，且在F14中以最快速度收斂至目標解。

圖6 不同慣性權重在F 4、F5、F 6上的效果Fig.6 Effect of different inertia weight on F 4,F 5,F 6

圖7 不同慣性權重在F 7、F 9、F 10上的效果Fig.7 Effect of different inertia weight on F 7,F 9,F10

3.3 整體改進對比

綜合SCVPSO算法中各項改進策略，為進一步驗證其性能和優勢，實驗選取了基本粒子群算法PSO[7]、linear decay inertial weight PSO（LDWPSO）[8]、adaptive simulated annealing PSO（SAPSO）[14]、PSO based on dynamic acceleration coefficients（PSO-DAC）[22]、a normal distribution decay inertial weight PSO（NDPSO）[23]、exponential decay weight PSO（EXPPSO）[24]來作為對比實驗，設置種群數目為100，測試函數搜索范圍如表2所示。為保證實驗的有效性，各個粒子群算法在每個測試函數上均獨立運行30次，統計了在D=30、100時單峰函數和多峰函數上的實驗結果如表3～表6所示。

表3 各個算法在D=30單峰函數F1～F7上的結果Table 3 Results of each algorithm on D=30 unimodal function F 1～F 7

表6 各個算法在D=100多峰函數F 8～F 13上的結果Table 6 Results of each algorithm on D=100 multimodal function F 8～F 13

從表格中可以看出，在D=30時絕大部分單峰函數上，SCVPSO相比于其他算法在收斂精度上具有顯著提升，在多峰函數中也具有一定的優勢；在提升問題維度D=100后，SCVPSO的尋優結果仍明顯優于其他對比算法。其中在多峰函數F9、F13中，提升維度后使粒子變異概率也隨之提高，這使得SCVPSO尋優結果重新取得優勢，驗證了概率變異策略的有效性及改進算法對高維度的魯棒性。為了更直觀地對比不同算法在精度上的差別及其在收斂速度上的表現，實驗選取了D=100時部分函數上具有代表性的迭代曲線，如圖9～圖11所示。

表4 各個算法在D=30多峰函數F 8～F 13上的結果Table 4 Results of each algorithm on D=30 multimodal function F 8～F 13

表5 各個算法在D=100單峰函數F 1～F 7上的結果Table 5 Results of each algorithm on D=100 unimodal function F 1～F 7

由圖9～圖11中可以看出，在函數F3、F5、F11中，迭代中期由于種群陷入局部最優整體曲線停滯，得益于SCVPSO算法中w曲線的二次上升轉折，加大慣性影響，跳出了局部區域繼續尋優，最終取得了較好的效果，再次驗證了該方案w曲線的有效性。在函數F1、F2、F3、F4中迭代后期，SCVPSO仍然不斷更新全局最優值，保持著良好的搜索效率。在多峰函數F10、F11、F15中，本文算法能以最快的速度完成尋優任務，充分展現了概率總結性變異在配合新的慣性權重后帶來的優勢，在增加問題搜索空間的同時也提高了最終求解精度。從不同維度的實驗中可以得出，在相同的迭代次數時SCVPSO的適應度值均優于其他算法，且在迭代速度和精度上均具有顯著優勢。

圖9 不同算法在F 1、F 2、F 3上的效果Fig.9 Effect of different algorithms on F 1,F 2,F 3

圖10 不同算法在F 4、F 5、F 6上的效果Fig.10 Effect of different algorithms on F 4,F 5,F 6

圖11 不同算法在F10、F11、F15上的效果Fig.11 Effect of different algorithmson F10,F 11,F15

4 結束語

本文采用非線性轉折上升再遞減曲線來控制慣性權重隨迭代次數的變化，保證了粒子在陷入局部最優后能以最快速度跳出當前區域，擴大搜索空間避免早熟；對篩選的局部粒子作反向搜索處理，提高了種群尋優的效率；引入新的參數scr來分析各個粒子近期求解情況，配合新的慣性權重擴大搜索空間，通過概率單向變異引導粒子指向全局最優，增加了種群中粒子多樣性。仿真實驗表明，SCVPSO算法在多個單峰函數和多峰函數上，與其他粒子群算法相比具有較高的收斂速度以及求解精度。下一階段將圍繞引入的scr參數對種群進行詳細分類，方便對粒子做更進一步的分析研究。