遺傳算法的改進

1、遺傳算法的改進遺傳算法的改進n 自從1975年Holland系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來，眾多學(xué)者一直致力于推動遺傳算法的發(fā)展，對編碼方式、控制參數(shù)的確定、選擇方式和交叉機理等進行了深入的探究，引入了動態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能，提出了各種改進的遺傳算法。n下面介紹幾種改進的遺傳算法。分層遺傳算法n (1,2,)iNnNnGA iNN對于一個問題，首先隨機地生成個樣本，然后將它們分成 個子種群，每個子種群包含個樣本，對每個子種群獨立地運行各自的遺傳算法，即它們?yōu)?。這 個遺傳算法最好在設(shè)置特性上有較大的差異，這樣就可以為將來的高層遺傳算法產(chǎn)生更多種類的優(yōu)良模式。11, ,

2、(1,1)1 iiNRnR i j iN jnGAjNANA iGA 在每個子種群的遺傳算法運行到一定代數(shù)后，將個遺傳算法的結(jié)果記錄到二維數(shù)組，則表示的結(jié)果種群的第 個個體。同時，將 各結(jié)果種群的平均適應(yīng)度值紀(jì)錄到數(shù)組中，表示的結(jié)果種群平均適應(yīng)度值。1.1,2. ,1 ,11,;11 , ,1 ,1ANNRR inR jnxi jNxnR i xnR j xn選擇基于數(shù)組即 個遺傳算法的平均適應(yīng)度值，對數(shù)組 代表的結(jié)果種群進行選擇操作，一些結(jié)果種群由于它們的平均適應(yīng)度高而被復(fù)制，甚至復(fù)制多次；另一些結(jié)果種群由于它們的種群平均適應(yīng)度值低而被淘汰。交叉如果和被隨機匹配到一起，而且從位置 進行交叉（

3、） 則和相互交換相應(yīng)的部分。這一步相當(dāng)ijGAGAnx于交換和中結(jié)果種群的個個體。3.1,1RNnN變異以很小的概率將少量的隨機生成的新個體替換中隨機抽取的個體。產(chǎn)生 個新的種群，重新開始在新的種群中繼續(xù)各自的操作。繼續(xù)循環(huán)操作，直至得到滿意的結(jié)果。CHC算法n CHC算法是Eshelman于1991年提出的一種改進遺傳算法，第一個C代表跨世代精英選擇(Cross generational elitist selection)策略，H代表異物種重組，第二個C代表大變異。CHC算法與基本遺傳算法不同點在于：n1、選擇n通常，遺傳算法是依據(jù)個體的適應(yīng)度復(fù)制個體完成選擇操作的，而在CHC算法中，上世

4、代種群與通過新的交叉方法產(chǎn)生的個體群混合起來，從中按一定概率選擇較優(yōu)的個體。這一策略稱為跨世代精英選擇。n2、交叉n CHC算法使用的重組操作是對均勻交叉的一種改進。n當(dāng)兩個父個體位置相異的位數(shù)為m時，從中n隨機選取m/2個位置，實行父個體位置的互換。顯然，這樣的操作對模式具有很強的破壞性。因此，確定一閥值，當(dāng)個體間的海明距離低于該閥值，不進行交叉操作。并且，隨著種群的進化，逐漸減小該閥值。n3、變異nCHC算法在進化前期不采取變異操作，當(dāng)種群進化到一定的收斂時期，從優(yōu)秀個體中選擇一部分個體進行初始化。初始化的方法是選擇一定比例的位置，隨機決定他們的值。這個比例值稱為擴散率，一般取0.35。自

5、適應(yīng)遺傳算法n 遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性, Pc 越大，新個體產(chǎn)生的速度就越快，然而 Pc過大時遺傳模式被破壞的可能性也越大，使得具有高適應(yīng)度的個體結(jié)果很快就被破壞；但是如果Pc過小，會使搜索過程緩慢，一直停滯不前。對于變異概率Pm，如果Pm過小，就不易產(chǎn)生新的個體結(jié)構(gòu)，如果Pm取值過大，那么遺傳算法就變成了隨機搜索算法。Srinvivas等提出了一種自適應(yīng)遺傳算法， Pc和 Pm能夠隨適應(yīng)度自動改變。n算法思想: 對于適應(yīng)度高與群體平均適應(yīng)值的個體，相對應(yīng)于較低的Pc和 Pm，使該解得以保護進入下一代；而低于平均

