第遺傳算法演示文稿

當(dāng)前第1頁\共有57頁\編于星期五\11點(diǎn)優(yōu)選第遺傳算法當(dāng)前第2頁\共有57頁\編于星期五\11點(diǎn)常用的智能優(yōu)化算法遺傳算法模擬退火算法禁忌搜索算法粒子群算法蟻群算法……當(dāng)前第3頁\共有57頁\編于星期五\11點(diǎn)智能優(yōu)化算法的特點(diǎn)從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個求解空間中探索最優(yōu)解。求解的過程通常是一個迭代的過程，即不是一步就完成。由于它們可以把搜索空間擴(kuò)展到整個問題空間，因而具有全局優(yōu)化性能。當(dāng)前第4頁\共有57頁\編于星期五\11點(diǎn)遺傳算法概述美國J.Holland教授于1975年在專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出。借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象。當(dāng)前第5頁\共有57頁\編于星期五\11點(diǎn)遺傳算法概述在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止?；具z傳算法（SimpleGeneticAlgorithms，GA)又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。當(dāng)前第6頁\共有57頁\編于星期五\11點(diǎn)基本遺傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)當(dāng)前第7頁\共有57頁\編于星期五\11點(diǎn)編碼遺傳算法（GA）通過某種編碼機(jī)制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串?；具z傳算法（SGA）使用二進(jìn)制串進(jìn)行編碼。1000101110110101000111

染色體基因當(dāng)前第8頁\共有57頁\編于星期五\11點(diǎn)編碼示例求下列一元函數(shù)的最大值：其中x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。當(dāng)前第9頁\共有57頁\編于星期五\11點(diǎn)一個問題對于x∈[-1,2]，結(jié)果精確到6位小數(shù)，（1）二進(jìn)制編碼要求取多少位？（2）十進(jìn)制實數(shù)與二進(jìn)制編碼之間應(yīng)滿足怎樣的數(shù)學(xué)關(guān)系？當(dāng)前第10頁\共有57頁\編于星期五\11點(diǎn)編碼示例的分析區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以二進(jìn)制編碼長度至少需要22位。編碼過程實質(zhì)是將區(qū)間[-1，2]內(nèi)對應(yīng)的實數(shù)值轉(zhuǎn)化為一個二進(jìn)制串（b21b20b19b18…b1b0）。當(dāng)前第11頁\共有57頁\編于星期五\11點(diǎn)一個問題對于x∈[-1,2]，結(jié)果精確到6位小數(shù)，十進(jìn)制實數(shù)與二進(jìn)制編碼之間應(yīng)滿足怎樣的數(shù)學(xué)關(guān)系？當(dāng)前第12頁\共有57頁\編于星期五\11點(diǎn)編碼(二進(jìn)制)與實數(shù)(十進(jìn)制)的轉(zhuǎn)換(1000101110110101000111)2當(dāng)前第13頁\共有57頁\編于星期五\11點(diǎn)編碼與實數(shù)的轉(zhuǎn)換(1000101110110101000111)20.637197當(dāng)前第14頁\共有57頁\編于星期五\11點(diǎn)當(dāng)前第15頁\共有57頁\編于星期五\11點(diǎn)基因型與表現(xiàn)型基因型：表現(xiàn)型：0.637197

編碼解碼個體（染色體）

1000101110110101000111基因當(dāng)前第16頁\共有57頁\編于星期五\11點(diǎn)初始種群基本遺傳算法（SGA）采用隨機(jī)方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。當(dāng)前第17頁\共有57頁\編于星期五\11點(diǎn)適應(yīng)度函數(shù)遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。當(dāng)前第18頁\共有57頁\編于星期五\11點(diǎn)選擇算子遺傳算法使用選擇運(yùn)算對個體進(jìn)行優(yōu)勝劣汰操作。適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是從父代群體中選取一些個體，遺傳到下一代群體?；具z傳算法（SGA）中選擇算子采用輪盤賭選擇方法。當(dāng)前第19頁\共有57頁\編于星期五\11點(diǎn)一等獎二等獎三等獎四等獎輪盤賭選擇方法當(dāng)前第20頁\共有57頁\編于星期五\11點(diǎn)輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，其基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值成正比。設(shè)群體大小為N，個體xi

