具備預判能力和向最小距離學習的粒子群算法

舒小麗，劉衍民，張倩

（1.貴州民族大學數據科學與信息工程學院，貴陽 550025；2.遵義師范學院數學學院，遵義 563006；3.貴州大學數學與統計學院，貴陽 550025）

0 引言

粒子群算法［1］（PSO）是模擬了鳥類在群體中的捕食行為，它將群體中的鳥看作是無質量的粒子，通過群體中粒子之間的相互合作和信息交流來尋找最佳食物的位置。由于粒子群算法相對簡單，易于實現，且沒有太多的控制參數需要調節。1995年由Kennedy和Eberhart正式提出以來，吸引了眾多研究者對此進行研究。多次模擬實驗結果顯示，該算法對于解決大多數優化問題都有較好的優化效果。目前被應用于控制系統、預測時間、動態車輛路徑以及其他算法領域。但是，PSO算法在復雜的多峰問題上還存在多樣性差、易早熟收斂、精度低等一系列問題，為了解決這些問題，提升算法的運行效果，研究者們提出了許多該算法的改進。①參數改進：Kennedy等［2］人在1998年提出了線性慣性權重因子，改進了早期粒子群算法收斂性慢的問題；②拓撲結構：根據拓撲結構的不同對粒子群算法進行改進，比較經典的是分為局部的拓撲結構和全局拓撲結構，它們的差異是學習樣本的選擇不同，該方法對于不同的問題表現出不同的優化效果；③多群粒子群算法：VAN［3］和劉衍民［4］將種群分為多個種群，由種群之間信息共享，提高算法的運行效率，它們與原始的粒子群算法相比性能有顯著提高。

本文在研究者研究的基礎上，結合SHI［2］和張津源［5］提出了具備預判能力和向最小距離學習的粒子群算法。該算法中首先粒子根據每個粒子的個體極值對自己下一代的尋優做一個預判；其次，粒子的社會部分學習對象是從預判的方向上選取最小距離，這些策略可很大程度上提高粒子的尋優精度。

1 標準的粒子群算法

標準的粒子群算法與最先提出的粒子群算法相比，前者在速度更新時的記憶項中多了一個慣性權重，即w。w的大小影響著粒子的搜尋能力。當w較大時，具有很好的全局搜尋能力，而局部搜尋能力較弱；當w較小時，局部搜尋能力較強，全局搜尋能力較弱。因此，選擇合適的w值有助于平衡PSO算法的全局尋化能力和局部尋優化能力。PSO算法的速度和位置更新方程如下：

其中，a1、a2為學習因子；r1、r2為［0,1］中均勻分布的參數；Pit表示粒子i在尋優過程中時刻t經歷的最佳位置，稱為粒子的“自我認知項”。Gt表示尋優過程中群體在時刻t經歷的最好位置，稱為粒子的“群體認知項”，也稱為社會學習部分。

2 具備預判能力和向最小距離學習的粒子群算法

2.1 預判

在尋優過程中，PSO算法的粒子根據式（1）和式（2）更新其速度和位置。由于粒子在尋優過程中受個體極值和群體最優的整體指導，使得對粒子的每一維度過程的關注極少，特別在復雜的多峰問題上。又由于粒子在尋優過程中產生很大的隨機性，使得粒子收斂到最佳位置更加艱難。比如在群體尋優過程中：粒子剛開始運動的方向是向著群體最優解的方向前進的，但由于尋優過程的復雜性和隨機性，在進行到某代時可能會偏離最優解的方向，如若繼續使用式（1）更新速度，由于上一代錯誤信息的指導，必將導致收斂速度慢、精度不高等問題。

為解決這個問題，粒子在下一次更新迭代時會進行一個預判，即通過監督粒子在進化過程中的運動方向以及運動位置，對下一代實施干預，以防被錯誤信息指導。本文的預判策略是：首先規定個體極值的維度為正時是該維度較好的方向，反之，故粒子在下一次尋優時對各個粒子的個體極值每一維度進行預判，對維度為正的，則不改變方向，對維度為負的則改變該維度的方向。即面對個體極值中維度較差的方向時，則向反方向尋優。面對個體極值中維度較好的方向時，尋優方向不變。

2.2 具備預判能力和向最小距離學習的粒子群算法（MDPSO）

當前的研究者所做的研究中，種群速度更新的社會部分都采用了整個維度的更新策略。但在面對復雜的多維函數優化問題時，該方法可能會因為維間的相互干擾導致某些正確的尋優維度的信息被掩蓋。從文獻［3］推斷出，如果每個粒子速度更新都向群體最優學習，將會造成“steps foward，one step back”的現象。雖然下一代的函數值更好了，但可能有的維度信息比上一代更差了，這造成了好的維度信息的丟失。

根據粒子群算法的特點，個體極值既然是粒子歷史過程中經歷的最好的位置，并且全局最優也是從個體極值中挑選出來的，那么每個粒子的個體極值中都隱藏著較好的解的信息。又因為每個粒子的個體極值各不相同，在尋優時為群體提供了多種選擇。在以上實施預判的基礎上，粒子從每個粒子的個體極值中逐一挑選距離最小值作為粒子在該維度的學習對象。在每一維度都確定后，就組成了一個新的維度，稱為“最小距離”，用Z表示。由于新的Z是從每個個體極值的每一維度挑選出最小距離組成的。故該策略能有效的提高算法的尋優速度。新的學習策略速度更新如下：

2.3 MDPSO算法流程

MDPSO算法在尋優過程中，每個粒子根據個體極值與最小距離Z調整其飛行方向，并逐步逼近最優解。

（1）初始化種群，設置a1、a2和w，并計算其適應值。

（2）粒子實施預判，確保向正確的方向飛行，并找出Z。

