基于高斯學(xué)習(xí)多峰延遲粒子群優(yōu)化算法

康朝海, 王思琪, 任偉建, 王博宇

(1. 東北石油大學(xué) 電氣信息工程學(xué)院, 黑龍江 大慶 163318； 2. 本田技研科技有限公司 技術(shù)三部, 廣州 510760)

0 引 言

標(biāo)準(zhǔn)粒子群在解決復(fù)雜的多峰函數(shù)時(shí)容易陷入局部最優(yōu)值[1], 從而限制了PSO(Particle Swarm Optimization)的廣泛應(yīng)用。因此, 加快收斂速度和避免局部最優(yōu)成為PSO研究中最重要也是最有吸引力的兩個(gè)目標(biāo)。雖然現(xiàn)有研究已提出了許多變體PSO算法分別實(shí)現(xiàn)這兩個(gè)目標(biāo)[1-4], 但很難同時(shí)實(shí)現(xiàn)這兩個(gè)目標(biāo)。例如, 文獻(xiàn)[1]的綜合學(xué)習(xí)PSO(Comprehensive-Learning PSO)著重于避免局部最優(yōu), 但由此導(dǎo)致收斂速度變慢。為同時(shí)實(shí)現(xiàn)這兩個(gè)目標(biāo), 筆者通過(guò)引入高斯學(xué)習(xí)提高算法收斂速度。在此基礎(chǔ)上, 根據(jù)粒子分布特征進(jìn)行進(jìn)化狀態(tài)估計(jì), 然后針對(duì)4種狀態(tài)引入延遲因子避免局部最優(yōu)。對(duì)單峰多峰函數(shù)的仿真實(shí)驗(yàn)表明, 改進(jìn)的混合算法提高了收斂速度, 同時(shí)增強(qiáng)了粒子逃脫局部最優(yōu)的能力。

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

1.1 粒子群算法原理

PSO方法是受到鳥(niǎo)群覓食的啟發(fā)所提出的模型。粒子種群個(gè)體視為無(wú)質(zhì)量無(wú)體積的粒子, 粒子在搜索空間內(nèi)運(yùn)動(dòng), 其運(yùn)動(dòng)過(guò)程是一個(gè)社會(huì)學(xué)習(xí)和自我學(xué)習(xí)的過(guò)程, 在學(xué)習(xí)過(guò)程中不斷對(duì)自己的搜索方向及搜索速度進(jìn)行調(diào)整。

粒子群[5]中每個(gè)粒子i在搜索空間進(jìn)行搜索時(shí)要考慮兩個(gè)重要的向量, 即速度向量和位置向量。在進(jìn)化迭代過(guò)程中, 粒子i按照下式運(yùn)動(dòng)

(1)

1.2 粒子群的研究現(xiàn)狀

粒子群算法由于其簡(jiǎn)單高效而得到廣泛應(yīng)用。目前眾多學(xué)者已提出了各種方法提高PSO的尋優(yōu)能力[6]。兩個(gè)較為突出的改進(jìn)方法分別是調(diào)節(jié)算法參數(shù)和結(jié)合輔助搜索算子。其中, 合理權(quán)衡全局搜索和局部搜索可為找到最優(yōu)解提供有效的幫助, Shi等[7-9]將慣性權(quán)重的概念引入標(biāo)準(zhǔn)粒子群算法中, 提出ω線性遞減, 迭代生成慣性權(quán)重

(2)

其中ωmin為慣性權(quán)重初值；ωmax為慣性權(quán)重終值；g為當(dāng)前迭代次數(shù)；G為最大迭代次數(shù)。

較大的慣性權(quán)重會(huì)使PSO偏向于全局搜尋, 而較小的慣性權(quán)重偏向于局部搜尋[10]。因此,ωmin和ωmax通常分別設(shè)定為0.9和0.4。此外, 文獻(xiàn)[11]已提出了PSO-TVAC(PSO with Time-Vary Acceleration Coefficients), 算法如下

