獨立自適應調整參數的粒子群優化算法*

張其文，尉雅晨

蘭州理工大學 計算機與通信學院，蘭州 730050

1 引言

粒子群算法（particle warm optimization，PSO）[1]是由Kennedy 和Eberhart 博士于1995 年共同提出來的一種模仿鳥類群體行為的智能優化算法。該算法已得到了廣泛的應用[2-3]。粒子群算法具有實現簡單、控制參數少等優點，粒子群算法的收斂性能取決于“勘探”與“開發”之間的平衡，而算法中參數的合理選擇對粒子群算法平衡“勘探”與“開發”起重要作用。典型的參數調整包括：慣性權重、學習因子、最大速度、收縮因子等。Zhang 等[4]提出利用貝葉斯技術根據粒子的位置自適應調整慣性權重，提高了算法在多維復雜函數中的收斂精度及速度。Taherkhani等[5]提出了基于穩定性的自適應慣性權重，且學習因子根據慣性權重自適應調整，算法的求解質量和收斂速度都有明顯的提高。Tian 等[6]提出了一種介于線性與非線性之間的自適應改變慣性權重的方法，使算法具有更好地平衡“勘探”與“開發”的能力。董紅斌等人[7]提出了一種動態調整慣性權重的粒子群算法，使算法具有跳出局部最優的能力。蔣麗等[8]在二階振蕩粒子群算法的基礎上改進振蕩環節的參數取值，采用互不相同的參數取值調節了粒子群算法的全局與局部搜索能力，提高了種群多樣性。黃洋等[9]提出了一種基于S 型函數的自適應粒子群算法，算法根據倒S 型函數的特點對慣性權重進行非線性調整，有效平衡了算法的全局搜索與局部搜索能力。張鑫等[10]提出利用鎖定因子及當前粒子的位置自適應調整慣性權重的自適應簡化粒子群算法，實驗結果表明算法具有較好的收斂能力。此外，Liang等[11]將綜合學習策略應用于粒子群算法中，使用粒子的歷史最佳位置來更新粒子的速度，維持種群的多樣性，有效地防止算法過早收斂。Tanweer 等[12]提出自調節粒子群算法，采用最佳粒子的慣性權重自調節和其余粒子通過對全局最佳位置的感知來確定搜索方向的兩種學習策略，算法在大多數問題上表現出良好的收斂能力。李煒等[13]提出一種改進粒子群算法，該算法通過結合特征聚類信息改進了種群的初始化策略，且根據粒子在決策空間中的密度，對粒子進行交互操作，保持種群的多樣性，避免過早收斂。

目前，大部分改進粒子群算法均在不同程度上提高了算法的收斂性能，但它們在參數設置方面均基于種群，沒有考慮粒子與粒子間進化能力的差異及種群整體的進化情況，在進化的每一代中所有粒子的參數設置是相同的，這樣全局搜索與局部搜索就很難達到平衡。針對這一問題，本文提出了獨立自適應參數調整的粒子群優化算法，通過獨立粒子的進化能力、種群進化能力及進化率來動態調整每個粒子的參數，增強算法平衡全局搜索與局部搜索的能力。同時加入粒子重構策略使進化能力較弱的粒子通過向進化能力較強的粒子進行學習生成新粒子，這既增加了種群多樣性，也使算法能跳出局部最優。

2 粒子群算法

1998 年Shi 和Eberhart[14]首次提出將慣性權重添加到粒子群算法的速度更新公式當中去，如下所示：

其中，t為當前迭代次數，r1、r2為[0,1]之間的隨機數，用來維持種群的多樣性。Pb為個體歷史最優位置，Gb為群體歷史最優位置，c1、c2為學習因子。ω稱為慣性權重，它用于表示粒子上一代的速度對當前粒子運動行為的影響。目前使用較多的慣性權重的設置方式是隨迭代次數的增加而線性減小：

其中，ωinit為初始權重，ωend為最終權重，T為最大迭代次數。

3 參數的調整

在進化過程中，粒子與粒子之間的進化能力、種群的整體進化能力、求解的問題均不同，因此本文在對參數的設置方面充分考慮了這些不同之處，使參數能在不同的情況下進行自適應調整。

定義1（粒子進化能力）在進化過程中，將粒子進化能力定義為該粒子相較于其他粒子能找到的較好解的能力。

