徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)指導(dǎo)的粒子群優(yōu)化算法求解多峰優(yōu)化問題

張 瀟,宋 威,2

1(江南大學(xué) 人工智能與計算機學(xué)院,江蘇 無錫 214122)

2(江南大學(xué) 江蘇省模式識別與計算智能工程實驗室,江蘇 無錫 214122)

1 引 言

粒子群優(yōu)化(Particle Swarm Optimization,PSO)[1]算法一種典型的群體智能(Swarm Intelligence,SI)[2]算法,它模擬了自然界中生物種群的自組織交互行為,具有對問題解析性質(zhì)要求低,實現(xiàn)簡單且收斂速度快等優(yōu)點.在過去20年間PSO受到學(xué)術(shù)界的廣泛關(guān)注,并被應(yīng)用于特征選擇[3]、人群分類[4]、車間調(diào)度[5]和疫情傳播預(yù)測[6]等多種領(lǐng)域.然而,在現(xiàn)實世界中存在著大量多峰優(yōu)化問題.該類問題的特點是,在解空間中同時存在著多個局部最優(yōu)解與一個全局最優(yōu)解.利用傳統(tǒng)PSO算法求解多峰優(yōu)化問題時,由于缺乏多樣性且搜索動作選取不合理,導(dǎo)致其難以找到問題的全局最優(yōu)解.

目前,一些PSO的改進方法將種群劃分成多個子群,其目的是保持種群多樣性[7,8].然而這些方法大多依賴于人為經(jīng)驗或是預(yù)設(shè)的規(guī)則,根據(jù)各粒子在解空間中的位置,利用聚類或小生境的思想將整個種群劃分為多個子群,使各子群分布在解空間中的不同區(qū)域來進行搜索.Kennedy最早提出利用PSO算法來求解多峰優(yōu)化問題[9],其思路是利用k-means算法將種群聚成多個類簇,然后用類簇的中心作為該鄰域的最優(yōu)解,指導(dǎo)對應(yīng)類簇中粒子的學(xué)習(xí).Brits等人提出了一種基于小生境技術(shù)的PSO算法[10],具體內(nèi)容包括:如果主種群中某個粒子的適應(yīng)值在一定的迭代次數(shù)中變化較小,該粒子將和當(dāng)前主種群中距其最近的另一個粒子構(gòu)成一個小生境.此過程不斷循環(huán),最終實現(xiàn)子群的劃分.Parrott等人提出了一種基于種群生成的PSO算法[11],在運行的每一代,首先將當(dāng)前種群中適應(yīng)值最優(yōu)的粒子確定為一個種子,并利用該種子和空間中所有與它距離小于一定半徑的粒子來構(gòu)造一個種群.剩余的粒子會重復(fù)上述構(gòu)造過程,直到全部粒子均被劃分至不同的種群,因而使得不同種群將在不同的區(qū)域進行搜索.然而,上述的多子群方法需要與問題相關(guān)的先驗知識,如預(yù)先設(shè)置聚類簇的個數(shù)或種群半徑等,導(dǎo)致這些方法無法根據(jù)不同的優(yōu)化問題合理地劃分子群.而且這些方法也沒有對粒子的搜索動作進行精心地設(shè)計,影響了搜索的性能.針對上述問題,本文將徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)引入PSO,提出一種徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)指導(dǎo)的粒子群優(yōu)化(Radical Basis Function Neural Network Guided Particle Swarm Optimization,RBFNN-PSO)算法來求解多峰優(yōu)化問題,RBFNN-PSO利用徑向基函數(shù)指導(dǎo)網(wǎng)絡(luò)(RBF Guided Network,RBFGN),在保持種群多樣性的前提下,對包括定位學(xué)習(xí)目標(biāo)和調(diào)整加速系數(shù)在內(nèi)的搜索動作進行合理的指導(dǎo).

為了在搜索過程中保持種群多樣性,首先設(shè)計子群劃分方法,選擇能代表子群的搜索特性且與現(xiàn)有子群中心遠離的粒子作為子群中心.子群的搜索特性通過候選子群中心對由其確定的子群中所有粒子的重要性進行體現(xiàn).所設(shè)計的子群劃分方法通過選擇合適的子群中心,實現(xiàn)子群的劃分.因此,不同子群中的粒子在各自子群中心指導(dǎo)下搜索,呈現(xiàn)出多樣的搜索特性,提升了種群多樣性.其次,在考慮多樣性的同時,選擇各子群中心作為相應(yīng)子群中粒子的學(xué)習(xí)目標(biāo),實現(xiàn)了粒子學(xué)習(xí)目標(biāo)的定位.由于將粒子當(dāng)前位置映射為搜索動作屬于非線性映射,作為典型的非線性映射模型,本文利用徑向基函數(shù)神經(jīng)網(wǎng)絡(luò),實現(xiàn)從粒子位置到搜索動作的映射.同時,徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)屬于增量模型,能利用輸入的每個位置來更新網(wǎng)絡(luò).本文設(shè)計RBFGN的輸入為種群中每個粒子的當(dāng)前位置,之后利用獲取的子群中心設(shè)置其隱藏層節(jié)點.為了調(diào)整粒子的加速系數(shù),在RBFGN輸出層輸出當(dāng)前輸入粒子的加速系數(shù)調(diào)整動作,包括增加、減少加速系數(shù)或保持加速系數(shù)不變3個動作.最后,為了訓(xùn)練RBFGN,本文引入強化學(xué)習(xí)對網(wǎng)絡(luò)決策出的動作(包括定位學(xué)習(xí)目標(biāo)和調(diào)整加速系數(shù))進行獎勵或懲罰,其目的是根據(jù)反饋,獲得最大的累積收益,實現(xiàn)對隱藏層節(jié)點(代表子群中粒子的學(xué)習(xí)目標(biāo))和輸出動作相連權(quán)值(控制粒子的加速系數(shù))的有效調(diào)整,從而使RBFNN-PSO能合理指導(dǎo)粒子的搜索動作,以解決多峰優(yōu)化問題.

