人工智能課件5

第5章計(jì)算智能(2):進(jìn)化計(jì)算人工生命5.1遺傳算法5.2進(jìn)化策略5.3進(jìn)化編程5.4人工生命10/3/20241第5章計(jì)算智能(2):進(jìn)化計(jì)算人工生命5.1遺傳算法5.2進(jìn)化策略5.3進(jìn)化編程5.4人工生命10/3/20242第5章計(jì)算智能(2):進(jìn)化計(jì)算人工生命5.1遺傳算法5.2進(jìn)化策略5.3進(jìn)化編程5.4人工生命10/3/202435.1遺傳算法遺傳算法是為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題找出一個(gè)解決方法。遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類搜索算法，從某種程度上說遺傳算法是對(duì)生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。霍蘭德(Holland)在他的著作《AdaptationinNaturalandArtificialSystems》首次提出遺傳算法。10/3/20244基本概念種群：初始給定的多個(gè)解的集合，它是問題解空間的一個(gè)子集。個(gè)體：種群中的單個(gè)元素，通常由一個(gè)用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來表示，如用0，1組成的長度為l的串來表示個(gè)體。染色體：對(duì)個(gè)體進(jìn)行編碼后得到的編碼串。染色體中的每一位成為基因，若干基因構(gòu)成的有效信息段稱為基因組。適應(yīng)度函數(shù)：用來對(duì)種群中個(gè)體的適應(yīng)型進(jìn)行度量的函數(shù)。10/3/202455.1遺傳算法

基本機(jī)理我們以霍蘭德(Holland)的遺傳算法

通常被稱為“簡單遺傳算法”(簡稱SGA)來分析遺傳算法的結(jié)構(gòu)和機(jī)理。結(jié)合推銷員旅行問題(貨郎擔(dān)問題(TravellingSalesmanProblem，簡記為TSP))加以說明：設(shè)有n個(gè)城市，城市i和城市j之間的距離為d(i，j)，i,j=1,...,n．TSP問題是要找遍訪每個(gè)域市恰好一次的一條回路，且其路徑總長度為最短。10/3/202465.1遺傳算法

基本機(jī)理1.編碼與解碼

我們可以把復(fù)雜的問題結(jié)構(gòu)化為簡單的位串形式編碼表示，這個(gè)過程叫編碼；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫解碼。我們把位串形式編碼表示叫染色體，有時(shí)也叫個(gè)體。對(duì)TSP可以按一條回路城市的次序進(jìn)行編碼，比如碼串134567829表示從城市1開始，依次是城市3,4,5,6,7,8,2,9，最后回到城市1。一般情況是從城市w1開始，依次經(jīng)過城市w2,……，wn，最后回到城市w1，我們就有如下編碼表示：

w1w2……wn由于是回路，記wn+1=w1。它其實(shí)是1，……，n的一個(gè)循環(huán)排列。要注意w1,w2,……，wn是互不相同的。10/3/202475.1遺傳算法

基本機(jī)理2.適應(yīng)度函數(shù)為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)勝劣汰原則。對(duì)優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。TSP的目標(biāo)是路徑總長度為最短，路徑總長度的倒數(shù)就可以為TSP的適應(yīng)度函數(shù)：請(qǐng)注意其中wn+1=w1。適應(yīng)度函數(shù)要有效反映每一個(gè)染色體與問題的最優(yōu)解染色體之間的差距，一個(gè)染色體與問題的最優(yōu)解染色體之間的差距小，則對(duì)應(yīng)的適應(yīng)度函數(shù)值之差就小，否則就大。適應(yīng)度函數(shù)的取值大小與求解問題對(duì)象的意義有很大的關(guān)系。10/3/202485.1遺傳算法

基本機(jī)理遺傳操作簡單遺傳算法的遺傳操作主要有三種:選擇、交叉、變異。選擇操作也叫復(fù)制操作，根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應(yīng)度較大(優(yōu)良)個(gè)體有較大的存在機(jī)會(huì)，而適應(yīng)度較?。ǖ土樱┑膫€(gè)體繼續(xù)存在的機(jī)會(huì)也較小。簡單遺傳算法采用賭輪選擇機(jī)制，令Σfi表示群體的適應(yīng)度值之總和，fi表示種群中第i個(gè)染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額fi／Σfi。10/3/202495.1遺傳算法

