人工智能原理課件

1、人 工 智 能 原 理Artificial Intelligence Principle 信息工程學院張永梅第1頁，共109頁。第5章 計算智能(2)進化計算人工生命第2頁，共109頁。第五章 計算智能(2)5.1 遺傳算法 5.2 進化策略5.3 進化編程5.4 人工生命第3頁，共109頁。第五章 計算智能(2)作業(yè)： 5-2，5-7，5-9 第4頁，共109頁。答疑時間及地點 第5頁，共109頁。第四章 計算智能(1)4.1 概述 4.2 神經(jīng)計算 4.3 模糊計算 第6頁，共109頁。計算智能涉及神經(jīng)網(wǎng)絡、模糊邏輯、進化計算和人工生命等領(lǐng)域，它的研究和發(fā)展反映了當代科學技術(shù)多學科交叉與集

2、成的重要發(fā)展趨勢。 計算智能是借鑒仿生學的思想，基于人們對生物體 智能機理的認識，采用數(shù)值計算的方法去模擬和實 現(xiàn)人類的智能。計算智能是一種以模型（計算模型、數(shù)學模型）為基礎，以分布、并行計算為特征的自然智能模擬方法。第7頁，共109頁。進化計算（Evolutionary Computation, EC）包括：遺傳算法(genetic algorithms，GA) 進化策略(evolution strategies) 進化編程(evolutionary programming) 遺傳編程(genetic programming)人類不滿足于模仿生物進化行為，希望能夠建立具有自然生命特征的人造生

3、命和人造生命系統(tǒng)。人工生命是人工智能和計算智能的一個新的研究熱點。進化計算是一種對人類智能的演化模擬方法，它是通過對生物遺傳和演化過程的認識，用進化算法去模擬人類智能的進化規(guī)律的。 第8頁，共109頁。人工生命(Artificial life，AL)是通過人工模擬生命系統(tǒng)，來研究生命的領(lǐng)域。人工生命的概念，包括兩個方面內(nèi)容： （1）屬于計算機科學領(lǐng)域的虛擬生命系統(tǒng)，涉及計算機軟件工程與人工智能技術(shù)； （2）基因工程技術(shù)人工改造生物的工程生物系統(tǒng)，涉及合成生物學技術(shù)。 AL是首先由計算機科學家Christopher Langton于1987年在Los Alamos National Labora

4、tory召開的生成以及模擬生命系統(tǒng)的國際會議上提出。第9頁，共109頁。世界首個人工生命結(jié)構(gòu)誕生 中新網(wǎng)2010年5月22日電 綜合媒體報道，美國克萊格.文特爾研究所一個有華人參與的研究團隊宣布，在實驗中制造出世界首個完全由人造基因指令控制的人造生命，使人類的能力拓展到可以操縱自然世界，將來可制造有特殊功能的生物，在生產(chǎn)疫苗及潔凈能源等領(lǐng)域大派用場。 由美國生物學家文特爾領(lǐng)導的研究團隊，重塑“絲狀支原體絲狀亞種”(Mycoplasma mycoides)這種微生物的DNA，并將新DNA 片段“黏”在一起，植入另一種山羊支原體中。新生命于2010年4月誕生，昵稱“Synthia”(合成體)，這種

5、微生物由藍色細胞組成，能夠生長、繁殖，細胞分裂了逾10億次，產(chǎn)生一代又一代的人造生命。植入的DNA 片段包含約850個基因，而人類DNA圖譜上共有約2萬個基因。第10頁，共109頁。進化計算（Evolutionary Computation,EC）包括：遺傳算法(genetic algorithms，GA) 進化策略(evolution strategies) 進化編程(evolutionary programming) 遺傳編程(genetic programming)其中，遺傳算法是進化計算中最初形成的一種具有普遍影響的模擬進化優(yōu)化算法。因此我們主要討論遺傳算法。第11頁，共109頁。 進

6、化計算是一種模擬自然界生物進化過程與機制進行問題求解的自組織、自適應的隨機搜索技術(shù)。它將生物進化過程中的 繁殖（Reproduction） 變異（Mutation） 競爭（Competition） 選擇（Selection）引入到了算法中。什么是進化計算第12頁，共109頁。進化計算的生物學基礎 自然界生物進化過程是進化計算的生物學基礎，它主要包括: 遺傳(Heredity)變異(Mutation)進化(Evolution)理論 第13頁，共109頁。生物進化與遺傳算法 群體種群子群選擇婚配變異遭淘汰的群體第14頁，共109頁。遺傳算法(Genetic Algorithm) 達爾文進化論：“物

