時空眾包環境下時效均衡改進粒子群優化算法

黃素葉

閩西職業技術學院，福建 龍巖 364021

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

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

基于以上背景，本文在時空眾包環境下，設計了時效均衡改進粒子群優化算法，從而提高了時效均衡改進粒子群優化算法的優化效果.

1 時效均衡改進粒子群優化算法設計

1.1 選擇粒子群優化參數

時效均衡改進粒子群優化算法的設計需要控制一些參數，如粒子群的規模、學習因子、慣性權重、種群拓撲結構及最大速度等，如何選擇粒子群優化參數將對算法的優化效果產生直接影響.

1.1.1 粒子群的慣性權重參數

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

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

(1)

式中，mmax表示權重參數質量最大值，mmin表示權重參數最小值，Tmax表示所需最長計算時間.

1.1.2 學習因子c1和c2

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

學習因子c1和c2兩個參數都具有各自調節的功能，但是兩個參數的調節是相互脫離的，減弱了算法在計算過程中的統一性，不利于算法的優化檢索性能.本文在時空眾包環境下，將學習因子選取慣性權重參數的非線性函數：

(2)

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

1.1.3 最大速度vmax

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

1.2 提取時效均衡最優粒子

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

(3)

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

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

(4)

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

ΔF=|fm-favg|

(5)

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

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

(6)

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

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

1.3 優化時效均衡改進粒子群

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

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

根據時效均衡改進粒子群優化算法流程，詳細分析了時效均衡改進粒子群優化算法的實現步驟：

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

Step2：計算粒子群的平均最優位置；

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

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

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

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

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

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

2 實驗對比分析

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

表1 實驗參數設置Tab.1 Experimental parameter setting

根據上述環境和參數設定，進行時效均衡改進粒子群優化試驗，分析ε指標值對比結果、超體積指標值對比結果以及算法運行時間對比結果，具體內容如下所述.

2.1 ε指標值對比試驗

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

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

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

2.2 超體積指標值對比試驗

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

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

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

2.3 算法運行時間對比試驗

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

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

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

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

3 結束語

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