遺傳算法基礎(chǔ)

1、遺傳算法基礎(chǔ)講解人：蔡亮1遺傳算法的產(chǎn)生 50，60年代 Holland 提出遺傳算法 60年代中期 Holland的學(xué)生J.D.Bagley 提出“遺傳算法” 一詞 70年代 Holland 模式定理 Adaptation in Natural and Artificial Systems發(fā)表Holland的學(xué)生De Jong 將遺傳算法用于最優(yōu)化問題 Grefenstette 開發(fā)了第一個遺傳算法軟件 2遺傳算法的發(fā)展 Evolutionary Computationcomputational intelligence 3遺傳算法的生物學(xué)基礎(chǔ) 生物進(jìn)化理論與遺傳學(xué) 達(dá)爾文的進(jìn)化論 達(dá)爾文（

2、1858）的自然選擇學(xué)說包括：1遺傳2變異3生存斗爭和適者生存遺傳學(xué)1866孟德爾提出的分離律和自由組合律，奠定了現(xiàn)代遺傳學(xué)的基礎(chǔ) 摩爾根進(jìn)一步確立了染色體的遺傳學(xué)說，認(rèn)為遺傳性狀是由基因決定4遺傳算法的生物學(xué)基礎(chǔ)遺傳學(xué)的基本結(jié)論生物的所有遺傳信息都包含在其染色體中,染色體決定了生物的性狀染色體是由基因及其由規(guī)律的排列所構(gòu)成.遺傳和進(jìn)化過程發(fā)生在染色體上生物的繁殖過程是由基因的復(fù)制過程來完成的通過同源染色體間的交叉和變異會產(chǎn)生新的物種,使生物呈現(xiàn)新的性狀對環(huán)境適應(yīng)性好的基因或染色體比適應(yīng)性差的基因或染色體有更多的機(jī)會遺傳到下一代5遺傳算法的生物學(xué)基礎(chǔ) 生物進(jìn)化理論與遺傳學(xué)現(xiàn)代綜合進(jìn)化論 沒有所

3、謂生存斗爭的問題，單是個體繁殖機(jī)會的差異也能造成后代基因庫組成的改變，自然選擇也能夠進(jìn)行生物的進(jìn)化實(shí)際上是種群的進(jìn)化每一代個體基因型的改變會影響種群基因庫的組成種群基因庫的進(jìn)化就是種群的進(jìn)化基因庫+適者繁殖=群體進(jìn)化6遺傳算法的生物學(xué)基礎(chǔ) 生物進(jìn)化理論與遺傳學(xué)非達(dá)爾文式進(jìn)化理論 1.分子進(jìn)化中性理論 2.跳躍進(jìn)化理論 3.間斷平衡進(jìn)化理論非漸變進(jìn)化理論的核心基礎(chǔ)仍然是自然選擇7遺傳算法的生物進(jìn)化模型現(xiàn)代綜合進(jìn)化論選擇優(yōu)勝劣汰遺傳保持優(yōu)良特性變異產(chǎn)生新特性8遺傳算法的基本術(shù)語編碼：從問題域到遺傳域的映射。即性狀與基因的DNA序列的映射 解碼：從遺傳域到問題域的映射。即將DNA序列解釋成個體的性狀

4、適應(yīng)度：種群的某個個體對生存環(huán)境的適應(yīng)程度。適應(yīng)度高的個體可以獲得更多的繁殖機(jī)會，而適應(yīng)度低的個體，其繁殖機(jī)會就會比較少，甚至逐漸滅絕 選擇：以一定概率從種群中選擇若干個體的操作。一般而言，選擇就是基于適應(yīng)度的優(yōu)勝劣汰的過程 交叉：有性生殖生物在繁殖下一時兩個同源染色體之間通過交叉而重組，即在兩個染色體的相同位置處DNA被切斷，前后兩串分別交叉組合形成新的染色體 9遺傳算法的基本思想10遺傳算法的流程圖編碼解碼11遺傳算法基本要素與實(shí)現(xiàn)技術(shù)編碼與解碼問題域（解空間） 優(yōu)化變量 遺傳域（基因空間）優(yōu)化變量的代碼表示映射二進(jìn)制編碼浮點(diǎn)數(shù)編碼符號編碼12編碼與解碼二進(jìn)制編碼二進(jìn)制編碼是遺傳算法中最常

