遺傳算法基礎(chǔ)

遺傳算法基礎(chǔ)第一頁，共四十四頁，編輯于2023年，星期三遺傳算法的產(chǎn)生

50，60年代Holland提出遺傳算法

60年代中期Holland的學(xué)生J.D.Bagley提出“遺傳算法”一詞

70年代Holland模式定理《AdaptationinNaturalandArtificialSystems》發(fā)表Holland的學(xué)生DeJong將遺傳算法用于最優(yōu)化問題Grefenstette開發(fā)了第一個(gè)遺傳算法軟件第二頁，共四十四頁，編輯于2023年，星期三遺傳算法的發(fā)展

EvolutionaryComputationcomputationalintelligence

第三頁，共四十四頁，編輯于2023年，星期三遺傳算法的生物學(xué)基礎(chǔ)

生物進(jìn)化理論與遺傳學(xué)

達(dá)爾文的進(jìn)化論

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

生物進(jìn)化理論與遺傳學(xué)現(xiàn)代綜合進(jìn)化論

沒有所謂生存斗爭(zhēng)的問題，單是個(gè)體繁殖機(jī)會(huì)的差異也能造成后代基因庫組成的改變，自然選擇也能夠進(jìn)行生物的進(jìn)化實(shí)際上是種群的進(jìn)化每一代個(gè)體基因型的改變會(huì)影響種群基因庫的組成種群基因庫的進(jìn)化就是種群的進(jìn)化基因庫+適者繁殖=群體進(jìn)化第六頁，共四十四頁，編輯于2023年，星期三遺傳算法的生物學(xué)基礎(chǔ)

生物進(jìn)化理論與遺傳學(xué)非達(dá)爾文式進(jìn)化理論1.分子進(jìn)化中性理論2.跳躍進(jìn)化理論3.間斷平衡進(jìn)化理論非漸變進(jìn)化理論的核心基礎(chǔ)仍然是自然選擇第七頁，共四十四頁，編輯于2023年，星期三遺傳算法的生物進(jìn)化模型現(xiàn)代綜合進(jìn)化論選擇優(yōu)勝劣汰遺傳保持優(yōu)良特性變異產(chǎn)生新特性第八頁，共四十四頁，編輯于2023年，星期三遺傳算法的基本術(shù)語編碼：從問題域到遺傳域的映射。即性狀與基因的DNA序列的映射解碼：從遺傳域到問題域的映射。即將DNA序列解釋成個(gè)體的性狀適應(yīng)度：種群的某個(gè)個(gè)體對(duì)生存環(huán)境的適應(yīng)程度。適應(yīng)度高的個(gè)體可以獲得更多的繁殖機(jī)會(huì)，而適應(yīng)度低的個(gè)體，其繁殖機(jī)會(huì)就會(huì)比較少，甚至逐漸滅絕選擇：以一定概率從種群中選擇若干個(gè)體的操作。一般而言，選擇就是基于適應(yīng)度的優(yōu)勝劣汰的過程交叉：有性生殖生物在繁殖下一時(shí)兩個(gè)同源染色體之間通過交叉而重組，即在兩個(gè)染色體的相同位置處DNA被切斷，前后兩串分別交叉組合形成新的染色體第九頁，共四十四頁，編輯于2023年，星期三遺傳算法的基本思想第十頁，共四十四頁，編輯于2023年，星期三遺傳算法的流程圖編碼解碼第十一頁，共四十四頁，編輯于2023年，星期三遺傳算法基本要素與實(shí)現(xiàn)技術(shù)編碼與解碼問題域（解空間）優(yōu)化變量遺傳域（基因空間）優(yōu)化變量的代碼表示映射二進(jìn)制編碼浮點(diǎn)數(shù)編碼符號(hào)編碼第十二頁，共四十四頁，編輯于2023年，星期三編碼與解碼二進(jìn)制編碼二進(jìn)制編碼是遺傳算法中最常用、最原始的一種編碼方法，它將原問題的解空間映射到二進(jìn)制空間上，然后進(jìn)行遺傳操作。找到最優(yōu)個(gè)體后再通過解碼過程還原原始的數(shù)據(jù)形式進(jìn)行適應(yīng)度評(píng)價(jià)二進(jìn)制編碼的串長(zhǎng)度取決于求解的精度編碼公式解碼公式第十三頁，共四十四頁，編輯于2023年，星期三編碼與解碼浮點(diǎn)編碼個(gè)體的基因值用某一范圍內(nèi)決策變量的一個(gè)浮點(diǎn)數(shù)來表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。浮點(diǎn)編碼使用的是決策變量的真實(shí)值2.509.543.250.254.257.00X:某個(gè)優(yōu)化問題含有6個(gè)變量，則它的一個(gè)基因表達(dá)為對(duì)應(yīng)的表現(xiàn)型為x=[2.50,9.54,3.25,0.25,4.25,7.00]第十四頁，共四十四頁，編輯于2023年，星期三編碼與解碼符號(hào)編碼個(gè)體基因值取自一個(gè)無數(shù)值含意，而只有代碼含義的符號(hào)集。符號(hào)集可以是字母，也可以是數(shù)字序號(hào)。如血型A，B，AB，O可以分別用[a,b,c,d]表示，或者[a1,a2,a3,a4],也可表示為[1，2，3，4]第十五頁，共四十四頁，編輯于2023年，星期三遺傳算法基本要素與實(shí)現(xiàn)技術(shù)最小與最大的轉(zhuǎn)化個(gè)體適應(yīng)度評(píng)價(jià)為正確計(jì)算個(gè)體的遺傳概率，個(gè)體的適應(yīng)度必須為正數(shù)或者為零，不能為負(fù)數(shù)而目標(biāo)函數(shù)在尋優(yōu)區(qū)間有一下三種狀態(tài)：第十六頁，共四十四頁，編輯于2023年，星期三個(gè)體適應(yīng)度評(píng)價(jià)F（x）＝f（x）＋CF（x）F（x）F（x）第十七頁，共四十四頁，編輯于2023年，星期三遺傳算法基本要素與實(shí)現(xiàn)技術(shù)選擇算子適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大，適應(yīng)度較低的個(gè)體被遺傳到下一代群體中的概率較小。選擇方法比例選擇法（輪盤賭）錦標(biāo)賽選擇法

