第4章(3遺傳算法)好文檔.ppt

1、第4章,計(jì)算智能的仿生技術(shù) (3) 遺 傳 算 法,43 遺傳算法,431 遺傳算法原理 432 優(yōu)化模型的遺傳算法求解 433 基于遺傳的分類學(xué)習(xí)系統(tǒng),4.3.1 遺傳算法原理,遺傳算法（Genetic Algorithms,GA）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化搜索算法。 它模擬了生物的繁殖、交配和變異現(xiàn)象，從初始的種群，產(chǎn)生一群更適應(yīng)環(huán)境的后代。,1975年美國(guó)Michigan大學(xué)J.Holland教授提出。 美國(guó)人De.Jong博士將遺傳算法應(yīng)用于函數(shù)優(yōu)化。 Goldberg完成了遺傳算法的框架。,4.3.1.1 遺傳算法概述,遺傳算法（Genetic

2、Algorithms，GA）是一種基于遺傳學(xué)的搜索優(yōu)化算法。 遺傳是作為一種指令碼封裝在每個(gè)染色體（個(gè)體）中，并以基因（位）的形式包含在染色體（個(gè)體）中。 在遺傳算法中，“染色體”對(duì)應(yīng)的是數(shù)據(jù)或數(shù)組，通常是由一維的串結(jié)構(gòu)數(shù)據(jù)來(lái)表現(xiàn)。串上各個(gè)位置對(duì)應(yīng)“基因”，而各位置上的值對(duì)應(yīng)基因的取值?；蚪M成的串就是染色體，或者叫做基因型個(gè)體。一定數(shù)量的個(gè)體組成了群體。,遺傳算法將問(wèn)題的每個(gè)可能的解按某種形式進(jìn)行編碼，編碼后的解稱作染色體（個(gè)體）。 隨機(jī)選取N個(gè)染色體（個(gè)體）構(gòu)成初始種群，再根據(jù)預(yù)定的評(píng)價(jià)函數(shù)對(duì)每個(gè)染色體計(jì)算適應(yīng)值，使得性能較好的染色體具有較高的適應(yīng)值。,選擇適應(yīng)值高的染色體進(jìn)行復(fù)制，通過(guò)遺

3、傳算子：選擇、交叉（重組）、變異，來(lái)產(chǎn)生一群新的更適應(yīng)環(huán)境的染色體，形成新的種群。 這樣一代一代不斷繁殖、進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，求得問(wèn)題的最優(yōu)解。,遺傳算法的處理流程圖,4.3.1.2遺傳算法中的基本要素,遺傳算法中包含了如下五個(gè)基本要素： 1）問(wèn)題編碼 2）初始群體的設(shè)定 3）適應(yīng)值函數(shù)的設(shè)計(jì) 4）遺傳操作設(shè)計(jì) 5）控制參數(shù)設(shè)定（主要是指群體大小和使用遺傳操作的概率等） 這五個(gè)要素構(gòu)成了遺傳算法的核心內(nèi)容。,（1）問(wèn)題編碼,如何將問(wèn)題描述成位串的形式，即問(wèn)題編碼。一般將問(wèn)題中各參數(shù)用二進(jìn)制編碼，構(gòu)成子串，再將子串拼接起來(lái)構(gòu)成“染色體”位串。 不同串長(zhǎng)和不同的碼制，對(duì)問(wèn)題求解

4、的精度和遺傳算法收斂時(shí)間會(huì)有很多影響。 目前也出現(xiàn)采用其它編碼方式，如用向量、規(guī)則來(lái)表示染色體。,（2）初始群體的生成,遺傳算法是群體型操作，這樣必須為遺傳操作準(zhǔn)備一個(gè)由若干初始解組成的初始群體。 初始群體的每個(gè)個(gè)體都是通過(guò)隨機(jī)方法產(chǎn)生的。,（3）適應(yīng)值函數(shù)的確定,適應(yīng)值函數(shù)是根據(jù)目標(biāo)函數(shù)確定的。適應(yīng)值總是非負(fù)的，任何情況下總是希望越大越好。 適應(yīng)值函數(shù)的選取至關(guān)重要，它直接影響到算法的收斂速度即最終能否找到最優(yōu)解。 函數(shù)優(yōu)化問(wèn)題可直接將目標(biāo)函數(shù)本身作為適應(yīng)值函數(shù)。,（4）控制參數(shù),參數(shù)主要有個(gè)體編碼長(zhǎng)度、群體大小M、交叉概率Pc、變異概率Pm、終止代數(shù)T等 這些參數(shù)對(duì)遺傳算法的運(yùn)行影響很大，

