遺傳算法講義

遺傳算法講義遺傳算法1基本概念2選擇算子3交叉算子4變異算子5基本遺傳算法

6基本實(shí)現(xiàn)技術(shù)7遺傳算法應(yīng)用

遺傳算法生物進(jìn)化自然法則優(yōu)勝劣汰適者生存有性繁殖基因通過(guò)有性繁殖不斷進(jìn)行混合和重組遺傳算法從生物界按照自然選擇和有性繁殖、遺傳變異的自然進(jìn)化現(xiàn)象中得到啟發(fā)，而設(shè)計(jì)的一種優(yōu)化搜索算法遺傳算法應(yīng)用函數(shù)優(yōu)化組合優(yōu)化：旅行商、圖形化分…生產(chǎn)調(diào)度：車(chē)間調(diào)度、生產(chǎn)規(guī)劃…自動(dòng)控制：控制器、參數(shù)辨識(shí)…機(jī)器人智能控制：機(jī)器人路徑規(guī)劃、運(yùn)動(dòng)軌跡規(guī)劃…圖像處理與模式識(shí)別：特征提取、圖像分割…人工生命：進(jìn)化模型、學(xué)習(xí)模型、行為模型…遺傳程序設(shè)計(jì)機(jī)器學(xué)習(xí)1基本概念

個(gè)體個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象（一般就是問(wèn)題的解）的一種稱(chēng)呼一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)種群

種群(population)就是模擬生物種群而由若干個(gè)體組成的群體它一般是整個(gè)搜索空間的一個(gè)很小的子集通過(guò)對(duì)種群實(shí)施遺傳操作，使其不斷更新?lián)Q代而實(shí)現(xiàn)對(duì)整個(gè)論域空間的搜索1基本概念

適應(yīng)度(fitness)借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度，而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度適應(yīng)度函數(shù)(fitnessfunction)問(wèn)題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系一般是一個(gè)實(shí)值函數(shù)，且一般大于零該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)1基本概念

染色體(chromosome)染色體是由若干基因組成的位串（生物學(xué)）個(gè)體對(duì)象由若干字符串組成來(lái)表示（遺傳算法）遺傳算法(geneticalgorithm)染色體就是問(wèn)題中個(gè)體的某種字符串形式的編碼表示染色體以字符串來(lái)表示基因是字符串中的一個(gè)個(gè)字符個(gè)體染色體

9----

1001

（2，5，6）----0101011101基本概念

遺傳算子(geneticoperator)選擇(selection)交叉(crossover)變異(mutation)2選擇算子選擇算子模擬生物界優(yōu)勝劣汰的自然選擇法則的一種染色體運(yùn)算從種群中選擇適應(yīng)度較高的染色體進(jìn)行復(fù)制，以生成下一代種群算法：個(gè)體適應(yīng)度計(jì)算在被選集中每個(gè)個(gè)體具有一個(gè)選擇概率選擇概率取決于種群中個(gè)體的適應(yīng)度及其分布個(gè)體適應(yīng)度計(jì)算，即個(gè)體選擇概率計(jì)算個(gè)體選擇方法按照適應(yīng)度進(jìn)行父代個(gè)體的選擇2選擇算子個(gè)體適應(yīng)度計(jì)算按比例的適應(yīng)度計(jì)算(proportionalfitnessassignment)基于排序的適應(yīng)度計(jì)算(rank-basedfitnessassignment)個(gè)體選擇方法輪盤(pán)賭選擇(roulettewheelselection)隨機(jī)遍歷抽樣(stochasticuniversalsampling)局部選擇(localselection)截?cái)噙x擇(truncationselection)錦標(biāo)賽選擇(tournamentselection)2.1按比例的適應(yīng)度計(jì)算算法：對(duì)一個(gè)規(guī)模為N的種群S，按每個(gè)染色體xiS的選擇概率P(xi)所決定的選中機(jī)會(huì)，分N次從S中隨機(jī)選擇N個(gè)染色體，并進(jìn)行復(fù)制

其中：f為適應(yīng)度函數(shù)

f(xi)為xi的適應(yīng)度優(yōu)勝劣汰概率越高，隨機(jī)選中概率越大概率越高，選中次數(shù)越多適應(yīng)度高的染色體后代越多2.2輪盤(pán)賭選擇原理：做一個(gè)單位圓，然后按各個(gè)染色體的選擇概率將圓面劃分為相應(yīng)的扇形區(qū)域轉(zhuǎn)動(dòng)輪盤(pán)，輪盤(pán)靜止時(shí)指針指向某一扇區(qū)，即為選中扇區(qū)，相應(yīng)的個(gè)體/染色體即被選中

