毛煥宇 王文東

1(浙江紡織服裝職業(yè)技術(shù)學(xué)院信息媒體學(xué)院 浙江 寧波 315211)2(延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 陜西 延安 716000)

0 引 言

作為一種智能種群優(yōu)化算法，PSO算法[1]與其他種群進(jìn)化算法相似，是以隨機(jī)解組成的種群進(jìn)行初始化的。不同之處在于，傳統(tǒng)的PSO并不僅僅是一次性的適者生存法則，它對(duì)于物種行為的模擬，其每一個(gè)候選解均與一個(gè)進(jìn)化速率相關(guān)。PSO的優(yōu)勢(shì)取決于粒子朝著全局最優(yōu)解進(jìn)化的收斂速度[2]。粒子群進(jìn)化算法不僅簡(jiǎn)單，且運(yùn)行頻率較高，適應(yīng)性好，廣泛應(yīng)用于多目標(biāo)最優(yōu)化和路徑規(guī)化問(wèn)題研究中。然而，如何在當(dāng)前空間的搜索與新搜索空間的開(kāi)發(fā)上取得一定的平衡是粒子群進(jìn)化的關(guān)鍵問(wèn)題。對(duì)于傳統(tǒng)的粒子群優(yōu)化而言，搜索初期的粒子可以較快收斂至較優(yōu)解周圍，但搜索晚期會(huì)出現(xiàn)眾多粒子密集聚焦同一區(qū)域的情況。文獻(xiàn)[3]的研究結(jié)果證實(shí)，粒子搜索最優(yōu)解過(guò)程中，若慣性權(quán)重值過(guò)大，則搜索過(guò)程近似全局搜索機(jī)制，對(duì)于新區(qū)域的不斷搜索會(huì)導(dǎo)致粒子過(guò)度分散，無(wú)法聚焦和收斂，得不到最終穩(wěn)定的種群；而過(guò)小的慣性權(quán)重則使得搜索近似局部搜索機(jī)制，粒子收斂過(guò)快，而陷入局部極值點(diǎn)中。

文獻(xiàn)[4]提出通過(guò)一種模糊控制機(jī)制和隨機(jī)化方法，實(shí)現(xiàn)對(duì)粒子迭代進(jìn)化中的慣性權(quán)重調(diào)整，但是得到的粒子收斂性性能并不理想，原因在于其算法計(jì)算復(fù)雜度較高，計(jì)算時(shí)間過(guò)長(zhǎng)。文獻(xiàn)[5]引入一種收斂因子對(duì)種群進(jìn)行迭代處理，以一種參數(shù)動(dòng)態(tài)配置方法防止部分種群粒子的進(jìn)化方向出現(xiàn)過(guò)大偏離，無(wú)法到達(dá)最優(yōu)區(qū)域，可以實(shí)現(xiàn)控制收斂。文獻(xiàn)[6]提出一種動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)控制粒子移動(dòng)，使初始階段的進(jìn)化過(guò)程中鄰居粒子數(shù)量降低，隨著迭代搜索的進(jìn)行，再根據(jù)粒子間距更新粒子活動(dòng)鄰近區(qū)域，極大地提升了粒子種群的多樣性，但算法收斂需要的迭代次數(shù)較大。文獻(xiàn)[7]將集群化的粒子群中的中心粒子視為最優(yōu)粒子，將聚類后得到的全局聚類中心作為全局最優(yōu)粒子，進(jìn)而以聚類的方式實(shí)現(xiàn)了最優(yōu)粒子的鄰近區(qū)域的更新規(guī)則。文獻(xiàn)[8]設(shè)計(jì)一種動(dòng)態(tài)聚簇的粒子群算法，使相近特點(diǎn)的粒子可組成群，以群體方式共同進(jìn)化，以此改變粒子尋優(yōu)性能。文獻(xiàn)[9]則利用小世界網(wǎng)絡(luò)思想改善粒子尋優(yōu)能力，避免了種群早熟。

