具備自糾正和逐維學習能力的粒子群算法

張津源，張 軍，季偉東，孫小晴，張 瓏

1(哈爾濱師范大學 計算機科學與信息工程學院，哈爾濱 150025)

2(天津師范大學 計算機與信息工程學院，天津 300387)

1 引 言

粒子群算法(Particle Swarm Optimization)是由Kennedy和Eberhart[1]在1995年受鳥類覓食行為的啟發提出的一種進化算法.在算法中，每個粒子代表一個問題的潛在解.每個粒子以一定速度在多維搜索空間中飛行，粒子速度隨著個體最佳位置和群體最佳位置的變換而更新.粒子群算法運行速度快且易于實現，近年來在旅行商問題[2]、文本功能選擇[3]、預測時間[4]和動態車輛路徑[5]等眾多領域被廣泛應用.但這些特點也使得粒子群算法存在很大的隨機性，當粒子群算法在優化比較復雜的多峰問題時易出現過早陷入局部最優、收斂速度慢、收斂精度低等一系列問題，針對PSO存在的這些問題，研究學者們在調整參數、結合其他優化策略或算法以及改變粒子的鄰域拓撲結構等方面做出了許多改進工作.

1998年Shi和Eberhart[6]提出了帶有慣性權重的的粒子群優化算法，改進了最早期的PSO算法容易陷入局部最優的問題.Clerc隨后就提出了帶有壓縮因子的粒子群優化算法[7]，根據粒子進化的不同階段控制權重大小，解決陷入局部最優的問題并提高收斂速度.這是兩種最經典的PSO改進算法.Gang[8]基于自然界中的種群遷移行為，將種群隨機劃分為若干子種群，利用競賽選擇的方式進行粒子遷移.Zhang[9]采用自適應策略在子種群上更新慣性權重，并通過共享信息自適應地更新當前記錄.Xin[10]等人將粒子群算法和差分演化算法相結合,周期性的分析兩算法性能并根據判定結果設置使用概率，將兩算法充分結合，提高了解的質量.Xia[11]保留初始種群中的最差粒子并記錄粒子的歷史最差位置，利用這些信息牽引部分粒子迅速逃離局部最優；同時使用較優粒子的差分結果指導局部學習，有效平衡了粒子收斂能力和種群多樣性.Li[12]提出了一種基于信息共享機制的競爭-協作PSO，一旦種群陷入局部最優，使用競爭機制選擇評價結果更優的粒子指導其學習，同時種群中的所有粒子共享個體最優位置，加強了解之間的交流.隨后Xia[13]又提出了一種基于多尺度選擇性學習和探測-收縮機制的PSO.粒子根據當前進化階段選擇不同尺度進行學習，并且利用歷史信息指導最優粒子在不同情況下采用探測收縮策略，保證了個體學習效率和算法開采能力.Wang[14]基于Logistic模型提出了一種自適應控制種群規模的策略，能夠自適應的兼顧種群有效性和多樣性，將該策略應用于PSO中顯著提高了粒子收斂速度.Zhu[15]等人關注個體最優和群體最優的選擇，將多目標優化問題分解為子問題集并為其分配相應的對象指導優化.Cao[16]深入探索了粒子種群的并行屬性，根據分布式并行計算的特點提出了一種針對優化多目標大規模種群問題的改進粒子群算法.Tian[17]采用混沌反向策略生成高質量的解提高粒子尋優能力，基于有效的多樣性機制使用3種不同突變策略來提高種群多樣性.Li[18]遵循一階差分方程的原理構造粒子的搜索軌跡，減少粒子的隨機搜索使得粒子更加完全地探索搜索空間.Santos[19]通過對梯度信息和多樣性控制提出了一種半自治的粒子群優化算法，提高了局部搜索效率.Abdelhafiz[20]利用粒子群優化和Akaike信息準則確定非線性放大器行為模型的維數，將該方案應用于廣義記憶多項式模型，減少了發現最小模型的時間.上述研究成果中基于PSO的改進算法各有優點，都在粒子群算法的收斂速度和精度上有所改善，但是沒有消除粒子群算法中隨機性的影響，且大部分采用整體更新評價策略，無法避免維間干擾問題.

