慣性權(quán)重自適應(yīng)計(jì)算的粒子群優(yōu)化算法

楊穎穎，陳壽文

1 引言

粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)[1]源于對(duì)鳥(niǎo)群和魚(yú)群覓食行為的模擬，是由Eberhart和Kennedy于1995年提出的一種隨機(jī)優(yōu)化算法。該算法具有原理簡(jiǎn)單、易于實(shí)現(xiàn)、以及參數(shù)少等特點(diǎn)[2]，已被廣泛地應(yīng)用于科學(xué)和工程領(lǐng)域[3]。然而，迭代運(yùn)行后期出現(xiàn)進(jìn)化停滯、以及易于陷入局部最優(yōu)解等局限，使得該算法用于求解多模優(yōu)化問(wèn)題的適應(yīng)性受到限制[4]。慣性權(quán)重(inertia weight)[5]用以平衡PSO算法的全局搜索能力和局部搜索能力。針對(duì)PSO算法的上述缺陷，很多學(xué)者開(kāi)展了算法慣性權(quán)重的改進(jìn)研究。目前，用于計(jì)算慣性權(quán)重的策略可以劃分為3種[6]：時(shí)間變化(time varying)、常數(shù)或隨機(jī)數(shù)(constant or random)慣性權(quán)重、自適應(yīng)(adaptive)慣性權(quán)重。其中，自適應(yīng)慣性權(quán)重策略的基本思想是構(gòu)建用于監(jiān)測(cè)群體進(jìn)化狀態(tài)動(dòng)態(tài)變化的群體反饋(feedback)參數(shù)的函數(shù)。大量研究結(jié)果表明運(yùn)用該種策略比使用其他兩種策略來(lái)計(jì)算慣性權(quán)重更有效[6]。文獻(xiàn)[7]以粒子群的進(jìn)化速度和粒子聚集度作為群體反饋參數(shù)，通過(guò)構(gòu)建這兩個(gè)參數(shù)的線性函數(shù)來(lái)計(jì)算慣性權(quán)重，提出了一種動(dòng)態(tài)改變慣性權(quán)重的DCWPSO算法，既提高了粒子群的尋優(yōu)精度又加快了粒子群的尋優(yōu)速度。在文獻(xiàn)[7]的研究基礎(chǔ)上，本文用粒子聚集度作為群體反饋參數(shù)，提出一種自適應(yīng)計(jì)算慣性權(quán)重方法(Method for Adaptively Computing Inertia Weight, MACIW)，進(jìn)而基于MACIW設(shè)計(jì)了一種自適應(yīng)粒子群優(yōu)化算法(Adaptive PSO based on MACIW, APSOM)。以Sphere等六個(gè)函數(shù)為測(cè)試對(duì)象，通過(guò)與LDWPSO等算法的比較，實(shí)驗(yàn)結(jié)果顯示APSOM算法具有較強(qiáng)的尋優(yōu)能力和穩(wěn)定性。

2 粒子群優(yōu)化算法及群體反饋參數(shù)

2.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法中的每個(gè)粒子都有位置和速度，粒子通過(guò)跟蹤自身迄今為止所發(fā)現(xiàn)的最優(yōu)位置pbest和種群迄今為止所發(fā)現(xiàn)的最優(yōu)位置gbest，分別按照(1)式和(2)式來(lái)迭代更新自身的速度和位置。

(1)

(2)

ω(t)=ωmax-t(ωmax-ωmin)/T

(3)

上式中，ωmax和ωmin分別為慣性權(quán)重的初始值和終止值，t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。

2.2 群體反饋參數(shù)

群體反饋(feedback)參數(shù)[6]可用來(lái)實(shí)時(shí)地監(jiān)測(cè)群體進(jìn)化狀態(tài)。文獻(xiàn)[7]定義了粒子群的進(jìn)化速度因子h和粒子聚集度因子s，二者的計(jì)算式分別如(4)式和(5)式。

(4)

(5)

假定適應(yīng)度函數(shù)在搜索空間內(nèi)的值恒大于0，則h∈(0，1]且s∈(0，1]。由(4)式來(lái)看，若粒子群出現(xiàn)進(jìn)化停滯現(xiàn)象，則粒子群的進(jìn)化速度因子h=1；h值越小，粒子群的進(jìn)化速度越快。另外，由(5)式可知，粒子聚集度因子s值越大，粒子群聚集度越大；當(dāng)粒子群中的所有粒子具有同一性，則s=1。