基本機(jī)理交叉操作的簡單方式是將被選擇出的兩個(gè)個(gè)體P1和P2作為父母個(gè)體，將兩者的部分碼值進(jìn)行交換。假設(shè)有如下八位長的二個(gè)體：

產(chǎn)生一個(gè)在1到7之間的隨機(jī)數(shù)c，假如現(xiàn)在產(chǎn)生的是3，將P1和P2的低三位交換：P1的高五位與P2的低三位組成數(shù)串10001001，這就是P1和P2的一個(gè)后代Q1個(gè)體；P2的高五位與P1的低三位組成數(shù)串11011110，這就是P1和P2的一個(gè)后代Q2個(gè)體。其交換過程如下圖所示：

10/3/2024105.1遺傳算法

基本機(jī)理變異操作的簡單方式是改變數(shù)碼串的某個(gè)位置上的數(shù)碼。我們先以最簡單的二進(jìn)制編碼表示方式來說明，二進(jìn)制編碼表示的每一個(gè)位置的數(shù)碼只有0與1這兩個(gè)可能，比如有如下二進(jìn)制編碼表示：

10/3/2024115.1遺傳算法

基本機(jī)理其碼長為8，隨機(jī)產(chǎn)生一個(gè)1至8之間的數(shù)k，假如現(xiàn)在k=5，對(duì)從右往左的第5位進(jìn)行變異操作，將原來的0變?yōu)?，得到如下數(shù)碼串：

二進(jìn)制編碼表示時(shí)的簡單變異操作是將0與1互換：0變異為1，1變異為0。

現(xiàn)在對(duì)TSP的變異操作作簡單介紹，隨機(jī)產(chǎn)生一個(gè)1至n之間的數(shù)k，決定對(duì)回路中的第k個(gè)城市的代碼wk作變異操作，又產(chǎn)生一個(gè)1至n之間的數(shù)w，替代wk，并將wk加到尾部，得到：w1w2……wk-1wwk+1……wnwk你發(fā)現(xiàn)這個(gè)串有n+1個(gè)數(shù)碼，注意數(shù)w其實(shí)在此串中出現(xiàn)重復(fù)了，必須刪除與數(shù)w相重復(fù)的，得到合法的染色體。10/3/202412生物進(jìn)化與遺傳算法之間的對(duì)應(yīng)關(guān)系

生物進(jìn)化中的概念遺傳算法中的作用環(huán)境適應(yīng)函數(shù)適應(yīng)性適應(yīng)值函數(shù)適者生存適應(yīng)函數(shù)值最大的解被保留的概率最大個(gè)體問題的一個(gè)解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據(jù)適應(yīng)函數(shù)選擇一組解交配以一定的方式由雙親產(chǎn)生后代的過程變異編碼的某些分量發(fā)生變化的過程10/3/2024135.1遺傳算法

求解步驟遺傳算法類似于自然進(jìn)化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對(duì)求解問題的本身一無所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始群體；通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群。對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化。10/3/2024145.1遺傳算法

求解步驟10/3/2024155.1遺傳算法

收斂性一般的遺傳算法不一定收斂，采用優(yōu)秀個(gè)體保護(hù)法就是將每代中的最優(yōu)個(gè)體，直接進(jìn)入子代，相應(yīng)淘汰其子代中適應(yīng)度最差的個(gè)體，使種群規(guī)模不變。求到的解通常只是所要解決問題的最優(yōu)解的一個(gè)近似解，或者叫滿意解。近似解與問題真正的最優(yōu)解的差是一個(gè)統(tǒng)計(jì)意義下的量，也就是說每次程序運(yùn)行得到的解的質(zhì)量可能是有較大的差別的。

10/3/2024165.1遺傳算法

發(fā)展現(xiàn)狀如果一個(gè)應(yīng)用問題不能求得目標(biāo)函數(shù)的全局最優(yōu)值,而只能或只希望求一定意義下的“滿意解”，這時(shí),可供選擇的方法之一自然是遺傳算法，因?yàn)檫z傳算法比其他算法有更多的優(yōu)勢。近年來遺傳算法在商業(yè)應(yīng)用方面取得了一系列重要成果。比如通用電器公司的計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)Engeneous,這是一個(gè)采用了遺傳算法以及其他傳統(tǒng)的優(yōu)化技術(shù)做為尋優(yōu)手段的混合系統(tǒng)(hybridsystem)。Engeneous已成功地應(yīng)用于汽輪機(jī)設(shè)計(jì),并改善了新的波音777發(fā)動(dòng)機(jī)的性能，這是目前正在研究和應(yīng)用的一個(gè)重要方面。10/3/2024175.1遺傳算法