7、競天擇、適者生存” 。70年代由美國的密執(zhí)根大學的Holland在他的著作Adaptation in Natural and Artificial Systems首次提出遺傳算法，并主要由他和他的學生發(fā)展起來。近年來，遺傳算法作為一種有效的工具，已廣泛地應用于最優(yōu)化問題求解之中。 第15頁，共109頁。第五章 計算智能(2)5.1 遺傳算法 5.2 進化策略5.3 進化編程5.4 人工生命第16頁，共109頁。5.1 遺傳算法 遺傳算法是模仿生物遺傳學和自然選擇機理，通過人工方式所構(gòu)造的一類優(yōu)化搜索算法，是對生物進化過程進行的一種數(shù)學仿真，是進化計算的最重要的形式。遺傳算法為那些難以找到傳統(tǒng)數(shù)

8、學模型的難題指出了一個解決方法。進化計算和遺傳算法借鑒了生物科學中的某些知識，這也體現(xiàn)了人工智能這一交叉學科的特點。 第17頁，共109頁。5.1 遺傳算法 遺傳算法的起源自然界所提供的答案是經(jīng)過漫長的自適應遺傳過程獲得的結(jié)果。我們也可以利用這一過程本身去解決一些復雜的問題。遺傳算法的研究主要集中在以下幾個方面：函數(shù)優(yōu)化、組合優(yōu)化生產(chǎn)調(diào)度、自動控制、機器人學、圖像處理、人工生命、演化編程和機器學習。第18頁，共109頁。5.1.1 遺傳算法的基本機理 霍蘭德的遺傳算法通常稱為簡單遺傳算法（Simple Genetic Algorithm , SGA）?，F(xiàn)以此作為討論主要對象，加上適應的改進，來

9、分析遺傳算法的結(jié)構(gòu)和機理。5.1 遺傳算法編碼與解碼適應度函數(shù) 遺傳操作 第19頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法 基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進化，直到滿足目標為止。遺傳算法的基本概念 遺傳算法（Genetic Algorithm）是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。第20頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念 遺傳算法是從代表問題可能潛在的解集的一個種群（populati

10、on）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體（individual）組成。 初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（fitness）大小挑選（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。 這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。第21頁，共

11、109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念 遺傳算法是一類可用于復雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點： 1、遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實際值本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學中的染色體和基因的概念，可以模仿自然界生物的遺傳和進化機理，也使得我們能夠方便地應用遺傳操作算子。 2、遺傳算法直接以適應度作為搜索信息，無需導數(shù)等其它輔助信息。 3、遺傳算法使用多個點的搜索信息，具有隱含并行性。 4、遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。第22頁，共109

12、頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法 基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進化，直到滿足目標為止。遺傳算法的基本概念 種群（Population）：種群是初始給定的多個解的集合。它一般是整個搜索空間的一個很小的子集。 個體（Individual）：個體是指種群中的單個元素。一個個體也就是搜索空間中的一個點。 染色體（Chromos）：由多個基因組成，表示一個個體。染色體是指對個體進行編碼后所得到的編碼串。染色體中的每1位稱為基因，染色體上由若干個基因構(gòu)成的一個有效信息段稱為基因組。 適應度（Fitness

13、）函數(shù)：適應度函數(shù)是一種用來對種群中各個個體的環(huán)境適應性進行度量的函數(shù)。其函數(shù)值是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據(jù)。 第23頁，共109頁。第24頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念適應度(fitness) 借鑒生物個體對環(huán)境的適應程度，而對問題中的個體對象所設計的表征其優(yōu)劣的一種測度適應度函數(shù)(fitness function)問題中的全體個體與其適應度之間的一個對應關(guān)系一般是一個實值函數(shù)該函數(shù)就是遺傳算法中指導搜索的評價函數(shù) 第25頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念染色體(chromosome)染色

14、體是由若干基因組成的位串（生物學）個體對象由若干字符串組成來表示（遺傳算法） 個體 染色體 9 - 1001 （2，5，6）- 010 101 110遺傳算法(genetic algorithm)染色體就是問題中個體的某種字符串形式的編碼表示染色體以字符串來表示基因是字符串中的一個個字符第26頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念編碼與解碼將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫解碼或譯碼。第27頁，共109頁。 Huffman編碼方法是一種效率高、方法簡單的編碼。信源中符號出現(xiàn)的概率相差越大，Huff

