拓?fù)湎嗷プ饔门c距離的影響引入歐椋鳥群飛行機(jī)制的改進(jìn)粒子群算法

拓?fù)湎嗷プ饔门c距離的影響引入歐椋鳥群飛行機(jī)制的改進(jìn)粒子群算法

0pso算法的改進(jìn)顆粒群優(yōu)化算法（pso）是年輕群體智能優(yōu)化算法。與遺傳統(tǒng)計(jì)方法（ga）、免疫算法（ia）和螞蟻算法（aco）相比，由于其自由參數(shù)少、算法結(jié)構(gòu)簡單、易于實(shí)現(xiàn)，因此獲得了該算法。因此,近年來在最優(yōu)化領(lǐng)域和群學(xué)習(xí)領(lǐng)域得到了廣泛的研究和應(yīng)用,國際進(jìn)化計(jì)算會(huì)議(CEC)也將其列為討論專題之一。粒子群算法是由美國科學(xué)家Kennedy等人在1995年提出的,最初是為了模擬鳥群的群體覓食和運(yùn)動(dòng)行為,所以其數(shù)學(xué)基礎(chǔ)并不完善,實(shí)現(xiàn)技術(shù)也不規(guī)范,在參數(shù)設(shè)置、收斂理論等方面還存在許多值得深入研究的問題。因此,從PSO出現(xiàn)至今,出現(xiàn)了眾多對(duì)基本PSO的改進(jìn)算法,如對(duì)慣性權(quán)重的不同設(shè)置方式、結(jié)合遺傳算子(選擇、交叉、變異)的改進(jìn)算法、免疫粒子群算法、量子粒子群算法等。這些算法在不同程度上提高了粒子群算法的收斂精度和速度,在一定范圍內(nèi)避免粒子種群的早熟。實(shí)際上,這些改進(jìn)算法利用了粒子群算法的進(jìn)化特性,結(jié)合其他群智能算法的復(fù)雜算子和進(jìn)化機(jī)理,使得基本PSO算法獲得更優(yōu)的參數(shù)設(shè)置和種群個(gè)體,從而使算法具有更好的性能。但是這些改進(jìn)算法的基本框架都建立在Kennedy-Eberhart的位移—速度模型上,這就使得其性能的改進(jìn)逃不出模型的局限性,而復(fù)雜的進(jìn)化算子和策略的引入也使得原本簡潔的算法變得非常復(fù)雜,算法實(shí)現(xiàn)變得困難,算法的運(yùn)行效率很低。近年來生物學(xué)家通過對(duì)歐椋鳥群深入研究和觀察發(fā)現(xiàn),鳥類的群體行為并非由群體中個(gè)體的相對(duì)距離決定,而是受到個(gè)體與特定數(shù)量的相鄰個(gè)體間的拓?fù)渥饔弥萍s。這一新的發(fā)現(xiàn)為粒子群算法的改進(jìn)提供了新的思路。本文受這一最新研究啟發(fā),提出了一種新的引入歐椋鳥飛行機(jī)制的SFPSO(starlingflightparticleswarmoptimization)算法。1改進(jìn)粒子群算法傳統(tǒng)PSO及其各種改進(jìn)算法,其基本框架和原理都建立在Kennedy-Eberhart的位移—速度模型的基礎(chǔ)上,采用空間距離準(zhǔn)則來決定粒子的下一個(gè)位置,沒有考慮粒子間的拓?fù)渥饔?。從社?huì)學(xué)的角度理解,種群的學(xué)習(xí)和進(jìn)化采用自省式與精英式相結(jié)合的方式,即個(gè)體通過三個(gè)通道完成學(xué)習(xí)和進(jìn)化:個(gè)體歷史值、歷史最優(yōu)值(自省式)和社會(huì)歷史最優(yōu)值(精英式)。其位置、速度更新公式如式(1)(2)所示。其中:k代表進(jìn)化代數(shù)(k=1,2,…,itermax),itermax表示最大進(jìn)化代數(shù);i代表第i個(gè)粒子,j代表第j個(gè)待優(yōu)化參數(shù);c1、c2為學(xué)習(xí)因子,通常取c1=c2=2;r1、r2為介于(0,1)間的隨機(jī)數(shù);ppbest(k)ij、pgbest(k)j分別表示第i個(gè)粒子第j個(gè)參數(shù)在第k代的歷史最優(yōu)位置和第j個(gè)參數(shù)在第k代的社會(huì)最優(yōu)位置;p(k)ij、v(k)ij分別代表第i個(gè)粒子第j個(gè)參數(shù)在第k代的位置和速度。式(1)中的前兩項(xiàng)代表自省式學(xué)習(xí),第三項(xiàng)代表精英式學(xué)習(xí)。v(k+1)ij=v(k)ij+c1×r1×(ppbest(k)ij-p(k)ij)+c2×r2×(pglobal(k)j-p(k)ij)(1)p(k+1)ij=p(k)ij+v(k+1)ij(2)為保證算法的收斂,Shi等人和Clerc在Kennedy-Eberhart模型的基礎(chǔ)之上相繼引入權(quán)重和收斂因子等,并逐步建立了算法嚴(yán)格的數(shù)學(xué)基礎(chǔ);后來的學(xué)者為了使算法適應(yīng)更為復(fù)雜的情形,將模糊理論、遺傳算法、免疫算法、混沌等與粒子群算法結(jié)合起來,使粒子群算法得到了很大的發(fā)展。但是,所有這些算法依然存在如下問題:a)容易出現(xiàn)早熟現(xiàn)象,表現(xiàn)在進(jìn)化過程中,種群會(huì)迅速失去多樣性,這在多模態(tài)問題和高維復(fù)雜優(yōu)化場合容易陷入局部最優(yōu)解;b)算法的精度不高,這與其容易失去多樣性密切相關(guān);c)各種改進(jìn)算法使傳統(tǒng)PSO算法具有了自適應(yīng)性,一定程度上提高了算法的精度,使算法適應(yīng)了更為復(fù)雜的情形,但復(fù)雜算子的引入使算法變得更為復(fù)雜,實(shí)現(xiàn)起來比較困難,自由參數(shù)的增多使算法效率不高,并且難以控制。從粒子進(jìn)化的過程看,建立在Kennedy-Eberhart模型基礎(chǔ)之上的PSO算法,種群中不同個(gè)體之間缺乏信息交流(只與最優(yōu)粒子交流),這使得算法開始后不久粒子便出現(xiàn)集中,很快失去個(gè)性,導(dǎo)致種群失去多樣性,一旦陷入局部極值后,就很難再跳出來。這對(duì)于簡單的單極值函數(shù)優(yōu)化影響不大,但對(duì)于復(fù)雜函數(shù)和多模態(tài)優(yōu)化問題,算法就有可能無法找到全局點(diǎn)。文獻(xiàn)提出了一種小生境PSO算法來改善這種狀況,它只采用自省式的學(xué)習(xí)方式,以增強(qiáng)粒子的個(gè)性,保證多樣性,使粒子能收斂于不同的極值點(diǎn)。但是該算法不適合大的搜索解空間,而且粒子群必須保證一定的規(guī)模,否則難以保證精度和找到所有的極值點(diǎn)。圖1的粒子云圖變化展示了傳統(tǒng)粒子群算法如何失去種群多樣性和陷入局部極值點(diǎn)的過程。2歐景鳥群飛行的本質(zhì)歐椋鳥,又叫燕八哥,主要分布在歐洲境內(nèi)、加拿大中部和美國全境,每到黃昏時(shí)分,在一些地區(qū)的上空,成百上千只歐椋鳥聚集在一起飛行,形成一道奇特的風(fēng)景。其奇特之處在于整個(gè)鳥群的飛行就像雪崩,在飛行過程中形成一個(gè)單一的實(shí)體,個(gè)體之間完全同步,這種現(xiàn)象引起了世界各地研究者的廣泛興趣。羅馬大學(xué)的理論物理學(xué)家喬治·帕里希認(rèn)為歐椋鳥的這種飛行機(jī)制類似于雪崩和晶體形成的瞬時(shí)轉(zhuǎn)變的均衡臨界系統(tǒng),但這種幾乎瞬時(shí)的信號(hào)處理速度依然令人困惑。Ballerini等人經(jīng)過長期觀察發(fā)現(xiàn),歐椋鳥群之所以能形成一個(gè)單一實(shí)體,在于鳥群個(gè)體與一定數(shù)量相鄰個(gè)體之間存在拓?fù)渥饔?這種作用的程度取決于這種相鄰個(gè)體的數(shù)量,而個(gè)體之間的距離并不起決定作用。圖2是歐椋鳥鳥群和計(jì)算機(jī)從三個(gè)角度重建的圖像。2.1拓?fù)渥饔脵C(jī)制基于生物學(xué)家對(duì)歐椋鳥群的研究,Montes等人研究了三種拓?fù)浣Y(jié)構(gòu)的粒子群算法,對(duì)歐椋鳥的飛行進(jìn)行模擬:a)全連接結(jié)構(gòu),即種群中的每個(gè)粒子是其他所有粒子的相鄰點(diǎn);b)VonNeumann拓?fù)浣Y(jié)構(gòu),即種群中每個(gè)粒子有四個(gè)相鄰的粒子;c)環(huán)形拓?fù)浣Y(jié)構(gòu),即每個(gè)粒子有三個(gè)相鄰粒子。文獻(xiàn)提出通過所謂的極化作用Φ來度量歐椋鳥群的整體有序程度,但是對(duì)于鳥群中個(gè)體行為狀態(tài)的波動(dòng)應(yīng)該用種群整體的速度平均衡量,即對(duì)N個(gè)個(gè)體群體中的個(gè)體i,其速度的波動(dòng)為ui=vi-1ΝΝ∑k=1vk(3)極化作用和速度的波動(dòng)在一定程度上反映了鳥群在空間中飛行時(shí)的拓?fù)渥兓潭然蛳嗷プ饔玫某潭取Ｒ虼?本文在Montes等人研究的基礎(chǔ)上,在位移—速度框架下,將這種拓?fù)湎嗷プ饔脵C(jī)制引入算法,并對(duì)參數(shù)進(jìn)行了新的設(shè)置,使算法在具有歐椋鳥飛行特征的同時(shí)具有更強(qiáng)的自適應(yīng)性。其速度更新公式為v(k+1)ij=ω×v(k)ij+c1×rand×(ppbest(k)ij-p(k)ij)+c2×rand×(pglobal(k)j-p(k)ij)+c3×rand×V_topologic(k)ij(4)V_topologic(k)ij=1ΝΣn∈Τv(k)nj(5)其中:c3為拓?fù)鋵W(xué)習(xí)因子;N=num,num=#T(集合的勢);T為與第i只鳥發(fā)生拓?fù)渥饔?、?shù)量為num的粒子集合;其他參數(shù)含義同式(1)(2)。由于拓?fù)漤?xiàng)式(4)的引入,使傳統(tǒng)粒子群算法發(fā)生了深刻的變化,即單獨(dú)粒子與一定數(shù)量的其他粒子在速度上保持某種同步,傳統(tǒng)粒子群算法是不具備這一特點(diǎn)的。粒子云圖表現(xiàn)為以群落為單位在解空間飛行,而不是傳統(tǒng)算法中以點(diǎn)為單位飛行。圖3用具有方向性箭頭表示的粒子飛行姿態(tài)說明了這一新特點(diǎn)。由于每只鳥的運(yùn)動(dòng)與相鄰鳥的關(guān)系最為密切,相互之間完成主要的信息交流,因此,不同于Montes等人的研究,這里拓?fù)湎嗷プ饔玫募蟃,選取num個(gè)最近鄰個(gè)體,而不是任意選取。采用歐式距離度量兩個(gè)不同粒子的距離遠(yuǎn)近,即Dist(k)(i,j)=√D∑n=1(p(k)in-p(k)jn)2(6)對(duì)于第k代第i個(gè)粒子,計(jì)算其與其他粒子的距離,取num個(gè)距離最近的粒子,其序號(hào)組成集合T,根據(jù)式(4)計(jì)算拓?fù)渥饔庙?xiàng)。num采用事先設(shè)置的方式,一般取num=3～7。由于拓?fù)湟蜃铀鸬淖饔檬潜３址N群的多樣性,從而在更大范圍進(jìn)行搜索,當(dāng)慣性權(quán)重減小,使粒子群逐漸失去多樣性時(shí),此時(shí)應(yīng)加強(qiáng)拓?fù)渥饔?使粒子與其他個(gè)體的信息交互增強(qiáng),從而避免種群坍縮到局部點(diǎn);同時(shí),為了保證精度,默認(rèn)三分之二代數(shù)后找到全局解,不再保持粒子的多樣性,因此此時(shí)置c3=0,拓?fù)渥饔靡蜃訛閏3=(1-ω)×(k≤23G)(7)其中:ω為慣性權(quán)重因子;k為進(jìn)化代數(shù);G為總代數(shù)。拓?fù)渥饔脵C(jī)制使SFPSO算法具備兩個(gè)明顯優(yōu)勢:a)粒子的運(yùn)動(dòng)具有同步的特征,表現(xiàn)在飛行中粒子云圖始終保持一定的大小,這便于在大范圍進(jìn)行搜索,而不易早熟,相鄰粒子的拓?fù)渥饔每梢詫⒘Ｗ尤簬С鼍植繕O值點(diǎn);b)對(duì)于多模態(tài)優(yōu)化問題,SFPSO算法具備找到所有全局極值點(diǎn)的能力。2.2控制因子的選取首先給出粒子動(dòng)能的概念。定義1假設(shè)粒子的質(zhì)量為單位1,第i個(gè)粒子在第k代的動(dòng)能定義為Ei=12D∑j=1(v(k)ij)2(8)其中:j=1,…,D,D為解空間維數(shù),則粒子群的總動(dòng)能為E=Ν∑i=1Ei。粒子群的動(dòng)能反映了算法進(jìn)化的節(jié)奏,動(dòng)能大,表明節(jié)奏快,反之則表明節(jié)奏慢?？旃?jié)奏需要慣性權(quán)重不斷減小,而節(jié)奏慢下來后需要大的慣性權(quán)重,以保證粒子不要過度集中。于是慣性權(quán)重因子可通過式(9)自適應(yīng)得到,即ω=ωmax-(ωmax-ωmin)×iter/itermax+α×rand×e-E(9)其中:α稱為控制因子;ωmax、ωmin為線性遞減權(quán)重的動(dòng)態(tài)范圍;rand為介于(0,1)間的任意數(shù),通過動(dòng)能的作用,對(duì)慣性權(quán)重的遞減起到一定的緩沖作用,使慣性權(quán)重能根據(jù)算法的節(jié)奏自適應(yīng)地調(diào)整。自適應(yīng)慣性權(quán)重策略很大程度上保證了算法的收斂性,并有利于精度的提高。2.3重新更新機(jī)制的缺陷受歐椋鳥覓食機(jī)制的啟發(fā),引入另一個(gè)簡單卻非常有效的機(jī)制,即獵食動(dòng)物的驚擾。當(dāng)有獵食動(dòng)物出現(xiàn)的時(shí)候,歐椋鳥群以較大的逃逸速度vesc迅速向四面散開,而后又依照原有機(jī)制在新的位置重新開始更新。這相當(dāng)于遺傳算法的變異機(jī)制,卻又簡單直接得多,其計(jì)算式為v(k+1)ij=-sign(v(k+1)ij)×vesc(10)驚擾機(jī)制非常有利于逃出局部極值點(diǎn)。不過在要求精度的情況下,獵食動(dòng)物的過度驚擾會(huì)導(dǎo)致鳥群沒有足夠的時(shí)間開發(fā)極值點(diǎn),從而導(dǎo)致精度下降。因此,根據(jù)進(jìn)化過程和經(jīng)驗(yàn),一般以釋放2～3次獵食動(dòng)物比較合理,同時(shí)在進(jìn)化的最后20～30代不再進(jìn)行驚擾,以保證算法的精度。2.4性能各因子更新的一般特征綜上所述,SFPSO算法可描述如下:Initializationswarm_size=N,itermax=G;%種群規(guī)模及進(jìn)化最大代數(shù)c1=λ;c2=γ;ωmax、ωmin和控制因子α;scope=[start,end];%解空間范圍,start、end為向量,長度為解空間維數(shù)DV_limit=Vmax;%最大速度限制初始化粒子位置逃逸速度vesc;foreachbirdp(1)ij=start(j)+(end(j)-start(j))*rand;%第i只鳥第j維參數(shù)的初始位置v(1)ij=Vmax*rand;%第i只鳥第j維參數(shù)的初始速度fitness(0)i=∞;%個(gè)體歷史最優(yōu)適應(yīng)度初始值endfitness_global(0)=∞;%社會(huì)歷史最優(yōu)適應(yīng)度初始值Evolutionk=1;%k代表進(jìn)化代數(shù)do%進(jìn)化循環(huán)體foreachbirdfitness(k)i=f(p(k)i1,p(k)i2,…,p(k)iD);%計(jì)算每只鳥的當(dāng)前適應(yīng)度值iffitness(k)i>fitness(k-1)ippbest(k)ij=p(k-1)ij;%更新個(gè)體歷史最優(yōu)位置,j=1,…,Dendendfitness_global(k)=min(fitness(k)1,fitness(k)2,…,fitnessΝ(k));%計(jì)算當(dāng)前社會(huì)最優(yōu)適應(yīng)度值iffitness_global(k)>fitness_global(k-1)fitness_global(k)=fitness_global(k-1);%更新當(dāng)前社會(huì)最優(yōu)適應(yīng)度值endpglobalj(k)=argpij(k)min(fitness1(k),fitness2(k),?,fitnessΝ(k));%更新當(dāng)前社會(huì)最優(yōu)位置,j=1,…,D通過式(5)(6)計(jì)算粒子群總動(dòng)能和慣性權(quán)重ω,拓?fù)渥饔靡蜃觕3=(1-ω)*(k≤23G)foreachbirdV_topologicij(k)=1ΝΣn∈Τvnj(k);%N=num,num=#T,T為與第i只發(fā)生拓?fù)渥饔玫淖罱忴B的集合vij(k+1)=ω*vij(k)+c1*rand*(ppbestij(k)-pij(k))+c2*rand*(pglobalj(k)-pij(k))+c3*rand*V_topologicij(k);pij(k+1)=pij(k)+vij(k+1);%更新速度和位置,j=1,…,D限制最大速度為[-Vmax,Vmax];最大位置[start,end];ifiter=獵食動(dòng)物時(shí)間,vij(k+1)=-sign(vij(k+1))*vesc;endk=k+1;end(while(k≤G))3種算法比較為了驗(yàn)證SFPSO算法的有效性,基于Benchmark標(biāo)準(zhǔn)函數(shù)庫的四個(gè)典型函數(shù)(表1)進(jìn)行優(yōu)化計(jì)算,對(duì)PSO、GA-PSO和SFPSO算法在找到全局極值點(diǎn)的精度、成功率和效率三個(gè)方面進(jìn)行了比較(表2)。算法的參數(shù)設(shè)置為:粒子群規(guī)模100,位置范圍根據(jù)函數(shù)確定,速度上界取位置的總變化范圍,初始速度和初始位置根據(jù)表1設(shè)置,最大進(jìn)化代數(shù)200,學(xué)習(xí)因子c1=0.1,c2=0.3,慣性權(quán)重上、下界wmax=0.9,wmin=0.4,控制因子α=0.3,解空間維數(shù)為2,逃逸速度取速度上界,釋放獵食動(dòng)物1次,每種算法單獨(dú)運(yùn)行100次。表2給出了三種算法的比較。圖4為運(yùn)行100代時(shí)四種函數(shù)的PSO、GA-PSO和SFPSO算法成功時(shí)的收斂曲線比較。根據(jù)實(shí)驗(yàn)過程和結(jié)果,可以得出如下結(jié)論:a)從圖4和表2可以看出,SFPSO和GA-PSO均能更快地找到全局極值點(diǎn),成功率大大提高,平均所需代數(shù)得到很大降低,所以平均下來的精度要高一些,收斂稍快一些;限于篇幅問題,沒有列出找不到全局極值點(diǎn)的情形,如果兩種算法一開始都沒找到全局極值點(diǎn),SFPSO隨著算法的運(yùn)行最終可以找到,而PSO將再也無法找到全局點(diǎn)。值得指出的是,對(duì)于多極值函數(shù)f4,SFPSO在算法運(yùn)行過程中找到兩個(gè)點(diǎn),而PSO只能找到一個(gè)點(diǎn),GA-PSO算法有時(shí)可以找到兩個(gè)點(diǎn)。b)在SFPSO算法中,粒子動(dòng)能概念的引入使慣性權(quán)重的遞減與算法運(yùn)行的節(jié)奏保持了一致,從而使算法具有更好的自適應(yīng)性。