2.2輪盤(pán)賭選擇算法：在[0,1]區(qū)間，產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r若rq1，則染色體1被選中若qk-1<

rqk(2kN)，則染色體k被選中其中qi為染色體xi(i=1,2,…,n)的累積概率一個(gè)染色體xi被選中的次數(shù)，可由期望值e(xi)來(lái)確定

為種群S中全體染色體的平均適應(yīng)度

2.2輪盤(pán)賭選擇上述輪盤(pán)選擇過(guò)程，可描述如下：Ⅰ.順序累計(jì)群體內(nèi)各個(gè)體的適應(yīng)度，得相應(yīng)的累計(jì)值Si，最后一個(gè)累計(jì)值為SnⅡ.在[0,Sn]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)rⅢ.依次用Si與r比較，第一個(gè)出現(xiàn)Si大于或等于r的個(gè)體j被選為復(fù)制對(duì)象Ⅳ.重復(fù)Ⅲ、Ⅳ項(xiàng)，直至新群體的個(gè)體數(shù)目等于父代群體的規(guī)模3交叉算子交叉算子交叉又稱(chēng)重組，是按概率交換兩個(gè)個(gè)體的某一位或幾位，體現(xiàn)信息的交換組合出新的個(gè)體，實(shí)現(xiàn)在串行空間上的有效搜索生成新個(gè)體的主要方法3交叉算子單點(diǎn)雜交產(chǎn)生一個(gè)在1到L－1之間的隨機(jī)數(shù)i配對(duì)的兩個(gè)串相互對(duì)應(yīng)的交換從i＋1到L的位段3交叉算子例3.1

設(shè)染色體s1=1011011100

染色體s2=0001110011交換其后2位基因s1:1011011100s1’：1011011111s2：0001110011s2’：0001110000單點(diǎn)交叉4變異算子變異算子突變改變?nèi)旧w某個(gè)/些位上的基因隨機(jī)化算子，生成新個(gè)體次要算子，但在恢復(fù)群體中失去的多樣性方面具有潛在的作用4變異算子例1

設(shè)染色體s=1011011100

s1:1011011100s1’：1011011000二進(jìn)制變異5基本遺傳算法遺傳算法對(duì)種群中的染色體反復(fù)做三種遺傳操作使其朝著適應(yīng)度增高的方向不斷更新?lián)Q代，直至出現(xiàn)了適應(yīng)度滿足目標(biāo)條件的染色體為止算法拓展遺傳算法在自然與社會(huì)現(xiàn)象模擬、工程計(jì)算等方面得到了廣泛的應(yīng)用基本遺傳算法是Holland提出的一種統(tǒng)一的最基本的遺傳算法，簡(jiǎn)稱(chēng)SGA（SimpleGeneticAlgorithm)、CGA（CanonicalGeneticAlgorithm）其它的“GA類(lèi)”算法稱(chēng)為GAs(GeneticAlgorithms）,可以把GA看作是GAs的一種特例

5基本遺傳算法參數(shù)種群規(guī)模種群的大小，用染色體個(gè)數(shù)表示最大換代數(shù)種群更新?lián)Q代的上限，也是算法終止一個(gè)條件交叉率Pc參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例取值范圍：變異率Pm發(fā)生變異的基因位數(shù)占全體染色體的基因總位數(shù)的比例取值范圍：染色體編碼長(zhǎng)度L

5基本遺傳算法算法

步1：在論域空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc，

變異率Pm，代數(shù)Gen步2：

隨機(jī)產(chǎn)生U中的N個(gè)染色體s1,s2…sN,組成初始種群S={s1,s2…sN}，置代

數(shù)t=1步3：若終止條件滿足，則取S中適應(yīng)度最大的染色體作為所求結(jié)果，算法結(jié)束步4：計(jì)算S中每個(gè)染色體的適應(yīng)度f(wàn)()步5：

按選擇概率p(si)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選中1個(gè)染色體并將

其復(fù)制，共做N次，然后將復(fù)制得到的N染色體組成群體S1步6：按Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對(duì)

進(jìn)行交叉操作，并用產(chǎn)生的染色體代替原染色體，組成群體S2步7：按Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異

