融合迭代和問題維度的速度約束粒子群算法

王子航，劉建華，薛醒思，朱 劍，陳宇翔

（1.福建工程學院計算機科學與數學學院，福建 福州 350118;2.福建工程學院福建省大數據挖掘與應用技術重點實驗室，福建 福州 350118）

粒子群優化算法 （particle swarm optimization,PSO）最初是由Eberhart 等[1]和Kennedy 等[2]于1995年提出，通過模擬動物群體的社會行為，比如鳥群的捕食行為，構建一種群體智能優化算法。與其他遺傳算法[3]和蟻群算法[4]等智能算法相比PSO 算法具有實現簡單且收斂速度快的優勢，廣泛應用于很多領域，比如函數優化[5]，神經網絡訓練[6]，軌跡優化[7]等。PSO算法在運算前期效果較好，在后期存在易陷入局部最優值問題，因此學者們提出了各種各樣的改進方法。例如，鄧浩等[8]提出了自適應權重參數調整的PSO算法；張德華等[9]提出了具有不同學習策略的PSO 算法；Wang 等[10]則將其他優化算法與粒子群算法結合，得到新的PSO 算法。各種PSO 算法從PSO 不同元素中改進，提升了算法精度與性能。

速度約束是PSO 算法運行過程中的一個步驟操作，目的是防止粒子跳出搜索空間，避免出現不可行解。最早的速度約束策略采用固定值[11]，然后出現對PSO 速度邊界約束的研究和改進策略，例如，Helwig 等[12]提出并比較了多種用于粒子群優化的速度邊界約束處理技術；Jiang 等[13]研究了速度約束策略解決高維問題存在的缺陷并提出了幾種解決方案。近年來，有學者提出一些自適應速度約束策略，并提高了算法的性能。例如，Barrera 等[14]提出速度邊界隨迭代次數而幾何變化的策略；Adewumi 等[15]提出在粒子每代計算速度最高值和最低值的絕對值，據此計算速度邊界。

隨迭代次數而變化的速度約束策略具有自適應性，可以更好地提高算法性能。但是，由于PSO 算法的種群狀態不確定，其局部搜索有可能發生在初始階段，而全局搜索也可能發生在后期，因此速度邊界不僅受迭代次數影響，還應該與粒子群的狀態有關。Li 等[16]提出一種基于種群狀態的自適應速度約束粒子群算法（particle swarm optimization with statebased adaptive velocity limit strategy，PSOSAVL），通過評估種群進化狀態值而設置速度約束范圍，提高算法性能。但PSOSAVL 算法只是根據粒子之間的距離評估種群進化狀態，并沒有考慮迭代次數，所以還是存在陷入局部最優的風險。

同時，PSO 算法與求解問題的維度有關，根據維度提出改進算法的策略，可以提高其性能。例如，蔣曉屾等[17]提出，算法粒子每一維采用不同衰減權重，提高了多樣性和局部搜索能力；鄧志誠等[18]提出一種具有動態子空間隨機單維變異粒子群算法，當某維退化且算法性能下降時，該維采用變異，有效地提升算法收斂速度和求解質量。然而，對于PSO算法速度約束與求解問題維度的關系，目前并沒有發現文獻研究。

基于上述的分析，本文提出一種融合迭代和問題維度的速度約束粒子群算法 （PSO with velocity limit combining iteration and problem dimension，VLPSOID）。該算法不僅計算種群進化狀態評估值（evolutionary state evaluation，ESE），而且考慮了迭代次數和求解問題的維度。算法首先設計受迭代次數和維度影響的計算公式，將其融合進化狀態評估值計算中，再根據進化狀態評價估值確定速度約束范圍，使用算法速度約束既受迭代變化影響，也受到問題維度影響，具有自適應性，提高了粒子群算法的性能。

1 相關知識介紹

1.1 粒子群優化算法

在每次迭代過程中，粒子群算法計算每個粒子速度，更新自身位置，并且速度受到群體最優位置和自身歷史最優位置的影響。標準的PSO 算法的數學描述如下。

假設粒子種群規模為N，問題維度為D；第i 個粒子位置向量xi=（），速度向量vi=（，）；第i 個粒子第d 維的速度和位置在t 代的更新如下

式中：t 為當前迭代數；ω 為慣性權重；c1和c2為加速因子；為第t 代第i 個粒子第d 維的速度；r1和r2為介于0 和1 之間的隨機數；為第t 代第i 個粒子第d 維的位置；為第i 個粒子第d 維的個體歷史最優位置；為整個粒子群第t 代第d 維的全局最優位置。