為進一步解決以上問題，同時關注到已有國內學者將逐維策略應用在一些除粒子群以外的其他群體智能算法上[21-23]獲得了不錯的優化效果.本文提出了一種具備自糾正和逐維學習能力的粒子群算法.通過提出一種糾正策略來控制算法隨機性，同時使用改進的逐維學習策略更新最優粒子，有效提高粒子尋優能力.通過使用不同的控制周期巧妙結合兩種策略的特性，使得本算法將兩種策略的優點實現最大化的發揮.本文對選取的12個測試函數進行實驗，結果表明，本文提出的兩種策略發揮出了各自優勢，改進的SCDLPSO相比PSO的尋優速度更快，求解精度更高；相比于其他3種改進的主流PSO算法[11，14,24]，SCDLPSO同樣具有一定的競爭力.

2 具備自糾正和逐維學習能力的粒子群算法

2.1 糾正策略

傳統PSO中粒子在進化過程中按照公式(1)和公式(2)進行速度和位移更新，粒子在進化過程中受個體最優(Pbest)和群體最優(Gbest)的指導，缺乏對粒子整個運動過程的關注，特別是在尋優難度較大的復雜多峰函數上，使得粒子在進化過程中產生很大的隨機性，這是導致粒子群算法收斂速度慢的重要原因之一.

(1)

(2)

比如在種群進化過程中可能存在這種情況：粒子初始運動方向是向著最優解的方向前進的，但由于尋優過程的復雜性，接下來的某代上卻朝著偏離最優解的方向移動，此時若繼續按照公式(1)、公式(2)更新速度和位移，受由上一代部分粒子隨機飛行而產生的錯誤信息指導，必然浪費粒子學習時間，導致收斂速度變慢.

為了解決這個問題，提出了一種糾正策略，即通過監督粒子在整個進化過程中運動方向的變化情況，對粒子下一代尋優方向實施干預以避免其繼續受到錯誤指導，從而提高種群收斂速度.圖1給出了糾正策略的簡單示意圖.圖中A類粒子表示受到了隨機性和錯誤指導的影響的粒子，其下一代更新將偏離最優解的方向，使用公式(3)更新速度，將速度向量方向取反，使得下一代能夠向著最優解的方向移動，提高收斂速度，位置更新使用公式(2)；同時，運動方向正確的B類粒子則將繼續按照原有的方式進行更新.

圖1 糾正策略的二維示意圖

(3)

2.2 Pbest指導Gbest的逐維學習策略

目前在大部分研究中，對種群中最優粒子指導方面都采用了選取所有維度整體更新再評價的策略，但對于復雜的多維函數的優化問題，使用這種方法會由于維間的相互干擾導致某些正確進化維度的信息被掩蓋，從而導致評價次數的浪費，降低算法的收斂速度和效率.而逐維學習策略將最優解和學習對象在維度上進行拆分，獨立的對每一維度上的信息進行考察，能夠有效避免維間干擾的問題.

在PSO中，隨著種群的進化，每個粒子的Pbest都在不斷更新，它記錄并更新著在飛行過程中的歷史最佳表現，利用價值高.因此為了保證逐維策略中學習對象的多樣性和有效性，本文結合Pbest的特點和逐維策略的優勢提出了一種Pbest指導Gbest的逐維學習策略.

圖2給出了本策略的模型示意圖.圖中引入了數據結構中的壓棧與出棧操作模擬種群中所有Pbest逐個的對最優粒子進行指導的動作.

圖2 Pbest指導Gbest的逐維學習策略模型圖

該策略的思想是：按維度分解Gbest和Pbest位置向量，將Pbest上某一維的值和Gbest上其他維的值組成新的Gbest；計算適應度值評價新解；若當前新解質量更優則保留Pbest該維度信息對解的更新結果；否則放棄當前維度值，保留原Gbest維度信息不變.采用這樣的貪心評價方式，直到各維度更新完畢.當一個Pbest的所有維上的信息都對Gbest的相應維指導結束后，執行出棧操作離開Pbest棧容器，并對Pbest棧容器進行壓縮，開始其他Pbest對Gbest的指導.

算法1.Pbest指導Gbest的逐維學習策略

1.Fori=1:sizepop

2. Forj=1:D

3. 將第i個粒子的Pbest的第j維上的值替換給Gbest第j維得到newGbest;

4. Iffun(newGbest)

5. 用newGbest更新Gbest位置；

6. End

7. End

8.End

sizepop表示種群規模，D表示維數，newGbest表示在Pbest中第i維替換給Gbest第i維后的粒子，fun表示用于計算粒子適應度值的函數(fun(Gbest)即粒子Gbest的適應度值).

