一種快速自適應(yīng)粒子群算法

劉生建　羅林　楊艷

摘 要：為了解決標(biāo)準(zhǔn)粒子群優(yōu)化算法（SPSO）不能適應(yīng)復(fù)雜非線性優(yōu)化過程的問題，提出了一種動(dòng)態(tài)改變慣性權(quán)重的快速自適應(yīng)粒子群優(yōu)化算法（QAPSO），直接利用群粒子的位置分布情況控制粒子飛行的慣性權(quán)重，借助于個(gè)體最優(yōu)位置和全局最優(yōu)位置的平均作用避免粒子陷入局部最優(yōu)。通過多個(gè)基準(zhǔn)函數(shù)仿真結(jié)果表明，在不引入額外設(shè)計(jì)及增加實(shí)現(xiàn)復(fù)雜度的前提下，相對(duì)于SPOS等經(jīng)典算法，QAPSO在收斂速度、最優(yōu)解精度等方面獲得了大幅提升，尤其對(duì)于多峰函數(shù)效果更明顯。

關(guān)鍵詞：粒子群算法；均值粒子群算法；快速自適應(yīng)

DOI：10.11907/rjdk.171514

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）009-0042-04

Abstract：A quickly adaptive particle swarm optimization algorithm （QAPSO） with dynamically changing inertia weight was presented to solve the problem that the Standard Particle Swarm Optimization algorithm （SPSO） cannot adapt to the complex and nonlinear optimization process.The QAPSO evaluates the population distribution， and automatic control inertia weight. By using the mean of the optimal individual position and the global optimal position， the best global particle can jump out of the local optima. The QAPSO has comprehensively been evaluated based on benchmark functions. Results show that QAPSO substantially enhances the performance of paradigm such as the SPSO in terms of convergence speed， solution accuracy without introducing an additional design or implementation complexity， especially for multimodal functions.

Key Words：swarm intelligence optimizationalgorithm； mean swarm optimization algorithm； inertia weight adaptability

0 引言

自蟻群算法（Ant Colony Optimization ， ACO）成功應(yīng)用于旅行商問題（TSP）之后[1]，仿生群智能研究開始迅速發(fā)展，先后出現(xiàn)了粒子群、蜂群、人工魚群、蝙蝠群、狼群、螢火蟲等主要解決連續(xù)問題的優(yōu)化算法。

Kennedy和Eberhart在1995年提出了來源于鳥群等生物種群覓食行為的粒子群優(yōu)化算法（Particle Swarm Optimizer， PSO）[2-3]，由于概念簡(jiǎn)單，實(shí)現(xiàn)容易，且只有少數(shù)參數(shù)需要調(diào)整，所以PSO算法發(fā)展迅速，并廣泛應(yīng)用于函數(shù)尋優(yōu)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模式分類、模糊系統(tǒng)控制等領(lǐng)域。雖然PSO相比魚群算法等有較強(qiáng)的全局搜索能力，但還是容易陷入局部極值，不易收斂到全局最優(yōu)。所以出現(xiàn)了一些改進(jìn)的PSO算法。例如Shi Y等[4]提出了線性遞減權(quán)值（LDIW）策略；Kusum Deep等[5]提出均值粒子群優(yōu)化方法（MPSO）；Zhan Z H等[6]提出了自適應(yīng)粒子群優(yōu)化算法等。

本文主要對(duì)經(jīng)典粒子群算法的性能及問題進(jìn)行分析，并針對(duì)收斂精度低和收斂速度慢的問題，在均值粒子群算法基礎(chǔ)上，根據(jù)粒子間的距離函數(shù)動(dòng)態(tài)調(diào)整算法中的慣性權(quán)重，合理調(diào)整粒子飛行速度。當(dāng)最優(yōu)粒子和其它粒子位置相距較遠(yuǎn)時(shí)，設(shè)置較大的慣性系數(shù)，由此解決函數(shù)尋優(yōu)過程中探索和開發(fā)之間的矛盾。實(shí)驗(yàn)仿真結(jié)果表明，本文提出的改進(jìn)算法性能有了明顯提高，具有相對(duì)收斂速度快、精度高等優(yōu)點(diǎn)。