2 相關(guān)工作

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

PSO由Kennedy和Eberhart于1995年提出,它通過模擬鳥群覓食行為來尋找問題的最優(yōu)解.具體而言,PSO中每個粒子具有速度和位置兩種屬性,根據(jù)自身和種群的歷史最優(yōu)位置來確定下一步搜索動作.帶有慣性權(quán)重的標(biāo)準(zhǔn)PSO由Shi和Eberhart在1998年提出.每次迭代中,第i個粒子的速度和位置更新公式如下:

vi(t+1)=w×vi(t)+c1×r1×(pbesti-xi(t))
+c2×r2×(gbest-x(t))

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

其中,xi(t)表示第i個粒子在第t次迭代的位置,vi(t)表示第i個粒子在第t次迭代的速度,pbesti表示第i個粒子歷史最優(yōu)位置,gbest表示種群的歷史最優(yōu)位置.c1和c2代表兩個加速系數(shù),r1和r2是[0,1]范圍內(nèi)均勻分布的兩個隨機數(shù).w是慣性權(quán)重,用于控制各粒子上一代速度對當(dāng)前速度的影響.目前通用的慣性權(quán)重控制方法是使其隨著迭代次數(shù)的增加而線性減小[12]:

(3)

其中,wmax為迭代開始時最大的慣性權(quán)重值,wmin為迭代結(jié)束時最小的慣性權(quán)重值,Tmax表示最大迭代次數(shù).

2.2 徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)

徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)(Radical Basis Function Neural Network,RBFNN)于1988 年由Broomhead和Lowe提出.它屬于前饋型神經(jīng)網(wǎng)絡(luò),具有良好的泛化能力與較快的收斂速度,能以較高的精度逼近任意函數(shù),常用于擬合難以解析的非線性映射[13].RBFNN輸入層與隱藏層之間的連接僅起到傳輸數(shù)據(jù)的功能,因此前兩層間的權(quán)值均為1.隱藏層激活函數(shù)為徑向基函數(shù),通常選用高斯核函數(shù),高斯核函數(shù)包含中心μ與寬度σ兩個屬性,第k個隱藏層節(jié)點對于第i個輸入xi的激活結(jié)果為:

(4)

(5)

其中,αk是第k個隱藏層節(jié)點與輸出層相連的權(quán)值向量.

3 RBFNN-PSO算法

3.1 徑向基函數(shù)指導(dǎo)網(wǎng)絡(luò)RBFGN

本文設(shè)計RBFGN,其目的是獲取一種不依賴于先驗知識便可解決多峰優(yōu)化問題的方法,RBFGN通過提升種群多樣性并合理指導(dǎo)粒子的搜索動作來有效求解多峰優(yōu)化問題.由于需要將輸入的粒子位置映射為其對應(yīng)的搜索動作,此過程屬于非線性映射.作為典型的非線性映射模型,本文基于徑向基函數(shù)神經(jīng)網(wǎng)絡(luò),進一步設(shè)計RBFGN,實現(xiàn)從粒子位置到其搜索動作的映射,以更好解決多峰優(yōu)化問題.

本文構(gòu)造的RBFGN包含輸入層、隱藏層和輸出層,是一個緊湊的3層徑向基函數(shù)神經(jīng)網(wǎng)絡(luò).RBFGN的輸入為種群中每個粒子的當(dāng)前位置,因此,RBFGN的輸入層包含D個節(jié)點,對應(yīng)粒子位置在空間中的D個維度.輸入層與隱藏層之間的連接僅起到傳輸數(shù)據(jù)的功能,因此前兩層間的權(quán)值均為1.RBFGN的隱藏層包含若干個節(jié)點,每個節(jié)點代表一個子群,RBFGN通過調(diào)整隱藏層節(jié)點,實現(xiàn)對種群的劃分.隱藏層節(jié)點的中心μ與寬度σ對應(yīng)相應(yīng)子群的子群中心與子群寬度.為了使初始子群分布在解空間中的不同區(qū)域,本文利用層次的k-means聚類方法來初始化子群.首先將種群中的粒子劃分為l×k個類簇,由于種群規(guī)模(N=50)的限制,取l為2.隨后每兩個最相近的類簇將會融合,直到最后只剩下k個類簇,將k個類簇的中心作為初始的子群中心,每個類簇中所有粒子到中心的平均距離作為初始的子群寬度.受限于種群規(guī)模(N=50),初始的子群個數(shù)k設(shè)置為10,對應(yīng)初始的10個隱藏層節(jié)點.