1.2 進化狀態評估策略

進化狀態評估策略是評估計算算法粒子種群狀態值，判斷算法當前搜索狀態并改進算法，使用PSO 算法具有自適應性。Zhan 等[19]提出一種自適應粒子群優化算法（adaptive particle swarm optimization, APSO），首次采用進化狀態評估（evolutionary state evaluation, ESE）策略改進PSO 算法；后來也有文獻提出改進的ESE 策略[20]，提高了算法效率。ESE策略考慮了種群粒子分布狀態及其適應度值，根據進化狀態評估值將種群狀態分為4 種類型：探索，開發，收斂以及跳出。種群進化狀態評估值定義如下，假定f 為種群進化狀態評估值，則f 值通過式（4）和式（5）兩步計算得到。

式中：Li為第i 個粒子到其他粒子的平均距離，Lg為全局最佳粒子到其他粒子的平均距離，Lmin和Lmax分別為Li的最大值和最小值。根據式（5），Li值為0和1 之間的值，式（4）是體現一個粒子到其他粒子之間平均距離，式（5）將種群最優粒子平均距離歸一化處理，得到種群ESE 值f，然后用于控制粒子速度約束。

但是，式（5）評估種群進化狀態值，只是采用全局最優粒子的平均距離，存在陷入局部最優風險。本文提出一種融合迭代和問題維度的自適應進化狀態評估策略，改進種群狀態評估方法，改進粒子群算法的速度約束，形成一種融合迭代和問題維度的速度約束粒子群算法。

2 融合迭代和問題維度的速度約束粒子群算法

本算法采用了融合迭代和問題維度的自適應進化狀態評估策略，其方法是先由式（4）和式（5）計算f 值；然后讓其受當前迭代次數t 和求解問題維度D 影響，得到新的狀態評估值f＾，如式（6）。這里s（t）和h（D）分別表示受到迭代次數t 和問題維度D 影響的公式，各自采用了不同影響策略，影響著原始種群狀態評估值f。s（t）為迭代策略，h（D）為維度策略

式中：η 為影響系數，η∈（0，1），控制兩個策略對原始種群狀態評估值f 的影響程度。

2.1 迭代策略

PSO 算法要盡可能地在前期處于探索狀態，在后期處于開發狀態。當種群狀態評估值采用式（5）計算f 值時，應考慮迭代次數t 對其影響，目的是使f 值在前期相對較大，在后期慢慢變小。這樣算法在前期全局搜索能力較強，能夠搜尋更大空間，容易跳出局部最優點；算法在后期局部搜索能力增強，重點搜索有希望的局部區域。因此，本小節設計一個迭代策略，使其影響種群狀態評估值f，使其值隨著迭代遞減。

本文設計迭代策略s（t）如式（7），tmax為最大迭代次數。圖1 則表示s（t）是隨迭代t 指數遞減的圖像。如圖1 所示，s（t）在迭代前期，值相對較大，而隨迭代變化，s（t）值緩慢下降，最后值為1。指數遞減比線性遞減下降更快，容易使f 值突變，全局搜索能力下降快，其變化范圍從e 到1。

圖1 迭代策略值隨迭代次數的變化Fig.1 Change of iteration strategy value with iteration

2.2 維度策略

隨著問題維度增大，PSO 算法計算成本增加，搜索效率降低。由于在更新高維的粒子位置時，粒子每個維度都同時到達最佳位置的概率降低，粒子更可能遠離最佳位置，降低算法性能。因此PSO 算法會受到問題維度的影響，本節設計維度策略，使種群狀態評估值f 受求解問題維度D 影響，其值隨維度D 增加而增加，增強算法的全局搜索能力。

本文設計策略函數h（D）如式（8）所示，其變化如圖2 所示。在低維時，h 值變化比較大，而隨著維度增加，h 值變化慢慢變平緩，最終趨于穩定。

圖2 維度策略值隨問題維度的變化Fig.2 The change of dimension policy value with the problem dimension

2.3 種群進化狀態評價方法

在式（6）的基礎上，融合迭代策略和維度策略到ESE 值f 中，得到新ESE 值，其計算如下

式中：η 為影響系數，用于控制兩種策略影響ESE 值的程度，η∈（0，1），具體取值由實驗方法決定；t 為迭代次數；tmax為最大迭代次數；D 為求解問題維度。

2.4 進化狀態評估值決定速度約束的策略

