一種新的混合粒子群優化算法

徐生兵 蹇柯 夏文杰

摘 ?要：針對粒子群算法在進化后期收斂精度低、收斂速度慢，尤其是高維時候容易早熟等問題，提出了一種新的混合粒子群優化算法。新算法首先設計了一種新的慣性權重，使慣性權重取值在進化初期和后期都較為適中;其次，為了有效抑制粒子陷入局部極值，引入了粒子最優速度和最差適應值的概念，并以此為基礎，設計了粒子的一種新的自適應變異方式;最后引入了平均收斂率和最小平均收斂代數兩個概念，可以更好地評價和比較本文算法的性能。八個標準測試函數在100 維、200 維進行的數值實驗證實，新算法收斂精度高，收斂速度快，且有效預防了早熟現象。

關鍵詞：粒子群優化;慣性權重;早熟;變異

中圖分類號：TP183 ? ? 文獻標識碼：A

Algorithm of a New Hybrid Particle Swarm Optimization

XU Shengbing， JIAN Ke， XIA Wenjie

（School of Computer and Information， City College of Dongguan， Dongguan 523419， China）

xusb@ccdgut.edu.cn; jianke@ccdgut.edu.cn; xiawj@ccdgut.edu.cn

Abstract： This paper proposes a new hybrid particle swarm optimization algorithm to solve the problems of low convergence accuracy， slow convergence speed of particle swarm optimization algorithm in the late evolution stage， and being prone to mature early especially in the high-dimensional case. The new algorithm first proposes to design a new inertia weight， which makes the value selection of inertia weight moderate in the early and late evolution. Secondly， in order to effectively restrain the particles from falling into the local extreme value， the concepts of particle optimal velocity and the worst fitness of particles are introduced. Based on this， a new adaptive mutation method of particles is designed. Finally， the concepts of average convergence rate minimum average convergence algebra are introduced， which can better evaluate and compare the performance of the proposed algorithm. The numerical experiments of 8 standard test functions in 100 and 200 dimensions verify that the new algorithm has high convergence accuracy， fast convergence speed， and effectively prevents premature phenomenon.

Keywords： particle swarm optimization; inertia weight; premature; mutation

1 ? 引言（Introduction）

粒子群優化（PSO）算法是由Eberhart、Kenned于1995 年提出的一種基于種群智能行為的優化算法。由于其概念明確、需要設置的參數少、編程易于實現等優點，目前在工程領域已經得到廣泛的應用。但PSO算法在優化復雜函數問題時極易陷入局部極值，并且會出現早熟現象，這又限制了其進一步應用。為提高PSO算法的優化性能，許多學者提出了各種改進的PSO算法[1-10]。其中，在慣性權重方面，SHI等人[1]于1998 年首次引入了慣性權重的概念，并提出了一種線性遞減的權重策略（LDWPSO）;黃軒等人[2]提出了一種基于隨機慣量權重的快速PSO算法（Faster PSO with Random inertia weight，FRPSO），即慣性權重在0.4—0.6的隨機取值;LIANG等人[3]提出了一種利用種群質心和種群個體極值質心的PSO算法（PSO with Centroid，CPSO），使得粒子的更新不僅與傳統PSO算法中的個體極值和全局極值相關，而且還與種群中其他粒子的位置和個體極值相關。

2 ?標準粒子群算法（Standard particle swarm optimization algorithm ）

標準粒子群算法的數學描述過程如下：

在d 維搜索空間中，PSO算法首先初始化s 個隨機粒子，然后通過追蹤兩個極值（全局極值和個體極值）位置對粒子的位置進行更新，迭代運行直至滿足停機條件，最后輸出最優解。其中，在第t 代時，假設某個粒子的位置為，速度為，則第 代粒子的位置和速度分別為：

（1） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

其中，式（1）、式（2）分別稱為速度更新方程和位置更新方程;稱為慣性權重，表示對前一代速度的保留程度，一般取值范圍為;c1、c2稱為學習因子，一般取值為2.0;是之間均勻分布的隨機數;為粒子自身迄今為止找到的最好位置，即粒子的個體極值位置;為整個種群迄今為止找到的最好位置，即種群的全局極值位置。

上述的慣性權重是PSO算法的一個十分重要的參數。SHI等人通過大量的數值實驗表明：較大的慣性權重有利于全局搜索，而較小的慣性權重有利于局部搜索，因而可以在迭代初期設置一個較大的慣性權重，以便較為迅速地定位到一個較優的搜索區域;在迭代后期使用一個較小的慣性權重，以便在這個較優的區域進行局部搜索，進而搜索到更好的解。因此，SHI提出了一種慣性權重線性遞減（Linear-Decreased Weight， LDW）的策略，即：