第十八頁，共四十四頁，編輯于2023年，星期三比例選擇法（輪盤賭）基本思想

各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。設(shè)群體大小為，個(gè)體的適應(yīng)度大小為，則個(gè)體被選中的概率為第十九頁，共四十四頁，編輯于2023年，星期三比例選擇法（輪盤賭）具體步驟

1）計(jì)算各基因適應(yīng)度值和選擇概率

2）累計(jì)所有基因選擇概率值，記錄中間累加值S-mid和最后累加值sum=∑3）產(chǎn)生一個(gè)隨機(jī)數(shù)N，0〈N〈14）選擇對(duì)應(yīng)中間累加值S-mid的基因進(jìn)入交換集

5）重復(fù)（3）和（4），直到獲得足夠的基因。第二十頁，共四十四頁，編輯于2023年，星期三比例選擇法（輪盤賭）舉例染色體的適應(yīng)度和所占的比例第二十一頁，共四十四頁，編輯于2023年，星期三錦標(biāo)賽選擇法基本思想每次隨機(jī)選取n個(gè)個(gè)體，比較之后選擇其中適應(yīng)度最高的個(gè)體做為下一代種群的父本第二十二頁，共四十四頁，編輯于2023年，星期三遺傳算法基本要素與實(shí)現(xiàn)技術(shù)交叉算子選擇是對(duì)優(yōu)秀個(gè)體的復(fù)制，不能產(chǎn)生新個(gè)體，交叉對(duì)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉操作是產(chǎn)生新個(gè)體的主要方法主要問題如何對(duì)染色體進(jìn)行配對(duì)如果確定交叉點(diǎn)的位置如何進(jìn)行部分基因交換第二十三頁，共四十四頁，編輯于2023年，星期三隨機(jī)配對(duì)將選擇出的種群中的M個(gè)個(gè)體以隨即的方式組成M/2對(duì)配對(duì)個(gè)體組，交叉操作就是在這些配對(duì)個(gè)體組中的兩個(gè)個(gè)體之間進(jìn)行第二十四頁，共四十四頁，編輯于2023年，星期三二進(jìn)制編碼染色體的交叉單點(diǎn)交叉

基因位數(shù)為，交叉點(diǎn)k的范圍為[1,-1],在該點(diǎn)為分界相互交換變量例如：子個(gè)體101110100101子個(gè)體210101011010第二十五頁，共四十四頁，編輯于2023年，星期三二進(jìn)制編碼染色體的交叉多點(diǎn)交叉多點(diǎn)交叉的破壞性可以促進(jìn)解空間的搜索第二十六頁，共四十四頁，編輯于2023年，星期三二進(jìn)制編碼染色體的交叉均勻交叉

兩個(gè)配對(duì)個(gè)體的染色體每個(gè)基因位以相同的交叉概率進(jìn)行交換具體步驟隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼串長(zhǎng)度等長(zhǎng)的屏蔽字W＝按下列規(guī)則交叉兩個(gè)父本的基因若=0，則父代第i個(gè)基因相互交換若=1，則父代第i個(gè)基因不相互交換第二十七頁，共四十四頁，編輯于2023年，星期三均勻交叉例如第二十八頁，共四十四頁，編輯于2023年，星期三浮點(diǎn)編碼染色體的交叉線性交叉交叉公式子個(gè)體＝父?jìng)€(gè)體1＋F×(父?jìng)€(gè)體2-父?jìng)€(gè)體1)F為[0,1]間的均勻分布隨機(jī)數(shù)第二十九頁，共四十四頁，編輯于2023年，星期三浮點(diǎn)編碼染色體的交叉中間交叉交叉公式子個(gè)體i＝父?jìng)€(gè)體1i＋F×(父?jìng)€(gè)體2i-父?jìng)€(gè)體1i)第三十頁，共四十四頁，編輯于2023年，星期三遺傳算法基本要素與實(shí)現(xiàn)技術(shù)變異算子將個(gè)體染色體編碼串中的某些基因位編碼字符集的其它字符替換二進(jìn)制編碼染色體的變異