2.4.1 速度約束的計算方法

假定μ 為PSO 速度約束值（VL）與其搜索最大位置（xmax）比例值，μ∈（0，1），而速度約束VL 限制在速度下邊界和上邊界［VLmin，VLmax］之間。

2.4.2 超參數設置方法

α 和β 為兩個超參數設置基于原則為，當f＾值越大時，PSO 算法種群傾向于全局搜索，粒子速度約束邊界變大；而當越小時，種群傾向于局部搜索，粒子速度約束邊界收縮。當時，VL 達到最大值VLmax，此時μ=μmin；當=0 時，VL 達到其最小值VLmin，此時μ=μmax。μmin，μmax分別為VL 與xmax的最大比例和最小比例。假設μmin和μmax已知，根據式（11）可得式（12），推導求解α 和β 值。當給定速度約束VL 的比例最大值μmax和比例最小值μmin時，可以根據式（12）設置式（11）的超參數α 和β 值。

2.5 融合迭代和問題維度的速度約束PSO 算法

本節PSO 算法速度約束公式為式（3），其速度邊界值VL 采用式（11）計算。式（11）VL 由進化狀態評估ESE 值f＾決定，而f＾值融合了迭代次數和問題維度的影響，得到一種融合迭代和問題維度的速度約束PSO 算法。

當PSO 算法求解的問題維度D 和其當前迭代次數t 已知，并設置好μmin和μmax時，可以用本文提出的相關策略及其公式，求解速度約束值VL 及其范圍值[-VL，VL]，其算法具體過程的偽代碼見算法Calc_VL，本文提出PSO 算法流程的偽代碼見算法Calc_Best。

2.6 時間復雜度分析

根據算法Calc_VL 和算法Calc_Best，VLPSOID算法的時間成本主要是：計算種群狀態，更新粒子的速度和位置。對于算法Calc_VL，時間成本主要為式（4），需要計算粒子之間的距離，涉及粒子之間每個維度，N 個粒子之間要相互計算，所以時間復雜度為O（D*N2）。對于算法Calc_Best，由于每次迭代調用算法Calc_VL，最后時間復雜度為O（tmax*D*N2）。算法Calc_Best 在更新粒子速度和位置時，時間復雜度為O（tmax*D*N）。綜上所述，VLPSOID 算法的最終時間復雜度為O（tmax*D*N2），主要時間成本花費在計算粒子之間的距離，原因是需要計算算法種群的狀態評估值（ESE）。

3 實驗分析

本節實驗分析方法用PSO 算法求解CEC2013中的28 個基準測試函數[21]，測試對比VLPSOID 算法與其他相關PSO 算法的性能。28 個函數的信息如表1 所示，共分為3 類：f1～f5為單峰函數；f6～f20為多峰函數；f21～f28為復合函數。與之對比算法有：基于種群狀態的自適應速度約束粒子群算法（PSOSAVL），基于分層自主學習的改進粒子群優化算法（HCPSO）[22]，具有拓撲時變和搜索擾動的混合粒子群優化算法（HPSO）[23]，以及標準PSO 算法；各算法的實驗參數設置采用原始論文的數據，如表2所示。

表1 CEC 2013 測試函數Tab.1 CEC 2013 benchmark functions

表2 用于比較的算法以及參數Tab.2 Algorithms and parameters for comparison

3.1 影響系數η 的敏感性分析

VLPSOID 算法式（9）的影響系數η 控制迭代次數和問題維度對原始ESE 值f 的影響強度，η∈（0，1）。但η 具體取值表現為影響敏感程度，本節采用實驗方法分析，根據η 取不同值時，分析VLPSOID 算法優化部分函數的實驗性能，尋求一個最優η 取值。

實驗的種群粒子數為30 個，最大迭代次數為20 000 次，實驗選擇的優化函數是f3，f8，f13，f18，f23，f286 種函數，函數維度分別為20，40，60，80，100 維；η 取[0，1]之間均衡地取不同的10 個值，實驗比較同一函數在同一個維度，其函數適應度值的大小。實驗結果如表3 所示，在η 取不同值時，算法計算函數在不同維度時的最優值。

表3 不同維度的最優值結果Tab.3 The best result with different η in different dimension

算法處于不同維度時，采用不同的η 值對結果的影響也是不同的。最終統計了所選6 個函數的結果，得到總結果表。由總結果表得到，當η 值分別取0.6，0.7，0.8 時，取得較好解的次數分別為6 次，7次，10 次。相比較其他值，當η 值為0.6，0.7，0.8 時，算法取得的結果更為突出。因此，為了能夠整體提升算法的性能，本文建議影響系數η 取值范圍在[0.6，0.8]。