在初始化RBFGN隱藏層節(jié)點之后,第i個輸入粒子xi經(jīng)過第k個隱藏層節(jié)點利用公式(4)進行激活,輸出的響應(yīng)為φk(xi).同時,由公式(4)可以看出,若xi離某個子群中心μk的距離大于子群半徑σk,它將會得到較小的響應(yīng).因此,xi受其最近子群中心的影響最大,該粒子將被分配到其最近子群中心所確定的子群中,并向該中心學(xué)習(xí).RBFGN輸出層包含3個節(jié)點,分別代表3個候選動作,即增加、減少局部加速系數(shù)cn或保持cn不變,其中cn控制著xi向其子群中心學(xué)習(xí)的力度.根據(jù)公式(5),擁有m個隱藏層節(jié)點的RBFGN輸出為zi.為了便于后續(xù)的網(wǎng)絡(luò)訓(xùn)練,本文利用softmax來激活zi,將其歸一化到[0,1]區(qū)間:

oi=softmax(zi)

(6)

其中,oi?3表示zi經(jīng)過激活后的結(jié)果.在3個輸出節(jié)點中,產(chǎn)生最大輸出值的節(jié)點將被選為動作節(jié)點,其輸出值yac為:

yac=max(oi)

(7)

然后,RBFGN根據(jù)選擇的動作節(jié)點來更新cn:

(8)

其中,Δ代表加速系數(shù)cn的變化.公式(8)中的3種情況分別對應(yīng)3種候選動作,即增加、減少cn或保持cn不變.隨后給出粒子的全局加速系數(shù):

cg=c-cn

(9)

其中c=4.0為常數(shù),這是由于大量的實驗已證明將加速系數(shù)之和設(shè)置為4.0有利于粒子群優(yōu)化算法找到最優(yōu)解[14,15].同時,cn和cg的初始值均設(shè)置為2.0,以在算法初始階段平衡局部與全局搜索.根據(jù)公式(8)和公式(9)獲得的cn和cg,進一步給出當(dāng)前輸入粒子xi(t)的速度和位置更新公式:

vi(t+1)=w×vi+cg×rg×(gbest-xi(t))
+cn×rn×(μnr-xi(t))

(10)

xi(t+1)=xi(t)+vi(t+1)

(11)

其中,t與t+1是連續(xù)的兩個時刻,w代表慣性權(quán)重,μnr表示離xi(t)最近的子群中心,gbest為全局最優(yōu)位置,rg和rn是兩個[0,1]范圍內(nèi)均勻分布的隨機數(shù).本文利用RBFGN來定位每個輸入粒子的學(xué)習(xí)目標(biāo),并調(diào)整其局部加速系數(shù).進一步地,利用公式(10)和公式(11)實現(xiàn)粒子位置的更新,并評價其在新位置的適應(yīng)值.從而構(gòu)造出RBFNN-PSO.圖1給出了的RBFNN-PSO的結(jié)構(gòu)圖.

圖1 RBFNN-PSO結(jié)構(gòu)圖Fig.1 Structure of RBFNN-PSO

3.2 子群候選中心的重要性

RBFGN通過調(diào)整代表子群的隱藏層節(jié)點,實現(xiàn)種群的劃分,以生成多個子群.RBFGN隱藏層節(jié)點包括中心μ與寬度σ對應(yīng)相應(yīng)子群的子群中心與子群寬度.之后,SBDNN為每個輸入粒子選擇離其最近的子群中心作為學(xué)習(xí)目標(biāo).為保持種群的多樣性,首先需要選出能反映子群搜索特性的候選中心,子群的搜索特性通過候選中心對由其確定的子群中所有粒子的重要性進行體現(xiàn).具體地,候選中心的重要性定義為其所屬隱藏層節(jié)點在網(wǎng)絡(luò)輸出上做出的平均貢獻,該貢獻利用移除其所屬隱藏層節(jié)點后對網(wǎng)絡(luò)輸出造成的誤差來計算.例如,對于輸入粒子xi,若候選中心屬于第j個隱藏層節(jié)點,則當(dāng)?shù)趈個隱藏層節(jié)點被移除時剩余m-1個隱藏層節(jié)點的網(wǎng)絡(luò)輸出為:

(12)

根據(jù)公式(5)和公式(12),移除第j個隱藏層節(jié)點對網(wǎng)絡(luò)輸出造成的誤差為:

(13)

因此,候選中心中重要性sj由移除其所屬的第j個隱藏層節(jié)點后,對網(wǎng)絡(luò)輸出造成的平均誤差來計算:

(14)