15、man編碼效果越好。哈夫曼（Huffman）編碼 Huffman編碼一般可將數(shù)據(jù)壓縮20%至 90%，其壓縮效率取決于被壓縮數(shù)據(jù)的 特征。第28頁，共109頁。 （1）把信源符號xi(i=1,2,N)按出現(xiàn)概率的值由小到大的順序排列；Huffman編碼步驟 （2）對兩個概率最小的符號分別分配以“0”和“1”，然后把這兩個概率相加作為一個新的輔助符號的概率； （3）將這個新的輔助符號與其他符號一起重新按概率大小順序排列； （4）跳到第2步，直到出現(xiàn)概率相加為1為止；第29頁，共109頁。Huffman編碼步驟 （5）用線將符號連接起來，從而得到一個碼樹，樹的N個端點對應N個信源符號； （6）從最

16、后一個概率為1的節(jié)點開始，沿著到達信源的每個符號，將一路遇到的二進制碼“0”或“1”順序排列起來，就是端點所對應的信源符號的碼字。第30頁，共109頁。 Huffman編碼方法例如：信源符號分布為： a:4/22 b:3/22 c:2/22 d:1/22 e:5/22 f:7/22排序為： d, c, b, a, e, f 1/22 2/22 3/22 4/22 5/22 7/22第31頁，共109頁。Huffman編碼方法cbafe7/225/224/222/2210f=11 e=01 a=00 b=101 c=1001 d=1000d1/223/226/2222/2213/229/223/

17、2210101010第32頁，共109頁。哈夫曼解碼 在通信中，若將字符用哈夫曼編碼形式發(fā)送出去，對方接收到編碼后，將編碼還原成字符的過程，稱為哈夫曼解（譯）碼。 解碼: 從根結(jié)點起，每輸入一個數(shù)碼即沿二叉樹下移一層，數(shù)碼為0時移向左分支，數(shù)碼為1時移向右分支，待達到葉子結(jié)點時即譯出一個字符，再輸入的數(shù)碼又從根結(jié)點開始重新做起。反復由根出發(fā)，直到譯碼完成。 第33頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念遺傳操作（Genetic Operator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。包括以下3種基本形式： 選擇（Selection） 交叉（Cr

18、osssover） 變異（Mutation） 第34頁，共109頁。5.1.1 遺傳算法的基本機理 5.1 遺傳算法遺傳算法的基本概念 遺傳操作選擇操作也叫復制（reproduction）操作，根據(jù)個體的適應度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。交叉操作的簡單方式是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值進行交換。變異操作的簡單方式是改變數(shù)碼串的某個位置上的數(shù)碼。二進制編碼表示的簡單變異操作是將0與1互換：0變異為1，1變異為0。第35頁，共109頁。選擇算子模擬生物界優(yōu)勝劣汰的自然選擇法則的一種染色體運算從種群中選擇適應度較高的染色體進行復制，以生成下

19、一代種群算法：個體適應度計算在被選集中每個個體具有一個選擇概率選擇概率取決于種群中個體的適應度及其分布個體適應度計算，即個體選擇概率計算個體選擇方法 按照適應度進行父代個體的選擇第36頁，共109頁。交叉算子交換、交配、雜交互換兩個染色體某些位上的基因隨機化算子，生成新個體變異算子突變改變?nèi)旧w某個/些位上的基因隨機化算子，生成新個體次要算子，但在恢復群體中失去的多樣性方面具有潛在的作用第37頁，共109頁。生物進化與遺傳算法之間的對應關(guān)系 生物進化中的概念遺傳算法中的作用環(huán)境適應性適者生存?zhèn)€體染色體基因種群(群體)交叉變異第38頁，共109頁。生物進化與遺傳算法之間的對應關(guān)系 生物進化中的概

