李 響，華 敏

（1.開封大學(xué) 信息工程學(xué)院，河南 開封475004；2.信陽農(nóng)林學(xué)院 計(jì)算機(jī)科學(xué)系，河南 信陽464000）

0 引 言

粒子群優(yōu)化算法［1］具有概念簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)，但是粒子群算法在解決一些復(fù)雜的多峰問題時(shí)，由于進(jìn)化模式不夠完善，容易陷入局部最優(yōu)。許多學(xué)者提出了改進(jìn)進(jìn)化模型的粒子群算法，何勝等人提出了一種新的學(xué)習(xí)模型的CLPSO 算法［2］；Huang等人使用多個(gè)全局最優(yōu)粒子的集合替換單個(gè)最優(yōu)粒子來更新粒子的速度，提出了ELPSO算法［3］；朱海梅等人提出了一種高速收斂粒子群優(yōu)化算法［4］；吳曉軍等人提出了一種均勻搜索粒子群算法［5］。但由于這些算法均只采用了一種進(jìn)化模式，很難滿足算法在不同的進(jìn)化階段對(duì)開發(fā)與探測(cè)能力的需求。因此，一些學(xué)者又進(jìn)一步提出了一些多種群、多模型的改進(jìn)粒子群優(yōu)化算法。劉衍民等人提出一種基于動(dòng)態(tài)鄰居和變異因子的粒子群算法 （DNMPSO）［6］；Zhao等人考慮尋優(yōu)不同階段的開發(fā)與探測(cè)能力需求的差異，提出了一種多階段多模型的改進(jìn)粒子群優(yōu)化算法［7］；Sun等人將粒子先采用多種群進(jìn)化模式進(jìn)化，然后再采用混合蛙跳模式進(jìn)化的方法提出了HPSO 算法［8］；史小露等人將粒子每次進(jìn)化都進(jìn)行全局和局部?jī)纱嗡阉?，提出了FSPSO 算法［9］；Wang Hui等人采用一種新的多樣性增強(qiáng)機(jī)制和兩種鄰域搜索策略，提出了鄰域搜索和多樣性增強(qiáng)的粒子群優(yōu)化算法 （DNSPSO）［10］。雖然將粒子分成多個(gè)子群或者將算法分成多個(gè)階段，采用不同的進(jìn)化策略，但由于這些算法都是根據(jù)經(jīng)驗(yàn)進(jìn)行分群或者分階段，所以在某些進(jìn)化階段下，算法的進(jìn)化模式仍然無法滿足算法需求，從而導(dǎo)致算法性能下降。為此，提出了一種自適應(yīng)選擇進(jìn)化模式的粒子群算法。

1 粒子群算法

粒子群算法具體可描述為：假設(shè)在一個(gè)D 維的目標(biāo)搜索空間中，N 個(gè)粒子組成了一個(gè)粒子群體，第i個(gè)粒子的位置和速度分別表示為：xi＝（xi1，xi2，…，xiD）和vi＝（vi1，vi2，…，viD）；單個(gè)粒子當(dāng)前找到的個(gè)體最優(yōu)位置為pi＝（pi1，pi2，…，piD）（pbest），整個(gè)粒子全體當(dāng)前找到的全局最優(yōu)位置為pg＝（pg1，pg2，…，pgD）（gbest）。粒子每個(gè)粒子根據(jù)如下的公式迭代更新速度和位置

其中，i＝（1，2，......N），d＝（1，2，......D）；ω為慣性權(quán)重；c1和c2為加速常數(shù)；r1和r2為0到1之間均勻分布的隨機(jī)數(shù)；vtid為粒子i當(dāng)前的速度；vt＋1id為粒子i 更新后的速度；xtid為粒子i當(dāng)前的位置；xt＋1id為粒子i更新后的新位置。

2 改進(jìn)算法的實(shí)現(xiàn)

