遺傳算法案例分析

遺傳算法案例分析利用遺傳算法，求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。分析：原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最小值的點x的問題。那么，［0,31］中的點x就是個體，函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(解)空間。這樣，只要能給出個體x的適當(dāng)染色體編碼，該問題就可以用遺傳算法來解決。二次函數(shù)的圖像如圖所示。二次函數(shù)y二次函數(shù)y=x2的圖像設(shè)定種群規(guī)模，編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個體組成初始種群S:1S=S=13(01101)，s=8(01000)，S=24(11000)s=19(10011)定義適應(yīng)度函數(shù)。取適應(yīng)度函數(shù)：f(x)=x2。計算各代種群中的各個體的適應(yīng)度，并對其染色體進(jìn)行遺傳操作，直到適應(yīng)度最高的個體(即31(11111))出現(xiàn)為止。首先計算種群S中各個體的適應(yīng)度f(s)。容易求得，112f(s)=f(13)=13=16912f(s)=f(24)=24=57622f(s)=f(8)=8=6432f(s)=f(19)=19=3614再計算種群S中各個體的選擇概率。選擇概率的計算公式為1P(x)=f(xi)'kf(xJ)j=1由此求得，P(s)=P(13)=0.141P(s)=P(24)=0.492P(s)=P(8)=0.063P(s)=P(19)=0.314用賭輪選擇法可得，

設(shè)從區(qū)間［0,1］中產(chǎn)生4個隨機數(shù)如下:r=0.450126,1r=0.572496,3r=0.1103472r=0.985034第一代選中次數(shù)表染色體適應(yīng)設(shè)從區(qū)間［0,1］中產(chǎn)生4個隨機數(shù)如下:r=0.450126,1r=0.572496,3r=0.1103472r=0.985034第一代選中次數(shù)表染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.3111表1于是，經(jīng)復(fù)制得群體:s’=11000(24),s’=01101(13)TOC\o"1-5"\h\z12s’=11000(24),s’=10011(19)\o"CurrentDocument"34設(shè)交叉率p=100%,即S中的全體染色體都參加交叉運算。設(shè)s’與s’配對，c112s’與s’配對。分別交換后兩位基因，得新染色體：s’=11001(25),s’=01100(12)s’=11011(27),s’=10000(16)34設(shè)變異率p=0.001。這樣，群體S中共有5X4X0.001=0.02位基因可以變異。m10.02位顯然不足1位，所以本輪遺傳操作不做變異。于是，得到第二代種群S:2s=11001(25),s=01100(12)TOC\o"1-5"\h\z12s=11011(27),s=10000(16)34表2第二代選中次數(shù)表染色體適應(yīng)度選擇概率積累概率估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.1511TOC\o"1-5"\h\z假設(shè)這一輪選擇-復(fù)制操作中，種群s2中的4個染色體都被選中，則得到群體:s’=11001(25)，s’=01100(12)12s’=11011(27)，s’=10000(16)\o"CurrentDocument"34做交叉運算，讓s’與s’，s’與s’分別交換后三位基因，得1234s’’=11100(28)，s’’=01001(9)12s’’=11000(24)，s’’=10011(19)34這一輪仍然不會發(fā)生變異。于是，得第三代種群S3：s1=11100(28)，s2=01001(9)s3=11000(24)，s4=10011(19)表3第三代選中次數(shù)

染色體適應(yīng)度選擇概率積累概率估計的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.81s4=100113610.211設(shè)這一輪的選擇-復(fù)制結(jié)果為:s'=11100(28),s'=11100(28)TOC\o"1-5"\h\z12s'=11000(24),s'=10011(19)\o"CurrentDocument"34'與s'分別交換后兩位基因，得3s'=11100（28）2s'=10000（16）4做交叉運算，讓s‘與s',s142s'=11111（31），1s'與s'分別交換后兩位基因，得3s'=11100（28）2s'=10000（16）4這一輪仍然不會發(fā)生變異。于是，得第四代種群s4：s1=11111（31），s2=11100（28）s3=11000（24），s4=10000（16）顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最