多策略融合的粒子群優(yōu)化算法

廖瑋霖，程 杉，尚冬冬，魏昭彬

三峽大學 微電網湖北省協同創(chuàng)新中心，湖北 宜昌443002

Kennedy 和Eberhart[1]于1995 年提出的PSO 算法具有原理簡單、參數較少、收斂速度較快等優(yōu)點，在神經網絡訓練[2]、參數優(yōu)化[3]、圖像處理[4]、聚類分析[5]、特征選擇[6]、應用檢測[7]等多個領域應用廣泛。由于PSO 算法易陷入局部最優(yōu)，學者們提出了各種改進方法，主要有以下三類：

（1）改進算法結構策略。為了確保粒子速度不降至0，文獻[8]在速度更新公式中加入微小擾動項，為PSO算法逃脫局部最優(yōu)提供了可能，但也降低了后期的局部搜索能力及收斂速度；文獻[9]通過反向預測因子改善速度更新公式，并利用斥力因子對粒子位置進行修正，提高了PSO算法尋優(yōu)能力，但如何選擇合適的最小允許間距尚未明確；文獻[10]提出了一種多信息融合的三迭代變量慣性權重策略，提高了種群多樣性，但降低了算法的收斂速度；文獻[11]舍棄了速度更新項和自我認知項，僅使用全局最優(yōu)解引導粒子進行位置更新，并通過鎖定因子降低粒子陷入局部最優(yōu)的概率，提高了收斂速度和精度，但在病態(tài)函數求解問題上精度仍較差。

（2）引入新的進化策略。文獻[12]通過變異策略使得更新后的粒子有一定幾率變異，防止了進化過程中陷入局部最優(yōu)難以跳出的問題，但變異率如何設置恰當仍未解決；為了提升粒子脫離局部最優(yōu)解的能力，文獻[13]提出排異和競爭策略，而排異策略中的算子如何設置尚未明確；文獻[14]引入“剪枝”策略，增強了全局搜索能力和局部搜索能力，但剪枝需人工調整優(yōu)化插枝方差及解決速度修正問題；文獻[15]通過特征聚類提高了初始化種群的質量，并根據相似性對粒子進行相對應的交互操作，提高了種群多樣性，提升了算法尋優(yōu)能力。

（3）與其他智能算法融合。文獻[16]在PSO算法中加入人工蜂群搜索算子，搜索算子擁有很強的搜索能力，使算法快速跳出局部最優(yōu)，但也降低了算法的局部搜索能力；文獻[17]將人工蜂群搜索和混合蛙跳局部搜索融入PSO，使算法具有較快的收斂速度和較好的搜索能力；文獻[18]加入遺傳算法（GA）的交叉變異機制，以協調PSO算法全局搜索和局部搜索能力，但GA算法與PSO算法本身固有缺點無法消除，算法仍有概率陷入局部最優(yōu)；文獻[19]采用反向學習提高了種群多樣性，并融入灰狼算法的搜索方式降低了PSO 算法陷入局部最優(yōu)的概率，提高了求解精度。

各種改進方法均在一定程度上提升了PSO 算法的收斂性能，但由于全局搜索能力與局部搜索能力的彼此制約，大幅度地限制了PSO算法性能的提升。本文提出一種多策略融合的粒子群優(yōu)化算法（MSPSO），算法引入三種策略：一是采用三黑洞系統捕獲策略，開辟新的搜索區(qū)域，以提高種群多樣性；二是引入多維隨機干擾策略，使粒子搜索的更加細致，進而提升計算精度；三是通過早熟擾動策略，使算法陷入局部最優(yōu)的概率降低。三黑洞系統捕獲策略和多維隨機干擾策略的存在使得算法具備了獨立的全局搜索與局部搜索機制，并通過協調因子使算法由全局搜索向局部搜索的漸進式轉變?；诘湫蜏y試函數的仿真結果表明，在單峰函數和多峰函數中，MSPSO 算法的尋優(yōu)能力和收斂速度均明顯優(yōu)于其他改進算法。

1 粒子群優(yōu)化算法及其缺陷

1.1 粒子群優(yōu)化算法

在PSO 算法中，粒子通過學習自身經歷（個體最優(yōu)pbest）與社會經歷（全局最優(yōu)gbest），改變自身飛行的速度和方向，以達到尋優(yōu)目的。