改進(jìn)粒子群算法與標(biāo)準(zhǔn)粒子群算法相比主要在以下3個(gè)方面做了改進(jìn)：①提出了2種不同的進(jìn)化模型，一種為開發(fā)模型，一種為探測(cè)模型；②提出了一種速度多樣性指標(biāo)，通過計(jì)算2 種進(jìn)化模型的速度多樣性指標(biāo)可以確定2種進(jìn)化模型各自的選擇概率，從而讓粒子根據(jù)選擇概率自適應(yīng)選擇相應(yīng)的進(jìn)化模式進(jìn)行更新；③增加了一種一維學(xué)習(xí)機(jī)制，該機(jī)制是將最優(yōu)粒子位置隨機(jī)選擇一維，按照高斯隨機(jī)分布的原則在這一維進(jìn)行學(xué)習(xí)。

2.1 進(jìn)化模型

粒子群算法中的粒子存在的探測(cè)與開發(fā)2種能力：粒子的探測(cè)能力強(qiáng)調(diào)在搜索范圍內(nèi)探測(cè)新的搜索區(qū)域，而粒子的開發(fā)能力則側(cè)重在所得區(qū)域內(nèi)實(shí)現(xiàn)精細(xì)搜索。這2種能力相互制約，當(dāng)粒子探測(cè)能力強(qiáng)時(shí)其開發(fā)能力就弱，相反，當(dāng)粒子開發(fā)能力強(qiáng)時(shí)其探測(cè)能力就弱。與粒子探測(cè)與開發(fā)能力相對(duì)應(yīng)學(xué)者們提出了2種進(jìn)化模型，一種是探測(cè)模型，一種是開發(fā)模型。探測(cè)模型的速度更新公式為

開發(fā)模型的速度更新公式為

其中，式 （3）、式 （4）中的參數(shù)說明同式 （1）、式 （2），另外2種進(jìn)化模式的位置更新公式一致。探測(cè)模型中由于只有粒子自身經(jīng)驗(yàn)的影響，粒子發(fā)散性較強(qiáng)，具有較強(qiáng)的探測(cè)能力，能夠較好的探測(cè)新的領(lǐng)域。開發(fā)模型中由于只有群體最優(yōu)粒子的影響，收斂性較強(qiáng)，具有較強(qiáng)的開發(fā)能力，能夠較好的實(shí)現(xiàn)精細(xì)搜索。

2.2 速度多樣性

算法的群體多樣性是指種群中個(gè)體的差異，反映了群智能算法的運(yùn)行信息，是衡量算法探索和開發(fā)能力的一個(gè)重要指標(biāo)。目前，粒子群算法，群體多樣性主要有認(rèn)知多樣性，位置多樣性和速度多樣性這3種定義，本文采用的是速度多樣性，根據(jù)文獻(xiàn) ［11］其具體計(jì)算如下

其中，N 表示粒子個(gè)數(shù)目，dim 為維數(shù)，vij表示第i個(gè)粒子第j維速度值，表示在第j維上速度多樣性值，Dp表示速度總體多樣性值。

通過計(jì)算2種進(jìn)化模型的速度總體多樣性值D0，D1，進(jìn)而得到2種進(jìn)化模式的概率選擇公式p，然后粒子通過輪盤賭的方法產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)r，若r＜p則現(xiàn)在進(jìn)化模式1，若r＞p，則選擇進(jìn)化模式2。P的具體計(jì)算公式如下

式中：pt——第t次迭代進(jìn)化模式的選擇概率，pt－1——第t－1次迭代進(jìn)化模式的選擇概率，在初始階段，2 種進(jìn)化模式的選擇概率相等p0＝0.5。由式 （8）可知，若D0＝D1，則pt保持不變，若D0＞D1，則pt＞pt－1，相反若D0＜D1，則pt＜pt－1，由此可見粒子根據(jù)pt選擇進(jìn)化模型時(shí)，粒子總是優(yōu)先選擇多樣性較好的模型。并且為了保證2種模型在全部進(jìn)化過程中，都有被選中的概率。本文對(duì)pt進(jìn)行了限制，使0.25≤pt≤0.75。

