基于慣性權值非線性遞減的改進粒子群算法*

華 勇，王雙園，白國振，李炳初

(上海理工大學 機械工程學院，上海 200093)

0 引 言

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是由Eberhart和Kennedy于1995年提出的一種新的全局優(yōu)化算法[1]，它源自于對鳥類捕食行為的模擬。目前，PSO算法已經發(fā)展為一種通用的優(yōu)化進化算法，并被廣泛應用于神經網絡訓練、模糊系統(tǒng)控制、人工智能等領域[2-3]。但粒子群優(yōu)化算法始終存在著早熟收斂、收斂速度慢甚至不收斂等一系列問題，針對這些存在的問題，國內外眾多學者提出了許多改進策略，主要有以下3種策略：

(1)對粒子的速度和位置采用不同的參數策略來更新，如采用線性慣性權值動態(tài)變化策略[4-5]，使算法可以在迭代初期以較快的速度尋找到粒子最優(yōu)解的大致位置，隨著迭代的進行而慣性權重逐漸減小，粒子速度開始減慢，粒子開始進行局部高精度搜索。該策略的主要特點是速度和位置的更新由粒子自身經驗和群體經驗指導。

(2)引入變異策略。粒子群算法結合生物種群進化里的變異操作能夠提高算法的開拓尋優(yōu)能力，并能夠有效地克服收斂早熟。如采用柯西變異的策略[6]，以一定的概率選中粒子進行柯西變異，而未被選中的粒子則采用不同子群進化策略，可以有效地提高算法的收斂性能與效率。但變異策略也存在著諸多問題，何時變異及變異概率的確定等問題在實際求解問題中都難以確定。

(3)混合智能算法。粒子群算法結合其他算法，以達到優(yōu)勢互補的效果，可有效地提高算法的性能。如在粒子群算法中引入了雞群算法[7]，使得改進后的混合粒子群算法優(yōu)化在機器人路徑規(guī)劃中得到很好的應用。

在參考粒子群算法的各種改進策略基礎上，提出了一種基于自然選擇和慣性權值非線性遞減的粒子群算法。在算法的迭代過程中，粒子最大速度和慣性權值非線性遞減以保證粒子的全局尋優(yōu)能力與局部能力相互平衡，權重控制因子的調整可以保證最大慣性權值與最小慣性權值在種群進化過程中所占的比例；為了提高算法進化過程中種群的多樣性，引入二階振蕩策略，考慮粒子群算法的適用性問題，進一步地將遺傳算法中的自然選擇機制加入其中，有效地提高算法的尋優(yōu)精度。基準測試函數的仿真實驗結果表明，所提出的算法有效地克服了粒子群算法過早收斂和不收斂的問題，使粒子的尋優(yōu)能力和搜索精度得到顯著提升，相比于文獻[8]中所提出的改進粒子群算法，本文所提出的算法優(yōu)化性能更佳。

1 粒子群算法的基本原理

1.1 基本粒子群算法

粒子群優(yōu)化算法具有獨特的搜索機制，是受鳥群捕食行為的啟發(fā)而提出來的一種群體智能優(yōu)化算法。其關鍵在于每個粒子在解空間內根據自己的記憶和從其他粒子獲取的社會信息來更新自己的位置，通過個體之間的競爭與合作，實現在復雜空間中最優(yōu)解的尋找。該算法中每個問題的潛在解都是搜索空間中的一只鳥，也簡稱為粒子。該算法的數學理論描述為:設在一個D維搜索空間中，每個粒子是一個點，粒子規(guī)模為N，第i個粒子的位置矢量可以描述為xi=(xi1,xi2,…,xiD)，速度矢量可描述為vi=(vi1,vi2,…,viD)，第i個粒子搜索到的最優(yōu)位置為pi=(pi1,pi2,…,piD)，稱為個體極值，表示粒子的個體經驗；整個種群搜索到的最優(yōu)位置為pg=(pg1,pg2,…,pgD)，稱為全局極值，表示粒子的群體經驗。粒子的速度和位置更新公式如下:

(1)

其中，i=1,2,…,N，N為粒子規(guī)模；d=1,2,…,D，D為解空間的維數，即自變量的個數；w為慣性權重；c1為種群粒子的個體學習因子，c2為種群粒子的社會學習因子，分別用于調節(jié)粒子向個體極值與全局極值方向的最大步長，體現了粒子間的信息共享與合作；r1與r2為在[0,1]區(qū)間上均勻分布的兩個隨機數。

1.2 權重因子線性變化的粒子群算法LDWPSO