(3)

(4)

其中c1i、c1f、c2i和c2f為常數(shù)。

Zhan等[12]提出了一種自適應(yīng)PSO(Adaptive-Particle-Swarm-Optimization)算法, 引入了一個(gè)進(jìn)化因子(EF: Evolutionary Factor)量化平均距離(全局最佳粒子和其他粒子之間的距離)。根據(jù)進(jìn)化因素, 通過(guò)一系列模糊隸屬函數(shù), 定義了4種狀態(tài), 即探索狀態(tài)、 開(kāi)發(fā)狀態(tài)、 收斂狀態(tài)和跳出狀態(tài)。這4種狀態(tài)已被用于每次迭代中自適應(yīng)地控制慣性權(quán)重和加速度系數(shù)。Tang等[13]提出了一種SPSO(Switching PSO)算法, 克服了文獻(xiàn)[12]算法的缺點(diǎn)。馬爾可夫鏈根據(jù)進(jìn)化因子決定的當(dāng)前形態(tài)預(yù)測(cè)下一個(gè)形態(tài), 且速度更新規(guī)則根據(jù)進(jìn)化狀態(tài)更新為另一種模式。

2 高斯學(xué)習(xí)策略

筆者在已有的高斯學(xué)習(xí)[14-15]基礎(chǔ)上進(jìn)行改進(jìn), 調(diào)整高斯學(xué)習(xí)的調(diào)用時(shí)機(jī)和適用個(gè)體。當(dāng)全局最優(yōu)值連續(xù)3代無(wú)變化時(shí), 對(duì)全局最優(yōu)個(gè)體和本次迭代中最優(yōu)的前10%個(gè)體進(jìn)行高斯學(xué)習(xí), 在擴(kuò)大學(xué)習(xí)對(duì)象的同時(shí)降低多次學(xué)習(xí)對(duì)整體算法運(yùn)行速度的影響。

高斯學(xué)習(xí)是以引入高斯分布為基礎(chǔ), 從原有的最優(yōu)個(gè)體隨機(jī)選取某一維加上一個(gè)高斯隨機(jī)擾動(dòng)項(xiàng), 其他維度保持不變, 從而獲得一個(gè)新個(gè)體。若新個(gè)體適應(yīng)度值優(yōu)于原個(gè)體, 則保留新個(gè)體； 否則不保留。其學(xué)習(xí)方式為

Pd=Pd+(Xmax-Xmin)G(μ,σ2)

(5)

d=r(1,D)

(6)

其中P為當(dāng)前最優(yōu)個(gè)體的位置；d為該個(gè)體的一個(gè)隨機(jī)維度；Xmax和Xmin為維度分量的上界和下界；G(μ,σ2)是服從高斯分布N(μ,δ2)的隨機(jī)數(shù),μ為高斯分布的均值；σ2為高斯分布的方差；r(1,D)為產(chǎn)生1～D之間的隨機(jī)整數(shù), 其中D為總維數(shù)。

為了提高算法的收斂速度, 將高斯學(xué)習(xí)策略[16]引入標(biāo)準(zhǔn)粒子群中, 對(duì)6種標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行Matlab仿真, 結(jié)果證明收斂速度較標(biāo)準(zhǔn)粒子群算法快。

3 基于高斯學(xué)習(xí)多峰延遲粒子群優(yōu)化算法

粒子群算法是基于種群的迭代算法, 在解決復(fù)雜的多峰函數(shù)問(wèn)題時(shí), 為具備更好的全局搜尋能力, 筆者在之前演化狀態(tài)估計(jì)ESE(Evolutionary State Estimation)技術(shù)[17-18]中引入高斯學(xué)習(xí), 并在粒子群速度公式上加入延遲因子, 有效地避免局部最優(yōu)并且提高收斂速度。通過(guò)評(píng)價(jià)每次迭代的進(jìn)化因子, 根據(jù)粒子群的間隔對(duì)進(jìn)化狀態(tài)進(jìn)行分類。然后, 根據(jù)進(jìn)化狀態(tài), 速度更新模型將從一種模式切換到另一種模式。此外, 為減少局部陷阱現(xiàn)象并擴(kuò)大搜索空間, 將多峰延遲信息添加到速度更新模型中。

