信息工程概論課件 第十一講 機(jī)器學(xué)習(xí)-遺傳算法_第1頁
信息工程概論課件 第十一講 機(jī)器學(xué)習(xí)-遺傳算法_第2頁
信息工程概論課件 第十一講 機(jī)器學(xué)習(xí)-遺傳算法_第3頁
信息工程概論課件 第十一講 機(jī)器學(xué)習(xí)-遺傳算法_第4頁
信息工程概論課件 第十一講 機(jī)器學(xué)習(xí)-遺傳算法_第5頁
已閱讀5頁,還剩27頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第11講機(jī)器學(xué)習(xí)-遺傳算法個(gè)體與種群●個(gè)體就是模擬生物個(gè)體而對(duì)問題中的對(duì)象(一般就是問題的解)的一種稱呼,一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)?!穹N群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。11.1基本概念2信息科學(xué)導(dǎo)論適應(yīng)度與適應(yīng)度函數(shù)●適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,而對(duì)問題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。●適應(yīng)度函數(shù)(fitnessfunction)就是問題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。11.1基本概念3信息科學(xué)導(dǎo)論染色體與基因染色體(chromosome)就是問題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因(gene)。例如:個(gè)體染色體

9----1001(2,5,6)----01010111011.1基本概念4信息科學(xué)導(dǎo)論遺傳操作

亦稱遺傳算子(geneticoperator),就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作:●選擇-復(fù)制(selection-reproduction)●交叉(crossover,亦稱交換、交配或雜交)●變異(mutation,亦稱突變)11.1基本概念5信息科學(xué)導(dǎo)論

選擇-復(fù)制通常做法是:對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xi∈S的選擇概率P(xi)所決定的選中機(jī)會(huì),分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。

這里的選擇概率P(xi)的計(jì)算公式為11.1基本概念6信息科學(xué)導(dǎo)論

交叉就是互換兩個(gè)染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。例如,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即11.1基本概念7信息科學(xué)導(dǎo)論變異就是改變?nèi)旧w某個(gè)(些)位上的基因。例如,設(shè)染色體s=11001101將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。11.1基本概念8信息科學(xué)導(dǎo)論

遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束11.2基本遺傳算法9信息科學(xué)導(dǎo)論

算法中的一些控制參數(shù):■

種群規(guī)?!?/p>

最大換代數(shù)■

交叉率(crossoverrate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例,記為Pc,取值范圍一般為0.4~0.99。

變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例,記為Pm,取值范圍一般為0.0001~0.1。11.2基本遺傳算法10信息科學(xué)導(dǎo)論步1

在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x),給定種群規(guī)模N,交叉率Pc和變異率Pm,代數(shù)T;步2

隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN,組成初始種群S={s1,s2,…,sN},置代數(shù)計(jì)數(shù)器t=1;步3

計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f();步4

若終止條件滿足,則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果,算法結(jié)束。11.2基本遺傳算法11信息科學(xué)導(dǎo)論

步5

按選擇概率P(xi)所決定的選中機(jī)會(huì),每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制,共做N次,然后將復(fù)制所得的N個(gè)染色體組成群體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,t=t+1,轉(zhuǎn)步3。11.2基本遺傳算法12信息科學(xué)導(dǎo)論

利用遺傳算法求解區(qū)間[0,31]上的二次函數(shù)y=x2的最大值。y=x2

31

XY11.3遺傳算法應(yīng)用舉例13信息科學(xué)導(dǎo)論分析

原問題可轉(zhuǎn)化為在區(qū)間[0,31]中搜索能使y取最大值的點(diǎn)a的問題。那么,[0,31]

中的點(diǎn)x就是個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度,區(qū)間[0,31]就是一個(gè)(解)空間

。11.3遺傳算法應(yīng)用舉例

(1)設(shè)定種群規(guī)模,編碼染色體,產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4;用5位二進(jìn)制數(shù)編碼染色體;取下列個(gè)體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)14信息科學(xué)導(dǎo)論(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù):f(x)=x2(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31(11111))出現(xiàn)為止。11.3遺傳算法應(yīng)用舉例15信息科學(xué)導(dǎo)論首先計(jì)算種群S1中各個(gè)體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應(yīng)度f(si)。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36111.3遺傳算法應(yīng)用舉例16信息科學(xué)導(dǎo)論再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.3111.3遺傳算法應(yīng)用舉例17信息科學(xué)導(dǎo)論

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法11.3遺傳算法應(yīng)用舉例18信息科學(xué)導(dǎo)論在算法中賭輪選擇法可用下面的子過程來模擬:

