時空眾包環(huán)境下時效均衡改進粒子群優(yōu)化算法

黃素葉

閩西職業(yè)技術(shù)學院，福建 龍巖 364021

時效均衡粒子群優(yōu)化算法是一種基于生物種群隨機搜索的粒子優(yōu)化算法，根據(jù)思想主要是源于鳥類種群的覓食行為規(guī)律，時效均衡改進粒子群中每一個粒子通過自己所處的最優(yōu)值，跟蹤并調(diào)整前進速度和方向，從而實現(xiàn)種群個體在空間中的尋優(yōu)[1].國外對于時效均衡改進粒子群優(yōu)化算法的研究最早可追溯到20世紀初期，由于當時的理論框架較難適應不同應變場,只能夠解決單工況問題,到20世紀中期將數(shù)值計算方法引入到了粒子群優(yōu)化算法中，求解了離散粒子結(jié)構(gòu)拓撲的優(yōu)化問題[2]；國內(nèi)關(guān)于時效均衡改進粒子群優(yōu)化算法的研究較晚，在近20年到30年才開始研究時效均衡改進粒子群優(yōu)化算法，同時也成為結(jié)構(gòu)設(shè)計優(yōu)化領(lǐng)域的研究熱點[3].

基于自適應動態(tài)改變的粒子群優(yōu)化算法根據(jù)粒子的適應度值來調(diào)整算法的權(quán)重，采用非線性指數(shù)遞減來提高算法的搜索能力，避免粒子群優(yōu)化算法出現(xiàn)局部極值的現(xiàn)象，從而提高算法的性能，實驗結(jié)果表明該算法可以提高收斂速度，但收斂成效和精度較差，超體積指標出現(xiàn)異常值[4]；基于分解和差分進化的粒子群優(yōu)化算法通過一組向量的產(chǎn)生，確保時效均衡粒子分布的均勻性，采用時效均衡粒子重置策略，確保時效均衡粒子的多樣性，實現(xiàn)時效均衡粒子群的優(yōu)化，實驗顯示該算法在求解粒子群優(yōu)化問題方面具有收斂性好的優(yōu)勢，但是算法運行時間較長[5].

基于以上背景，本文在時空眾包環(huán)境下，設(shè)計了時效均衡改進粒子群優(yōu)化算法，從而提高了時效均衡改進粒子群優(yōu)化算法的優(yōu)化效果.

1 時效均衡改進粒子群優(yōu)化算法設(shè)計

1.1 選擇粒子群優(yōu)化參數(shù)

時效均衡改進粒子群優(yōu)化算法的設(shè)計需要控制一些參數(shù)，如粒子群的規(guī)模、學習因子、慣性權(quán)重、種群拓撲結(jié)構(gòu)及最大速度等，如何選擇粒子群優(yōu)化參數(shù)將對算法的優(yōu)化效果產(chǎn)生直接影響.

1.1.1 粒子群的慣性權(quán)重參數(shù)

粒子群慣性權(quán)重參數(shù)ω可以衡量粒子群優(yōu)化算法的搜索性能，使算法在整個計算過程中分配合理.粒子群慣性權(quán)重的增大,算法的搜索能力會隨著增強,而隨著粒子群慣性權(quán)重的減小,將使算法只在局部具有搜索能力[6].通常粒子群慣性權(quán)重參數(shù)的優(yōu)選范圍在0～1.4之間是最合適的，但是粒子群慣性權(quán)重參數(shù)的取值在0.8～1.2之間時，算法的收斂速度會加快.粒子群慣性權(quán)重參數(shù)設(shè)置在0.8～1.2范圍時,會提高算法的收斂速度.因此為了使算法在計算初期具有全局搜索能力、計算末期具有局部搜索能力，我們可以在優(yōu)選慣性權(quán)重參數(shù)時,將粒子群慣性權(quán)重設(shè)置為隨算法計算的進行而減小.因為算法具有計算代價和效果兩個因素,所以我們采取慣性權(quán)重線性削減策略，將慣性權(quán)重值降到0.4附近，作為粒子群慣性權(quán)重的優(yōu)選參數(shù).