1 標(biāo)準(zhǔn)粒子群優(yōu)化算法

設(shè)N個(gè)粒子組成一個(gè)群，其中第i個(gè)粒子的位置表示為一個(gè)D維的矢量xi=（xi1，xi2，…，xid），第i個(gè)粒子的歷史最優(yōu)位置為pi=（pi1，pi2，…，pid），整個(gè)粒子群迄今為止搜索到的最好位置記為pg=（pg1，pg2，…，pgd）。第i個(gè)粒子的速度vi=（vi1，vi2，…，vid）。粒子群算法基于迭代思想，粒子按如下公式（1）、（2）調(diào)整自己的相應(yīng)位置[7]：vk+1id=ω*vkid+c1*r1*（pkid-xkid）+

c2*r2*（pkgd-xkid）

（1）

xk+1id=xkid+vk+1idxid∈[xd-min，xd-max]

（2） 其中，1≤i≤N（N為種群個(gè)體總數(shù)），1≤d≤D，k為迭代次數(shù)，c1和c2是非負(fù)數(shù)，c1表示粒子個(gè)體最優(yōu)位置的自我影響，而c2則表示群體最優(yōu)位置的群體影響。r1和r2是[0 ，1]區(qū)間的隨機(jī)數(shù)。ω表示慣性權(quán)重因子，在公式（1）中一般是固定值，范圍一般為[0.4，0.9]，可決定粒子先前速度對(duì)目前運(yùn)動(dòng)的影響程度，從而起到平衡算法全局搜索和局部搜索能力的作用。當(dāng)粒子速度較大時(shí)，飛行較快，有利于全局勘探，但有可能超過最優(yōu)解；反之則有利于局部開發(fā)。endprint

粒子在解空間內(nèi)不斷跟蹤個(gè)體極值與全局極值， 直到達(dá)到規(guī)定的迭代次數(shù)或滿足規(guī)定的誤差標(biāo)準(zhǔn)為止。在尋優(yōu)初期，ω應(yīng)取0.9～1.4，然后根據(jù)迭代次數(shù)線性減少到0.4，公式如下：ω=ωmax-（ωmax-ωmin）ttmax

（3） 其中，t表示目前的迭代次數(shù)，tmax表示設(shè)定的最大迭代次數(shù)，ωmax表示最大慣性權(quán)重因子，ωmin表示最小慣性權(quán)重因子。

也可以從物理含義上來解釋公式（1），一個(gè)單位質(zhì)量的粒子在單位時(shí)間上受到來自Pi和Pg兩處吸引力的共同作用，從而引起加速度變化。加速度變化導(dǎo)致速度改變，最終改變粒子所處位置。本文將ω固定的PSO簡(jiǎn)稱為SPSO，而依據(jù)公式（3）計(jì)算的PSO簡(jiǎn)稱為L(zhǎng)PSO，以對(duì)算法性能進(jìn)行對(duì)比分析。

2 均值粒子群優(yōu)化算法

與基本粒子群形成對(duì)比的是，均值粒子群優(yōu)化算法（MPSO）速度更新公式中用線性組合pkid+pkgd2和pkid-pkgd2取代了pkid和pkgd。因此，速度更新公式（1）轉(zhuǎn)換為公式（4）：vk+1id=ω*vkid+c1*r1*（pkid+pkgd2-xkid）+

c2*r2*（pkid-pkgd2-xkid）

（4） 其中等式中的第一項(xiàng)與公式（1）含義相同；第二項(xiàng)與矢量（pkid+pkgd2-xkid）成比例變化，它吸引粒子由當(dāng)前位置方向指向全局最優(yōu)位置和粒子個(gè)體最優(yōu)位置的平均位置方向；第三項(xiàng)與矢量（pkid-pkgd2-xkid）成比例變化，它吸引粒子由當(dāng)前位置方向指向粒子個(gè)體最優(yōu)位置方向和全局最優(yōu)位置負(fù)方向的平均位置方向。其它更新和參數(shù)設(shè)置與基本粒子群算法相同。

