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

1、遺傳算法的根本原理和方法一、編碼編碼：把一個(gè)問題的可行解從其解空間轉(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)定性.動(dòng)態(tài)參數(shù)編碼(D

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

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

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

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

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

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

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

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

10、個(gè)體編碼串進(jìn)行解碼處理后,可得到個(gè)體的表現(xiàn)型.2、由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值.3、根據(jù)最優(yōu)化問題的類型,由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)那么求出個(gè)體的適應(yīng)度.適應(yīng)度函數(shù)的設(shè)計(jì)主要應(yīng)滿足以下要求：1、單值、連續(xù)、非負(fù)、最大化.2、合理、一致性.較難.3、計(jì)算量小.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):在遺傳算法的不同階段,對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小.常用的尺度變換方法如下：1、線性尺度變換：F,= a F + b2 乘籍尺度變換：F,=F '3 指數(shù)尺度變換：F'=exp(beitaF)六、約束條件處理1、搜索空間限定法：對(duì)遺傳算法的搜索空間的大小加以限制,使得搜索空間中表示一個(gè)個(gè)體的點(diǎn)與解空 間中的表示一個(gè)可行解的點(diǎn)有一一對(duì)應(yīng)關(guān)系.2、可行解變換法：在由個(gè)體基因型