3.2 對μmin 和μmax 的敏感性分析

算法的μmin和μmax是分別表示VL 與位置最大值μmax的最小比例和最大比例，決定式（12）計算超參數α 和β 值。本節針對部分測試函數，采用實驗方法，分析其取值的敏感度。實驗的測試函數為f12，f18，f23，f26；函數的維度為50 維，算法種群大小為30 個，最大迭代次數為50 000 次。實驗方法是，先固定μmin為0.5，測試μmax取[0.4，1.0]范圍內不同值時，算法求解函數最優值，實驗結果如表4 及圖3左側所示。然后，固定μmax為0.7，測試μmin取[0.1，0.7]范圍內不同值時，算法求解函數最優值，實驗結果如表5 及圖3 右側所示。

表4 不同μmax 值求解函數的最優值（μmin=0.5）Tab.4 The best value for different μmax（μmin=0.5）

表5 不同μmin 值求解函數的最優值（μmax=0.7）Tab.5 The best value for different μmin（μmax=0.7）

圖3 函數適應度隨μmax 和μmin 變化的曲線Fig.3 Curve of fitness as a function of μmax and μmin

觀察表4 數據，本文算法對μmax的取值不敏感并且不同的μmax取值都提供了較為滿意的結果，因此可以得出結論，本文算法對于變化的μmax具有健壯性。根據表4 以及圖3 左側的結果，建議μmax取值范圍[0.6，0.7]。觀察表5 數據，算法對μmin取值有一定的敏感性，當μmin取過小時，算法的優化效果變差，從圖3 各子圖的右側圖，也可得到驗證。因此，應避免μmin取0.1 和0.2 值。觀察表5 和圖3 左側，μmin取值范圍應該在[0.5，0.6]之間最佳。綜上所述，VLPSOID 對于變化的μmax具有魯棒性，而對μmin值具有敏感性。本文建議在[0.6，0.7] 內選擇μmax，在[0.5，0.6]內選擇μmin。

3.3 迭代策略影響VLPSOID 算法的分析

本小節將式（6）的迭代策略s（t）式去除，稱算法為VLPSOD，并與VLPSOID 的性能比較分析。實驗對28 個基準函數優化計算，兩個算法分別獨立運行10次，比較兩個算法求解函數的平均最優適應度。實驗設置種群粒子數為30 個，函數維度為30 維，算法迭代次數為10 000 次。實驗結果如表6 所示。

表6 VLPSOD 算法與VLPSOID 實驗對比Tab.6 Comparison between VLPSOD and VLPSOID

根據表6，與VLPSOID 算法相比，去除迭代策略的VLPSOD 算法性能出現降低。28 個測試函數,VLPSOD 在18 個函數中的表現要差于VLPSOID 算法（全部的5 個單峰函數，15 個多峰函數的9 個，8 個復合函數的4 個），表明VLPSOID 要優于VLPSOD。這說明迭代策略能使算法在前期增強全局搜索能力，后期增強局部搜索能力，促進算法尋優能力。因此，迭代策略能提高算法優化效果和性能。

3.4 維度策略影響VLPSOID 算法的分析

針對維度策略影響VLPSOID 算法性能分析，本節將式（6）的維度策略h（D）去除，稱算法為VLPSOI，并與VLPSOID 的性能比較分析。實驗選擇的優化函數是f3，f8，f13，f18，f23，f286 種函數, 兩個算法分別獨立運行10 次，比較兩個算法在求解不同維度的函數的平均最優適應度。實驗設置種群粒子數30 個，函數維度分別設置為30，60，90 維，算法迭代次數為50 000 次。實驗結果如表7 所示。

表7 VLPSOID 算法與VLPSOI 實驗對比Tab.7 Comparison between VLPSOID and VLPSOI

觀察表7 可知，與完整VLPSOID 算法相比，去除維度策略的VLPSOI 性能出現下降的趨勢。能夠明顯地看出VLPSOI 在這6 個測試函數的表現中差于VLPSOID，這說明，去除了維度策略，算法在高維空間尋優能力變差，導致性能降低。維度策略能提高算法的優化效果和性能。

3.5 VLPSOID 算法的性能分析