5、需要認(rèn)真選擇。,4.3.1.3 遺傳算子,1、選擇(Selection)算子 依據(jù)每個(gè)染色體的適應(yīng)值大小，適應(yīng)值越大，被選中的概率就越大，其子孫在下一代產(chǎn)生的個(gè)數(shù)就越多。 選擇操作是建立在群體中個(gè)體的適應(yīng)值評(píng)估基礎(chǔ)上的，目前常用的選擇算子有適應(yīng)值比例法、最佳個(gè)體保存法、期望值方法等。,2、交叉(Crossover)算子 通過(guò)染色體重組來(lái)產(chǎn)生新一代染色體。 如有兩個(gè)用二進(jìn)制編碼的個(gè)體A和B。 交叉前后為： A=a1a2a3a4a5 A=a1a2a3b4b5 B=b1b2b3b4b5 B=b1b2b3a4a5 (父代) (子代),3、變異(Mutation)算子 變異增加了遺傳算法找到接近最優(yōu)解的

6、能力。 變異就是以很小的概率，隨機(jī)地改變字符串某個(gè)位置上的值。把某一位的內(nèi)容進(jìn)行變異。 在二進(jìn)制編碼中，就是將某位0變成1，1變成0。 如：110010的第四位變異成110110 （父代） （子代）,4.3.1.4 遺傳算法的理論基礎(chǔ),1.模式定理 遺傳算法的理論基礎(chǔ)是Holland提出的模式定理。一個(gè)模式(Schema)就是一個(gè)描述種群中在位串的某些確定位置上具有相似性的位串子集的相似性模板(Similarity Template)。 模式定理是遺傳算法的理論基礎(chǔ)，它說(shuō)明： 高適應(yīng)值、長(zhǎng)度短、階數(shù)低的模式在后代中至少以指數(shù)增長(zhǎng)包含該模式H的位串的數(shù)目。 原因在于遺傳使高適應(yīng)值的模式復(fù)制更多的

7、后代。,2基因塊假設(shè) 高適應(yīng)值、長(zhǎng)度短、低階的模式叫基因塊?；驂K假說(shuō)： 長(zhǎng)度短的、低階的、高適應(yīng)值的模式(基因塊)通過(guò)遺傳操作繁殖、交換、變異，的逐漸進(jìn)化，形成潛在的適應(yīng)性較高的位串。 該假設(shè)指出，通過(guò)遺傳算法能尋找到接近全局最優(yōu)解的能力。,4.3.1.5 遺傳算法的特點(diǎn),遺傳算法是進(jìn)行群體的搜索。 它對(duì)多個(gè)個(gè)體進(jìn)行群體搜索，構(gòu)成一個(gè)不斷進(jìn)化的群體序列，它能找到全局最優(yōu)解（優(yōu)于爬山法） 遺傳算法是一種隨機(jī)搜索方法，三個(gè)算子都是隨機(jī)操作，利用概率轉(zhuǎn)移規(guī)則。,遺傳算法的處理對(duì)象是問(wèn)題參變量進(jìn)行編碼的個(gè)體，而不是參變量自身。 參變量編碼成位串個(gè)體，通過(guò)遺傳算子進(jìn)行操作。不是對(duì)參數(shù)變量進(jìn)行直接操作。