的適應(yīng)度為f(xi)，則個體xi的選擇概率為：當(dāng)前第21頁\共有57頁\編于星期五\11點(diǎn)輪盤賭選擇法可用如下過程模擬來實現(xiàn)：(1)在［0,1］內(nèi)產(chǎn)生一個均勻分布的隨機(jī)數(shù)r。(2)若r≤q1,則染色體x1被選中。(3)若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi

(i=1,2,…,n)的積累概率,其計算公式為輪盤賭選擇方法當(dāng)前第22頁\共有57頁\編于星期五\11點(diǎn)積累概率實例：

輪盤賭選擇方法00.140.630.691q1q2

q3

q4

0.140.490.060.31積累概率概率當(dāng)前第23頁\共有57頁\編于星期五\11點(diǎn)輪盤賭選擇方法輪盤賭選擇方法的實現(xiàn)步驟:（1）計算群體中所有個體的適應(yīng)度值；（2）計算每個個體的選擇概率；（3）計算積累概率；（4）采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個個體遺傳到下一代群體的概率進(jìn)行匹配）來確定各個個體是否遺傳到下一代群體中。當(dāng)前第24頁\共有57頁\編于星期五\11點(diǎn)輪盤賭選擇方法例如，有染色體

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當(dāng)前第25頁\共有57頁\編于星期五\11點(diǎn)染色體的選擇概率為當(dāng)前第26頁\共有57頁\編于星期五\11點(diǎn)染色體的累計概率為當(dāng)前第27頁\共有57頁\編于星期五\11點(diǎn)s40.31s20.49s10.14S30.0600.140.630.691q1q2

q3

q4

0.140.490.060.31當(dāng)前第28頁\共有57頁\編于星期五\11點(diǎn)

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

r1=0.450126,r2=0.110347

r3=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

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

y=x2

31

XY遺傳算法的應(yīng)用舉例當(dāng)前第37頁\共有57頁\編于星期五\11點(diǎn)

[分析]

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。個體：［0,31］中的任意點(diǎn)x

適應(yīng)度：函數(shù)值f(x)=x2

解空間：區(qū)間［0,31］這樣,只要能給出個體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。當(dāng)前第38頁\共有57頁\編于星期五\11點(diǎn)[解]

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

(2)定義適應(yīng)度函數(shù),取適應(yīng)度函數(shù)

f(x)=x2

當(dāng)前第39頁\共有57頁\編于星期五\11點(diǎn)

(3)計算各代種群中的各個體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個體，即31（11111）出現(xiàn)為止。

當(dāng)前第40頁\共有57頁\編于星期五\11點(diǎn)首先計算種群S1中各個體

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=361當(dāng)前第41頁\共有57頁\編于星期五\11點(diǎn)再計算種群S1中各個體的選擇概率。

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31當(dāng)前第42頁\共有57頁\編于星期五\11點(diǎn)再計算種群S1中各個體的積累概率當(dāng)前第43頁\共有57頁\編于星期五\11點(diǎn)00.140.630.691q1q2

q3

q4

0.140.490.060.31種群S1中各個體的積累概率當(dāng)前第44頁\共有57頁\編于星期五\11點(diǎn)選擇-復(fù)制：設(shè)從區(qū)間［0,1］中產(chǎn)生4個隨機(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

1當(dāng)前第45頁\共有57頁\編于星期五\11點(diǎn)于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）

被選中兩次當(dāng)前第46頁\共有57頁\編于星期五\11點(diǎn)交叉

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

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

s1’=11000（24）,s2’=01101（13）

s3’=11000（24）,s4’=10011（19）分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

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

當(dāng)前第47頁\共有57頁\編于星期五\11點(diǎn)變異

設(shè)變異率pm=0.001。

這樣，群體S1中共有5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。當(dāng)前第48頁\共有57頁\編于星期五\11點(diǎn)于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）當(dāng)前第49頁\共有57頁\編于星期五\11點(diǎn)

第二代種群S2中各染色體的情況染色體適應(yīng)度選擇概率積累概率估計選中次數(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

1當(dāng)前第50頁\共有57頁\編于星期五\11點(diǎn)

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個染色體都被選中，則得到群體：

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）

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

當(dāng)前第51頁\共有57頁\編于星期五\11點(diǎn)于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

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

當(dāng)前第52頁\共有57頁\編于星期五\11點(diǎn)

第三代種群S3中各染色體的情況染色體適應(yīng)度選擇概率積累概率估計的選中次數(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

1當(dāng)前第53頁\共有57頁\編于星期五\11點(diǎn)

設(shè)這一輪的選擇-復(fù)制結(jié)果為