遺傳算法的實(shí)現(xiàn)及應(yīng)用舉例PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1第1頁/共158頁 0)(00)(,)()(minminminCXfCXfCXfXF當(dāng)當(dāng)，時(shí)時(shí)當(dāng)當(dāng)?shù)?頁/共158頁minC第3頁/共158頁第4頁/共158頁cp第5頁/共158頁mp第6頁/共158頁問題：求問題：求（1）編碼：）編碼： 編碼長度為編碼長度為5（2）初始群體生成：群體大小設(shè)置為）初始群體生成：群體大小設(shè)置為4，隨機(jī)產(chǎn)，隨機(jī)產(chǎn)生四個(gè)個(gè)體：生四個(gè)個(gè)體： 編碼：編碼： 01101，11000，01000，10011 解碼：解碼： 13 24 8 19 適應(yīng)度：適應(yīng)度： 169 576 64 361（3）適應(yīng)度函數(shù)：）適應(yīng)度函數(shù)：31,.,1 , 0,)(max2xxxf1

2、111100000 x2)(xxf第7頁/共158頁（4）輪盤賭輪盤賭選擇：選擇概率選擇：選擇概率 個(gè)體：個(gè)體： 01101，11000，01000，10011 適應(yīng)度：適應(yīng)度： 169 576 64 361 選擇概率：選擇概率：0.14 0.49 0.06 0.31選擇選擇 11000 和和 01101交配產(chǎn)生下一代交配產(chǎn)生下一代ffPii/第8頁/共158頁（5）交叉操作：發(fā)生交叉的概率取大）交叉操作：發(fā)生交叉的概率取大交叉點(diǎn)位置的選取是隨機(jī)的（單點(diǎn)交叉）交叉點(diǎn)位置的選取是隨機(jī)的（單點(diǎn)交叉） 0110 1 0110 0 1100 0 1100 18.0cP第9頁/共158頁（6）變異：發(fā)生

3、變異的概率取小）變異：發(fā)生變異的概率取小改變某個(gè)字節(jié)改變某個(gè)字節(jié) 11001 11101（7）新群體的產(chǎn)生：）新群體的產(chǎn)生： 保留上一代最優(yōu)個(gè)體，保留上一代最優(yōu)個(gè)體，1個(gè)新個(gè)體取代舊個(gè)體個(gè)新個(gè)體取代舊個(gè)體 11101，11000，01000，10011（8）重復(fù)上述操作）重復(fù)上述操作20次，次，或許就能夠得到最優(yōu)解或許就能夠得到最優(yōu)解！ 0001.0mP第10頁/共158頁第11頁/共158頁TSP問題問題問題復(fù)雜度問題復(fù)雜度:指數(shù)增長的！指數(shù)增長的！(NP完全問題完全問題)12個(gè)城市，具有個(gè)城市，具有39916800條不同的路徑條不同的路徑。一條路徑對應(yīng)一個(gè)排列！一條路徑對應(yīng)一個(gè)排列！交叉算

4、子交叉算子傳統(tǒng)的交叉算子可能產(chǎn)生無效路徑。傳統(tǒng)的交叉算子可能產(chǎn)生無效路徑。第12頁/共158頁交叉算子交叉算子（1）基于位置的交叉）基于位置的交叉 把一個(gè)父代在向量上的被選元的位把一個(gè)父代在向量上的被選元的位置強(qiáng)加到另一個(gè)父代。置強(qiáng)加到另一個(gè)父代。父代父代1： 1 2 3 4 5 6 7 8 9 10父代父代2： 5 9 2 4 6 1 10 7 3 8所選位置：所選位置： * * * * 子代子代1： 1 9 2 3 6 4 5 7 8 10子代子代2： 9 2 3 4 5 6 1 8 10 7第13頁/共158頁交叉算子交叉算子（2）部分映射交叉）部分映射交叉利用父代所選段內(nèi)元的對應(yīng)定義子

5、代。利用父代所選段內(nèi)元的對應(yīng)定義子代。父代父代1： 2 6 4 3 8 1 5 10 7 9父代父代2： 8 5 1 10 7 6 2 4 3 9子代子代1： 5 1 4 3 7 6 2 10 8 9子代子代2： 7 2 6 10 8 1 5 4 3 9第14頁/共158頁變異算子變異算子起雙重作用：起雙重作用：1、提供和保持群體的多樣性；、提供和保持群體的多樣性； 2、搜索算子的作用。、搜索算子的作用。(1) 基于位置的變異：基于位置的變異：隨機(jī)選擇兩個(gè)元，隨機(jī)選擇兩個(gè)元，然后把第二個(gè)元放在第一個(gè)元之前；然后把第二個(gè)元放在第一個(gè)元之前；(2) 基于次序的變異：基于次序的變異：隨機(jī)選擇兩個(gè)元，

6、隨機(jī)選擇兩個(gè)元，然后交換他們的位置；然后交換他們的位置；(3) 打亂變異：打亂變異：隨機(jī)選擇一段，然后打亂隨機(jī)選擇一段，然后打亂這段內(nèi)的次序。這段內(nèi)的次序。第15頁/共158頁n二者是同一個(gè)解二者是同一個(gè)解n(n -1)!/2第16頁/共158頁第17頁/共158頁.p1p2pir選擇操作算子選擇操作算子: 輪盤式選擇輪盤式選擇首先計(jì)算每個(gè)個(gè)體首先計(jì)算每個(gè)個(gè)體 i 被選中被選中的概率的概率然后根據(jù)概率的大小將將圓然后根據(jù)概率的大小將將圓盤分為盤分為 n個(gè)扇形，每個(gè)扇形個(gè)扇形，每個(gè)扇形的大小為的大小為 。選擇時(shí)轉(zhuǎn)。選擇時(shí)轉(zhuǎn)動(dòng)輪盤，參考點(diǎn)動(dòng)輪盤，參考點(diǎn)r落到扇形落到扇形i則選擇個(gè)體則選擇個(gè)體i 。

7、 njijfifp1)()(ip 2第18頁/共158頁第19頁/共158頁第20頁/共158頁第21頁/共158頁第22頁/共158頁第23頁/共158頁則用長度為則用長度為10的二進(jìn)制字符串一次的二進(jìn)制字符串一次表征所有離散表征所有離散點(diǎn)點(diǎn)0000000000，000000001，1111110001。,),(minbaxxf 第24頁/共158頁第25頁/共158頁11242322214321xxxxx ,x ,x ,xfy554321x ,x ,x ,x 已知函數(shù)已知函數(shù) 其中其中 ，用遺傳算法求解，用遺傳算法求解y的的最大值。最大值。第26頁/共158頁第27頁/共158頁第28頁/

8、共158頁第29頁/共158頁第30頁/共158頁第31頁/共158頁第32頁/共158頁第33頁/共158頁第34頁/共158頁問題的提出問題的提出 一元函數(shù)求最大值：一元函數(shù)求最大值：2 , 1 0 . 2)10sin()(xxxxf第35頁/共158頁問題的提出問題的提出 用微分法求取用微分法求取 f(x) 的最大值：的最大值： 解有無窮多個(gè)：解有無窮多個(gè)：xxxxxxf10)10tan( 0)10cos(10)10sin()( 即的實(shí)數(shù)遞減序列。一接近于是及，0), 2, 1, 2 , 1( , 2, 1 ,2012 0 , 2 , 1 ,20120iiiixxiixiiiii第36頁

9、/共158頁問題的提出問題的提出 當(dāng)當(dāng)i為奇數(shù)時(shí)為奇數(shù)時(shí)xi對應(yīng)局部極大值點(diǎn)，對應(yīng)局部極大值點(diǎn)，i為偶數(shù)時(shí)為偶數(shù)時(shí)xi對對應(yīng)局部極小值。應(yīng)局部極小值。x19即為區(qū)間即為區(qū)間-1,2內(nèi)的最大值點(diǎn)內(nèi)的最大值點(diǎn) 此時(shí)，函數(shù)最大值此時(shí)，函數(shù)最大值 f(x19) 比比f(1.85)=3.85稍大。稍大。19191985. 12037x第37頁/共158頁編碼編碼 表現(xiàn)型：表現(xiàn)型：x 基因型：二進(jìn)制編碼（串長取決于求解精度）基因型：二進(jìn)制編碼（串長取決于求解精度） 串長與精度之間的關(guān)系串長與精度之間的關(guān)系： 若要求求解精度到若要求求解精度到6位小數(shù)，區(qū)間長度為位小數(shù)，區(qū)間長度為2-(-1)3，即需將區(qū)間分

10、為，即需將區(qū)間分為3/0.000001=3106等份。等份。 所以編碼的二進(jìn)制串長應(yīng)為所以編碼的二進(jìn)制串長應(yīng)為22位。位。419430423000000220971522221第38頁/共158頁產(chǎn)生產(chǎn)生初始種群初始種群 產(chǎn)生的方式：隨機(jī)產(chǎn)生的方式：隨機(jī) 產(chǎn)生的結(jié)果：長度為產(chǎn)生的結(jié)果：長度為22的二進(jìn)制串的二進(jìn)制串 產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50， 1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 00011001

11、01001100000011 0000011010010000000000 第39頁/共158頁計(jì)算適應(yīng)度計(jì)算適應(yīng)度 不同的問題有不同的適應(yīng)度計(jì)算方法不同的問題有不同的適應(yīng)度計(jì)算方法 本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù) 將某個(gè)體轉(zhuǎn)化為將某個(gè)體轉(zhuǎn)化為-1,2區(qū)間的實(shí)數(shù)：區(qū)間的實(shí)數(shù)： s= x=0.637197 計(jì)算計(jì)算x的函數(shù)值（適應(yīng)度）：的函數(shù)值（適應(yīng)度）： f(x)=xsin(10 x)+2.0=2.586345第40頁/共158頁計(jì)算適應(yīng)度計(jì)算適應(yīng)度 二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換： 第一步，將一個(gè)二進(jìn)制串（第一步，將一個(gè)二進(jìn)制串（b21

