粒子置換的雙種群綜合學習PSO 算法

紀 偉，李英梅+，季偉東，張 瓏

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

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

粒子群算法（particle swarm optimization，PSO）是由Kennedy 和Eberhart[1]于1995 年提出的一種群智能算法。群智能算法、模擬退火算法、遺傳算法等構建起智能優化算法的基本體系結構，其中群智能算法，如粒子群算法、人工蜂群算法、螢火蟲算法和布谷鳥算法等[2]，通過模擬群體性動物行為，在搜索空間內部利用個體間的信息交流、信息共享達到尋找最優解的目的。然而群智能算法發展至今仍然存在無法有效平衡求解精度和收斂速度的瓶頸，對于基本群智能算法的優化也是眾多學者一直以來的研究方向。逐維改進的布谷鳥搜索算法[3]通過逐維更新評價，將維度組合成新的解，進行迭代更新；2018 年王曉靜等人[4]提出一種基于均勻局部搜索和可變步長策略的螢火蟲優化算法，算法結合局部搜索算子和動態可變步長的策略，有效平衡了算法收斂速度和求解精度；2019 年謝承旺等人[5]提出一種多策略協同的多目標螢火蟲算法，均勻隨機化初始種群，利用精英個體指導螢火蟲移動，通過加擾動和ε-三點最短路徑策略增加種群多樣性；在螢火蟲算法的基礎上，文獻[6]提出一種變步長螢火蟲算法來解決數值優化問題；文獻[7]受PSO 算法的啟發，將全局最優解Gbest 的信息融合到人工蜂群算法中，提出了一種Gbest指導的人工蜂群算法。

在眾多群智能優化算法中，PSO 簡單高效，收斂速度快，逐漸在優化算法中脫穎而出[8]。利用PSO 算法的天然優勢，在此基礎上優化創新，能夠取得更為高效的結果。PSO 因在求解連續問題上的優勢，使得提出至今廣泛應用于參數優化[9]、結果預測[10]、問題診斷[11]等領域。PSO 中每個粒子都視作待優化問題的一個候選解，利用個體歷史最優信息和全局最優信息更新粒子速度和位置，在搜索空間迭代搜尋最優解。如同其他群智能算法，PSO 也存在多樣性差、易于早熟收斂等問題[12]，因此針對PSO 的改進方法層出不窮，根據眾多學者的分析和研究，大致分為如下四方面：

（1）算法參數方面。分析及研究PSO 的參數特性，通過優化算法參數來平衡全局勘探和局部搜索。文獻[13]提出一種基于高斯函數實現非線性遞減慣性權重的改進算法，從而更好地平衡粒子群搜索性能。2018 年王磊等人[14]將自適應慣性權重和學習因子與二維擾動策略相結合，提高了算法的收斂速度和求解精度。2019 年文獻[15]提出一種基于單個粒子最優適應度值的慣性權重調整方法，使得粒子具有不同的慣性權重，該方法增大了慣性權重的多樣性，同時有效平衡了全局勘探和局部搜索能力。

（2）拓撲結構方面。根據粒子間的社會關系設計不同的拓撲結構，豐富個體的學習模式，從而達到改善種群多樣性的目的。文獻[16]中粒子去除全局最優的影響，粒子的學習對象僅為種群中任意兩個粒子個體最優中的較優者。文獻[17]提出將PSO 中個體視作動態網絡拓撲結構下的節點，粒子通過動態變化的網絡結構豐富學習模式，平衡全局勘探與局部搜索。文獻[18]提出一種改進的鏈結構粒子群算法，其中粒子只受相鄰粒子影響，而不共享整個種群的鄰域最優，結果表明算法具有穩定的優化能力。2015 年Liu 等人[19]將“小世界”網絡的特性作為鄰域拓撲引入PSO，通過概率P逐代改變鄰域拓撲結構，豐富了粒子間的學習模式，有效改善了PSO 綜合性能。