2.3 一維學(xué)習(xí)機(jī)制

為了加快算法的收斂速度，文獻(xiàn) ［12］引進(jìn)了一種新的一維學(xué)習(xí)機(jī)制。該機(jī)制在全局最優(yōu)粒子位置的基礎(chǔ)上，隨機(jī)地選擇一維，然后在這一維度的位置上加上一個(gè)成高斯分布的隨機(jī)數(shù)，而其他維數(shù)上的數(shù)值保持不變，比較新粒子與全局最優(yōu)粒子適應(yīng)值，若優(yōu)于最優(yōu)粒子，則替換最優(yōu)粒子，否則不保留。其具體學(xué)習(xí)公式為

2018年11月，第二十六屆世界計(jì)量組織大會(huì)將在巴黎召開，屆時(shí)將對(duì)我們所熟知的基本計(jì)量單位做出重大調(diào)整。千克作為國際單位制中質(zhì)量的基本單位，將基于普朗克常數(shù)進(jìn)行重新定義，而沿用了129年的國際千克原器也將退出歷史舞臺(tái)。

式中：P 表示全局最優(yōu)粒子位置，d 表示全局最優(yōu)粒子的某一隨機(jī)維度，μ為高斯隨機(jī)數(shù)的均值，σ2為高斯隨機(jī)數(shù)的方差，文中

式中：Max，Min——函數(shù)的搜索范圍，g——當(dāng)前學(xué)習(xí)的次數(shù)，G——每次迭代需要學(xué)習(xí)的次數(shù)。

2.4 改進(jìn)算法流程

改進(jìn)算法具體流程為：①粒子初始化；②根據(jù)式 （8）計(jì)算出2種模型的選擇概率；③粒子根據(jù)②中計(jì)算得到的概率p選擇相應(yīng)的進(jìn)化模式進(jìn)行速度更新；④按照位置更新式 （2）進(jìn)行位置更新；⑤根據(jù)一維學(xué)習(xí)機(jī)制，對(duì)最優(yōu)粒子進(jìn)行更新；⑥判斷算法是否結(jié)束，否返回步驟2。

3 仿真結(jié)果與實(shí)驗(yàn)分析

3.1 測(cè)試函數(shù)

為測(cè)試算法的性能，選擇8個(gè)經(jīng)典的基準(zhǔn)函數(shù)進(jìn)行仿真實(shí)驗(yàn)［13］，函數(shù)維數(shù)都為30，形式如下：

3.2 仿真實(shí)驗(yàn)結(jié)果

為更好地測(cè)試本文算法的性能，選擇幾種改進(jìn)粒子群算法進(jìn)行對(duì)比測(cè)試實(shí)驗(yàn)。這些改進(jìn)算法中CLPSO 算法為單模式改進(jìn)算法，HPSO 算法為多模式改進(jìn)算法，F(xiàn)SPSO 算法為2個(gè)階段改進(jìn)算法［14］。算法參數(shù)設(shè)置為，粒子個(gè)數(shù)為20，評(píng)估次數(shù)為20萬次。為了消除算法隨機(jī)性的影響，各算法對(duì)每個(gè)函數(shù)運(yùn)行30次，取平均值作為優(yōu)化結(jié)果。文算法簡(jiǎn)稱ASPSO 算法，算法的測(cè)試結(jié)果見表1。

表1 改進(jìn)算法的測(cè)試結(jié)果

從測(cè)試結(jié)果可知：ASPSO 算法在8個(gè)測(cè)試函數(shù)中，有5個(gè)測(cè)試函數(shù)測(cè)試結(jié)果比其他3種算法結(jié)果都好。特別是在Quadric函數(shù)，Rosenbrock函數(shù)，Schwefel函數(shù)和Rastrigin函數(shù)上。ASPSO 算法結(jié)果與其他3種算法相比結(jié)果有大幅度的提高，例如，Quadric函數(shù)結(jié)果比其他算法高了3個(gè)數(shù)量級(jí)，Rosenbrock函數(shù)比其他算法高了2個(gè)數(shù)量級(jí)。