通過在逐維學習策略中引入貪心評價策略，徹底消除了某些維上出現退化的情況，避免了進化維度信息被掩蓋的的問題，從而獲得更高質量的解，顯著提高收斂精度.同時，與大多數逐維學習策略中所采用的向某個單一對象學習的方式不同，該策略中Gbest受種群個體Pbest的指導影響，加強了個體最優粒子與群體最優粒子之間的聯系，提高了最優粒子學習對象的多樣性.

2.3 具備自糾正和逐維學習能力的粒子群算法

為了實現自動化的判斷粒子更新方向，本文預設周期T1跟蹤粒子運動軌跡并最終作出評估，若偏離最優解，則在T1+1代采用糾正策略；為了降低算法復雜度，采用每進化T2代使用一次逐維策略的辦法.通過在兩策略中引入兩種不同的控制周期，提出了自糾正PSO(Self-Correcting Particle Swarm Optimization,SCPSO)、逐維學習的PSO(Dimension by Dimension Learning Particle Swarm Optimization,DLPSO)和具備自糾正和逐維學習能力的PSO(Particle Swarm Optimization with Self-Correcting and Dimension by Dimension Learning Capabilities,SCDLPSO).

首先，為了將糾正策略動態的應用于PSO，實現自動化地干預粒子學習方向，基于周期性思想，提出了自糾正PSO(SCPSO).每T1個評估代和1個糾正代共同組成自糾正策略的控制周期，及時避免粒子向更壞趨勢更新.下面給出了兩個功能代的概念和使用糾正策略的具體運行方式.

概念1評估代：判斷粒子進化趨勢的正確性.在評估代內記錄粒子更新的適應度值，通過采用二分均值的比較辦法，將預設的評估周期代數T1分半，在每個評估周期末代比較粒子后T1/2與前T1/2的適應度值平均值大小，如果粒子前T1/2的解更優，則判定粒子在本個評估周期T1內的更新受到了誤導；反之，則判定粒子尋優方向基本準確.粒子在評估代上使用公式(1)更新速度.

概念2糾正代：根據評估結果作出響應，干預粒子學習方向.根據前T1個評估代的判定結果在第T1+1代作出響應，如果粒子受到了誤導，則在糾正代觸發糾正策略，使用公式(3)將粒子的速度方向置反，保證粒子的運動方向在下一個評估代開始之前得到糾正；反之，則繼續使用公式(1)進行速度更新.粒子在評估代和糾正代上的位置更新公式都使用公式(2).

SCPSO在評估代上的運作方式和標準PSO大致相同，且大部分工作都是在糾正代上完成，因此算法2的自糾正策略中省略了評估代上的工作流程.

算法2.自糾正策略

1.Fori=1:sizepop

2. IFearlyMin

3. 使用公式(3)更新速度，使用公式(2)更新位置；

4.ELIFearlyMin>laterMin

5. 使用公式(1)更新速度，使用公式(2)更新位置；

6. End

7. 計算適應度值，更新Pbest,Gbest；

8.End

sizepop表示種群規模，earlyMin表示粒子在評估代T代中的前T1/2代的適應度值平均值，laterMin表示粒子在評估代T代中的后T1/2代的適應度值平均值

其次，考慮到連續使用逐維學習策略將導致計算量大、算法復雜度升高的問題，基于周期性思想提出了逐維學習的PSO(Dimension by Dimension Learning Particle Swarm Optimization,DLPSO)，在算法1中設置了一個較大的逐維學習周期T2，種群的整個迭代過程中只有在周期時間點上開啟全局最優向個體最優逐維學習的機制，在略微影響求解精度的情況下，能夠大幅減小了算法的復雜度.DLPSO將2.2中的算法1默認在每T2代上使用.

最后，SCDLPSO通過使用不同的控制周期將兩策略結合，當粒子每進化T1個評估代后使用糾正策略，能夠自動化的對粒子進化趨勢進行監督，提高收斂速度，而后根據評估結果在每T1+1個糾正代上作出響應.采用糾正策略后，為進一步提高粒子的收斂精度，在每T2個代數周期上使用逐維學習策略，通過減少運行次數的方式來達到降低算法復雜度的目的.通過使用兩種不同的控制周期充分結合兩策略，發揮出最大優勢.SCDLPSO的運行流程如圖3所示.

圖3 算法整體流程圖

2.4 算法流程

具備自糾正和逐維學習能力的PSO(SCDLPSO)的算法流程如下：

Step 1.初始化種群，設置相應參數；

Step 2.判斷當前代是否為評估代，若是，轉Step 3，若不是，說明當前為糾正代，轉Step 5；

Step 3.使用公式(1)、公式(2)更新種群中粒子的速度和位置；

