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

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

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

3、數(shù)級聯(lián)編碼：對含有多個變量的個體進(jìn)行編碼的方法.通常將各個參數(shù)分別以某種編碼方法進(jìn)行 編碼,然后再將他們的編碼根據(jù)一定順序連接在一起就組成了表示全部參數(shù)的個體編碼.5、 多參數(shù)交叉編碼：將各個參數(shù)中起主要作用的碼位集中在一起,這樣它們就不易于被遺傳算子破壞掉.評估編碼的三個標(biāo)準(zhǔn)：完備性、健全性、非冗余性.二、選擇遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一 種遺傳運(yùn)算,用來確定重組或交叉?zhèn)€體,以及被選個體將產(chǎn)生多少個子代個體.常用的選擇算子：1、 輪盤賭選擇(Roulette Wheel Selection):是一種回放式隨機(jī)采樣方法.每個個體進(jìn)

4、入下一代的概率等 于它的適應(yīng)度值與整個種群中個體適應(yīng)度值和的比例.選擇誤差較大.2、 隨機(jī)競爭選擇(Stochastic Tournament):每次按輪盤賭選擇一對個體,然后讓這兩個個體進(jìn)行競爭, 適應(yīng)度高的被選中,如此反復(fù),直到選滿為止.3、最正保證存選擇：首先按輪盤賭選擇方法執(zhí)行遺傳算法的選擇操作,然后將當(dāng)前群體中適應(yīng)度最高的個 體結(jié)構(gòu)完整地復(fù)制到下一代群體中.4、 無回放隨機(jī)選擇(也叫期望值選擇Excepted Value Selection):根據(jù)每個個體在下一代群體中的生存 期望來進(jìn)行隨機(jī)選擇運(yùn)算.方法如下(1) 計算群體中每個個體在下一代群體中的生存期望數(shù)目No(2) 假設(shè)某一個

5、體被選中參與交叉運(yùn)算,那么它在下一代中的生存期望數(shù)目減去0.5,假設(shè)某一個體未被選中參與交叉運(yùn)算,那么它在下一代中的生存期望數(shù)目減去1.0o(3) 隨著選擇過程的進(jìn)行,假設(shè)某一個體的生存期望數(shù)目小于0時,那么該個體就不再有時機(jī)被選中.5、確定式選擇：根據(jù)一種確定的方式來進(jìn)行選擇操作.具體操作過程如下：(1) 計算群體中各個個體在下一代群體中的期望生存數(shù)目No(2) 用N的整數(shù)局部確定各個對應(yīng)個體在下一代群體中的生存數(shù)目.(3) 用N的小數(shù)局部對個體進(jìn)行降序排列,順序取前M個個體參加到下一代群體中.至此可完全確定出下一代群體中M個個體.6、無回放余數(shù)隨機(jī)選擇：可保證適應(yīng)度比平均適應(yīng)度大的一些個體

6、能夠被遺傳到下一代群體中,因而選擇誤差比較小.7、均勻排序：對群體中的所有個體按期適應(yīng)度大小進(jìn)行排序,基于這個排序來分配各個個體被選中的概 率.8、最正保證存策略：當(dāng)前群體中適應(yīng)度最高的個體不參與交叉運(yùn)算和變異運(yùn)算,而是用它來代替掉本代群體中經(jīng)過交叉、變異等操作后所產(chǎn)生的適應(yīng)度最低的個體.9、隨機(jī)聯(lián)賽選擇：每次選取幾個個體中適應(yīng)度最高的一個個體遺傳到下一代群體中10、排擠選擇：新生成的子代將代替或排擠相似的舊父代個體,提升群體的多樣性.三、交叉遺傳算法的交叉操作,是指對兩個相互配對的染色體按某種方式相互交換其局部基因,從而形成兩個新的 個體.適用于二進(jìn)制編碼個體或浮點(diǎn)數(shù)編碼個體的交叉算子：1、