5、用、最原始的一種編碼方法，它將原問題的解空間映射到二進(jìn)制空間上，然后進(jìn)行遺傳操作。找到最優(yōu)個體后再通過解碼過程還原原始的數(shù)據(jù)形式進(jìn)行適應(yīng)度評價二進(jìn)制編碼的串長度 取決于求解的精度 編碼公式解碼公式13編碼與解碼浮點(diǎn)編碼個體的基因值用某一范圍內(nèi)決策變量的一個浮點(diǎn)數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。浮點(diǎn)編碼使用的是決策變量的真實(shí)值2.509.543.250.254.257.00X:某個優(yōu)化問題含有6個變量，則它的一個基因表達(dá)為對應(yīng)的表現(xiàn)型為 x=2.50,9.54,3.25,0.25,4.25,7.0014編碼與解碼符號編碼個體基因值取自一個無數(shù)值含意，而只有代碼含義的符號集。符號集可以

6、是字母，也可以是數(shù)字序號。如血型A，B，AB，O可以分別用a,b,c,d表示，或者a1,a2,a3,a4,也可表示為1，2，3，415遺傳算法基本要素與實(shí)現(xiàn)技術(shù)最小與最大的轉(zhuǎn)化個體適應(yīng)度評價 為正確計(jì)算個體的遺傳概率，個體的適應(yīng)度必須為正數(shù)或者為零，不能為負(fù)數(shù)而目標(biāo)函數(shù)在尋優(yōu)區(qū)間有一下三種狀態(tài)：16個體適應(yīng)度評價F（x）f（x）CF（x）F（x）F（x）17遺傳算法基本要素與實(shí)現(xiàn)技術(shù)選擇算子適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大，適應(yīng)度較低的個體被遺傳到下一代群體中的概率較小。選擇方法 比例選擇法（輪盤賭） 錦標(biāo)賽選擇法 18比例選擇法（輪盤賭）基本思想 各個個體被選中的概率與其適應(yīng)度

7、大小成正比。設(shè)群體大小為 ，個體 的適應(yīng)度大小為 ，則 個體 被選中的概率為 19比例選擇法（輪盤賭）具體步驟 1）計(jì)算各基因適應(yīng)度值和選擇概率 2）累計(jì)所有基因選擇概率值，記錄中間累 加值S - mid 和最后累加值 sum = 3）產(chǎn)生一個隨機(jī)數(shù) N，0 N 1 4）選擇對應(yīng)中間累加值S - mid 的基因進(jìn)入交換集 5）重復(fù)（3）和（4），直到獲得足夠的基因。20比例選擇法（輪盤賭）舉例染色體的適應(yīng)度和所占的比例21錦標(biāo)賽選擇法基本思想 每次隨機(jī)選取n個個體，比較之后選擇其中適應(yīng)度最高的個體做為下一代種群的父本22遺傳算法基本要素與實(shí)現(xiàn)技術(shù)交叉算子 選擇是對優(yōu)秀個體的復(fù)制，不能產(chǎn)生新個體

8、，交叉對相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉操作是產(chǎn)生新個體的主要方法主要問題 如何對染色體進(jìn)行配對 如果確定交叉點(diǎn)的位置 如何進(jìn)行部分基因交換23隨機(jī)配對將選擇出的種群中的M個個體以隨即的方式組成M/2對配對個體組，交叉操作就是在這些配對個體組中的兩個個體之間進(jìn)行24二進(jìn)制編碼染色體的交叉單點(diǎn)交叉 基因位數(shù)為 ，交叉點(diǎn)k的范圍為1, -1,在該點(diǎn)為分界相互交換變量例如：子個體1 0 1 1 1 0 1 0 0 1 0 1子個體2 1 0 1 0 1 0 1 1 0 1 025二進(jìn)制編碼染色體的交叉多點(diǎn)交叉多點(diǎn)交叉的破壞性可以促進(jìn)解空間的搜索26二進(jìn)制編碼染