3 快速自適應(yīng)粒子群算法（QAPSO）

3.1 基本思想

計(jì)算現(xiàn)有粒子群中每個(gè)粒子距離其它粒子的距離因子di，現(xiàn)有粒子群中適應(yīng)度最高的粒子，設(shè)其距離因子為dg，距離因子的最小值為dmin，最大值為dmax，計(jì)算粒子群的分布信息因子f。f值為1表示最優(yōu)粒子遠(yuǎn)離其它粒子，直接將下一次迭代的慣性權(quán)重設(shè)置為f值，即可合理控制其它粒子飛向最優(yōu)位置的速度。

粒子的距離因子如公式（5）所示：di=1N-1∑Nj=1，j≠i∑Dk=1xik-xjk

（5） 公式（5）也可使用歐氏距離，但采用曼哈頓距離計(jì)算量較少。

粒子群的分布信息因子如公式（6）所示：f=dg-dmindmax-dminf∈[0，1]

（6）

ωk+1i=f

（7） 最優(yōu)粒子和其它粒子之間的位置關(guān)系主要有3種情況，如圖1所示。

圖1（a）表示算法初期，所有粒子隨機(jī)分布，最優(yōu)粒子與其它粒子差別不大，dg≈di，粒子群處于勘探階段；圖1（b）表示其它粒子向當(dāng)前最優(yōu)粒子靠攏，dgdi，處于收斂階段；圖1（c）表示出現(xiàn)新的更優(yōu)位置后，dgdi，其它粒子紛紛跳出原有局部最優(yōu)位置。

3.2 QAPSO算法描述

Step1：初始化粒子群數(shù)目N，在函數(shù)定義域內(nèi)對(duì)每個(gè)粒子的初始位置和初始速度進(jìn)行隨機(jī)初始化。

Step2：將粒子的pi設(shè)置為當(dāng)前位置，pg設(shè)置為初始群體中最佳粒子的位置。

Step3：判斷算是否滿足終止條件，如果滿足，轉(zhuǎn)Step6；否則執(zhí)行（4）。

Step4：對(duì)粒子群中的所有粒子i執(zhí)行如下操作：①根據(jù)式（2）、（4）更新粒子的速度及位置；②計(jì)算粒子i的適應(yīng)度值fi；③如果fi優(yōu)于pi的適應(yīng)度值，則更新pi為粒子i的當(dāng)前位置；④如果fi優(yōu)于pg的適應(yīng)度值，則更新pg為粒子i的當(dāng)前位置；④根據(jù)式（5）計(jì)算距離因子di，更新dg、dmin、dmax。

Step5：根據(jù)式（6）、（7）計(jì)算粒子群的分布信息因子，從而確定下一次迭代慣性權(quán)重ω的值。然后回到Step3繼續(xù)執(zhí)行。

Step6：輸出pg，結(jié)束算法運(yùn)行。

4 仿真實(shí)驗(yàn)與數(shù)值分析

本文使用Matlab2014b對(duì)上述QAPSO算法編寫了仿真程序，同時(shí)也針對(duì)標(biāo)準(zhǔn)粒子群算法（SPSO）、均值粒子群算法（MPSO）、慣性權(quán)重線性遞減粒子群算法（LPSO）在同樣的環(huán)境下進(jìn)行仿真。仿真程序中，粒子群規(guī)模N取40，對(duì)比算法中加速常數(shù)c1和c2為2，固定慣性權(quán)重ω取0.729 8。LPSO算法中，ω從0.9線性遞減到0.4。對(duì)每個(gè)測(cè)試函數(shù)均進(jìn)行20次獨(dú)立實(shí)驗(yàn)，函數(shù)評(píng)估精度設(shè)為10-15。參考文獻(xiàn)[8]選取了6個(gè)測(cè)試函數(shù)。

單峰函數(shù)有：