為了平衡全局搜索與局部搜索，在不同的搜索階段采用不同的慣性權重，即權重w隨著迭代次數的增加而線性減小，以使算法在搜索初期時擁有較大的慣性權重，有利于搜索整個解空間，不易陷入局部最優(yōu)值。而在搜索后期，種群擁有較小的慣性權重，有利于種群對局部進行精細化挖掘，使粒子可以較快地收斂于全局最優(yōu)值，其數學描述如式(2)所示[5]：

(2)

1.3 帶壓縮因子的粒子群算法CPSO

將標準粒子群算法中速度更新公式的每一項都與學習因子牽連起來，在一定程度上，粒子的自我學習價值與社會學習價值也能作用在速度慣性的變化上，其數學描述如式(3)所示[9-10]：

(3)

壓縮因子按照下式計算:

(4)

其中，φ=c1+c2，通常當c1=c2=2.05，λ=0.729時，算法具有較好的性能。

2 改進的粒子群算法MPSO

2.1 慣性權值非線性變化策略

慣性權重是PSO算法中極其重要的參數，它描述了粒子上一代速度對當前代速度的影響，控制其取值大小可有效地調節(jié)平衡PSO算法的全局與局部尋優(yōu)能力。當慣性權值較大時，全局尋優(yōu)能力較強，局部尋優(yōu)能力較弱；當慣性權重較小時，局部尋優(yōu)能力較強，而全局尋優(yōu)能力將減弱?？紤]切比雪夫濾波器幅頻響應曲線模型在線性和非線性行為之間表現出極好的過渡性，提出了一種基于切比雪夫濾波器慣性權重非線性變化策略，并引入權重控制因子，通過調節(jié)該控制因子的大小進而來調整最大慣性權值在種群進化過程中所占的比例，能夠保證粒子群在初始狀態(tài)時以較大的慣性權值進行全局開發(fā)性搜索，而在迭代后期又以較小的固定權值進行更為精細化的局部尋優(yōu)，其數學模型如式(5)所示:

(5)

其中，K為權重控制因子，t為種群當前進化代數，T為種群總的進化代數。在算法迭代初始，粒子的權值可以取得最大值0.95，有利于前期的全局搜索，而隨著迭代次數的增加，粒子的權值逐漸趨近最小值0.4，此時可以更好地進行局部精細化搜索。

2.2 粒子最大速度非線性遞減策略

粒子最大速度的設置非常重要，較大的速度有利于種群進行全局的開發(fā)，但粒子速度過大，會導致粒子在搜索的過程中錯過全局最優(yōu)解；與之相反，較小的速度有助于種群進行局部搜索，但速度過小，會導致粒子不能夠在解空間內進行充分探索，從而陷入局部最優(yōu)的可能性提高。為了進一步提高PSO算法的性能，防止因為粒子飛離搜索空間而造成種群多樣性減小，進而提出了一種粒子最大速度非線性遞減策略。粒子的最大速度在隨著種群迭代的進行過程中呈現非線性減小，可使粒子有效地避免因為過大的速度而落入邊界區(qū)域進行無效地搜索。粒子最大速度非線性遞減策略數學模型如式(6)所示：

(6)

其中，vmax與vmin分別為種群粒子最大速度的最大值與最小值，它們的取值由標準測試函數定義域確定。

2.3 自然選擇原理

考慮到PSO算法優(yōu)化性能會受到的隨機因素影響較多，為了提高算法的適用性，結合遺傳算法中的選擇思想，在上述幾種改進策略的基礎上加入自然選擇機制，其基本思想為每次迭代過程中將整個粒子群按照適應值的大小來進行排序，并用群體中適應值最好的一半的粒子的速度與位置來替換群體中適應值最差的一半的粒子的位置和速度，在這一過程中保留原來個體記憶的最優(yōu)值，來提高粒子接近最優(yōu)值的幾率。

2.4 粒子二階振蕩策略

粒子群算法在迭代過程中是呈現漸進收斂的，整個迭代過程中種群的多樣性勢必會有減小的趨勢，這不利于粒子尋求最優(yōu)解的幾率提高，在標準粒子群算法的基礎上，采用文獻[11]中所述的方法，對粒子速度更新進行二階振蕩處理，以進一步提高種群的多樣性，改善算法的全局與局部收斂平衡性能。其速度更新方程如下：

(7)

3 改進粒子群算法的流程

改進粒子群算法的主要實現步驟如下:

(1)設定各參數，初始化種群中各粒子的位置和速度；

(2)計算種群中每個粒子的適應度值，初始化種群個體最優(yōu)值和全局最優(yōu)值，將當前各粒子的位置和適應度值存儲在各個粒子的pi，將當前所有pbest中適應度值最優(yōu)個體的位置和適應度值存儲于pg中；

