變采樣周期的粒子群優(yōu)化模型

變采樣周期的粒子群優(yōu)化模型

1速度vid顆粒優(yōu)化算法是一種優(yōu)化算法，用于模擬生物群體（如鳥群）的行為。聯(lián)合行為傾向于通過粒子間的合作和競爭，并具有優(yōu)秀成績。這是集體智能研究領(lǐng)域的熱點(diǎn)。對于D維復(fù)雜搜索空間,標(biāo)準(zhǔn)PSO算法的n(n≥2)個(gè)粒子的質(zhì)點(diǎn)動力學(xué)表示為uf8f1式中:vid是粒子速度向量;xid是粒子的位置向量;pid為個(gè)體位置最優(yōu)值;pgd為群體位置最優(yōu)值;c1,c2為加速因子;w為慣性因子;ri1,ri2∈為服從統(tǒng)一分布的隨機(jī)數(shù).盡管標(biāo)準(zhǔn)PSO已經(jīng)在諸多領(lǐng)域得到成功的應(yīng)用,但是還存在很多需要改進(jìn)的地方.從式(1)可以看出,PSO算法粒子的更新都是以一定的時(shí)間間隔.從控制系統(tǒng)的角度看,它是一個(gè)離散系統(tǒng).從生物系統(tǒng)的角度看,生物群體的運(yùn)動是連續(xù)的.也就是說,個(gè)體的運(yùn)動不可能是以固定間隔時(shí)間跳躍的,而是連續(xù)光滑的.受這種事實(shí)的啟發(fā),連續(xù)時(shí)間的粒子群算法可能會提高離散PSO算法的優(yōu)化性能.考慮到連續(xù)系統(tǒng)在實(shí)際應(yīng)用中需要數(shù)字化(采樣),本文提出一種采樣粒子群優(yōu)化新模型.2采樣顆粒群優(yōu)化模型spss2.1pso算法描述為了便于統(tǒng)一描述,傳統(tǒng)PSO算法的描述如下:考慮最小化優(yōu)化問題其中:D是優(yōu)化問題的維數(shù),??RD是優(yōu)化問題的可行域,f:?→R是需要最小化的目標(biāo)函數(shù)值.設(shè)群體規(guī)模為n,不失一般性,PSO算法可以重新寫為其中:2.2系統(tǒng)“記憶”要建立采樣粒子群優(yōu)化模型,首先將式(3)前兩方程擴(kuò)展為如下的群體動力系統(tǒng)uf8f1其中:xid為個(gè)體位置,vid為個(gè)體速度,T為采樣時(shí)間,Mi為個(gè)體質(zhì)量,ui為個(gè)體控制輸入,ui(kT)=Miβ(pkTid-xkTid)+γ(pkTgd-xkTid).為書寫方便,在下文,令“kT”為t∈R+.由上面分析知,系統(tǒng)的狀態(tài)變量除了xi,vi外,pid起優(yōu)解“記憶”的作用.在離散PSO算法中,由式(3)第3個(gè)方程可以看出pid的變化是通過兩個(gè)離散狀態(tài)實(shí)現(xiàn)的.這里通過如下方式近似pid的連續(xù)變化.其中:a>0為常數(shù),δ=sgn(f(ptid)-f(xtid)).在式(5)中,考慮如下情況:1)當(dāng)f(pid(t))-f(xi(t))0時(shí),δ=1,此時(shí),pid(t+1)=pid(t)+2Ta(xi(t)-pid(t)).即當(dāng)前點(diǎn)目標(biāo)函數(shù)值小于個(gè)體最優(yōu)值時(shí),個(gè)體最優(yōu)值往當(dāng)前點(diǎn)移動.特殊情況,當(dāng)T=1,a=0.5時(shí),pid(t+1)=xi(t).2)當(dāng)f(pid(t))-f(xi(t))<0時(shí),δ=-1,此時(shí)pid(t+1)=pid(t).即當(dāng)前點(diǎn)目標(biāo)函數(shù)值大于個(gè)體最優(yōu)值時(shí),個(gè)體最優(yōu)值保持不變.pgd僅僅影響系統(tǒng)的平衡點(diǎn),可以看作系統(tǒng)的設(shè)定點(diǎn).這樣就將由式(3)描述的標(biāo)準(zhǔn)PSO算法拓展為式(4)和(5)描述的采樣PSO算法.2.3其他控制參數(shù)的edi-t為了分析算法的穩(wěn)定性,需要分析個(gè)體對群體最優(yōu)值pgd的聚集性能epi(t)、個(gè)體的速度趨同性能evi(t)和個(gè)體優(yōu)值對pgd的聚集性能edi(t),考慮如下誤差系統(tǒng):uf8f1假假設(shè)1在采樣時(shí)間T內(nèi),群體最優(yōu)解pgd保持不變或者變化極小,即vgd(t)=pgd(t+1)-pgd(t)～=0.其中?=a(1+δ).將式(7)寫成矩陣形式定義Ei=[epi,edi,evi]T,則第i個(gè)粒子的誤差動力學(xué)可以描述為3spss模式模型的穩(wěn)定性分析statianalysiss3.1算法穩(wěn)定性分析在本節(jié)中,通過李雅普諾夫函數(shù)分析粒子群算法的穩(wěn)定性,得出算法穩(wěn)定的條件.首先給出系統(tǒng)穩(wěn)定的假設(shè)條件.假設(shè)2令eli=epi-edi,假設(shè)定定理1考慮誤差系統(tǒng)(9),如果滿足假設(shè)1和假設(shè)2,系統(tǒng)在α<1,β,γ>0下一致穩(wěn)定.證為了研究誤差系統(tǒng)的穩(wěn)定性,構(gòu)造每個(gè)個(gè)體的李雅普諾夫函數(shù)為則:在上式中,?i的取值為“0”或“2a”.因此,當(dāng)α<1時(shí),˙V(t)<0,即定理得證.證畢.從定理1可以看出,算法穩(wěn)定的一個(gè)重要條件是系統(tǒng)采樣時(shí)間要滿足假設(shè)1和假設(shè)2.從假設(shè)1和假設(shè)2中只能知道采樣時(shí)間要足夠小,但是不能確定具體的范圍.下面將進(jìn)一步分析粒子軌跡收斂的采樣時(shí)間的約束條件.3.2算法有效性分析由式(4)(5)得:式中:式(13)的齊次矩陣形式為系數(shù)矩陣的特征多項(xiàng)式為該特征多項(xiàng)式的3個(gè)特征值分別為定定理2采樣粒子優(yōu)化模型的粒子軌跡收斂的采樣時(shí)間滿足條件證由式(14)所示,系統(tǒng)收斂的條件是系數(shù)矩陣|B|<1,即其特征值max{λ2,3}<1由λ2,3<1整理得.證畢.定理1和定理2保證了算法的穩(wěn)定性和粒子軌跡的收斂性.但是并不能說明算法能收斂到局部最優(yōu)或全局最優(yōu).下面將進(jìn)一步分析算法的收斂性及其改進(jìn)策略.4spss填補(bǔ)性分析coversions4.1fz條件Solis和Wets研究了隨機(jī)優(yōu)化算法的隨機(jī)逼近問題,給出了隨機(jī)優(yōu)化算法是局部最優(yōu)還是全局優(yōu)化的條件.本文利用其結(jié)果研究采樣粒子群算法的收斂性特性.為方便起見,先給出隨機(jī)優(yōu)化算法局部收斂和全局收斂的相關(guān)定義與引理如下:定義1給定函數(shù)f:Rn→R,S?Rn,點(diǎn)z∈S使f最小,可以定義為.條條件1f(G(z,ξ))f(z),且ifξ∈S,thenf(G(z,ξ))f(ξ),其中G是產(chǎn)生問題解的函數(shù).上述條件意味著隨機(jī)優(yōu)化算法新產(chǎn)生的解不差于當(dāng)前解.定定義2令ψ=inf(t:v[z∈S|f(z)<t]>0)其中v[A]是集合A的Lebesgue測度.最優(yōu)區(qū)域Rε可以定義為Rε={z∈S|f(z)<ψ+ε},其中ε>0.條條件2給定任意z0∈S,存在常數(shù)θ>0和0<μ1,對于任意k,使得:其中z包含于緊集L0={z∈S|f(z)f(z0)},表示點(diǎn)z到集合A的距離.條件3對于S的子集A,滿足v[A]>0,有其中ηk[A]表示A被產(chǎn)生的概率為ηk.條件2和條件3分別給出了算法局部最優(yōu)和全局最優(yōu)的條件,于是有如下引理:引理1假設(shè)f是可測函數(shù),S是Rn上的可測子集,且滿足條件1和條件2.令{zk}+∞k=0為算法產(chǎn)生的解序列.則其中P[zk∈Rε]是zk屬于局部最優(yōu)區(qū)域Rε的概率.引理2假設(shè)f是可測函數(shù),S是Rn上的可測子集,且滿足條件1和條件3.令{zk}+∞k=0為算法產(chǎn)生的解序列.則其中P[zk∈Rε]是zk屬于全局最優(yōu)區(qū)域Rε的概率.4.2pso算法收斂性分析由式(13),可以將xit+1寫為:其中:引理3對于SPSO算法,α<1,β,γ>0,則存在值1N<∞使得g2(xi(t-1))<ε,||g3(xi(t-1))<ε,?t>N,ε>0.證由定理1得證.證畢.定定理3SPSO算法不滿足條件2,無法保證收斂到局部極值.證對于SPSO,從式(4)和(5)可以看出,條件1中的函數(shù)D可以定義為顯然,式(21)滿足條件1.由β=c1.r1,γ=c2.r2,且r1,r2∈為服從統(tǒng)一分布的隨機(jī)數(shù),可以知道0βc1,0γc2.從式(21)可以看出,xit+1的搜索域的變化決定于g2和g3.而g2和g3是與βT2和γT2參數(shù)有關(guān)的超立方體.由引理3,當(dāng)xit=pit=pgt時(shí),xit+1的搜索域趨向于零.也就是說,在找到最優(yōu)解前,從最優(yōu)區(qū)域附近產(chǎn)生解的概率趨近于零.這明顯不符合條件2.因此無法保證算法收斂到局部極值.證畢.4.3算法與量子群模型由上面分析可以看出,當(dāng)xi=pi=pg時(shí),算法的速度更新僅僅依賴于αvi,j(t).因?yàn)棣?lt;1,當(dāng)vi,j(t)接近0的時(shí)候,粒子將靠近不是局部極值點(diǎn)的pgt而停止運(yùn)動.這也是算法不能收斂到局部極值點(diǎn)的原因?yàn)榱私鉀Q算法的這種問題,BerghF提出了通過改變最優(yōu)粒子位置更新方式為:其中:ρ(t)>0為時(shí)變常數(shù),r3(t)∈為隨機(jī)數(shù).并證明了該更新方式的SPSO算法(LocalSPSOLSPSO)滿足條件1和條件2,是局部最優(yōu)算法而不是全局最優(yōu)算法,參見文獻(xiàn).為了使SPSO算法具有全局尋優(yōu)能力,最簡單的辦法就是使其滿足條件3可以通過為群體增加隨機(jī)粒子來實(shí)現(xiàn).文獻(xiàn)提出了一種Multi-startPSO算法,迭代若干次后,保留粒子群的歷史最優(yōu)位置,粒子全部重新初始化,以擴(kuò)大搜索空間,保證收斂到全局最優(yōu).但是這種方式完全改變了粒子之間的結(jié)構(gòu)關(guān)系,使收斂速度降低.本文將根據(jù)粒子特性的不同進(jìn)行分群,對不同特性的粒子采用不同的位置更新策略,使算法既具有多極值尋優(yōu)能力,又能保證算法較快的收斂.首先給出關(guān)于量子群模型的定義.定定義3量子群模型,粒子群由“中性粒子”和“量子粒子”組成.粒子s到中心粒子p的距離d(s,p)R1的粒子為量子粒子;粒子s到中心粒子p的距離R1<d(s,p)R2的粒子為中性粒子.基于上述定義,首先將群體分成多個(gè)量子群.量子群的劃分根據(jù)如下方式:在每一次迭代過程中,對每個(gè)個(gè)體的適應(yīng)度從好到差進(jìn)行排序存儲在Ls.根據(jù)適應(yīng)度和位置關(guān)系將粒子分群,算法如圖1所示對于不同的粒子采用不同的更新策略,算法如圖2所示.由于增加了隨機(jī)粒子,采樣空間擴(kuò)大到整個(gè)搜索空間,算法滿足條件3.5計(jì)算測試成功為了驗(yàn)證本文算法,分別選擇單模態(tài)、多模態(tài)函數(shù)進(jìn)行測試,測試函數(shù)見附錄.本文使用MATLAB實(shí)現(xiàn)了上述算法.每個(gè)算例均隨機(jī)運(yùn)行20次,然后平均統(tǒng)計(jì)各項(xiàng)優(yōu)化性能指標(biāo):目標(biāo)函數(shù)評價(jià)次數(shù)(evals)、平均CPU時(shí)間(time)、平均誤差(err)以及優(yōu)化成功率(%).其中,在給定的迭代次數(shù)內(nèi)(文中num=10000),若搜索最終解與問題最優(yōu)解之間的關(guān)系滿足式(24),則認(rèn)為算法測試成功.其中:f*是目標(biāo)函數(shù)的全局最優(yōu)解;fα是算法搜索解;ε1和ε2是給定參數(shù)(文中ε1=ε2=10-4).首先利用單模態(tài)函數(shù)DeJong(n=4)來分析算法的穩(wěn)定性和收斂性.根據(jù)定理1和定理2的條件,選取多組參數(shù)進(jìn)行測試.圖3為在n=20,α=0.4,c1=2,c2=2情況下,不同采用時(shí)間的系統(tǒng)軌跡圖.從圖3可以看出當(dāng)T=1.4粒子軌跡發(fā)散.同時(shí),采樣時(shí)間越小,系統(tǒng)收斂速度越慢,同時(shí)易陷入“早熟”.采用時(shí)間越大,系統(tǒng)穩(wěn)定越慢,但粒子探索能力較強(qiáng).隨后,對LSPSO在α=0.4,c1=2,c2=2參數(shù)下,不同采用周期的穩(wěn)定和收斂性能進(jìn)行分析.圖4為LSPSO算法不同采樣周期的系統(tǒng)粒子軌跡.實(shí)驗(yàn)結(jié)果表明,LSPSO在不同的采樣周期下,都能收斂到局部最優(yōu)值.表1為SPSO、LSPSO和PSO在不同參數(shù)下的優(yōu)化性能比較.從表1可以看出,采樣周期粒子群算法(尤其是LSPSO)相對于傳統(tǒng)粒子群算法具有更大的參數(shù)穩(wěn)定性.最后,利用多模態(tài)函數(shù)f1測試Q-SPSO的多極值尋優(yōu)能力.圖5為測試函數(shù)的曲面圖,采用參數(shù)n=50,α=0.4,c1=2,c2=2,R1=0.2,R2=2.圖6為函數(shù)優(yōu)化過程中的粒子運(yùn)行軌跡,從圖6中可以看出,粒子能找到所有的局部極值點(diǎn)(實(shí)驗(yàn)的多次運(yùn)行結(jié)果一致).6算法性能的優(yōu)化本文提出一種變采樣周期的粒子群優(yōu)化模型,顯然,傳統(tǒng)的粒子群算法可以看作該模型的一種采樣周期形式.分析結(jié)果表明變采樣周期粒子群優(yōu)化算法主要有兩點(diǎn)好處,一是增強(qiáng)算法的參數(shù)適應(yīng)性,二是可以通過采樣周期的改變而改變算法的搜索能力.本文理論分析了算法的收斂特性,并給出了