（3）使用式（3）、式（2）更新粒子的速度與位置。

（4）更新個體極值和全局最優。每次迭代后，如果粒子當前位置的適應值小于該粒子歷史最佳位置的適應值，則用當前的位置更新個體極值，否則不更新；如果粒子當前位置的適應值小于群體最優位置的適應值，則用當前位置更新群體最優位置，否則不更新。

（5）如果沒有達到給定閾值，則返回（2），反之，算法結束。群體最優位置即是全局最優解。

2.4 算法的復雜性分析

為了研究MDPSO算法復雜度是否比PSO算法的更加復雜，用T表示最大的迭代次數，po p表示種群規模，D表示粒子的維數，MDPSO算法在PSO算法的基礎上給粒子增加了一個預判行為，并對算法中社會部分的學習做了調整。其中MDPSO算法的復雜度計算為K1=O（po p×D×T），PSO算法的復雜度計算為k2=O（pop×D×T）。由于K1=K2，故從以上的推導可得MDPSO算法與PSO算法的復雜度相比并無差別。

3 實驗設置與討論

3.1 檢測函數和算法的參數設置

本文選擇CEC2017年版中的檢測函數，具體如下：

Sum-of-different-power（F1），Zakharov（F2），High-condition-elliptic（F3），Ackley（F4），Rastrgin（F5），Expanded-sxhaffer-F6（F6），Bent-cigar（F7），Schaffer-f7（F8），Non-continypus-rataed-rastrigin（F9），Griewank（F10），并將MDPSO算法與5種具有代表性的改進PSO算法進行比較，這些算法分別 是：PSO1［2］、UPSO［6］、CLPSO［7］、CPSO［2］和wFIPS［8］。

為了使各算法的實驗結果對比顯著，本文實驗的相關數據設置如下：種群規模都為30，各算法在每個檢測函數上獨立運行30次，每個檢測函數每次運行6×104次函數評價，其他實驗相關參數與算法在提出時一致。

3.2 實驗結果及分析

3.2.1 收斂特性

為了展現各算法在上述參數設置下的收斂特性，圖1給出了這些算法在6×104次函數評價后的收斂特征曲線圖。

同時，為了檢驗各種算法運行結果之間的差異是否具有統計學意義，采用Wilcoxon秩和檢驗對MDPSO算法得到的結果與其他五種改進PSO算法中最好的一組結果進行檢驗。表1右側給出了檢驗結果。其中h=1表示運行結果有差異，h=0表示運行結果沒有差異。

表1 各算法實驗對比結果（平均值）

從表1和表2可以看出，本文提出的MDPSO算法在10個檢測函數上的性能表現相比其他5種PSO算法更加優秀。其中在函數F1、F3、F7、F8上表現較為明顯，函數的均值與其他的各種算法中最好的結果分別降低了97、58、59和30個數量級，說明MDPSO算法在改善粒子群的尋優能力較為顯著，在規避早熟問題上更加具有優勢。

表2 各算法實驗對比結果（最小值）

表1右側給出了Wilcoxon秩和檢驗結果分析。除F6外，其余5種改進的PSO算法中最好結果集與MDPSO算法的結果集的數據差異在95%置信區間內具有統計學意義。

從圖1可以看出，除Ackley函數外，MDPSO算法在逐漸尋優過程中取得了最好的運行效果。尤其對于Zakharov，Schaffer-f7從一開始就表現出明顯的優勢。這主要是預判行為找出了食物在每個維度上的較好方向，指導粒子向好的方向飛行，使粒子更容易找到較好的解。

圖1 檢測函數收斂特征圖

3.2.2 魯棒性分析

為了測試各種改進的PSO算法在不同的函數上運行是否具有穩定性，選擇了3個單峰函數（Zakharov，High-condition-elliptic和Ackley）和3個多峰函數（Bent-cigar，Schaffer-f7和Griewank）。根據表1與表2的數據可以看出，wFIPS與其他算法相比效果不明顯。所以表3給出了MDPSO與4種算法獨立運行60次的魯棒性分析結果，其中“FES”表示在算法達到給定閾值時的函數評價次數，“S”表示算法達到給定閾值的比例（單位：100%），各函數的閾值分別為1.81e+06、3.95e-04、3.7e-05、0.095、0.05和7.1e-05。

從表3可以看出：在單峰檢測函數中，對于Zakharov函數，僅僅只有MDPSO算法達到了給定閾值的比例是100%，但PSO和CLPSO也顯示了其較為穩定。對于Expanded-sxhaffer-F6函數，UPSO和MDPSO達到給定閾值的比例是100%，但MDPSO運用了較少的函數評價，另外PSO和CLPSO也顯示了其較為穩定。對于Ackley函數，PSO和MDPSO達到閾值的比例是100%，UPSO和CLPSO也顯示了其穩定性。在3個多峰函數中，僅僅只有MDPSO達到閾值的比例是100%。但UPSO在Bent-cigar也表現其穩定性，且CLPSO和CPSO在Schaffer-f7也表現了其穩定性。

表3 各種算法的魯棒性分析

從以上可知，不管從算法的收斂特性、尋優能力還是從算法的魯棒性分析結果看，MDPSO算法都表現出一定的優勢。

4 結語

為了解決由于PSO算法尋優過程中的隨機性和在更新時對粒子的整體指導而導致粒子在尋優過程中易早熟收斂、精度不高等問題。本文提出了MDPSO算法。該算法是由粒子預判出較好方向，再從個體極值中提取每個粒子的有效信息指導粒子的社會部分學習。并通過Wilcoxon秩和檢驗和基準函數尋優實驗表明，該算法不管在單峰函數還是多峰函數相比其他算法都表現出一定有效性和優越性。因此，MDPSO算法可以作為求解多峰和單峰問題的一種有效的方法。