針對分析本文提出的VLPSOID 算法性能，將其與表2 列出的4 種算法在28 個測試函數上實驗比較，每個測試函數獨立運行50 次，得到其平均最優適應度值（Mean）及其標準方差（standard deviation, Std.）。實驗參數設置如表8 所示，實驗結果如表9 所示。

表8 實驗的參數設置Tab.8 Experimental parameters

表9 基準測試函數的實驗結果Tab.9 Experimental results of function tests

根據表9，相比其他算法，VLPSOID 在28 個函數中有14 個函數均值和方差表現為最好，其中5個單峰函數有4 個，15 個多峰函數中有6 個，8 個復合函數中有4 個；其他算法表現最好的HCPSO也只在28 個函數中有7 個；因此，在相比較的算法中，VLPSOID 的性能為最佳的算法。

雖然在28 個測試函數中，只有14 個函數效果優于其他算法，采用弗里德曼檢測方法可知，VLPSOID 算法無論是在單峰函數、多峰函數和復合函數的檢驗值，還是在綜合的檢驗值，在比較的算法中排名最好，說明其綜合性能最佳。

為了更好地驗證VLPSOID 算法性能有效性，針對表9 的實驗數據，做t 檢驗方法驗證。t 檢驗自由度和顯著性水平設置分別為49 和0.05，最終結果如表10 所示。其中，粗體表示本文算法好于對比算法，灰體表示本文算法表現較差。

從表中可以看出，與PSOSAVL 算法相比，算法性能只有在f14，f16，f21，f22，f25，f26這6 個函數上處于劣勢，其余函數則明顯處于優勢；而對比HPSO算法，可以看出VLPSOID 算法效果顯著；與HCPSO 算法相比，本文算法在7 個函數上效果差于對比算法。最后，與PSO 算法對比可以看出，本文算法只有在f8，f15，f16函數上處于劣勢。總體結果是，在28 個函數的對比中，本文算法好于PSOSAVL、HPSO、HCPSO 和PSO 的函數個數分別為22、28、21、25。綜上所述，本文算法在對比算法中有一定的競爭能力。

3.6 算法的收斂性分析

為分析算法的收斂狀態，采用VLPSOID 與其他幾個算法優化6 個基準測試函數，演示了每個算法計算測試函數的適應度隨迭代變化的曲線，結果如圖4。其中，6 個函數分別是，單峰函數選取一個函數，多峰函數選取3 個函數以及復合函數選取兩個函數。實驗參數設置種群維度為30 維，種群大小為30 個，迭代次數為150 000 次。

圖4 不同算法的函數適應度隨迭代變化圖Fig.4 Convergence curves of six test functions

由圖4（a）可知，VLPSOID 在單峰函數中與其他算法中表現相當。由圖4（b）、圖4（c）和圖4（d）中可知，VLPSOID 算法在多峰函數中表現良好，大約迭代到一萬代時，就能找到較好的解，收斂速度快且精度較高。從圖4（e）和圖4（f）能明顯得出，對于復合函數，VLPSOID 算法在前期下降速度相對于其他算法快，且在后期其精度也能得到保證。綜上所述，VLPSOID 不管在單峰函數還是多峰函數，其收斂速度較快且精度較高。

3.7 算法的運算時間評估

為了進一步驗證VLPSOID 在尋優速度上的優勢，在相同環境下，將各算法在CEC2013 測試集28個函數中分別獨立運行10 次，記錄達到指定精度時算法的平均運行時間，并規定，如果迭代次數超過200 000 次后仍未達到指定精度，則用空白表示。最終結果如表11 所示。

表11 算法達到指定精度的運算時間Tab.11 Running time of algorithm to achieve specified accuracys

由表11 看出，相較于對比算法，VLPSOID 的在5 個單峰函數和復合函數中表現稍差，而在多峰函數中，VLPSOID 的總體排名較為靠前。在本文中，由于VLPSOID 在每一代都需要對粒子的距離進行計算，從而計算算法種群的狀態評估值,因此在此階段需要額外的計算時間，會導致算法在部分測試函數中沒有表現出其尋優速度的優勢。但從表10 結果中可以看出，VLPSOID 在收斂精度有著出色的表現，因此一些時間上的損耗是可以接受的。

4 結論

1）VLPSOID 算法在前期具有較好的全局搜索能力，在后期具有較強的局部搜索能力，算法對問題維度具有擴展性。

2）在CEC2013 測試函數上，算法無論在單峰函數、多峰函數，還是復雜函數上，具有更好性能，更具有適用性，并具有解決不同維度問題的能力。