編碼字符集為{0,1},變異操作就是將變異點(diǎn)上的基因取反變異點(diǎn)是按概率Pm在染色體基因位上指定的第三十一頁，共四十四頁，編輯于2023年，星期三二進(jìn)制編碼染色體的變異具體步驟隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼串長(zhǎng)度等長(zhǎng)的屏蔽字W＝為[0,1]間的隨機(jī)數(shù)按下列規(guī)則對(duì)基因進(jìn)行變異若Pm，則父代基因第i位變異若>Pm，則父代基因第i位不變異第三十二頁，共四十四頁，編輯于2023年，星期三浮點(diǎn)編碼染色體的變異浮點(diǎn)編碼變異第三十三頁，共四十四頁，編輯于2023年，星期三遺傳算法的數(shù)學(xué)基礎(chǔ)

模式定理模式

定義：種群中的個(gè)體即基因串中相同的結(jié)構(gòu)例如：(以二進(jìn)制編碼為例)假設(shè)編碼基因串長(zhǎng)度為5模式H＝11**0描述了在基因位1，2取值為“1”，在基因位5取值為“0”的所有個(gè)體的集合{11000，11010，11100，11110}第三十四頁，共四十四頁，編輯于2023年，星期三模式定理結(jié)論1定義在長(zhǎng)度為的二進(jìn)制編碼基因串上的模式共有證明：在長(zhǎng)為的基因串中任選定k位作為模式中的確定位，則這樣的模式共有有二項(xiàng)式定理第三十五頁，共四十四頁，編輯于2023年，星期三模式定理模式階

定義：在模式H中具有確定基因值的位置數(shù)目稱為該模式的模式階，記為例如：基因長(zhǎng)度固定時(shí)，模式階越高，能與該模式匹配的樣本基因就越少第三十六頁，共四十四頁，編輯于2023年，星期三模式定理模式定義長(zhǎng)度定義：模式H中第一個(gè)確定基因值的位置和最后一個(gè)確定基因值的位置之間的距離，稱為該模式的模式定義長(zhǎng)度，記為例如：第三十七頁，共四十四頁，編輯于2023年，星期三模式定理引入模式的概念后，我們將遺傳算法看作是對(duì)模式的一種運(yùn)算。某一模式H的各個(gè)樣本經(jīng)過選擇，交叉，變異運(yùn)算后，得到一些新的樣本和新的模式。符號(hào)說明假定在給定的時(shí)刻t，一個(gè)特定的模式H有m個(gè)代表串包含在種群中，記為m(H,t)。種群個(gè)體的適應(yīng)度為，個(gè)體總數(shù)記為n，模式H的平均適應(yīng)度記為，種群的平均適應(yīng)度為第三十八頁，共四十四頁，編輯于2023年，星期三模式定理選擇算子的作用若>1，m（H，t）增加若<1，m（H，t）減少在選擇算子的作用下，對(duì)于平均適用度高于群體平均適應(yīng)度的模式，其樣本數(shù)將增長(zhǎng)，對(duì)于平均適用度低于群體平均適應(yīng)度的模式，其樣本數(shù)將減少第三十九頁，共四十四頁，編輯于2023年，星期三模式定理交叉算子的作用（單點(diǎn)交叉）模式H1被破壞的幾率大于模式H2一般地，模式H被破壞的幾率小于，考慮到交叉操作是按照交叉概率Pc進(jìn)行的，所以模式H的生存概率大于第四十頁，共四十四頁，編輯于2023年，星期三模式定理變異算子的作用此時(shí)若某一模式被破壞，則必然是模式描述形式中的確定位發(fā)生了改變，破壞發(fā)生概率為

當(dāng)有則模式生存概率為第四十一頁，共四十四頁，編輯于2023年，星期三模式定理綜合選擇，交叉，變異操作下，種群中模式H的子代樣本數(shù)目為結(jié)論二：模式定理遺傳算法中，在選擇，交叉和變異算子的作用下，具有低階，短的定義長(zhǎng)度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將逐代增加第四十二頁，共四十四頁，編輯于2023年，星期三遺傳算法的數(shù)學(xué)基礎(chǔ)

收斂性分析遺傳算法的收斂性定義定義一：種群狀態(tài)空間所有可能的種群狀態(tài)的集合稱為種群狀態(tài)空間，它的元素代表一個(gè)種群，這個(gè)種群的個(gè)體就用描述定義二：漸進(jìn)收斂

若算法在t時(shí)刻的種群滿足則成算法漸進(jìn)收斂到經(jīng)典的遺傳算法不具