20、念遺傳算法中的作用環(huán)境適應函數(shù)適應性函數(shù)適應值適者生存適應函數(shù)值最大的解被保留的概率最大個體問題的一個解染色體解的編碼基因編碼的元素種群(群體)根據(jù)適應函數(shù)選擇的一組解交叉以一定的方式由雙親產(chǎn)生后代的過程變異編碼的某些分量發(fā)生變化的過程第39頁，共109頁。5.1.2 遺傳算法的求解步驟 遺傳算法的主要特點 5.1 遺傳算法(1)遺傳算法利用目標函數(shù)的適應度這一信息而非利用導數(shù)或其它輔助信息來指導搜索；(2)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進行隨機操作。第40頁，共109頁。第41頁，共109頁。第42頁，共109頁。遺傳算法對種群中的染色體反復做三種遺傳操作使其朝著適應

21、度增高的方向不斷更新?lián)Q代，直至出現(xiàn)了適應度滿足目標條件的染色體為止第43頁，共109頁。遺傳算法參數(shù)種群規(guī)模種群的大小，用染色體個數(shù)表示最大換代數(shù)種群更新?lián)Q代的上限，也是算法終止一個條件交叉率Pc參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例取值范圍：0.4-0.99變異率Pm發(fā)生變異的基因位數(shù)占全體染色體的基因總位數(shù)的比例取值范圍：0.0001-0.1染色體編碼 長度L 第44頁，共109頁。第45頁，共109頁。第46頁，共109頁。第47頁，共109頁。遺傳算法流程圖(1) 初始化群體;5.1 遺傳算法(2) 計算群體上每個個體的適應度值; (3) 按由個體適應度值所決定的某個規(guī)則選擇將

22、進入下一代的個體; (4) 按概率Pc進行交叉操作; (5) 按概率Pc進行變異操作; (6) 若沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進入下一步。 (7) 輸出群體中適應度值最優(yōu)的染色體作為問題的 滿意解或最優(yōu)解。第48頁，共109頁。GA算法框圖第49頁，共109頁。 一般遺傳算法的主要步驟如下：(1) 隨機產(chǎn)生一個由確定長度的特征字符串組成的 初始群體。5.1 遺傳算法 (2)對該字符串群體迭代地執(zhí)行下面的步驟和，直到滿足停止標準： 計算群體中每個個體字符串的適應值； 應用選擇、交叉、變異等遺傳算子產(chǎn)生下一代群體。 (3)把在后代中出現(xiàn)的最好的個體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個

23、結(jié)果可以表示問題的一個解。第50頁，共109頁。產(chǎn)生初始群體是否滿足停止準則計算每個個體的適應值i=M?GEN:=GEN+1依概率選擇遺傳操作執(zhí)行復制選擇一個個體i:=i+1選擇兩個個體選擇一個個體執(zhí)行變異i:=0GEN:=0復制到新群體i:=i+1將兩個后代插入新群體插入到新群體執(zhí)行雜交指定結(jié)果結(jié)束是否是否變異復制交叉5.1 遺傳算法流程圖第51頁，共109頁。第52頁，共109頁。第53頁，共109頁。例：求函數(shù)的最大值第54頁，共109頁。第55頁，共109頁。例：求函數(shù)的最大值其中x為0, 31間的整數(shù) 編碼：采用二進制形式編碼由于x的定義域是0, 31間的整數(shù)，剛好可以用5位二進制數(shù)

24、表示，因此可以用5位二進制數(shù)表示該問題的解，即染色體。如00000表示x0，10101表示x21，11111表示x31等第56頁，共109頁。問題：求（1）編碼： 此時取均長為5，每個染色體（2）初始群體生成：群體大小視情況而定，此處設置為4，隨機產(chǎn)生四個個體： 編碼： 01101，11000，01000，10011 解碼： 13 24 8 19 適應度： 169 576 64 361（3）適應度評價：第57頁，共109頁。第58頁，共109頁。（4）選擇：選擇概率 個體： 01101，11000，01000，10011 適應度： 169 576 64 361 選擇概率：0.14 0.49 0

25、.06 0.31 選擇結(jié)果：01101，11000，11000，10011（5）交叉操作：發(fā)生交叉的概率較大，變異概率很小。哪兩個個體配對交叉是隨機的。 交叉點位置的選取是隨機的（單點交叉） 0110 1 01100 11 000 11 011 1100 0 11001 10 011 10 000 假設采用輪盤式選擇個體，四個個體依次選中次數(shù)為1，2，0，1。染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應值太小而被淘汰 。第59頁，共109頁。第60頁，共109頁。第61頁，共109頁。輪盤式選擇首先計算每個個體 i 被選中的概率然后根據(jù)概率的大小將圓盤分為 n個扇形。選擇時

