《遺傳算法的改進(jìn)》PPT課件

《《遺傳算法的改進(jìn)》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、遺傳算法的改進(jìn)遺傳算法的改進(jìn)自從1975年Holland系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來(lái)，眾多學(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代表跨世代精英選擇(Crossgenerationalelitistselection)策略，H代表異物種

2、重組，第二個(gè)C代表大變異。CHC算法與基本遺傳算法不同點(diǎn)在于：1、選擇通常，遺傳算法是依據(jù)個(gè)體的適應(yīng)度復(fù)制個(gè)體完成選擇操作的，而在CHC算法中，上世代種群與通過(guò)新的交叉方法產(chǎn)生的個(gè)體群混合起來(lái)，從中按一定概率選擇較優(yōu)的個(gè)體。這一策略稱為跨世代精英選擇。2、交叉CHC算法使用的重組操作是對(duì)均勻交叉的一種改進(jìn)。當(dāng)兩個(gè)父?jìng)€(gè)體位置相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位置的互換。顯然，這樣的操作對(duì)模式具有很強(qiáng)的破壞性。因此，確定一閥值，當(dāng)個(gè)體間的海明距離低于該閥值，不進(jìn)行交叉操作。并且，隨

3、著種群的進(jìn)化，逐漸減小該閥值。3、變異CHC算法在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定的收斂時(shí)期，從優(yōu)秀個(gè)體中選擇一部分個(gè)體進(jìn)行初始化。初始化的方法是選擇一定比例的位置，隨機(jī)決定他們的值。這個(gè)比例值稱為擴(kuò)散率，一般取0.35。自適應(yīng)遺傳算法遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性,Pc越大，新個(gè)體產(chǎn)生的速度就越快，然而Pc過(guò)大時(shí)遺傳模式被破壞的可能性也越大，使得具有高適應(yīng)度的個(gè)體結(jié)果很快就被破壞；但是如果Pc過(guò)小，會(huì)使搜索過(guò)程緩慢

4、，一直停滯不前。對(duì)于變異概率Pm，如果Pm過(guò)小，就不易產(chǎn)生新的個(gè)體結(jié)構(gòu)，如果Pm取值過(guò)大，那么遺傳算法就變成了隨機(jī)搜索算法。Srinvivas等提出了一種自適應(yīng)遺傳算法，Pc和Pm能夠隨適應(yīng)度自動(dòng)改變。算法思想:對(duì)于適應(yīng)度高與群體平均適應(yīng)值的個(gè)體，相對(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ì)于群體處于

5、進(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ì)算問(wèn)題時(shí),往往只能找到幾個(gè)局部最優(yōu)解,而無(wú)法收斂到全局最優(yōu)解。這是因?yàn)樵跇?biāo)準(zhǔn)的遺傳算法的初期,群體保持了多樣性,但是到了算法后期,群體的多樣性遭到了破壞,大量個(gè)體集中

6、于某一個(gè)極值點(diǎn)附近,它們的后代造成了近親繁殖,這樣就易造成收斂于一個(gè)局部最優(yōu)解,而無(wú)法跳出該局部搜索。在生物學(xué)中,小生境是指特定環(huán)境下的一種生存環(huán)境,相同的生物生活在同一個(gè)小生境中。借鑒此概念,遺傳算法將每一代個(gè)體劃分為若干類,每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群,再在種群中以及不同種群之間通過(guò)雜交、變異產(chǎn)生新一代個(gè)體群,同時(shí)采用預(yù)選擇機(jī)制或者排擠機(jī)制或共享機(jī)制完成選擇操作。這樣可以更好的保持群體的多樣性,使其具有很高的全局尋優(yōu)能力和收斂速度?；陬A(yù)選擇機(jī)制的選擇策略：

7、當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度超過(guò)其父代個(gè)體的適應(yīng)度時(shí)，所產(chǎn)生的子代個(gè)體才能代替其父代個(gè)體而遺傳到下一代群體中，否則父代個(gè)體仍保留在下一代群體中。由于子代個(gè)體和父代個(gè)體之間編碼結(jié)構(gòu)的相似性，所以替換掉的只是一些編碼結(jié)構(gòu)相似的個(gè)體，能夠有效地維持群體的多樣性，并造就小生境的進(jìn)化環(huán)境?；谂艛D機(jī)制的選擇策略：思想起源于在一個(gè)有限的生存空間中，各種不同的生物為了能夠延續(xù)生存，必須相互競(jìng)爭(zhēng)各種有限資源。因此，在算法中設(shè)置一個(gè)排擠因子CF（CF=2或3），由群體中隨機(jī)地選取N/CF個(gè)個(gè)體組成排擠成員，然后依據(jù)新

8、產(chǎn)生的個(gè)體與排擠成員之間的相似性來(lái)排擠一些相似個(gè)體，隨著排擠過(guò)程的進(jìn)行，群體中的個(gè)體逐漸被分類，從而形成一個(gè)個(gè)小的生成環(huán)境，并維持了群體的多樣性。共享法的選擇策略：通過(guò)個(gè)體之間的相似程度的共享函數(shù)來(lái)調(diào)整群體中各個(gè)個(gè)體的適應(yīng)度，適應(yīng)度共享函數(shù)的直接目的是將搜索空間的多個(gè)不同峰值在地理上區(qū)分開(kāi)來(lái)，每一個(gè)峰值處接受一定比例數(shù)目的個(gè)體?；旌线z傳算法梯度法、爬山法、模擬退火等一些優(yōu)化算法具有很強(qiáng)的局部搜索能力，如果融合這些優(yōu)化方法的思想，構(gòu)成一種混合遺傳算法，是提高遺傳算法運(yùn)行效率和求解質(zhì)量