假設在D維的搜索空間中，種群大小為N。其中，第i個粒子的位置Xi=(xi,1,xi,2,…,xi,D)和速度Vi=(vi,1,vi,2,…,vi,D)的更新公式為：

其中，vi,d(t+1)和xi,d(t+1)分別為第i個粒子的第d維在第t+1 代的速度和位置，w為慣性權重，c1和c2為學習系數，r1和r2為[0，1]間均勻分布的隨機數。

為有效調節(jié)算法的全局搜索與局部搜索能力，w線性降低[20]被廣泛應用：

其中，t為當前迭代次數，T為總迭代次數，wmax、wmin分別為最大權重、最小權重。

1.2 粒子群優(yōu)化算法的缺陷

對于PSO算法的缺陷，通過Schwefel測試函數進行說明，該函數表達式為：

Schwefel 是一個典型的多峰函數，具有欺騙性，在x=（420.968 7，…，420.968 7）處取得全局最優(yōu)，但這測試函數有多個局部最優(yōu)，且全局最優(yōu)距離局部最優(yōu)很遠，一旦陷入局部最優(yōu)極難逃脫。

算法測試時，wmax=0.9,wmin=0.4，w按照式（2）調整，c1=c2=2，T=1 000，N=40,D=2。執(zhí)行算法后得到每個粒子在每一代的位置分布，如圖1、2所示。

圖1 PSO算法下的粒子位置分布

圖2 PSO算法下x1 隨迭代次數增加的位置分布

由圖1可見，在PSO算法下粒子主要集中分布在搜索范圍的右端偏上區(qū)域，對于可能存在最優(yōu)解的區(qū)域未能進行有效的搜索，種群多樣性較差。由圖2 可見，隨著迭代次數的增加，所有粒子逐步向x1=200 附近聚集，由于后期全局搜索能力減弱以致無法跳出局部最優(yōu)。

為了考察PSO算法在不同維度下的尋優(yōu)能力，圖3給出了當D=2～15 時，對Schwefel 測試函數獨立運行30次，PSO算法尋優(yōu)結果箱線圖。

圖3 PSO算法尋優(yōu)結果箱線圖

由圖3 可見，D≥3 時，PSO 算法已經難以收斂，且收斂性隨著維數增加越來越差，主要原因為：

（1）PSO算法的更新公式決定了全局搜索與局部搜索能力相互制約，無法發(fā)揮各自更好的作用。

（2）PSO 算法在迭代后期全局搜索能力逐步喪失，一旦陷入局部最優(yōu)，便難以逃脫局部最優(yōu)。

2 多策略粒子群優(yōu)化算法

2.1 三黑洞系統捕獲策略

宇宙星系合并過程中會產生多個雙黑洞系統，若雙黑洞系統的壽命足夠長，將會與其他星系發(fā)生合并，出現三黑洞系統[21-22]。三黑洞相互作用[23]，且由于引力的存在，微粒有一定概率被黑洞系統捕獲。受此啟發(fā)，將三黑洞系統捕獲微粒機理引入PSO算法，拓寬粒子搜索的區(qū)域，以增強全局搜索能力。

如圖4所示，設常數閾值p∈[0，1]作為三黑洞系統捕獲粒子xi的概率。對于每一粒子xi每次迭代產生一隨機數l∈[0，1]，若l≤p，則xi被三黑洞系統捕獲，否則按傳統方式進行更新。

圖4 粒子位置更新示意圖

若xi被三黑洞系統捕獲后，分別以gbest、(gbest+xmax)/2 和(gbest+xmin)/2 為中心，r為黑洞半徑，形成三黑洞區(qū)域。產生一隨機數l1∈[0，1]。若l1＞p1，則xi被系統中黑洞1捕獲；若l1∈[p2,p1]，則xi被黑洞2捕獲；若l1＜p2，則xi被黑洞3捕獲，被捕獲后的粒子位置為：

其中，xmax/xmin為粒子搜索區(qū)域的上/下限，常數閾值p1,p2∈[0，1]，且p1＞p2，r3為[-1，1]的隨機數。

2.2 多維隨機干擾策略

