總結(jié)性自適應(yīng)變異的粒子群算法

陳博文，鄒 海

安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601

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

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

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

1 基本粒子群算法

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

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

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

2 SCVPSO算法

2.1 新的慣性權(quán)重自適應(yīng)函數(shù)

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

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

圖1 SCVPSO算法慣性權(quán)重曲線Fig.1 Inertia weight curve of SCVPSO

2.2 局部粒子反向搜索處理

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

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

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

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

2.3 劣勢粒子位置總結(jié)性變異

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

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

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

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

變異具體流程如下：

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

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

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

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

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

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

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

表2 基準測試函數(shù)Table 2 Benchmark function

2.4 算法流程

綜合2.1～2.3節(jié)的相關(guān)改進分析，本文提出的總結(jié)性自適應(yīng)變異粒子群算法具體步驟如下：

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

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

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

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

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

步驟6在未達到結(jié)束條件時，轉(zhuǎn)到步驟2繼續(xù)向下執(zhí)行，直到結(jié)束，找到規(guī)定迭代次數(shù)中的gbest值以及其對應(yīng)的位置。

按照給定的參數(shù)設(shè)置以及限定條件來執(zhí)行整個流程。

3 實驗及結(jié)果分析

3.1 實驗測試函數(shù)

為了檢驗改進后算法性能，選取了如表2中所示的15個基準測試函數(shù)進行測試，已確定各個函數(shù)搜索范圍和最優(yōu)值，其中F1～F7為單峰測試函數(shù)，F(xiàn)8～F13為多峰測試函數(shù)，F(xiàn)14、F15為固定維度多峰測試函數(shù)。

3.2 慣性系數(shù)提升對比

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

圖4 不同方案的慣性權(quán)重Fig.4 Inertia weight of different ideas

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

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

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

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

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

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

3.3 整體改進對比

綜合SCVPSO算法中各項改進策略，為進一步驗證其性能和優(yōu)勢，實驗選取了基本粒子群算法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]來作為對比實驗，設(shè)置種群數(shù)目為100，測試函數(shù)搜索范圍如表2所示。為保證實驗的有效性，各個粒子群算法在每個測試函數(shù)上均獨立運行30次，統(tǒng)計了在D=30、100時單峰函數(shù)和多峰函數(shù)上的實驗結(jié)果如表3～表6所示。

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

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

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

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

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

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

圖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 結(jié)束語

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