人工智能入門 課件 4.進(jìn)化計(jì)算

進(jìn)化計(jì)算01AI:EC2大綱生命對(duì)搜索方法的啟示什么是進(jìn)化計(jì)算(EC)?進(jìn)化算法(EA)遺傳算法進(jìn)化規(guī)劃進(jìn)化策略AI:EC3

一個(gè)啟發(fā)式搜索的新思路?進(jìn)化計(jì)算確定還是隨機(jī)?若確實(shí)如此啟發(fā)式搜索（優(yōu)化）方法是數(shù)學(xué)和計(jì)算機(jī)科學(xué)的核心主題AI:EC4PartⅠ:生物對(duì)搜索的啟示AI:EC5Q.什么是搜索問題最好的解決方案?.人類的大腦

能產(chǎn)生“汽車,紐約,戰(zhàn)爭,等”

(afterDouglasAdams)

神經(jīng)計(jì)算

.進(jìn)化機(jī)制

導(dǎo)致人腦的產(chǎn)生(afterDarwinetal.)

進(jìn)化計(jì)算

AI:EC6達(dá)爾文進(jìn)化基于群體的進(jìn)化，而非個(gè)體的變化適者生存:有限的資源導(dǎo)致激烈的競爭,那些能最有效的占有資源的個(gè)體(最適應(yīng)環(huán)境的個(gè)體)有更高的概率被繁殖下去(被選擇)AI:EC7達(dá)爾文進(jìn)化多樣性引起變化:如果表現(xiàn)特征:有更高的概率被繁殖下去可以繼承則他們往往會(huì)形成更多的后代，從而導(dǎo)致新的組合特征.

隨機(jī)性的作用最優(yōu)的解不一定都能生存下去AI:EC8自然遺傳學(xué)遺傳信息需要通過有機(jī)體的DNA編碼遺傳下去基因的微小變化導(dǎo)致生物體的微小變化(如身高,頭發(fā)，顏色)對(duì)于一個(gè)特定的物種，其遺傳物質(zhì)是基本相同的AI:EC9基因和基因組由DNA鏈編碼的基因稱為染色體在大多數(shù)細(xì)胞中，有兩條染色體排成雙螺旋結(jié)構(gòu)(diploidy)一個(gè)個(gè)體的全部遺傳物質(zhì)的集合稱為基因組AI:EC10個(gè)體遺傳物質(zhì)改變的主要手段:重組從至少兩個(gè)父代個(gè)體中獲得遺傳物質(zhì)產(chǎn)生新的個(gè)體,如,在一對(duì)染色體的交叉點(diǎn)上連接交換染色體:

重組前

重組后圖片來源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC11個(gè)體遺傳物質(zhì)改變的主要手段:突變一些遺傳物質(zhì)會(huì)發(fā)生輕微的改變，這個(gè)過程偶爾發(fā)生這意味著子代個(gè)體可能擁有父代個(gè)體所沒有的遺傳物質(zhì)這種改變極有可能是災(zāi)難性的AI:EC12進(jìn)化理論突變,重組

新的遺傳物質(zhì)或者新的組合.繁殖的越多則基因的性能可以得到更多的改進(jìn)

好的基因得到更多被遺傳的機(jī)會(huì)壞的基因則會(huì)在遺傳的過程中減少在其生存環(huán)境中，有機(jī)體作為一個(gè)整體得到進(jìn)化.采用進(jìn)化的方法計(jì)算或求解問題能夠幫助我們找到問題的最優(yōu)解：進(jìn)化計(jì)算AI:EC13PartⅡ:什么是進(jìn)化計(jì)算?AI:EC14以這樣的方式放置8皇后一個(gè)8x8的棋盤上，他們不能互相卡到對(duì)方，例子:8皇后問題

[AfterA.E.EibenandJ.E.Smith,IntroductiontoEvolutionaryComputing]

AI:EC1512345678遺傳物質(zhì):

一列數(shù)字1-8表現(xiàn)特性:

一個(gè)棋局配置Obviousmapping8皇后問題:表示AI:EC16一個(gè)皇后的懲罰:

它能卡住的皇后個(gè)數(shù).

一種棋局的懲罰:

對(duì)每一個(gè)皇后的懲罰值求和.

目標(biāo):使得懲罰值最小

最優(yōu)棋局:

