遺傳算法簡介

《遺傳算法簡介》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、遺傳算法簡介主講人：蔡慧君小組成員：賀鵬飛指導老師：許楨英基本概念1基本遺傳算法2遺傳算法應用舉例3遺傳算法的特點和優(yōu)勢41.基本概念1.1個體與種群●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點?！穹N群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集。1.2適應度與適應度函數(shù)●適應度(fitness)就是借鑒生物個體對環(huán)境的適應程度,而對問題中的個體對象所設計的表征其優(yōu)劣的一種測度?！襁m應度函數(shù)(fitnessfunction)就是問題中的全體個體與其適應度之間的一個

2、對應關(guān)系。它一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導搜索的評價函數(shù)。1.3染色體與基因染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體9----1001（2，5，6）----0101011101.4遺傳操作亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運算。遺傳算法中有三種遺傳操作:●選擇-復制(selection-reproduction)●交叉(crossover，亦稱交換、交配或雜交)●變異(mutation，亦稱突變)選擇-復制通常做法是：對于一個規(guī)模為N的種群S,按

3、每個染色體xi∈S的選擇概率P(xi)所決定的選中機會,分N次從S中隨機選定N個染色體,并進行復制。這里的選擇概率P(xi)的計算公式為交叉就是互換兩個染色體某些位上的基因。s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。例如,設染色體s1=01001011,s2=10010101,交換其后4位基因,即變異就是改變?nèi)旧w某個(些)位上的基因。例如,設染色體s=11001101將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。2基本遺傳算法遺傳算法基本流程框圖生成初始種群計算適

4、應度選擇-復制交叉變異生成新一代種群終止?結(jié)束YN基本遺傳算法步1在搜索空間U上定義一個適應度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；步2隨機產(chǎn)生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計數(shù)器t=1；步3計算S中每個個體的適應度f(x)；步4若終止條件滿足，則取S中適應度最大的個體作為所求結(jié)果，算法結(jié)束。步5按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體并將其染色體復制，共做N次，然后將復制所得的N個染色體組成群體S1；步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對

5、進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；步8將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；3.遺傳算法應用舉例例4.1利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。y=x231XY分析原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就

6、可以用遺傳算法來解決。解(1)設定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設定為4；用5位二進制數(shù)編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定義適應度函數(shù),取適應度函數(shù)：f(x)=x2(3)計算各代種群中的各個體的適應度,并對其染色體進行遺傳操作,直到適應度最高的個體(即31（11111）)出現(xiàn)為止。首先計算種群S1中各個體s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的適應度f(si)。容易求得f(s1)=f(13)=

7、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ū)間內(nèi)產(chǎn)生一個均勻分布的隨機數(shù)r。②若r≤