3.3 Friendman檢驗(yàn)結(jié)果

為了方便在統(tǒng)計(jì)意義上比較多個(gè)算法的性能，采用Friendman檢驗(yàn)對(duì)結(jié)果分析，結(jié)果見表2。

表2 Friendman檢驗(yàn)結(jié)果

表2中給出CLPSO、HPSO、FSPSO 和ASPSO 這4種算法在8個(gè)測(cè)試函數(shù)上的總體性能的秩均值。算法的秩均值越小，性能越好，排名越高。由此可知，四種算法的性能排序依次如下：ASPSO 算法、CLPSO 算法、HPSO 算法和FSPSO 算法，ASPSO 算法在4 種算法中整體性能最好。

3.4 收斂性分析

為了更加直觀的比較出幾種算法的收斂性能，本文選取了6個(gè)函數(shù)，將其收斂對(duì)比情況繪制成圖表形式。其中前面3個(gè)為單峰函數(shù)分別為：Sphere函數(shù)收斂如圖1所示，Quadric函數(shù)收斂如圖2 所示，Rosenbrock 函數(shù)收斂如圖3所示。

圖1 Sphere函數(shù)收斂

圖2 Quadric函數(shù)收斂

從上邊3個(gè)單峰函數(shù)收斂情況對(duì)比可知，ASPSO 算法除了Sphere函數(shù)，其他函數(shù)收斂速度都是最快的，而且收斂速度曲線比較平滑。而Sphere函數(shù)在前半階段收斂速度也是最快的。另外，3 個(gè)為多峰函數(shù)分別為Schwefel函數(shù)收斂如圖4 所示，Rastrigin函數(shù)收斂如圖5 所示，Ackley函數(shù)收斂如圖6所示。

由以上3個(gè)多峰函數(shù)收斂情況圖可以明顯看出，ASPSO 算法的收斂速度明顯比其他3種算法都快，并且收斂精度也是最高的。綜合以上結(jié)果說明ASPSO 算法不管是在單峰函數(shù)還是多峰函數(shù)上，收斂速度都是非常快的，并未出現(xiàn)有的階段較快，有的階段較慢的情況。相反，對(duì)比的改進(jìn)算法則出現(xiàn)的在某些階段收斂較快而在某些階段則收斂較慢的現(xiàn)象。

圖3 Rosenbrock函數(shù)收斂

圖4 Schwefel函數(shù)收斂

圖5 Rastrigin函數(shù)收斂

4 結(jié)束語

圖6 Ackley函數(shù)收斂

根據(jù)速度多樣性指標(biāo)，提出的一種自適應(yīng)選擇進(jìn)化模式的改進(jìn)粒子群算法，在單峰和多峰測(cè)試函數(shù)都表現(xiàn)出良好的性能，具有較好的全局搜索能力和較快的收斂速度。在8個(gè)測(cè)試函數(shù)的仿真結(jié)果中，與目前幾種常見的改進(jìn)粒子群算法相比，ASPSO 算法有5個(gè)測(cè)試函數(shù)的測(cè)試效果最好，其中2個(gè)為單峰函數(shù)，3個(gè)為多峰函數(shù)。且Friendman檢驗(yàn)結(jié)果表明在8個(gè)測(cè)試函數(shù)中ASPSO 算法整體性能排名第一。另外根據(jù)算法收斂對(duì)比情況圖可知，ASPSO算法在大部分測(cè)試函數(shù)上，其收斂速度是最快的，且由于ASPSO 算法是一種自適應(yīng)調(diào)整進(jìn)化模式的改進(jìn)算法，能夠滿足算法在不同的進(jìn)化階段對(duì)開發(fā)與探測(cè)能力的不同需求，因此收斂速度在整個(gè)進(jìn)化階段比較平滑，為出現(xiàn)時(shí)快時(shí)慢的現(xiàn)象。