26、轉(zhuǎn)動輪盤，參考點r落到扇形i ，則選擇個體i 。.p1p2pir第62頁，共109頁。 從統(tǒng)計角度看，個體的適應度值越大，其對應的扇區(qū)的面積越大，被選中的可能性也越大。 這種方法有點類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為賭輪選擇。第63頁，共109頁。第64頁，共109頁。交叉操作 交叉（Crossover）操作是指按照某種方式對選擇的父代個體的染色體的部分基因進行交配重組，從而形成新的個體。 交配重組是自然界中生物遺傳進化的一個主要環(huán)節(jié)，也是遺傳算法中產(chǎn)生新的個體的最主要方法。 基本遺傳操作第65頁，共109頁。單點交叉 單點交叉也稱簡單交叉，它是先在兩個父代個體的編碼

27、串中隨機設定一個交叉點，然后對這兩個父代個體交叉點前面或后面部分的基因進行交換，并生成子代中的兩個新的個體。假設兩個父代的個體串分別是： X=x1 x2 xk xk+1 xn Y=y1 y2 yk yk+1 yn 隨機選擇第k位為交叉點，若采用對交叉點后面的基因進行交換的方法，交叉后生成的兩個新的個體是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 第66頁，共109頁。例 設有兩個父代的個體串A=0 0 1 1 0 1 和B=1 1 0 0 1 0 ，若隨機交叉點為4，則交叉后生成的兩個新的個體是： A= 0 0 1 1 1 0 B= 1 1 0 0 0

28、1 第67頁，共109頁。（4）選擇：選擇概率 個體： 01101，11000，01000，10011 適應度： 169 576 64 361 選擇概率：0.14 0.49 0.06 0.31 選擇結(jié)果：01101，11000，11000，10011（5）交叉操作：發(fā)生交叉的概率較大，變異概率很小。哪兩個個體配對交叉是隨機的。 交叉點位置的選取是隨機的（單點交叉） 0110 1 01100 11 000 11 011 1100 0 11001 10 011 10 000 假設采用輪盤式選擇個體，四個個體依次選中次數(shù)為1，2，0，1。染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適

29、應值太小而被淘汰 。第68頁，共109頁。（6）變異：發(fā)生變異的概率很小。假設本次沒有發(fā)生變異，則變異前的種群即為進化后所得到的第1代種群。（7）新群體的產(chǎn)生： 保留上一代最優(yōu)個體，一般為10%左右，至少1個 用新個體取代舊個體，隨機取代或擇優(yōu)取代。 11000，11011，11001，10011（8）重復上述操作。第69頁，共109頁。第70頁，共109頁。第71頁，共109頁。第72頁，共109頁。說明：GA的終止條件一般人為設置； GA只能求次優(yōu)解或滿意解。分析：按第二代新群體進行遺傳操作，若無變異，永遠也找不到最優(yōu)解擇優(yōu)取代有問題。 若隨機地將個體01101選入新群體中，有可能找到最優(yōu)

30、解。 在經(jīng)過編碼以后，遺傳算法幾乎不需要任何與問題有關(guān)的知識，唯一需要的信息是適應值的計算。也不需要使用者對問題有很深入的了解和求解技巧，通過選擇、交叉和變異等簡單的操作求解復雜的問題，是一個比較通用的優(yōu)化算法。第73頁，共109頁。收斂性定理 如果在代的進化過程中，遺傳算法每次保留到目前為止的最好解，并且算法以交叉和變異為其隨機化操作，則對于一個全局最優(yōu)化問題，當進化代數(shù)趨于無窮時，遺傳算法找到最優(yōu)解的概率為1。 第74頁，共109頁。遺傳算法圖搜索解空間搜索問題空間搜索-解隨機搜索、隨機選取初始點集/種群固定初始/目標節(jié)點尋找最優(yōu)解/次優(yōu)解尋找解點集-點集、并行計算點-點需適應度函數(shù)需先驗

31、知識全局搜索約束較多算法比較第75頁，共109頁。遺傳算法的實現(xiàn) 5.1 遺傳算法遺傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、隨機、自適應的搜索方法。MATLAB通用遺傳算法工具箱GAOT使用群體搜索技術(shù)，將種群代表一組問題的解，通過對當前種群施加選擇、交叉和變異等一系列遺傳操作，從而得到新的一代種群，并逐步使種群進化到包含近似最優(yōu)解狀態(tài) 。第76頁，共109頁。第五章 計算智能(2)5.1 遺傳算法 5.2 進化策略5.3 進化編程5.4 人工生命第77頁，共109頁。5.2 進化策略進化策略(Evolution Strategies，ES)是一類模仿自然進化原理以求解參數(shù)

