基于中心位的粒子群優化算法

張淵博 鄒德旋 張春韻 杜星瀚

摘? 要： 針對粒子群優化算法（Particle Swarm Optimization，簡稱PSO）容易陷入局部極值、進化后期的收斂速度慢和精度低等缺點，提出了基于中心位的粒子群優化算法（Particle swarm optimization algorithm based on center particle，簡稱CPPSO）。該算法采取雙策略更新粒子位置，一種通過隨機慣性權重作用的粒子和影響算子作用的個體極值、全局極值來更新粒子位置，另一種在之前更新的粒子位置基礎上，通過中心位采用差分算法來更新粒子位置。通過和其他3種優化算法在18個典型基準函數的仿真測試結果表明，該算法具有更好的全局收斂能力，其收斂速度、尋優精度和穩定性都有明顯的提升。

關鍵詞： 粒子群優化算法; 隨機慣性權重; 簡化粒子群優化方程; 影響算子; 中心位; 基準函數

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2021）12-22-05

Abstract： Aiming at the shortcomings of particle swarm optimization （PSO）， such as prone to fall into local extreme values， slow convergence speed and low accuracy in the later stage of evolution， a particle swarm optimization algorithm based on the central particle （CPPSO） is proposed. The algorithm adopts two strategies to update the particle position. One is to update the particle position through the particles affected by stochastic inertia weight and the individual extreme value and global extreme value affected by the influence operator; the other is to update the particle position by using the difference algorithm through the center position based on the previously updated particle position. Simulation test results of 18 benchmark functions with other 3 optimization algorithms show that the proposed algorithm has better global convergence ability， and the accuracy， speed and stability of convergence are significantly improved.

Key words： particle swarm optimization algorithm; stochastic inertia weight; simplified particle swarm optimization equations;influence factor; center position; benchmark function

0 引言

粒子群算法（PSO）是由Kennedy和Eberhart[1，2]在1995年提出的。由于其結構簡單、計算量小，粒子群算法已被廣泛應用于求解大范圍優化問題[3]。該算法已成功應用于解決許多實際優化問題，如路徑規劃[4]、柔性作業車間調度[5]、特征選擇[6]、深度神經網絡[7]等。粒子群優化算法雖然原理簡單、易于實現、收斂速度快，但仍存在收斂過早、全局搜索能力差等缺點。為了提高粒子群算法的優化性能，許多學者提出了各種各樣的粒子群算法變體。這些算法可分為兩大類：自適應粒子群算法和混合算法。

自適應粒子群算法主要是對粒子群算法公式進行改進和更新。在后來的研究中實施了一種自我調節權重來調整最佳粒子以改善勘探。其中，張鑫[8]提出的自適應簡化粒子群優化算法（Self-Adjusted Simplified Particle Swarm Optimization，簡稱SASPSO），在每代更新時，通過權重以及全局極值引導來更新位置，并加入鎖定因子，使全局歷史最優解有規律地引導粒子位置更新。改進慣性權重公式，令其根據當前粒子位置做出自適應配置。不論速度還是精度都得到了提高。趙國新[9]提出的混合自適應量子粒子群優化算法（Hybrid Adaptive Quantum Particle Swarm Optimization，簡稱HAQPSO），使用收縮—擴張系數隨著粒子的適應度值的改變而自適應調整;利用Levy飛行策略的偶爾長距離的跳躍，使得種群多樣性增加，提高了跳出局部最優的能力。在Rosenbrock函數問題上得到了很大改進。

混合算法的重點是結合不同算法的優點，來提高粒子的搜索能力。許多學者在這方面做出了突出研究，其中，易文周[10]提出一種結合粒子群和差分演化的兩階段算法，前期用粒子群算法進行全局搜索，后期用差分演化算法進行局部搜索，發揮兩種算法的優點而避開各自的短處。李俊[11]提出了一種基于異維變異的差分混合粒子群算法，首先，使用熵度量初始化粒子;其次引入異維變異學習策略和維度因子以引導粒子及時跳出局部極值達到最優解。但是迭代次數很大，有較長的運行時間。

雖然改進的優化算法眾多，方法獨特，但針對粒子群優化算法快速逃脫局部最優到達理論值的研究仍是值得的。本文采取雙策略更新粒子位置，一種通過隨機慣性權重作用的粒子和影響算子作用的個體極值、全局極值更新粒子位置，另一種在之前更新的粒子位置基礎上，通過中心位采用差分算法更新粒子位置。從而比較兩者新粒子的適應度，進而選擇好的位置迭代尋優。最后改進算法通過和其他三種優化算法在用18個典型基準函數的仿真測試。

1 基本粒子群優化算法