當環(huán)境發(fā)生改變時，植物能改變形態(tài)和發(fā)展性狀等，即植物的可塑性[24]。環(huán)境微小變化對植物的微小隨機干擾，可以糾正自身發(fā)育誤差，即發(fā)育渠化作用[25]。可塑性和發(fā)育渠化作用相結合，提高了植物對環(huán)境的適應性和植物發(fā)育的穩(wěn)定性。受此啟發(fā)，引入多維隨機干擾機制保證搜索的小幅度變動，以提高局部搜索能力。

設常數閾值pp∈[0，1]，對每一粒子的每一維產生一隨機數k∈[0，1]，若k≤pp，則采取干擾策略：

其中，φ為干擾程度，r4為[-1，1]的隨機數。

2.3 早熟擾動策略

當滿足式（6）時，重置粒子的位置，使其隨機分布在gbest附近，從而潛在地跳出局部最優(yōu)，即：

其中，Fg(t)/Fg(t-1)分別為第t/t-1 代全局最優(yōu)對應的函數值，ra為[-1，1]的隨機數。

2.4 全局與局部搜索能力的協調

在迭代前期，為拓寬搜索區(qū)域及增強種群多樣性，需要較強的全局搜索能力；在迭代后期，為搜索的細致及提高算法的計算精度，需要較強的局部搜索能力。通過協調因子ε調節(jié)全局搜索能力與局部搜索能力，即：

其中，t為當前迭代次數，T為總迭代次數。

MSPSO算法選擇策略方式為：每一粒子xi產生[0，1]的隨機數m，若ε＞m，則選擇三黑洞系統捕獲策略，否則選擇多維隨機干擾策略。

隨著迭代次數增加，ε從1 非線性地減小至0.368。在迭代前期，大多數粒子選擇三黑洞系統捕獲策略，使得全局搜索能力較強，提高種群多樣性；在迭代后期，大多數粒子選擇多維隨機干擾策略，使得局部搜索能力，提高了計算精度。同時，局部搜索能力隨著迭代次數的增加而增強，完成了從全局搜索向局部搜索的轉變。

2.5 算法流程

MSPSO算法流程如圖5所示，具體步驟如下：

步驟1 設置N、T、D，粒子的搜索區(qū)域[Xmin,Xmax]和速度限制[Vmin,Vmax]，隨機初始化粒子的位置和速度、個體最優(yōu)pbest和全局最優(yōu)gbest，令t=1。

步驟2 按式（8）計算ε。

步驟3 為每一粒子產生一隨機數m。

步驟4 若ε＞m，則轉步驟5；否則轉步驟6。

步驟5 為每一粒子產生一隨機數l，若l≤p，則按式（4）更新粒子；否則按式（1）更新粒子。

步驟6 按式（5）更新粒子。

步驟7 計算粒子對應的函數值，更新個體最優(yōu)pbest和個體最優(yōu)對應的函數值、全局最優(yōu)gbest和全局最優(yōu)對應的函數值。

步驟8 按式（6）判斷是否出現早熟，若早熟，則轉步驟9；否則轉步驟10。

步驟9 按式（7）進行早熟擾動。

步驟10 若t≥T，則輸出當前全局最優(yōu)解；否則t=t+1，返回步驟2。

圖5 多策略粒子群優(yōu)化算法流程圖

2.6 MSPSO算法性能分析

同樣通過對Schwefel函數進行測試來說明MSPSO算法的特點。算法測試時，r=0.1,φ=0.05,p=0.35,p1=0.8,p2=0.2，其他參數與1.2 節(jié)一致。執(zhí)行算法后得到每個粒子在每一代的位置分布，如圖6、圖7所示。

由圖6 可見，MSPSO 算法比PSO 算法的多樣性更好，由于搜索邊界和歷史最優(yōu)粒子近似關于原點對稱，導致三黑洞系統捕獲策略生成的粒子主要集中在搜索范圍的對角線上；由于多維隨機干擾策略的細致搜索，使得在全局最優(yōu)解附近的粒子占多數。由圖7可見，隨著迭代次數的增加，粒子呈現出聚集和分散兩種狀態(tài)，即全局搜索和局部搜索，說明在協調因子ε的作用下，在迭代過程中始終存在全局搜索和局部搜索。

圖6 MSPSO算法下的粒子位置分布

圖7 MSPSO算法下x1 隨迭代次數增加的位置分布

