徐生兵 蹇柯 夏文杰

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

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

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

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

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

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

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

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

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

（3）

其中，為最大慣性權(quán)重，為最小慣性權(quán)重，一般取，;為當(dāng)前迭代次數(shù);為總迭代次數(shù)。這樣，就會(huì)隨著迭代次數(shù)的增加而線(xiàn)性遞減。因此，使用式（3）權(quán)重策略的PSO算法被稱(chēng)為慣性權(quán)重線(xià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)過(guò)大量數(shù)值實(shí)驗(yàn)證實(shí)：慣性權(quán)重在0.4—0.6隨機(jī)取值時(shí)，其總體實(shí)驗(yàn)效果要優(yōu)于LDWPSO。與LDWPSO的慣性權(quán)重相比，F(xiàn)RPSO的特點(diǎn)是：初期慣性權(quán)重較小，后期慣性權(quán)重較大。但后期慣性權(quán)重較大是不利于粒子局部搜索的（這在文獻(xiàn)[7]FRPSO與LDWPSO的對(duì)比實(shí)驗(yàn)中也可以看出來(lái)）?？紤]到兩種權(quán)重的各自特點(diǎn)和實(shí)驗(yàn)效果，本文構(gòu)造了一種新的慣性權(quán)重，使其值在初期和后期均介于兩者之間，具體如下：

（4）

其中，，。

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

3.2 ? 一種新的變異策略

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

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

，表示粒子的初始速度。

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

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

那么，對(duì)粒子的變異操作是：

（5）

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

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

3.3 ? NHPSO算法流程

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

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

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

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

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

4.2 ? 實(shí)驗(yàn)參數(shù)設(shè)置及實(shí)驗(yàn)方案設(shè)計(jì)

4.2.1 ? 實(shí)驗(yàn)參數(shù)設(shè)置

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

4.2.2 ? 實(shí)驗(yàn)方案設(shè)計(jì)

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

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

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

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

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

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

4.3 ? 實(shí)驗(yàn)結(jié)果

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

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

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

5 ? 結(jié)論（Conclusion）

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

由于NHPSO在100 維和200 維有很好的優(yōu)化效果，因此是一種很有實(shí)用價(jià)值的智能優(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] 黃軒，張軍，詹志輝.基于隨機(jī)慣量權(quán)重的快速粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(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] 楊英杰.粒子群算法及其應(yīng)用研究[M].北京：北京理工大學(xué)出版社，2017：1-186.

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

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

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

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

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

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

作者簡(jiǎn)介：

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

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

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