6、適應(yīng)值的個體，相對應(yīng)于較高的Pc和 Pm，使該解被淘汰。1maxmax23maxmax4maxmax(),(),cmavgavgcavgavgavgmavgPPkffffffPkffkffffffPkffffff在自適應(yīng)遺傳算法中， 和按如下公式進行自適應(yīng)調(diào)整：其中，群體中最大的適應(yīng)度值每代群體的平均適應(yīng)度值要交叉的兩個個體重較大的適應(yīng)度值要變異個體的適應(yīng)度值n從上式可以看出，當(dāng)適應(yīng)度度值越接近最大適應(yīng)度值時，交叉率和變異率就越小，當(dāng)?shù)扔谧畲筮m應(yīng)度值時，交叉率和變異率為零，這種調(diào)整方法對于群體處于進化后期比較合適，但對于進化初期不利，因為進化初期群體中的較優(yōu)個體幾乎不發(fā)生變化，容易使進化走向局

7、部最優(yōu)解的可能性增大。為此，可以作進一步的改進，使群體中最大適應(yīng)度值的個體的交叉率和變異率分別為 和 。為了保證每一代的最優(yōu)個體不被破壞，采用精英選擇策略，使他們直接復(fù)制到下一代中。2cP2mP12max1max112max1max11212()(),()(),0.9,0.6,0.1,0.001cmcccavgavgccavgmmmavgavgmmavgccmmPPPPffPffffPPffPPffPffffPPffPPPP改進后， 和按如下公式進行自適應(yīng)調(diào)整：取基于小生境技術(shù)的遺傳算法n 基本遺傳算法在求解多峰值函數(shù)的優(yōu)化計算問題時基本遺傳算法在求解多峰值函數(shù)的優(yōu)化計算問題時, , 往往只能

8、找到往往只能找到幾個局部最優(yōu)解幾個局部最優(yōu)解, , 而無法收斂到全局最優(yōu)解。這是因為在標(biāo)準(zhǔn)的遺傳而無法收斂到全局最優(yōu)解。這是因為在標(biāo)準(zhǔn)的遺傳算法的初期算法的初期, , 群體保持了多樣性群體保持了多樣性, , 但是到了算法后期但是到了算法后期, , 群體的多樣性群體的多樣性遭到了破壞遭到了破壞, , 大量個體集中于某一個極值點附近大量個體集中于某一個極值點附近, , 它們的后代造成了它們的后代造成了近親繁殖近親繁殖, , 這樣就易造成收斂于一個局部最優(yōu)解這樣就易造成收斂于一個局部最優(yōu)解, , 而無法跳出該局部而無法跳出該局部搜索搜索 。n 在生物學(xué)中在生物學(xué)中, , 小生境是指特定環(huán)境下的一種生

9、存環(huán)境小生境是指特定環(huán)境下的一種生存環(huán)境, , 相同的生相同的生物生活在同一個小生境中。借鑒此概念物生活在同一個小生境中。借鑒此概念, , 遺傳算法將每一代個體劃分遺傳算法將每一代個體劃分為若干類為若干類, , 每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表組成一個種群表組成一個種群, , 再在種群中以及不同種群之間通過雜交、變異產(chǎn)生再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個體群新一代個體群, , 同時采用預(yù)選擇機制或者排擠機制或共享機制完成選同時采用預(yù)選擇機制或者排擠機制或共享機制完成選擇操作。這樣可以更好的保持群體的多樣性擇