(3)根據式(5)對慣性權值進行更新；

(4)根據式(7)以及式(1)中的位置更新公式進行粒子的速度和位置更新；

(5)根據式(6)對粒子的最大速度進行更新，以保證算法的收斂性能；

(6)比較粒子適應度值與其經歷過的最好的位置進行比較，更新粒子當前的個體最優(yōu)值；

(7)比較粒子適應度值與種群全局極值，更新粒子當前的全局最優(yōu)值；

(8)將種群適應度值的大小進行排序，用群體中最好的一半的粒子的速度和位置替換最差的一半的粒子的速度和位置，同時把持種群中個體最優(yōu)值與全局最優(yōu)值記憶不變；

(9)若滿足迭代停止條件，則搜索結束；若不滿足迭代停止條件，則返回步驟(3)。

4 仿真實驗及結果分析

4.1 權重控制因子K的確定

首先設計了一個實驗，討論了所提算法慣性權值調整策略中權重控制因子K的取值。文獻[13]指出當較大的慣性權值在種群進化過程中所占比例超過二分之一迭代數時，將不利于保證解的精度，因為迭代后期主要是以粒子進行精細化搜索為主。針對此，改進算法采用30維Sphere函數對K從3～8的幾個不同取值的收斂結果進行比較，參數設計見表3所示。對應于K值的不同取值，文中改進算法都獨立運行20次，并計算其平均性能，實驗結果如表1所示。

表1 30維時不同K值對Sphere函數的實驗結果

從表1可以看出：當K=8的時候，算法的收斂性能最優(yōu)，其所達到的收斂精度與穩(wěn)定性也是最高的。這也證明了粒子群算法在迭代后期需要以較小的慣性權值進行局部精細化搜索的重要性。從表1中也可以看出，隨著K值的不斷增大，即較小的慣性權重值在種群進化過程中所占比重越大，文中改進算法搜索到的最優(yōu)解精度也隨之提高，但迭代次數都未有較大的波動，因此，在后面的仿真實驗設計中，文中改進算法的K值均取為8。

4.2 仿真試驗設計

為了對所提算法的性能進行分析和驗證，選取8個典型Benchmark測試函數來進行分析，將其測試結果與標準粒子群算法(PSO)、慣性權值線性變化的粒子群算法(LDWPSO)和帶壓縮因子的粒子群算法(CPSO)的測試結果進行比較,每個函數的參數設置如表2所示，每個算法的參數設置如表3所示?？紤]到算法每次運行的隨機性，對于每個測試函數所采用的不同優(yōu)化算法都重復獨立運行 30次，取所得最優(yōu)解的均值與方差作為最終的優(yōu)化結果。

表2 標準Benchmark測試函數參數設置

表3 各種算法的參數設置

由于篇幅有限，圖1—圖6給出了當維數D=30時該6個測試函數的平均最優(yōu)適應度值隨迭代次數的進化曲線。6個測試函數情況如式(8)—式(13)所示。

圖1 f1測試函數

圖2 f2測試函數

圖3 f3測試函數

圖4 f4測試函數

圖5 f5測試函數

圖6 f6測試函數

Sphere函數:

(8)

該函數是一個典型的單峰函數，在解空間上僅有一個極值點，當xi=0(i=1,2…)時取全局極小值0。

Rosenbrock函數:

(9)

該函數是一個非凸的病態(tài)多峰函數，雖然在解空間上有一個最小值點，但一般算法很難尋到最優(yōu)解，其全局極小值位于一個平滑且狹長的拋物線形山谷內。當xi=1(i=1,2…)時取全局極小值0。

Griewank函數:

(10)

該函數是一個多峰函數，存在許多局部極小值點，是一種典型的非線性多模態(tài)函數，當xi=0(i=1,2…)時取全局極小值0。

Quadric函數:

(11)

該函數是一個單峰函數，當xi=0(i=1,2…)時取全局極小值0。

Ackley函數:

(12)

該函數是一個多峰函數，當xi=0(i=1,2…)時取全局極小值0。

Rastrigin函數:

(13)

該函數是一個多峰函數，擁有大量局部極值點，也是一種典型的非線性多模態(tài)函數，當xi=0(i=1,2…)時取全局極小值0。

算法性能評估指標采用如下方法:固定進化最優(yōu)目標值，評估算法達到最優(yōu)目標值的成功率(Success Rate，SR)，評估方式為算法達到最優(yōu)目標值次數與算法執(zhí)行總次數的比值；固定進化代數，評估算法收斂時的平均迭代次數(Average Iteration Times，AIT)，以反映算法的收斂性能。本文認為算法所尋得的最優(yōu)值在連續(xù)2 000次迭代過程中沒有變化時，即認為算法進入了收斂狀態(tài)；固定進化代數，評估20次試驗所得最優(yōu)解的平均值(Mean)與最優(yōu)解的標準方差(Std)，以反映算法的搜索性能與搜索精度。

