論文演化算法的收斂性分析及算法改進(jìn)

《論文演化算法的收斂性分析及算法改進(jìn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、演化算法的收斂性分析及算法改進(jìn)覃俊%，!康立山%陳毓屏%%（武漢大學(xué)軟件工程國家重點(diǎn)實(shí)驗(yàn)室，武漢I#""J!）!（中南民族大學(xué)計(jì)科院，武漢I#""JI）5>1*0)：K8LMNLOD(31*0)$B(1摘要文章利用馬爾可夫隨機(jī)過程刻畫了演化算法，證明了標(biāo)準(zhǔn)演化算法是不收斂的，說明了演化算法收斂于最優(yōu)解的必要條件：非完全遍歷性。并論證了采取精華保留策略的標(biāo)準(zhǔn)遺傳算法以概率%收斂于最優(yōu)解，并據(jù)此分析了一個(gè)典型實(shí)例——CPC<算法的收斂性及其算法改進(jìn)方案。關(guān)鍵詞遺傳算法收斂性精華策略文章編號(hào)%""!>Q##

2、%>（!""#）%&>""&%>"!文獻(xiàn)標(biāo)識(shí)碼<中圖分類號(hào)PR#"%$S!"#$%&’#()#&*#+&,-./0/,&1+-)%(02"3435(%’#3#&2%6$%3572,20%&+-)%(02"380&97&:，;<,&)=0/",&:$"#&>750&):%（PD4/3*34T49U*V(8*3(89(W/(W3K*845+=0+4480+=，X2D*+Y+0648A039，X2D*+I#""J!）!（/(23D:4+348Y+0648A039W(8Z*30(+*)0304A，X2D*+I

3、#""JI）+?/2(,*2：PD4B(1;23*30(+*)=(803D10A604K4,K03D*1*8?(6BD*0+$[30A34A30W04,3D*33D4B)*AA0BB(1;23*30(+*)=(7803D10A+(3B(+648=4,3((;301*)84A()230(+2+30)*+4)030A3A38*34=90A2A4,$@(84(648，*W*1(2AB(1;23*30(+*)=(803D10AA32,04,$<#.@%(1/：:(1;23*30(+*)=(803D1，:(+6

4、48=4+B4，5)030A3A38*34=9%引言隨機(jī)生成一個(gè)初始群體演化算法的理論分析主要集中在三個(gè)方面：一方面是由確定每一個(gè)體適應(yīng)值按比例選擇機(jī)制進(jìn)行選擇挑出父體’())*+,提出的模式定理，并在其基礎(chǔ)上導(dǎo)出的隱含并行定理，84;4*3這些理論是從基因空間（編碼空間）這一較低層的角度去抽象以概率!"雜交算法。第二個(gè)方面是基于偏序關(guān)系的理論在偏序空間分析了演以概率!#變異化算法的收斂性，文獻(xiàn)-%.利用偏序集的一些結(jié)論導(dǎo)出了隱含并計(jì)算個(gè)體適應(yīng)值行性的定量分析。這兩種方法雖然定量地估算出了具有較優(yōu)結(jié)按

5、比例選擇機(jī)制進(jìn)行選擇挑出父體構(gòu)特點(diǎn)的模式在進(jìn)化過程中的增長規(guī)律以及并行性度量，但未2+30)終止條件能導(dǎo)出遺法算法能夠收斂于問題最優(yōu)解的概率。還有許多學(xué)者其中算法的比例選擇是指按適應(yīng)值高低比例選取父體。越從其它方面去刻畫演化算法，如模擬演化算法（/012)*34,56(7好的個(gè)體（這里指適應(yīng)值越?。┍贿x中的概率越大。)230(+*89:(1;23*30(+）模型，類模擬退火（/012)*34,<++4*)0+=>從算法易見，:C<的選擇、雜交和變異算子都是獨(dú)立隨機(jī))0?4）方法等。還有學(xué)者結(jié)合具體的應(yīng)

6、用來分析演化算法，如適進(jìn)行的，新群體僅與其父代群體及遺傳算子有關(guān)，而與其父代應(yīng)值地圖，最優(yōu)控制理論，小生境技術(shù)等，從不同角度刻畫了演群體之前的各代群體無關(guān)，即滿足后無效性，并且各代群體之化算法，對(duì)算法的設(shè)計(jì)、分析和應(yīng)用都有一定意義。但對(duì)算法收間的轉(zhuǎn)換概率與時(shí)間起點(diǎn)無關(guān)，即:C<構(gòu)成的@*8?(6鏈?zhǔn)菚r(shí)斂性分析未能給出較一般的框架-#.。齊的。該文試圖基于馬爾可夫隨機(jī)過程這個(gè)較高層的角度去刻!$%（#，#&%）E!F’（#G%）E%(’（#）)$H)!$%畫演化算法。如果把演化算法進(jìn)化過程中的每一代群體

7、看作為其中$，%!*為狀態(tài)，#為起始時(shí)刻。并且初始分布對(duì)一種狀態(tài)的話，則可以把整個(gè)進(jìn)化過程作為一個(gè)隨機(jī)過程來考@*8?(6鏈極限行為無影響，所以初始群體分布可任意。查，并可利用@*8?(6鏈來對(duì)進(jìn)化過程進(jìn)行收斂性分析。-結(jié)論%.：基本遺傳算法收斂于最優(yōu)解的概率小于%。證明將群體的各種可能狀態(tài)*分為包括最優(yōu)個(gè)體的狀態(tài)!標(biāo)準(zhǔn)演化算法描述及其收斂性分析*"和不包括最優(yōu)個(gè)體的狀態(tài)*+；*)*""*+（*"#*+E!）。要證明!%進(jìn)標(biāo)準(zhǔn)演化算法（:)*AA0BC4+430B<)=(803D1，簡(jiǎn)稱:C<）求解入

8、*"狀態(tài)的穩(wěn)定概率小于%。此類優(yōu)化問題的算法框架描述如下：用反證法。假設(shè)基本遺傳算法能收斂于最優(yōu)解的概率等于基金項(xiàng)目：國家自然科學(xué)基金（編號(hào)：S&S#"#"，S""J#"I#，J""J%"I!）作者簡(jiǎn)介：覃俊（%&SQ>），女，副教授，在職博士生，主要研究領(lǐng)域：遺傳算法，電子商務(wù)，數(shù)據(jù)庫與T]]。計(jì)算機(jī)工程與應(yīng)用!""#$%&&%%，則進(jìn)入!"狀態(tài)的穩(wěn)定概率應(yīng)等于"，即：部最優(yōu)，要么所找的多目標(biāo)優(yōu)化解不完全（H15IJ7解集中在某’()$+$#"!",