8、 遺傳算法利用適應(yīng)值信息，而不需要導(dǎo)數(shù)或其它輔助信息。 遺傳算法用適應(yīng)值評(píng)估個(gè)體，用遺傳算子產(chǎn)生更優(yōu)后代，不需要像神經(jīng)網(wǎng)絡(luò)中用梯度公式引導(dǎo)。,隱含并行性： 遺傳算法是對(duì)N個(gè)位串個(gè)體進(jìn)行運(yùn)算，它隱含了大量的模式（用通配符#包含的個(gè)體）,4.3.2 優(yōu)化模型的遺傳算法求解,遺傳算法用于優(yōu)化計(jì)算例,例1：求發(fā)f(x)=x2 在0，31上的 最大值。 一、初始種群 1.編碼：用五位二進(jìn)制表示x，有 x=0 0 0 0 0 0 x=31 1 1 1 1 1 2.初始種群 隨機(jī)產(chǎn)生4個(gè)個(gè)體：13 ， 24 ， 8 ，19 3.適應(yīng)值fi 直接用目標(biāo)函數(shù)作為適應(yīng)值：fi=xi2,非負(fù) ; (2)逐步增大 4

9、.選擇率ps和期望值 選擇率： ps=fi/fi 平均適應(yīng)值： f =fi/n 期望值： fi/f 5.實(shí)選值 期望值取整數(shù),初始種群參數(shù)計(jì)算,二、遺傳,說(shuō)明：,1.選擇（繁殖） 在種群眾，實(shí)選值（期望值）高者多繁殖；實(shí)選值（期望值）低者少繁殖或不繁殖。 繁殖（復(fù)制）的個(gè)體放入交配池中。 2.交叉 隨機(jī)選擇交配對(duì)象（相同個(gè)體不交配），如個(gè)體1和2，3 和4。 隨機(jī)選擇交叉點(diǎn)進(jìn)行交叉。,3.變異 取變異概率pe=0.01，表示每100個(gè)體中有一個(gè)個(gè)體的一位發(fā)生變異。（暫不變異） 新的種群，其平均值和最大值都有很大提高。 均值：293 439 最大值：576 729 新種群中四個(gè)個(gè)體，有2個(gè)變好：

10、25，25；2個(gè)變壞：12，16。,三、再遺傳一代,單純用交叉而沒(méi)有用變異，則遺傳多少代得不到最優(yōu)解31(1 1 1 1 1 )。主要是第三位所有個(gè)體都是0，這樣只能得到27（1 1 0 1 1） 次優(yōu)解。 若在第四位中挑選一個(gè)個(gè)體進(jìn)行變異，由0變成1，在進(jìn)行遺傳將會(huì)得到最優(yōu)解。,說(shuō)明：,例2：旅行商路徑問(wèn)題（TSP）,已知n個(gè)城市的地理位置（x,y），求經(jīng)過(guò)所有城市，并回到出發(fā)城市且每個(gè)城市僅經(jīng)過(guò)一次的最短距離。 這是一個(gè)NP完全問(wèn)題，其計(jì)算量為城市個(gè)數(shù)的指數(shù)量級(jí)。現(xiàn)用遺傳算法來(lái)解決這個(gè)問(wèn)題。,1、編碼,每條路徑對(duì)應(yīng)一個(gè)個(gè)體，個(gè)體形式地表示為R=City_No|City_No互不重復(fù)n，n為

11、城市數(shù)。例如對(duì)于n=10的TSP問(wèn)題，對(duì)其中一個(gè)個(gè)體 它表示一條城市路徑： 3 1 5 7 8 9 10 4 2 6,2、適應(yīng)值函數(shù),每個(gè)個(gè)體代表一條可能的路徑。個(gè)體n的適應(yīng)值為： 其中N為種群數(shù)，Dn為 沿個(gè)體標(biāo)示的城市序列的所經(jīng)過(guò)的距離： 其中ni表示個(gè)體中第i位的城市編號(hào)，n11=n1。 適應(yīng)值為非負(fù)，且取值越大越好。 表示所有個(gè)體的路徑長(zhǎng)度的總和,3、交叉,隨機(jī)地從種群中選出要交叉的兩個(gè)不同個(gè)體，隨機(jī)地選取一個(gè)交叉段。交叉段中兩個(gè)個(gè)體的對(duì)應(yīng)部分通過(guò)匹配換位實(shí)現(xiàn)交叉操作。對(duì)個(gè)體A和B： A9 8 4 |5 6 7| 1 3 2 10 B8 7 1 |4 10 3| 2 9 6 5 交叉段

