拓撲相互作用與距離的影響引入歐椋鳥群飛行機制的改進粒子群算法

拓撲相互作用與距離的影響引入歐椋鳥群飛行機制的改進粒子群算法

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