發(fā)展現(xiàn)狀遺傳算法具有隱并行性，它可容易改造成為并行/分布式算法，用來解決那些復(fù)雜性問題。到目前，遺傳算法的理論機(jī)制仍不是很清楚，這可能和生命科學(xué)的研究一樣，將是一個(gè)永恒的研究課題，但也是一個(gè)難題。已有很多學(xué)者對(duì)遺傳算法作了一些深入的研究，近幾十年來，遺傳算法的文獻(xiàn)已相當(dāng)多。10/3/2024185.2進(jìn)化策略進(jìn)化策略(evolutionstrategies,ES)是一類模仿自然進(jìn)化原理以求解參數(shù)優(yōu)化問題的算法。它是雷切伯格、施韋費(fèi)爾和彼得.比納特于1964年提出來的，并在德國共同建立。試探答案的組成部分被看做是個(gè)體的行為特性，而不是染色體中的基因。雷切伯格1973年進(jìn)行了多父代單子代的工作，施韋費(fèi)爾1981年創(chuàng)造性使用了多父代多子代。10/3/2024195.2進(jìn)化策略進(jìn)化策略是可替代工程師直覺的一種方法。直到最近，當(dāng)沒有分析對(duì)象函數(shù)可用，傳統(tǒng)的優(yōu)化方法不存在，工程師必須依賴于他們的直覺時(shí)，進(jìn)化策略才被用于優(yōu)化技術(shù)問題中。和遺傳算法不同，進(jìn)化策略僅用到突變操作。10/3/2024205.2進(jìn)化策略

進(jìn)化算法開始初始種群評(píng)價(jià)產(chǎn)生機(jī)制形成下一代種群停機(jī)輸出NY10/3/2024215.2進(jìn)化策略

與遺傳算法的區(qū)別(1)進(jìn)化策略和遺傳算法表示個(gè)體的方式不同，進(jìn)化策略在浮點(diǎn)矢量上運(yùn)行，而遺傳算法一般運(yùn)行在二進(jìn)制矢量上。(2)進(jìn)化策略和遺傳算法的選擇過程不同。(3)進(jìn)化策略和遺傳算法的復(fù)制參數(shù)不同，遺傳算法的復(fù)制參數(shù)在進(jìn)化過程中保持恒定，而進(jìn)化策略時(shí)時(shí)改變它們。10/3/2024225.3進(jìn)化編程又稱進(jìn)化規(guī)劃：根據(jù)正確預(yù)測的符號(hào)數(shù)來度量適應(yīng)值。通過變異，為父代群體中的每個(gè)機(jī)器狀態(tài)產(chǎn)生一個(gè)子代。父代和子代中最好的部分被選擇生存下來。10/3/2024235.3進(jìn)化編程的步驟產(chǎn)生初始群體，它由關(guān)于問題(計(jì)算機(jī)程序)的函數(shù)隨機(jī)組合而成迭代完成下述過程，直到滿足選種標(biāo)準(zhǔn)為止(1)執(zhí)行群體中的每個(gè)程序，根據(jù)它解決問題的能力，給它指定一個(gè)適應(yīng)值(2)應(yīng)用變異等操作創(chuàng)造的計(jì)算機(jī)程序群體。在后代中適應(yīng)值最高的計(jì)算機(jī)程序個(gè)體被指定為進(jìn)化編程的結(jié)果。10/3/2024245.4人工生命人工生命是指具有生命特征的人造系統(tǒng)。人工生命是20世紀(jì)80年代后期開始興起的一種新的學(xué)科領(lǐng)域，也是計(jì)算機(jī)科學(xué)繼人工智能之后出現(xiàn)的新的發(fā)展方向之一。世界上首先提出“人工生命”概念的人，是美國洛斯·阿莫斯國家實(shí)驗(yàn)室的克里斯·蘭頓博士。10/3/2024255.4人工生命人工生命的研究現(xiàn)狀與人工智能早期歷史可以說是并行的。40年代末，50年代初，馮.諾伊曼提出了…..1956年達(dá)特默斯的夏季討論會(huì)上……60年代，羅森勃拉特(Rosenblatt)研究感知機(jī)，70年代以來，喬姆斯基(Chomsky)的形式語言理論應(yīng)用在程序設(shè)計(jì)語言的規(guī)范說明和開發(fā)編譯程序10/3/2024265.4人工生命人工生命是形成新的信息處理體系強(qiáng)大的推動(dòng)力，并成為研究生物的一個(gè)特別有用的工具。人工生命的研究可能將信息科學(xué)和生命科學(xué)結(jié)合起來，形成生命信息科學(xué)。在21世紀(jì)初人工生命的研究將會(huì)蓬勃發(fā)展，并取得突破性進(jìn)展。人工生命研究的科學(xué)問題如下：