4.3 實驗結果及分析

表4列出了不同算法在6個測試函數中的性能指標，表5與表6分別給出了固定進化代數下求解6個測試函數時上述4種對比算法的最優(yōu)值、平均最優(yōu)值與最優(yōu)值方差結果。其中，“-”表示對應算法在迭代過程中未達到收斂條件，即在固定進化代數內該算法不能收斂。可以看出，所提出的MPSO算法與其他3種算法在收斂性能與搜索精度上有著顯著的差異，具體表現在:

(1)當測試函數為30維時，根據表4所列出的數據，對于上述全體測試函數，IMPSO算法的成功率都是100%，而不管對于單峰函數f1、f4還是多峰函數f2、f3、f5、f6，算法SPSO均未能達到理想目標值，成功率都是0。算法LDWPSO與算法CPSO在測試函數f1實驗中的成功率分別為0和10%，在測試函數f2實驗中的成功率分別為70%和90%，對于測試函數f3、f4、f5而言，這兩種算法也均未能達到理想目標值，其成功率均為0。對于具有大量局部極值點的測試函數f6而言，算法LDWPSO的成功率超過了50%，而算法CPSO則表現出成功率為0，但都次于算法IMPSO在每個測試函數實驗中所取得的成功率。結合測試函數為50維時的算法性能指標數據，能進一步地說明IMPSO算法不管是在單峰函數求解過程中，還是多峰高維函數求解過程中，其均能表現出自身的穩(wěn)定性優(yōu)勢。

表4 各優(yōu)化算法對每個測試函數的性能測試指標

(2)根據表5、表6可知：無論測試函數是30維還是50維，對于多峰函數f3、f6而言，算法IMPSO在每次進化過程中均能搜索到全局極小值點，比實驗所設定的理想目標值精度更高，而算法SPSO、LDWPSO、CPSO在多峰函數f3測試中，均未能達到理想目標值，對于多峰函數f6，只有算法LDWPSO能在不同維度的解空間中搜索到理想目標值，但其成功率不高，分別為10%、65%。對于單峰函數f1、f4，算法IMPSO在解空間中搜索到的最優(yōu)值對比于另外3種算法，差異更是明顯，且IMPSO算法在不同維度解空間中最優(yōu)值的標準方差遠遠小于另外3種算法，這也反映了IMPSO算法在單峰高維函數中的穩(wěn)定性。對于多峰函數f2和f5，算法IMPSO所搜索到的最優(yōu)解精度也遠遠高于其他三種算法。結合上述可看出，IMPSO算法具有更優(yōu)越的全局尋優(yōu)能力。

表5 30維時各優(yōu)化算法對每個測試函數的實驗結果

表6 50維時各優(yōu)化算法對每個測試函數的實驗結果

(3)根據表4所列出的AIT數據，結合圖1—圖6 所給出的不同算法在不同測試函數中平均最優(yōu)值進化曲線，可明顯地看出，除了在單峰函數f1與f4測試中，算法IMPSO在前期收斂速度慢于其他3種算法外，在其他4種測試函數中，算法IMPSO收斂速度均要優(yōu)于另外3種算法且均能進入收斂狀態(tài)，而另外3種算法在不同測試函數中都有表現出不收斂或者過早陷入局部最優(yōu)值而達到收斂的情形。

(4)從圖1—圖6可以看出：除了多峰函數f2對應的平均最優(yōu)值進化曲線在前500次迭代范圍時收斂速度最快外，其余五組測試函數的收斂速度均在迭代次數超過500次后才開始進入快速收斂狀態(tài)，這是因為當種群進化代數至500次時，種群粒子的慣性權值開始發(fā)生明顯的非線性遞減變化，對應的粒子將進行精細化搜索狀態(tài)，從而快速地靠近最優(yōu)值附近。而不同的測試函數，算法在其解空間內進行搜索時都具有一定的隨機性與動態(tài)性。

從實驗結果表4—表6和圖1—圖6可以看出：IMPSO算法在多峰、高維的空間中測試時，其優(yōu)化性能要優(yōu)于另外3種經典算法，但在單峰、高維的空間中測試時，所提算法也存在前期搜索速度較慢的缺陷。

5 結束語

