人工智能原理課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、后一個(gè)概率為1的節(jié)點(diǎn)開始，沿著到達(dá)信源的每個(gè)符號(hào)，將一路遇到的二進(jìn)制碼“0”或“1”順序排列起來，就是端點(diǎn)所對(duì)應(yīng)的信源符號(hào)的碼字。第30頁，共109頁。 Huffman編碼方法例如：信源符號(hào)分布為： a:4/22 b:3/22 c:2/22 d:1/22 e:5/22 f:7/22排序?yàn)椋?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ā)送出去，對(duì)方接收到編碼后，將編碼還原成字符的過程，稱為哈夫曼解（譯）碼。 解碼: 從根結(jié)點(diǎn)起，每輸入一個(gè)數(shù)碼即沿二叉樹下移一層，數(shù)碼為0時(shí)移向左分支，數(shù)碼為1時(shí)移向右分支，待達(dá)到葉子結(jié)點(diǎn)時(shí)即譯出一個(gè)字符，再輸入的數(shù)碼又從根結(jié)點(diǎn)開始重新做起。反復(fù)由根出發(fā)，直到譯碼完成。 第33頁，共109頁。5.1.1 遺傳算法的基本機(jī)理 5.1 遺傳算法遺傳算法的基本概念遺傳操作（Genetic Operator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。包括以下3種基本形式： 選擇（Selection） 交叉（Cr

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

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

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

21、度增高的方向不斷更新?lián)Q代，直至出現(xiàn)了適應(yīng)度滿足目標(biāo)條件的染色體為止第43頁，共109頁。遺傳算法參數(shù)種群規(guī)模種群的大小，用染色體個(gè)數(shù)表示最大換代數(shù)種群更新?lián)Q代的上限，也是算法終止一個(gè)條件交叉率Pc參加交叉運(yùn)算的染色體個(gè)數(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) 計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值; (3) 按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、工生命第93頁，共109頁。研究人工生命的意義 人工生命是自然生命的模擬、延伸與擴(kuò)展，其研究開發(fā)有重大的科學(xué)意義和廣泛的應(yīng)用價(jià)值。5.4 人工生命 開發(fā)基于人工生命的工程技術(shù)新方法、新系統(tǒng)、新產(chǎn)品 為自然生命的研究提供新模型、新工具、新環(huán)境 延伸人類壽命、減緩衰老、防治疾病擴(kuò)展自然生命，人工進(jìn)化、優(yōu)生優(yōu)育 促進(jìn)生命、信息、系統(tǒng)科學(xué)的交叉與發(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、適應(yīng)系統(tǒng)和遺傳進(jìn)化系統(tǒng)等。 第95頁，共109頁。人工生命的科學(xué)框架 生命現(xiàn)象仿生系統(tǒng)生命現(xiàn)象的建模與仿真 進(jìn)化動(dòng)力學(xué) 人工生命的計(jì)算理論和工具 進(jìn)化機(jī)器人 進(jìn)化和學(xué)習(xí)等的結(jié)合 人工生命的應(yīng)用5.4 人工生命第96頁，共109頁。人工生命的研究方法 （1）信息模型法 根據(jù)內(nèi)部和外部系統(tǒng)所表現(xiàn)的生命行為來建造信息模型。5.4 人工生命（2）工作原理法 生命行為所顯示的自律分?jǐn)?shù)和非線性行為，其工作原理是混沌和分形，以此為基礎(chǔ)研究人工生命的機(jī)理。 第97頁，共109頁。人工生命的研究技術(shù)途徑 (1) 工程技術(shù)途徑 利用計(jì)算機(jī)、自動(dòng)化、微電子、精密機(jī)械、光電通信、人工智能、神經(jīng)網(wǎng)絡(luò)等有關(guān)工程技術(shù)方法和

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

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