其中,p為候選中心所屬的第j個隱藏層節(jié)點對應(yīng)子群中粒子的個數(shù).通過計算候選中心所屬隱藏層節(jié)點的貢獻,從而獲得候選中心的重要性.

3.3 增加子群(隱藏層節(jié)點)

隨著種群中粒子的順序輸入,如果某個輸入粒子的重要性足夠高,那么它便能反映由其確定子群的搜索特性,并將作為其確定子群的候選中心.為保持種群多樣性,還需考慮該候選中心是否和已有的其他中心相近.因此,根據(jù)候選中心的重要性,以及該中心與已有的最近子群中心的距離,設(shè)計增加子群的條件:

(15)

其中,xi代表當(dāng)前輸入網(wǎng)絡(luò)的粒子,xj代表將被劃分到以xi為中心的新子群中的粒子,p代表將要被劃分到新子群中粒子的個數(shù).μnr代表離xi最近的已有子群中心,ε和σmin分別代表重要性閾值和距離閾值.因此,當(dāng)兩個條件均滿足時,xi將作為其確定子群的中心.由于不同子群的中心相互遠離,且不同子群中的粒子分別向能反映各自子群搜索特性的中心學(xué)習(xí),整個種群將呈現(xiàn)多樣的搜索特性,提升了種群的多樣性.相應(yīng)地,新增加的第m+1個隱藏層節(jié)點的中心位置μK+1,寬度σK+1,以及該節(jié)點與輸出層節(jié)點相連的權(quán)值αK+1被初始化為:

(16)

其中,κ是重疊因子,它決定搜索空間中新子群與其最近子群間的重疊程度,為了實現(xiàn)子群的公平劃分,κ設(shè)置為0.5.ei設(shè)置為di-zi,其中zi和di分別為網(wǎng)絡(luò)在增加隱藏層節(jié)點前對于輸入粒子xi的實際輸出與期望輸出,其目的是使網(wǎng)絡(luò)在增加隱藏層節(jié)點后,針對輸入粒子xi能做出期望的輸出.

3.4 基于強化學(xué)習(xí)的網(wǎng)絡(luò)訓(xùn)練

本文引入強化學(xué)習(xí)來訓(xùn)練RBFGN.具體地,通過對網(wǎng)絡(luò)決策出的動作進行獎勵或懲罰,并根據(jù)產(chǎn)生的反饋來訓(xùn)練網(wǎng)絡(luò)參數(shù).期望利用反饋,獲得最大的累積收益,實現(xiàn)對隱藏層節(jié)點(代表子群中粒子的學(xué)習(xí)目標(biāo)),以及其與動作節(jié)點相連權(quán)值(控制粒子的加速系數(shù))的有效調(diào)整.對于輸入的粒子,在經(jīng)過網(wǎng)絡(luò)決策出的動作指導(dǎo)其學(xué)習(xí)之后,若其適應(yīng)值變好,則動作節(jié)點將收到正反饋,即獎勵;反之,它將收到負反饋,即懲罰.

對于輸入到RBFGN的粒子xi,根據(jù)公式(15)若增加子群的條件均滿足時,xi將作為新的隱藏層節(jié)點中心,亦被看作是新的子群中心.相應(yīng)地,新的隱藏層節(jié)點中心、寬度,以及該節(jié)點與輸出層節(jié)點相連的權(quán)值將按照公式(16)進行設(shè)置.否則,若公式(15)的任一條件不滿足,xi將被考慮用于更新RBFGN.在此情況下,針對RBFGN隱藏層節(jié)點和權(quán)值的更新,只需考慮更新距xi最近的子群中心、該中心所在隱藏層節(jié)點的寬度,以及該中心所在隱藏層節(jié)點與動作節(jié)點相連的一個權(quán)值.這是因為:1)本文利用梯度下降法來更新網(wǎng)絡(luò)參數(shù),由公式(4)可知,當(dāng)隱藏層節(jié)點的中心離xi較遠時,該節(jié)點將產(chǎn)生較小的響應(yīng),而且相比于產(chǎn)生的響應(yīng),該節(jié)點響應(yīng)的一階導(dǎo)數(shù)會更快地趨近于0.因此在網(wǎng)絡(luò)隱藏層節(jié)點更新方面,只需更新距xi最近的子群中心,以及該中心所在隱藏層節(jié)點的寬度;2)在輸出層中,利用強化學(xué)習(xí)只獎勵或懲罰擁有最大輸出的動作節(jié)點.因此在網(wǎng)絡(luò)權(quán)值更新方面,只需更新距xi最近子群中心所在隱藏層節(jié)點與動作節(jié)點相連的一個權(quán)值.

具體地,對于輸入的粒子,在經(jīng)過網(wǎng)絡(luò)決策出的動作指導(dǎo)其學(xué)習(xí)之后,若其適應(yīng)值變好,此時將對動作節(jié)點進行獎勵,使其輸出趨近于1.反之,若其適應(yīng)值變差,則需對動作節(jié)進行懲罰,使其輸出趨近于0.基于梯度下降法,給出RBFGN權(quán)值的更新:

Δαac=ηzac(dac-yac)yac(1-yac)