不同于以上工作，本文在每次迭代過(guò)程中更新粒子速度的同時(shí)，將當(dāng)前的參考粒子與全局種群的最優(yōu)粒子間的距離考慮到進(jìn)化過(guò)程中，并根據(jù)該距離值，設(shè)計(jì)一種隸屬度函數(shù)動(dòng)態(tài)地為粒子調(diào)整其慣性權(quán)重。該自適應(yīng)的調(diào)整方法使得離最優(yōu)粒子較遠(yuǎn)的粒子可以擁有更大的慣性權(quán)重，從而提高全局搜索性能，而離最優(yōu)粒子較近的粒子可以擁有更小的慣性權(quán)重，提高其局部搜索性能。

1 粒子群優(yōu)化及其早熟分析

對(duì)于PSO，設(shè)m個(gè)粒子分布在d維度空間中，每個(gè)粒子的維度以速度和位置進(jìn)行描述，在t次迭代時(shí)，分別表示為：

(1)

迭代過(guò)程中，單個(gè)粒子已搜索到的最優(yōu)位置表示為Pi=(pi1,pi2,…,pid)，將其稱為pbest，即個(gè)體最優(yōu)解。而所有粒子搜索到的最優(yōu)位置為Pg=(pg1,pg2,…,pgd)，即全局最優(yōu)gbest。PSO即是所有粒子更新其粒子速度和位置的尋優(yōu)過(guò)程，可表示為：

(2)

式中：t表示迭代次數(shù)；d表示搜索空間的維度；w表示慣性權(quán)重值，w∈[0.1,0.9]；rand()表示隨機(jī)數(shù)，rand()∈[0,1]；c1和c2為常量，稱為認(rèn)知因子。

對(duì)于傳統(tǒng)的粒子群而言，更小的慣性權(quán)重更利于局部搜索，慣性權(quán)重增加則利于全局搜索。因此，若w值在迭代過(guò)程中保持恒定不變會(huì)降低PSO的性能。文獻(xiàn)[10-11]中的研究表明，w值在迭代過(guò)程中的線性降低可以明顯地增強(qiáng)PSO的收斂性能。具體方式為：賦予迭代初期的粒子更優(yōu)的全局搜索能力，而賦予迭代后期的粒子更優(yōu)的局部搜索能力。換言之，在迭代過(guò)程早期，需要設(shè)置較大w值；在迭代過(guò)程晚期，需要設(shè)置較小w值。針對(duì)這一問(wèn)題，文獻(xiàn)[12]通過(guò)利用慣性權(quán)重最值wmax和wmin設(shè)計(jì)了一種線性遞減機(jī)制對(duì)w值進(jìn)行動(dòng)態(tài)調(diào)整：

(3)

式中：tmax為種群迭代的最大次數(shù)。

式(3)中的慣性權(quán)重調(diào)整策略表明w值是線性遞減的，而線性遞減并不能表現(xiàn)粒子間的差異。為了反映每次迭代過(guò)程中粒子間的差異，根據(jù)粒子間距，本文利用隸屬度函數(shù)的概念，設(shè)計(jì)了一種可對(duì)粒子慣性權(quán)重進(jìn)行自適應(yīng)更新的改進(jìn)粒子群算法。并且，為了使得具有更高適應(yīng)度的粒子被選擇為全局最優(yōu)粒子的概率更大，還設(shè)計(jì)了一種Roulette(輪盤賭)方法進(jìn)行最優(yōu)粒子的選擇。

2 基于自適應(yīng)慣性權(quán)重的粒子群算法

2.1 粒子間的距離度量

定義1以Xi=[xi1,xi2,…,xid]表示粒子i，f表示粒子的適應(yīng)度，種群中粒子i與粒子j間的距離定義為：

(4)

根據(jù)定義1可知，對(duì)于任意粒子i、j和k，粒子間的距離將具備以下性質(zhì)：

性質(zhì)1非負(fù)性。粒子i和j間的距離是非負(fù)的，即D(i,j)≥0。

性質(zhì)2粒子與本身間的距離為零值，即D(i,i)=0。

性質(zhì)3對(duì)稱性。粒子i到粒子j的距離等于粒子j和粒子i的距離，即D(i,j)=D(j,i)。

