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

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

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

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

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

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

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

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

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

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

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