定義2（種群進化能力）在進化過程中，將種群進化能力定義為種群中所有粒子能找到比當前最優解更好解的能力。

粒子的進化能力與種群的進化能力計算公式如下：

定義3（進化率）在進化過程中，將粒子的進化率定義為粒子在種群中進化能力變化程度的大小。

粒子在種群中進化能力的進化率計算如下：

若粒子進化能力及種群進化能力都較強時，粒子進化率較小，則粒子在下一代會較多地繼承上一代粒子的進化能力，反之亦然。

3.1 自適應慣性權重

本文根據粒子進化能力與種群的進化能力為每個粒子設置自適應慣性權重，這樣既保證了粒子的多樣性，又方便粒子更好地在空間中進行搜索。獨立粒子的慣性權重設置公式如式（7）所示：

綜上所述，在t+1 代時每個粒子慣性權重的調整都由第t代時粒子進化能力和種群進化能力共同決定。群體中的粒子能否發現比當前全局最優更好的解決定了粒子的搜索范圍，而粒子本身進化能力的強弱則是設置獨立粒子慣性權重的關鍵。

3.2 自適應學習因子

學習因子是體現粒子向自身歷史最優學習與向群體歷史最優學習能力的兩個參數。本文在將學習因子c1設計為遞減函數、c2設計為遞增函數的基礎上根據粒子進化能力的變化率去調整每一代中每個粒子的學習因子。這樣的設置方式與其他經典學習因子的取值方式相比，不但能在迭代初期保證粒子的學習能力，加強全局搜索；在迭代后期保證粒子的社會學習，利于局部精準搜索，還通過獨立粒子之間不同的進化率，對學習因子進行調整，使粒子結合自身情況調整學習模式。調整公式如下所示：

其中，c1max表示學習因子的最大值；c2min表示學習因子的最小值。粒子在迭代初期應該具有較強的自我學習能力，此時的c1值較大，c2值較小。若某粒子i的進化率較小，那么該粒子相比其他粒子的c1稍大、c2稍小，更有利于該粒子進行全局搜索。隨著迭代次數的增加，粒子應該具有較強的社會學習能力，此時的c1值較小，c2值較大。若粒子i的進化率較大，那么該粒子相比其他粒子的c1稍小、c2稍大，更有利于該粒子進行局部搜索。本文中，每個粒子的學習因子均根據粒子進化能力的變化率進行自適應調整。式中的參數取值c1max=2,c2min=0.8。

4 粒子重構策略

為了進一步保障種群多樣性，使粒子有跳出局部最優的能力，本文采用粒子重構策略，它的主要思想是從種群中選擇出部分進化能力較弱的粒子向進化能力較強的粒子進行學習，重新構造出新粒子。

4.1 粒子的選擇

由式（4）可知，在進化過程中，粒子的進化能力與該粒子的適應度值相關，因此本文將粒子適應度值的好壞作為評判粒子進化能力強弱的標準。在使用粒子重構策略前，先將種群中的粒子按照適應度值進行排序，選擇出末尾的個粒子作為進化能力較弱的粒子，這部分粒子將進行重構操作。剩余的個粒子為進化能力較強的粒子，是進化能力較弱的粒子進行重構時需要學習的范例。其中由式（10）、式（11）進行確定：

其中，N表示種群的總規模。被選擇重構的粒子數是隨著迭代次數t的增加而增長的，被選擇重構的粒子數最大可達到種群總規模的80%。

4.2 粒子的重構

最后將新生成的粒子與進化能力較強的粒子合并后一起進行下一次迭代。該策略的優勢在于它既能有效地拓寬種群的搜索范圍，又能保證算法的收斂精度與速度。

5 獨立自適應調整參數的粒子群優化算法

5.1 算法的收斂性分析

算法參數的選取和算法的收斂性是決定粒子群算法性能與效率的重要因素，因此對算法的收斂條件及滿足收斂時參數的取值范圍進行分析是十分有必要的。為了使下面對粒子群算法的分析更加方便直觀，在不失一般性的條件下，將粒子的速度與位置的維數從D維簡化為1 維，令Pi為粒子i自身找到的最好的位置，Pg為整個種群找到的最好位置，令：

因此可以將PSO 的速度與位置公式簡化如下：

再令：

可將式（13）、式（14）表示為：