懲罰值的倒數(shù)最大時(shí)8皇后問題:適應(yīng)度評(píng)價(jià)AI:EC17

突變:

交換兩個(gè)隨機(jī)選擇的點(diǎn)

(概率:80%)1234567812345678

重組:

交叉(概率:100%)876425311352467887645123135628748皇后問題:遺傳算子5432126478AI:EC18父代選擇:挑選五個(gè)父代個(gè)體，并選擇其中最優(yōu)的兩個(gè)執(zhí)行重組操作生存選擇(替換策略)當(dāng)一個(gè)新的子代個(gè)體要插入種群中時(shí)，選擇種群中將被替換的一個(gè)個(gè)體，選擇規(guī)則為:將種群中的個(gè)體按適應(yīng)度降序排列將個(gè)體由高到低列舉替換排列中第一個(gè)適應(yīng)度比當(dāng)前子代適應(yīng)度低的個(gè)體8皇后問題:選擇AI:EC19初始化:隨機(jī)終止:根據(jù)適應(yīng)度的評(píng)價(jià)問題得到了解決或者循環(huán)迭代次數(shù)達(dá)到最大（比如10，000）8皇后問題:初始化\終止條件AI:EC208皇后問題:總結(jié)注意：操作和參數(shù)的選擇不只有這一種可能AI:EC21生物進(jìn)化與搜索的類比進(jìn)化個(gè)體適應(yīng)度環(huán)境搜索候選解解的質(zhì)量待求解的問題AI:EC22進(jìn)化算法構(gòu)成tt+1突變重組繁殖選擇圖片來源IdaSprinkhuizen-Kuyper:Introductionto

EvolutionaryComputation,2000.AI:EC23進(jìn)化機(jī)制遺傳增加了多樣性突變重組選擇減少了多樣性父代選擇：選擇用于繁殖的父代子代選擇：選擇保留下來的子代AI:EC24進(jìn)化中的循環(huán)過程重組突變種群子代父代父代選擇子代選擇圖片來源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC25表示基因表示:編碼:表型=>基因(不一定是一一對(duì)應(yīng)的)解碼:基因=>表型(必須是一一對(duì)應(yīng)的)表型表示:問題的特定編碼AI:EC26進(jìn)化(適應(yīng)度)函數(shù)表示對(duì)種群（解）的要求，即質(zhì)量函數(shù)

或

目標(biāo)函數(shù)為每一個(gè)表型計(jì)算一個(gè)代表其適應(yīng)度的實(shí)數(shù)，這樣構(gòu)成了遺傳選擇的基礎(chǔ)因此該函數(shù)的判斷能力越大越好AI:EC27基因操作產(chǎn)生新的候選解

通常根據(jù)父代個(gè)體數(shù)分為兩類:=1:突變操作>1:重組操作=2:交叉操作有很多關(guān)于重組和突變重要性的爭論現(xiàn)在大多數(shù)進(jìn)化算法兩者都有AI:EC28父代選擇機(jī)制個(gè)體作為父代的概率是根據(jù)其適應(yīng)度得出來的高質(zhì)量的解有更高的概率被作為父代個(gè)體出現(xiàn)，但它并不是一定會(huì)作為父代個(gè)體出現(xiàn)，即使是種群中最差的個(gè)體也不是完全沒有機(jī)會(huì)作為父代個(gè)體出現(xiàn)這種隨機(jī)性可以在一定程度上避免陷入局部最優(yōu)解.AI:EC29子代選擇或稱為替換策略從子代+父代的種群中產(chǎn)生新的種群的方法兩種方法適應(yīng)度準(zhǔn)則

:例如挑選種群中一定數(shù)量適應(yīng)度最好的個(gè)體作為新的種群年齡準(zhǔn)則:

產(chǎn)生和父代個(gè)體一樣多的子代個(gè)體，淘汰所有的父代個(gè)體AI:EC30初始化/終止條件初始化

通常采用隨機(jī)初始化的策略。終止條件

檢查每一代種群個(gè)體，看以下條件是否滿足：

