具有動(dòng)態(tài)學(xué)習(xí)能力的分層進(jìn)化粒子群優(yōu)化算法

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

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

0 引言

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

本文結(jié)合文獻(xiàn)［13］的層次學(xué)習(xí)思想與文獻(xiàn)［14］的動(dòng)態(tài)學(xué)習(xí)能力策略，對文獻(xiàn)［13］全局收斂能力不足和文獻(xiàn)［14］收斂速度慢的問題進(jìn)行改進(jìn)，提出一種具有動(dòng)態(tài)學(xué)習(xí)能力的分層進(jìn)化粒子群優(yōu)化算法。首先將粒子按照適應(yīng)度值排序，根據(jù)其適應(yīng)度值將粒子分為多個(gè)層次；然后對不同層次的粒子選擇不同的進(jìn)化策略，同時(shí)根據(jù)粒子在整個(gè)種群中排序的不同動(dòng)態(tài)調(diào)整粒子的學(xué)習(xí)能力，使高層級(jí)粒子具有精確的搜索能力，低層級(jí)粒子具有較高的空間探索能力，在保證算法全局收斂能力的同時(shí)提高算法收斂速度；最后將本文提出的算法與標(biāo)準(zhǔn)粒子群算法（PSO）、慣性權(quán)重線性遞減粒子群算法（LDWPSO）、余弦學(xué)習(xí)因子粒子群算法（IPSO）與可擴(kuò)展的社會(huì)學(xué)習(xí)粒子群算法（SLPSO）進(jìn)行對比實(shí)驗(yàn)，證實(shí)本文算法性能。

1 基本粒子群優(yōu)化算法

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

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

2 改進(jìn)的粒子群算法

2.1 算法原理

2.1.1 排序分層與學(xué)習(xí)策略

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

排序分層與學(xué)習(xí)策略如圖1 所示。

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

2.1.2 進(jìn)化策略

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

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

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

pL為粒子對應(yīng)的學(xué)習(xí)能力，粒子學(xué)習(xí)能力與該粒子在整個(gè)種群中排名負(fù)相關(guān)。粒子學(xué)習(xí)能力計(jì)算公式如下：

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

（2）LNL-1層的粒子向LNL層中兩個(gè)不同的粒子學(xué)習(xí)，LNL-1層粒子更新公式如下：

其中：r1，r2，r3為區(qū)間(0,1)內(nèi)的隨機(jī)數(shù)，表示LNL-1層的第j個(gè)粒子，為對應(yīng)速度；代表LNL層中兩個(gè)不同粒子。注意：Q1、Q2屬于區(qū)間[1,LS]之間的隨機(jī)整數(shù)，并且Q1≠Q(mào)2。

Fig.2 Particles learning curve圖2 粒子學(xué)習(xí)能力變化曲線

（3）LNL層粒子在整個(gè)種群進(jìn)化過程中起主導(dǎo)作用。為避免整個(gè)種群在進(jìn)化過程中過度向全局最優(yōu)粒子學(xué)習(xí)，導(dǎo)致種群多樣性快速喪失，在升級(jí)最高層粒子時(shí)，保留最高層級(jí)中最優(yōu)的兩個(gè)粒子。LNL層粒子更新公式如下：

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

2.2 DHEPSO 算法步驟

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 測試函數(shù)

為驗(yàn)證本文算法的正確性，選取4 個(gè)典型測試函數(shù)［18-20］進(jìn)行仿真對比實(shí)驗(yàn)，測試函數(shù)公式與搜索范圍如表1 所示。

3.2 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)硬件環(huán)境為AMD A10-4600M,CPU 為2.40 GHz，內(nèi)存為8 GB，在Matlab 2018a 下完成。

Table 1 4 typical test functions表1 4 個(gè)典型測試函數(shù)

為驗(yàn)證本文算法的有效性，選取PSO 算法、LDWPSO算法、IPSO 算法、SLPSO 算法與DHEPSO 算法進(jìn)行仿真對比實(shí)驗(yàn)，各種算法獨(dú)立運(yùn)行30 次，統(tǒng)計(jì)粒子適應(yīng)度的平均值與標(biāo)準(zhǔn)差。設(shè)置所有算法初始種群數(shù)量NP=100，最大迭代次數(shù)500 次，函數(shù)粒子維數(shù)分別取30 維和50 維。各算法的初始參數(shù)設(shè)置如表2 所示。

Table 2 Algorithm initial parameters settings表2 算法初始參數(shù)設(shè)置

3.3 結(jié)果分析

5 種算法在4 個(gè)測試函數(shù)上的標(biāo)準(zhǔn)差（Std）和適應(yīng)度平均值（Mean）統(tǒng)計(jì)數(shù)據(jù)如表3 所示，實(shí)驗(yàn)最好結(jié)果用粗體表示。

Table 3 5 kinds of PSO algorithm simulation results of four test function表3 5 種PSO 算法對4 個(gè)測試函數(shù)仿真結(jié)果

由表3 可以看出，對于所選的測試函數(shù)除f2和f4外，DHEPSO 算法在所規(guī)定的迭代次數(shù)內(nèi)達(dá)到全局最優(yōu)。DHEPSO 算法相對于基本PSO 算法和其它兩種對比算法，在收斂精度和穩(wěn)定性上都有很大優(yōu)勢。雖然f2和f4函數(shù)沒有收斂到全局最優(yōu)，但是由表中數(shù)據(jù)可以看出其它對比算法優(yōu)化效果較差，并且對于f2函數(shù)，DHEPSO 算法的優(yōu)化結(jié)果比其它算法低了14 個(gè)數(shù)量級(jí)。

為了更直觀表現(xiàn)出算法的收斂情況和適應(yīng)度變化情況，圖3 給出在50 維時(shí)部分算法的適應(yīng)度對比曲線，其中f1和f6函數(shù)的縱坐標(biāo)是以10 為底取對數(shù)的結(jié)果。由圖3中的適應(yīng)度曲線可以看出，DHEPSO 算法在4 個(gè)測試函數(shù)中收斂速度最快，同時(shí)全局收斂能力最好。

Fig.3 Algorithm fitness curves圖3 算法適應(yīng)度曲線

4 結(jié)語

本文在標(biāo)準(zhǔn)粒子群算法基礎(chǔ)上提出一種具有動(dòng)態(tài)學(xué)習(xí)能力的分層進(jìn)化粒子群優(yōu)化算法，結(jié)合分層進(jìn)化策略與動(dòng)態(tài)學(xué)習(xí)能力思想，避免迭代后期種群多樣性喪失，有效提高了全局收斂能力，同時(shí)保證了算法收斂速度。在4 個(gè)典型測試函數(shù)上本文算法均取得良好成績，證明本文算法具有良好的優(yōu)化性能。但是算法在高維病態(tài)函數(shù)上性能提升較小，這是以后改進(jìn)方向。通過對標(biāo)準(zhǔn)粒子群算法與其改進(jìn)算法的深入研究可知，對粒子群算法初始種群、慣性權(quán)重、學(xué)習(xí)因子等方面進(jìn)行合理改進(jìn)，均可有效提升算法性能。