(完整版)遺傳算法的基本原理

1、遺傳算法的基本原理和方法一、編碼編碼：把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法的搜索空間的轉(zhuǎn)換方法。解碼(譯碼)：遺傳算法解空間向問題空間的轉(zhuǎn)換。二進制編碼的缺點是漢明懸崖(HammingCliff),就是在某些相鄰整數(shù)的二進制代碼之間有很大的漢明距離，使得遺傳算法的交叉和突變都難以跨越。格雷碼(GrayCode)：在相鄰整數(shù)之間漢明距離都為1。(較好)有意義的積木塊編碼規(guī)則：所定編碼應(yīng)當(dāng)易于生成與所求問題相關(guān)的短距和低階的積木塊；最小字符集編碼規(guī)則，所定編碼應(yīng)采用最小字符集以使問題得到自然的表示或描述。二進制編碼比十進制編碼搜索能力強，但不能保持群體穩(wěn)定性。動態(tài)參數(shù)編碼(DynamicPa

2、remeterCoding):為了得到很高的精度，讓遺傳算法從很粗糙的精度開始收斂,當(dāng)遺傳算法找到一個區(qū)域后，就將搜索現(xiàn)在在這個區(qū)域，重新編碼，重新啟動，重復(fù)這一過程，直到達到要求的精度為止。編碼方法：1、二進制編碼方法缺點：存在著連續(xù)函數(shù)離散化時的映射誤差。不能直接反映出所求問題的本身結(jié)構(gòu)特征，不便于開發(fā)針對問題的專門知識的遺傳運算算子，很難滿足積木塊編碼原則2、格雷碼編碼：連續(xù)的兩個整數(shù)所對應(yīng)的編碼之間僅僅只有一個碼位是不同的，其余碼位都相同。3、浮點數(shù)編碼方法：個體的每個基因值用某一范圍內(nèi)的某個浮點數(shù)來表示，個體的編碼長度等于其決策變量的位數(shù)。4、各參數(shù)級聯(lián)編碼：對含有多個變量的個體進行

3、編碼的方法。通常將各個參數(shù)分別以某種編碼方法進行編碼，然后再將他們的編碼按照一定順序連接在一起就組成了表示全部參數(shù)的個體編碼。5、多參數(shù)交叉編碼：將各個參數(shù)中起主要作用的碼位集中在一起，這樣它們就不易于被遺傳算子破壞掉。評估編碼的三個規(guī)范：完備性、健全性、非冗余性。二、選擇遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運算，用來確定重組或交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。常用的選擇算子：1、輪盤賭選擇(RouletteWheelSelection):是一種回放式隨機采樣方法。每個個體進入下一代的概率等于它的適應(yīng)度值與整個種群中個體適

4、應(yīng)度值和的比例。選擇誤差較大。2、隨機競爭選擇（StochasticTournament）:每次按輪盤賭選擇一對個體，然后讓這兩個個體進行競爭，適應(yīng)度高的被選中，如此反復(fù)，直到選滿為止。3、最佳保留選擇:首先按輪盤賭選擇方法執(zhí)行遺傳算法的選擇操作，然后將當(dāng)前群體中適應(yīng)度最高的個體結(jié)構(gòu)完整地復(fù)制到下一代群體中。4、無回放隨機選擇（也叫期望值選擇ExceptedValueSelection）:根據(jù)每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下（1）計算群體中每個個體在下一代群體中的生存期望數(shù)目N。（2）若某一個體被選中參與交叉運算，則它在下一代中的生存期望數(shù)目減去0.5，若某一個體未

5、被選中參與交叉運算，則它在下一代中的生存期望數(shù)目減去1.0。（3）隨著選擇過程的進行，若某一個體的生存期望數(shù)目小于0時，則該個體就不再有機會被選中。5、確定式選擇:按照一種確定的方式來進行選擇操作。具體操作過程如下:（1）計算群體中各個個體在下一代群體中的期望生存數(shù)目N。（2）用N的整數(shù)部分確定各個對應(yīng)個體在下一代群體中的生存數(shù)目。（3）用N的小數(shù)部分對個體進行降序排列，順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。6、無回放余數(shù)隨機選擇：可確保適應(yīng)度比平均適應(yīng)度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小。7、均勻排序：對群體中的所有個體按期適應(yīng)度大小

