一種新的混合粒子群優(yōu)化算法

徐生兵 蹇柯 夏文杰

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

關(guān)鍵詞：粒子群優(yōu)化;慣性權(quán)重;早熟;變異

中圖分類號：TP183 ? ? 文獻(xiàn)標(biāo)識碼：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）

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

2 ?標(biāo)準(zhǔn)粒子群算法（Standard particle swarm optimization algorithm ）

標(biāo)準(zhǔn)粒子群算法的數(shù)學(xué)描述過程如下：

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

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

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

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

（3）

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

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

3.1 ? 一種新的慣性權(quán)重策略

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

（4）

其中，，。

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

3.2 ? 一種新的變異策略

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

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

，表示粒子的初始速度。

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

，表示粒子的初始適應(yīng)值。

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

（5）

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

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

3.3 ? NHPSO算法流程

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

4 ? 數(shù)值仿真實驗（Numerical simulation experiments）

4.1 ? 標(biāo)準(zhǔn)測試函數(shù)

在數(shù)值仿真實驗中，選取如表1所示的八個標(biāo)準(zhǔn)測試函數(shù)對LDWPSO、FRPSO、CPSO和NHPSO進(jìn)行性能對比實驗。

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

4.2 ? 實驗參數(shù)設(shè)置及實驗方案設(shè)計

4.2.1 ? 實驗參數(shù)設(shè)置

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

4.2.2 ? 實驗方案設(shè)計

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

定義3：如果算法在指定代的運算中，最終優(yōu)化結(jié)果，其中為預(yù)設(shè)精度，則稱該次算法收斂。若算法在次運算中，有次收斂，則平均收斂率。

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

別為，則最小平均收斂代數(shù)。

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

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

4.3 ? 實驗結(jié)果

表2、表3、表4是八個標(biāo)準(zhǔn)測試函數(shù)在實驗方案1和方案2下得到的實驗結(jié)果。

圖3至圖10分別是八個測試函數(shù)分別在LDWPSO、FRPSO、CPSO和NHPSO下的迭代進(jìn)化圖。

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

5 ? 結(jié)論（Conclusion）

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

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

參考文獻(xiàn)（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] 黃軒，張軍，詹志輝.基于隨機慣量權(quán)重的快速粒子群優(yōu)化算法[J].計算機工程與設(shè)計，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] 楊英杰.粒子群算法及其應(yīng)用研究[M].北京：北京理工大學(xué)出版社，2017：1-186.

[5] 李根.基于云任務(wù)調(diào)度及粒子群算法的網(wǎng)絡(luò)安全系統(tǒng)設(shè)計[J].軟件工程，2018，21（05）：28-30.

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

[7] 陳強，王宇嘉，梁海娜，等.目標(biāo)空間映射策略的高維多目標(biāo)粒子群優(yōu)化算法[J].智能系統(tǒng)學(xué)報，2021，16（02）：362-370.

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

[9] 楊博雯，錢偉懿.多慣性權(quán)重的自適應(yīng)粒子群優(yōu)化算法[J].渤海大學(xué)學(xué)報，2021，42（01）：45-52.

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

作者簡介：

徐生兵（1980-），男，碩士，講師.研究領(lǐng)域：智能計算及其應(yīng)用.

蹇 ? 柯（1983-），男，碩士，講師.研究領(lǐng)域：智能優(yōu)化，盲源分離.

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