(17)

αac=αac+Δαac

(18)

其中αac代表距xi最近子群中心所在隱藏層節(jié)點與動作節(jié)點相連的權(quán)值,Δαac代表權(quán)值的更新梯度,η代表學(xué)習(xí)率.zac代表動作節(jié)點在softmax操作之前的實際輸出,yac代表動作節(jié)點在softmax之后的實際輸出.dac是動作節(jié)點在softmax之后的期望輸出,即當(dāng)動作節(jié)點受到獎勵時dac為1,否則dac為0.

在更新權(quán)值之后,繼續(xù)更新距xi最近的子群中心μnr,以及該中心所在隱藏層節(jié)點的寬度σnr.在公式(17)中已得到(dac-yi)yi(1-yi)的結(jié)果,故不需再重復(fù)計算,設(shè)qac=(dac-yi)yi(1-yi),則μnr和σnr的更新如下:

(19)

μnr=μnr+Δμnr

(20)

(21)

σnr=σnr+Δσnr

(22)

其中,Δμnr和Δσnr分別代表μnr和σnr的更新梯度.

3.5 刪除子群(隱藏層節(jié)點)

隨著種群的進化與網(wǎng)絡(luò)的更新,粒子的位置不斷發(fā)生改變,而且包含子群中心的隱藏層節(jié)點也會被更新,針對輸入到RBFGN的粒子xi,若離其最近的子群中心k無法反映所屬子群的搜索特性,或者該子群中心與其他子群中心距離較近,則需考慮刪除該子群,故刪除子群的條件為:

(23)

其中,xj代表由第k個子群中心所確定子群中的粒子,p是該子群中粒子的總數(shù),μk和μnr分別代表第k個子群中心的位置和距該中心最近的另一子群中心的位置.ε和σmin分別代表重要性閾值和距離閾值,這兩個閾值被同樣地用于公式(15).基于公式(16)中的重疊因子k=0.5,公式(15)和公式(23)中σmin設(shè)置為當(dāng)前隱藏層所包含的最小子群寬度的兩倍,以確保每個隱藏層節(jié)點的子群寬度至少為當(dāng)前最小的子群寬度.若公式(23)的任一條件被滿足,將刪除離xi最近的子群中心k所在的子群(隱藏層節(jié)點).

3.6 算法流程

RBFNN-PSO的流程圖如圖2所示,RBFNN-PSO的算法步驟見算法1.

圖2 RBFNN-PSO流程圖Fig.2 Flowchart of RBFNN-PSO

算法1.

輸入：MaxFEs:適應(yīng)值函數(shù)最大的評估次數(shù),N:種群規(guī)模,k:初始種群個數(shù).

輸出：gbest:最后一代中最優(yōu)粒子的適應(yīng)值.

步驟1.初始化種群;

步驟2.利用層次的k-means聚類方法初始化子群,作為RBFGN的初始隱藏層節(jié)點;

步驟3.隨機初始化RBFGN的權(quán)值;

步驟4.輸入粒子的位置到RBFGN;

步驟5.RBFGN決策出輸入粒子的搜索動作;

步驟6.根據(jù)搜索動作更新輸入粒子的位置與適應(yīng)值;

步驟7.根據(jù)適應(yīng)值變化獲取反饋;

第三，農(nóng)村區(qū)域出現(xiàn)不平衡的矛盾?，F(xiàn)行“新農(nóng)?！倍嗬U多得的方式在市場經(jīng)濟中本無可厚非，但個人賬戶積累制易于出現(xiàn)“保富不保貧”以及擴大覆蓋面難的問題。[7]同時，國家補貼具有不公平性，經(jīng)濟發(fā)達地區(qū)普遍好于欠發(fā)達地區(qū)，例如北京的養(yǎng)老金每人每月最高可達280元，而最低的地方每月基礎(chǔ)養(yǎng)老金是55元。另外，在現(xiàn)有的財政體系下，經(jīng)濟欠發(fā)達地區(qū)資金普遍存在緊缺狀況。因此，國家向農(nóng)村提供的養(yǎng)老資源應(yīng)充分考慮區(qū)域不平衡問題，做到養(yǎng)老資源供給的實質(zhì)公平。

步驟8.根據(jù)公式(15)判斷是否滿足增加子群的條件,若滿足,跳轉(zhuǎn)至步驟9;否則,轉(zhuǎn)至步驟10;

步驟9.設(shè)置新的隱藏層節(jié)點,包括節(jié)點中心、寬度及其與輸出層相連的權(quán)值,并跳轉(zhuǎn)至步驟13;

步驟10.更新權(quán)值和隱藏層節(jié)點;

步驟11.根據(jù)公式(23)判斷是否滿足刪除子群的條件,若滿足,跳轉(zhuǎn)至步驟12;否則,轉(zhuǎn)至步驟13;

步驟12.刪除隱藏層節(jié)點;

步驟13.FEs=FEs+1;

步驟14.判斷算法是否滿足FEs

3.7 算法時間復(fù)雜度分析