3 自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法

3.1 自適應(yīng)慣性權(quán)重

慣性權(quán)重是PSO算法中一個(gè)重要參數(shù)，用于平衡粒子群的全局勘探能力和局部開(kāi)采能力，影響著PSO算法中粒子群的尋優(yōu)精度和尋優(yōu)速度。本文設(shè)計(jì)自適應(yīng)慣性權(quán)重策略的思想是：構(gòu)建保持大小關(guān)系恒成立的慣性權(quán)重計(jì)算式的集合，確立該集合與粒子聚集度因子之間的映射關(guān)系，依據(jù)該映射關(guān)系通過(guò)監(jiān)測(cè)粒子聚集度因子來(lái)自適應(yīng)地計(jì)算慣性權(quán)重。其中，所設(shè)計(jì)的慣性權(quán)重計(jì)算式的集合A由(6)-(8)式形成。

(6)

(7)

(8)

上三式中，h為粒子群的進(jìn)化速度因子，s為粒子聚集度因子，二者計(jì)算式分別如(4)和(5)式，e為自然對(duì)數(shù)的底，ωmax和ωmin分別為慣性權(quán)重的初始值和終止值，t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。

設(shè)定T=100，ωmin=0.4，ωmax=0.9，與任意一個(gè)t∈{0，1，…,T}相對(duì)應(yīng)的h和s，分別從(0，1]中隨機(jī)選取，再按照(6)-(8)式分別來(lái)計(jì)算慣性權(quán)重，其結(jié)果ωi(t)與迭代次數(shù)t之間的對(duì)應(yīng)關(guān)系如圖1所示。

圖1 慣性權(quán)重ω(t)與迭代次數(shù)t之間的對(duì)應(yīng)關(guān)系

從圖1來(lái)看，按(6)-(8)式所計(jì)算的慣性權(quán)重ωi(t)∈[ωmin,ωmax]且關(guān)系ω1(t)≤ω2(t)≤ω3(t)始終成立。這與上述分析結(jié)果是一致的。

從PSO算法運(yùn)行過(guò)程來(lái)看，初始時(shí)，隨機(jī)初始化各粒子位置使得粒子聚集度較低；隨著算法迭代運(yùn)行次數(shù)的增加，粒子逐漸向某一個(gè)或多個(gè)位置聚集，使得粒子聚集度呈現(xiàn)上升趨勢(shì)；迭代后期，粒子聚集度趨于最高值，算法也趨于收斂。粒子聚集度低、適中、以及高這三種情形可用來(lái)區(qū)分群體進(jìn)化狀態(tài)。粒子聚集度因子(s)值越大，粒子聚集度越高[7]。劃分s隸屬度區(qū)間后，shigh

Shi等人[5]得出關(guān)于慣性權(quán)重的研究結(jié)論，較大慣性權(quán)重有利于粒子群體發(fā)揮全局尋優(yōu)能力以加快粒子群尋優(yōu)速度，較小慣性權(quán)重有利于粒子群體發(fā)揮局部尋優(yōu)能力以提高粒子群尋優(yōu)精度。粒子聚集度越高，算法越易于陷入局部最優(yōu)，通過(guò)增大慣性權(quán)重來(lái)擴(kuò)大粒子群搜索空間，提高粒子群的全局尋優(yōu)能力，從而加速粒子群的尋優(yōu)速度；粒子聚集度越低，種群多樣性越強(qiáng)，通過(guò)減小慣性權(quán)重來(lái)縮小粒子群搜索空間，提高粒子群的局部尋優(yōu)能力，從而提高粒子群的尋優(yōu)精度。同時(shí)，張選平等人[7]的研究結(jié)果表明，慣性權(quán)重與s之間的對(duì)應(yīng)關(guān)系是前者隨著后者的增大而增大。因此，本文所構(gòu)建的集合A與s之間的映射關(guān)系如(9)式。