［1］GENG Huantong，GAO Jun，JIA Tingting，et al.Multi－objective particle swarm optimization method with balanced diversity and convergence［J］.Journal of Computer Applications，2013，33 （7）：1926－1929 （in Chinese）.［耿煥同，高軍，賈婷婷，等.均衡分布性和收斂性的多目標(biāo)粒子群優(yōu)化方法 ［J］.計(jì)算機(jī)應(yīng)用，2013，33 （7）：1926－1929.］

［2］HE Sheng，PAN Yu，WU Fangsheng，et al.Research of improvement CLPSO algorithm and its performance for optimization composition test functions［J］.Computer Engineering and Design，2009，30 （8）：1963－1965 （in Chinese）.［何勝，潘瑜，吳訪升，等.改進(jìn)的CLPSO 算法及對(duì)復(fù)雜組合函數(shù)的優(yōu)化研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （8）：1963－1965.］

［3］Huang Han，Qin Hu，Hao Zhifeng，et al.Example－based learning particle swarm optimization for continuous optimization［J］.Information Sciences，2012，182 （1）：125－138.

［4］ZHU Haimei，WU Yongping.A PSO algorithm with high speed convergence［J］.Control and Decision，2010，25 （1）：20－25（in Chinese）.［朱海梅，吳永萍.一種高速收斂粒子群優(yōu)化算法［J］.控制與決策，2010，25 （1）：20－25.］

［5］WU Xiaojun，YANG Zhanzhong，ZHAO Ming.A uniform search particle swarm optimization ［J］.Acta Electronica Sinica，2011，39 （6）：1261－1266 （in Chinese）.［吳曉軍，楊戰(zhàn)中，趙明.均勻搜索粒子群算法 ［J］.電子學(xué)報(bào)，2011，39（6）：1261－1266.］

［6］LIU Yanmin，ZHAO Qingzhen，SUI Changling，et al.Particle swarm optimizer based on dynamic neighborhood topology and mutation operator［J］Control and Decision，2010，25 （7）：968－974 （in Chinese）.［劉衍民，趙慶禎，隋常玲，等.一種基于動(dòng)態(tài)鄰居和變異因子的粒子群算法 ［J］.控制與決策，2010，25 （7）：968－974.］

［7］Zhao Jia，Lu Li，Sun Hui，et al.A novel two sub－swarms exchange particleswarm optimization based on multi－phases［C］／／IEEE International Conference on Granular Computing，2010.

［8］Hui Sun，Jun Li，Wen Lili，et al.A hybird particle swarm optimization for wireless sensor network coverage problem ［J］.Sensor Letters，2012，10 （8）：1744－1750.

［9］SHI Xiaolu，SUN Hui，LI Jun，et al.Particle swarm optimization algorithm with fast convergence and adaptive escape ［J］.Journal of Computer Applications，2013，33 （5）：1308－1312（in Chinese）.［史小露，孫輝，李俊，等.具有快速收斂和自適應(yīng)逃逸功能的粒子群算法 ［J］.計(jì)算機(jī)應(yīng)用，2013，33 （5）：1308－1312.］

［10］WANG Hui，SUN Hui，LI Changhe，et al.Diversity enhanced particle swarm optimization with neighborhood search［J］.Information Sciences，2013，223：119－135.

［11］Zhan Zhihui，Zhang Jun，Li Yun，et al.Adaptive particle swarm optimization［J］.IEEE Transactions on Systems，Man and Cybernetics，2009，39 （6）：1362－1381.

［12］CHENG Shi，SHI Yuhui.Measurement of PSO diversity based on L1norm ［J］.Computer Science，2011，38 （7）：190－193（in Chinese）.［程適，史玉回.基于L1范式的粒子群體多樣性研究 ［J］.計(jì)算機(jī)科學(xué)，2011，38 （7）：190－193.］