（3）多種群方面。相比單一的粒子種群，多個種群間利用有效的信息交流機制，不但可以豐富種群資源，還可以合理利用其他種群信息指導當前種群進化。文獻[20]中Liang 等人把粒子種群分為具有小鄰域結構的小群，采用隨機重組算法實現種群間信息交流，增加了種群多樣性，在復雜的多峰函數上具有較快收斂速度。2017 年Chengkhuntod 等人[21]利用多個PSO 種群迭代更新，如果陷入局部最優且局部最優不同，則種群的局部最優進行復制操作；如果陷入局部最優且局部最優相同，則局部最優進行重置操作，從而脫離局部最優位置。2018 年鄧先禮等人[22]提出一種基于多種群的自適應遷移PSO 算法，為三個種群分配不同的加速度因子使其具有不同的搜索特性，周期性評價種群優劣程度，進行粒子遷移操作，實現不同搜索特性的種群協作尋優以及合理分配資源。

（4）算法（策略）混合方面。不同的優化算法（策略）在性能上具有不同的優勢，巧妙融合不同優化算法（策略）思想，提出優劣互補的創新算法，同樣也能提升算法的綜合性能。文獻[23]中Kayhan 等人將粒子群算法和電子表格求解器相結合，提出一種新的混合全局和局部優化算法，將PSO 用作全局優化算法，求解器用作局部優化算法，二者通過解的相互補充，來產生良好初始解，避免陷入局部最優。夏學文等人[24]提出一種具備反向學習和局部學習能力的粒子群算法，當陷入局部最優時對大部分粒子應用反向學習策略，對小部分較優粒子應用局部學習策略，提高了種群多樣性的同時避免了陷入局部最優。2018 年Wang 等人[25]結合自學習的候選生成策略和競爭性學習策略，提出一種自適應學習策略的混合PSO 算法，能夠較好地平衡全局勘探和局部搜索。

另外還有一些新穎的PSO 改進算法，如文獻[26]提出一種基于Logistic 映射的自適應變尺度混沌粒子群算法，對部分較優粒子進行變尺度混沌局部優化，從而提高算法求解精度。文獻[27]采用最壞粒子替換策略進行種群更新，結合短期記憶和長期記憶存儲粒子信息。2019 年徐利鋒等人[28]提出一種多級擾動的混合粒子群優化算法，避免陷入局部最優位置，在多目標優化問題上取得較好效果。

上述所有的PSO 算法的改進，其目的都是為了解決種群多樣性差，求解精度低，收斂速度慢等問題。針對這些問題，本文結合拓撲結構優化，多種群協同尋優和混合策略等思想，提出一種粒子置換的雙種群綜合學習PSO 算法（comprehensive learning PSO algorithm based on particle permutation，PP-CLPSO），根據粒子群算法搜索過程的快速性和收斂性，以及Logistic 混沌思想對搜索空間的隨機性和遍歷性，設置具有不同搜索特性的雙種群系統：自適應慣性權重的PSO 種群和基于Logistic 映射的混沌化種群。然后利用粒子編號機制，建立雙種群間粒子一一對應的同號結構和種群內粒子兩兩一對的同位結構，賦予粒子新型社會關系；當自適應慣性權重PSO 種群搜索過程陷入局部最優時，PSO 種群同位結構下適應度值較差的粒子與混沌化種群中具有相同編號的粒子進行同號粒子置換操作，實現雙種群間的信息交流，增加了種群多樣性；對粒子置換操作后的雙種群系統，綜合同位粒子學習策略和局部學習策略，既保證了全局勘探能力，又提高了局部搜索精度。

1 PSO 算法

其中，w為慣性權重，表示當前代的速度對下一代速度的影響，通常采用線性遞減的慣性權重選擇技術，公式為w=wmax-t?(wmax-wmin)/T，其中wmax=0.9，wmin=0.4，T為最大迭代次數，t為當前迭代次數；c1和c2為學習因子，表示粒子對個體歷史最優和全局最優的學習能力，取值一般為c1=c2=2.0；r1和r2為[0,1]之內的隨機數。

2 PP-CLPSO 算法的主要思想

2.1 雙種群系統

2.1.1 自適應慣性權重的PSO 種群（Pop1）