定義4（平衡點）將R*定義為動態系統R(t+1)=A*R(t)的平衡點，在本文中，平衡點R*必須滿足條件：?t≥0 均滿足R(t+1)=R(t)。

根據李亞普諾夫的穩定性可知，系統收斂到平衡點的充分必要條件是A的全部特征值均要小于或等于1。

|A-λE|=0 稱為矩陣A的特征方程。矩陣A的特征值為特征方程λ2-(ω+1-φ)λ+ω=0 的解，因此解得線性系統R的兩個特征值為：

其中Δ=(ω+1-φ)2-4ω

對Δ=0,Δ＞0,Δ＜0 分別討論后，得出系統R(t)的收斂域為：

系統收斂的充分必要條件為：

本文根據粒子自身進化與種群進化能力對每個粒子進行自適應獨立參數設置，其中參數的取值為ωinit=0.9,ωend=0.4,c1max=c2max=2,c1min=c2min=0.8。根據式（4）～式（9）可得：

由此可得IAP-PSO 中關于參數的設置滿足算法的收斂條件，證明該算法具有在搜索空間中收斂到局部最優點甚至是全局最優點的能力。

5.2 算法的具體流程

IAP-PSO 算法的基本步驟：

步驟1 隨機初始化N個粒子，初始化參數ωinit、ωend、c1max、c2max、c1min、c2min，最大迭代次數T，問題維度D等。

步驟2 計算粒子的適應度值，找出個體最優Pb與全局最優Gb。

步驟3 根據式（1）、式（2）更新粒子的速度與位置。

步驟4 計算粒子的適應度值，更新個體最優與全局最優。

步驟5 根據式（4）～式（9）計算出粒子i在第t+1代時的慣性權重及學習因子。

步驟6 選擇出進化能力較弱的粒子，根據式（12）向進化能力較強的粒子進行學習，重構新粒子，將新粒子與進化能力較強的粒子合并。

步驟7 判斷算法是否達到終止條件，若滿足，則算法停止并輸出最優值；若不滿足，跳轉到步驟3 繼續執行。

5.3 時間復雜度分析

由IAP-PSO 算法可知，其主要包括如下部分：（1）初始化，時間復雜度為O(N×D)；（2）粒子進行速度與位置的更新，時間復雜度為O(N×D)；（3）計算粒子適應度值，更新個體最優及全局最優的時間復雜度為O(N×D)；（4）自適應調整粒子的慣性權重與學習因子，時間復雜度均為O(N×D)；（5）計算粒子的進化能力，選出需要重構的粒子進行粒子重構，時間復雜度為O(N×D)；（6）判斷迭代是否停止的時間復雜度為O(1)。因此，IAP-PSO 算法的時間復雜度為O(N×D)。

6 實驗分析與結果

6.1 算法的多樣性分析

粒子群算法易陷入局部最優點的主要原因就是種群在迭代后期種群多樣性下降。以函數Schwefel為例，將IAP-PSO、PSO 算法進行多樣性對比。圖1為兩個算法在迭代初期進行初始化時的種群分布圖，圖2 為迭代后期兩個算法迭代到全局最優值為3 000 左右（算法還未收斂）時的種群分布圖。

由圖1 可知兩算法在迭代初期粒子分布都較為均勻。從圖2 中可以看出，兩種算法迭代到后期時，IAP-PSO 算法仍保持著較高的多樣性，粒子分布均勻，具有強的進化能力。而PSO 算法的多樣性明顯劣于IAP-PSO 算法，已呈現出聚集狀態。

6.2 測試函數

對CEC2013 標準測試函數集中的10 個基準函數進行仿真實驗，用于測試IAP-PSO 算法的性能，測試函數的具體信息如表1 所示。

Fig.1 Initial population distribution圖1 初始種群分布

Fig.2 Population distribution in later stages圖2 后期種群分布

Table 1 10 test functions used in experiment表1 實驗中使用的10 個測試函數

6.3 對比算法