性質(zhì)4粒子間的距離滿足三角形邊長(zhǎng)性質(zhì)，即D(i,j)≤D(i,k)+D(k,j)。

不同于其他粒子距離度量方法，式(4)利用曼哈坦距離(Manhattan Distance)[13]度量粒子間距，不僅考慮了無(wú)關(guān)參數(shù)間的距離，而且還考慮了目標(biāo)函數(shù)間的距離。

定義2粒子間的最大距離定義為：

Dmax=max{D(i,j)}

(5)

定義3若N為粒子數(shù)量，粒子間的平均距離為所有粒子對(duì)的間距之和與粒子數(shù)量的商值，可定義為：

(6)

定義4粒子與種群中的最優(yōu)粒子間的平均距離定義為：

(7)

2.2 隸屬度函數(shù)及其自適應(yīng)規(guī)則

對(duì)于PSO, 粒子速度的慣性權(quán)重更新僅與當(dāng)前迭代的次數(shù)相關(guān)，并未考慮粒子本身的特點(diǎn)?，F(xiàn)實(shí)情況是:粒子需要以自身與最優(yōu)粒子間距離為依據(jù)，動(dòng)態(tài)調(diào)整慣性權(quán)重值。當(dāng)粒子與最優(yōu)粒子相距較遠(yuǎn)時(shí)，粒子需要擁有更大的慣性權(quán)重，這有助于搜索全局最優(yōu)，并更快地收斂。若粒子距離最優(yōu)粒子較近，則應(yīng)該賦予更小慣性權(quán)重。基于此，根據(jù)D(i,pg)和慣性權(quán)重w，算法設(shè)計(jì)以下模糊規(guī)則：

規(guī)則1：若D(i,pg)較小，則慣性權(quán)重w也較小；

規(guī)則2：若D(i,pg)中等，則慣性權(quán)重w也中等；

規(guī)則3：若D(i,pg)較大，則慣性權(quán)重w也較大。

PSO-AIWA算法中D(i,pg)與w的隸屬度函數(shù)[14]如圖1和圖2所示，圖中δ和θ表示隸屬度因子。

進(jìn)行粒子更新時(shí)，若僅考慮粒子最優(yōu)位置pi和全局最優(yōu)粒子Pg，可能導(dǎo)致最終得到局部最優(yōu)。針對(duì)該問(wèn)題，算法選擇若干個(gè)最優(yōu)粒子在確定距離內(nèi)參與迭代過(guò)程。具體地，在每次迭代中，選擇任意k個(gè)全局最優(yōu)粒子為候選粒子，通過(guò)Roulette方法從k個(gè)粒子選擇最終的全局最優(yōu)粒子。

為了使單個(gè)具有更大適應(yīng)度的粒子當(dāng)選為全局最優(yōu)粒子的概率更高，需要增加擁有更大適應(yīng)度粒子的慣性權(quán)重。在k個(gè)全局最優(yōu)粒子中，計(jì)算選擇粒子m為全局最優(yōu)粒子的概率為：

(8)

式中：fit(x)表示粒子x的適應(yīng)度。

(9)

利用Roulette方法，對(duì)于任意的r∈[0,1]，如果式(10)得到滿足，則粒子m被選擇為全局最優(yōu)粒子。

(10)

本文提出的PSO-AIWA算法將根據(jù)粒子與最優(yōu)粒子間距對(duì)慣性權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整。當(dāng)粒子與最優(yōu)粒子間的距離大于門限值TH時(shí)，粒子則擁有更大的慣性權(quán)重；反之則賦予更小值。門限值TH設(shè)置為Daverage。粒子慣性權(quán)重的自適應(yīng)調(diào)整方式為：

(11)

式中：pg表示通過(guò)Roulette方法選擇的種群中的全局最優(yōu)粒子；wmax和wmin分別表示慣性權(quán)重值的最大值與最小值。

算法1給出了PSO-AIWA算法的偽代碼。

算法1PSO-AIWA算法

1. 輸入：tmax,N,k,wmax,wmin,c1,c2,δ,θ

2. 輸出：全局最優(yōu)解pg

