單變量邊緣分布算法與蟻群算法的混合算法收斂性分析(編輯修改稿)
2024-08-31 13:46 本頁面
【文章內(nèi)容簡介】 算法的優(yōu)化解序列{x(n)。n≥0}是有限狀態(tài)的齊次馬爾科夫鏈。引理4［8］杰出者遺傳算法的馬爾科夫鏈序列的優(yōu)化解滿意值序列是單調(diào)不增的，即：f(x(n))≥f(x(n+1)),n≥0。定理3umda算法的馬爾科夫鏈序列的優(yōu)化解滿意值序列是單調(diào)不增的，即對于任意的n≥0，有f(x(n))≥f(x(n+1))。證明xn(n+1)=xi0(n)，其中i0=argminj{f(xj(n))}。則f(x(n))≥f(xn(n+1))≥f(x(n+1))。定理4umdaaa算法的馬爾科夫鏈序列的優(yōu)化解滿意值序列是單調(diào)不增的，即對于任意的n≥0，有f(x(n))≥f(x(n+1))。證明：由定理3，i0=argminj{f(xj(n))}，則有xn(n+1)=xi0(n)，f(x(n))≥f(xn(n+1))≥f(x(n+1))。又由于算法采用了螞蟻圈的算法，i0=argminj{f(xj(n))}，同樣有xn(m+1)=xi0(m)，f(x(m))≥f(xn(m+1))≥f(x(m+1))。而螞蟻圈算法是以umda算法的結(jié)果為初始分布，具有優(yōu)值繼承性，因此對于任意的n≥0，有f(x(n))≥f(x(n+1))。即umdaaa算法的馬爾科夫鏈序列的優(yōu)化解滿意值序列是單調(diào)不增的。引理5［8］杰出者遺傳算法種群馬爾科夫鏈序列{x(n)。n≥0}由概率1收斂到滿意種群集m*的子集m*0定理5umda算法種群馬爾科夫鏈序列{x(n)。n≥0}由概率1收斂到滿意種群集m*的子集m*0m*0={y=(y1,y2,…，yn)。yn∈m}即：limn→∞ p{x(n)∈m*0|x(0)=x0}=1證明：對于任意x,y∈sn,有：p(n,n+1,x,yi)=∑y1,y2,zp{ts(x(n))=y1,y2)}p{tm(y1,y2)=z}p{tsa(z)=yi}式中：yi=(x1,…，xi－1,yi,xi+1,…,xn)。而當(dāng)y≠yi(i≤n)時(shí)p{n,n+1,x,y}=0,于是{x(n)。n≥0}是非時(shí)齊的馬爾科夫鏈，記為：p∞(x,y)=limn→∞ p{n,n+1,x,y}。那么有：p∞(x,y)0,x∈m*,y∈m*0,因此p(∞)=(p∞(x,y)。x,y∈sn)具有惟一的不可約非周期常返類m*。而sn
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1