時空眾包環(huán)境下，時效均衡粒子群優(yōu)化算法具有很多優(yōu)點，但是會使粒子群會追隨最優(yōu)粒子飛行，算法迭代計算若干次之后，會使得時效均衡粒子群產(chǎn)生很強的趨同性,導致算法的收斂速度減慢[7].為了克服算法在迭代計算方面的缺點，又考慮到慣性權(quán)重參數(shù)對算法性能的影響，將慣性權(quán)重值設(shè)置為0.7，隨著迭代計算次數(shù)的增加將慣性權(quán)重參數(shù)遞減到0.4，慣性權(quán)重參數(shù)的變化由式(1)確定：

(1)

式中，mmax表示權(quán)重參數(shù)質(zhì)量最大值，mmin表示權(quán)重參數(shù)最小值，Tmax表示所需最長計算時間.

1.1.2 學習因子c1和c2

慣性權(quán)重參數(shù)的引入可以提高算法的檢索性能，但是學習因子也影響著算法的性能[8].學習因子c1和c2的選擇是通過粒子群的運動軌跡，同時必須滿足c1+c2≤4.學習因子c1和c2是控制時效均衡粒子向最優(yōu)個體學習的因子，從而控制向粒子群內(nèi)的最優(yōu)點靠近.如果c1=0，則時效均衡粒子不具有自身經(jīng)驗，算法的收斂速度也比較快，但是當算法應用到復雜性較高的問題中時，會使算法極易進入局部最優(yōu)狀態(tài)；如果c2=0，說明時效均衡粒子只有自身經(jīng)驗，而沒有粒子群共享信息，由于時效均衡粒子個體之間不存在交流，算法得到解的概率很小[9].

學習因子c1和c2兩個參數(shù)都具有各自調(diào)節(jié)的功能，但是兩個參數(shù)的調(diào)節(jié)是相互脫離的，減弱了算法在計算過程中的統(tǒng)一性，不利于算法的優(yōu)化檢索性能.本文在時空眾包環(huán)境下，將學習因子選取慣性權(quán)重參數(shù)的非線性函數(shù)：

(2)

粒子群優(yōu)化算法的優(yōu)化算法隨著學習因子c1和c2的變化而變化，時效均衡粒子的速度也會發(fā)生變化，優(yōu)選學習因子c1和c2參數(shù)時，通常選擇c1=c2，并將參數(shù)的范圍設(shè)置在0～4之間.

1.1.3 最大速度vmax

在一次迭代計算過程中，時效均衡粒子的最大移動距離由最大速度vmax決定，算法的搜索能力會隨著vmax的增大而增強，只是與此同時容易導致時效均衡粒子最優(yōu)解的錯過；算法的開發(fā)能力會隨著vmax的值減小而增強，但會使算法極易進入局部最優(yōu)狀態(tài)[10].因此，通常采用調(diào)整慣性權(quán)重的方式來設(shè)置最大速度vmax的值.在時空眾包環(huán)境下，為了提高算法的統(tǒng)一性，一般采用通過對慣性權(quán)重參數(shù)動態(tài)調(diào)整學習因子和設(shè)置最大速度參數(shù)，完成粒子群參數(shù)的選擇.

1.2 提取時效均衡最優(yōu)粒子

時效均衡改進粒子群優(yōu)化算法往往忽略了對粒子個體極值更新的改進，通常采用粒子間的支配關(guān)系來提取時效均衡最優(yōu)粒子個體.時效均衡粒子群在進化過程中，會出現(xiàn)時效均衡粒子的極值得不到更新[11].首先，計算時效均衡粒子群中單個粒子的強度si，單個粒子的適應值fi，時效均衡粒子群中單個粒子的強度si可以根據(jù)式(3)計算：