3. 初始化粒子種群

4. 計(jì)算最優(yōu)粒子pi和pg

5. 當(dāng)t≤tmax

6. 計(jì)算粒子距離Daverage

7. 計(jì)算距離的隸屬度

8. 利用輪盤轉(zhuǎn)選擇規(guī)則計(jì)算w

9. 根據(jù)式(2)更新粒子速度和位置

10. 更新最優(yōu)粒子pi和pg

11. 更新迭代次數(shù)t

12. 返回全局最優(yōu)解pg

算法輸入?yún)?shù)包括：最大迭代次數(shù)、粒子總數(shù)、候選粒子數(shù)量、慣性權(quán)重最大值和最小值、認(rèn)知因子、隸屬度因子，算法輸出全局最優(yōu)粒子，即步驟1和步驟2。步驟3初始化種群粒子，包括粒子位置和速率。步驟4獲取初始種群的最優(yōu)粒子。步驟5表明，若當(dāng)前迭代次數(shù)小于或等于最大迭代次數(shù)。步驟6計(jì)算粒子間的平均距離。步驟7計(jì)算基于粒子距離的隸屬度。步驟8利用Roulette方法與相應(yīng)的模糊規(guī)則計(jì)算當(dāng)前的慣性權(quán)重。步驟9利用式(2)對(duì)粒子速度和位置進(jìn)行更新。步驟10更新當(dāng)前粒子搜索到的最優(yōu)位置和所有粒子的最優(yōu)位置。步驟11更新迭代次數(shù)，返回步驟5繼續(xù)搜索過(guò)程。最終在步驟12返回收斂的全局最優(yōu)粒子，即最優(yōu)解。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)配置與基準(zhǔn)函數(shù)

利用MATLAB平臺(tái)實(shí)現(xiàn)了融合隸屬度函數(shù)的自適應(yīng)慣性權(quán)重粒子群算法的仿真測(cè)試。選取6種基準(zhǔn)算法，包括：Sphere函數(shù)、Rastrigin函數(shù)、Rosenbrocks函數(shù)、Quadric函數(shù)、Griewank函數(shù)和Rotated Quadric函數(shù)，以上測(cè)試函數(shù)是廣泛應(yīng)用于粒子群進(jìn)化問(wèn)題測(cè)試的經(jīng)典函數(shù)。6種基準(zhǔn)函數(shù)中，Rosenbrocks函數(shù)、Rastrigin函數(shù)、Rotated Quadric函數(shù)和Griewank函數(shù)為多峰值函數(shù)，其他函數(shù)為單峰值函數(shù)。表1給出了以上6種基準(zhǔn)函數(shù)的相關(guān)搜索參數(shù)聲明。表2給出了算法中屬于粒子群的相關(guān)參數(shù)設(shè)置。為了證明算法性能的有效性，使用隨機(jī)慣性權(quán)重的經(jīng)典PSO算法和線性慣性權(quán)重的PSO-LDIW算法[12]作為性能的對(duì)比算法。

表1 測(cè)試函數(shù)聲明

表2 參數(shù)設(shè)置

1) Sphere函數(shù):

(12)

2) Quadric函數(shù):

(13)

3) Rosenbrocks函數(shù):

(14)

4) Rastrigin函數(shù):

(15)

5) Griewank函數(shù):

(16)

6) Rotated Quadric函數(shù):

(17)

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