32、優(yōu)化問題的算法。它是由雷切伯格（Rechenberg）、施韋費爾（Schwefel）和彼得比納特（Peter Bienert）于1964年提出的，并在德國共同建立的。第78頁，共109頁。5.2.1 進化策略的算法模型 尋求與函數(shù)極值關(guān)聯(lián)的實n維矢量x。隨機選擇父矢量的初始群體。（雙親向量的初始群體）父矢量xi, i=1,p產(chǎn)生子代矢量xi。（子孫向量的創(chuàng)建）對誤差 (i=1,p)排序以選擇和決定保持哪些矢量。繼續(xù)產(chǎn)生新的試驗數(shù)據(jù)以及選擇最小誤差矢量。該過程將繼續(xù)到找到符合條件的答案或者所有的計算已經(jīng)全部完成為止。5.2 進化策略最簡單形式的進化策略可描述如下：第79頁，共109頁。5.2.2

33、 進化策略和遺傳算法的區(qū)別 進化策略和遺傳算法有著很強的相似性，它們都是一類模仿自然進化原理的算法。5.2 進化策略兩者也存在著區(qū)別，其中最基本的區(qū)別是它們的研究領(lǐng)域不同。進化策略是一種數(shù)值優(yōu)化的方法，它采用一個具有自適應步長和傾角的特定爬山方法。遺傳算法從廣義上說是一種自適應搜索技術(shù)。第80頁，共109頁。5.2.2 進化策略和遺傳算法的區(qū)別 除了研究和應用領(lǐng)域外，進化策略和遺傳算法還有以下區(qū)別：(1) 進化策略和遺傳算法表示個體的方式不同，進化策略在浮點矢量上運行，而遺傳算法一般運行在二進制矢量上。5.2 進化策略(2) 進化策略和遺傳算法的選擇過程不同。(3) 進化策略和遺傳算法的復制參

34、數(shù)不同，遺傳算法的復制參數(shù)(交叉和變異的可能性) 在進化過程中保持恒定，而進化策略時時改變它們。隨著技術(shù)的發(fā)展，進化策略和遺傳算法以上的差別越來越不明顯。 第81頁，共109頁。第五章 計算智能(2)5.1 遺傳算法 5.2 進化策略5.3 進化編程5.4 人工生命第82頁，共109頁。5.3 進化編程進化編程(Evolutionary Programming，EP)，又稱為進化規(guī)劃（Evolutionary Planning），是由福格爾（Fogel）在1962年提出的一種模仿人類智能的方法。進化編程根據(jù)正確預測的符號數(shù)來度量適應值。通過變異，為父代群體中的每個機器狀態(tài)產(chǎn)生一個子代。父代和子

35、代中最好的部分被選擇生存下來。它的提出是受自然生物進化機制的啟發(fā)。第83頁，共109頁。5.3.1 進化編程的機理與表示進化編程的過程，可理解為從所有可能的計算機程序形成的空間中，搜索具有高的適應度的計算機程序個體。在進化程序設計中，幾百或幾千個計算機程序參與遺傳進化。5.3 進化編程進化編程由一隨機產(chǎn)生的計算機程序群體開始，群體中每個計算機程序個體是用適應度來評價的，該適應值與特定的問題領(lǐng)域有關(guān)。 第84頁，共109頁。5.3.2 進化編程的步驟 進化編程分為三個步驟：產(chǎn)生初始群體。它由關(guān)于問題(計算機程序)的函數(shù)隨機組合而成。5.3 進化編程迭代完成下述子步驟，直至滿足選中標準為止：執(zhí)行群

36、體中的每個程序，根據(jù)它解決問題的能力，給它指定一個適應值。應用變異等操作創(chuàng)造新程序群體?；谶m應值根據(jù)概率從群體中選出一個計算機程序個體，然后用合適的操作作用于該計算機程序個體。把現(xiàn)有的計算機程序復制到新的群體中。通過遺傳隨機重組兩個現(xiàn)有的程序, 創(chuàng)造出新的計算機程序個體。在后代中適應值最高的計算機程序個體被指定為進化編程的結(jié)果。這一結(jié)果可能是問題的解或近似解。第85頁，共109頁。變異和創(chuàng)造子代評估已存在的FSM用最好的狀態(tài)機預測和添加符號選擇父代初始化觀測順序是否是否預測初始化群體圖 進化編程的基本過程5.3 進化編程FSM（Finite State Machine，有限狀態(tài)機） 第86頁