如圖8所示為MSPSO算法在2～15維下，對Schwefel測試函數獨立運行30 次尋優(yōu)結果的箱線圖?？梢?，MSPSO算法隨著維度增加，仍具有較強的收斂精度，其收斂精度高出PSO算法6個數量級。

圖8 MSPSO算法尋優(yōu)結果箱線圖

為了進一步考察算法的全局搜索能力和局部搜索能力及跳出早熟的能力，圖9給出了在Schwefel函數下MSPSO算法的尋優(yōu)性能。

由圖9 可見，通過協調因子ε使得迭代前期較多粒子選擇三黑洞系統捕獲策略，而迭代后期較多粒子選擇多維隨機干擾策略，即前期具備較強的全局搜索能力，后期具備較強的局部搜索能力。且在迭代過程中有781代采用了早熟擾動策略，粒子跳出局部能力較強，大幅度地降低了種群陷入早熟收斂的概率。

圖9 MSPSO算法全局搜索能力和局部搜索能力

2.7 MSPSO算法復雜度

PSO 算法的時間復雜度主要為粒子速度與位置的更新，其時間復雜度為O(N×D×T)。對于MSPSO 算法，與PSO 算法的差異，主要是采用不同的更新策略及加入早熟擾動策略，更新策略和早熟擾動策略的時間復雜度分別為O(N×D×T)和O(T)，與PSO 算法的時間復雜度大致相同。

PSO算法的空間復雜度主要為所有粒子的存儲，其空間復雜度為O(N×D)。MSPSO算法主要是由于采用不同策略，增加了幾個隨機數（即文中m、l、l1、k）存儲，其空間復雜度為O(1)，與PSO 算法的空間復雜度大致相同。

3 仿真實驗與結果分析

3.1 實驗設計

為驗證MSPSO 算法的收斂性能，將其與改進算法結構策略的PSO算法[20]和PSOCF算法[26]、新進化策略的RBHPSO 算法[27]、智能算法融合的ILSPSO 算法[28]和MPSO 算法[29]進行對比，并選取如表1 所示的9 個典型的函數進行測試。仿真實驗時，各算法的粒子移動速度范圍與搜索范圍一致，T=1 000,N=40,D=30。各算法其他參數設置如下所示。

（1）PSO 算法：wmax=0.9,wmin=0.4，慣性權重線性下降，c1=c2=2。

（2）PSOCF算法：c1=c2=2.05，收縮因子φ=0.729。

（3）RBHPSO 算法：w和c1、c2與PSO 算法一致，p=0.1,r=0.01。

（4）ILSPSO算法：學習因子c=2，可調參數χ=0.95。

（5）MPSO 算法：采用標準PSO 算法時，w和c1、c2與PSO算法一致，采用帶壓縮因子PSO算法時，φ和c1、c2與PSOCF算法一致。

（6）MSPSO算法：w與PSO算法一致，最大學習系數c1max=2.5 ，c2max=2.5 ，最小學習系數c1min=0.5 ，c2min=0.5，c1線性降低，c2線性增加，r=0.1,φ=0.05。

表1 典型測試函數

3.2 常數閾值的選取

3.2.1 三黑洞系統捕獲策略的p、p1、p2

在三黑洞系統捕獲策略中，p、p1、p2的不同取值將影響算法的全局搜索能力。三黑洞系統捕獲的概率p越大，表示能更有效地拓寬粒子的搜索區(qū)域，但p的取值過大將導致粒子分散程度較大，不利于收斂。當粒子被系統捕獲后，黑洞1 和3 的主要作用是搜索遠離歷史最優(yōu)解的潛在最優(yōu)粒子，故而黑洞1 和黑洞3 的捕獲概率相同，即1-p1=p2。

設置以下幾組取值，在其他參數相同的情況下進行實驗對比，由于f2～f8尋優(yōu)結果相差較小，故表2 為f1、f9函數在30 次獨立運行下的尋優(yōu)結果平均值。由表2可看出，當p=0.35,p1=0.8,p2=0.2 時，算法尋優(yōu)效果最好，故p、p1、p2分別取為0.35、0.8、0.2。

表2 p、p1、p2 不同取值下的對比

3.2.2 多維隨機干擾策略的pp