在PSO中，每個粒子代表多維空間中的一個點，其當前位置用[xtid]表示，其中[i]為單個粒子，[t]為迭代次數。每個粒子的初始位置到目前為止最優解用[pid]表示。算法跟蹤的另一個值是全局最優解[pgd]。粒子速度[vt+1id]為每次迭代[t]時粒子位置的變化。簡而言之，粒子群優化算法使試圖通過更新粒子的速度，使其朝著自身最優解和全局最優解的方向加速。[vtid]和[xtid]都是迭代更新的分別通過以下兩個方程：

其中，認知因子[c1]和社會因子[c2]統稱為加速系數。[r1]和[r2]是第[t]次迭代生成[（0≤rand≤1）]的隨機數，[N]表示種群的大小。[ω]為權重，粒子速度更新方程中存在三個矢量分量;即動量向量，認知或個人成分和社會或全局成分。

2 改進的粒子群算法

2.1 簡化粒子群算法

胡旺[12]提出一種簡化粒子群優化算法，在原始粒子群算法上，舍去速度項，由個體極值、全局極值和權重共同更新粒子位置，本文在此基礎上，提出影響算子，并且加入隨機慣性權重更新粒子位置。迭代公式如下：

其中右邊的第1項為“歷史”部分，表示過去對現在的影響，通過[ω]來調節影響程度;第2項為“認知”部分，表示粒子對自身的思考;第3項為“社會”部分，表示與鄰居粒子的比較和模仿，實現粒子間的信息共享以及合作。其中影響算子[e1，e2]表示為：

影響算子能夠有效的改變兩種極值對粒子位置的更新，并且平衡個體極值與全局極值。粒子的更新前期受個體極值影響大，使粒子快速找到相對較好的位置，尋優中期，一部分粒子向全局最優值靠近，一部分粒子繼續搜尋更好的位置點，迭代次數達到后期時，所有粒子向全局最優值靠近，使粒子得到更好的收斂。

2.2 隨機慣性權重

慣性權重[ω]是粒子位置更新中重要的參數之一。它起到了一個平衡全局搜索能力和局部搜索能力的作用，恰當的[ω]值可以提高尋優能力，減少迭代次數。本文提出隨機慣性權重，表示為：

式中[r]為[（0，1）]之間的隨機數;[t]為當前迭代次數;[T]為最大迭代次數;[i]為第[i]個粒子。改進的權重的特性是隨迭代次數非線性下降的，使算法具備逃脫局部最優的能力。在后期較小慣性權重，有利于提高局部搜索能力。

3 改進的差分進化算法

差分進化（Differential Evolution，DE）算法是由Storn和Price[13]這二位科學家在1995年提出的一種基于遺傳算法的啟發式隨機搜索算法，具有結構簡單、容易實現、收斂速度快、魯棒性強等優點。本文基于差分進化的變異操作進行改進，改進的公式如下：

式⑺通過中心位與變量[G]隨機地生成粒子的一維信息進行差分進化，以達到跳出局部最優的效果。其中[qtid]為采用差分算法更新的新位置，[F]為縮放因子，[xtid]為采用公式⑷更新后的粒子位置。[F]和[G]計算公式如下：

其中[r]為（0，1）的隨機數，[t]為當前迭代次數，[T]為最大迭代次數，為了跳出局部最優值，本文基于文獻[14]設計一種中心位，跳出局部最優，中心位表示為：

算法實現步驟如下。

Step1 設置最大迭代次數、種群數量、影響算子，初始化種群位置，慣性權重。

Step2 根據適應度函數計算出粒子的適應度。

Step3 比較找出個體極值[Pbest]與全局極值[Gbest]。

Step4 根據式⑷，⑸，⑹，分別計算出影響算子[e1，e2]和慣性權重[ω]。

Step5 根據式⑶更新粒子位置。

Step6 根據式⑺更新出新的粒子位置。

Step7 計算兩種粒子的適應度值，更新兩種極值。

Step8 判斷是否滿足終止條件，若滿足執行Step9，否則轉到Step4。

Step9 輸出全局極值[Gbest]。

4 仿真實驗

4.1 測試函數

為了檢驗算法CPPSO的有效性，用18個標準測試函數進行仿真對比，其中函數[f3、f4、f6、f9、f12-f18]為單峰測試函數，函數[f11]在低維情況下為單峰，高維情況下為多峰，[f1、f2、f5、f7、f8、f10]為多峰函數，[f8、f11]為病態的二次函數。測試函數見表1。

4.2 實驗參數與測試結果

本文算法的參數設置如下：粒子種群數目40個，粒子維數30維，最大迭代次數為100，每個測試函數算法運行30次，將適應度值取以10為底對數值表示。兩種算法的實驗數據對比結果見表2。

從表2可以看出，對于測試函數，CPPSO算法基本上優于SASPSO算法，除了[f8]、[f12]的最小值，CPPSO劣于SASPSO，其標準差都比SASPSO小。[f11]函數搜尋最優解極為困難，但CPPSO算法搜尋到了SASPSO算法難以達到的比較好的解。雖然實驗結果中[f1、f2、f9、f12]和[f13、f14]相差不是很大，但是[f2、f3、f6、f15、f16、f18]測試函數結果，無論是最小值、平均值，還是標準差，相比SASPSO算法都能搜尋到更準確穩定的解。而且CPPSO算法搜索到[f4、f5、f7、f10]的理論解。

