具有動態學習能力的分層進化粒子群優化算法

徐 超，單志勇，2，徐好好

（1.東華大學信息科學與技術學院；2.數字化紡織服裝技術教育部工程研究中心，上海 201620）

0 引言

粒子群優化（Particle Swarm Optimization，PSO）算法1995 年由Kennedy 等［1］提出。粒子群算法由于原理簡單、容易實現等優點，在實際工程中得到廣泛應用［2-4］，但是粒子群算法對于高維函數問題往往不能收斂到全局最優點，收斂精度不高。針對這些問題，研究人員引進多種理論改進粒子群算法，集中在算法本身改進和與其它算法混合兩個方面［5-7］。文獻［8］提出一種具有指數衰減慣性權重的粒子群優化算法，改進后的算法收斂精度和收斂速度都得到提升；文獻［9］利用余弦函數調整慣性權重與學習因子，增強粒子進化的多樣性；文獻［10］將引力搜索算法與動態多種群粒子群算法相結合，通過鄰域進化策略提高粒子全局搜索能力；Ghasemi 等［11］將學習因子與算法迭代次數線性組合，給予粒子跳躍的學習能力，增強粒子跳出局部極值的能力；劉軍梅［12］通過混沌效應，使種群數量隨優化過程變多，保護種群多樣性；文獻［13］提出一種層次學習粒子群優化算法，算法進化過程中保留最高層粒子，避免種群多樣性喪失，提高算法的全局收斂能力；Cheng 等［14］將粒子按照適應度值進行排序，根據粒子排序的不同調整粒子學習能力，算法在高維函數問題上具有良好的尋優性能。

本文結合文獻［13］的層次學習思想與文獻［14］的動態學習能力策略，對文獻［13］全局收斂能力不足和文獻［14］收斂速度慢的問題進行改進，提出一種具有動態學習能力的分層進化粒子群優化算法。首先將粒子按照適應度值排序，根據其適應度值將粒子分為多個層次；然后對不同層次的粒子選擇不同的進化策略，同時根據粒子在整個種群中排序的不同動態調整粒子的學習能力，使高層級粒子具有精確的搜索能力，低層級粒子具有較高的空間探索能力，在保證算法全局收斂能力的同時提高算法收斂速度；最后將本文提出的算法與標準粒子群算法（PSO）、慣性權重線性遞減粒子群算法（LDWPSO）、余弦學習因子粒子群算法（IPSO）與可擴展的社會學習粒子群算法（SLPSO）進行對比實驗，證實本文算法性能。

1 基本粒子群優化算法

隨機產生含有N 個粒子的種群，每個粒子都是D 維向量，用xi=[xi1,xi2,…,xiD]表示，第i個粒子對應的速度也為D 維向量，用vi=[vi1,vi2,…,viD]表示，其中i=1,2,…,N，粒子更新公式如下：

其中：w為慣性權重，c1、c2為學習因子，r1、r2為[0,1]之間的隨機數，pbest(xi)表示第i個粒子自身經歷過的最優位置，gbest表示整個種群經歷過的最優位置。每個粒子通過不斷進化pbest和gbest來更新自身的速度與位置，從而尋找到優化問題的最優解［15-17］。

2 改進的粒子群算法

2.1 算法原理

2.1.1 排序分層與學習策略

在進化過程中，粒子通常處于不同演化狀態，不同的粒子學習能力也不同。為了區分粒子，根據適應度值將粒子劃分為不同層次。假設NP個粒子被劃分為NL個層級，每個層級NL以Li表示（1≤i≤NL）。在分層之前粒子首先按照適應度降序排序，較好的粒子屬于較高層級，層級指數也較大，L1是最低層，LNL是最高層。每層所含有的粒子數量大小由LS表示，很明顯，LS=NP/NL。假設粒子在整個種群中排名為m，粒子層級指數i與m的關系如下：

排序分層與學習策略如圖1 所示。

Fig.1 DHEPSO layered algorithm圖1 DHEPSO 算法分層

2.1.2 進化策略

為避免種群在迭代過程中過早喪失多樣性，同時保證算法收斂速度，本文對L1～LNL-2、LNL-1、LNL三個不同范圍層次的粒子采取不同的學習與進化策略。進化策略如下：

（1）L1～LNL-2層的粒子更新公式如下：

其中：i=1,2,…,NL-2；j=1,2,…LS；t代表當前迭代次數，表示第i層的第j個粒子，表示第rl1層的第K1個粒子，表示第rl2層的第K2個粒子，K1、K2屬于區間[1,LS]的隨機整數。注意：rl1、rl2屬于區間[i+1,NL]之間的隨機整數，并且rl1≠rl2。

pL為粒子對應的學習能力，粒子學習能力與該粒子在整個種群中排名負相關。粒子學習能力計算公式如下：

其中，D為粒子維數，m為將粒子適應度按照降序排列后該粒子在整個種群中的排名，α為控制學習因子，一般取α∈[0,1.5]。圖2 為NP=100、D=50 時，pL隨m和α的變化曲線。從圖中可以看出，在種群數量固定，粒子維數相同情況下，粒子的學習能力隨排名的增大遞減，控制學習因子α越小，粒子的學習能力隨排名的變化程度越大。