10、操作。這樣可以更好的保持群體的多樣性, , 使其具有很高的全局尋使其具有很高的全局尋優(yōu)能力和收斂速度。優(yōu)能力和收斂速度。n 基于預(yù)選擇機制的選擇策略：當(dāng)新產(chǎn)生的子代個體的基于預(yù)選擇機制的選擇策略：當(dāng)新產(chǎn)生的子代個體的適應(yīng)度超過其父代個體的適應(yīng)度時，所產(chǎn)生的子代個體才適應(yīng)度超過其父代個體的適應(yīng)度時，所產(chǎn)生的子代個體才能代替其父代個體而遺傳到下一代群體中，否則父代個體能代替其父代個體而遺傳到下一代群體中，否則父代個體仍保留在下一代群體中。由于子代個體和父代個體之間編仍保留在下一代群體中。由于子代個體和父代個體之間編碼結(jié)構(gòu)的相似性，所以替換掉的只是一些編碼結(jié)構(gòu)相似的碼結(jié)構(gòu)的相似性，所以替換掉的只是一

11、些編碼結(jié)構(gòu)相似的個體，能夠有效地維持群體的多樣性，并造就小生境的進個體，能夠有效地維持群體的多樣性，并造就小生境的進化環(huán)境?；h(huán)境。n 基于排擠機制的選擇策略：思想起源于在一個有限基于排擠機制的選擇策略：思想起源于在一個有限的生存空間中，各種不同的生物為了能夠延續(xù)生存，必須的生存空間中，各種不同的生物為了能夠延續(xù)生存，必須相互競爭各種有限資源。因此，在算法中設(shè)置一個排擠因相互競爭各種有限資源。因此，在算法中設(shè)置一個排擠因子子CFCF（CF=2CF=2或或3 3），由群體中隨機地選?。扇后w中隨機地選取N/CFN/CF個個體組成個個體組成排擠成員，然后依據(jù)新產(chǎn)生的個體與排擠成員之間的相似排擠成

12、員，然后依據(jù)新產(chǎn)生的個體與排擠成員之間的相似性來排擠一些相似個體，隨著排擠過程的進行，群體中的性來排擠一些相似個體，隨著排擠過程的進行，群體中的個體逐漸被分類，從而形成一個個小的生成環(huán)境，并維持個體逐漸被分類，從而形成一個個小的生成環(huán)境，并維持了群體的多樣性。了群體的多樣性。n 共享法的選擇策略：通過個體之間的相似程度的共享函共享法的選擇策略：通過個體之間的相似程度的共享函數(shù)來調(diào)整群體中各個個體的適應(yīng)度，適應(yīng)度共享函數(shù)的直數(shù)來調(diào)整群體中各個個體的適應(yīng)度，適應(yīng)度共享函數(shù)的直接目的是將搜索空間的多個不同峰值在地理上區(qū)分開來，接目的是將搜索空間的多個不同峰值在地理上區(qū)分開來，每一個峰值處接受一定比例

13、數(shù)目的個體。每一個峰值處接受一定比例數(shù)目的個體?；旌线z傳算法n 梯度法、爬山法、模擬退火等一些優(yōu)化算法具有很強的局部搜索能力，如果融合這些優(yōu)化方法的思想，構(gòu)成一種混合遺傳算法，是提高遺傳算法運行效率和求解質(zhì)量一個有效手段。n1、遺傳算法與最速下降法相結(jié)合n主要改進是：在每次繁殖中產(chǎn)生的新的子代，都要以概率Ps判斷是否需要進行線性搜索運算，經(jīng)最速下降算子的線性搜索運算產(chǎn)生的新的個體繼承了其父代的優(yōu)良品質(zhì)。2:1( )( )()( )( )exp()( )( )kkMetrolpisijPf if jP ijf if jf if jt、遺傳算法與模擬退火法相結(jié)合的混合遺傳算法改進為：將接受準(zhǔn)則應(yīng)用于確定從當(dāng)前解到新解 轉(zhuǎn)移的概率背包問題背包問題 (knapsack problem)11,10-11,20nniinssppcixxin這是一個典型的最優(yōu)化問題。基本背包問題：設(shè) 件物體的重量分別為使用價值分別為，一個背包能承受的總重量為 如何裝包使總價值最大。第 件物體裝包設(shè) 為變量，否則111212max.0,1,1,21,10iiniiiiiiinnpxscxstinxniiisppppsss這一問題的數(shù)