37、，共109頁。 進化計算的三種算法即遺傳算法、進化策略和進化編程都是模擬生物界自然進化過程而建立的魯棒性計算機算法。在統(tǒng)一框架下對三種算法進行比較，可以發(fā)現(xiàn)它們有許多相似之處，同時也存在較大的差別。進化策略和進化編程都把變異作為主要搜索算子，而在標準的遺傳算法中，變異只處于次要位置。交叉在遺傳算法中起著重要作用，而在進化編程中卻被完全省去，在進化策略中與自適應結(jié)合使用，起了很重要的作用。標準遺傳算法和進化編程都強調(diào)隨機選擇機制的重要性，而從進化策略的角度看，選擇（復制）是完全確定的。進化策略和進化編程確定地把某些個體排除在被選擇（復制）之外，而標準遺傳算法一般都對每個個體指定一個非零的選擇概率

38、。 第87頁，共109頁。第五章 計算智能(2)5.1 遺傳算法 5.2 進化策略5.3 進化編程5.4 人工生命第88頁，共109頁。5.4 人工生命 自然界是生命之源。自然生命千千萬萬，千姿百態(tài)，千差萬別，巧奪天工，奇妙無窮。人工生命（Artificial Life，AL）試圖通過人工方法建造具有自然生命特征的人造系統(tǒng)。人工生命是生命科學、信息科學和系統(tǒng)科學等學科交叉研究的產(chǎn)物，其研究成果必將促進人工智能的發(fā)展。 第89頁，共109頁。5.4.1 人工生命研究的起源和發(fā)展 人類長期以來一直力圖用科學技術(shù)方法模擬自然界，包括人腦本身。1943年麥卡絡奇和皮茨提出了MP神經(jīng)學網(wǎng)絡模型。5.4

39、人工生命人工生命的許多早期研究工作也源于人工智能。20世紀70年代以來，康拉德（Conrad）等提出不斷完善的“人工世界”模型。20世紀80年代，人工神經(jīng)網(wǎng)絡再度興起促進人工生命的發(fā)展。在1987年第一次人工生命研討會上，美國圣塔菲研究所（Santa Fe Institute，SFI）非線性研究組的蘭頓（Langton）正式提出人工生命的概念，建立起人工生命新學科。此后，人工生命研究進入一個蓬勃發(fā)展的新時期。第90頁，共109頁。5.4.2 人工生命的定義和研究意義 人工生命是一項抽象地提取控制生物現(xiàn)象的基本動態(tài)原理，并且通過物理媒介（如計算機）來模擬生命系統(tǒng)動態(tài)發(fā)展過程的研究工作。5.4 人

40、工生命通俗地講，人工生命即人造的生命，非自然的生命。然而，要對人工生命做出嚴格的定義，卻需要對問題進行深入研究。 第91頁，共109頁。人工生命系統(tǒng) 1987年蘭德提出的人工生命定義為：“人工生命是研究能夠演示出自然生命系統(tǒng)特征行為的人造系統(tǒng)”。5.4 人工生命通過計算機或其它機器對類似生命的行為進行綜合研究，以便對傳統(tǒng)生物科學起互補作用。蘭德在計算機上演示了他們研制的具有生命特征的軟件系統(tǒng)，并把這類具有生命現(xiàn)象和特征的人造系統(tǒng)稱為人工生命系統(tǒng)。 第92頁，共109頁。自然生命的共同特征和現(xiàn)象 自繁殖、自進化、自尋優(yōu)自成長、自學習、自組織自穩(wěn)定、自適應、自協(xié)調(diào)物質(zhì)構(gòu)造能量轉(zhuǎn)換信息處理5.4 人