（1）Rosenbrock 函數(shù)。f1（X）=∑D-1i=1[100（xi+1-x2i）2+（xi-1）2]

（8）

-10≤xi≤10 當(dāng)D=30，X*=（1，…，1）時(shí)，其全局最優(yōu)值f（X*）=0， 尋優(yōu)成功標(biāo)準(zhǔn)為f（X）≤10。該函數(shù)在全局最優(yōu)位置附近變換十分平緩，當(dāng)D=2時(shí)，該函數(shù)分布如圖2所示。很多優(yōu)化算法很難找到全局最優(yōu)位置或找到最優(yōu)值需要的迭代次數(shù)較多。

（2）Schwefel′s 函數(shù)。f2（X）=∑Di=1xi+∏Di=1xi

（9）

-10≤xi≤10 當(dāng)D=30，X*=（0，…，0）時(shí)，其全局最優(yōu)值f（X*）=0， 尋優(yōu)成功標(biāo)準(zhǔn)為f（X）≤0.01。

多單峰函數(shù)有：

（3）Dropwave函數(shù)。f3（X）=-1+cos（12x1+x2）0.5（x1+x2）+2

（10）

-2≤x1，x2≤2 當(dāng)X*=（0，0）時(shí)，其全局最優(yōu)值f（X*）= -1，尋優(yōu)成功標(biāo)準(zhǔn)為f（X）≤-0.99。

（4）Eggcrate函數(shù)。該函數(shù)的局部峰值很多，當(dāng)D=2時(shí)，該函數(shù)分布如圖3所示。f4（X）=x21+x22+25（sin2x1+sin2x2）endprint

（11）

-π≤x1，x2≤π 當(dāng)X*=（0，0）時(shí)，其全局最優(yōu)值 f（X*）= 0，尋優(yōu)成功標(biāo)準(zhǔn)為f（X）≤0.01。

（5）Rastrigin函數(shù)。f5（X）=∑Di=1[x2i-10cos（2πxi）+10]

（12）

-5.12≤xi≤5.12 當(dāng)D=30，X*=（0，…，0）時(shí)，其全局最優(yōu)值f（X*）= 0，尋優(yōu)成功標(biāo)準(zhǔn)為f（X）≤0.01。

（6）Ackley 函數(shù)。f6（X）=-20exp（-0.21D∑Di=1x2i）-

exp（1D∑Di=1cos（2πxi））+20+exp（1）

（13）

-32≤xi≤32 當(dāng)D=30，X*=（0，…，0）時(shí)，其全局最優(yōu)值f（X*）= 0，尋優(yōu)成功標(biāo)準(zhǔn)為f（X）≤0.01。

表1～表6分別給出了6個(gè)函數(shù)在Intel Xeon E3-1230V2和8G DDR3內(nèi)存、128G固態(tài)硬盤計(jì)算機(jī)上運(yùn)行計(jì)算的結(jié)果比較，所有算法的最大迭代次數(shù)均為200。

從表1～表6中可以看出，QAPSO除單峰函數(shù)f1和其它優(yōu)化算法一樣均未成功找到最優(yōu)值外，其它函數(shù)尋優(yōu)精度和時(shí)間都明顯優(yōu)于LPSO、MPSO、SPSO，尤其是在處理變化劇烈的多峰函數(shù)（f4、f5等）時(shí)。LPSO和MPSO算法性能相差不大，SPSO表現(xiàn)最差。在收斂速度上，QAPSO與LPSO、MPSO、SPSO相比有明顯優(yōu)勢(shì)，收斂時(shí)間大大縮短。由于收斂速度差別較大，所以圖中的橫坐標(biāo)迭代次數(shù)從20開始計(jì)數(shù)，以避免縱坐標(biāo)函數(shù)值差距過大。從圖2、圖3可以明顯看出，算法總體性能表現(xiàn)為：QAPSO>MPSO>LPSO>SPSO。

5 原因分析