(3)

式中，ni表示時效均衡粒子群中的第i個粒子所支配的粒子個體數(shù)，N表示時效均衡粒子群的規(guī)模.

在粒子群中，單個粒子的適應值fi是由種群所有支配給它的粒子個體強度來決定的，計算公式為

(4)

式中，si表示粒子個體s與i粒子之間的支配關(guān)系.假設(shè)fi為第i個粒子個體的適應值，時效均衡粒子群中最優(yōu)粒子個體的適應值為fm，粒子群整體的平均適應值為favg，則有

ΔF=|fm-favg|

(5)

ΔF的值越小，說明粒子群的收斂性越容易早熟.

令粒子個體的精度為ε，當ΔF>ε時，按照粒子間的支配關(guān)系，在粒子個體的當前位置和歷史位置中選擇比較優(yōu)秀的一個作為最優(yōu)位置；當ΔF<ε，就從粒子群的外部檔案中選擇一個非劣解與當前最優(yōu)解替換[12].提取時效均衡最優(yōu)粒子除了考慮粒子個體的選擇，還要考慮全局最優(yōu)粒子的選擇，一般通過在粒子群的非劣解集中隨機選擇一個解的方式作為全局最優(yōu)粒子.為了提高算法求解的多樣性，本文通過動態(tài)加權(quán)法完成對全局最優(yōu)粒子的提取[13].按照式(6)計算粒子群中各個粒子的適應度，計算公式為

(6)

式中，ai表示第i個粒子的位置，M表示粒子的最終位置.

本文利用粒子個體之間的支配關(guān)系,結(jié)合選擇個體最優(yōu)粒子和全局最優(yōu)粒子的選擇要求,完成了時效均衡最優(yōu)粒子的提取，從而改進粒子個體極值的更新[14]；接下來通過優(yōu)化時效均衡改進粒子群優(yōu)化算法設(shè)計，來實現(xiàn)時效均衡粒子群的優(yōu)化.

1.3 優(yōu)化時效均衡改進粒子群

在一個N維搜索空間中，粒子群優(yōu)化算法由M個粒子組成的粒子群X={X1，X2，…,XM}，t時刻，第i個粒子的位置表示為Xi(t)=[Xi,1(t),Xi,2(t),…,Xi,N(t)]，i=1,2,…,m，粒子不具有速度向量.粒子個體的最優(yōu)位置表示為Pi(t)=[Pi,1(t),Pi,2(t),…,Pi,N(t)]，粒子群的全局最好位置表示為G(t)=[G1(t),G2(t),…,GN(t)]，且存在G(t)=Pg(t).時效均衡改進粒子群優(yōu)化算法流程如圖1所示.

圖1 時效均衡改進粒子群優(yōu)化算法流程Fig.1 The flow of improved particle swarm optimization algorithm for time effective equilibrium

根據(jù)時效均衡改進粒子群優(yōu)化算法流程，詳細分析了時效均衡改進粒子群優(yōu)化算法的實現(xiàn)步驟：

Step1：在粒子群中對粒子的具體位置進行初始化；

Step2：計算粒子群的平均最優(yōu)位置；

Step3：對粒子當前位置的適應值進行計算,對比前一次迭代計算的適應值,如果小于前一次迭代計算的結(jié)果，則根據(jù)粒子的歷史位置更新成為粒子當前所處的位置，即如果存在f[Xi(t+1)]

Step5：比較前一次的迭代計算結(jié)果和粒子當前全局最優(yōu)位置,若粒子當前全局最優(yōu)位置的值比前一次的迭代計算結(jié)果的值更好，則利用粒子群全局最優(yōu)位置來更新粒子的位置；

Step6：計算粒子每一維的最優(yōu)位置，得到一個粒子的隨機點位置；

Step7：計算粒子所處的最新位置；