（2）LNL-1層的粒子向LNL層中兩個不同的粒子學習，LNL-1層粒子更新公式如下：

其中：r1，r2，r3為區間(0,1)內的隨機數，表示LNL-1層的第j個粒子，為對應速度；代表LNL層中兩個不同粒子。注意：Q1、Q2屬于區間[1,LS]之間的隨機整數，并且Q1≠Q2。

Fig.2 Particles learning curve圖2 粒子學習能力變化曲線

（3）LNL層粒子在整個種群進化過程中起主導作用。為避免整個種群在進化過程中過度向全局最優粒子學習，導致種群多樣性快速喪失，在升級最高層粒子時，保留最高層級中最優的兩個粒子。LNL層粒子更新公式如下：

其中：r1，r2，r3為區間(0,1)內的隨機數，代表第NL層中的第j個粒子，注意1≤j≤LS-2；代表LNL層中的兩個不同粒子，M1、M2屬于區間[j+1,LS]之間的隨機整數，并且M1≠M2。

2.2 DHEPSO 算法步驟

DHEPSO 算法步驟如下：①初始化種群數量NP、層數NL、控制學習因子α、最大迭代次MAX_FES；②計算所有粒子適應度值，全局最優位置為x，f(x)為對應的適應度值；③將粒子按照適應度降序排列，同時記錄粒子在種群中的排名m；④根據公式（4）求出粒子對應的學習能力pL；⑤根據m和公式（2）求出粒子對應的層級指數，將粒子劃分進對應層級；⑥根據公式（3）升級L1到LNL-2層粒子，如果f(xi,j)＜f(x)，則令x=xi,j，f(x)=f(xi,j)；⑦根據公式（5）升級LNL-1層粒子，如果f(xNL-1,j)＜f(x)，則令x=xNL-1,j，f(x)=f(xNL-1,j)；⑧根據公式（6）升級LNL層粒子，如果f(xNL,j)＜f(x)，則令x=xNL,j，f(x)=f(xNL,j)；⑨更新全局最優位置x和全局極值f(x)；⑩如果達到最大迭代次數則算法終止，輸出全局最優位置和全局極值，否則跳到步驟③。

3 仿真實驗與結果分析

3.1 測試函數

為驗證本文算法的正確性，選取4 個典型測試函數［18-20］進行仿真對比實驗，測試函數公式與搜索范圍如表1 所示。

3.2 實驗設置

實驗硬件環境為AMD A10-4600M,CPU 為2.40 GHz，內存為8 GB，在Matlab 2018a 下完成。

Table 1 4 typical test functions表1 4 個典型測試函數

為驗證本文算法的有效性，選取PSO 算法、LDWPSO算法、IPSO 算法、SLPSO 算法與DHEPSO 算法進行仿真對比實驗，各種算法獨立運行30 次，統計粒子適應度的平均值與標準差。設置所有算法初始種群數量NP=100，最大迭代次數500 次，函數粒子維數分別取30 維和50 維。各算法的初始參數設置如表2 所示。

Table 2 Algorithm initial parameters settings表2 算法初始參數設置

3.3 結果分析

5 種算法在4 個測試函數上的標準差（Std）和適應度平均值（Mean）統計數據如表3 所示，實驗最好結果用粗體表示。

Table 3 5 kinds of PSO algorithm simulation results of four test function表3 5 種PSO 算法對4 個測試函數仿真結果

由表3 可以看出，對于所選的測試函數除f2和f4外，DHEPSO 算法在所規定的迭代次數內達到全局最優。DHEPSO 算法相對于基本PSO 算法和其它兩種對比算法，在收斂精度和穩定性上都有很大優勢。雖然f2和f4函數沒有收斂到全局最優，但是由表中數據可以看出其它對比算法優化效果較差，并且對于f2函數，DHEPSO 算法的優化結果比其它算法低了14 個數量級。

為了更直觀表現出算法的收斂情況和適應度變化情況，圖3 給出在50 維時部分算法的適應度對比曲線，其中f1和f6函數的縱坐標是以10 為底取對數的結果。由圖3中的適應度曲線可以看出，DHEPSO 算法在4 個測試函數中收斂速度最快，同時全局收斂能力最好。

Fig.3 Algorithm fitness curves圖3 算法適應度曲線

4 結語

本文在標準粒子群算法基礎上提出一種具有動態學習能力的分層進化粒子群優化算法，結合分層進化策略與動態學習能力思想，避免迭代后期種群多樣性喪失，有效提高了全局收斂能力，同時保證了算法收斂速度。在4 個典型測試函數上本文算法均取得良好成績，證明本文算法具有良好的優化性能。但是算法在高維病態函數上性能提升較小，這是以后改進方向。通過對標準粒子群算法與其改進算法的深入研究可知，對粒子群算法初始種群、慣性權重、學習因子等方面進行合理改進，均可有效提升算法性能。