3.1 粒子群的進(jìn)化狀態(tài)估計(jì)

由文獻(xiàn)[12]可知, 在PSO過(guò)程中, 粒子分布特征不僅隨迭代次數(shù)變化, 而且隨進(jìn)化狀態(tài)變化。例如, 在早期階段, 粒子可能散布在各個(gè)區(qū)域, 因此粒子是分散的。然而, 隨著演化過(guò)程的繼續(xù), 粒子將聚集在一起并聚合到局部或全局優(yōu)化區(qū)域, 因此粒子分布信息與早期的信息不同。

根據(jù)搜索過(guò)程中的進(jìn)化因子, 收斂狀態(tài)、 開(kāi)發(fā)狀態(tài)、 探索狀態(tài)和跳出狀態(tài)分別用S1,S2,S3,S4表示。種群中第i個(gè)粒子和其他粒子之間的平均距離

(7)

其中M為群體大??；D為粒子維數(shù)。因此, 進(jìn)化因子

圖1 狀態(tài)分配圖Fig.1 State assignment

(8)

其中dg為全局最優(yōu)粒子與群體其他粒子之間的平均距離；dmax和dmin分別為種群中di的最大值和最小值。進(jìn)化狀態(tài)根據(jù)進(jìn)化因子由一系列模糊函數(shù)進(jìn)行分類, 根據(jù)馬爾可夫鏈, 等式分割策略用文獻(xiàn)[19-20]中的狀態(tài)預(yù)測(cè)對(duì)進(jìn)化狀態(tài)分類。進(jìn)化狀態(tài)估計(jì)利用粒子分布和相對(duì)粒子適應(yīng)性的形成, 在狀態(tài)的過(guò)渡期采用單例方法進(jìn)行最終分類, 4種狀態(tài)分配圖如圖1所示。

進(jìn)化狀態(tài)

(9)

3.2 多峰延遲粒子群策略

為進(jìn)一步提高粒子群算法的搜索能力, 文獻(xiàn)[13]提出了切換PSO算法(SPSO), 其速度方程由馬爾科夫鏈確定, 將馬爾可夫跳躍參數(shù)引入速度和位置的更新方程中, 其更新方式為

vi(k+1)=ω(k)vi(k)+c1(Si(k))r1j(k)(pi(k)-xi(k))+

c2(Si(k))r2j(k)(pg(k)-xi(k)),xi(k+1)=xi(k)+vi(k+1)

(10)

其中c1(Si(k))和c2(Si(k))為加速度系數(shù)；j(k)為馬爾科夫跳躍參數(shù)；pi(k)為粒子建立的最佳位置；pg(k)為整個(gè)群體中最好的位置。

然而, PSO算法還有一定的空間用于增強(qiáng)其擺脫早熟收斂的能力, 文獻(xiàn)[21]提出了具有延遲信息的切換延遲PSO算法(Switching delayed PSO),不僅可改善全局搜索, 還可增強(qiáng)快速到達(dá)gbest的能力。此算法的速度和位置方程為

vi(k+1)=ω(k)vi(k)+c1(Si(k))r1(pi(k-τ1(Si(k)))-xi(k))+

c2(Si(k))r2(pg(k-τ2(Si(k)))-xi(k)),xi(k+1)=xi(k)+vi(k+1)

(11)

其中常數(shù)τ1(Si(k))和τ2(Si(k))為延遲因子。

為更徹底搜索整個(gè)空間, 文獻(xiàn)[22]提出了多模延遲粒子群策略, 在新的學(xué)習(xí)策略中, 使用MDPSO(Multimodal Delayed PSO)算法, 其位置和速度更新式為