操作，并用產(chǎn)生的新染色體代替原染色體，組成群體S3步8：將群體S3作為新種群，即用S3代替S，Gen=Gen+1，轉(zhuǎn)步35流程圖計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評(píng)價(jià)滿足終止條件嗎？終止選擇雜交變異Y基本遺傳算法的算法流程圖編碼和生成初始種群N選擇6基本實(shí)現(xiàn)技術(shù)編碼方法二進(jìn)制編碼格雷編碼編碼規(guī)則應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案應(yīng)使用能使問(wèn)題得到自然表示或描述的具有最小編碼字符集的編碼方案6基本實(shí)現(xiàn)技術(shù)適應(yīng)值函數(shù)適應(yīng)值函數(shù)必須是正數(shù)出現(xiàn)負(fù)數(shù)時(shí)應(yīng)進(jìn)行變換，常用變換方式有三種：線性比例法：g(x)=a*f(x)+b(b>0)指數(shù)比例法：g(x)=exp(af(x))(a0)冪指數(shù)比例法：g(x)=(f(x))a(a為偶數(shù))7算法舉例例2

利用遺傳算法求解區(qū)間[0,31]上的二次函數(shù)y=x2的最大值分析原問(wèn)題轉(zhuǎn)化為[0,31]中尋找能使y取最大值的點(diǎn)x區(qū)間[0,31]為論域空間/解空間x為個(gè)體對(duì)象函數(shù)f(x)=x2

可作為適應(yīng)度函數(shù)7算法舉例解：定義適應(yīng)度函數(shù)，編碼染色體適應(yīng)度函數(shù)取f(x)=x2

用5位二進(jìn)制數(shù)作為個(gè)體x的基因型編碼/染色體設(shè)定種群規(guī)模，產(chǎn)生初始種群種群規(guī)模N=4初始種群S={s1=01101(13),s2=11000(24)，s3=01000(8)，s4=10011(19)}7算法舉例計(jì)算各代種群中各染色體的適應(yīng)度，并進(jìn)行遺傳操作

選擇設(shè)從區(qū)間[0,1]產(chǎn)生4個(gè)隨機(jī)數(shù)r1=0.45,r2=0.11,r3=0.57,r4=0.98按輪盤(pán)賭選擇法，染色體s1,s2，s3，s4依次選中次數(shù)為1，2，0，1選擇產(chǎn)生種群S1={s1=11000(24),s2=01101(13)，s3=11000(24)，s4=10011(19)}染色體適應(yīng)度選擇概率累積概率估計(jì)選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0017算法舉例

交叉設(shè)交叉率Pc=100%,即S1全部染色體參與交叉將s1與s2配對(duì)，s3與s4配對(duì)，交換后兩位基因新種群S2={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}變異設(shè)變異率Pm=0.001種群變異基因位數(shù)：Pm*L*N=0.001*5*4=0.020.02不足1，本輪不做變異--------------第一代遺傳操作完成----------------第二代種群S={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}7算法舉例選擇設(shè)從區(qū)間[0,1]產(chǎn)生4個(gè)隨機(jī)數(shù)r1=0.25,r2=0.41,r3=0.77,r4=0.98按輪盤(pán)賭選擇法，染色體s1,s2，s3，s4依次選中次數(shù)為1，1，1，1選擇產(chǎn)生種群S1={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}染色體適應(yīng)度選擇概率累積概率估計(jì)選中次數(shù)s1=110016250.360.361s2=011001440.080.441s3=110117290.410.851s4=100002560.151.0017算法舉例

交叉將s1與s2配對(duì)，s3與s4配對(duì)，交換后三位基因新種群S2={s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)}變異種群變異基因位數(shù)：Pm*L*N=0.001*5*4=0.020.02不足1，本輪不做變異--------------第二代遺傳操作完成----------------第三代種群S={s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)}7算法舉例選擇設(shè)從區(qū)間[0,1]產(chǎn)生4個(gè)隨機(jī)數(shù)r1=0.25,r2=0.41,r3=0.77,r4=0.98按輪盤(pán)賭選擇法，染色體s1,s2，s3，s4依次選中次數(shù)為2，0，1，1選擇產(chǎn)生種群S1={s1=11100(28),s2=11100(28)，s3=11000(24)，s4=10011(19)}染色體適應(yīng)度選擇概率累積概率估計(jì)選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0017算法舉例

交叉將s1與s4配對(duì)，s2與s3配對(duì)，交換后兩位基因新種群S2={s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)}變異種群變異基因位數(shù)：Pm*L*N=0.001*5*4=0.020.02不足1，本輪不做變異--------------第三代遺傳操作完成----------------第四代種群S={s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)}7算法舉例在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。將染色體“11111”解碼為表現(xiàn)型，得所求最優(yōu)解：31將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961