PSO 算法的搜索方式是利用個體歷史最優信息和種群最優位置信息，指導粒子動態更新速度和位置，慣性權重w作為PSO 算法中的一個重要參數，在搜索過程中起到調整粒子下一次迭代飛行速度，平衡全局勘探和局部搜索的作用。常用的線性遞減的慣性權重，在迭代后期慣性權重較小，粒子飛行速度較慢，而PP-CLPSO 的一個核心思想是每當Pop1 陷入局部最優就執行粒子置換策略，而置換操作往往發生在迭代后期，此時粒子需要較大的飛行速度向有利位置飛行，顯然線性遞減的慣性權重選擇技術不適用于PP-CLPSO。本文慣性權重選擇技術不再依賴粒子的迭代次數，而是根據粒子的適應度值進行自適應調節。自適應慣性權重選擇技術見算法1。

算法1自適應慣性權重算法

步驟1計算Pop1 粒子適應度值fi的平均適應度值favg。

步驟2取適應度值大于favg的粒子，計算平均適應度值fworseavg；取適應度值小于favg的粒子，計算平均適應度值fbetteravg。

步驟3如果fi＞fworseavg，則第i個粒子的慣性權重賦值為wmax。

步驟4如果fi＜fbetteravg，則第i個粒子的慣性權重賦值為wmin。

步驟5如果fbetteravg≤fi≤fworseavg，則第i個粒子的慣性權重按照式（3）、式（4）賦值。

其中，wmax=0.9，wmin=0.4，ε表示位于fbetteravg和fworseavg之間的粒子適應度值歸一化到Sigmoid 函數自變量[a,b]之間的取值，根據w取值范圍得到a=-0.405 47，b=2.197 22。這樣就建立了適應度值與慣性權重之間的非線性關系，較大適應度值的粒子具有較大的慣性權重，使其加速向最優位置飛行；較小適應度值的粒子，避免飛行速度過大而跳過最優位置，因此賦予較小慣性權重；粒子隨著適應度值的降低，慣性權重非線性下降。解決了迭代后期置換操作后的粒子慣性權重太小的問題，改善了Pop1 的收斂特性。

2.1.2 基于Logistic映射的混沌化種群（Pop2）

Logistic 映射是混沌系統中常見的一維混沌映射，處于混沌態Logistic 映射系統中的變量具有隨機性和遍歷性。Logistic 映射具有多種形式，式（5）是一常見的Logistic映射形式，其中混沌域為(0,1)，Logistic參數μ=[0,4]，當3.569 945 6…≤μ≤4 時，系統處于混沌狀態。

本文根據混沌思想生成基于Logistic 映射的混沌化種群（Pop2），種群內的每個粒子隨迭代次數增加，不改變其遍歷種群搜索范圍的方式，與Pop1 的搜索過程并行進行，為整個雙種群系統提供了豐富的粒子資源，極大地增加了種群多樣性。Pop2 搜索步驟見算法2。

算法2Pop2 搜索

步驟1t=1；

步驟2生成N個混沌域(0,1)內的初始向量，其中第i個粒子的D維初始向量為

步驟3利用式（5）迭代生成混沌序列

步驟4按照將產生的混沌序列映射到粒子原始解空間，得到，更新適應度值；

步驟5更新最優信息，t=t+1，返回步驟2。

2.2 同號結構和同位結構

對于種群規模大小均為N的Pop1 和Pop2，利用粒子編號機制明確種群粒子信息，通過粒子編號機制使得種群間粒子形成一一對應的同號結構，并且生成種群內部的兩兩一對的同位結構，如圖1。同號結構是基于粒子編號機制賦予粒子間的一種虛擬結構，指導雙種群粒子的信息交流，當滿足粒子置換操作條件時，依據同號結構進行粒子置換操作。同位結構提供了一種新的社會學習模式，當粒子置換操作后，Pop1 內處于同位結構下的粒子相互學習，指導粒子進行對自身有利的飛行。

2.3 粒子置換策略

Fig.1 Same sign structure and same position structure圖1 同號結構和同位結構