vi(k+1)=ωvi(k)+c1r1(pi(k)-xi(k))+c2r2(pg(k)-xi(k))+

si(k)c3r3(pi(k-τi(k))-xi(k))

+sg(k)c4r4(pg(k-τg(k))-xi(k))xi(k+1)=xi(k)+vi(k+1)

(12)

其中τi(k)和τg(k)分別為局部和全局延遲最佳粒子在[0,k]中均勻分布的隨機(jī)延遲；ri(i=1,2,3,4)是[0,1]中的隨機(jī)均勻分布數(shù);si(k)和sg(k)是速度更新模型中新增項(xiàng)的強(qiáng)度因子, 其值取決于進(jìn)化因子[21], 并按照如下方式設(shè)置。

1) 收斂狀態(tài)S1： 群體中的粒子有望盡快地飛入全局最優(yōu)點(diǎn)附近的區(qū)域。因此, 速度更新模型中省略延遲信息, 即將si(k)和sg(k)都設(shè)置為零。

2) 開(kāi)發(fā)狀態(tài)S2： 群中的粒子容易陷入局部最佳粒子周?chē)膮^(qū)域。因此, 局部延遲信息被加入到速度更新模型中, 即在強(qiáng)度因子si(k)=S2(k)的情況下, 隨機(jī)選擇先前迭代中的局部最佳粒子用于速度更新。

3) 探索狀態(tài)S3： 盡可能多地搜索最優(yōu)值很重要。因此, 為了更徹底探索整個(gè)空間, 引進(jìn)全局延遲信息, 即強(qiáng)度因子sg(k)=S3(k), 隨機(jī)選擇先前迭代中的全局最優(yōu)粒子用于速度更新。

4) 跳出狀態(tài)S4： 局部最佳粒子急于從局部最優(yōu)點(diǎn)周?chē)膮^(qū)域跳出。因此, 要為這些粒子提供更多的能量從這個(gè)區(qū)域逃逸, 同時(shí)引進(jìn)局部和全局延遲信息, 即強(qiáng)度因子si(k)=S4(k)和sg(k)=S4(k)。

由式(3)和式(4)可得：c1=c3和c2=c4。

3.3 改進(jìn)算法步驟及流程圖

多峰延遲粒子群策略雖然會(huì)對(duì)搜索空間進(jìn)行徹底搜索并且更有可能獲得全局最優(yōu), 但是該策略會(huì)略微降低收斂速度。由上述分析可知, 引入高斯學(xué)習(xí)策略可有效提高收斂速度。筆者在上述多峰延遲粒子群算法中引進(jìn)改進(jìn)高斯學(xué)習(xí)策略, 算法步驟如下。

Step1 初始化粒子群和算法參數(shù)。根據(jù)式(2)～式(4)計(jì)算出相應(yīng)的ω和ci。

Step2 計(jì)算評(píng)估每個(gè)粒子的適應(yīng)值, 更換pbest和gbest, 并將其留存為歷史信息。

Step3 判斷全局最優(yōu)值是否連續(xù)3代無(wú)變化, 滿足則根據(jù)式(5)和式(6)對(duì)全局最優(yōu)值和本次迭代最優(yōu)的前10%個(gè)體進(jìn)行一次高斯學(xué)習(xí)。

Step4 在當(dāng)前位置, 根據(jù)式(7)計(jì)算每個(gè)粒子i到所有其他粒子的平均距離di。

Step5 比較所有di并確定最大距離dmax和最小距離dmin。將全局最佳粒子di定義為dg。通過(guò)式(8)計(jì)算進(jìn)化因子, 通過(guò)式(9)確定進(jìn)化狀態(tài)。

Step6 根據(jù)隨機(jī)延遲τi(k)、τg(k)和強(qiáng)度因子si(k)、sg(k)的設(shè)置方式更新多峰延遲信息。

