《遺傳算法的基本原理(共2頁).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《遺傳算法的基本原理(共2頁).doc（2頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上遺傳算法的基本原理遺傳算法類似于自然進(jìn)化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個(gè)染色體進(jìn)行評價(jià)，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始群體；通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群。對這個(gè)新種群進(jìn)行下一輪進(jìn)化。這就是遺傳算法的基本原理。下面就是遺傳算法思想：(1) 初始化群體;(2) 計(jì)算

2、群體上每個(gè)個(gè)體的適應(yīng)度值;(3) 按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體;(4) 按概率PX進(jìn)行交叉操作;(5) 按概率PM進(jìn)行突變操作;(6) 沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)。(7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。程序的停止條件最簡單的有如下二種：完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。根據(jù)遺傳算法思想可以畫出如右圖所示的簡單遺傳算法框圖：圖 3.22 簡單遺傳算法框圖 遺傳算法的選擇算子選擇即從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池的過程. 遺傳算法中最

3、常用的選擇方式是輪盤賭(Roulette Wheel)選擇方式, 也稱比例選擇或復(fù)制. 在該方法中, 各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比例. 設(shè)群體規(guī)模大小為N, 個(gè)體i 的適應(yīng)度值為Fi , 則這個(gè)個(gè)體被選擇的概率為:顯然, 個(gè)體適應(yīng)度越大, 其被選擇的概率越高,反之亦然.遺傳算法另一種常用的選擇方式是錦標(biāo)賽選擇方式, 其基本思想是將上一代群體中的個(gè)體和本次遺傳操作產(chǎn)生的所有新個(gè)體放到一起按適值從大到小的順序排隊(duì), 然后取排在前面的N 個(gè)(N 為群體規(guī)模)個(gè)體組成新一代群體.遺傳算法的交叉算子作用于某2 個(gè)父代個(gè)體時(shí), 會(huì)產(chǎn)生2 個(gè)子代個(gè)體, 父子2 代共4 個(gè)個(gè)體平等競爭, 淘汰2 個(gè)低

4、適值個(gè)體, 保留2 個(gè)高適值個(gè)體. 遺傳算法的變異算子作用于某一父代個(gè)體時(shí),會(huì)產(chǎn)生一個(gè)子代個(gè)體, 如果子代個(gè)體的適值比父代個(gè)體的高, 則用子代個(gè)體取代父代個(gè)體; 否則保留父代個(gè)體淘汰子代個(gè)體, 這就是父子競爭選擇.遺傳算法初始群體中的個(gè)體一般是隨機(jī)產(chǎn)生的, 初始群體中的個(gè)體均勻地分布于整個(gè)串空間.在遺傳迭代的早期, 群體中個(gè)體適值差別很大, 按上述3 種選擇方式容易出現(xiàn)的問題是: 在選擇下一代群體時(shí), 適值低的個(gè)體被選中的機(jī)會(huì)很小, 最佳個(gè)體在下一代的生存機(jī)會(huì)將顯著增加, 而最差個(gè)體的生存機(jī)會(huì)將被剝奪,低適值個(gè)體淘汰太快容易使算法收斂于局部最優(yōu)解. 群體中的最佳個(gè)體快速充滿整個(gè)群體, 導(dǎo)致群體

5、多樣性降低, GA 也過早地喪失了進(jìn)化能力. 而到了遺傳迭代的晚期,群體中個(gè)體適值差別不大, 算法收斂速度慢. 此外,遺傳算法只有在引入了最優(yōu)保持操作后才是全局收斂的. 因此, 我們提出改進(jìn)的選擇策略, 先對群體中個(gè)體的適值進(jìn)行變換, 再按個(gè)體適值大小的比例進(jìn)行選擇. 具體方法是: 先將參與選擇的X 個(gè)個(gè)體按適值從小到大順序編號(hào)(相同適值的個(gè)體可隨意排列), 然后以個(gè)體的序號(hào)作為其變換后的適值, 即X 個(gè)個(gè)體的適值分別變換為1, 2, 3, X. 編號(hào)為m 的個(gè)體被選中的概率為p=m /X , 1mX. 顯然, 這種改進(jìn)的選擇與個(gè)體的適應(yīng)值無直接關(guān)系, 僅僅與個(gè)體之間的適應(yīng)值相對大小有關(guān). 這

6、種策略一方面通過對群體中個(gè)體適值的變換, 使群體中的個(gè)體在遺傳迭代的整個(gè)過程中都能保持良好的多樣性, 既保證了算法具有較快的收斂速度, 又能防止算法收斂于局部最優(yōu)解; 另一方面能使上一代的最優(yōu)個(gè)體一定會(huì)被選擇到下一代, 即這種選擇策略隱含了最優(yōu)保持操作, 保證了算法的全局收斂性. 由于選擇概率比較容易控制, 所以適用于動(dòng)態(tài)調(diào)整選擇概率, 根據(jù)進(jìn)化效果適時(shí)改變?nèi)后w選擇壓力.即輪盤賭選擇方式、聯(lián)賽選擇方式和父子競爭選擇方式, 前一種選擇方式在引入了最優(yōu)保持操作后能保證算法的全局收斂性, 但收斂速度較慢; 后2種選擇方式不能保證算法的全局收斂性, 很可能收斂于局部最優(yōu)解, 但有較快的收斂速度. 因此,適當(dāng)選擇遺傳算法的選擇方式對提高算法的計(jì)算專心-專注-專業(yè)