1) 種群粒子分布情況。實(shí)驗(yàn)1觀察了3種算法利用測(cè)試基準(zhǔn)函數(shù)f5得到的迭代次數(shù)分別為50、100和200時(shí)的粒子分布情況，結(jié)果如圖3所示。種群中粒子的分布可以一定程度地反映種群個(gè)體的多樣性。PSO利用的是隨機(jī)化的慣性權(quán)重值對(duì)粒子狀態(tài)進(jìn)行調(diào)整，所得到的種群粒子分布在不同的迭代次數(shù)下始終處于較為分散的狀態(tài)，即圖3(a)。在粒子進(jìn)化的后期，部分粒子已經(jīng)逐漸陷入一些局部極值點(diǎn)的區(qū)域內(nèi)，即使繼續(xù)進(jìn)行狀態(tài)進(jìn)化與搜索，也無(wú)法有進(jìn)一步改進(jìn)。相比隨機(jī)慣性權(quán)重PSO，PSO-LDIW算法在全局收斂性上表現(xiàn)更加優(yōu)秀，其多數(shù)粒子均可以在迭代次數(shù)的后期逐漸進(jìn)入到全局最優(yōu)點(diǎn)的區(qū)域內(nèi)，原因在于該算法利用慣性權(quán)重值是線性遞減式改變的，尋優(yōu)性能得到了提升。而本文提出的PSO-AIWA算法比較另外兩種算法而言，其粒子具有更好的聚集性，粒子進(jìn)化過(guò)程中并沒(méi)有過(guò)早地使自身聚焦至局部極值點(diǎn)附近的區(qū)域，從而導(dǎo)致早熟，影響整體尋優(yōu)結(jié)果。主要原因在于：PSO-AIWA算法可以根據(jù)設(shè)計(jì)隸屬度函數(shù)動(dòng)態(tài)的調(diào)整粒子慣性權(quán)重，而隸屬度函數(shù)又是基于當(dāng)前粒子與全局最優(yōu)粒子間的距離得到的。

(a) 利用隨機(jī)慣性權(quán)重的PSO粒子分布

(b) 利用線性遞減慣性權(quán)重的PSO-LDIW粒子分布

(c) 利用隸屬度的動(dòng)態(tài)自適應(yīng)慣性權(quán)重的PSO-AIWA粒子分布圖3 種群粒子分布情況

2) 算法收斂性。實(shí)驗(yàn)2觀察了3種算法的收斂性性能，實(shí)驗(yàn)?zāi)康氖潜容^3種算法在擁有相同初始數(shù)據(jù)情況下的收斂速度和效率。實(shí)驗(yàn)在完全相同的條件下測(cè)試了所有6種基準(zhǔn)函數(shù)下的收斂性能，其他參數(shù)與實(shí)驗(yàn)1也是相同的。從圖4的結(jié)果可以看到，無(wú)論是單峰值基準(zhǔn)函數(shù)還是多峰值基準(zhǔn)函數(shù)情況，PSO-AIWA算法在收斂速度和精確度上均要優(yōu)于PSO算法和PSO-LDIW算法。測(cè)試中，在搜索能力上，PSO-LDIW算法要優(yōu)于傳統(tǒng)PSO算法。而PSO-AIWA算法比PSO-LDIW算法則表現(xiàn)出更好的性能，其搜索能力更佳。綜合來(lái)看，采用自適應(yīng)慣性權(quán)重調(diào)整機(jī)制的PSO-AIWA算法可以從根本上改善對(duì)比算法中對(duì)慣性權(quán)重的單一計(jì)算方式，降低搜索性能對(duì)于初始參數(shù)設(shè)置的過(guò)多依賴。

(a) Sphere函數(shù)

(b) Quadric函數(shù)

(c) Rosenbrocks函數(shù)

(d) Rastrigin函數(shù)

(e) Griewank函數(shù)

(f) Rotated Quadric函數(shù)圖4 最優(yōu)適應(yīng)度收斂性