由表1可知，單峰函數(shù)f1的尋優(yōu)能力不太理想，其原因是函數(shù)值在最優(yōu)位置區(qū)域內(nèi)變化十分緩慢，各粒子的函數(shù)值非常接近，直接導(dǎo)致f取值接近0。QAPSO直接使用f作為慣性系數(shù)，所以使得粒子失去慣性作用。

由于SPSO采用固定慣性權(quán)重策略，在前期探索解空間時(shí)能力不強(qiáng)，而在后期由于慣性較大，又缺乏局部開發(fā)能力，很難搜索到最優(yōu)解；LPSO則在前期加強(qiáng)了勘探能力，在后期采用較小的慣性權(quán)重，增強(qiáng)了局部尋優(yōu)能力；MPSO則考慮到當(dāng)前個(gè)體最優(yōu)和群體最優(yōu)位置對(duì)粒子群可能產(chǎn)生的“誤導(dǎo)”，增強(qiáng)了粒子跳出局部最優(yōu)的能力；而QAPSO進(jìn)一步使用群體分布因子來動(dòng)態(tài)調(diào)整下一次迭代的慣性權(quán)重，從而在多峰函數(shù)的尋優(yōu)過程中表現(xiàn)出較強(qiáng)的適應(yīng)能力。圖4、圖5表示QAPSO、SPSO對(duì)f4尋優(yōu)過程中群分布因子的變化過程，可看出在迭代后期，SPSO算法過早收斂到了局部最優(yōu)值，群個(gè)體趨向相同位置，減少了群體多樣性。反之，QAPSO則在整個(gè)過程中一直充分保持了群體多樣性。

6 結(jié)語

本文提出了一種基于粒子群分布因子的均值粒子群改進(jìn)優(yōu)化算法，實(shí)驗(yàn)結(jié)果表明，與標(biāo)準(zhǔn)粒子群算法、線性改變權(quán)重粒子群優(yōu)化算法、均值粒子群算法相比，本文算法的收斂速度快、精度較高。本文以種群位置分布因子作為慣性權(quán)重，平衡了算法的全局探索和局部開發(fā)能力，使粒子跳出局部最優(yōu)束縛。6個(gè)函數(shù)優(yōu)化的仿真結(jié)果表明， 本文算法在成功率、平均最優(yōu)值、收斂時(shí)間上都有很大改善，特別對(duì)于多峰函數(shù)，算法性能的改善更為明顯。對(duì)于單峰函數(shù)，可繼續(xù)進(jìn)行研究改進(jìn)，一種簡(jiǎn)單策略是在發(fā)現(xiàn)最優(yōu)值變化緩慢時(shí)切換為標(biāo)準(zhǔn)粒子群方法，從而擴(kuò)大算法的使用范圍。

參考文獻(xiàn)：

[1] DORTGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony cooperating agents[J]. IEEE Trans. on Systems， Man， and Cybernetics Part B： Cybernetics，1996，26（1）：29-41.

[2] KENNEDY J， EBERHART R. Particle swarm optimization[C]. International Conference on Neural Networks，Perth， Australia： IEEE，1995：1942-1948.

[3] EBERHART R C， KENNEDY J. A new optimizer using particle swarm theory[J]. Institute of Electrical and Electronics Engineers，1995（10）：39-43.

[4] SHI Y， EBERHART R. A modified swarm optimizer[C].IEEE International Conference of Evolutionary Computation Anchorage， Alaska： IEEE Press，1998：69-73.

[5] KUSUM DEEP， JAGDISH CHAND BANSAL. Mean particle swarm optimisation for function optimisation[J]. Computational Intelligence Studies，2009（1）：72-92.

[6] ZHANZH， ZHANGJ， LIY， et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man， and Cybernetics — Part B： Cybernetics，2009，39（6）：1362-1381.

[7] X YAO， YLIU， G M LIN. Evolutionary programming made faster[J] . IEEE Trans. Evol. Comput.，1999（2）：82-102.

[8] SHI Y， EBERHART R. Empirical study of particle swarm optimization[C]. International Conference on Evolutionary Computation，Washington， USA： IEEE，1999：1945-1950.

（責(zé)任編輯：黃 ?。〆ndprint