Step8：重復Step2～ Step7，直到滿足終止條件.

綜上所述，在時空眾包環(huán)境下，通過對粒子群的學習因子、慣性權(quán)重、最大速度等參數(shù)的選擇進行對粒子群優(yōu)化和對粒子群的個體粒子最優(yōu)位置和全局最優(yōu)粒子的選擇，完成時效均衡最優(yōu)粒子的提取；最后通過優(yōu)化時效均衡改進粒子群優(yōu)化算法設(shè)計，實現(xiàn)了時效均衡粒子群的優(yōu)化[15].

2 實驗對比分析

為了測試時效均衡改進粒子群優(yōu)化算法在時空眾包環(huán)境下的應用性能，進行仿真實驗，實驗采用Matlab設(shè)計，對時效均衡改進粒子群的節(jié)點覆蓋設(shè)定為200×200的二維平面，最優(yōu)子節(jié)點數(shù)為16，中繼傳輸節(jié)點的信息通信覆蓋半徑為R=1.25，總的節(jié)點規(guī)模為150，改進持續(xù)時間設(shè)定為20 min(持續(xù)12個采樣點)，采樣點的時間采樣間隔為12 min，最大迭代輪次為2 000，其他參數(shù)設(shè)定具體如表1所示.

表1 實驗參數(shù)設(shè)置Tab.1 Experimental parameter setting

根據(jù)上述環(huán)境和參數(shù)設(shè)定，進行時效均衡改進粒子群優(yōu)化試驗，分析ε指標值對比結(jié)果、超體積指標值對比結(jié)果以及算法運行時間對比結(jié)果，具體內(nèi)容如下所述.

2.1 ε指標值對比試驗

ε指標是一個用于評價粒子群優(yōu)化算法收斂性能的指標，可以使用任意兩個問題的解來判斷算法的收斂性.ε指標值對比實驗以測試函數(shù)變量個數(shù)為自變量，分別采用基于自適應動態(tài)改變的粒子群優(yōu)化算法、基于分解和差分進化的粒子群優(yōu)化算法及時空眾包環(huán)境下的粒子群優(yōu)化算法，對測試函數(shù)的求解問題進行優(yōu)化計算，得到ε指標值對比結(jié)果如圖2所示.

圖2 ε指標值對比結(jié)果Fig.2 Comparison results of ε index values

從圖2的實驗結(jié)果可以看出，測試函數(shù)變量個數(shù)在30個以內(nèi)時，三種粒子群優(yōu)化算法的收斂性保持基本一致，而當測試函數(shù)變量個數(shù)超過30以上時，基于自適應動態(tài)改變的粒子群優(yōu)化算法由于計算過程比較復雜，不能很好地控制求解個數(shù)，使得ε指標值變小，導致該算法的收斂性變差；基于分解和差分進化的粒子群優(yōu)化算法與基于自適應動態(tài)改變的粒子群優(yōu)化算法的收斂性相差不大，測試函數(shù)變量個數(shù)在70個～100個之間時，ε指標值始終比基于自適應動態(tài)改變的粒子群優(yōu)化算法大0.05，說明該算法的收斂性一般，可以滿足求解要求；而時空眾包環(huán)境下的粒子群優(yōu)化算法由于優(yōu)化參數(shù)的選擇，當測試函數(shù)變量個數(shù)超過40個時，ε指標值就開始迅速變大，可以求出問題的最優(yōu)解位置，說明該算法具有較強的收斂性.

2.2 超體積指標值對比試驗

超體積指標是指被非支配解集覆蓋的目標空間求解區(qū)域大小，通常用于評價測試函數(shù)的解集質(zhì)量.超體積指標值對比實驗以測試函數(shù)變量個數(shù)為自變量，分別采用基于自適應動態(tài)改變的粒子群優(yōu)化算法、基于分解和差分進化的粒子群優(yōu)化算法及時空眾包環(huán)境下的粒子群優(yōu)化算法，對測試函數(shù)的求解問題進行優(yōu)化計算，得到超體積指標值對比結(jié)果如圖3所示.