在執行粒子置換策略之前需要明確兩個問題，即何時進行粒子置換操作和置換種群中哪些粒子。在PP-CLPSO 算法中，Pop1 搜索后期種群多樣性差，陷入局部最優位置時粒子收斂速度減慢，最終導致算法停滯，若在此時雙種群系統資源進行調度，配合粒子學習模式的改變，可使算法重新激活。因此本文以Pop1 的收斂程度作為粒子置換策略的指標，當檢測到Pop1 種群最優信息cycle代未更新，則認為Pop1 陷入局部最優位置，觸發粒子置換策略。對于第二個問題，由于此時Pop1 的粒子已經陷入局部最優，無法找到更優的解，此時選擇當前同位結構下個體適應度值較差的個粒子與Pop2 進行同號粒子置換操作。粒子置換策略不但激活了停滯狀態的Pop1，改善了種群的多樣性，而且建立了雙種群系統之間的關聯性，實現雙種群間信息交流。

2.4 綜合學習策略

粒子置換操作后的雙種群系統引入了新的粒子信息，就需要新的學習模式指導粒子學習，來平衡全局勘探和局部搜索的能力。本文結合同位粒子學習和局部學習兩種方式，進行S代的綜合學習策略，來達到雙種群協同尋優的目的。

2.4.1 同位粒子學習

對于置換操作后的Pop1 來說，新置換進來的粒子位置信息具有混沌化特性，可以很好地用來指導其同位結構下陷入局部最優位置的粒子跳出局部最優位置，本文把這部分粒子的學習模式稱為同位粒子反向學習，如Part1。而新置換進來的粒子也可以利用其同位粒子所具備的較優位置信息進行正向搜索，本文把這部分粒子學習模式稱為同位粒子正向學習，如Part2。

Part1：Pop1 保留下的N/2 個粒子反向學習的對象是其歷史最差位置和當前代同位結構下新置換進來的Pop2 混沌態的粒子位置，其中第i個粒子的速度信息和位置信息更新公式如式（6）、式（2）所示。

2.4.2 局部學習

對于置換操作后的Pop2 來說，其目的是為了進行局部細致搜索。首先取全局最優位置：

通過計算其個體最優位置與全局最優位置的絕對距離差值，以此距離為最大搜索步長，在個體歷史最優位置采取線性遞減搜索步長的方式向全局最優靠近，即完成Pop2 內N個粒子在個體歷史最優位置的局部搜索。具體操作如Part3，局部學習采用貪心策略更新其位置信息。

Part3：此時Pop2 內的N個粒子，分別計算其歷史最優位置與全局最優位置的差值距離di=Gbest′-，以di作為第i個粒子的最大搜索步長，然后分別在其歷史最優位置采用線性遞減的搜索步長向全局最優位置正向搜索，其中第i個粒子的位置更新公式如式（8），r為[0,1]之間的隨機數，s、S分別為當前綜合學習代數和最大綜合學習代數。

需要說明的是，綜合學習期間的Pop1，其目的是為了使粒子能夠通過同位粒子學習策略分布在搜索空間，此時需要調整自適應選擇慣性權重技術，即將fi＜fbetteravg的粒子慣性權重賦值為wmax，使適應度較小的粒子以更大的飛行速度跳出局部最優；將fi＞fworseavg的粒子慣性權重賦值為wmin，使適應度較大的粒子以較小的速度緩慢向較優信息靠近，其他粒子以式（3）、式（4）選擇其慣性權重。經過S代綜合學習后會出現兩種情況：一是全局最優信息發生更新，則令Gbest1=Gbest′，指導種群再次按照原搜索方式進行迭代尋優；二是全局最優信息未發生更新，此時Pop1 經過S代的同位粒子學習也已經跳出局部最優位置，粒子較好地分布于搜索空間，綜合學習完成后，重新啟動原搜索方式繼續迭代尋優。

2.5 PP-CLPSO 算法流程

根據上述改進算法策略介紹，PP-CLPSO 的算法流程如圖2。

Fig.2 Flowchart of PP-CLPSO algorithm圖2 PP-CLPSO 算法流程圖

3 實驗結果與分析

3.1 測試函數

本文選取9 個經典測試函數來檢驗PP-CLPSO算法的綜合性能，根據函數特點分為：F1～F5單峰函數，F6～F9多峰函數。測試函數詳細信息見表1。

Table 1 Test function表1 測試函數

3.2 對比算法

