張 瀟,宋 威,2
1(江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院,江蘇 無錫 214122)
2(江南大學(xué) 江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室,江蘇 無錫 214122)
粒子群優(yōu)化(Particle Swarm Optimization,PSO)[1]算法一種典型的群體智能(Swarm Intelligence,SI)[2]算法,它模擬了自然界中生物種群的自組織交互行為,具有對(duì)問題解析性質(zhì)要求低,實(shí)現(xiàn)簡(jiǎn)單且收斂速度快等優(yōu)點(diǎn).在過去20年間PSO受到學(xué)術(shù)界的廣泛關(guān)注,并被應(yīng)用于特征選擇[3]、人群分類[4]、車間調(diào)度[5]和疫情傳播預(yù)測(cè)[6]等多種領(lǐng)域.然而,在現(xiàn)實(shí)世界中存在著大量多峰優(yōu)化問題.該類問題的特點(diǎn)是,在解空間中同時(shí)存在著多個(gè)局部最優(yōu)解與一個(gè)全局最優(yōu)解.利用傳統(tǒng)PSO算法求解多峰優(yōu)化問題時(shí),由于缺乏多樣性且搜索動(dòng)作選取不合理,導(dǎo)致其難以找到問題的全局最優(yōu)解.
目前,一些PSO的改進(jìn)方法將種群劃分成多個(gè)子群,其目的是保持種群多樣性[7,8].然而這些方法大多依賴于人為經(jīng)驗(yàn)或是預(yù)設(shè)的規(guī)則,根據(jù)各粒子在解空間中的位置,利用聚類或小生境的思想將整個(gè)種群劃分為多個(gè)子群,使各子群分布在解空間中的不同區(qū)域來進(jìn)行搜索.Kennedy最早提出利用PSO算法來求解多峰優(yōu)化問題[9],其思路是利用k-means算法將種群聚成多個(gè)類簇,然后用類簇的中心作為該鄰域的最優(yōu)解,指導(dǎo)對(duì)應(yīng)類簇中粒子的學(xué)習(xí).Brits等人提出了一種基于小生境技術(shù)的PSO算法[10],具體內(nèi)容包括:如果主種群中某個(gè)粒子的適應(yīng)值在一定的迭代次數(shù)中變化較小,該粒子將和當(dāng)前主種群中距其最近的另一個(gè)粒子構(gòu)成一個(gè)小生境.此過程不斷循環(huán),最終實(shí)現(xiàn)子群的劃分.Parrott等人提出了一種基于種群生成的PSO算法[11],在運(yùn)行的每一代,首先將當(dāng)前種群中適應(yīng)值最優(yōu)的粒子確定為一個(gè)種子,并利用該種子和空間中所有與它距離小于一定半徑的粒子來構(gòu)造一個(gè)種群.剩余的粒子會(huì)重復(fù)上述構(gòu)造過程,直到全部粒子均被劃分至不同的種群,因而使得不同種群將在不同的區(qū)域進(jìn)行搜索.然而,上述的多子群方法需要與問題相關(guān)的先驗(yàn)知識(shí),如預(yù)先設(shè)置聚類簇的個(gè)數(shù)或種群半徑等,導(dǎo)致這些方法無法根據(jù)不同的優(yōu)化問題合理地劃分子群.而且這些方法也沒有對(duì)粒子的搜索動(dòng)作進(jìn)行精心地設(shè)計(jì),影響了搜索的性能.針對(duì)上述問題,本文將徑向基函數(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),在保持種群多樣性的前提下,對(duì)包括定位學(xué)習(xí)目標(biāo)和調(diào)整加速系數(shù)在內(nèi)的搜索動(dòng)作進(jìn)行合理的指導(dǎo).
為了在搜索過程中保持種群多樣性,首先設(shè)計(jì)子群劃分方法,選擇能代表子群的搜索特性且與現(xiàn)有子群中心遠(yuǎn)離的粒子作為子群中心.子群的搜索特性通過候選子群中心對(duì)由其確定的子群中所有粒子的重要性進(jìn)行體現(xiàn).所設(shè)計(jì)的子群劃分方法通過選擇合適的子群中心,實(shí)現(xiàn)子群的劃分.因此,不同子群中的粒子在各自子群中心指導(dǎo)下搜索,呈現(xiàn)出多樣的搜索特性,提升了種群多樣性.其次,在考慮多樣性的同時(shí),選擇各子群中心作為相應(yīng)子群中粒子的學(xué)習(xí)目標(biāo),實(shí)現(xiàn)了粒子學(xué)習(xí)目標(biāo)的定位.由于將粒子當(dāng)前位置映射為搜索動(dòng)作屬于非線性映射,作為典型的非線性映射模型,本文利用徑向基函數(shù)神經(jīng)網(wǎng)絡(luò),實(shí)現(xiàn)從粒子位置到搜索動(dòng)作的映射.同時(shí),徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)屬于增量模型,能利用輸入的每個(gè)位置來更新網(wǎng)絡(luò).本文設(shè)計(jì)RBFGN的輸入為種群中每個(gè)粒子的當(dāng)前位置,之后利用獲取的子群中心設(shè)置其隱藏層節(jié)點(diǎn).為了調(diào)整粒子的加速系數(shù),在RBFGN輸出層輸出當(dāng)前輸入粒子的加速系數(shù)調(diào)整動(dòng)作,包括增加、減少加速系數(shù)或保持加速系數(shù)不變3個(gè)動(dòng)作.最后,為了訓(xùn)練RBFGN,本文引入強(qiáng)化學(xué)習(xí)對(duì)網(wǎng)絡(luò)決策出的動(dòng)作(包括定位學(xué)習(xí)目標(biāo)和調(diào)整加速系數(shù))進(jìn)行獎(jiǎng)勵(lì)或懲罰,其目的是根據(jù)反饋,獲得最大的累積收益,實(shí)現(xiàn)對(duì)隱藏層節(jié)點(diǎn)(代表子群中粒子的學(xué)習(xí)目標(biāo))和輸出動(dòng)作相連權(quán)值(控制粒子的加速系數(shù))的有效調(diào)整,從而使RBFNN-PSO能合理指導(dǎo)粒子的搜索動(dòng)作,以解決多峰優(yōu)化問題.
PSO由Kennedy和Eberhart于1995年提出,它通過模擬鳥群覓食行為來尋找問題的最優(yōu)解.具體而言,PSO中每個(gè)粒子具有速度和位置兩種屬性,根據(jù)自身和種群的歷史最優(yōu)位置來確定下一步搜索動(dòng)作.帶有慣性權(quán)重的標(biāo)準(zhǔn)PSO由Shi和Eberhart在1998年提出.每次迭代中,第i個(gè)粒子的速度和位置更新公式如下:
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個(gè)粒子在第t次迭代的位置,vi(t)表示第i個(gè)粒子在第t次迭代的速度,pbesti表示第i個(gè)粒子歷史最優(yōu)位置,gbest表示種群的歷史最優(yōu)位置.c1和c2代表兩個(gè)加速系數(shù),r1和r2是[0,1]范圍內(nèi)均勻分布的兩個(gè)隨機(jī)數(shù).w是慣性權(quán)重,用于控制各粒子上一代速度對(duì)當(dāng)前速度的影響.目前通用的慣性權(quán)重控制方法是使其隨著迭代次數(shù)的增加而線性減小[12]:
(3)
其中,wmax為迭代開始時(shí)最大的慣性權(quán)重值,wmin為迭代結(jié)束時(shí)最小的慣性權(quán)重值,Tmax表示最大迭代次數(shù).
徑向基函數(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ù)包含中心μ與寬度σ兩個(gè)屬性,第k個(gè)隱藏層節(jié)點(diǎn)對(duì)于第i個(gè)輸入xi的激活結(jié)果為:
(4)
(5)
其中,αk是第k個(gè)隱藏層節(jié)點(diǎn)與輸出層相連的權(quán)值向量.
本文設(shè)計(jì)RBFGN,其目的是獲取一種不依賴于先驗(yàn)知識(shí)便可解決多峰優(yōu)化問題的方法,RBFGN通過提升種群多樣性并合理指導(dǎo)粒子的搜索動(dòng)作來有效求解多峰優(yōu)化問題.由于需要將輸入的粒子位置映射為其對(duì)應(yīng)的搜索動(dòng)作,此過程屬于非線性映射.作為典型的非線性映射模型,本文基于徑向基函數(shù)神經(jīng)網(wǎng)絡(luò),進(jìn)一步設(shè)計(jì)RBFGN,實(shí)現(xiàn)從粒子位置到其搜索動(dòng)作的映射,以更好解決多峰優(yōu)化問題.
本文構(gòu)造的RBFGN包含輸入層、隱藏層和輸出層,是一個(gè)緊湊的3層徑向基函數(shù)神經(jīng)網(wǎng)絡(luò).RBFGN的輸入為種群中每個(gè)粒子的當(dāng)前位置,因此,RBFGN的輸入層包含D個(gè)節(jié)點(diǎn),對(duì)應(yīng)粒子位置在空間中的D個(gè)維度.輸入層與隱藏層之間的連接僅起到傳輸數(shù)據(jù)的功能,因此前兩層間的權(quán)值均為1.RBFGN的隱藏層包含若干個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)代表一個(gè)子群,RBFGN通過調(diào)整隱藏層節(jié)點(diǎn),實(shí)現(xiàn)對(duì)種群的劃分.隱藏層節(jié)點(diǎn)的中心μ與寬度σ對(duì)應(yīng)相應(yīng)子群的子群中心與子群寬度.為了使初始子群分布在解空間中的不同區(qū)域,本文利用層次的k-means聚類方法來初始化子群.首先將種群中的粒子劃分為l×k個(gè)類簇,由于種群規(guī)模(N=50)的限制,取l為2.隨后每?jī)蓚€(gè)最相近的類簇將會(huì)融合,直到最后只剩下k個(gè)類簇,將k個(gè)類簇的中心作為初始的子群中心,每個(gè)類簇中所有粒子到中心的平均距離作為初始的子群寬度.受限于種群規(guī)模(N=50),初始的子群個(gè)數(shù)k設(shè)置為10,對(duì)應(yīng)初始的10個(gè)隱藏層節(jié)點(diǎn).
在初始化RBFGN隱藏層節(jié)點(diǎn)之后,第i個(gè)輸入粒子xi經(jīng)過第k個(gè)隱藏層節(jié)點(diǎn)利用公式(4)進(jìn)行激活,輸出的響應(yīng)為φk(xi).同時(shí),由公式(4)可以看出,若xi離某個(gè)子群中心μk的距離大于子群半徑σk,它將會(huì)得到較小的響應(yīng).因此,xi受其最近子群中心的影響最大,該粒子將被分配到其最近子群中心所確定的子群中,并向該中心學(xué)習(xí).RBFGN輸出層包含3個(gè)節(jié)點(diǎn),分別代表3個(gè)候選動(dòng)作,即增加、減少局部加速系數(shù)cn或保持cn不變,其中cn控制著xi向其子群中心學(xué)習(xí)的力度.根據(jù)公式(5),擁有m個(gè)隱藏層節(jié)點(diǎn)的RBFGN輸出為zi.為了便于后續(xù)的網(wǎng)絡(luò)訓(xùn)練,本文利用softmax來激活zi,將其歸一化到[0,1]區(qū)間:
oi=softmax(zi)
(6)
其中,oi?3表示zi經(jīng)過激活后的結(jié)果.在3個(gè)輸出節(jié)點(diǎn)中,產(chǎn)生最大輸出值的節(jié)點(diǎn)將被選為動(dòng)作節(jié)點(diǎn),其輸出值yac為:
yac=max(oi)
(7)
然后,RBFGN根據(jù)選擇的動(dòng)作節(jié)點(diǎn)來更新cn:
(8)
其中,Δ代表加速系數(shù)cn的變化.公式(8)中的3種情況分別對(duì)應(yīng)3種候選動(dòng)作,即增加、減少cn或保持cn不變.隨后給出粒子的全局加速系數(shù):
cg=c-cn
(9)
其中c=4.0為常數(shù),這是由于大量的實(shí)驗(yàn)已證明將加速系數(shù)之和設(shè)置為4.0有利于粒子群優(yōu)化算法找到最優(yōu)解[14,15].同時(shí),cn和cg的初始值均設(shè)置為2.0,以在算法初始階段平衡局部與全局搜索.根據(jù)公式(8)和公式(9)獲得的cn和cg,進(jìn)一步給出當(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ù)的兩個(gè)時(shí)刻,w代表慣性權(quán)重,μnr表示離xi(t)最近的子群中心,gbest為全局最優(yōu)位置,rg和rn是兩個(gè)[0,1]范圍內(nèi)均勻分布的隨機(jī)數(shù).本文利用RBFGN來定位每個(gè)輸入粒子的學(xué)習(xí)目標(biāo),并調(diào)整其局部加速系數(shù).進(jìn)一步地,利用公式(10)和公式(11)實(shí)現(xiàn)粒子位置的更新,并評(píng)價(jià)其在新位置的適應(yīng)值.從而構(gòu)造出RBFNN-PSO.圖1給出了的RBFNN-PSO的結(jié)構(gòu)圖.
圖1 RBFNN-PSO結(jié)構(gòu)圖Fig.1 Structure of RBFNN-PSO
RBFGN通過調(diào)整代表子群的隱藏層節(jié)點(diǎn),實(shí)現(xiàn)種群的劃分,以生成多個(gè)子群.RBFGN隱藏層節(jié)點(diǎn)包括中心μ與寬度σ對(duì)應(yīng)相應(yīng)子群的子群中心與子群寬度.之后,SBDNN為每個(gè)輸入粒子選擇離其最近的子群中心作為學(xué)習(xí)目標(biāo).為保持種群的多樣性,首先需要選出能反映子群搜索特性的候選中心,子群的搜索特性通過候選中心對(duì)由其確定的子群中所有粒子的重要性進(jìn)行體現(xiàn).具體地,候選中心的重要性定義為其所屬隱藏層節(jié)點(diǎn)在網(wǎng)絡(luò)輸出上做出的平均貢獻(xiàn),該貢獻(xiàn)利用移除其所屬隱藏層節(jié)點(diǎn)后對(duì)網(wǎng)絡(luò)輸出造成的誤差來計(jì)算.例如,對(duì)于輸入粒子xi,若候選中心屬于第j個(gè)隱藏層節(jié)點(diǎn),則當(dāng)?shù)趈個(gè)隱藏層節(jié)點(diǎn)被移除時(shí)剩余m-1個(gè)隱藏層節(jié)點(diǎn)的網(wǎng)絡(luò)輸出為:
(12)
根據(jù)公式(5)和公式(12),移除第j個(gè)隱藏層節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)輸出造成的誤差為:
(13)
因此,候選中心中重要性sj由移除其所屬的第j個(gè)隱藏層節(jié)點(diǎn)后,對(duì)網(wǎng)絡(luò)輸出造成的平均誤差來計(jì)算:
(14)
其中,p為候選中心所屬的第j個(gè)隱藏層節(jié)點(diǎn)對(duì)應(yīng)子群中粒子的個(gè)數(shù).通過計(jì)算候選中心所屬隱藏層節(jié)點(diǎn)的貢獻(xiàn),從而獲得候選中心的重要性.
隨著種群中粒子的順序輸入,如果某個(gè)輸入粒子的重要性足夠高,那么它便能反映由其確定子群的搜索特性,并將作為其確定子群的候選中心.為保持種群多樣性,還需考慮該候選中心是否和已有的其他中心相近.因此,根據(jù)候選中心的重要性,以及該中心與已有的最近子群中心的距離,設(shè)計(jì)增加子群的條件:
(15)
其中,xi代表當(dāng)前輸入網(wǎng)絡(luò)的粒子,xj代表將被劃分到以xi為中心的新子群中的粒子,p代表將要被劃分到新子群中粒子的個(gè)數(shù).μnr代表離xi最近的已有子群中心,ε和σmin分別代表重要性閾值和距離閾值.因此,當(dāng)兩個(gè)條件均滿足時(shí),xi將作為其確定子群的中心.由于不同子群的中心相互遠(yuǎn)離,且不同子群中的粒子分別向能反映各自子群搜索特性的中心學(xué)習(xí),整個(gè)種群將呈現(xiàn)多樣的搜索特性,提升了種群的多樣性.相應(yīng)地,新增加的第m+1個(gè)隱藏層節(jié)點(diǎn)的中心位置μK+1,寬度σK+1,以及該節(jié)點(diǎn)與輸出層節(jié)點(diǎn)相連的權(quán)值αK+1被初始化為:
(16)
其中,κ是重疊因子,它決定搜索空間中新子群與其最近子群間的重疊程度,為了實(shí)現(xiàn)子群的公平劃分,κ設(shè)置為0.5.ei設(shè)置為di-zi,其中zi和di分別為網(wǎng)絡(luò)在增加隱藏層節(jié)點(diǎn)前對(duì)于輸入粒子xi的實(shí)際輸出與期望輸出,其目的是使網(wǎng)絡(luò)在增加隱藏層節(jié)點(diǎn)后,針對(duì)輸入粒子xi能做出期望的輸出.
本文引入強(qiáng)化學(xué)習(xí)來訓(xùn)練RBFGN.具體地,通過對(duì)網(wǎng)絡(luò)決策出的動(dòng)作進(jìn)行獎(jiǎng)勵(lì)或懲罰,并根據(jù)產(chǎn)生的反饋來訓(xùn)練網(wǎng)絡(luò)參數(shù).期望利用反饋,獲得最大的累積收益,實(shí)現(xiàn)對(duì)隱藏層節(jié)點(diǎn)(代表子群中粒子的學(xué)習(xí)目標(biāo)),以及其與動(dòng)作節(jié)點(diǎn)相連權(quán)值(控制粒子的加速系數(shù))的有效調(diào)整.對(duì)于輸入的粒子,在經(jīng)過網(wǎng)絡(luò)決策出的動(dòng)作指導(dǎo)其學(xué)習(xí)之后,若其適應(yīng)值變好,則動(dòng)作節(jié)點(diǎn)將收到正反饋,即獎(jiǎng)勵(lì);反之,它將收到負(fù)反饋,即懲罰.
對(duì)于輸入到RBFGN的粒子xi,根據(jù)公式(15)若增加子群的條件均滿足時(shí),xi將作為新的隱藏層節(jié)點(diǎn)中心,亦被看作是新的子群中心.相應(yīng)地,新的隱藏層節(jié)點(diǎn)中心、寬度,以及該節(jié)點(diǎn)與輸出層節(jié)點(diǎn)相連的權(quán)值將按照公式(16)進(jìn)行設(shè)置.否則,若公式(15)的任一條件不滿足,xi將被考慮用于更新RBFGN.在此情況下,針對(duì)RBFGN隱藏層節(jié)點(diǎn)和權(quán)值的更新,只需考慮更新距xi最近的子群中心、該中心所在隱藏層節(jié)點(diǎn)的寬度,以及該中心所在隱藏層節(jié)點(diǎn)與動(dòng)作節(jié)點(diǎn)相連的一個(gè)權(quán)值.這是因?yàn)?1)本文利用梯度下降法來更新網(wǎng)絡(luò)參數(shù),由公式(4)可知,當(dāng)隱藏層節(jié)點(diǎn)的中心離xi較遠(yuǎn)時(shí),該節(jié)點(diǎn)將產(chǎn)生較小的響應(yīng),而且相比于產(chǎn)生的響應(yīng),該節(jié)點(diǎn)響應(yīng)的一階導(dǎo)數(shù)會(huì)更快地趨近于0.因此在網(wǎng)絡(luò)隱藏層節(jié)點(diǎn)更新方面,只需更新距xi最近的子群中心,以及該中心所在隱藏層節(jié)點(diǎn)的寬度;2)在輸出層中,利用強(qiáng)化學(xué)習(xí)只獎(jiǎng)勵(lì)或懲罰擁有最大輸出的動(dòng)作節(jié)點(diǎn).因此在網(wǎng)絡(luò)權(quán)值更新方面,只需更新距xi最近子群中心所在隱藏層節(jié)點(diǎn)與動(dòng)作節(jié)點(diǎn)相連的一個(gè)權(quán)值.
具體地,對(duì)于輸入的粒子,在經(jīng)過網(wǎng)絡(luò)決策出的動(dòng)作指導(dǎo)其學(xué)習(xí)之后,若其適應(yīng)值變好,此時(shí)將對(duì)動(dòng)作節(jié)點(diǎn)進(jìn)行獎(jiǎng)勵(lì),使其輸出趨近于1.反之,若其適應(yīng)值變差,則需對(duì)動(dòng)作節(jié)進(jìn)行懲罰,使其輸出趨近于0.基于梯度下降法,給出RBFGN權(quán)值的更新:
Δαac=ηzac(dac-yac)yac(1-yac)
(17)
αac=αac+Δαac
(18)
其中αac代表距xi最近子群中心所在隱藏層節(jié)點(diǎn)與動(dòng)作節(jié)點(diǎn)相連的權(quán)值,Δαac代表權(quán)值的更新梯度,η代表學(xué)習(xí)率.zac代表動(dòng)作節(jié)點(diǎn)在softmax操作之前的實(shí)際輸出,yac代表動(dòng)作節(jié)點(diǎn)在softmax之后的實(shí)際輸出.dac是動(dòng)作節(jié)點(diǎn)在softmax之后的期望輸出,即當(dāng)動(dòng)作節(jié)點(diǎn)受到獎(jiǎng)勵(lì)時(shí)dac為1,否則dac為0.
在更新權(quán)值之后,繼續(xù)更新距xi最近的子群中心μnr,以及該中心所在隱藏層節(jié)點(diǎn)的寬度σnr.在公式(17)中已得到(dac-yi)yi(1-yi)的結(jié)果,故不需再重復(fù)計(jì)算,設(shè)qac=(dac-yi)yi(1-yi),則μnr和σnr的更新如下:
(19)
μnr=μnr+Δμnr
(20)
(21)
σnr=σnr+Δσnr
(22)
其中,Δμnr和Δσnr分別代表μnr和σnr的更新梯度.
隨著種群的進(jìn)化與網(wǎng)絡(luò)的更新,粒子的位置不斷發(fā)生改變,而且包含子群中心的隱藏層節(jié)點(diǎn)也會(huì)被更新,針對(duì)輸入到RBFGN的粒子xi,若離其最近的子群中心k無法反映所屬子群的搜索特性,或者該子群中心與其他子群中心距離較近,則需考慮刪除該子群,故刪除子群的條件為:
(23)
其中,xj代表由第k個(gè)子群中心所確定子群中的粒子,p是該子群中粒子的總數(shù),μk和μnr分別代表第k個(gè)子群中心的位置和距該中心最近的另一子群中心的位置.ε和σmin分別代表重要性閾值和距離閾值,這兩個(gè)閾值被同樣地用于公式(15).基于公式(16)中的重疊因子k=0.5,公式(15)和公式(23)中σmin設(shè)置為當(dāng)前隱藏層所包含的最小子群寬度的兩倍,以確保每個(gè)隱藏層節(jié)點(diǎn)的子群寬度至少為當(dāng)前最小的子群寬度.若公式(23)的任一條件被滿足,將刪除離xi最近的子群中心k所在的子群(隱藏層節(jié)點(diǎn)).
RBFNN-PSO的流程圖如圖2所示,RBFNN-PSO的算法步驟見算法1.
圖2 RBFNN-PSO流程圖Fig.2 Flowchart of RBFNN-PSO
算法1.
輸入:MaxFEs:適應(yīng)值函數(shù)最大的評(píng)估次數(shù),N:種群規(guī)模,k:初始種群個(gè)數(shù).
輸出:gbest:最后一代中最優(yōu)粒子的適應(yīng)值.
步驟1.初始化種群;
步驟2.利用層次的k-means聚類方法初始化子群,作為RBFGN的初始隱藏層節(jié)點(diǎn);
步驟3.隨機(jī)初始化RBFGN的權(quán)值;
步驟4.輸入粒子的位置到RBFGN;
步驟5.RBFGN決策出輸入粒子的搜索動(dòng)作;
步驟6.根據(jù)搜索動(dòng)作更新輸入粒子的位置與適應(yīng)值;
步驟7.根據(jù)適應(yīng)值變化獲取反饋;
第三,農(nóng)村區(qū)域出現(xiàn)不平衡的矛盾?,F(xiàn)行“新農(nóng)?!倍嗬U多得的方式在市場(chǎng)經(jīng)濟(jì)中本無可厚非,但個(gè)人賬戶積累制易于出現(xiàn)“保富不保貧”以及擴(kuò)大覆蓋面難的問題。[7]同時(shí),國(guó)家補(bǔ)貼具有不公平性,經(jīng)濟(jì)發(fā)達(dá)地區(qū)普遍好于欠發(fā)達(dá)地區(qū),例如北京的養(yǎng)老金每人每月最高可達(dá)280元,而最低的地方每月基礎(chǔ)養(yǎng)老金是55元。另外,在現(xiàn)有的財(cái)政體系下,經(jīng)濟(jì)欠發(fā)達(dá)地區(qū)資金普遍存在緊缺狀況。因此,國(guó)家向農(nóng)村提供的養(yǎng)老資源應(yīng)充分考慮區(qū)域不平衡問題,做到養(yǎng)老資源供給的實(shí)質(zhì)公平。
步驟8.根據(jù)公式(15)判斷是否滿足增加子群的條件,若滿足,跳轉(zhuǎn)至步驟9;否則,轉(zhuǎn)至步驟10;
步驟9.設(shè)置新的隱藏層節(jié)點(diǎn),包括節(jié)點(diǎn)中心、寬度及其與輸出層相連的權(quán)值,并跳轉(zhuǎn)至步驟13;
步驟10.更新權(quán)值和隱藏層節(jié)點(diǎn);
步驟11.根據(jù)公式(23)判斷是否滿足刪除子群的條件,若滿足,跳轉(zhuǎn)至步驟12;否則,轉(zhuǎn)至步驟13;
步驟12.刪除隱藏層節(jié)點(diǎn);
步驟13.FEs=FEs+1;
步驟14.判斷算法是否滿足FEs 由圖2可以看出,RBFNN-PSO的時(shí)間復(fù)雜度主要源于初始化種群和RBFGN,通過網(wǎng)絡(luò)前饋計(jì)算為輸入粒子決策出相應(yīng)的搜索動(dòng)作,增加或刪除RBFGN隱藏層節(jié)點(diǎn)(子群),以及更新RBFGN權(quán)值與隱藏層節(jié)點(diǎn).對(duì)于D維搜索空間中的多峰優(yōu)化問題,初始化規(guī)模為N的種群需要的時(shí)間復(fù)雜度為O(ND).基于初始的種群,本文利用層次的k-means聚類方法生成k個(gè)類簇中心,作為RBFGN的初始隱藏層節(jié)點(diǎn)(子群)中心,并初始化網(wǎng)絡(luò)權(quán)值,其總的時(shí)間復(fù)雜度為O(kND)(k 假設(shè)當(dāng)前隱藏層包括m個(gè)節(jié)點(diǎn),在RBFGN的前饋計(jì)算過程中,實(shí)現(xiàn)對(duì)輸入粒子兩個(gè)搜索動(dòng)作的決策.作為搜索動(dòng)作之一,定位輸入粒子的學(xué)習(xí)目標(biāo)需要計(jì)算該粒子與m個(gè)子群中心的距離,以找出距其最近的子群中心,時(shí)間復(fù)雜度為O(mD+m)=O(mD).由于RBFGN前兩層之間的連接只起到將輸入粒子傳遞到隱藏層的作用(前兩層間的權(quán)值均設(shè)置為1),在實(shí)際計(jì)算過程中,根據(jù)公式(4)輸入的粒子直接參與每個(gè)隱藏層節(jié)點(diǎn)的響應(yīng)值計(jì)算.根據(jù)響應(yīng)的定義,需要計(jì)算輸入粒子到每個(gè)隱藏層節(jié)點(diǎn)中心(共m個(gè))的距離,而該距離在之前定位學(xué)習(xí)目標(biāo)的過程中已獲取,因此計(jì)算輸入粒子在m個(gè)隱藏層節(jié)點(diǎn)上響應(yīng)值的時(shí)間復(fù)雜度為O(m).作為RBFGN產(chǎn)生的另一搜索動(dòng)作,調(diào)整輸入粒子的加速系數(shù)其時(shí)間耗費(fèi)主要發(fā)生在網(wǎng)絡(luò)后兩層間的前饋計(jì)算,以及輸出層的動(dòng)作選擇(輸出層共有3個(gè)節(jié)點(diǎn),對(duì)應(yīng)增加、減少加速系數(shù),以及保持加速系數(shù)不變),決策出該動(dòng)作所需的時(shí)間復(fù)雜度為O(m+3m+3)=O(m).因此,對(duì)于輸入粒子,RBFGN決策出兩個(gè)搜索動(dòng)作的時(shí)間復(fù)雜度為O(mD+m)=O(mD). 利用RBFGN決策出的兩個(gè)動(dòng)作更新輸入粒子的位置和適應(yīng)值之后,基于公式(15)若增加子群的兩個(gè)條件均滿足,將選擇當(dāng)前的輸入粒子作為新的隱藏層節(jié)點(diǎn)(子群)中心.在公式(15)中的條件中,為了判斷種群中哪些粒子被分配到候選新子群,需要考慮種群中每個(gè)粒子(共N個(gè))到m+1個(gè)隱藏層節(jié)點(diǎn)中心(包括候選新子群中心)的距離,而直接計(jì)算這些距離會(huì)造成昂貴的計(jì)算耗費(fèi).實(shí)際上只需計(jì)算每個(gè)粒子(共N個(gè))到候選新子群中心的距離,其時(shí)間復(fù)雜度為O(ND).這是因?yàn)樵谕瓿沙跏甲尤簞澐种?可利用一個(gè)N維的數(shù)組來保存每個(gè)粒子到其最近子群中心的距離(該距離首先由層次的k-means聚類方法得到,且該聚類方法只會(huì)執(zhí)行一次).相應(yīng)地,在后面每次更新各粒子到其最近子群中心的距離時(shí),只需比較當(dāng)前保存的距離和粒子到候選新子群中心間的距離,故計(jì)算公式(15)中條件的時(shí)間復(fù)雜度為O(ND).接著,利用公式(16)設(shè)置新子群中心的各項(xiàng)參數(shù).對(duì)于輸入的粒子,由于在之前的前饋計(jì)算過程中已經(jīng)獲得了計(jì)算該公式所需的μnr和ei,因此不會(huì)增加額外的時(shí)間復(fù)雜度.基于公式(15),若增加子群的任一條件不滿足,則需更新RBFGN的隱藏層節(jié)點(diǎn)和權(quán)值.由3.4節(jié)的分析可知,對(duì)于輸入的粒子,只需更新一個(gè)隱藏層節(jié)點(diǎn),以及該節(jié)點(diǎn)與動(dòng)作節(jié)點(diǎn)相連的一個(gè)權(quán)值.在更新過程中,公式(17)~公式(22)中的參數(shù)zac,yac和μnr已在之前的搜索動(dòng)作決策過程中獲得,也不會(huì)增加額外的時(shí)間復(fù)雜度.在更新過程之后,若公式(23)的任一條件滿足,則會(huì)刪除更新后不適合的隱藏層節(jié)點(diǎn)(子群).由于公式(23)與公式(15)中的條件均相反,類似地計(jì)算公式(23)所需的時(shí)間復(fù)雜度也為O(ND).值得注意的是,在每次迭代過程中增加隱藏層節(jié)點(diǎn)和刪除隱藏層節(jié)點(diǎn)這兩者最多只會(huì)執(zhí)行其一,因此逐個(gè)輸入種群中的粒子,算法總的時(shí)間復(fù)雜度為O(N2D). 本文選取CEC2013測(cè)試集[16]的15個(gè)多峰函數(shù)來反映RBFNN-PSO的表現(xiàn).15個(gè)多峰函數(shù)如表 1所示. 15個(gè)多峰函數(shù)在每個(gè)維度上的搜索范圍均設(shè)置為[-100,100].根據(jù)CEC2013的統(tǒng)一要求,MaxFEs設(shè)置為10000×D,其中D=30為搜索空間的維度.RBFNN-PSO的種群規(guī)模設(shè)置為50.為了公平比較,在15個(gè)測(cè)試函數(shù)上每種算法均獨(dú)立運(yùn)行30次,并計(jì)算其平均求解結(jié)果. 為了設(shè)置公式(15)和公式(23)中的,選擇取值不同的在CEC2013測(cè)試集15個(gè)多峰函數(shù)上進(jìn)行實(shí)驗(yàn),其中的取值為0.001,0.01,0.1和1.表2給出不同取值下RBFNN-PSO在15個(gè)多峰函數(shù)上的平均適應(yīng)值(Mean)及其標(biāo)準(zhǔn)差(Std.).每個(gè)函數(shù)上最好的平均適應(yīng)值用黑體下劃線標(biāo)記,并在下方給出了Mean的平均排名,以展示不同取值下算法的綜合表現(xiàn). 表1 CEC2013多峰函數(shù)Table 1 Multimodal functions in CEC2013 由表2可以看出,當(dāng)ε取值為0.01時(shí)RBFNN-PSO在除了f19之外的14個(gè)多峰函數(shù)上均取得了最好的平均適應(yīng)值,并以1.07的平均排名在15個(gè)多峰函數(shù)上獲得最好的綜合表現(xiàn).這是因?yàn)楫?dāng)ε=0.001時(shí),重要性閾值過小,輸入的粒子容易被初始化為新的子群中心,使得子群過多.由于種群規(guī)模有限(固定為50),過多的子群將造成有些子群中粒子個(gè)數(shù)較少,不利于子群的搜索.而當(dāng)ε=0.1或ε=1時(shí),重要性閾值過大,將造成子群數(shù)量不足,不利于保持種群多樣性.因此在后續(xù)實(shí)驗(yàn)中我們將ε設(shè)置為0.01. 4.3.1 RBFNN-PSO與PSO變體算法比較 本文首先選擇5種PSO變體算法進(jìn)行比較,對(duì)比算法包括融入社會(huì)影響力的粒子群優(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],和帶有信息共享機(jī)制的競(jìng)爭(zhēng)和合作粒子群優(yōu)化算法(Competitive and Cooperative Particle Swarm Optimization with Information Sharing Mechanism,CCPSO-ISM)[21].這些算法均采用其原始論文中的參數(shù)設(shè)置. 表3給出了6種算法在15個(gè)多峰測(cè)試函數(shù)上的平均適應(yīng)值(Mean)及其標(biāo)準(zhǔn)差(Std.).每個(gè)函數(shù)上的最好平均適應(yīng)值通過粗體下劃線標(biāo)記.為進(jìn)一步展示各算法的綜合表現(xiàn),表4給出了6種算法在15個(gè)多峰測(cè)試函數(shù)上Mean的排名與平均排名.由表3可以看出,RBFNN-PSO在其中7個(gè)多峰測(cè)試函數(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)勢(shì)明顯. 表3 6種算法在CEC2013測(cè)試集15個(gè)多峰函數(shù)上的平均求解結(jié)果比較Table 3 Comparisons of the mean resultsfor the 6 algorithms on the 15 multimodal functions of CEC2013 test suite 表4 6種算法在CEC2013測(cè)試集15個(gè)多峰函數(shù)上的分別排名與平均排名比較Table 4 Comparisons of the ranks and averageranks for the 6 algorithms on the 15 multimodal functions of CEC2013 test suite 為了更直觀地展示算法的求解精度與收斂速度,圖3給出在8個(gè)多峰測(cè)試函數(shù)(f6、f8、f10、f11、f14、f16、f17、f18)上,6種算法的適應(yīng)值隨迭代次數(shù)變化的曲線.從圖3可以看出,除了f18,RBFNN-PSO在其他7個(gè)函數(shù)上均取得最好的求解精度,而且在其中的f11和f17上收斂最快.另外,根據(jù)RBFNN-PSO在f6、f8、f14、f16、f17上的收斂曲線,即使在其前期搜索精度不高的情況下,通過保持種群多樣性與合理指導(dǎo)粒子搜索動(dòng)作,RBFNN-PSO最終取得比其他5種算法更優(yōu)的求解精度. 圖3 6種算法的收斂曲線比較Fig.3 Comparisons of convergencecurves with respect to 6 algorithms 為了比較各個(gè)算法的尋優(yōu)速度,在相同的仿真環(huán)境下,6種算法在CEC2013測(cè)試集的15個(gè)多峰函數(shù)上分別獨(dú)立運(yùn)行30次,表5記錄了6種算法達(dá)到指定精度時(shí)的平均運(yùn)行時(shí)間.由表5可以看出,在15個(gè)多峰函數(shù)上,RBFNN-PSO到達(dá)指定精度的時(shí)間消耗與其他5種對(duì)比算法大致相同,且相比于其他5種算法,RBFNN-PSO在f7、f11和f17上運(yùn)行時(shí)間最短.基于3.7節(jié)的分析,RBFNN-PSO需要為每個(gè)輸入粒子決策出相應(yīng)的搜索動(dòng)作,增加或刪除RBFGN隱藏層節(jié)點(diǎn)(子群),以及更新權(quán)值與隱藏層節(jié)點(diǎn),會(huì)造成一定的時(shí)間耗費(fèi),導(dǎo)致其時(shí)間復(fù)雜度的增加.但是由于其對(duì)搜索動(dòng)作的出色決策能力,在達(dá)到指定精度時(shí),運(yùn)行的代數(shù)相對(duì)較少,從而在運(yùn)行時(shí)間上和其他5種算法大致相同.然而,重要的是在表3和表4中本文提出的RBFNN-PSO在求解精度方面,相對(duì)于其他5種算法優(yōu)勢(shì)明顯. 表5 6種算法在CEC2013測(cè)試集15個(gè)多峰函數(shù)上達(dá)到指定求解精度的運(yùn)行時(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)化算法的比較 為了進(jìn)一步驗(yàn)證本文所提出的RBFNN-PSO求解多峰優(yōu)化問題的有效性,還將該算法與3種其他優(yōu)化算法(非基于PSO的優(yōu)化算法)進(jìn)行比較,這些算法包括:CoDE[22]、PBILc[23]和AABC[24],分別屬于差分進(jìn)化算法、群體分布估計(jì)算法和人工蜂群算法的變體. 表6給出了RBFNN-PSO、CoDE、PBILc、AABC這4種算法在15個(gè)多峰測(cè)試函數(shù)上的平均適應(yīng)值(Mean)及其標(biāo)準(zhǔn)差(Std.).每個(gè)函數(shù)上的最好平均適應(yīng)值通過粗體下劃線標(biāo)記.為了展示各算法的綜合表現(xiàn),在表6的下方給出了其根據(jù)Mean的平均排名.從表6可以看出,相比于其他3種算法,RBFNN-PSO在7個(gè)函數(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,進(jìn)一步驗(yàn)證了本文所提出的RBFNN-PSO求解多峰優(yōu)化問題的有效性. 表6 4種算法在CEC2013測(cè)試集15個(gè)多峰函數(shù)上的平均求解結(jié)果比較Table 6 Comparisons of the mean resultsfor the 4 algorithms on the 15 multimodal functions of CEC2013 test suite 本文提出一種徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)指導(dǎo)的粒子群優(yōu)化算法(RBFNN-PSO).該算法利用設(shè)計(jì)的徑向基函數(shù)指導(dǎo)網(wǎng)絡(luò)(RBFGN),在保持種群多樣性的同時(shí),合理定位粒子學(xué)習(xí)目標(biāo),有效調(diào)整粒子加速系數(shù),以最終解決多峰優(yōu)化問題.具體地,RBFGN將整個(gè)種群劃分為多個(gè)子群,子群中心作為子群粒子的學(xué)習(xí)目標(biāo),指導(dǎo)其搜索.RBFGN充分考慮種群多樣性,選擇能代表子群搜索特性的粒子作為子群中心,并使之遠(yuǎn)離已存在的子群中心.因而,通過選擇合適的子群中心,實(shí)現(xiàn)子群的劃分.不同子群粒子在各自子群中心指導(dǎo)下搜索,呈現(xiàn)出多樣的搜索特性,提升了種群多樣性.RBFGN的輸出層輸出粒子加速系數(shù)的調(diào)整動(dòng)作,并根據(jù)隱藏層決策出的學(xué)習(xí)目標(biāo),有效指導(dǎo)粒子的搜索.本文引入強(qiáng)化學(xué)習(xí)來訓(xùn)練網(wǎng)絡(luò),利用產(chǎn)生的反饋,期望獲得最大的累積收益,實(shí)現(xiàn)對(duì)隱藏層節(jié)點(diǎn),以及其與動(dòng)作節(jié)點(diǎn)相連權(quán)值的有效調(diào)整. 為了反映RBFNN-PSO的表現(xiàn),在CEC2013測(cè)試集上的15個(gè)多峰函數(shù)中開展廣泛實(shí)驗(yàn),通過與5種主流的PSO變體算法以及3種其他優(yōu)化算法進(jìn)行比較,其結(jié)果表明本文所提出的RBFNN-PSO求解多峰優(yōu)化問題的能力優(yōu)勢(shì)明顯.在下一步工作中,將把RBFNN-PSO應(yīng)用于求解一些實(shí)際多峰優(yōu)化問題,并將其拓展到更復(fù)雜的優(yōu)化領(lǐng)域,例如動(dòng)態(tài)優(yōu)化領(lǐng)域和大規(guī)模優(yōu)化領(lǐng)域等.3.7 算法時(shí)間復(fù)雜度分析
4 仿真實(shí)驗(yàn)及結(jié)果分析
4.1 測(cè)試函數(shù)
4.2 參數(shù)設(shè)置
4.3 實(shí)驗(yàn)結(jié)果與分析
5 結(jié) 論