圖3 超體積指標值對比結(jié)果Fig.3 Comparison results of super volume index values

從圖3的實驗結(jié)果可以看出，采用基于自適應動態(tài)改變的粒子群優(yōu)化算法來求解測試函數(shù)時，當測試函數(shù)的變量個數(shù)為40個時，超體積指標值出現(xiàn)了異常值，原因可能是算法中沒有對參數(shù)進行優(yōu)化，使該算法計算得到的解集質(zhì)量變差；由于采用基于分解和差分進化的粒子群優(yōu)化算法缺少對解集最優(yōu)位置的提取，導致利用該算法求解測試函數(shù)時，經(jīng)常發(fā)生求解異常情況，但是由于超體積指標值相對較高，說明該算法計算得到的解集質(zhì)量良好；而采用時空眾包環(huán)境下的粒子群優(yōu)化算法來求解測試函數(shù)時，由于該算法不僅優(yōu)化的參數(shù)，還提取了解集的最優(yōu)位置，使超體積指標值隨著測試函數(shù)變量的增加而變大，計算得到的解集質(zhì)量非常好.

2.3 算法運行時間對比試驗

算法運行時間對比實驗以測試函數(shù)變量個數(shù)為自變量，分別采用基于自適應動態(tài)改變的粒子群優(yōu)化算法、基于分解和差分進化的粒子群優(yōu)化算法及時空眾包環(huán)境下的粒子群優(yōu)化算法，對測試函數(shù)的求解問題進行優(yōu)化計算，得到算法運行時間對比結(jié)果如表2所示.

表2 算法運行時間對比結(jié)果Tab.2 Comparison results of algorithm running time

從表2的實驗結(jié)果可以看出，時空眾包環(huán)境下的粒子群優(yōu)化算法的運行時間明顯少于其他兩種算法，隨著測試函數(shù)變量數(shù)量的增加，其他兩種算法的運行時間都超過10 ms，而測試函數(shù)變量數(shù)量對時空眾包環(huán)境下的粒子群優(yōu)化算法的影響較小，說明該算法的參數(shù)優(yōu)化部分,可以通過運行時間的減少,降低算法復雜度.

綜合以上實驗結(jié)果，無論是在收斂性、解集質(zhì)量還是算法運行時間方面，時空眾包環(huán)境下的粒子群優(yōu)化算法的性能明顯優(yōu)于其他兩種算法.

3 結(jié)束語

時效均衡改進粒子群優(yōu)化算法的設(shè)計需要對微粒群的規(guī)模、學習因子、慣性權(quán)重、群體拓撲結(jié)構(gòu)和最大速度等幾個參數(shù)進行控制，微粒群優(yōu)化參數(shù)的選取直接影響著算法的優(yōu)化效果.原有方法收斂成效和精度較差，超體積指標出現(xiàn)異常值且算法運行時間較長，為此本文提出了時空眾包環(huán)境下時效均衡改進粒子群優(yōu)化算法.在時空眾包環(huán)境下，通過上述提到的參數(shù)進行對粒子群優(yōu)化，且對粒子群的個體粒子最優(yōu)位置和全局最優(yōu)粒子進行選擇，完成對時效均衡最優(yōu)粒子的提取；最后通過優(yōu)化時效均衡改進粒子群優(yōu)化算法設(shè)計，實現(xiàn)了時效均衡粒子群的優(yōu)化.實驗結(jié)果顯示，時空眾包環(huán)境下的粒子群優(yōu)化算法的性能更好.對于未來的工作，可以考慮引入多目標對時效均衡粒子群優(yōu)化算法進行進一步研究，充分考慮優(yōu)化算法不同特征，并依據(jù)實際開發(fā)情況進行全新度量.