第9講-MATLAB遺傳算法_第1頁
第9講-MATLAB遺傳算法_第2頁
第9講-MATLAB遺傳算法_第3頁
第9講-MATLAB遺傳算法_第4頁
第9講-MATLAB遺傳算法_第5頁
已閱讀5頁,還剩47頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

基于遺傳算法的隨機優(yōu)化搜索基本概念基本遺傳算法

遺傳算法應用舉例

遺傳算法的特點與優(yōu)勢

基因,遺傳,進化復制復制:適者生存,只有適合的,更可能得到復制交叉染色體的交叉:產生更多更豐富的組合,多樣性變異基因突變:很少,但可以產生新的性狀遺傳進化通過染色體的選擇復制,交叉,變異,推動整個群體向著優(yōu)化的方向進化遺傳算法:模擬生物遺傳進化的過程,尋找最優(yōu)解

基本概念

1.局部最優(yōu)與全局最優(yōu)?

2.適應度與適應度函數

適應度(fitness)就是借鑒生物個體對環(huán)境的適應程度,而對問題中的個體對象所設計的表征其優(yōu)劣的一種測度。

●適應度函數(fitnessfunction)就是問題中的全體個體與其適應度之間的一個對應關系。它一般是一個實值函數。該函數就是遺傳算法中指導搜索的評價函數。

3.進化,基因,染色體

染色體(chromosome)就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因(gene)。例如:個體染色體

9----

1001

(2,5,6)----0101011104.遺傳操作

亦稱遺傳算子(geneticoperator),就是關于染色體的運算。遺傳算法中有三種遺傳操作:

選擇-復制(selection-reproduction)

交叉(crossover,亦稱交換、交配或雜交)

變異(mutation,亦稱突變)

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

這里的選擇概率P(xi)的計算公式為

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

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設染色體s1=01001011,s2=10010101,

交換其后4位基因,即

變異就是改變染色體某個(些)位上的基因。例如,設染色體s=11001101將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。4.2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計算適應度選擇-復制交叉變異生成新一代種群終止?結束

算法中的一些控制參數:

種群規(guī)模

最大換代數

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

變異率(mutationrate)是指發(fā)生變異的基因位數所占全體染色體的基因總位數的比例,記為Pm,取值范圍一般為0.0001~0.1。

基本遺傳算法

步1

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

步2

隨機產生U中的N個個體s1,s2,…,sN,組成初始種群S={s1,s2,…,sN},置代數計數器t=1;

步3

計算S中每個個體的適應度f();

步4

若終止條件滿足,則取S中適應度最大的個體作為所求結果,算法結束。

步5

按選擇概率P(xi)所決定的選中機會,每次從S中隨機選定1個個體并將其染色體復制,共做N次,然后將復制所得的N個染色體組成群體S1;

步6

按交叉率Pc所決定的參加交叉的染色體數c,從S1中隨機確定c個染色體,配對進行交叉操作,并用產生的新染色體代替原染色體,得群體S2;

步7

按變異率Pm所決定的變異次數m,從S2中隨機確定m個染色體,分別進行變異操作,并用產生的新染色體代替原染色體,得群體S3;

步8

將群體S3作為新一代種群,即用S3代替S,t=t+1,轉步3;

4.3遺傳算法應用舉例

例4.1

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

y=x2

31

XY

分析

原問題可轉化為在區(qū)間[0,31]中搜索能使y取最大值的點a的問題。那么,[0,31]中的點x就是個體,函數值f(x)恰好就可以作為x的適應度,區(qū)間[0,31]就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。

(1)

設定種群規(guī)模,編碼染色體,產生初始種群。將種群規(guī)模設定為4;用5位二進制數編碼染色體;取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應度函數,

取適應度函數:f(x)=x2

(3)計算各代種群中的各個體的適應度,并對其染色體進行遺傳操作,直到適應度最高的個體(即31(11111))出現為止。

首先計算種群S1中各個體

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

s3=8(01000),s4=19(10011)的適應度f(si)

。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法

在算法中賭輪選擇法可用下面的子過程來模擬:①在[0,1]區(qū)間內產生一個均勻分布的隨機數r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為選擇-復制

設從區(qū)間[0,1]中產生4個隨機數如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應度選擇概率積累概率選中次數s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是,經復制得群體:s1’

=11000(24),s2’

=01101(13)s3’

=11000(24),s4’

=10011(19)交叉

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

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

s3’’=11011(27),s4’’=10000(16)

變異設變異率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)

第二代種群S2中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001

假設這一輪選擇-復制操作中,種群S2中的4個染色體都被選中,則得到群體:

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

s3’=11011(27),s4’=10000(16)

做交叉運算,讓s1’與s2’,s3’與s4’

分別交換后三位基因,得

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

s3’’=11000(24),s4’’=10011(19)

這一輪仍然不會發(fā)生變異。

于是,得第三代種群S3:

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

s3=11000(24),s4=10011(19)

第三代種群S3中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001

設這一輪的選擇-復制結果為:

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

s3’=11000(24),s4’=10011(19)

做交叉運算,讓s1’與s4’,s2’與s3’

分別交換后兩位基因,得

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

s3’’=11000(24),s4’’=10000(16)

這一輪仍然不會發(fā)生變異。

于是,得第四代種群S4:

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

s3=11000(24),s4=10000(16)

顯然,在這一代種群中已經出現了適應度最高的染色體s1=11111。于是,遺傳操作終止,將染色體“11111”作為最終結果輸出。然后,將染色體“11111”解碼為表現型,即得所求的最優(yōu)解:31。將31代入函數y=x2中,即得原問題的解,即函數y=x2的最大值為961。

YYy=x2

8131924

X第一代種群及其適應度y=x2

12162527

XY第二代種群及其適應度y=x2

9192428

XY第三代種群及其適應度y=x2

16242831

X第四代種群及其適應度4.4遺傳算法的特點與優(yōu)勢

◆遺傳算法的主要特點

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

——遺傳算法的搜索隨機地始于搜索空間的一個點集,而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點或終止節(jié)點,所以遺傳算法是一種隨機搜索算法。

——遺傳算法總是在尋找優(yōu)解,而不像圖搜索那樣并非總是要求優(yōu)解,而一般是設法盡快找到解,所以遺傳算法又是一種優(yōu)化搜索算法。

——遺傳算法的搜索過程是從空間的一個點集(種群)到另一個點集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個點到另一個點地搜索。因而它實際是一種并行搜索,適合大規(guī)模并行計算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。

——遺傳算法的適應性強,

溫馨提示

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

評論

0/150

提交評論