41、工生命第93頁，共109頁。研究人工生命的意義 人工生命是自然生命的模擬、延伸與擴展，其研究開發(fā)有重大的科學意義和廣泛的應用價值。5.4 人工生命 開發(fā)基于人工生命的工程技術(shù)新方法、新系統(tǒng)、新產(chǎn)品 為自然生命的研究提供新模型、新工具、新環(huán)境 延伸人類壽命、減緩衰老、防治疾病擴展自然生命，人工進化、優(yōu)生優(yōu)育 促進生命、信息、系統(tǒng)科學的交叉與發(fā)展第94頁，共109頁。5.4.3 人工生命的研究內(nèi)容和方法 人工生命的研究內(nèi)容人工生命的研究內(nèi)容大致可分為兩類：構(gòu)成生物體的內(nèi)部系統(tǒng)，包括腦、神經(jīng)系統(tǒng)、內(nèi)分泌系統(tǒng)、免疫系統(tǒng)、遺傳系統(tǒng)、酶系統(tǒng)、代謝系統(tǒng)等。5.4 人工生命在生物體及其群體的外部系統(tǒng)，包括環(huán)境

42、適應系統(tǒng)和遺傳進化系統(tǒng)等。 第95頁，共109頁。人工生命的科學框架 生命現(xiàn)象仿生系統(tǒng)生命現(xiàn)象的建模與仿真 進化動力學 人工生命的計算理論和工具 進化機器人 進化和學習等的結(jié)合 人工生命的應用5.4 人工生命第96頁，共109頁。人工生命的研究方法 （1）信息模型法 根據(jù)內(nèi)部和外部系統(tǒng)所表現(xiàn)的生命行為來建造信息模型。5.4 人工生命（2）工作原理法 生命行為所顯示的自律分數(shù)和非線性行為，其工作原理是混沌和分形，以此為基礎研究人工生命的機理。 第97頁，共109頁。人工生命的研究技術(shù)途徑 (1) 工程技術(shù)途徑 利用計算機、自動化、微電子、精密機械、光電通信、人工智能、神經(jīng)網(wǎng)絡等有關(guān)工程技術(shù)方法和

43、途徑，研究開發(fā)、設計制造人工生命。通過計算機屏幕，以及三維動畫，虛擬現(xiàn)實的軟件方法或采用光機電一體化的硬件裝置來演示和體現(xiàn)人工生命。 5.4 人工生命第98頁，共109頁。(2) 生物科學途徑 利用生物科學方法和技術(shù)，通過人工合成、基因控制，無性繁殖過程，培育生成人工生命。5.4 人工生命由于倫理學、社會學、人類學等方面的問題，通過生物科學途徑生成的人工生命，如克隆人引起了不少爭論。需要研究和制訂相應的社會監(jiān)督、國家法律和國際公約。第99頁，共109頁。5.4.4 人工生命的實例 人工腦 波蘭人工智能和心理學教授安奇布勒（Andrzej Buller）及一些日本學者在日本現(xiàn)代通訊研究所進化系統(tǒng)

44、研究室對人工腦的研究，已取得重要進展。5.4 人工生命計算機病毒 計算機進程 細胞自動機 人工核苷酸 第100頁，共109頁。 在計算機病毒出現(xiàn)以前，病毒一直是一個純生物學的概念。它是指具有一定生物學結(jié)構(gòu)的最小的生命單位，是一團能夠自主復制的遺傳物質(zhì)。自然界的生物病毒有很多種，總共1000多種，是自然界普遍存在的一種生命現(xiàn)象。 一般認為，計算機病毒這一概念是在1983年由美國專家科恩（Fred Cohen）在一次計算機安全學術(shù)會議上正式提出的，并獲準進行了實驗演示，從而證實了計算機病毒的存在。世界上最早發(fā)現(xiàn)的計算機病毒是“巴基斯坦”病毒，時間是1986年1月。1987年和1988年，計算機病毒肆虐歐美，1989年計算機病毒悄然登陸中華大地。截止目前，估計世界上已有的計算機病毒達6000余種，并越來越嚴重地威脅著計算機系統(tǒng)的安全，使得計算機用戶談毒色變、惶恐不安。于是人們一致地對計算機病毒采取了消滅與預防的策略和方針。第101頁，共109頁。 計算機病毒可能并非人們通常所認為的那樣只有消極作用、破壞性作用，如果我們能夠哲學地思考與看待計算機病毒，那么我們就會發(fā)現(xiàn)它所潛在的一些十分有益的作用、建設性的作用。計算機病毒有可能對人類探索生命的奧秘發(fā)揮十分獨特而積極的作用。第102頁，共109頁。 根據(jù)科恩于1983年給計算機病毒下的定義：計算機病毒是一種程序。它用