9、色體的交叉均勻交叉 兩個配對個體的染色體每個基因位以相同的交叉概率進(jìn)行交換具體步驟隨機(jī)產(chǎn)生一個與個體編碼串長度等長的屏蔽字W按下列規(guī)則交叉兩個父本的基因若 =0，則父代第i個基因相互交換若 =1，則父代第i個基因不相互交換27均勻交叉例如28浮點(diǎn)編碼染色體的交叉線性交叉交叉公式子個體父個體1F(父個體2-父個體1)F為0,1間的均勻分布隨機(jī)數(shù)29浮點(diǎn)編碼染色體的交叉中間交叉交叉公式子個體i父個體1iF(父個體2i-父個體1i)30遺傳算法基本要素與實(shí)現(xiàn)技術(shù)變異算子 將個體染色體編碼串中的某些基因位編碼字符集的其它字符替換二進(jìn)制編碼染色體的變異 編碼字符集為0,1,變異操作就是將變異點(diǎn)上的基因取

10、反 變異點(diǎn)是按概率Pm在染色體基因位上指定的31二進(jìn)制編碼染色體的變異具體步驟隨機(jī)產(chǎn)生一個與個體編碼串長度等長的屏蔽字W 為0,1間的隨機(jī)數(shù)按下列規(guī)則對基因進(jìn)行變異若 Pm，則父代基因第i位變異若 Pm，則父代基因第i位不變異32浮點(diǎn)編碼染色體的變異浮點(diǎn)編碼變異33遺傳算法的數(shù)學(xué)基礎(chǔ)模式定理模式 定義：種群中的個體即基因串中相同的結(jié)構(gòu)例如：(以二進(jìn)制編碼為例) 假設(shè)編碼基因串長度為5模式H1 1 * * 0描述了在基因位1，2取值為“1”，在基因位5取值為“0”的所有個體的集合11000，11010 ，11100 ，11110 34模式定理結(jié)論1定義在長度為 的二進(jìn)制編碼基因串上的模式共有證明

11、：在長為 的基因串中任選定k位作為模式中的確定位，則這樣的模式共有 有二項(xiàng)式定理35模式定理模式階 定義：在模式H中具有確定基因值的位置數(shù)目稱為該模式的模式階，記為例如：基因長度固定時，模式階越高，能與該模式匹配的樣本基因就越少36模式定理模式定義長度定義：模式H中第一個確定基因值的位置和最后一個確定基因值的位置之間的距離，稱為該模式的模式定義長度，記為例如：37模式定理引入模式的概念后，我們將遺傳算法看作是對模式的一種運(yùn)算。某一模式H的各個樣本經(jīng)過選擇，交叉，變異運(yùn)算后，得到一些新的樣本和新的模式。符號說明假定在給定的時刻t，一個特定的模式H有m個代表串包含在種群 中，記為m(H,t)。種群

12、個體 的適應(yīng)度為 ，個體總數(shù)記為n，模式H的平均適應(yīng)度記為 ，種群的平均適應(yīng)度為38模式定理選擇算子的作用若 1，m（H，t）增加若 1，m（H，t）減少在選擇算子的作用下，對于平均適用度高于群體平均適應(yīng)度的模式，其樣本數(shù)將增長，對于平均適用度低于群體平均適應(yīng)度的模式，其樣本數(shù)將減少39模式定理交叉算子的作用（單點(diǎn)交叉）模式H1被破壞的幾率大于模式H2一般地，模式H被破壞的幾率小于 ，考慮到交叉操作是按照交叉概率Pc進(jìn)行的，所以模式H的生存概率大于40模式定理變異算子的作用此時若某一模式被破壞，則必然是模式描述形式中的確定位發(fā)生了改變，破壞發(fā)生概率為 當(dāng) 有則模式生存概率為41模式定理綜合選擇，交叉，變異操作下，種群中模式H的子代樣本數(shù)目為結(jié)論二：模式定理遺傳算法中，在選擇，交叉和變異算子的作用下，具有低階，短的定義長度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將逐代增加42遺傳算法的數(shù)學(xué)基礎(chǔ)收斂性分析遺傳算法的收斂性定義