Step 4.計算種群中粒子適應度值，并更新種群Pbest、Gbest；轉Step 6；

Step 5.使用算法2更新種群中粒子的速度、位置和Pbest、Gbest；

Step 6.判斷當前代是否為逐維學習代，若是，轉Step 7，若不是，轉Step 8；

Step 7.使用算法1更新種群Gbest；

Step 8.判斷是否滿足停止條件，若不滿足，轉Step 2，若滿足，結束.

3 仿真實驗與結果分析

本文使用Matlab2018a進行仿真實驗.選取了表1中的12個經典測試函數來評估算法的尋優能力.算法在不同類型的函數上表現不同，因此本文選擇了多個特征明顯的函數進行實驗，表1中F1、F2、F3、F9、F11、F12是高維單峰函數，僅存在一個全局最優點；F4～F8是高維多峰函數，含多個局部最優點，尋優難度較大.12個測試函數均為尋找最小值問題，全局最優值為0，F10的維數不能少于4維，且全局最小值和維數有關，易陷入局部最優.每個函數的特征如表1所示.

為了更加全面地驗證本文提出的算法有效性，本實驗共分為兩階段完成.在3.1的實驗中將主要對比傳統PSO、SCPSO、DLPSO和SCDLPSO，這一階段的主要目的有兩個，分別是：1)通過對比結果來驗證本文算法策略的有效性和分析在不同指標上取得改進的原因；2)通過增加不同維度上測試函數的對比實驗來說明本文算法策略的有效性和穩定性.3.2的實驗中將本文的SCDLPSO與RLPSO[11]、SaDCPS+PSO[14]、CPSO[24]幾種優秀的PSO改進算法進行比較，以便分析本文算法在同級別改進算法中的競爭力.

3.1 與PSO對比實驗結果分析

3.1.1 尋優能力比較

本實驗將本文提出的3種算法與傳統PSO進行對比，驗證應用兩種策略使得算法在不同方面取得優勢的真實性.基本參數設置如下：計算次數Time=10，最大迭代次數maxgen=1000，種群規模sizepop=50，維數D=100，學習因子c1、c2都為2；本文算法1(DLPSO)中的評估學習周期T設置為50，每個算法獨立運行10次，算法2(SCPSO)中的評估周期T設置為4，上述將兩種結合的整體算法(SCDLPSO)中的參數和算法1、2中的一致，評估周期T1設置為4，學習周期T2設置為50.

選取了表1中12個經典的測試函數來驗證本文提出的3種算法性能.取平均值和最優值作為測試結果，具體測試結果詳細見表2和圖4.通過表2不難看出本文提出的SCDLPSO在12個測試函數上的性能表現相比基本PSO都更加優秀，其中對于函數F1、F4、F9、F11上優勢明顯，函數的均值相比基本PSO分別降低了16、31、16和16個數量級，說明本文中的算法能夠顯著改善粒子群的尋優能力、在避免發生早熟收斂的問題上更加具有優勢，且其解非常接近最優解.同時本文先后提出的SCPSO、DLPSO相比基本PSO也都更加優秀，而SCDLPSO相比SCPSO，DLPSO在12個測試函數上的表現又更加優秀，說明本文算法達到了充分結合并發揮兩種算法的優越性的目的.

表1 12個經典的測試函數

表2 改進算法與傳統PSO在12個測試函數優化的結果

圖4是4個PSO算法在12個測試函數上尋優過程的收斂曲線圖，從圖中可以清晰的看出，本文提出的3種算法在12個測試函數上的收斂速度和精度明顯優于基本PSO，同時SCDLPSO優于SCPSO和DLPSO.

下面通過對本文提出的3種算法在函數6上的收斂曲線進行詳細分析：如圖4(f)所示，SCDLPSO與SCPSO相比，收斂曲線中出現了斷層式的下降.這是由于DLPSO發揮了作用，通過在每個設置好的周期點上使用逐維學習策略使得最優解的尋找過程發生周期性的量級變化，說明SCDLPSO算法中引入的算法1更容易跳出局部最優值，避免早熟收斂；SCDLPSO相比DLPSO，在每個相同的時間點上幾乎都能搜索到更優的解，這是由于在周期性的使用糾正策略的過程中選擇了較小的控制周期，使得糾正粒子學習傾向的頻率更高，能更加及時的對粒子進化趨勢進行監督并糾正.說明SCPSO有效提升了種群粒子的收斂速度.收斂曲線表明SCDLPSO能夠結合SCPSO和DLPSO算法的不同優勢，保證粒子收斂速度的同時，仍能夠提高求解精度.

