人工智能課件5

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

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

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

基本機理1.編碼與解碼

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

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

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

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

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

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

10/3/2024105.1遺傳算法

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

10/3/2024115.1遺傳算法

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

二進制編碼表示時的簡單變異操作是將0與1互換：0變異為1，1變異為0。

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

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

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

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

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

10/3/2024165.1遺傳算法

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

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

進化算法開始初始種群評價產生機制形成下一代種群停機輸出NY10/3/2024215.2進化策略

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

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

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

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

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

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