7、 單點(diǎn)交叉(One pointCrossover):指在個體編碼串中只隨機(jī)設(shè)置一個交叉點(diǎn), 然后再該點(diǎn)相互交換兩個配對個體的局部染色體.2、兩點(diǎn)交叉與多點(diǎn)交叉：(1 )兩點(diǎn)交叉(Two pointCrossover):在個體編碼串中隨機(jī)設(shè)置了兩個交叉點(diǎn),然后再進(jìn)行局部基因交換.(2 )多點(diǎn)交叉(Multi-pointCrossover)3、均勻交叉(也稱一致交叉,Uniform Crossover):兩個配對個體的每個基因座上 的基因都以相同的交叉概率進(jìn)行交換,從而形成兩個新個體.4、 算術(shù)交叉(ArithmeticCrossover):由兩個個體的線性組合而產(chǎn)生出兩個新 的個體.該操作對象一

8、般是由浮點(diǎn)數(shù)編碼表示的個體.四、變異 遺傳算法中的變異運(yùn)算,是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基 因來替換,從而形成以給新的個體.以下變異算子適用于二進(jìn)制編碼和浮點(diǎn)數(shù)編碼的個體：1、根本位變異(Simple Mutation):對個體編碼串中以變異概率、隨機(jī)指定的某一位 或某幾位僅因座上的值做變異運(yùn)算.2、均勻變異(Uni form Mutation):分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù),以某 一較小的概率來替換個體編碼串中各個基因座上的原有基因值.(特別適用于在算法的初級運(yùn)行階段)3、邊界變異(Boundary Mutatio n):隨機(jī)的取基因座上的兩個

9、對應(yīng)邊界基因值之一 去替代原有基因值.特別適用于最優(yōu)點(diǎn)位于或接近于可行解的邊界時的一類問題.4、非均勻變異：對原有的基因值做一隨機(jī)擾動,以擾動后的結(jié)果作為變異后的新基因值.對每個基因座 都以相同的概率進(jìn)行變異運(yùn)算之后,相當(dāng)于整個解向量在解空間中作了一次稍微的變動. .一 ？. . 5、高斯近似變異：進(jìn)行變異操作時用符號均值為P的平均值,方差為P的正態(tài)分布的一個隨機(jī)數(shù)來替換原有的基因值.五、適應(yīng)度函數(shù)適應(yīng)度函數(shù)也稱評價函數(shù),是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個體好壞的標(biāo)準(zhǔn).適應(yīng)度函數(shù)總是非負(fù) 的,而目標(biāo)函數(shù)可能有正有負(fù),故需要在目標(biāo)函數(shù)與適應(yīng)度函數(shù)之間進(jìn)行變換.評價個體適應(yīng)度的一般過程為:1、對

10、個體編碼串進(jìn)行解碼處理后,可得到個體的表現(xiàn)型.2、由個體的表現(xiàn)型可計算出對應(yīng)個體的目標(biāo)函數(shù)值.3、根據(jù)最優(yōu)化問題的類型,由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)那么求出個體的適應(yīng)度.適應(yīng)度函數(shù)的設(shè)計主要應(yīng)滿足以下要求：1、單值、連續(xù)、非負(fù)、最大化.2、合理、一致性.較難.3、計算量小.4、通用性強(qiáng).由目標(biāo)函數(shù)f (x)到適應(yīng)度函數(shù)F it (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ù)為最小化問題問題：可能不滿足常用的輪盤賭選擇中概率非負(fù)的要求；某攜帶求解的函數(shù)在函數(shù)值分布上相差很大,由 此得到的平均適應(yīng)度可能不利于表達(dá)種群的平均性能.2、做轉(zhuǎn)換.(具體轉(zhuǎn)換方法略)3、同2 ,轉(zhuǎn)換公式不同適應(yīng)度尺度變換(FitnessScaling Trans form):在遺傳算法的不同階段,對個體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小.常用的尺度變換方法如下：1、線性尺度變換：F,= a F + b2 乘籍尺度變換：F,=F '3 指數(shù)尺度變換：F'=exp(beitaF)六、約束條件處理1、搜索空間限定法：對遺傳算法的搜索空間的大小加以限制,使得搜索空間中表示一個個體的點(diǎn)與解空 間中的表示一個可行解的點(diǎn)有一一對應(yīng)關(guān)系.2、可行解變換法：在由個體基因型