在參照現有粒子群算法參數時變策略的基礎上，針對粒子群算法出現的早熟收斂和不收斂的問題，提出了一種基于自然選擇和慣性權值非線性遞減變化策略的改進粒子群算法，并提出了粒子最大速度非線性遞減策略，使得算法有較好的全局搜索與局部搜索的平衡能力?？紤]種群多樣性對粒子收斂性能的提高有較大影響，采用二階振蕩策略來保證算法收斂性能的同時，能夠在進化過程中有效地提高種群的多樣性。為提高粒子群算法局部精細尋優(yōu)的能力與適用性，在算法中引入自然選擇機理，這也符合無免費午餐定理，有效地提高了算法的魯棒性，使得算法具有更好的全局尋優(yōu)能力。通過與其他算法在測試函數上的尋優(yōu)分析對比，實驗結果表明，所提出的改進算法能夠解決基本粒子群算法在求解高維復雜多峰非線性優(yōu)化問題時出現的容易陷入局部最優(yōu)值以及不收斂的問題。

參考文獻(References):

[1] KENNEDY J，EBERHART R C.Particle Swarm Optimization[C]//Proc of IEEE Inernational Conference on Neural Networks,Piscataway:IEEE Service Center,1995:1942—1948

[2] AMR M I，NOHA H E.Particle Swarm Optimization Trained Recurrent Neural Network for Voltage Instability Prediction[J].Journal of Electrical Systems and Information Technology,2018(10):216—228

[3] DIEU T B，QUANG T B.A Hybrid Artificial Intelligence Approach Using GIS-based Neural-fuzzy Inference System and Particle Swarm Optimization for Forest Firesusceptibility Modeling at A Tropical Area[J].Agricultural and Forest Meteorology,2017(4):32—44

[4] SHI Y，EBERHART R C.Parameter Selection in Particle Swarm Optimization[C]//Proc of 7th International Conference on Evolutionary Programming Vii,Berlin:Springer-Verlag Press,1998:591—600

[5] SHI Y，EBERHART R C.A Modified Particle Swarm Optimizer[C]//Proc of IEEE International Conference on Evolutionary Computation,Piscataway:IEEE Press,1998:69—73

[6] 王永驥，蘇婷婷,劉磊.基于柯西變異的多策略協(xié)同進化粒子群算法[J].系統(tǒng)仿真學報，2018,30(8):2875—2883

WANG Y J，SU T T，LIU L.Multi-strategy Cooperative Evolutionary PSO Based on Cauchy Mutation Strategy[J].Journal of System Simulation,2018,30(8):2875—2883(in Chinese)

[7] 賈會群，魏仲慧,何昕,等.基于改進粒子群算法的路勁規(guī)劃[J].農業(yè)機械學報，2018,49(12):372—377

JIA H Q，WEI Z H，HE X，et al.Path Planning Based on Improved Particle Swarm Optimization Algorithm[J].Transactions of the Chinese Society for Agricultural Machinery,2018,49(12):372—377(in Chinese)

[8] 馬國慶，李瑞峰，劉麗.學習因子和時間因子隨權重調整的粒子群算法[J].計算機應用研究，2014,31(11):3292—3294

MA G Q，LI R F，LIU L.Particle Swarm Optimization Algorithm of learning Factors and Time Factor Adjusting to Weights[J].Application Research of Computers,2014,31(11):3292—3294(in Chinese)

[9] CLERC M，KENNEDY J.The Particle Swarm:Explosion,Stability and Convergence in A Multidimensional Complex Space[J].IEEE trans on Systems Man and Cybernetics,2002(6):58—73

[10] CLERC M.The Swarm and the Queen:Towards A Deterministic and Adaptation in Particle Swarm Optimization[C]//Proc of the 1999 Congress on Evolutionary Computation,Washington:IEEE Press,1999:1951—1957

[11] 龔純，王正林.精通Matlab最優(yōu)化計算[M].北京:電子工業(yè)出版社，2009:296—299

GONG C,WANG Z L.Optimal Calculation by Matlab[M].Beijing:Electronic Industry Press,2009(in Chinese)

[12] 胡建秀，曾建潮.二階振蕩微粒群算法[J].系統(tǒng)仿真學報,2007,19(5):997—999

HU J X，ZENG J C.Two-order Oscillating Particle Swarm Optimization[J].Journal of System Simulation,2007,19(5):997—999(in Chinese)

[13] 方群，徐青.基于改進粒子群算法的無人機三維航跡規(guī)劃[J].西北工業(yè)大學學報，2017,35(1):67—68

FANG Q，XU Q.3D Route Planning for UAV Based on Improved PSO Algorithm[J].Journal of Northwestern Polytechnical University,2017,35(1):67—68(in Chinese)