為了驗證IAP-PSO 算法在求解復雜問題時的性能，將IAP-PSO 算法與動態調整慣性權重的粒子群算法（particle swarm optimization algorithm for dynamic adjustment of inertia weight，DIW-PSO）[7]、綜合學習粒子群算法（comprehensive learning particle swarm optimiser，CLPSO）[11]、自調整粒子群算法（self regulating particle swarm optimization algorithm，SRPSO）[12]及標準PSO[13]進行對比實驗。為了保證測試的公平性，算法的參數設置均相同：種群規模為40，迭代次數為1 000，分別在D=10、30、50 時獨立運行30次。實驗環境為：Intel i5 CPU 2.50 GHz，RAM 4 GB，Windows 7操作系統，Matlab R2016a。

6.4 算法性能測試的實驗結果與分析

表2～表4 分別是D=10,30,50 時PSO、CLPSO、SRPSO、DIW-PSO 與IAP-PSO 算法在測試函數上的結果，其中包括最優解、最差解、平均值和標準偏差。借鑒文獻[15]的數據統計與分析方法，采用顯著性水平為0.05 的Wilcoxon 秩檢驗方法來判斷算法性能。其中“+”“-”“～”分別表示IAP-PSO 算法的結果優于、劣于、相當于對應算法的測試結果。

從表2～表4 結果中得出，與其他算法相比，IAPPSO無論在低維還是高維，均能在單峰函數、多峰函數和組合函數中找到更好的結果。從表5的Wilcoxon結果來看，在α=0.05 時IAP-PSO 算法在測試函數上相較于對比算法均獲得了明顯的優勢。值得說明的是，相較其他算法IAP-PSO 算法在求解高維問題時具有突出優勢。此外，在圖3～圖8 中分別展示了算法在部分函數上收斂情況，從圖中可以清晰地觀察出IAP-PSO 算法在收斂速度與收斂精度上均具有顯著優勢。雖然IAP-PSO 算法自身也存在不足，當維數增加時，算法的穩定性相比其他算法略顯不足，但總的來說，IAP-PSO 算法與其他算法相比，在優化結果上都大有提升。

6.5 算法運行時間對比

為進一步說明IAP-PSO 算法在尋優速度上的優勢，使算法在相同的實驗環境下獨立運行20 次，粒子數均為40，記錄算法達到指定收斂精度時的運行時間。如果迭代到200 000 次后仍達不到要求的精度，則用“—”表示，如表6 所示。

Table 2 Optimized results of comparison algorithms on test functions(D=10)表2 對比算法對測試函數的優化結果（D=10）

Table 3 Optimized results of comparison algorithms on test functions(D=30)表3 對比算法對測試函數的優化結果（D=30)

Table 4 Optimized results of comparison algorithms on test functions(D=50)表4 對比算法對測試函數的優化結果(D=50）

Table 5 Results obtained by Wilcoxon test表5 通過Wilcoxon 的測試得到結果

Table 6 Running time of algorithm to achieve specified accuracy表6 算法達到指定精度的運行時間 s

Fig.3 Convergence curve of f1（D=30）圖3 函數f1的收斂曲線（D=30）

Fig.4 Convergence curve of f1（D=50）圖4 函數f1的收斂曲線（D=50）

Fig.5 Convergence curve of f6（D=30）圖5 函數f6的收斂曲線（D=30）

Fig.6 Convergence curve of f6（D=50）圖6 函數f6的收斂曲線（D=50）

Fig.7 Convergence curve of f10（D=30）圖7 函數f10的收斂曲線（D=30）

Fig.8 Convergence curve of f10（D=50）圖8 函數f10的收斂曲線（D=50）

由表6 知，在實驗環境相同的情況下，IAP-PSO算法達到指定精度要求時所運行的時間要比標準粒子群算法及其改進算法的運行時間更優，從運行時間方面再次驗證了IAP-PSO 算法的有效性。

7 結束語

為更好地達到粒子群算法局部搜索與全局搜索之間的平衡，本文提出獨立自適應調整參數的粒子群算法。算法利用粒子進化能力與種群進化能力的不同，自適應地調整每個粒子的慣性權重和學習因子。算法中還加入粒子重構策略，使每一代粒子中進化能力較弱的粒子向進化能力較強的粒子進行學習，并重新構造出新粒子，這既增加了種群的多樣性，也提高了算法的收斂性能。實驗結果表明，在解決高維復雜問題時該算法在收斂速度與收斂精度上都有明顯的優勢。在部分測試函數中IAP-PSO 算法的穩定性有待提高，并且算法應在實際應用問題中驗證其有效性，以上問題將是下一步研究的主要內容。