PP-CLPSO 算法結合了拓撲結構優化、算法參數改進、混合策略結合和多種群協同尋優的思想，為驗證PP-CLPSO 算法具有高效的求解精度和收斂速度，本文選取了4 個涉及上述優化思想的算法進行對比，分別為：用于多峰函數優化的綜合學習粒子群優化算法（comprehensive learning particle swarm optimizer，CLPSO）[16]、高斯分布衰減慣性權重粒子群優化算法（particle swarm optimization algorithm with decreasing inertia weight based on Gaussian function，GDIWPSO）[13]、具備反向學習和局部學習能力的粒子群優化算法（reverse-learning and local-learning PSO，RLPSO）[24]、基于多種群的自適應遷移粒子的粒子群算法（multipopulation based self-adaptive migration PSO，MSMPSO）[22]。上述對比算法的詳細參數設置如表2。

Table 2 Contrast algorithm表2 對比算法

Table 3 Influence of cycle on algorithm表3 cycle對算法的影響

3.3 參數設置

PP-CLPSO 算法是以Pop1 的收斂情況作為執行粒子置換策略和綜合學習策略的標準，因此如何判斷Pop1 陷入局部最優顯得格外重要，本文采取cycle代Gbest1未發生更新的方式來判斷種群是否收斂于局部最優位置。為了更好地確定cycle的值，在種群規模Popn=20(n=1,2)，粒子維度D=30，最大迭代次數T=2×104時，分別將cycle的值設為5、15、20、25、30 進行實驗測試，實驗結果如表3 所示，其中Mean、St分別表示獨立運行20 次實驗結果的平均值、標準差。

分析F9函數在相同參數和仿真環境下cycle對算法時間的影響，實驗結果如圖3，其中T1和T2為算法運行時間和達到指定精度（1.00E-04）所用時間，單位秒（s）。

Fig.3 Influence of cycle on algorithm time圖3 cycle對算法時間的影響

從上述分析結果可以看出，當cycle取值較小，種群中粒子在當前收斂狀態下仍然具有找到更優解的趨勢，若在此狀態下執行粒子置換操作，不但會增加置換操作的次數，導致算法整體時間大大增加，而且粒子收斂不徹底，也降低了求解結果的精確度；當cycle取值較大，粒子收斂于局部最優位置且沒有找到更優解的趨勢，此時過多的迭代也會增加達到指定求解精度的時間。根據實驗測試和結果分析表明，cycle設置為20 代，實驗的結果最佳。

此外綜合學習的代數也直接影響算法的整體性能，根據表2 結果取cycle=20，其他實驗參數同上，對綜合學習代數S分別設為10、20、30、40、50 的情況下進行實驗測試，根據表3 選擇結果具有明顯區別的測試函數F3、F9進行分析，實驗結果如表4 所示。

Table 4 Influence of comprehensive learning times S on algorithm表4 綜合學習代數S對算法的影響

從表4 可以看出，若綜合學習的代數太大，Part2同位粒子正向學習粒子再次收斂到局部最優位置，并且將增加算法整體時間，若綜合學習的代數太小，Part1 同位粒子反向學習粒子跳出局部最優位置的能力不足，并且全局勘探和局部搜索找到更優解的幾率較小，重新采用標準PSO 搜索方式容易再次陷入局部最優，根據實驗測試取綜合學習代數S=20。

3.4 實驗結果

3.4.1 求解結果分析

將PP-CLPSO 與4 個對比算法分別在30 維的測試函數上獨立運行20 次，將實驗結果的平均值和標準差用來評價算法的求解精度。算法在9 個測試函數上的求解結果見表5。其中加粗數據為對應測試函數的最優求解結果。從表5 可以看出，PP-CLPSO在9 個測試函數中有7 個取得最優求解結果。通過對求解結果的進一步分析可以看出，PP-CLPSO 在5個單峰函數中3 次找到全局最優解，說明相比其他對比算法，PP-CLPSO 在單峰函數上能夠較為精準地找到最優解。而在4 個多峰函數上，PP-CLPSO 有4 次找到最優結果，說明對于多峰問題，PP-CLPSO 能夠展現出更為優越的性能。

