遺傳算法之我見

《遺傳算法之我見》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、隨機(jī)化均勻設(shè)計(jì)遺傳算法摘要：眾所周知，遺傳算法的運(yùn)行機(jī)理及特點(diǎn)是具有定向制導(dǎo)的隨機(jī)搜索技術(shù)，其定向制導(dǎo)的原則是：導(dǎo)向以高適應(yīng)度模式為祖先的“家族”方向．以此結(jié)論為基礎(chǔ)．利用隨機(jī)化均勻設(shè)計(jì)的理論和方法，對(duì)遺傳算法中的交叉操作進(jìn)行了重新設(shè)計(jì)，給出了一個(gè)新的GA算法，稱之為隨機(jī)化均勻設(shè)計(jì)遺傳算法．最后將隨機(jī)化均勻設(shè)計(jì)遺傳算法應(yīng)用于求解函數(shù)優(yōu)化問題，并與簡(jiǎn)單遺傳算法和佳點(diǎn)集遺傳算法進(jìn)行比較．通過模擬比較，可以看出新的算法不但提高了算法的速度和精度，而且避免了其它方法常有的早期收斂現(xiàn)象。關(guān)鍵詞：遺傳算法(GA)佳點(diǎn)集理論佳點(diǎn)集遺傳算法(GGA)隨機(jī)化均勻設(shè)計(jì)(RUD)隨機(jī)化均勻

2、設(shè)計(jì)遺傳算引言20世紀(jì)60年代，美國(guó)Michigan大學(xué)的JohnHolland教授提出了模擬生物進(jìn)化的仿生智能算法，即遺傳算法(GeneticAlgorithms，GA)．其基本原理是模仿生物在進(jìn)化過程中，通過選擇淘汰基因突變和遺傳等方式產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良個(gè)體．遺傳算法以其簡(jiǎn)單易行性和可靠性，在組合優(yōu)化問題，機(jī)器學(xué)習(xí)問題，圖像處理與模式識(shí)別，通信網(wǎng)絡(luò)設(shè)計(jì)等很多領(lǐng)域取得了廣泛的應(yīng)用．遺傳算法通過適當(dāng)?shù)木幋a方式把實(shí)際問題轉(zhuǎn)化成生物種群的進(jìn)化問題，經(jīng)過多代的選擇，變異，交叉操作最終得到可接受的問題的解．算法中“選擇，變異，交叉”等操作直接關(guān)系遺傳算法的效率，一直是遺傳

3、算法的研究熱點(diǎn)．文獻(xiàn)[1]根據(jù)算法初期需要采用較大的交叉，變異概率來產(chǎn)生更多的新優(yōu)秀個(gè)體；算法后期，則需采用較小的交叉，變異概率來保護(hù)優(yōu)良模式，使算法盡快收斂．提出了自適應(yīng)遺傳算法，由條件發(fā)生器來自適應(yīng)調(diào)整交叉變異概率，提高算法的效率．文獻(xiàn)[2]為了改善遺傳搜索性能，通過分析基因池遺傳算法的無限種群動(dòng)力系統(tǒng)，刻畫了雙峰函數(shù)局部極值解的適值差與系統(tǒng)不動(dòng)點(diǎn)之間的解析關(guān)系，提出了針對(duì)多模態(tài)優(yōu)化問題的兩階段遺傳算法．文獻(xiàn)[3]提出了一種結(jié)合模擬退火，最優(yōu)個(gè)體遷移以及參數(shù)空間動(dòng)態(tài)退化的混合遺傳算法，來加快算法的收斂和提高搜索全局最優(yōu)值的能力．文獻(xiàn)[4]提出了量子遺傳算法，在量子

