最的遺傳算法教程實(shí)用教案

1、會(huì)計(jì)學(xué)1最的遺傳算法教程最的遺傳算法教程(jiochng)第一頁(yè)，共29頁(yè)。全局(qunj)優(yōu)化方法1）不依賴(lài)于初始條件；2）不與求解空間有緊密關(guān)系，對(duì)解域，無(wú)可微或連續(xù)的要求。求 解穩(wěn)健，但收斂(shulin)速度慢。能獲得全局最優(yōu)。適合于求解空間不知的情況第1頁(yè)/共29頁(yè)第二頁(yè)，共29頁(yè)。 選擇運(yùn)算 交換操作(cozu) 變異遺傳算法的基本(jbn)運(yùn)算遺傳算法基本原理 模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個(gè)(y )向量染色體，向量的每個(gè)元素稱(chēng)為基因。 通過(guò)不斷計(jì)算各染色體的適應(yīng)值，選擇最好的染色體，獲得最優(yōu)解。第2頁(yè)/共29頁(yè)第三頁(yè)，共29頁(yè)。選擇運(yùn)

2、算 從舊的種群中選擇適應(yīng)度高的染色體，放入匹配(ppi)集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體作準(zhǔn)備。選擇方法適應(yīng)度比例法（轉(zhuǎn)輪法）按各染色體適應(yīng)度大小比例來(lái)決定其被選擇數(shù)目(shm)的多少。某染色體被選的概率：Pc)()(iicxfxfPxi 為種群(zhn qn)中第i個(gè)染色體，第3頁(yè)/共29頁(yè)第四頁(yè)，共29頁(yè)。具體步驟1）計(jì)算各染色體適應(yīng)度值2）累計(jì)所有染色體適應(yīng)度值，記錄中間累加值S - mid 和最 后累加值 sum = f(xi)3） 產(chǎn)生一個(gè)隨機(jī)數(shù) N，0 N sum 4） 選擇對(duì)應(yīng)中間累加值S - mid 的第一個(gè)染色體進(jìn)入交換集 5） 重復(fù)(chngf)（3）和

3、（4），直到獲得足夠的染色體。舉例：具有(jyu)6個(gè)染色體的二進(jìn)制編碼、適應(yīng)度值、Pc累計(jì) 值。第4頁(yè)/共29頁(yè)第五頁(yè)，共29頁(yè)。染色體的 適應(yīng)度和所占的比例(bl)用轉(zhuǎn)輪方法(fngf)進(jìn)行選擇第5頁(yè)/共29頁(yè)第六頁(yè)，共29頁(yè)。染色體編號(hào) 1 2 3 4 5 6 7 8 9 10適應(yīng)度 8 217 7 212117 3 7被選概率0.10.020.22 0.09 0.02 0.16 0.14 0.09 0.03 0.09適應(yīng)度累計(jì) 8 10 27 34 36 48 59 66 6976隨機(jī)數(shù)23497613 1 2757所選染色體號(hào)碼 3 710 3 1 3 7染色體被選的概率(gil)被

4、選的染色體個(gè)數(shù)10個(gè)染色體種群按比例(bl)的選擇過(guò)程第6頁(yè)/共29頁(yè)第七頁(yè)，共29頁(yè)。交換(jiohun)操作 方法:隨機(jī)選擇(xunz)二個(gè)染色體(雙親染色體),隨機(jī)指定一點(diǎn)或多點(diǎn), 進(jìn)行交換,可得二個(gè)新的染色體(子輩染色體).新的子輩染色體: A 11010001 B 01011110模擬(mn)生物在自然界環(huán)境變化,引起基因的突變.在染色體二進(jìn)制編碼中,1變成0;或0變成1.突變產(chǎn)生染色體的多樣性,避免進(jìn)化中早期成熟,陷入局部極值點(diǎn),突變的概率很低.變異復(fù)制不能創(chuàng)新,交換解決染色體的創(chuàng)新第7頁(yè)/共29頁(yè)第八頁(yè)，共29頁(yè)。GA的流程(lichng)第8頁(yè)/共29頁(yè)第九頁(yè)，共29頁(yè)。簡(jiǎn)單(

5、jindn)遺傳算法（GA）的基本參數(shù)種群(zhn qn)規(guī)模 P: 參與進(jìn)化的染色體總數(shù).代溝G: 二代之間不相同的染色體數(shù)目,無(wú)重疊G = 1; 有重疊 0 G 1選擇方法: 轉(zhuǎn)輪法,精英選擇法,競(jìng)爭(zhēng)法.交換率: Pc 一般為60100%.變異率: Pm 一般為0.110%舉例(j l):變異概率取0.001第9頁(yè)/共29頁(yè)第十頁(yè)，共29頁(yè)。初始(ch sh)種群和它的適應(yīng)度值染色體的交換(jiohun)操縱第10頁(yè)/共29頁(yè)第十一頁(yè)，共29頁(yè)。舉例(j l)：14第11頁(yè)/共29頁(yè)第十二頁(yè)，共29頁(yè)。步驟1）編碼(bin m)：確定二進(jìn)制的位數(shù)；組成個(gè)體（染色體）位的二進(jìn)制的值，的第是相

6、應(yīng)于。和分別為和的最大值和最小值。是和或是，精度二進(jìn)制位數(shù)取決于運(yùn)算nqbqqqqqyxqqbqqqqqnNnnnnn08 , 212 12 minmaxminmax10minminmaxminmax步驟2）選擇種群(zhn qn)數(shù)P 和初始個(gè)體，計(jì)算適應(yīng)度值， P = 20；第12頁(yè)/共29頁(yè)第十三頁(yè)，共29頁(yè)。步驟3）確定選擇(xunz)方法；交換率PC；變異率Pm。選擇(xunz)方法用競(jìng)爭(zhēng)法； PC = 0.7, Pm = 0.05計(jì)算(j sun)結(jié)果： 8代后，f(x,y) =0.998757, 41代后，f(x,y) =1.00000, x =3.000290, y =2.99

7、9924. 160次適應(yīng)度計(jì)算(j sun)，達(dá)到最優(yōu)值。遺傳算法的基本(jbn)數(shù)學(xué)問(wèn)題一個(gè)重要的定理圖式定理什么叫圖式？（插入演示）演示12第13頁(yè)/共29頁(yè)第十四頁(yè)，共29頁(yè)。圖式染色體子集 10*1*1*1 1001111110111110111010010010101001101110染色體長(zhǎng)度字符集元素?cái)?shù)目為圖式數(shù)目 1LkQkQL圖式 *0111000*10*0*1*01110004321HHHHA（*為通配符）第14頁(yè)/共29頁(yè)第十五頁(yè)，共29頁(yè)。圖式(t sh)的描述： 定義長(zhǎng)度(chngd)（H)H左右二端有定義位置之間的距離； 圖式(t sh)的階次(或固定長(zhǎng)度)O(H）

8、H中非*位（有定義位） 的個(gè)數(shù)。圖式定理的推導(dǎo)圖式在選擇過(guò)程中的增加.第15頁(yè)/共29頁(yè)第十六頁(yè)，共29頁(yè)。 ,/ )(),( / )(),( /)(),( )()()() 1,(1,是種群平均適應(yīng)度）（）是種群中染色體的個(gè)數(shù)（ffHftHmnfHftHmnfnHftHmxfhfnhpntHmiiniiHPhiiHPhiisii經(jīng)過(guò)選擇,在t+1代,圖式(t sh)H的數(shù)量m(H,t+1)為: 第16頁(yè)/共29頁(yè)第十七頁(yè)，共29頁(yè)。圖式在交換(jiohun)中的破壞圖式(t sh)在變異中的破壞經(jīng)過(guò)選擇、交換、變異后在t+1中，圖式(t sh)H的數(shù)量：)(1)(1 )(),() 1,(mcP

9、HOLHPfHftHmtHm圖式定理：在選擇、交換、變異的作用下，階次低、定義長(zhǎng)度短、適應(yīng)度高的圖式（模塊）將按指數(shù)增長(zhǎng)的規(guī)律，一代一代地增長(zhǎng)。第17頁(yè)/共29頁(yè)第十八頁(yè)，共29頁(yè)。遺傳算法在應(yīng)用(yngyng)中的一些基本問(wèn)題1）知識(shí)(zh shi)的編碼 2）適應(yīng)度函數(shù)(hnsh)。 a) 適應(yīng)度函數(shù)(hnsh)值必須非負(fù)。根據(jù)情況做適當(dāng)?shù)奶幚?二進(jìn)制和十進(jìn)制的比較：二進(jìn)制有更多圖式和更大的搜索范圍；十進(jìn)制更接近于實(shí)際操作。12 minmaxlUUQ精度是二進(jìn)制的長(zhǎng)度小值。分別為變量的最大和最和 minmaxlUU第18頁(yè)/共29頁(yè)第十九頁(yè)，共29頁(yè)。第19頁(yè)/共29頁(yè)第二十頁(yè)，共29頁(yè)。