達(dá)到給定的或期望的適應(yīng)度達(dá)到最大的種群更新次數(shù)種群中的多樣性水平最小連續(xù)幾代更新都沒有使得種群中的適應(yīng)度得到改進(jìn)AI:EC31PartⅢ:進(jìn)化算法AI:EC32主要進(jìn)化算法遺傳算法(GA)J.Holland1962(AnnArbor,MI)進(jìn)化規(guī)劃(EP)L.Fogel1962(SanDiego,CA)進(jìn)化策略(ES)I.Rechenberg&H.-P.Schwefel1965(Berlin)遺傳規(guī)劃(GP)J.Koza1989(PaloAlto,CA)算法之間的相似性比差異更重要AI:EC33分類圖片來源:Introductionto

EvolutionaryComputationbyIdaSprinkhuizen-KuyperAI:EC34技術(shù)總結(jié)GAEPESGP表示基因型表現(xiàn)型表現(xiàn)型基因型突變√√√√重組√×√√父代選擇概率選擇確定選擇概率選擇概率選擇子代選擇排斥,確定混合，隨機(jī)混合，確定排斥，確定AI:EC353.1遺傳算法(GA)Holland最初提出的遺傳算法現(xiàn)在被稱作簡單遺傳算法(SGA)現(xiàn)在還常常被用作新的遺傳算法的測試基準(zhǔn)其他遺傳算法可能應(yīng)用不同的:表示方法突變方法交叉方法選擇機(jī)制AI:EC36表示基因組通常被用來表示候選解定長二進(jìn)制編碼(SGA)Holland傳統(tǒng)的

其收斂性有理論上的保證實(shí)值基因組人工進(jìn)化收斂性的證明很困難AI:EC37貪婪選擇:選擇適應(yīng)度最好的解按概率選擇:概率與適應(yīng)度成正比例如采用輪盤賭的方法(SGA)GA操作:選擇例如適應(yīng)度為：(2200,1800,1200,950,400,100)AI:EC38GA操作:交叉對(duì)于給定的父代個(gè)體，交叉以特定的概率

Pc

1發(fā)生(Pc

的典型范圍為(0.6,0.9))否則父代個(gè)體直接作為子代個(gè)體(克隆)例如,A.One-pointcrossover(SGA)

B.Two-pointcrossover

圖片來源:IntroductiontoStochasticSearchandOptimization(ISSO)byJ.C.SpallAI:EC39GA操作:突變獨(dú)立地改變每一個(gè)基因的概率

pmpm稱為

突變概率典型值介于（1/種群規(guī)模）和（1/

染色體長度）之間例如AI:EC40應(yīng)用例

[AfterA.L.Nelson]在一個(gè)由方格組成的棋盤上找到兩點(diǎn)間的最優(yōu)路徑該生物體:占據(jù)一個(gè)方格能夠移動(dòng)到最近鄰的方格目標(biāo):在最短的步驟內(nèi)從灰色方格移動(dòng)到綠色方格AI:EC41基因組例如:通過一個(gè)方向符號(hào)串表示一條路徑.方向的表示:北=00,東=10,南=11,西=01AI:EC42種群種群P

由一系列個(gè)體pn組成，N表示種群中擁有的個(gè)體數(shù)目AI:EC43適應(yīng)度函數(shù)和選擇策略適應(yīng)度函數(shù)距離目標(biāo)的最短合法路徑:F(pn)=S(steps)父代選擇:貪婪算法AI:EC44基因改變交叉:單點(diǎn)交叉突變:位串點(diǎn)突變AI:EC45實(shí)例方格尺寸:4X4種群中個(gè)體數(shù)目:N=4基因編碼:16bits適應(yīng)度函數(shù):F(p)=距離目標(biāo)的方格數(shù)選擇策略:貪婪算法AI:EC46實(shí)例：初始化種群初始化種群P(0):4個(gè)隨機(jī)的16位串AI:EC47實(shí)例：適應(yīng)度計(jì)算F(p1)=(8-8)–4=-4F(p2)=-5F(p3)=-6F(p4)=-4AI:EC48實(shí)例：選擇和更新選擇p1

和

p4

作為父代個(gè)體通過交叉和重組產(chǎn)生子代個(gè)體AI:EC49實(shí)例：子代選擇新一代個(gè)體為：AI:EC50對(duì)子代個(gè)體重復(fù)前面的操作重復(fù):F(p1)=-4F(p2)=-4

F(p3)=0F(p4)=-4AI:EC51總結(jié)進(jìn)化計(jì)算基于生物進(jìn)