在多維隨機干擾策略中，pp的不同取值將影響算法的局部搜索能力。在搜索后期，pp越大能保證粒子的干擾能力越強，能夠有效地避免粒子因聚集程度大而導致對狹小的區(qū)域進行過度搜索。

設置以下幾組取值，在其他參數相同的情況下進行實驗對比，表3為f1、f9函數在30次獨立運行下的尋優(yōu)結果平均值。由表3可看出，當pp=0.35，時，算法尋優(yōu)效果最好，故pp取為0.35。

3.3 固定迭代次數下算法的收斂精度和運算時間

各算法均獨立運行30次，從算法尋優(yōu)的平均值、最優(yōu)值、方差及平均時間評估算法性能，實驗結果如表4所示。為便于展示，將各測試函數的平均值分別取以10為底的對數，各測試函數曲線如圖10所示。此外，將計算結果低于10-300的值默認為0。

從收斂精度看：在單峰函數f2～f5，MSPSO算法收斂精度顯著高于其他5 種算法，高出上百個數量級；在多峰函數f6～f8中，MSPSO 算法與MPSO 算法收斂精度大致相同，高出其他4 種算法至少10 個數量級；在單峰病態(tài)函數f1和多峰欺騙函數f9中，MSPSO算法的收斂精度高于其他5種算法，但收斂精度較低。分析其原因：MSPSO算法在迭代前期，大多數粒子采用三黑洞系統捕獲策略，使得粒子在拓寬搜索區(qū)域的同時，能不斷地靠近最優(yōu)解，致使MSPSO 算法相較于其他算法均在500 代之前取得更高收斂精度，如圖10（a）～（i）所示；在迭代后期，大多數粒子采用多維隨機干擾策略，使得粒子的位置小幅度變動，搜索變得更加細致，致使MSPSO算法在500代之后的收斂精度進一步提升，如圖10（b）、（c）、（e）所示；對于易陷入局部最優(yōu)解的f1和f9，在整個迭代過程中一直存在的早熟擾動策略使陷入局部最優(yōu)的粒子不斷跳出，導致迭代曲線一直變化，如圖10（a）、（i）所示。

表3 pp 不同取值下的對比

表4 尋優(yōu)結果

從收斂速度看：在f1～f9中，MSPSO 算法比智能算法融合的ILSPSO算法和MPSO算法運算時間短，且與其他算法運算時間相差不大。分析其原因：MSPSO 算法相比于PSO算法，僅是迭代過程中不同更新策略的選取。

因此，在相同迭代次數下，MSPSO算法具備更好的尋優(yōu)能力。

圖10 測試函數曲線

表5 平均迭代次數和成功率

3.4 固定精度下算法的平均迭代次數和成功率

在給定精度下，比較各算法均獨立運行30 次后的平均迭代次數及成功率，如表5所示。平均迭代次數是指達到給定精度下的迭代次數的平均值，其中，“—”表示超過最大迭代次數時仍未達到給定精度；成功率是指達到給定精度的次數除以總次數。

從成功率看：在f2～f8中，MSPSO算法均能達到給定精度；在病態(tài)函數f1和欺騙函數f9中，相對于其他5種算法來看，MSPSO算法成功率最大。

從平均迭代次數看：在f1～f9中，MSPSO 算法所需的迭代次數均是最小。

因此，在給定精度下，MSPSO算法具備更快的收斂速度。

4 結束語

針對PSO 算法易于陷入局部最優(yōu)及收斂速度較慢的問題，本文提出了一種多策略融合的粒子群優(yōu)化算法（MSPSO）。三黑洞系統捕獲策略的采用拓寬了粒子的搜索區(qū)域，全局搜索能力加強，提高了種群多樣性；多維隨機干擾策略的引入使粒子搜索更加仔細，局部搜索能力加強，提高了種群尋優(yōu)精度；并利用協調因子使算法從全局搜索向局部搜索轉變，提高了收斂速度；同時，在搜索進程中，早熟擾動策略有效地降低了算法陷入局部最優(yōu)的概率。由算法性能測試和對比分析可見，較其他5 種PSO 算法，MSPSO 算法在尋優(yōu)能力、收斂速度均有較為明顯提升，在優(yōu)化問題領域中具有良好的應用前景。如何進一步提高MSPSO 算法在病態(tài)函數、欺騙函數中的收斂精度，是今后需要研究的方向。