遺傳算法課件

智能優(yōu)化算法智能優(yōu)化算法又稱現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。遺傳算法屬于智能優(yōu)化算法之一。常用的智能優(yōu)化算法遺傳算法模擬退火算法禁忌搜索算法粒子群算法蟻群算法……遺傳算法概述美國(guó)J.Holland教授于1975年在專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出。借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象。遺傳算法概述在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止?；具z傳算法（SimpleGeneticAlgorithms，GA)又稱簡(jiǎn)單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)?；具z傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)編碼示例求下列一元函數(shù)的最大值：其中x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。一個(gè)問(wèn)題對(duì)于x∈[-1,2]，結(jié)果精確到6位小數(shù)，（1）二進(jìn)制編碼要求取多少位？（2）十進(jìn)制實(shí)數(shù)與二進(jìn)制編碼之間應(yīng)滿足怎樣的數(shù)學(xué)關(guān)系？編碼示例的分析區(qū)間長(zhǎng)度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因?yàn)?21<3×106<222，所以二進(jìn)制編碼長(zhǎng)度至少需要22位。編碼過(guò)程實(shí)質(zhì)是將區(qū)間[-1，2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20b19b18…b1b0）。1……101011000編碼(二進(jìn)制)與實(shí)數(shù)(十進(jìn)制)的轉(zhuǎn)換(10101000111)2編碼與實(shí)數(shù)的轉(zhuǎn)換(10101000111)20.637197初始種群基本遺傳算法（SGA）采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。初始種群中個(gè)體的數(shù)量稱為種群規(guī)模。適應(yīng)度函數(shù)遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來(lái)評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過(guò)程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問(wèn)題本身的要求而定。選擇算子遺傳算法使用選擇運(yùn)算對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰操作。適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是從父代群體中選取一些個(gè)體，遺傳到下一代群體?；具z傳算法（SGA）中選擇算子采用輪盤賭選擇方法。輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。設(shè)群體大小為N，個(gè)體xi

的適應(yīng)度為f(xi)，則個(gè)體xi的選擇概率為：輪盤賭選擇法可用如下過(guò)程模擬來(lái)實(shí)現(xiàn)：(1)在［0,1］內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。(2)若r≤q1,則染色體x1被選中。(3)若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi

(i=1,2,…,n)的積累概率,其計(jì)算公式為輪盤賭選擇方法積累概率實(shí)例：

輪盤賭選擇方法00.140.630.691q1q2

q3

q4

0.140.490.060.31積累概率概率輪盤賭選擇方法例如，有染色體s1=13(01101)s2=24(11000)s3=8(01000)s4=19(10011)假定適應(yīng)度為f(s)=s2，則f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361染色體的選擇概率為

例如，從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù):

r1=0.450126,r2=0.110347

r3=0.572496,r4=0.98503

染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001交叉算子交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。基本遺傳算法（SGA）中交叉算子采用單點(diǎn)交叉算子。單點(diǎn)交叉運(yùn)算交叉前：01000|01000011100|000101交叉后：01000|000101（孩子1）11100|010000（孩子2）交叉點(diǎn)變異算子變異運(yùn)算，是指改變個(gè)體編碼串中的某些基因值，從而形成新的個(gè)體。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，決定遺傳算法的局部搜索能力，保持種群多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索?；具z傳算法（SGA）中變異算子采用基本位變異算子。變異算子基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則將其變?yōu)?；反之，若原有基因值為1，則將其變?yōu)??；疚蛔儺愂纠儺惽埃?000010000變異后：1000010000變異點(diǎn)運(yùn)行參數(shù)（1）M：種群規(guī)模（2）T：遺傳運(yùn)算的終止進(jìn)化代數(shù)（3）Pc：交叉概率（4）Pm：變異概率基本遺傳算法的框圖產(chǎn)生初始群體滿足停止準(zhǔn)則？是輸出結(jié)果計(jì)算適應(yīng)度值比例選擇運(yùn)算單點(diǎn)交叉運(yùn)算基本位變異運(yùn)算否產(chǎn)生新一代群體執(zhí)行M/2次已知x為整數(shù)，利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY遺傳算法的應(yīng)用舉例

[分析]原問(wèn)題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問(wèn)題。個(gè)體：［0,31］中的任意點(diǎn)x適應(yīng)度：函數(shù)值f(x)=x2

解空間：區(qū)間［0,31］這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問(wèn)題就可以用遺傳算法來(lái)解決。[解]

(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(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)為止。

首先計(jì)算種群S1中各個(gè)體s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的適應(yīng)度f(wàn)(si),容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再計(jì)算種群S1中各個(gè)體的選擇概率。

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31再計(jì)算種群S1中各個(gè)體的積累概率00.140.630.691q1q2

q3

q4

0.140.490.060.31種群S1中各個(gè)體的積累概率選擇-復(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=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）

被選中兩次交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。

設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。

s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

變異

設(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）

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

假設(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ā)生變異。

于是，得第三代種群S3：s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代種群S3中各染色體的情況染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001

設(shè)這一輪的選擇-復(fù)制結(jié)果為：s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1