Step7 根據(jù)式(12), 更新粒子速度和位置。

Step8 判斷是否達(dá)到最大迭代次數(shù), 滿足則輸出全局最優(yōu)值； 否則返回執(zhí)行Step2。

算法流程圖如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flowchart

4 仿真實(shí)驗(yàn)

4.1 基準(zhǔn)函數(shù)的配置

在下面的仿真實(shí)例中, 采用了一些常用的基準(zhǔn)函數(shù)評(píng)估基于高斯學(xué)習(xí)多峰式延遲粒子群算法的性能?；鶞?zhǔn)函數(shù)由方程式給出, 如表1所示。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

表1中, 球函數(shù)f1(x)是典型單峰優(yōu)化問(wèn)題, 通常用于測(cè)驗(yàn)優(yōu)化算法的收斂速度；由于Rosenbrock函數(shù)f2(x)很難獲取全局最優(yōu), 它可看成多峰函數(shù)；f3(x)到f6(x)是其他典型單峰、 多峰函數(shù), 它們都很難獲取全局最優(yōu)值。為此, 表1展示了基準(zhǔn)函數(shù)的具體配置, 第4列是基準(zhǔn)函數(shù)的最優(yōu)值, 第5列是每個(gè)維度的搜索空間。

4.2 算法仿真

仿真采用表1的基準(zhǔn)函數(shù), 同時(shí)引入標(biāo)準(zhǔn)粒子群(PSO)算法進(jìn)行對(duì)比, 對(duì)比圖如圖3所示。

圖3 標(biāo)準(zhǔn)函數(shù)適應(yīng)度迭代曲線對(duì)比Fig.3 Comparison of standard function fitness value iteration curves

由圖3可知, 改進(jìn)的高斯學(xué)習(xí)可有效克服標(biāo)準(zhǔn)粒子群算法處理多峰的復(fù)雜問(wèn)題時(shí)收斂速度慢的缺點(diǎn)。6個(gè)測(cè)試函數(shù)的仿真實(shí)驗(yàn)中, Ackley的測(cè)試效果改進(jìn)最為明顯, GLPSO收斂速度明顯提高。

由上述仿真啟發(fā), 針對(duì)粒子群對(duì)多峰函數(shù)[23-24]尋優(yōu)能力的問(wèn)題, 引入改進(jìn)的高斯學(xué)習(xí)提高算法收斂速度, 并在此基礎(chǔ)上對(duì)4種進(jìn)化狀態(tài)加入延遲因子以避免陷入局部最優(yōu), 提出一種基于高斯學(xué)習(xí)的多峰延遲粒子群策略。

與此同時(shí), 引入PSO-LDIW(Linearly Decreasing Ineria Weight)、 PSO-TVAC(Time-Vary Acceleration Coefficients)、 PSO-CK(Constriction Factor)、 SPSO和SD(Switching Delayed)PSO、 MD(Modified Discrete)PSO 6種相應(yīng)標(biāo)準(zhǔn)的PSO算法與提出的GLMDPSO算法進(jìn)行比較。參數(shù)設(shè)置如下： 種群S=20, 種群維數(shù)D=20, 最大迭代次數(shù)N=1 000。每個(gè)實(shí)驗(yàn)獨(dú)立重復(fù)50次, 用于后續(xù)的統(tǒng)計(jì)分析。

4.3 仿真分析

上述PSO算法對(duì)每個(gè)基準(zhǔn)函數(shù)的平均適應(yīng)度曲線如圖4所示, 其中水平坐標(biāo)表示迭代次數(shù), 垂直坐標(biāo)的值用對(duì)數(shù)形式表示。

a Spere函數(shù)適應(yīng)度對(duì)數(shù)迭代曲線 b Rosenbrock函數(shù)適應(yīng)度對(duì)數(shù)迭代曲線 c Ackley函數(shù)適應(yīng)度對(duì)數(shù)迭代曲線

