動態多目標優化的時間變量區間劃分及進化算法

在計算機工程和電子通信等領域，有許多復雜的現實生活。其目標函數不僅與決策變量有關，而且隨著時間的推移而變化。因此，最佳解也隨著時間的推移而變化。這種優化問題通常被稱為動態優化問題（dynamicmoves，dynams）。動態優化問題是近年來發展與創新計算領域的一個新課題，引起了越來越多的研究人員的興趣。[4]。動態優化問題是近年來發展與創新計算領域的一個新課題，它主要分為動態單目標優化問題（sdops）和動態多目標優化問題（dynamic二維對象優化問題（sdops）。然而，當前的主要研究主要集中在sdops，對sdmps的科學研究較少，國際研究也很早就開始了。我們只能看到很少的理論。很少有研究發表基于時間變量的動態優化問題，但其解決方案很少。在此基礎上，本文提出了一種新的模型和動態優化問題的新算法和發展算法（失真算法）。主要，動態多目標優化問題是隨著時間的推移而發生的。同時，在每個初始區域中指定靜態序值和靜態密度的偏差，然后將任意動態多目標優化問題轉換為動態多目標優化問題。在該模型框架下，提供了另一個新的進化算法（vmga），以證明該算法的收斂性。為了將問題的時間緩慢變化，算法是有效的。為了獲得的特定時間的隨機解稱為動態多目標優化問題，以便在時間上最大限度地實現。為了消除惡意時間的變化，本文提供了一種自我分析的算子。計算機模擬結果表明，當動態多目標優化問題隨著時間的推移而變化時，分布均勻、最大的pare頭是最好的。1最優性條件的確定考慮下列動態多目標優化問題I:minx∈Ω(t)?[L,U]tf(x,t)=(f1(x,t),f2(x,t),?,fΜ(x,t))s.t.gi(x,t)≤0?i=1,2,?,p?(1)其中,t∈[a,b]?R1是時間變量,決策向量x=(x1,x2,…,xn)是Rn空間的n維向量,gi(x,t)(i=1,…,p)是依賴時間t的約束條件,fi(x,t)(i=1,…,M)為依賴時間t的動態子目標函數,由約束條件確定的解集Ω(t)={x|gi(x,t)≤0,i=1,…,p}稱為問題I的可行域,[L,U]t={x(t)=(x1,x2,…,xn)|li(t)≤xi≤ui(t),i=1,…,n}稱為其搜索空間.定義1.非劣性.一個向量ut=(u1,u2,…,uM)稱為非劣于向量vt=(v1,v2,…,vM),當且僅當對于?i∈{1,2,…,M},有ui≤vi∧?i∈{1,2,…,M}使得ui<vi.定義2.一個解xut∈Ω(t)稱為時刻t時動態多目標優化問題I的Pareto最優解,當且僅當不存在xvt∈Ω(t),使得vt=f(xvt,t)非劣于ut=f(xut,t).2將多目標動態優化問題轉換為兩個目標靜態優化問題ii2.1ti1ti對動態多目標優化問題I,在時間變量區間[a,b]中任意插入n-1個分點a=t0<t1<t2<…<tn-1<tn=b,把區間[a,b]分成任意n個時間小區間[ti-1,ti],i=1,…,n,即[a,b]=n∪i=1[ti-1,ti],記Δti=ti-ti-1(i=1,…,n),在每個小區間Δti上任取時刻ξi,當Δti充分小時,我們把定義在每個小區間[ti-1,ti]上的動態多目標優化問題近似為時刻ξi上的靜態多目標優化問題.若分點的個數無限增加時,不妨記λ=max{Δt1,Δt2,…,Δtn},當λ→0時,則原來隨時間連續變化的動態多目標優化問題I的Pareto最優解可以近似地看做是若干個時刻ξi上的靜態多目標優化問題的Pareto最優解的疊加.2.2[a,b]t的質量度量對優化問題I,在時間變量區間[a,b]得到上述第2.1節的任意一個劃分假設下,設時刻ξi∈Δti對應的第k代種群pk(ξi)由N個個體xk1(ξi),xk2(ξi),xkΝ(ξi)構成,nkl(ξi)是該種群中非劣于個體nkl(ξi)的所有個體的個數,則稱1+nkl(ξi)為個體nkl(ξi)(l=1,…,N)處于時刻ξi時的序值,記作nkl(ξi).另外,若設種群pk(ξi)中所有個體序值的平均值ˉr(ξi)=1ΝΝ∑l=1nkl(ξi),則當Δti充分小時,我們近似地把r(ξi)=1ΝΝ∑l=1(ˉr(ξi)-rkl(ξi))2定義為時刻ξi時第k代種群在時間小區間Δti上的靜態序值方差.進一步,記λ=max{Δt1,Δt2,…,Δtn},則無論對時間區間[a,b]如何劃分,也無論在區間Δti上對點ξi怎樣選取,當λ→0時,定義n∪i=1r(ξi)為時間區間[a,b]上所得種群的期望序值方差,記作Et∈[a,b](r(t)).從Et∈[a,b](r(t))的定義可以看出,其值越趨于零所得問題解的質量越好.因此,Et∈[a,b](r(t))可以作為求得問題I的Pareto解的質量度量.2.3ui,[l]對優化問題I,在時間變量區間[a,b]得到上述第2.1節的任意一個劃分假設下,設時刻ξi∈Δti對應的第k代種群pk(ξi)由N個個體xk1(ξi),xk2(ξi),…,xkΝ(ξi)構成,且其對應目標空間中解向量分別為Uk1(ξi),Uk2(ξi),…,UkΝ(ξi),在時刻ξi,取目標空間中M個參考點UkΝ+1(ξi),UkΝ+2(ξi),…,UkΝ+Μ(ξi),不妨設UkΝ+τ(ξi)(τ=1,…,M)的向量坐標為(uτ1,uτ2,…,uτi,…,uτΜ),則當i=τ=s(i,s=1,…,M)時,uτi=minx∈[L,U]tfs(x,t);當i≠τ=s時,uτi=maxx∈[L,U]tfs(x,t).另設Dkl(ξi)l∈{1,2,…,(N+M)}=min{‖Ukl(ξi),Ukl(ξi))‖2,j≠l,j=1～(N+M)},則ˉD(ξi)=1Ν+ΜΝ+Μ∑l=1Dlk(ξi)表示時刻ξi下第k代種群對應目標空間中解向量分布的平均距離.對于任意解向量Ulk(ξi)(l=1,…,N),稱|mlk(ξi)|為其在時刻ξi下的第k代種群對應于搜索空間中個體xlk(ξi)的密度,不妨記作ρkl(ξi),這里,mlk(ξi)={j|∥Ujk(ξi)-Ulk(ξi)∥p≤Dˉlk(ξi),j=1,2,?,l-1,l+1,?,Ν+Μ},若記pˉk(ξi)=1Ν∑l=1Νplk(ξi),則當Δti充分小時,定義ρ(ξi)=1Ν∑l=1Ν(pˉk(ξi)-ρlk(ξi))2為時刻ξi下的第k代種群在Δti上對應目標空間中解的靜態密度分布方差.記λ=max{Δt1,Δt2,…,Δtn},無論對時間區間[a,b]如何劃分,也無論在區間Δti上對點ξi怎樣選取,當λ→0時,定義∪i=1nρ(ξi)為時間區間[a,b]上所得種群對應于目標空間中解的期望密度方差,記作Et∈[a,b](ρ(t)).從Et∈[a,b](ρ(t))的定義可知,其值越趨于零表示所得問題I的Pareto解的均勻性越好,因此,Et∈[a,b](ρ(t))可以作為求得問題I的Pareto解的均勻性的度量.2.4模型的極限化從以上兩種度量可以看出,如果將上述兩種度量看成是兩個要優化的目標函數,則優化問題I可以近似地轉化為下列雙目標極小化問題II.min{Et∈[a,b](r(t)),Et∈[a,b](ρ(t))}.(2)對于雙目標優化模型II,由于兩個目標函數Et∈[a,b](r(t)),Et∈[a,b](ρ(t))分別表示時間區間[a,b]上所得種群的期望序值方差和對應于目標空間中解的期望密度分布方差,因此,對模型II的極小化,實質上是對[a,b]實區間上連續分布的時刻點處所得種群的序值方差及種群對應的目標空間中解的密度分布方差構成的一族雙目標極小化問題的Pareto解的疊加.在固定時刻ξi,設問題II的有效解集為Eξi(f,x),弱有效解集為Ewξi(f,x),則優化問題I與II的解有如下關系成立:定理1.E*(ξi)是優化問題I在時刻ξi下有效解集的充要條件是E*(ξi)?Ω(ξi)∩Ewξi(f,x),且對于E*(ξi),r(ξi)→0.證明.充分性:顯然成立.必要性:由于E*(ξi)是問題I在時刻ξi下的有效解集,故E*(ξi)?Ω(ξi),且E*(ξi)中每個解的序值應達到最小1,因此,種群pk(ξi)的序值方差r(ξi)達到最小,即r(ξi)→0.故E*(ξi)中每個解也是問題II的解,即E*(ξi)?Ω(ξi)∩Ewξi(f,x),故必要性成立.3新的多目標優化算法3.1算法的基本思想解動態優化問題的關鍵是在時間發生改變的情況下,如何使算法自動跟蹤環境的改變而繼續尋找新的Pareto最優解.下面我們給出一種自適應時間變化自檢算子:ε(t)=∑i=1Ν∥f(xi,t)-f(xi,t-1)∥pΝ∥R(t)-U(t)∥p?(3)這里,R(t)=(maxx∈[L,U]tfi(x,t))1×Μ?U(t)=(minx∈[L,U]tfi(x,t))1×Μ(i=1???Μ)分別表示時刻t時對應問題的搜索空間[L,U]t中的最差解和最好解,xi(i=1,…,N)是時刻t-1時用于測試時間發生變化的N個個體,如果ε(t)>η(η是給定的閾值),此時我們認為時間已發生改變,這時用式(3)引導算法重新進入下一個新的時刻.3.2添加其他衍生物的種群共—動態多目標優化進化算法(DMGA)流程Step1.對問題I的時間變量區間[a,b]按照第2.1節的方式進行任意劃分,不妨設所得一個劃分為a=t0<t1<…<tn-1<tn=b,同時記t=t0,…,tn為所得的一些連續分布時刻點,令t=t0.Step2.時刻ti(i=0,1,…,n)下,在搜索空間[L,U]ti上隨機產生規模為N的初始種群p0(ti),同時把p0(ti)中序值為1的個體存入一個臨時解集q0(ti),令k=0.Step3.據雜交概率pc隨機從第k代種群pk(ti)∪Sf(ti-1)(Sf(ti-1)表示時刻ti-1所得問題的Pareto最優解集)中選雜交的父代對(xkl(ti),xjk(ti))執行算術雜交產生其后代,沒有參與雜交的父代看成自己的后代,所有后代的集合記為ok(ti).Step4.對Step3產生的每個后代τk(ti),對其第s個分量τs變異如下:將搜索空間[L,U]ti中第s維子空間[ls,us]分成若干個子區間[ω1s,ω2s],[ω2s,ω3s],…,[ωns-1s,ωnss],使得|ωjs-ωj-1s|<s,其中j=2,…,ns,ω1s=ls,ωnss=us.隨機產生一個數rs∈,若rs≤pm,s=1,2,…,n,則隨機在{ω1s,…,ωn[JX-*3]s[JX*3]s}中選一個數ωj[JX-*3]s[JX*3]s代替τs,否則τs保持不變,這樣經變異后τk(ti)變為τˉk(ti),ok(ti)變為oˉk(ti).Step5.對oˉk(ti)中的所有個體xlk(ti)按其密度|mlk(ti)|值依次分配到C1,C2兩個解集,其中:C1={xlk(ti)‖mlk(ti)|=0,l=1,…,N‖},C2={xlk(ti)‖mlk(ti)>0,j=1,…,N‖},對C2中的每個個體在C1中隨機產生一個個體與其配對,采用啟發式進行雜交,把雜交產生的所有后代(共|C1|個)作為一個過渡子種群φk(ti),對φk(ti)中的每個個體以概率pc按Step4的方式進行變異,用變異后的個體代替其父代,這樣經變異后φk(ti)變為sk(ti),同時把C1中的個體直接復制到sk(ti)中生成新的種群sˉk(ti).Step6.用pk(ti)∪sˉk(ti)∪oˉk(ti)中序值等于1的個體替換qk(ti)中序值為1的個體生成新的臨時解集qk+1(ti).Step7.對pk(ti)∪sˉk(ti)∪oˉk(ti)∪qk+1(ti)中的個體按其適應度Fj(ti)=1+rjk(ti)(rjk(ti)表示時刻ti下第j個個體xjk(ti)的序值)的值由大到小依次選出N個個體組成時刻ti的下一代種群pk+1(ti).Step8.計算ε(ti),當ε(ti)>η(η是給定的閾值),令ti=ti+1,轉Step2,否則令k=k+1.轉Step3.4個多目標進化算法事實上,從以上可知,對動態多目標優化問題I,在時間變量區間[a,b]得到第2.1節的任意一個劃分假設下,我們把其近似地轉化成實區間[a,b]上連續分布的時刻點處所得種群的序值方差和對應于目標空間中解的密度分布方差構成的一族雙目標極小化問題的Pareto解的疊加,同時在時間變化自檢算子的作用下,算法從一個時刻自動進入下一新的時刻執行新的搜索,因此,對算法的收斂性,只需要討論在[a,b]區間上給定的任意時刻t下收斂.定義3.在時刻t,稱個體x′是從x通過雜交和變異可達的,如果Prob{MC(x)=x′}>0.MC(x)表示由x通過雜交和變異產生的點,Prob{·}表示隨機事件{·}的概率.定義4.在時刻t,若Prob{‖MC(x)-x′‖∞≤ε}>0,則稱個體x′是從x通過雜交和變異為ε-精度可達的.引理1.Veldhuizen已經證明,若一個多目標進化算法(MOEA)滿足下面兩個條件,則該MOEA以概率1收斂到全局最優解集.1)可行域中任意兩點x′和x,x′是從x通過雜交和變異可達.2)種群序列p0,p1,…,pk,…是單調的,即對?k,pk+1中的任意解非劣于pk中的任意解或至少不差于pk中的任意解.若將引理1中的第1個條件“可達”改為“ε-精度可達”,則與文獻第2章中定理4(第23-24頁)的證明完全一樣可證明MOEA以概率1收斂到問題的具有ε-精度最優解集.定理2.在時刻t,對充分小的?ε>0,若問題I的目標函數f(x,t)在搜索空間[L,U]t上連續,則本文算法DMGA以概率1收斂到問題I的具有ε-精度最優解集,即Ρrob{limk→∞∥pk(t)-ptrue(t)∥∞≤ε}=1.(4)‖pk(t)-ptrue(t)‖∞≤ε表示{‖x-x*‖∞≤ε|?x∈pk(t),?x*∈ptrue(t)},ptrue(t)為動態多目標優化問題I在時刻t下的Pareto最優解集.證明.首先證明在時刻t下,算法DMGA對任意兩點x′和x,x′是從x通過DMGA中的雜交和變異為ε-精度可達,即Ρrob{∥ΜC(x)-x′∥∞≤ε}>0?(5)其中,MC(x)是x通過雜交和變異算子產生的點.事實上,設xˉ是x通過雜交算子產生的任意點,即C(x)=xˉ,則只須證x′是xˉ通過變異算子為ε-精度可達,即Ρrob{∥Μ(xˉ)-x′∥∞≤ε}>0(6)成立.事實上,由算法的Step4可知,對x′的任一個分量x′s(s=1,…,n),若記|ωiss-x′s|=min{|ωjs-x′s|,j=1,…,n},則一定有不等式|ωiss-x′s|≤s成立,其中各ωjs由算法Step4給出的變異算子確定,記xˉ=(ωi1s,ωi2s,?,ωins),則∥x～-x′∥∞≤ε,因此,若能證明Ρrob{Μ(xˉ)=x～}>0,則Ρrob{∥Μ(xˉ)=x～∥∞≤ε}>0成立,設Μ(xˉ)和x～的Hamming距離為h,即Μ(xˉ)和x～的不同分量的個數為h,不失一般性,設Μ(xˉ)和x～的后n-h個分量相同,于是有Ρrob{Μ(xˉ)=x′}=(pmh∏i=1h1ni)[(1-pm)n-h∏j=h+1n(1-1nj)]＞0?(7)從而Ρrob{∥Μ(xˉ)=x～∥∞≤ε}>0,故由定義4知,x′是從x通過DMGA中的雜交和變異為ε-精度可達;另由算法DMGA的Step7可知,在時刻t,DMGA產生的種群序列?k,pk+1(t)中的任意解非劣于pk(t)中的解,或改進了pk(t)中的解(至少不劣于pk(t)中的解),因此,在固定時刻t,DMGA以概率1收斂到問題I具有ε-精度的最優解集.5實驗模擬與分析5.1不同發展程度的t本文選用4個動態多目標測試函數對算法性能進行測試,其中G1是采用文獻中SCH函數構造的,G2選自文獻,G3,G4選自文獻,且G3,G4是由具有形式定義minf(x,t)=(f1(x1,t),g(x,t)·h(f1(x1,t),g(x,t),t))的函數構成.G1:{minf(x,t)=(f1(x,t),f2(x,t)),s.t.f1(x,t)=t?x2;f2(x,t)=(1-t)?x2;x∈;t∈.G2:{minf(x,t)=(f1(x,t),f2(x,t)),s.t.f1(x,t)=t?(x12+(x2-1)2)+(1-t)?(x12+(x2+1)2+1),f2(x,t)=t?(x12+(x2-1)2)+(1-t)?((x1-1)2+x22+2),x∈;t∈.G3:{f1(x,t)=x1;g(x)=1+∑i=2n(xi-sin(0.5πt))2?h(f1,g)=1-f1?g;t=1nt-ττΤ-?n=20;x1∈;xi∈[-1,1];i=1,2,?,n?τΤ=5;nt=10.G4:{f1(x,t)=∑i=1mxiΗ(t);g(x,t)=1+G(t)+∑j=1n(xj-G(t))2,h(f1,g,t)=1-f1g;G(t)=|sin(0.5πt)|,Η(t)=10(2sin(0.5πt));t=1nt-ττΤ-;m=5;n=25;nt=10,τΤ=5;xi∈;i=2,3,?,n;xj∈[-1,1];j=2,3,?,n.5.2算法有效性驗證記本文算法為DMGA,用于比較的3種算法分別為DFGA,DCGA和DSGA,其中DFGA是作者Iason,David在文獻中基于向前預測估計技術給出的一種解DMOPs的方法,該方法對DMOPs處于下一環境的Pareto解按某種概率分布進行估計,其估計的結果會使求解的誤差較大.DCGA和DSGA兩種算法對問題的環境變化處在離散時間空間時的情形求解較為有效,對時間連續緩慢變化的DMOPs求解顯得精度不高,所得Pareto解在目標空間中的質量、均勻性較差.另外,基于文中采用的4個測試函數的時間變量均為連續實值區間,當時間變化時,難以對所求得問題的Pareto最優解進行表示,因此,在新模型II下,我們對給定動態多目標優化問題時間區間進行極細分割并取定一些時刻點(分別見圖例t中的取值)來對DMGA算法的有效性進行驗證.同時將本文算法DMGA對G1,…,G4分別求得的Pareto前沿面與文獻中算法的結果進行了對比.在計算中參數選取如下,對每個測試函數,算法