6、進行排序，基于這個排序來分配各個個體被選中的概率。8、最佳保存策略：當(dāng)前群體中適應(yīng)度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經(jīng)過交叉、變異等操作后所產(chǎn)生的適應(yīng)度最低的個體。9、隨機聯(lián)賽選擇：每次選取幾個個體中適應(yīng)度最高的一個個體遺傳到下一代群體中。10、排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。三、交叉遺傳算法的交叉操作，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。適用于二進制編碼個體或浮點數(shù)編碼個體的交叉算子：1、單點交叉(OnepointCrossover):指在個體編碼串中只隨機設(shè)置一個交叉點,然后再該點

7、相互交換兩個配對個體的部分染色體。2、兩點交叉與多點交叉：(1) 兩點交叉(TwopointCrossover):在個體編碼串中隨機設(shè)置了兩個交叉點，然后再進行部分基因交換。(2) 多點交叉(MultipointCrossover)3、均勻交叉(也稱一致交叉，UniformCrossover):兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體。4、算術(shù)交叉(ArithmeticCrossover):由兩個個體的線性組合而產(chǎn)生出兩個新的個體。該操作對象一般是由浮點數(shù)編碼表示的個體。四、變異遺傳算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座

8、上的其它等位基因來替換，從而形成以給新的個體。以下變異算子適用于二進制編碼和浮點數(shù)編碼的個體：1、基本位變異(SimpleMutation):對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。2、均勻變異(UniformMutation):分別用符合某一范圍內(nèi)均勻分布的隨機數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。(特別適用于在算法的初級運行階段)3、邊界變異(BoundaryMutation):隨機的取基因座上的兩個對應(yīng)邊界基因值之一去替代原有基因值。特別適用于最優(yōu)點位于或接近于可行解的邊界時的一類問題。4、非均勻變異：對原有的基因值做一隨機擾動

9、，以擾動后的結(jié)果作為變異后的新基因值。對每個基因座都以相同的概率進行變異運算之后，相當(dāng)于整個解向量在解空間中作了一次輕微的變動。5、高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P2勺正態(tài)分布的一個隨機數(shù)來替換原有的基因值。五、適應(yīng)度函數(shù)適應(yīng)度函數(shù)也稱評價函數(shù)，是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個體好壞的標(biāo)準。適應(yīng)度函數(shù)總是非負的，而目標(biāo)函數(shù)可能有正有負，故需要在目標(biāo)函數(shù)與適應(yīng)度函數(shù)之間進行變換。評價個體適應(yīng)度的一般過程為:1、對個體編碼串進行解碼處理后，可得到個體的表現(xiàn)型。2、由個體的表現(xiàn)型可計算出對應(yīng)個體的目標(biāo)函數(shù)值。3、根據(jù)最優(yōu)化問題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個

10、體的適應(yīng)度。適應(yīng)度函數(shù)的設(shè)計主要應(yīng)滿足以下要求：1、單值、連續(xù)、非負、最大化。2、合理、一致性。較難。3、計算量小。4、通用性強。由目標(biāo)函數(shù)f(x)到適應(yīng)度函數(shù)Fit(f(x)的轉(zhuǎn)換方法有以下三種：1、直接以待解的目標(biāo)函數(shù)f(x)轉(zhuǎn)換為適應(yīng)度函數(shù)。Fit(f(x)=f(x)目標(biāo)函數(shù)為最大化問題Fit(f(x)=f(x)目標(biāo)函數(shù)為最小化問題問題：可能不滿足常用的輪盤賭選擇中概率非負的要求；某攜帶求解的函數(shù)在函數(shù)值分布上相差很大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能。2、做轉(zhuǎn)換。(具體轉(zhuǎn)換方法略)3、同2，轉(zhuǎn)換公式不同。適應(yīng)度尺度變換(FitnessScalingTransform):在遺傳算法的不同階段，對個體的適應(yīng)度進行適當(dāng)?shù)臄U大或縮小。常用的尺度變換方法如下：1、線性尺度變換：F'=aF+b2、乘幕尺度變換：F'=Fk3、指數(shù)尺度變換：F=exp(beitaF)六、約束條件處理1、搜索空間限定法：對遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個個體的點與解空間中的表示一個可行解的點有一一對應(yīng)關(guān)系。2、可行解變換法：在由個體基因型向個