7算法舉例YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度遺傳算法在圖像分割中的應(yīng)用

圖像分割是自動(dòng)目標(biāo)識(shí)別的關(guān)鍵和首要步驟,其目的是將目標(biāo)和背景分離,為計(jì)算機(jī)視覺(jué)的后續(xù)處理提供依據(jù)。通常圖像分割包括閾值法、邊緣檢測(cè)法和區(qū)域跟蹤法。其中閾值法是圖像分割的常用方法。目前，已有眾多的閾值分割方法，如最小誤差閾值法、最大類(lèi)別方差法(Otsu法)及最佳直方圖熵法。最佳熵閾值方法(簡(jiǎn)稱(chēng)為KSW熵法)不需要先驗(yàn)知識(shí)，而且對(duì)于非理想雙峰直方圖的圖像也可以進(jìn)行分割。但在確定閾值時(shí)，尤其是確定多閾值時(shí)，計(jì)算量很大。遺傳算法是一具有魯棒性、并行性的優(yōu)化算法,因此利用遺傳算法實(shí)現(xiàn)KSW最佳熵閾值確定法，可以縮短尋找閾值的時(shí)間，從而有利于計(jì)算機(jī)視覺(jué)的后續(xù)處理遺傳算法在圖像分割中的應(yīng)用圖像分割的定義

圖像分割是將圖像分成若干個(gè)互不相交的各具特性的區(qū)域，并提取出感興趣目標(biāo)的技術(shù)和過(guò)程?；叶葓D像分割的依據(jù)

圖像局部特性的相似性和互斥性可作為圖像分割的依據(jù)，即：區(qū)域內(nèi)部的灰度相似性和區(qū)域之間的灰度突變性。遺傳算法在圖像分割中的應(yīng)用圖像分割的分類(lèi)基于閾值的分割——通過(guò)閾值對(duì)不同物體進(jìn)行分割基于邊緣的分割——先確定邊緣像素，并把它們連接在一起，以構(gòu)成所需的邊界基于區(qū)域的分割——把各像素劃歸到各個(gè)物體或區(qū)域中遺傳算法在圖像分割中的應(yīng)用閾值分割的原理

利用圖像中要提取的目標(biāo)物與其背景在灰度特性上的差異，把圖像視為具有不同灰度級(jí)的兩類(lèi)區(qū)域(目標(biāo)和背景)的組合，選取一個(gè)合適的閾值，以確定圖像中每個(gè)象素點(diǎn)應(yīng)該屬于目標(biāo)還是背景區(qū)域，從而產(chǎn)生相應(yīng)的二值圖像。遺傳算法在圖像分割中的應(yīng)用

設(shè)原始圖像f(x,y)，以一定的準(zhǔn)則在f(x,y)中找出一個(gè)合適的灰度值，作為閾值T，則分割后的圖像g(x,y)，可由下式表示：g(x,y)=1f(x,y)≥T0f(x,y)<Tg(x,y)=1f(x,y)≤T0f(x,y)>Tg(x,y)=1T1≤f(x,y)≤T20其它g(x,y)=f(x,y)f(x,y)≥T0其它遺傳算法在圖像分割中的應(yīng)用閾值化分割算法主要有兩個(gè)步驟：(1)確定需要的分割閾值；(2)將分割閾值與像素值比較以劃分像素。遺傳算法在圖像分割中的應(yīng)用根據(jù)Shannon熵的概念,對(duì)于灰度范圍{0,1,?,L-1}的圖像直方圖,其熵測(cè)量為所謂灰度的一維熵最大：就是選擇一個(gè)閾值，使圖像用這個(gè)閾值分割出的兩部分的一階灰度統(tǒng)計(jì)的信息量最大。遺傳算法在圖像分割中的應(yīng)用

目標(biāo)區(qū)域和背景區(qū)域的熵分別定義為：其中PiiOBt一維直方圖遺傳算法在圖像分割中的應(yīng)用

定義熵函數(shù)為：其中當(dāng)熵函數(shù)取最大值時(shí)對(duì)應(yīng)的灰度值t*就是所求的最佳閾值，即：目標(biāo)函數(shù)圖像分割實(shí)例（1）編碼：由于圖像灰度值在0～255之間，故將各個(gè)染色體編碼為8位二進(jìn)制碼，它代表某個(gè)分割閾值。（2）初始種群：隨機(jī)產(chǎn)生。初始種群的個(gè)體為隨機(jī)產(chǎn)生的,其相應(yīng)的適應(yīng)度值也各有高低。設(shè)置種群大小為10，最大繁