4、個(gè)體上實(shí)施量子雜交，這一操作有利于保留相對(duì)較好的基因段，并且為了加快算法的收斂速度，還引入了兩階段局部搜索.文獻(xiàn)[5]指出遺傳算法的本質(zhì)是一個(gè)具有定向制導(dǎo)的隨機(jī)搜索技術(shù)，其定向制導(dǎo)的原則是：導(dǎo)向以高適應(yīng)度模式為祖先的“家族”方向．而在高適應(yīng)度模式為祖先的“家族”中尋找更高的適應(yīng)度模式主要靠交叉操作來實(shí)現(xiàn)．1.遺傳算法交叉操作分析通常GA算法中的交叉操作，是按賭輪法隨機(jī)取兩個(gè)染色體進(jìn)行單點(diǎn)交叉操作(或多點(diǎn)交叉)，其子孫必屬于父輩模式中，所以GA算法中的交叉操作即在以高適應(yīng)度模式為祖先的“家族”中取一點(diǎn)作為交叉后的后代．這種取法當(dāng)然有其片面性，并不能保證取到的后代的適應(yīng)度

5、比母體的高．由數(shù)論方法知：在高適應(yīng)度模式空間中產(chǎn)生的均勻散布點(diǎn)集，它們的平均適應(yīng)度能代表高適應(yīng)度模式空間的平均適應(yīng)度．也就是說，這些點(diǎn)能很好的代表高適應(yīng)度模式空間的其他點(diǎn)，即要求此空間中的最優(yōu)值，只要在這些點(diǎn)中找即可．故有研究者提出在以高適應(yīng)度模式為祖先的“家族”中利用正交試驗(yàn)的方法求出幾點(diǎn)來作為交叉后的后代，這是一個(gè)好主意，不過當(dāng)因素的個(gè)數(shù)和等級(jí)增多時(shí)，不但試驗(yàn)的規(guī)模迅速增加，而且對(duì)應(yīng)的試驗(yàn)正交表也很難得到，這些問題給正交交叉法的運(yùn)用帶來一定的困難．張鈴提出了佳點(diǎn)集遺傳算法，即利用數(shù)論中的佳點(diǎn)集方法求出幾點(diǎn)來作為交叉后的后代，這可使其精度與維數(shù)無關(guān)，且這些點(diǎn)有很好的

6、散布性，克服了用正交設(shè)計(jì)法的不足．但是，佳點(diǎn)集的選取在n取定后是確定的，且佳點(diǎn)集分布點(diǎn)有方向性，不帶隨機(jī)性，所以很多格子是取不到的，其上的點(diǎn)也就不能作為交叉后的后代了，這將影響算法的整體搜索效果．為了克服上述不足，本文提出了隨機(jī)化均勻設(shè)計(jì)遺傳算法，利用隨機(jī)化均勻設(shè)計(jì)來設(shè)計(jì)一個(gè)新的交叉算法，提高GA的效率．實(shí)驗(yàn)證明不管在求解精度上還是在求解速度上，隨機(jī)化均勻設(shè)計(jì)遺傳算法不僅優(yōu)于GA，也優(yōu)于佳點(diǎn)集遺傳算法．2.佳點(diǎn)集遺傳算法設(shè)在傳統(tǒng)的GA算法基礎(chǔ)上,在進(jìn)行過復(fù)制后,對(duì)池中的元素按賭輪法選擇兩個(gè)元素A1,A2進(jìn)行佳點(diǎn)交叉操作不妨設(shè)A1與A2的前t個(gè)分量不同,后L-t個(gè)分量相

7、同由A1與A2進(jìn)行交叉(不管是單點(diǎn)交叉或是多點(diǎn)交叉),其子孫必屬于H,于是要在“高適應(yīng)度模式為祖先的家族方向”上搜索出更好的樣本,就是要在H中搜索出更好的樣本來.現(xiàn)在我們要在H上利用佳點(diǎn)集方法求出好樣本來,其方法是:將H的前t個(gè)分量看成一個(gè)t維的立方體(仍記為H),然后在H上求佳點(diǎn)集.或?qū)的每d個(gè)分量分成一組(不妨設(shè)共分成s組),每組表示一個(gè)實(shí)數(shù),于是s個(gè)組就表示s個(gè)實(shí)數(shù),這樣就將H變換成一個(gè)s維的實(shí)空間,可將其歸一化變換成一個(gè)s維的單位立方體,然后在其上求佳點(diǎn)集.如(1,1,0,0,1,0,1,0,1,1,0,1)是12維二進(jìn)制單位立方體中的一點(diǎn)