3) 性能的統(tǒng)計(jì)分析。實(shí)驗(yàn)3以統(tǒng)計(jì)方法觀察算法得到的適應(yīng)度值的變化，結(jié)果如表3所示。由于在可行區(qū)域中僅有一個(gè)全局極值點(diǎn)，且越接近極值點(diǎn)其變化越小，選擇Sphere函數(shù)進(jìn)行本實(shí)驗(yàn)的測(cè)試。結(jié)果表明，相同條件下，PSO-AIWA算法和PSO-LDIW算法得到的結(jié)果的準(zhǔn)確性上明顯優(yōu)于隨機(jī)慣性權(quán)重PSO，這表明慣性權(quán)重的調(diào)整策略在改進(jìn)粒子個(gè)體多樣性和維持迭代進(jìn)化的性能上是有效可行的。相比PSO-LDIW算法，PSO-AIWA算法則擁有更佳的表現(xiàn)，在相同的配置條件下，其得到的最小值、最大值和平均最優(yōu)值更接近于全局最優(yōu)，這表明本文所設(shè)計(jì)的基于隸屬度的慣性權(quán)重自適應(yīng)調(diào)整策略是可以增強(qiáng)粒子個(gè)體的搜索能力的，在最優(yōu)粒子的影響下，其粒子進(jìn)化方向選擇更優(yōu)。另外，在多峰值測(cè)試基準(zhǔn)函數(shù)下，PSO-AIWA算法同樣優(yōu)于PSO-LDIW和PSO算法。在20次的實(shí)驗(yàn)中，比較PSO、PSO-AIWA和PSO-LDIW算法得到的結(jié)果顯然更加接近于全局最小值，這表明粒子慣性權(quán)重的自適應(yīng)更改可以增加粒子的搜索能力。而本文在不同階段中所應(yīng)用的慣性權(quán)重自適應(yīng)調(diào)整策略則有效地提升了粒子進(jìn)化，更好地指導(dǎo)了粒子的尋優(yōu)。

表3 統(tǒng)計(jì)結(jié)果

續(xù)表3

綜合以上的分析，在算法得到的粒子分布性能方面，本文算法得到的粒子分布相對(duì)于其他算法可以更快地實(shí)現(xiàn)粒子的聚集。一方面證明了利用隸屬度的動(dòng)態(tài)自適應(yīng)慣性權(quán)重調(diào)整機(jī)制是有效可行的，另一方面也證實(shí)了它對(duì)隨機(jī)慣性權(quán)重和線性遞減慣性權(quán)重能夠更好地描述粒子的差異，給予不同粒子不同程度的尋優(yōu)方向和尋優(yōu)能力，有效避免了粒子陷入局部最優(yōu)。粒子較好的聚焦性也顯示出算法也將具有更好的收斂性，即圖4的結(jié)果；更快地收斂可使得粒子得到的平均適應(yīng)度會(huì)趨于穩(wěn)定，即表明已搜索到全局最優(yōu)解上。在粒子適應(yīng)度值的統(tǒng)計(jì)分析上，本文算法得到的適應(yīng)度值也是優(yōu)于對(duì)比算法的，這表明慣性權(quán)重的調(diào)整策略在改進(jìn)粒子個(gè)體多樣性和維持迭代進(jìn)化的性能上是有效可行的。同時(shí)，無(wú)論是利用多峰函數(shù)還是單峰函數(shù)進(jìn)行測(cè)試，結(jié)果都比較穩(wěn)定，這表明粒子慣性權(quán)重的自適應(yīng)更改可以增加粒子的搜索能力，不會(huì)由于測(cè)試基準(zhǔn)函數(shù)性質(zhì)的改變而改變粒子的尋優(yōu)性能。

4 結(jié) 語(yǔ)

本文為粒子群算法設(shè)計(jì)了一種新的慣性權(quán)重自適應(yīng)調(diào)整策略，解決了傳統(tǒng)粒子群算法忽略粒子間的差異，利用相同的慣性權(quán)重到所有種群粒子上的缺陷。算法的主要思想是可以根據(jù)與全局最優(yōu)粒子間的(距離)不同，通過(guò)基于粒子間距的隸屬度函數(shù)動(dòng)態(tài)調(diào)整粒子的慣性權(quán)重，使得每次迭代中，粒子可以根據(jù)當(dāng)前狀態(tài)在每個(gè)維度上的搜索空間內(nèi)選擇合適的慣性權(quán)重進(jìn)行狀態(tài)更新。通過(guò)覆蓋單峰函數(shù)和多峰函數(shù)的6組基準(zhǔn)函數(shù)進(jìn)行了大量仿真實(shí)驗(yàn)，結(jié)果表明，比較隨機(jī)式慣性權(quán)重和線性遞減式慣性權(quán)重的調(diào)整策略，本文算法在收斂速度、求解準(zhǔn)確性及參數(shù)敏感性上均表現(xiàn)出了更好的效果。