圖1-圖4是[f3、f8、f17、f18]典型的四個測試函數尋優30次平均適應度的迭代曲線，縱坐標是適應度對數值，可知，[f3、f8]的進化曲線在22代前已經穩定搜索到了比SASPSO算法較好的解。因為SASPSO算法只有全局極值引導的粒子更新，在一些多極值的函數尋優中容易陷入局部最優，導致尋優結果不精確，達不到理論值。CPPSO算法有影響算子作用的雙極值和中心位更新的位置信息，從而能夠及時地跳出局部最優。

4.3 算法性能分析

為進一步評價CPPSO算法的性能，對CPPSO算法與近兩年的新算法SASPSO、HAQPSO，以及動態調整慣性權重的粒子群算法（A particle swarm optimization algorithm that dynamically adjusts the weight of inertia，PSO-I）[15]算法在100維下進行30次實驗分析。在18個測試函數中找到具有代表性的[f1、f3、f8、f11、f17、f18]六個典型測試函數實驗。

從表3可知，CPPSO算法無論是最小值、平均值，還是方差都比其他三種算法優秀，除了[f8]，SASPSO算法搜索到了理論解，但很不穩定。維數的增加提高了算法尋優的復雜度，而對CPPSO算法影響不大，通過六個典型的測試函數可知，粒子維數的增加，對算法尋優精確度影響不大。

5 結束語

本文針對粒子群優化算法在迭代的后期會出現種群多樣性不足導致易陷入局部最優的問題，提出三點改進，首先，加入影響算子隨迭代次數，平衡了局部和全局搜索能力，使算法能很好的搜尋到較好的最優值，然后通過隨機慣性權重更新粒子位置，使算法很好的從全局尋優過渡到局部尋優，最后采用中心位改變粒子位置，使算法逃脫了局部最優，并且是算法找了更好的解。通過18個測試函數的實驗結果和與參考文獻中的方法進行比較可得，CPPSO算法的表現較好，改進的方法提升了算法的全局搜索能力，提高了穩定性以及收斂的精度。但針對個別測試函數算法仍存在陷入局部最優的問題，之后研究應對該問題深入了解，運用不同的局部搜索方法增加算法收斂精度。

參考文獻（References）：

[1] Kennedy J，Eberhart R.Particle swarm optimization[C].Proceedings of 1995 IEEE International Conference on Neural Networks.Piscataway，NJ：IEEE Press，2002：1942-1948

[2] Shi Y，Eberhart R C.Empirical study of particle swarmoptimization[C].Proceedings of the 1999 Congress on Evolutionary Computation.Piscataway，NJ：IEEE Service Center，1999：1945-1950

[3] 邵晴.粒子群算法研究及其工程應用案例[D].吉林大學，2017.

[4] 陳嘉林，魏國亮，田昕.改進粒子群算法的移動機器人平滑路徑規劃[J].小型微型計算機系統，2019.40（12）：2550-2555

[5] 尉雅晨.改進粒子群算法研究及其在柔性車間調度問題中的應用[D].蘭州理工大學，2020.

[6] 鄧瀚浡.大規模粒子群算法及其在視頻流量特征選擇中的應用研究[D].濟南大學，2019.

[7] 黃榮煌.采用粒子群算法優化深度神經網絡壓縮的研究[D].廈門大學，2019.

[8] 張鑫，鄒德旋，肖鵬，喻秋.自適應簡化粒子群優化算法及其應用[J].計算機工程與應用，2019.55（8）：250-263

[9] 趙國新，陳志煉，魏戰紅.混合自適應量子粒子群優化算法[J].微電子學與計算機，2019.36（7）：76-80，86

[10] 易文周.基于差分演化和粒子群優化的改進WSN覆蓋算法[J].計算機與現代化，2019.8：33-38，62

[11] 李俊，羅陽坤，李波，李喬木.基于異維變異的差分混合粒子群算法[J].計算機科學，2018.45（5）：208-214

[12] 胡旺，李志蜀.一種更簡化而高效的粒子群優化算法[J].軟件學報，2007.4：861-868

[13] Storn R. Differrential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces[J].Technical report， International Computer Science Institute，1995.11.

[14] Xiaojing Y， Qingju J， Xinke L. Center Particle Swarm Optimization Algorithm[C].2019 IEEE 3rd Information Technology， Networking， Electronic and Automation Control Conference （ITNEC）.IEEE，2019：2084-2087

[15] 吳靜，羅楊.動態調整慣性權重的粒子群算法優化[J].計算機系統應用，2019.28（12）：184-188