由圖2可以看出,RBFNN-PSO的時間復(fù)雜度主要源于初始化種群和RBFGN,通過網(wǎng)絡(luò)前饋計算為輸入粒子決策出相應(yīng)的搜索動作,增加或刪除RBFGN隱藏層節(jié)點(子群),以及更新RBFGN權(quán)值與隱藏層節(jié)點.對于D維搜索空間中的多峰優(yōu)化問題,初始化規(guī)模為N的種群需要的時間復(fù)雜度為O(ND).基于初始的種群,本文利用層次的k-means聚類方法生成k個類簇中心,作為RBFGN的初始隱藏層節(jié)點(子群)中心,并初始化網(wǎng)絡(luò)權(quán)值,其總的時間復(fù)雜度為O(kND)(k

假設(shè)當(dāng)前隱藏層包括m個節(jié)點,在RBFGN的前饋計算過程中,實現(xiàn)對輸入粒子兩個搜索動作的決策.作為搜索動作之一,定位輸入粒子的學(xué)習(xí)目標(biāo)需要計算該粒子與m個子群中心的距離,以找出距其最近的子群中心,時間復(fù)雜度為O(mD+m)=O(mD).由于RBFGN前兩層之間的連接只起到將輸入粒子傳遞到隱藏層的作用(前兩層間的權(quán)值均設(shè)置為1),在實際計算過程中,根據(jù)公式(4)輸入的粒子直接參與每個隱藏層節(jié)點的響應(yīng)值計算.根據(jù)響應(yīng)的定義,需要計算輸入粒子到每個隱藏層節(jié)點中心(共m個)的距離,而該距離在之前定位學(xué)習(xí)目標(biāo)的過程中已獲取,因此計算輸入粒子在m個隱藏層節(jié)點上響應(yīng)值的時間復(fù)雜度為O(m).作為RBFGN產(chǎn)生的另一搜索動作,調(diào)整輸入粒子的加速系數(shù)其時間耗費主要發(fā)生在網(wǎng)絡(luò)后兩層間的前饋計算,以及輸出層的動作選擇(輸出層共有3個節(jié)點,對應(yīng)增加、減少加速系數(shù),以及保持加速系數(shù)不變),決策出該動作所需的時間復(fù)雜度為O(m+3m+3)=O(m).因此,對于輸入粒子,RBFGN決策出兩個搜索動作的時間復(fù)雜度為O(mD+m)=O(mD).

利用RBFGN決策出的兩個動作更新輸入粒子的位置和適應(yīng)值之后,基于公式(15)若增加子群的兩個條件均滿足,將選擇當(dāng)前的輸入粒子作為新的隱藏層節(jié)點(子群)中心.在公式(15)中的條件中,為了判斷種群中哪些粒子被分配到候選新子群,需要考慮種群中每個粒子(共N個)到m+1個隱藏層節(jié)點中心(包括候選新子群中心)的距離,而直接計算這些距離會造成昂貴的計算耗費.實際上只需計算每個粒子(共N個)到候選新子群中心的距離,其時間復(fù)雜度為O(ND).這是因為在完成初始子群劃分之后,可利用一個N維的數(shù)組來保存每個粒子到其最近子群中心的距離(該距離首先由層次的k-means聚類方法得到,且該聚類方法只會執(zhí)行一次).相應(yīng)地,在后面每次更新各粒子到其最近子群中心的距離時,只需比較當(dāng)前保存的距離和粒子到候選新子群中心間的距離,故計算公式(15)中條件的時間復(fù)雜度為O(ND).接著,利用公式(16)設(shè)置新子群中心的各項參數(shù).對于輸入的粒子,由于在之前的前饋計算過程中已經(jīng)獲得了計算該公式所需的μnr和ei,因此不會增加額外的時間復(fù)雜度.基于公式(15),若增加子群的任一條件不滿足,則需更新RBFGN的隱藏層節(jié)點和權(quán)值.由3.4節(jié)的分析可知,對于輸入的粒子,只需更新一個隱藏層節(jié)點,以及該節(jié)點與動作節(jié)點相連的一個權(quán)值.在更新過程中,公式(17)～公式(22)中的參數(shù)zac,yac和μnr已在之前的搜索動作決策過程中獲得,也不會增加額外的時間復(fù)雜度.在更新過程之后,若公式(23)的任一條件滿足,則會刪除更新后不適合的隱藏層節(jié)點(子群).由于公式(23)與公式(15)中的條件均相反,類似地計算公式(23)所需的時間復(fù)雜度也為O(ND).值得注意的是,在每次迭代過程中增加隱藏層節(jié)點和刪除隱藏層節(jié)點這兩者最多只會執(zhí)行其一,因此逐個輸入種群中的粒子,算法總的時間復(fù)雜度為O(N2D).

4 仿真實驗及結(jié)果分析

4.1 測試函數(shù)

本文選取CEC2013測試集[16]的15個多峰函數(shù)來反映RBFNN-PSO的表現(xiàn).15個多峰函數(shù)如表 1所示.

4.2 參數(shù)設(shè)置

15個多峰函數(shù)在每個維度上的搜索范圍均設(shè)置為[-100,100].根據(jù)CEC2013的統(tǒng)一要求,MaxFEs設(shè)置為10000×D,其中D=30為搜索空間的維度.RBFNN-PSO的種群規(guī)模設(shè)置為50.為了公平比較,在15個測試函數(shù)上每種算法均獨立運行30次,并計算其平均求解結(jié)果.

為了設(shè)置公式(15)和公式(23)中的,選擇取值不同的在CEC2013測試集15個多峰函數(shù)上進行實驗,其中的取值為0.001,0.01,0.1和1.表2給出不同取值下RBFNN-PSO在15個多峰函數(shù)上的平均適應(yīng)值(Mean)及其標(biāo)準(zhǔn)差(Std.).每個函數(shù)上最好的平均適應(yīng)值用黑體下劃線標(biāo)記,并在下方給出了Mean的平均排名,以展示不同取值下算法的綜合表現(xiàn).

表1 CEC2013多峰函數(shù)Table 1 Multimodal functions in CEC2013

由表2可以看出,當(dāng)ε取值為0.01時RBFNN-PSO在除了f19之外的14個多峰函數(shù)上均取得了最好的平均適應(yīng)值,并以1.07的平均排名在15個多峰函數(shù)上獲得最好的綜合表現(xiàn).這是因為當(dāng)ε=0.001時,重要性閾值過小,輸入的粒子容易被初始化為新的子群中心,使得子群過多.由于種群規(guī)模有限(固定為50),過多的子群將造成有些子群中粒子個數(shù)較少,不利于子群的搜索.而當(dāng)ε=0.1或ε=1時,重要性閾值過大,將造成子群數(shù)量不足,不利于保持種群多樣性.因此在后續(xù)實驗中我們將ε設(shè)置為0.01.

4.3 實驗結(jié)果與分析

4.3.1 RBFNN-PSO與PSO變體算法比較

本文首先選擇5種PSO變體算法進行比較,對比算法包括融入社會影響力的粒子群優(yōu)化算法(PSO with Social Influence,PSOSI)[17],基于多榜樣和遺忘能力的拓展粒子群優(yōu)算法(An eXpanded Particle Swarm Optimization,XPSO)[18],自調(diào)整的粒子群優(yōu)化算法(Self Regulating Particle Swarm Optimization Algorithm,SRPSO)[19],基于多種群的自適應(yīng)遷移粒子的粒子群優(yōu)化算法(Multi-Population Based Self-Adaptive Migration PSO,MSMPSO)[20],和帶有信息共享機制的競爭和合作粒子群優(yōu)化算法(Competitive and Cooperative Particle Swarm Optimization with Information Sharing Mechanism,CCPSO-ISM)[21].這些算法均采用其原始論文中的參數(shù)設(shè)置.

表3給出了6種算法在15個多峰測試函數(shù)上的平均適應(yīng)值(Mean)及其標(biāo)準(zhǔn)差(Std.).每個函數(shù)上的最好平均適應(yīng)值通過粗體下劃線標(biāo)記.為進一步展示各算法的綜合表現(xiàn),表4給出了6種算法在15個多峰測試函數(shù)上Mean的排名與平均排名.由表3可以看出,RBFNN-PSO在其中7個多峰測試函數(shù)(f6、f8、f10、f11、f14、f16和f17)上獲得了最優(yōu)的平均適應(yīng)值.由表4可以看出,相比于其他5種算法RBFNN-PSO獲得了最佳的綜合表現(xiàn),其平均排名為2.00,比取得次優(yōu)表現(xiàn)的PSOSI,RBFNN-PSO在平均排名上低了0.80,其求解多峰優(yōu)化問題的能力優(yōu)勢明顯.

表3 6種算法在CEC2013測試集15個多峰函數(shù)上的平均求解結(jié)果比較Table 3 Comparisons of the mean resultsfor the 6 algorithms on the 15 multimodal functions of CEC2013 test suite

表4 6種算法在CEC2013測試集15個多峰函數(shù)上的分別排名與平均排名比較Table 4 Comparisons of the ranks and averageranks for the 6 algorithms on the 15 multimodal functions of CEC2013 test suite

為了更直觀地展示算法的求解精度與收斂速度,圖3給出在8個多峰測試函數(shù)(f6、f8、f10、f11、f14、f16、f17、f18)上,6種算法的適應(yīng)值隨迭代次數(shù)變化的曲線.從圖3可以看出,除了f18,RBFNN-PSO在其他7個函數(shù)上均取得最好的求解精度,而且在其中的f11和f17上收斂最快.另外,根據(jù)RBFNN-PSO在f6、f8、f14、f16、f17上的收斂曲線,即使在其前期搜索精度不高的情況下,通過保持種群多樣性與合理指導(dǎo)粒子搜索動作,RBFNN-PSO最終取得比其他5種算法更優(yōu)的求解精度.

圖3 6種算法的收斂曲線比較Fig.3 Comparisons of convergencecurves with respect to 6 algorithms

為了比較各個算法的尋優(yōu)速度,在相同的仿真環(huán)境下,6種算法在CEC2013測試集的15個多峰函數(shù)上分別獨立運行30次,表5記錄了6種算法達到指定精度時的平均運行時間.由表5可以看出,在15個多峰函數(shù)上,RBFNN-PSO到達指定精度的時間消耗與其他5種對比算法大致相同,且相比于其他5種算法,RBFNN-PSO在f7、f11和f17上運行時間最短.基于3.7節(jié)的分析,RBFNN-PSO需要為每個輸入粒子決策出相應(yīng)的搜索動作,增加或刪除RBFGN隱藏層節(jié)點(子群),以及更新權(quán)值與隱藏層節(jié)點,會造成一定的時間耗費,導(dǎo)致其時間復(fù)雜度的增加.但是由于其對搜索動作的出色決策能力,在達到指定精度時,運行的代數(shù)相對較少,從而在運行時間上和其他5種算法大致相同.然而,重要的是在表3和表4中本文提出的RBFNN-PSO在求解精度方面,相對于其他5種算法優(yōu)勢明顯.

表5 6種算法在CEC2013測試集15個多峰函數(shù)上達到指定求解精度的運行時間比較(秒)Table 5 Comparisons of time for the 6 algorithms on the 15 multimodal functions of CEC2013 to achieve specified accuracy(s)

4.3.2 RBFNN-PSO與其他優(yōu)化算法的比較

為了進一步驗證本文所提出的RBFNN-PSO求解多峰優(yōu)化問題的有效性,還將該算法與3種其他優(yōu)化算法(非基于PSO的優(yōu)化算法)進行比較,這些算法包括:CoDE[22]、PBILc[23]和AABC[24],分別屬于差分進化算法、群體分布估計算法和人工蜂群算法的變體.

表6給出了RBFNN-PSO、CoDE、PBILc、AABC這4種算法在15個多峰測試函數(shù)上的平均適應(yīng)值(Mean)及其標(biāo)準(zhǔn)差(Std.).每個函數(shù)上的最好平均適應(yīng)值通過粗體下劃線標(biāo)記.為了展示各算法的綜合表現(xiàn),在表6的下方給出了其根據(jù)Mean的平均排名.從表6可以看出,相比于其他3種算法,RBFNN-PSO在7個函數(shù)(f6、f8、f12、f14、f17、f19和f20)上取得最好的平均適應(yīng)值.而且根據(jù)平均排名,RBFNN-PSO獲得最佳的綜合表現(xiàn),其平均排名為1.73.與取得次優(yōu)綜合表現(xiàn)的CoDE相比,RBFNN-PSO在平均排名上低了0.54,進一步驗證了本文所提出的RBFNN-PSO求解多峰優(yōu)化問題的有效性.

表6 4種算法在CEC2013測試集15個多峰函數(shù)上的平均求解結(jié)果比較Table 6 Comparisons of the mean resultsfor the 4 algorithms on the 15 multimodal functions of CEC2013 test suite

5 結(jié) 論

本文提出一種徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)指導(dǎo)的粒子群優(yōu)化算法(RBFNN-PSO).該算法利用設(shè)計的徑向基函數(shù)指導(dǎo)網(wǎng)絡(luò)(RBFGN),在保持種群多樣性的同時,合理定位粒子學(xué)習(xí)目標(biāo),有效調(diào)整粒子加速系數(shù),以最終解決多峰優(yōu)化問題.具體地,RBFGN將整個種群劃分為多個子群,子群中心作為子群粒子的學(xué)習(xí)目標(biāo),指導(dǎo)其搜索.RBFGN充分考慮種群多樣性,選擇能代表子群搜索特性的粒子作為子群中心,并使之遠離已存在的子群中心.因而,通過選擇合適的子群中心,實現(xiàn)子群的劃分.不同子群粒子在各自子群中心指導(dǎo)下搜索,呈現(xiàn)出多樣的搜索特性,提升了種群多樣性.RBFGN的輸出層輸出粒子加速系數(shù)的調(diào)整動作,并根據(jù)隱藏層決策出的學(xué)習(xí)目標(biāo),有效指導(dǎo)粒子的搜索.本文引入強化學(xué)習(xí)來訓(xùn)練網(wǎng)絡(luò),利用產(chǎn)生的反饋,期望獲得最大的累積收益,實現(xiàn)對隱藏層節(jié)點,以及其與動作節(jié)點相連權(quán)值的有效調(diào)整.

為了反映RBFNN-PSO的表現(xiàn),在CEC2013測試集上的15個多峰函數(shù)中開展廣泛實驗,通過與5種主流的PSO變體算法以及3種其他優(yōu)化算法進行比較,其結(jié)果表明本文所提出的RBFNN-PSO求解多峰優(yōu)化問題的能力優(yōu)勢明顯.在下一步工作中,將把RBFNN-PSO應(yīng)用于求解一些實際多峰優(yōu)化問題,并將其拓展到更復(fù)雜的優(yōu)化領(lǐng)域,例如動態(tài)優(yōu)化領(lǐng)域和大規(guī)模優(yōu)化領(lǐng)域等.