R={(ω1(t)，shigh

(9)

依據(jù)上述映射關(guān)系R，通過(guò)監(jiān)測(cè)粒子聚集度因子，本文提出按照式(10)來(lái)自適應(yīng)計(jì)算慣性權(quán)重的方法(Method for Adaptively Computing Inertia Weight, MACIW)。

(10)

上式中，t為當(dāng)前迭代次數(shù)，s為粒子聚集度因子，ω1(t)、ω2(t)和ω3(t)對(duì)應(yīng)為按照(6)、(7)和(8)式來(lái)計(jì)算的慣性權(quán)重。

3.2 自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法

按照式(10)來(lái)計(jì)算慣性權(quán)重，本文設(shè)計(jì)了一種基于MACIW的自適應(yīng)粒子群優(yōu)化算法(Adaptive PSO based on MACIW, APSOM)。該算法的執(zhí)行過(guò)程表述如下：

1. 設(shè)定慣性權(quán)重區(qū)間[wmin,wmax]、最大迭代次數(shù)T和群體規(guī)模N；

3.評(píng)價(jià)各個(gè)粒子的適應(yīng)度，并確定各個(gè)粒子的pbest和種群對(duì)應(yīng)的gbest；

4.用(4)和(5)式分別來(lái)計(jì)算粒子群的進(jìn)化速度因子h和粒子聚集度因子s，并按照(10)式計(jì)算慣性權(quán)重；

5.用(1)和(2)式分別來(lái)更新粒子速度和位置；

6.判定終止運(yùn)行條件是否滿(mǎn)足，若滿(mǎn)足，終止；否則，轉(zhuǎn)步驟3。

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

本實(shí)驗(yàn)的運(yùn)行環(huán)境為Windows 10操作系統(tǒng), 內(nèi)存16G, Intel i7-7500U CPU 2.7GHz，算法采用Matlab R2016a實(shí)現(xiàn)。為了檢驗(yàn)APSOM算法有效性，以Sphere等6個(gè)函數(shù)為測(cè)試對(duì)象，并與算法LDWPSO[5]和DCWPSO[7]進(jìn)行比較。粒子群的適應(yīng)度函數(shù)選用各測(cè)試目標(biāo)函數(shù)，對(duì)應(yīng)各測(cè)試函數(shù)及其屬性描述如表1。

表1 測(cè)試函數(shù)及其屬性描述

設(shè)定ωmin=0.4,ωmax=0.9,c1=c2=2,S=40,D=30,T=3000，算法DCWPSO其他參數(shù)如原文。以達(dá)到最大迭代次數(shù)T為算法終止運(yùn)行判定條件，算法獨(dú)立運(yùn)行30輪，記錄算法所有輪最后一次迭代所對(duì)應(yīng)的群體最優(yōu)適應(yīng)度的最小值(Min)、均值(Ave)、中位數(shù)(Median)、最大值(Max)及標(biāo)準(zhǔn)差(Std)如表2。

從表2來(lái)看，在求解f1-f4函數(shù)最優(yōu)解時(shí)，算法APSOM的Ave指標(biāo)和Median指標(biāo)均要小于其他兩個(gè)算法，這說(shuō)明APSOM算法的尋優(yōu)精度是最高的。上述三個(gè)算法均能夠求解到f5的最優(yōu)解。求解f6函數(shù)最優(yōu)解時(shí)，算法APSOM的尋優(yōu)精度比DCWPSO算法稍低，但這兩個(gè)算法的尋優(yōu)精度均高于LDWPSO算法。在求解函數(shù)f1-f5時(shí)，APSOM算法的Std指標(biāo)比LDWPSO和DCWPSO算法的均要小，這說(shuō)明APSOM算法的穩(wěn)定性強(qiáng)于其他兩個(gè)算法。

依次設(shè)定函數(shù)f1-f6的容許精度為10-40、10-20、0.5、0.05、10-50和5×10-12，以不超過(guò)最大迭代次數(shù)且所求解的測(cè)試函數(shù)達(dá)到容許精度為算法終止運(yùn)行的判定條件，算法獨(dú)立運(yùn)行30輪，記錄成功可達(dá)率和函數(shù)評(píng)估次數(shù)平均值如表3。

從表3來(lái)看，就成功可達(dá)率指標(biāo)來(lái)說(shuō)，求解函數(shù)f1-f6最優(yōu)解時(shí)，APSOM算法均能夠達(dá)到可容許的尋優(yōu)精度，除f1和f3外，DCWPSO算法均能夠達(dá)到可容許精度，算法LDWPSO僅在求解f4和f5時(shí)能夠達(dá)到可容許精度，在求解其他4個(gè)函數(shù)時(shí)都不能達(dá)到。就函數(shù)評(píng)估次數(shù)平均值指標(biāo)來(lái)說(shuō)，DCWPSO和APSOM算法的該項(xiàng)指標(biāo)均要低于LDWPSO算法的，在求解函數(shù)f1、f3和f4時(shí)，APSOM算法的收斂速度是最快的，盡管在求解函數(shù)f2時(shí)，APSOM算法的該項(xiàng)指標(biāo)高于DCWPSO算法，但前者的尋優(yōu)精度要高于后者。

另外，以Sphere和Ellipsoid為例，APSOM等3個(gè)算法對(duì)應(yīng)的平均最佳適應(yīng)度(f)的迭代如圖2。

表2 不同算法測(cè)試結(jié)果

表3 三個(gè)算法的函數(shù)評(píng)估次數(shù)平均值和成功可達(dá)率

圖2 Sphere和Ellipsoid函數(shù)30次對(duì)應(yīng)的平均最佳適應(yīng)度進(jìn)化

由圖2可知，APSOM算法的尋優(yōu)能力比算法LDIWPSO和DCWPSO都要強(qiáng)。通過(guò)分析以上實(shí)驗(yàn)結(jié)果可知，總體來(lái)說(shuō)，算法APSOM的尋優(yōu)能力比另外兩個(gè)算法要強(qiáng)，尋優(yōu)過(guò)程比算法LDIWPSO和DCWPSO要穩(wěn)定。這說(shuō)明使用粒子聚集度因子判定群體狀態(tài)后，通過(guò)自適應(yīng)調(diào)整慣性權(quán)重可增強(qiáng)粒子群的尋優(yōu)能力，APSOM算法是有效的。

5 結(jié)束語(yǔ)

為了提高PSO算法的尋優(yōu)能力，提出了一種自適應(yīng)慣性權(quán)重計(jì)算方法MACIW，該方法的基本思想是：構(gòu)建保持大小關(guān)系恒成立的慣性權(quán)重計(jì)算式的集合，確立該集合與粒子聚集度因子之間的映射關(guān)系，依據(jù)該映射關(guān)系通過(guò)監(jiān)測(cè)粒子聚集度因子來(lái)自適應(yīng)地計(jì)算慣性權(quán)重。進(jìn)一步地，設(shè)計(jì)了基于MACIW的自適應(yīng)PSO算法APSOM。使用6個(gè)基本測(cè)試函數(shù)對(duì)APSOM算法及其他2個(gè)算法進(jìn)行仿真實(shí)驗(yàn)比較，結(jié)果驗(yàn)證了算法APSOM相對(duì)于所比較的2個(gè)算法具有更高的尋優(yōu)精度和穩(wěn)定性。工程優(yōu)化問(wèn)題求解中如何應(yīng)用該算法，以及進(jìn)一步提高該算法的性能將是下一步研究的重點(diǎn)。

[參 考 文 獻(xiàn)]

[1] Kennedy J, Eberhart R. Particle swarm optimization [C]. Proceedings of the IEEE International Conference on Neural Networks, IEEE, 1995, 4: 1942-1948.http://dx.doi.org/10.1109/ICNN.1995. 488968.

[2] Civicioglu P,Besdok E. A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms [J]. Artificial Intelligence Review, 2013, 39(4): 315-346.

[3] Zhang Y, Wang S, Ji G. A Comprehensive Survey on Particle Swarm Optimization Algorithm and Its Applications [J]. Mathematical Problems in Engineering, Volume 2015 (2015), Article ID 931256, 38 pages. http://dx.doi.org/10.1155/2015/931256.

[4] 陳小玉. 一種快速多種群的粒子群多模優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2018, 35(11), online, http://www.arocmag.com/article/02-2018-11-006.html

[5] Shi Y, Eberhart R. A modified particle swarm optimizer[C]. Proceedings of IEEE Congress on Computational Intelligence,CEC1998, IEEE, 1998: 69-73.

[6] Nickabadi A, Ebadzadeh M M, Safabakhsh R. A novel particle swarm optimization algorithm with adaptive inertia weight [J]. Applied Soft Computing, 2011, 11(4): 3658-3670.

[7] 張選平,杜玉平,秦國(guó)強(qiáng),覃征. 一種動(dòng)態(tài)改變慣性權(quán)重的自適應(yīng)粒子群算法[J].西安交通大學(xué)學(xué)報(bào), 2005, 39(10): 1039-1042.