12、b20b0）轉(zhuǎn)化為）轉(zhuǎn)化為10進(jìn)制數(shù)：進(jìn)制數(shù)： 第二步，第二步，x對應(yīng)的區(qū)間對應(yīng)的區(qū)間-1,2內(nèi)的實(shí)數(shù)：內(nèi)的實(shí)數(shù)：)2()(10210202021xbbbbiii12) 1(20 . 122xx(0000000000000000000000)-1(1111111111111111111111)2第41頁/共158頁遺傳操作遺傳操作 選擇：輪盤賭選擇法；選擇：輪盤賭選擇法； 交叉：單點(diǎn)交叉；交叉：單點(diǎn)交叉； 變異：小概率變異變異：小概率變異第42頁/共158頁模擬結(jié)果模擬結(jié)果 設(shè)置的參數(shù)設(shè)置的參數(shù)： 種群大小種群大小50；交叉概率；交叉概率0.75；變異概率；變異概率0.05；最；最大代數(shù)大代數(shù)

13、200。 得到的最佳個(gè)體得到的最佳個(gè)體： smax=; xmax=1.8506; f(xmax)=3.8503;第43頁/共158頁模擬結(jié)果模擬結(jié)果 進(jìn)化的過程進(jìn)化的過程：世代數(shù)世代數(shù)自變量自變量適應(yīng)度適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503第44頁/共158頁主程序主程序 %用遺傳算法進(jìn)行簡單函數(shù)的優(yōu)化用遺傳算法進(jìn)行簡單函數(shù)的優(yōu)化clearbn=22; %個(gè)體串長度個(gè)體串長度inn=50; %初始種群大小

14、初始種群大小gnmax=200; %最大代數(shù)最大代數(shù)pc=0.75; %交叉概率交叉概率pm=0.05; %變異概率變異概率Continue第45頁/共158頁主程序主程序 %產(chǎn)生初始種群，產(chǎn)生初始種群，0,1向量向量s=round(rand(inn,bn);%計(jì)算適應(yīng)度計(jì)算適應(yīng)度,返回適應(yīng)度返回適應(yīng)度f和累積概率和累積概率pf,p=objf(s); Continue第46頁/共158頁主程序主程序 gn=1;while gngnmax+1 for j=1:2:inn %選擇操作選擇操作 seln=sel(s,p); %交叉操作交叉操作 scro=cro(s,seln,pc); scnew(j

15、,:)=scro(1,:); scnew(j+1,:)=scro(2,:); %變異操作變異操作 smnew(j,:)=mut(scnew(j,:),pm); smnew(j+1,:)=mut(scnew(j+1,:),pm); endContinue第47頁/共158頁主程序主程序 s=smnew; %產(chǎn)生了新的種群產(chǎn)生了新的種群 %計(jì)算新種群的適應(yīng)度計(jì)算新種群的適應(yīng)度 f,p=objf(s); %記錄當(dāng)前代最好和平均的適應(yīng)度記錄當(dāng)前代最好和平均的適應(yīng)度 fmax,nmax=max(f); fmean=mean(f); ymax(gn)=fmax; ymean(gn)=fmean;Conti

16、nue第48頁/共158頁主程序主程序 %記錄當(dāng)前代的最佳個(gè)體記錄當(dāng)前代的最佳個(gè)體 x=n2to10(s(nmax,:); xx=-1.0+x*3/(power(2,bn)-1); xmax(gn)=xx; gn=gn+1endgn=gn-1;Continue第49頁/共158頁主程序主程序 %繪制曲線繪制曲線subplot(2,1,1);plot(1:gn,ymax;ymean);title(歷代適應(yīng)度變化歷代適應(yīng)度變化,fonts,10);legend(最大適應(yīng)度最大適應(yīng)度,平均適應(yīng)度平均適應(yīng)度);string1=最終適應(yīng)度最終適應(yīng)度,num2str(ymax(gn);gtext(stri

17、ng1);subplot(2,1,2);plot(1:gn,xmax,r-);legend(自變量自變量);string2=最終自變量最終自變量,num2str(xmax(gn);gtext(string2);End第50頁/共158頁計(jì)算適應(yīng)度和累計(jì)概率函數(shù)計(jì)算適應(yīng)度和累計(jì)概率函數(shù) %計(jì)算適應(yīng)度函數(shù)計(jì)算適應(yīng)度函數(shù)function f,p=objf(s);r=size(s); %讀取種群大小讀取種群大小inn=r(1); %有有inn個(gè)個(gè)體個(gè)個(gè)體bn=r(2); %個(gè)體長度為個(gè)體長度為bnContinue第51頁/共158頁計(jì)算適應(yīng)度和累計(jì)概率函數(shù)計(jì)算適應(yīng)度和累計(jì)概率函數(shù) for i=1:in

18、n x=n2to10(s(i,:); %將將二進(jìn)制轉(zhuǎn)換為十進(jìn)制二進(jìn)制轉(zhuǎn)換為十進(jìn)制 xx=-1.0+x*3/(power(2,bn)-1); %轉(zhuǎn)化為轉(zhuǎn)化為-1,2區(qū)間的實(shí)數(shù)區(qū)間的實(shí)數(shù) f(i)=ft(xx); %計(jì)算函數(shù)值，即適應(yīng)度計(jì)算函數(shù)值，即適應(yīng)度endf=f; %行向量轉(zhuǎn)列向量行向量轉(zhuǎn)列向量Continue第52頁/共158頁計(jì)算適應(yīng)度和累計(jì)概率函數(shù)計(jì)算適應(yīng)度和累計(jì)概率函數(shù) %計(jì)算選擇概率計(jì)算選擇概率fsum=0;for i=1:inn fsum=fsum+f(i)*f(i);endfor i=1:inn ps(i)=f(i)*f(i)/fsum;endContinue第53頁/共158

19、頁計(jì)算適應(yīng)度和累計(jì)概率函數(shù)計(jì)算適應(yīng)度和累計(jì)概率函數(shù) %計(jì)算累積概率計(jì)算累積概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;Back to main.m第54頁/共158頁計(jì)算目標(biāo)函數(shù)值函數(shù)計(jì)算目標(biāo)函數(shù)值函數(shù) %目標(biāo)函數(shù)目標(biāo)函數(shù)function y=ft(x);y=x.*sin(10*pi*x)+2;Back to objf.m2 , 1 0 . 2)10sin()(xxxxf第55頁/共158頁函數(shù)函數(shù)n2to10() Continue function x = n2to10(s) x = 0; for j = 1:22 x = x + s(

20、j) * 2(22-j); end function x = n2to10(s) x = s(1); for j = 1:21 x = x * 2 + s(j+1); end 第56頁/共158頁選擇操作函數(shù)選擇操作函數(shù) %“選擇選擇”操作操作function seln=sel(s,p);inn=size(p,1);%從種群中選擇兩個(gè)個(gè)體從種群中選擇兩個(gè)個(gè)體for i=1:2 r=rand; %產(chǎn)生一個(gè)隨機(jī)數(shù)產(chǎn)生一個(gè)隨機(jī)數(shù) prand=p-r; j=1; while prand(j)d）；）； 第147頁/共158頁用遺傳算法進(jìn)行特征提取用遺傳算法進(jìn)行特征提取 個(gè)體的表示方法：一個(gè)長度為個(gè)體的

21、表示方法：一個(gè)長度為L的個(gè)體對應(yīng)于的個(gè)體對應(yīng)于一個(gè)一個(gè)L維的二進(jìn)制特征矢量，它的每一位就表維的二進(jìn)制特征矢量，它的每一位就表示包括或排除一個(gè)相應(yīng)的特征。一個(gè)個(gè)體即是示包括或排除一個(gè)相應(yīng)的特征。一個(gè)個(gè)體即是一個(gè)可能的最優(yōu)特征子集；一個(gè)可能的最優(yōu)特征子集； 適應(yīng)度函數(shù)的設(shè)計(jì)：個(gè)體所代表的特征子集進(jìn)適應(yīng)度函數(shù)的設(shè)計(jì)：個(gè)體所代表的特征子集進(jìn)行分類時(shí)的識別率；行分類時(shí)的識別率； 遺傳算子：可采用各種方法；遺傳算子：可采用各種方法； 第148頁/共158頁用遺傳算法進(jìn)行特征提取用遺傳算法進(jìn)行特征提取 例：作品鑒別例：作品鑒別 將圖像分為將圖像分為mn格，對每一個(gè)格格，對每一個(gè)格 進(jìn)行數(shù)據(jù)分析，得到進(jìn)行數(shù)據(jù)

22、分析，得到L個(gè)特征，個(gè)特征， 從從L中選出中選出l個(gè)（個(gè)（Ll）特征送入）特征送入 分類器進(jìn)行識別。分類器進(jìn)行識別。 第149頁/共158頁用遺傳算法進(jìn)行特征提取用遺傳算法進(jìn)行特征提取 例：作品鑒別例：作品鑒別 個(gè)體的表示：個(gè)體的表示：l位長，每位代表一個(gè)特征的序號，位長，每位代表一個(gè)特征的序號，不可重復(fù)；不可重復(fù)； 適應(yīng)度函數(shù)的設(shè)計(jì)：識別率的函數(shù)；適應(yīng)度函數(shù)的設(shè)計(jì)：識別率的函數(shù)； 遺傳算子：符合個(gè)體編碼要求的算子。遺傳算子：符合個(gè)體編碼要求的算子。 第150頁/共158頁第151頁/共158頁GA 研究內(nèi)容與方向研究內(nèi)容與方向算法性能算法性能研究研究混合算混合算法研究法研究并行算并行算法研究法研究算法應(yīng)用算法