（3）

其中，為最大慣性權重，為最小慣性權重，一般取，;為當前迭代次數;為總迭代次數。這樣，就會隨著迭代次數的增加而線性遞減。因此，使用式（3）權重策略的PSO算法被稱為慣性權重線性遞減的PSO算法，即LDWPSO算法。

3 ?一種新的混合粒子群優化算法（A new hybrid particle swarm optimization algorithm， NHPSO）

3.1 ? 一種新的慣性權重策略

由于慣性權重在PSO算法中可以控制算法的全局搜索能力和局部搜索能力，因此，關于慣性權重的研究已經取得了不少的進展[2，9]，其中文獻[2]經過大量數值實驗證實：慣性權重在0.4—0.6隨機取值時，其總體實驗效果要優于LDWPSO。與LDWPSO的慣性權重相比，FRPSO的特點是：初期慣性權重較小，后期慣性權重較大。但后期慣性權重較大是不利于粒子局部搜索的（這在文獻[7]FRPSO與LDWPSO的對比實驗中也可以看出來）。考慮到兩種權重的各自特點和實驗效果，本文構造了一種新的慣性權重，使其值在初期和后期均介于兩者之間，具體如下：

（4）

其中，，。

是一個變化范圍較小的慣性權重，其變化范圍約為[0.1，0.37]，且在迭代后期權重稍有回升;是一個非線性遞減的權重，其變化范圍約為[0.14，0.9]，這樣的變化范圍約為[0.15，0.67]。因此，與LDWPSO中的慣性權重相比，新慣性權重初期較小，后期稍大;與FRPSO慣性權重相比，新慣性權重初期稍大，后期較小，符合設計的初衷。三種權重的變化如圖1所示（以為例）。

3.2 ? 一種新的變異策略

PSO算法在陷入局部極值的時候，粒子之間的差異性很小，因此，讓部分粒子變異將使得算法有機會搜索到更好的解。本文利用粒子的速度信息和種群適應值的信息，構造了一種新的粒子位置的變異策略。為了敘述方便，先對粒子最優速度和最差適應值做如下定義：

定義1：PSO算法中，某個粒子在第代的最優速度

，表示粒子的初始速度。

定義2：PSO算法中，某個粒子在第代的最差適應值

，表示粒子的初始適應值。

那么，對粒子的變異操作是：

（5）

其中，表示粒子在第代的適應值;表示全局極值粒子的最優速度，表示整個種群的當前最優適應值，用來給一個速度擾動。由于是一個較大的數，因此粒子可以以很大概率遠離當前位置。選取哪些粒子變異也是提高PSO算法性能的關鍵，本文變異的準則如下：

設種群在第 代各粒子的適應值分別為，則第 代種群的平均適應值，粒子與絕對偏差，檢驗值。其中，為粒子的個體極值，為粒子個數。對每個需要進行變異粒子的選取準則是。為了有效防止粒子陷入局部極值和確保算法的穩定性，在每一次迭代中對每一個滿足準則且不是全局極值的粒子按式（5）進行變異操作。

3.3 ? NHPSO算法流程

NHPSO算法的計算流程與LDWPSO算法的計算流程基本一致，不同之處有：（1）需要計算初始化粒子的最優速度和最差適應值，在每次更新的時候也要更新粒子的最優速度和最差適應值;（2）在每一次迭代過程中，對滿足變異條件的粒子均要進行變異操作。NHPSO算法的計算流程圖如圖2所示。

4 ? 數值仿真實驗（Numerical simulation experiments）

4.1 ? 標準測試函數

在數值仿真實驗中，選取如表1所示的八個標準測試函數對LDWPSO、FRPSO、CPSO和NHPSO進行性能對比實驗。

上述測試函數的理論全局最優解均為0。其中，容易優化;低維容易優化，高維很難優化;的優化難度較大;優化難度最大，是典型的極難優化非凸病態函數，是帶有一定欺騙性的函數，因為全局最優與最好的局部最優相距很遠，因此搜索算法往往朝著錯誤的方向收斂，是一個最小化問題，一般的PSO算法極易陷入局部極值且極難優化。

4.2 ? 實驗參數設置及實驗方案設計

4.2.1 ? 實驗參數設置