12、 對(duì)個(gè)體A，對(duì)交叉段中由B換位來(lái)的數(shù)，如4、10、3，在A中其它位相同的數(shù)進(jìn)行反交換，即4換為5，10換為6，3換為7；對(duì)個(gè)體B，相似處理，最后得到： A，9 8 5 |4 10 3| 1 7 2 6 B，8 3 1 |5 6 7| 2 9 10 4,4、變異,根據(jù)變異概率Pe，隨機(jī)地從種群中選出要變異的個(gè)體，隨機(jī)地在該個(gè)體上選出變異兩個(gè)位置，然后兩個(gè)位置上的城市序號(hào)進(jìn)行交換。如： A =9 8 4 5 6 7 1 3 2 10 下劃線部分為要變異的兩個(gè)位置。 變異為： A=9 7 4 5 6 8 1 3 2 10,5、遺傳算法結(jié)果,計(jì)算結(jié)果表明： n個(gè)城市的最佳路徑接近一個(gè)外圈無(wú)交叉的環(huán)路。

13、,4.3.3 基于遺傳的分類學(xué)習(xí)系統(tǒng),分類器系統(tǒng)是一種學(xué)習(xí)字符串規(guī)則（又稱分類器）的學(xué)習(xí)系統(tǒng)，它由規(guī)則與消息系統(tǒng)、信任分配系統(tǒng)及遺傳算法三個(gè)主要部分組成，其中規(guī)則與消息系統(tǒng)是產(chǎn)生式系統(tǒng)的一種特殊形式。 產(chǎn)生式規(guī)則的一般形式為： IF THEN 在分類器系統(tǒng)中，對(duì)產(chǎn)生式規(guī)則的語(yǔ)法作了很大的限制，采用了定長(zhǎng)的表示形式，從而適于采用遺傳操作。,4.3.3.1遺傳分類學(xué)習(xí)系統(tǒng) GCLS的基本原理,我們研制的遺傳分類學(xué)習(xí)系統(tǒng)GCLS是一種字符串規(guī)則（分類器）的學(xué)習(xí)系統(tǒng)。 它將規(guī)則“條件condition”和“結(jié)論action”合并成消息個(gè)體，也稱分類器。 適應(yīng)值設(shè)計(jì)成分類器（規(guī)則）覆蓋消息的個(gè)數(shù)，覆蓋消

14、息個(gè)數(shù)越多，規(guī)則的有效性愈大。,GCLS系統(tǒng)由五個(gè)部件組成,檢測(cè)器 消息表 分類器 測(cè)試表 作用器 分類器系統(tǒng)的詳細(xì)結(jié)構(gòu)框圖如下：,分類學(xué)習(xí)系統(tǒng)的工作流程,1. 初始化所有預(yù)置參數(shù)。 2. 將環(huán)境信息放入消息表中。 3. 對(duì)初始種群調(diào)用信任分配算法，修改其中規(guī)則的適應(yīng)值。 4. 對(duì)種群進(jìn)行合并操作，合并后的種群設(shè)為種 群M。,5. 假如種群M已經(jīng)收斂，則復(fù)制該種群的規(guī)則到精煉分類器中，而后跳至步驟（8）。 6. 調(diào)用遺傳算法，生成新一代種群L，將其與種群M合并后送給種群F，從而形成新的初始種群。 7. 返回步驟（3）。 8. 對(duì)測(cè)試表T調(diào)用精煉分類器規(guī)則，生成結(jié)論部分。 9. 將T送往作用器，轉(zhuǎn)換成實(shí)際的輸出值以作用于環(huán)境。,4.3.3.2 遺傳分類器學(xué)習(xí)系統(tǒng) GCLS的應(yīng)用,這是一個(gè)學(xué)習(xí)識(shí)別腦出血和腦血栓兩種疾病的診斷規(guī)則的應(yīng)用實(shí)例。為了作出判斷，應(yīng)當(dāng)考慮如下幾個(gè)方面的特征（屬性）：,編碼原則,獲取知識(shí),1、編碼方式 ：每個(gè)訓(xùn)練例子是由12個(gè)特征和1個(gè) 類別組成。,將例子編碼成二進(jìn)制字符串：消息就是一個(gè)有24位條件，2位結(jié)論組成的二元組。 如上面的例子： M=(010001010101010101100101),(01),獲取知識(shí),本試驗(yàn)在對(duì)30個(gè)訓(xùn)練樣本進(jìn)行學(xué)習(xí)后，