d Rastrigin函數(shù)適應(yīng)度對(duì)數(shù)迭代曲線 e Schwefel2.22函數(shù)適應(yīng)度對(duì)數(shù)迭代曲線 f Schwefel1.2函數(shù)適應(yīng)度對(duì)數(shù)迭代曲線圖4 標(biāo)準(zhǔn)函數(shù)適應(yīng)度值對(duì)數(shù)迭代曲線對(duì)比Fig.4 Comparison of logarithmic iterative curve of standard function fitness value

表2列出了各算法分別運(yùn)行50次適應(yīng)度的最小值、 平均值和標(biāo)準(zhǔn)差及每個(gè)算法對(duì)基準(zhǔn)函數(shù)尋優(yōu)的成功率。如表2所示, 一些算法對(duì)基準(zhǔn)函數(shù)的優(yōu)化成功率非常低, 即隨著迭代的增加, 算法的最優(yōu)解不會(huì)收斂到閾值以下, 因此它們和GLMDPSO算法相比, 平均值相差較大。GLMDPSO算法在Rosenbrock、 Ackley和Rastrigin基準(zhǔn)函數(shù)上的尋優(yōu)效果和收斂速度優(yōu)于其他算法。在Sphere函數(shù)中, PSO-CK和SPSO收斂速度稍快。由圖3和表2可知, GLMDPSO算法比其他算法具有更好的全局搜尋能力。由圖3可以看出, GLMDPSO的收斂速度比MDPSO的收斂速度更快, GLMDPSO仿真時(shí)間為17.820 3 s, 而MDPSO仿真時(shí)間為20.786 s。即GLMDPSO具有更強(qiáng)搜尋能力的同時(shí)還彌補(bǔ)了MDPSO收斂速度慢的缺點(diǎn)。因此, 筆者提出的GLMDPSO算法在標(biāo)準(zhǔn)評(píng)價(jià)中優(yōu)于其他PSO算法。

表2 7種算法在標(biāo)準(zhǔn)測(cè)試函數(shù)上的尋優(yōu)結(jié)果比較

(續(xù)表2)

函數(shù)性能指標(biāo)SDPSOMDPSOGLMDPSO平均值7.454302×10-41.580958×10-149.627854×10-15標(biāo)準(zhǔn)差1.029872×10-33.457360×10-144.422219×10-15成功率1.001.001.00Rastringin最小值7.966303×1004.974795×1003.979836×100平均值2.923278×1011.247678×1011.225792×101標(biāo)準(zhǔn)差1.655272×1014.066255×1003.905231×100成功率0.881.001.00Schwefel2.22最小值1.655272×1014.734266×10-278.967679×10-27平均值3.400491×1002.703748×10-193.258009×10-18標(biāo)準(zhǔn)差5.573131×1001.213013×10-181.294193×10-17成功率0.701.001.00Schwefel1.2最小值3.276157×1001.092504×10-152.279216×10-17平均值4.283769×1025.110758×10-101.800463×10-9標(biāo)準(zhǔn)差1.368428×1031.539366×10-91.090594×10-8成功率0.121.001.00

5 結(jié) 語(yǔ)

針對(duì)粒子群算法迭代最優(yōu)值搜索停滯及收斂精度低的問(wèn)題, 引入高斯學(xué)習(xí), 有效地加快收斂速度, 解決了算法收斂慢、 精度低的問(wèn)題。同時(shí)根據(jù)粒子群的進(jìn)化狀態(tài)估計(jì), 采用基于改進(jìn)高斯學(xué)習(xí)多峰延遲粒子群策略進(jìn)一步提升全局和局部搜索能力。為了對(duì)比其他6種算法, 針對(duì)6個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行數(shù)值仿真實(shí)驗(yàn), 實(shí)驗(yàn)結(jié)果證明了筆者算法可提高收斂速度, 同時(shí)保證良好的搜尋能力。