3.4.2 收斂曲線分析

為了更為直觀地看出與4 個對比算法在求解精度和收斂速度上的差異性，圖4 給出了對比算法在9個測試函數上的收斂曲線，其中每次運行的最大評價次數（maximum number of fitness evaluations）為FEs=10 000D，從圖4（a）、（b）、（d）可以看出PPCLPSO 在單峰函數上具有較快的收斂速度，并且能夠迅速找到全局最優值，對于圖4（c）、（e）其表現僅稍遜于MSMPSO，對于單峰函數能夠迅速收斂于全局最優位置。從圖4（g）、（h）這兩個多峰函數的收斂過程可以看出PP-CLPSO 搜索前期收斂速度和求解精度并不是最好的，但是通過粒子置換和綜合學習策略能夠使得算法在迭代后期也能夠有發現更優解的機會。從圖4（f）、（g）、（h）、（i）中能夠看出PPCLPSO 對于多峰函數具有較為準確的收斂特性。綜合來說，PP-CLPSO 不管是在解決單峰問題上還是多峰問題上，隨著迭代過程中的粒子置換和綜合學習，能夠使粒子在求解精度和收斂速度上呈現出較為優越的性能。

3.4.3 算法時間分析

根據PP-CLPSO 的算法流程可知，算法單次迭代所需要的時間為Ta+Tb+Tc，其中Ta為雙種群系統中所有粒子的進化一次所用的時間，Tb為粒子執行過程所占用的時間，Tc為粒子置換策略和綜合學習策略時間，當算法沒有陷入局部最優時Tc則為0。其中Ta的時間復雜度為O(N)，Tb的時間復雜度為O(1)，Tc的時間復雜度為O(S×N)，因此算法的時間復雜度為O(S×N)。

Table 5 Solution result表5 求解結果

Fig.4 Convergence curve圖4 收斂曲線

在仿真環境相同的情況下，為了更有效分析算法時間上的優勢，表6 給出了PP-CLPSO 與4 個對比算法在3 個單峰函數和3 個多峰函數達到指定求解精度（1.00E-04）所利用的時間，單位秒（s），其中“—”表示最大迭代次數后仍未達到該精度。

Table 6 Running time of algorithms表6 算法運行時間 s

從表6 中可以看出相比4 個對比算法來說能夠在更短的時間達到指定的求解精度，通過對算法流程分析可以得出，雖然陷入局部最優時候增加了S代的綜合學習，增加了算法單次迭代的時間，但是S代的綜合學習更快地找到全局最優解，供下次種群1 中利用，結合自適應慣性權重算法所賦予的不同權重系數，使得有利粒子能夠以更大的飛行速度，更快地收斂于全局最優位置。

3.4.4 算法綜合性能分析

為檢驗PP-CLPSO 算法的綜合性能，將其與其他群智能優化算法進行對比，在維度D=30，種群規模N=100，最大迭代次數T=D×10 000 的參數設定下，獨立運行50 次，取測試結果的平均誤差與文獻[4]的數據進行對比，其中DDICS[3]、GABC[7]、VSSFA[6]、UGCS[4]這4 個群智能算法的其他參數設置與其原文一致，實驗結果如表7 所示。由表7 可以看出PPCLPSO 在6 個測試函數上的求解結果均優于其他4個群智能算法。

Table 7 Mean error value of PP-CLPSO and other swarm intelligence algorithms表7 PP-CLPSO 與其他群智能算法的平均誤差值

4 結束語

本文提出的PP-CLPSO 算法旨在解決群智能優化算法難以跳出局部最優這一難題。利用標準粒子群算法和Logistic 混沌思想建立雙種群系統，種群間粒子形成獨特的同位結構和同號結構，通過動態置換粒子策略來增加種群多樣性，綜合同位粒子學習和局部學習兩種粒子學習策略，幫助算法跳出局部最優的同時提高收斂速度和求解精度。利用9 個測試函數和4 個粒子群改進算法、4 個群智能算法進行實驗對比，實驗結果表明PP-CLPSO 算法具有較為優異的綜合性能。進一步檢驗算法在實際應用問題中的有效性將是下一步研究的主要內容。