①在[0,1]區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為11.3遺傳算法應(yīng)用舉例19信息科學(xué)導(dǎo)論選擇-復(fù)制

設(shè)從區(qū)間[0,1]中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=01101

169

0.14

0.14

1s2=11000

576

0.49

0.63

2s3=01000

64

0.06

0.69

0s4=10011

361

0.31

1.00

111.3遺傳算法應(yīng)用舉例20信息科學(xué)導(dǎo)論于是,經(jīng)復(fù)制得群體:s1’=11000(24),s2’=01101(13)

s3’=11000(24),s4’=10011(19)11.3遺傳算法應(yīng)用舉例交叉

設(shè)交叉率pc=100%,即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì),s3’與s4’配對(duì)。分別交換后兩位基因,得新染色體:

s1’’=11001(25),s2’’=01100(12)

s3’’=11011(27),s4’’=10000(16)21信息科學(xué)導(dǎo)論變異

設(shè)變異率pm=0.001。這樣,群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位,所以本輪遺傳操作不做變異。于是,得到第二代種群S2:

s1=11001(25),s2=01100(12)

s3=11011(27),s4=10000(16)11.3遺傳算法應(yīng)用舉例22信息科學(xué)導(dǎo)論

第二代種群S2中各染色體的情況染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=11001

625

0.36

0.36

1s2=01100

144

0.08

0.44

0s3=11011

729

0.41

0.85

2s4=10000

256

0.15

1.00

111.3遺傳算法應(yīng)用舉例23信息科學(xué)導(dǎo)論假設(shè)這一輪選擇-復(fù)制操作中,種群S2中的4個(gè)染色體都被選中,則得到群體:

s1’=11001(25),s2’=01100(12)

s3’=11011(27),s4’=10000(16)做交叉運(yùn)算,讓s1’與s2’,s3’與s4’

分別交換后三位基因,得

s1’’=11100(28),s2’’=01001(9)

s3’’=11000(24),s4’’=10011(19)這一輪仍然不會(huì)發(fā)生變異。

11.3遺傳算法應(yīng)用舉例24信息科學(xué)導(dǎo)論于是,得第三代種群S3:

s1=11100(28),s2=01001(9)

s3=11000(24),s4=10011(19)11.3遺傳算法應(yīng)用舉例第三代種群S3中各染色體的情況染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=11100

784

0.44

0.44

2s2=01001

81

0.04

0.48

0s3=11000

576

0.32

0.80

1s4=10011

361

0.20

1.00

125信息科學(xué)導(dǎo)論設(shè)這一輪的選擇-復(fù)制結(jié)果為:

s1’=11100(28),s2’=11100(28)

s3’=11000(24),s4’=10011(19)做交叉運(yùn)算,讓s1’與s4’,s2’與s3’

分別交換后兩位基因,得

s1’’=11111(31),s2’’=11100(28)

s3’’=11000(24),s4’’=10000(16)這一輪仍然不會(huì)發(fā)生變異。11.3遺傳算法應(yīng)用舉例26信息科學(xué)導(dǎo)論于是,得第四代種群S4:

s1=11111(31),s2=11100(28)

s3=11000(24),s4=10000(16)顯然,在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是,遺傳操作終止,將染色體“11111”作為最終結(jié)果輸出。然后,將染色體“11111”解碼為表現(xiàn)型,即得所求的最優(yōu)解:31。將31代入函數(shù)y=x2中,即得原問題的解,即函數(shù)y=x2的最大值為961。11.3遺傳算法應(yīng)用舉例27信息科學(xué)導(dǎo)論YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代種群及其適應(yīng)度11.3遺傳算法應(yīng)用舉例28信息科學(xué)導(dǎo)論

◆遺傳算法的主要特點(diǎn)

——遺傳算法一般是直接在解空間搜索,而不像圖搜索那樣一般是在問題空間搜索,最后才找到解。

——遺傳算法的搜索隨

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論