在實驗中，所有算法的公共參數設置為：，為搜索區間長度的0.1，粒子的初始化區間為如表1所示的搜索區間，但的初始區間為[-300，300]。LDWPSO算法中，，;FRPSO和CPSO的參數設置均按參考文獻設置，且算法優化性能也與參考文獻一致。

4.2.2 ? 實驗方案設計

為了敘述方便，先給出算法平均收斂率和平均最小收斂代數的定義。

定義3：如果算法在指定代的運算中，最終優化結果，其中為預設精度，則稱該次算法收斂。若算法在次運算中，有次收斂，則平均收斂率。

定義4：當算法收斂時，第一次滿足預設精度的迭代次數稱為該次算法的最小收斂代數;如果算法在 次運算中不收斂，則。設算法在 次運算中，最小收斂代數分

別為，則最小平均收斂代數。

實驗方案1：在固定和的條件下，比較。該方案中，，，，如表1所示，實驗結果如表2（其中在表2中分別用Ⅰ、Ⅱ表示）所示。

實驗方案2：固定，比較算法在時的平均值、最小值、方差。此方案中，。實驗結果如表3和表4所示，從至在時的進化曲線如圖3至圖10所示。

4.3 ? 實驗結果

表2、表3、表4是八個標準測試函數在實驗方案1和方案2下得到的實驗結果。

圖3至圖10分別是八個測試函數分別在LDWPSO、FRPSO、CPSO和NHPSO下的迭代進化圖。

由上述實驗結果可以看出，NHPSO無論在收斂精度、收斂速度還是收斂率方面，都要顯著優于其他三種算法，并且在后期仍有很強的全局搜索能力，有效抑制了粒子早熟。這主要得益于NHPSO有較為適中的慣性權重，使之能在進化初期搜索到一個較好的候選優化位置，在進化后期收斂的同時仍具有較強的全局搜索能力;在每一次迭代中，對滿足條件的粒子采取了一種新的自適應變異策略，提高了種群的多樣性。

5 ? 結論（Conclusion）

本文針對PSO算法的早熟收斂問題，提出了一種新的混合粒子群優化算法——NHPSO算法。在NHPSO中，使用新慣性權重策略有效平衡了粒子的全局搜索能力和局部搜索能力;在每次迭代中，按確定條件選擇（而不是隨機選擇）粒子并對其進行新的自適應變異，不僅有利于算法的穩定性，而且有效抑制了粒子早熟。數值仿真實驗證實了以上兩點。

由于NHPSO在100 維和200 維有很好的優化效果，因此是一種很有實用價值的智能優化算法。

參考文獻（References）

[1] SHI Y， EBERHART R. A modified particle swarm optimizer[C]// IEEE.1998 Proceedings of the IEEE International Conference on Evolutionary Computation（CEC）. Piscataway， USA： IEEE， 1998：69-73.

[2] 黃軒，張軍，詹志輝.基于隨機慣量權重的快速粒子群優化算法[J].計算機工程與設計，2009，30（03）：55-57.

[3] LIANG S J， SONG S L， LI K， et al. An improved particle swarm optimization algorithm and its convergence analysis[C]// IEEE. 2nd International Conference on Computer Modeling and Simulation（ICCMS）. New York， USA： IEEE， 2010：

138-141.

[4] 楊英杰.粒子群算法及其應用研究[M].北京：北京理工大學出版社，2017：1-186.

[5] 李根.基于云任務調度及粒子群算法的網絡安全系統設計[J].軟件工程，2018，21（05）：28-30.

[6] 趙紅超，周洪慶，王書湖.無人機三維航跡規劃的量子粒子群優化算法[J].航天控制，2021，39（01）：40-45.

[7] 陳強，王宇嘉，梁海娜，等.目標空間映射策略的高維多目標粒子群優化算法[J].智能系統學報，2021，16（02）：362-370.

[8] 田夢丹，梁曉磊，符修文，等.具有博弈概率選擇的多子群粒子群算法[J].計算機科學，2021，48（10）：67-76.

[9] 楊博雯，錢偉懿.多慣性權重的自適應粒子群優化算法[J].渤海大學學報，2021，42（01）：45-52.

[10] 王建麗.基于隨機微粒群算法的開放實驗室規劃研究[J].軟件工程，2021，24（10）：28-30.

作者簡介：

徐生兵（1980-），男，碩士，講師.研究領域：智能計算及其應用.

蹇 ? 柯（1983-），男，碩士，講師.研究領域：智能優化，盲源分離.

夏文杰（1981-），男，碩士，講師.研究領域：計算機專色油墨配色的理論與實現.