生命自組織和自復(fù)制,發(fā)育和變異,系統(tǒng)復(fù)雜性,進(jìn)化和適應(yīng)動(dòng)力學(xué),智能主體,自主系統(tǒng),機(jī)器人和人工腦：10/3/2024275.4人工生命

實(shí)例人工腦澳大利亞一名科學(xué)家正在發(fā)明全球首個(gè)模仿人腦的人工腦袋，相信在約10年后，這人工腦的智力便能超越人腦40倍。正在日本進(jìn)行研究的澳大利亞科學(xué)家加里斯表示，他發(fā)明的“細(xì)胞自動(dòng)機(jī)”（CAM）便可以制造出用硅制成的7500萬人工神經(jīng)細(xì)胞-一種類似人腦細(xì)胞的功能。這個(gè)神經(jīng)細(xì)胞網(wǎng)絡(luò)跟人腦一樣隨機(jī)連結(jié)，且會(huì)按照達(dá)爾文的進(jìn)化論，像人腦神經(jīng)細(xì)胞般出現(xiàn)錯(cuò)誤情況。但整個(gè)電路每分鐘仍能運(yùn)作數(shù)千次。加里斯預(yù)計(jì)，完成這第一代人工腦后，便會(huì)將之發(fā)展為一只機(jī)械貓。此后研究便會(huì)發(fā)展第二代，至2007年，神經(jīng)細(xì)胞會(huì)超過100億個(gè)，即已達(dá)到一個(gè)弱智人士的智力，要再發(fā)展至普通成人智力亦非難事。10/3/2024285.4人工生命

實(shí)例計(jì)算機(jī)病毒20世紀(jì)80年代，計(jì)算機(jī)技術(shù)的飛速發(fā)展帶來的負(fù)面效應(yīng)。計(jì)算機(jī)病毒指在計(jì)算機(jī)上傳染的與生物學(xué)中的病毒具有相似生命現(xiàn)象的有害程序。它能夠通過自身繁殖，把自己復(fù)制到計(jì)算機(jī)內(nèi)已存儲(chǔ)的其他程序上的計(jì)算機(jī)程序。計(jì)算機(jī)病毒一般是惡性的，人為的用計(jì)算機(jī)語言寫成的可存儲(chǔ)的、可執(zhí)行的計(jì)算機(jī)非法程序。10/3/2024295.4人工生命

實(shí)例計(jì)算機(jī)進(jìn)程類似于計(jì)算機(jī)病毒，把進(jìn)程當(dāng)作生命體，可在時(shí)間空間中繁殖，從環(huán)境中汲取信息，修改所在的環(huán)境。計(jì)算機(jī)進(jìn)程可在內(nèi)存某個(gè)地方之外活著，等待適當(dāng)?shù)臈l件重新出現(xiàn)以便恢復(fù)它們的活動(dòng)狀態(tài)。10/3/2024305.4人工生命

實(shí)例細(xì)胞自動(dòng)機(jī)它是一種人工細(xì)胞陳列，每個(gè)細(xì)胞具有離散結(jié)構(gòu)。按照預(yù)先規(guī)定的規(guī)則，這些細(xì)胞的狀態(tài)可隨時(shí)間變化，通過陳列傳遞規(guī)則，計(jì)算每個(gè)細(xì)胞的當(dāng)前狀態(tài)及其鄰近細(xì)胞狀態(tài)。所有細(xì)胞均自發(fā)的更新狀態(tài)。細(xì)胞自動(dòng)機(jī)是1940年由馮.諾依曼發(fā)明的，它以數(shù)學(xué)和邏輯形式提供了理解自然系統(tǒng)的