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

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

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

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

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

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

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

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

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

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

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

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

1 PSO 算法

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

2 PP-CLPSO 算法的主要思想

2.1 雙種群系統(tǒng)

2.1.1 自適應慣性權(quán)重的PSO 種群（Pop1）

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

算法1自適應慣性權(quán)重算法

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

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

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

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

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

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

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

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

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

算法2Pop2 搜索

步驟1t=1；

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

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

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

步驟5更新最優(yōu)信息，t=t+1，返回步驟2。

2.2 同號結(jié)構(gòu)和同位結(jié)構(gòu)

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

2.3 粒子置換策略

Fig.1 Same sign structure and same position structure圖1 同號結(jié)構(gòu)和同位結(jié)構(gòu)

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

2.4 綜合學習策略

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

2.4.1 同位粒子學習

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

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

2.4.2 局部學習

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

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

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

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

2.5 PP-CLPSO 算法流程

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

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

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

3.1 測試函數(shù)

本文選取9 個經(jīng)典測試函數(shù)來檢驗PP-CLPSO算法的綜合性能，根據(jù)函數(shù)特點分為：F1～F5單峰函數(shù)，F(xiàn)6～F9多峰函數(shù)。測試函數(shù)詳細信息見表1。

Table 1 Test function表1 測試函數(shù)

3.2 對比算法

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

Table 2 Contrast algorithm表2 對比算法

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

3.3 參數(shù)設置

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

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

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

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

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

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

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

3.4 實驗結(jié)果

3.4.1 求解結(jié)果分析

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

3.4.2 收斂曲線分析

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

3.4.3 算法時間分析

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

Table 5 Solution result表5 求解結(jié)果

Fig.4 Convergence curve圖4 收斂曲線

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

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

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

3.4.4 算法綜合性能分析

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

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

4 結(jié)束語

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