10、3）全局最優(yōu)和收斂性。 根據(jù)圖式(t sh)定理，對(duì)于具有“欺騙性”函數(shù)，GA有可能落入局部最優(yōu)點(diǎn)。avgmavgavgfCfffbabaffmax 的選擇滿(mǎn)足以下條件：和。，所希望的復(fù)制的數(shù)目是最好種群數(shù)目情況下 mC0 .22 .1mC第20頁(yè)/共29頁(yè)第二十一頁(yè)，共29頁(yè)。欺騙性函數(shù)欺騙性函數(shù)(hnsh) 圖式劃分：指引相互之間競(jìng)爭(zhēng)(jngzhng)的定義位為同一集合的一組圖式。 如#表示定義位，則H1=*1*0*，H2=*0*1* ，H3=*1*1*， H4=*0*0* 同屬于劃分*#*#*。 總平均適應(yīng)度（OAF）：對(duì)一個(gè)給定(i dn)圖式，OAF即為其成員 的平均適應(yīng)度。 欺騙性

11、函數(shù)包含全局最優(yōu)的圖式其OAF不如包含局部最優(yōu)的OAF，這種劃分稱(chēng)為欺騙劃分，它會(huì)使GA陷入局部最優(yōu)。如最高階欺騙函數(shù)有k個(gè)定義位，則此函數(shù)稱(chēng)k階欺騙。第21頁(yè)/共29頁(yè)第二十二頁(yè)，共29頁(yè)。舉例：3位欺騙(qpin)函數(shù)第22頁(yè)/共29頁(yè)第二十三頁(yè)，共29頁(yè)。 高級(jí)(goj)GA算法1）操作(cozu)的改進(jìn)2）算法(sun f)的改進(jìn)選擇方法改進(jìn)：精英法（競(jìng)賽法）、置換式和非置換式 隨機(jī)選擇法，排序法。交換方法的改進(jìn)：多點(diǎn)交換；重組運(yùn)算微種群遺傳算法（GA）雙種群遺傳算法（DPGA）重組運(yùn)算：解決染色體分布過(guò)于集中問(wèn)題。把適應(yīng)度函數(shù)做進(jìn)一步處理。njjiiisxxdsxfxf1),(/)(

12、)(是共享度函數(shù) )(ds第23頁(yè)/共29頁(yè)第二十四頁(yè)，共29頁(yè)。終止條件：1）達(dá)到預(yù)定指標(biāo)(zhbio)；2）達(dá)到預(yù)定代數(shù)。GA算法(sun f)第24頁(yè)/共29頁(yè)第二十五頁(yè)，共29頁(yè)。雙種群(zhn qn)算法（ DPGA）基本思想(sxing)：利用人類(lèi)社會(huì)分工合作的機(jī)理。分成：全局種群粗搜索(su su)，尋找可能存在的最優(yōu)區(qū)域； 局部種群 精搜索(su su)在全局劃定的區(qū)域內(nèi)，尋找最優(yōu)點(diǎn)。第25頁(yè)/共29頁(yè)第二十六頁(yè)，共29頁(yè)。 100 ,100 0.1)(50sin()(100 ,100 )(001.00.15.0sin5.0536.65 ,536.65 )(1 0.002 2.048 , 2.048 ) (1 ) ( 100211.0222125.02221421