圖4 4種算法在12個測試函數上的尋優曲線

3.1.2 維度變化比較

為了驗證SCDLPSO算法在隨著維度的變化是否仍能夠擁有比傳統PSO更佳的收斂水平，進一步說明本文提出的改進算法的有效性，因此本節在3.1.1實驗中設置的維數D=100的基礎之上，將維數設置分別減小50維度和增加50維度，同樣選取表1當中的12個經典測試函數再次進行實驗對比尋優結果.設定計算次數Time=10，最大迭代次數maxgen=1000，種群規模sizepop=50，學習因子c1、c2都為2；SCDLPSO算法中評估周期T1=4，學習周期T2=50.表3給出了PSO算法和SCDLPSO算法分別在D=50和D=150的條件下運行后的平均值和最優值，最好的結果由粗體顯示.如表3所示，本文提出的SCDLPSO算法的尋優效果在12個測試函數上都顯著優于PSO算法.PSO算法維度從50增加到150的情況下，在12個測試函數上的尋優能力大幅降低，F1、F3、F7、F8、F11和F12函數的尋優結果的精度以2到3個數量級的大小的降低.相反，SCDLPSO算法在維度升高時，雖然數量級也有增加，但在除F2、F3、F10和F12以外的8個測試函數上的收斂精度都仍然趨近于最優值0，充分說明了本文提出的改進算法在求解精度上的有效性和穩定性.同時，當D=50時，函數F1、F4、F6、F11搜索到了最優值0；D=150時，函數F11搜索到了最優值0.由此可見，SCDLPSO算法采用的自糾正和逐維策略，在及時糾正粒子進化方向的同時，避免了維間干擾，展示出了更好的局部開采能力，有效解決了傳統PSO在高維環境下收斂精度低的問題.

3.2 與其他改進PSO對比實驗結果分析

為充分展現本文策略的有效性，本實驗將本文提出的SCDLPSO與3種基于融合不同改進策略的PSO算法進行對比，選取改進的PSO算法分別為在多峰函數表現優秀的RLPSO[13]、能夠自適應控制種群規模的SaDCPS+PSO[14]和引入混沌策略的CPSO[24].種群規模sizepop=50，維數D=100，最大迭代次數maxgen=2000，其他改進算法的參數與其文獻保持一致.表3給出了4種改進算法在12個測試函數上所尋找到的最優解.

表3 不同維度的尋優結果

從表4可以直觀的看出，針對不同函數，各個算法表現的性能也各不相同.對于F1，4種優化算法均尋找到了最優解0.針對F2和F3，SCDLPSO算法的性能弱于CPSO，但優于其他算法.在F5、F6、F8、F9、F10、F12上，SCDLPSO算法的性能都優于其他3個算法，特別是在F9上，SCDLPSO相比其他算法尋找到的最優結果超過了26個數量級，顯著提升了解的質量.在F7和F11上，SCDLPSO和RLPSO都尋找到了最優解0.對于函數F6，其它改進算法性能不理想，但SCDLPSO能夠成功收斂.

表4 各算法實驗對比結果

本文提出的SCDLPSO算法的優化結果無論是在處理單峰函數還是多峰函數問題上，相比另外3種算法都達到了更佳的尋優效果，充分證明本算法的有效性，體現出在改進算法中較強的競爭力.

4 結 論

為了解決由于PSO算法的隨機性而導致粒子在尋優過程中收斂速度慢、收斂精度低的問題，本文提出了一種具備自糾正和逐維學習能力的粒子群算法.通過提出的自糾正策略使得粒子能夠自動評估解的優劣情況，并及時糾正粒子的尋優方向；同時利用個體最優粒子對群體最優粒子進行逐維指導，提高粒子學習對象的多樣性并能夠充分利用Pbest上的有效信息，改善解的質量；分別應用不同的控制周期將兩策略結合到PSO中形成了SCPSO、DLPSO和SCDLPSO三種改進算法，實驗結果表明，本文提出的SCDLPSO能夠充分結合兩種改進策略的優勢，相比其他改進算法具有更快的收斂速度和更高的收斂精度.

雖然通過多次實驗對比能夠基本正確的設置控制周期，但文中算法控制周期的確定同樣也是一個優化問題，目前仍不能夠通過某種科學辦法平衡兩種策略的特點設置控制周期.因此，后續工作將主要解決這個問題，以充分發揮算法效能.此外，還需要將本算法在更多的實際優化問題中應用并進行分析驗證.