基于中心位的粒子群優(yōu)化算法

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

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

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

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

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

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

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

1 基本粒子群優(yōu)化算法

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

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

2 改進的粒子群算法

2.1 簡化粒子群算法

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

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

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

2.2 隨機慣性權重

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

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

3 改進的差分進化算法

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

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

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

算法實現(xiàn)步驟如下。

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

Step2 根據(jù)適應度函數(shù)計算出粒子的適應度。

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

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

Step5 根據(jù)式⑶更新粒子位置。

Step6 根據(jù)式⑺更新出新的粒子位置。

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

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

Step9 輸出全局極值[Gbest]。

4 仿真實驗

4.1 測試函數(shù)

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

4.2 實驗參數(shù)與測試結果

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

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

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

4.3 算法性能分析

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

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

5 結束語

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

參考文獻（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] 陳嘉林，魏國亮，田昕.改進粒子群算法的移動機器人平滑路徑規(guī)劃[J].小型微型計算機系統(tǒng)，2019.40（12）：2550-2555

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

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

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

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

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

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

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

[12] 胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[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] 吳靜，羅楊.動態(tài)調整慣性權重的粒子群算法優(yōu)化[J].計算機系統(tǒng)應用，2019.28（12）：184-188