遺傳算法的改進(jìn)ppt課件_第1頁
遺傳算法的改進(jìn)ppt課件_第2頁
遺傳算法的改進(jìn)ppt課件_第3頁
遺傳算法的改進(jìn)ppt課件_第4頁
遺傳算法的改進(jìn)ppt課件_第5頁
已閱讀5頁,還剩17頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、遺傳算法的改進(jìn),遺傳算法的改進(jìn),自從1975年Holland系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來,眾多學(xué)者一直致力于推動(dòng)遺傳算法的發(fā)展,對(duì)編碼方式、控制參數(shù)的確定、選擇方式和交叉機(jī)理等進(jìn)行了深入的探究,引入了動(dòng)態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能,提出了各種改進(jìn)的遺傳算法。 下面介紹幾種改進(jìn)的遺傳算法,分層遺傳算法,CHC算法,CHC算法是Eshelman于1991年提出的一種改進(jìn)遺傳算法,第一個(gè)C代表跨世代精英選擇(Cross generational elitist selection)策略,H代表異物種重組,第二個(gè)C代表大變異。CHC算法與基本遺傳算法不同點(diǎn)在于: 1、選擇 通常,遺

2、傳算法是依據(jù)個(gè)體的適應(yīng)度復(fù)制個(gè)體完成選擇操作的,而在CHC算法中,上世代種群與通過新的交叉方法產(chǎn)生的個(gè)體群混合起來,從中按一定概率選擇較優(yōu)的個(gè)體。這一策略稱為跨世代精英選擇,2、交叉 CHC算法使用的重組操作是對(duì)均勻交叉的一種改進(jìn)。 當(dāng)兩個(gè)父個(gè)體位置相異的位數(shù)為m時(shí),從中 隨機(jī)選取m/2個(gè)位置,實(shí)行父個(gè)體位置的互換。顯然,這樣的操作對(duì)模式具有很強(qiáng)的破壞性。因此,確定一閥值,當(dāng)個(gè)體間的海明距離低于該閥值,不進(jìn)行交叉操作。并且,隨著種群的進(jìn)化,逐漸減小該閥值。 3、變異 CHC算法在進(jìn)化前期不采取變異操作,當(dāng)種群進(jìn)化到一定的收斂時(shí)期,從優(yōu)秀個(gè)體中選擇一部分個(gè)體進(jìn)行初始化。初始化的方法是選擇一定比例

3、的位置,隨機(jī)決定他們的值。這個(gè)比例值稱為擴(kuò)散率,一般取0.35,自適應(yīng)遺傳算法,遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在,直接影響算法的收斂性, Pc 越大,新個(gè)體產(chǎn)生的速度就越快,然而 Pc過大時(shí)遺傳模式被破壞的可能性也越大,使得具有高適應(yīng)度的個(gè)體結(jié)果很快就被破壞;但是如果Pc過小,會(huì)使搜索過程緩慢,一直停滯不前。對(duì)于變異概率Pm,如果Pm過小,就不易產(chǎn)生新的個(gè)體結(jié)構(gòu),如果Pm取值過大,那么遺傳算法就變成了隨機(jī)搜索算法。Srinvivas等提出了一種自適應(yīng)遺傳算法, Pc和 Pm能夠隨適應(yīng)度自動(dòng)改變,算法思想: 對(duì)于適應(yīng)度高與群體平均適應(yīng)值的個(gè)體,相

4、對(duì)應(yīng)于較低的Pc和 Pm,使該解得以保護(hù)進(jìn)入下一代;而低于平均適應(yīng)值的個(gè)體,相對(duì)應(yīng)于較高的Pc和 Pm,使該解被淘汰,從上式可以看出,當(dāng)適應(yīng)度度值越接近最大適應(yīng)度值時(shí),交叉率和變異率就越小,當(dāng)?shù)扔谧畲筮m應(yīng)度值時(shí),交叉率和變異率為零,這種調(diào)整方法對(duì)于群體處于進(jìn)化后期比較合適,但對(duì)于進(jìn)化初期不利,因?yàn)檫M(jìn)化初期群體中的較優(yōu)個(gè)體幾乎不發(fā)生變化,容易使進(jìn)化走向局部最優(yōu)解的可能性增大。為此,可以作進(jìn)一步的改進(jìn),使群體中最大適應(yīng)度值的個(gè)體的交叉率和變異率分別為 和 。為了保證每一代的最優(yōu)個(gè)體不被破壞,采用精英選擇策略,使他們直接復(fù)制到下一代中,基于小生境技術(shù)的遺傳算法,基本遺傳算法在求解多峰值函數(shù)的優(yōu)化計(jì)算

5、問題時(shí), 往往只能找到幾個(gè)局部最優(yōu)解, 而無法收斂到全局最優(yōu)解。這是因?yàn)樵跇?biāo)準(zhǔn)的遺傳算法的初期, 群體保持了多樣性, 但是到了算法后期, 群體的多樣性遭到了破壞, 大量個(gè)體集中于某一個(gè)極值點(diǎn)附近, 它們的后代造成了近親繁殖, 這樣就易造成收斂于一個(gè)局部最優(yōu)解, 而無法跳出該局部搜索 。 在生物學(xué)中, 小生境是指特定環(huán)境下的一種生存環(huán)境, 相同的生物生活在同一個(gè)小生境中。借鑒此概念, 遺傳算法將每一代個(gè)體劃分為若干類, 每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群, 再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個(gè)體群, 同時(shí)采用預(yù)選擇機(jī)制或者排擠機(jī)制或共享機(jī)制完成選擇操

6、作。這樣可以更好的保持群體的多樣性, 使其具有很高的全局尋優(yōu)能力和收斂速度,基于預(yù)選擇機(jī)制的選擇策略:當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度超過其父代個(gè)體的適應(yīng)度時(shí),所產(chǎn)生的子代個(gè)體才能代替其父代個(gè)體而遺傳到下一代群體中,否則父代個(gè)體仍保留在下一代群體中。由于子代個(gè)體和父代個(gè)體之間編碼結(jié)構(gòu)的相似性,所以替換掉的只是一些編碼結(jié)構(gòu)相似的個(gè)體,能夠有效地維持群體的多樣性,并造就小生境的進(jìn)化環(huán)境。 基于排擠機(jī)制的選擇策略:思想起源于在一個(gè)有限的生存空間中,各種不同的生物為了能夠延續(xù)生存,必須相互競爭各種有限資源。因此,在算法中設(shè)置一個(gè)排擠因子CF(CF=2或3),由群體中隨機(jī)地選取N/CF個(gè)個(gè)體組成排擠成員,然后依據(jù)新產(chǎn)生的個(gè)體與排擠成員之間的相似性來排擠一些相似個(gè)體,隨著排擠過程的進(jìn)行,群體中的個(gè)體逐漸被分類,從而形成一個(gè)個(gè)小的生成環(huán)境,并維持了群體的多樣性。 共享法的選擇策略:通過個(gè)體之間的相似程度的共享函數(shù)來調(diào)整群體中各個(gè)個(gè)體的適應(yīng)度,適應(yīng)度共享函數(shù)的直接目的是將搜索空間的多個(gè)不同峰值在地理上區(qū)分開來,每一個(gè)峰值處接受一定比例數(shù)目的個(gè)體,混合遺傳算法,梯度法、爬山法、模擬退火等一些優(yōu)化算法具有很強(qiáng)的局部搜索能力,如果融合這些優(yōu)化方法的思想,構(gòu)成一種混合遺傳算法,是提高遺傳算法運(yùn)行效率和求解質(zhì)量一個(gè)有效手段。 1、遺傳算

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論