人工智能第五章9

人工智能原理

ArtificialIntelligencePrinciple信息工程學(xué)院張永梅第5章計(jì)算智能(2)進(jìn)化計(jì)算人工生命第五章計(jì)算智能(2)5.1遺傳算法5.2進(jìn)化戰(zhàn)略5.3進(jìn)化編程5.4人工生命第五章計(jì)算智能(2)作業(yè)：5-2，5-7，5-9答疑時(shí)間及地點(diǎn)答疑時(shí)間：每周四5、6節(jié)答疑地點(diǎn)：三教2604電子郵件：zhangym@聯(lián)絡(luò)方式：10842037第四章計(jì)算智能(1)4.1概述4.2神經(jīng)計(jì)算4.3模糊計(jì)算計(jì)算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化計(jì)算和人工生命等領(lǐng)域，它的研討和開展反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉與集成的重要開展趨勢(shì)。計(jì)算智能是自創(chuàng)仿生學(xué)的思想，基于人們對(duì)生物體智能機(jī)理的認(rèn)識(shí)，采用數(shù)值計(jì)算的方法去模擬和實(shí)現(xiàn)人類的智能。計(jì)算智能是一種以模型〔計(jì)算模型、數(shù)學(xué)模型〕為根底，以分布、并行計(jì)算為特征的自然智能模擬方法。進(jìn)化計(jì)算〔EvolutionaryComputation,EC〕包括：遺傳算法(geneticalgorithms，GA)進(jìn)化戰(zhàn)略(evolutionstrategies)進(jìn)化編程(evolutionaryprogramming)遺傳編程(geneticprogramming)人類不滿足于模擬生物進(jìn)化行為，希望可以建立具有自然生命特征的人造生命和人造生命系統(tǒng)。人工生命是人工智能和計(jì)算智能的一個(gè)新的研討熱點(diǎn)。進(jìn)化計(jì)算是一種對(duì)人類智能的演化模擬方法，它是經(jīng)過(guò)對(duì)生物遺傳和演化過(guò)程的認(rèn)識(shí)，用進(jìn)化算法去模擬人類智能的進(jìn)化規(guī)律的。人工生命(Artificiallife，AL)是經(jīng)過(guò)人工模擬生命系統(tǒng)，來(lái)研討生命的領(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é)家ChristopherLangton于1987年在LosAlamosNationalLaboratory召開的"生成以及模擬生命系統(tǒng)的國(guó)際會(huì)議"上提出。世界首個(gè)人工生命構(gòu)造誕生中新網(wǎng)2021年5月22日電綜合媒體報(bào)道，美國(guó)克萊格.文特爾研討所一個(gè)有華人參與的研討團(tuán)隊(duì)宣布，在實(shí)驗(yàn)中制造出世界首個(gè)完全由人造基因指令控制的人造生命，使人類的才干拓展到可以支配自然世界，未來(lái)可制造有特殊功能的生物，在消費(fèi)疫苗及干凈能源等領(lǐng)域大派用場(chǎng)。由美國(guó)生物學(xué)家文特爾指點(diǎn)的研討團(tuán)隊(duì)，重塑“絲狀支原體絲狀亞種〞(Mycoplasmamycoides)這種微生物的DNA，并將新DNA片段“黏〞在一同，植入另一種山羊支原體中。新生命于2021年4月誕生，昵稱“Synthia〞(合成體)，這種微生物由藍(lán)色細(xì)胞組成，可以生長(zhǎng)、繁衍，細(xì)胞分裂了逾10億次，產(chǎn)生一代又一代的人造生命。植入的DNA片段包含約850個(gè)基因，而人類DNA圖譜上共有約2萬(wàn)個(gè)基因。

進(jìn)化計(jì)算〔EvolutionaryComputation,EC〕包括：遺傳算法(geneticalgorithms，GA)進(jìn)化戰(zhàn)略(evolutionstrategies)進(jìn)化編程(evolutionaryprogramming)遺傳編程(geneticprogramming)其中，遺傳算法是進(jìn)化計(jì)算中最初構(gòu)成的一種具有普遍影響的模擬進(jìn)化優(yōu)化算法。因此我們主要討論遺傳算法。進(jìn)化計(jì)算是一種模擬自然界生物進(jìn)化過(guò)程與機(jī)制進(jìn)展問(wèn)題求解的自組織、自順應(yīng)的隨機(jī)搜索技術(shù)。它將生物進(jìn)化過(guò)程中的繁衍〔Reproduction〕變異〔Mutation〕競(jìng)爭(zhēng)〔Competition〕選擇〔Selection〕引入到了算法中。什么是進(jìn)化計(jì)算進(jìn)化計(jì)算的生物學(xué)根底自然界生物進(jìn)化過(guò)程是進(jìn)化計(jì)算的生物學(xué)根底，它主要包括:遺傳(Heredity)變異(Mutation)進(jìn)化(Evolution)實(shí)際

生物進(jìn)化與遺傳算法群體種群子群選擇婚配變異遭淘汰的群體遺傳算法(GeneticAlgorithm)達(dá)爾文進(jìn)化論：“物競(jìng)天擇、適者生存〞。70年代由美國(guó)的密執(zhí)根大學(xué)的Holland在他的著作<AdaptationinNaturalandArtificialSystems>初次提出遺傳算法，并主要由他和他的學(xué)生開展起來(lái)。近年來(lái)，遺傳算法作為一種有效的工具，已廣泛地運(yùn)用于最優(yōu)化問(wèn)題求解之中。第五章計(jì)算智能(2)5.1遺傳算法5.2進(jìn)化戰(zhàn)略5.3進(jìn)化編程5.4人工生命5.1遺傳算法遺傳算法是模擬生物遺傳學(xué)和自然選擇機(jī)理，經(jīng)過(guò)人工方式所構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過(guò)程進(jìn)展的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的最重要的方式。遺傳算法為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題指出了一個(gè)處理方法。進(jìn)化計(jì)算和遺傳算法自創(chuàng)了生物科學(xué)中的某些知識(shí)，這也表達(dá)了人工智能這一交叉學(xué)科的特點(diǎn)。5.1遺傳算法遺傳算法的來(lái)源自然界所提供的答案是經(jīng)過(guò)漫長(zhǎng)的自順應(yīng)——遺傳過(guò)程獲得的結(jié)果。我們也可以利用這一過(guò)程本身去處理一些復(fù)雜的問(wèn)題。遺傳算法的研討主要集中在以下幾個(gè)方面：函數(shù)優(yōu)化、組合優(yōu)化消費(fèi)調(diào)度、自動(dòng)控制、機(jī)器人學(xué)、圖像處置、人工生命、演化編程和機(jī)器學(xué)習(xí)。5.1.1遺傳算法的根本機(jī)理霍蘭德的遺傳算法通常稱為簡(jiǎn)單遺傳算法〔SimpleGeneticAlgorithm,SGA〕?，F(xiàn)以此作為討論主要對(duì)象，加上順應(yīng)的改良，來(lái)分析遺傳算法的構(gòu)造和機(jī)理。5.1遺傳算法編碼與解碼順應(yīng)度函數(shù)遺傳操作5.1.1遺傳算法的根本機(jī)理5.1遺傳算法根本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法那么選擇個(gè)體，并經(jīng)過(guò)雜交、變異來(lái)產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目的為止。遺傳算法的根本概念遺傳算法〔GeneticAlgorithm〕是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型，是一種經(jīng)過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。5.1.1遺傳算法的根本機(jī)理5.1遺傳算法遺傳算法的根本概念遺傳算法是從代表問(wèn)題能夠潛在的解集的一個(gè)種群〔population〕開場(chǎng)的，而一個(gè)種群那么由經(jīng)過(guò)基因〔gene〕編碼的一定數(shù)目的個(gè)體〔individual〕組成。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代〔generation〕演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的順應(yīng)度〔fitness〕大小挑選〔selection〕個(gè)體，并借助于自然遺傳學(xué)的遺傳算子〔geneticoperators〕進(jìn)展組合交叉〔crossover〕和變異〔mutation〕，產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加順應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼〔decoding〕，可以作為問(wèn)題近似最優(yōu)解。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í)踐值本身，而遺傳算法處置決策變量的某種編碼方式，使得我們可以自創(chuàng)生物學(xué)中的染色體和基因的概念，可以模擬自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們可以方便地運(yùn)用遺傳操作算子。

2、遺傳算法直接以順應(yīng)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它輔助信息。

3、遺傳算法運(yùn)用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。4、遺傳算法運(yùn)用概率搜索技術(shù)，而非確定性規(guī)那么。5.1.1遺傳算法的根本機(jī)理5.1遺傳算法根本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法那么選擇個(gè)體，并經(jīng)過(guò)雜交、變異來(lái)產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目的為止。遺傳算法的根本概念種群〔Population〕：種群是初始給定的多個(gè)解的集合。它普通是整個(gè)搜索空間的一個(gè)很小的子集。個(gè)體〔Individual〕：個(gè)體是指種群中的單個(gè)元素。一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。染色體〔Chromos〕：由多個(gè)基因組成，表示一個(gè)個(gè)體。染色體是指對(duì)個(gè)體進(jìn)展編碼后所得到的編碼串。染色體中的每1位稱為基因，染色體上由假設(shè)干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組。順應(yīng)度〔Fitness〕函數(shù)：順應(yīng)度函數(shù)是一種用來(lái)對(duì)種群中各個(gè)個(gè)體的環(huán)境順應(yīng)性進(jìn)展度量的函數(shù)。其函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要根據(jù)。5.1.1遺傳算法的根本機(jī)理5.1遺傳算法遺傳算法的根本概念順應(yīng)度(fitness)自創(chuàng)生物個(gè)體對(duì)環(huán)境的順應(yīng)程度，而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度順應(yīng)度函數(shù)(fitnessfunction)問(wèn)題中的全體個(gè)體與其順應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系普通是一個(gè)實(shí)值函數(shù)該函數(shù)就是遺傳算法中指點(diǎn)搜索的評(píng)價(jià)函數(shù)5.1.1遺傳算法的根本機(jī)理5.1遺傳算法遺傳算法的根本概念染色體(chromosome)染色體是由假設(shè)干基因組成的位串〔生物學(xué)〕個(gè)體對(duì)象由假設(shè)干字符串組成來(lái)表示〔遺傳算法〕個(gè)體染色體9----1001〔2，5，6〕----010101110遺傳算法(geneticalgorithm)染色體就是問(wèn)題中個(gè)體的某種字符串方式的編碼表示染色體以字符串來(lái)表示基因是字符串中的一個(gè)個(gè)字符5.1.1遺傳算法的根本機(jī)理5.1遺傳算法遺傳算法的根本概念編碼與解碼將問(wèn)題構(gòu)造變換為位串方式編碼表示的過(guò)程叫編碼；將位串方式編碼表示變換為原問(wèn)題構(gòu)造的過(guò)程叫解碼或譯碼。Huffman編碼方法是一種效率高、方法簡(jiǎn)單的編碼。信源中符號(hào)出現(xiàn)的概率相差越大，Huffman編碼效果越好。哈夫曼〔Huffman〕編碼Huffman編碼普通可將數(shù)據(jù)緊縮20%至90%，其緊縮效率取決于被緊縮數(shù)據(jù)的特征?！?〕把信源符號(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為止；Huffman編碼步驟〔5〕用線將符號(hào)銜接起來(lái)，從而得到一個(gè)碼樹，樹的N個(gè)端點(diǎn)對(duì)應(yīng)N個(gè)信源符號(hào)；

〔6〕從最后一個(gè)概率為1的節(jié)點(diǎn)開場(chǎng)，沿著到達(dá)信源的每個(gè)符號(hào)，將一路遇到的二進(jìn)制碼“0〞或“1〞順序陳列起來(lái)，就是端點(diǎn)所對(duì)應(yīng)的信源符號(hào)的碼字。Huffman編碼方法例如：信源符號(hào)分布為：a:4/22b:3/22c:2/22d:1/22e:5/22f:7/22排序?yàn)椋篸,c,b,a,e,f1/222/223/224/225/227/22Huffman編碼方法cbafe7/225/224/222/2210f=11e=01a=00b=101c=1001d=1000d1/223/226/2222/2213/229/223/2210101010哈夫曼解碼在通訊中，假設(shè)將字符用哈夫曼編碼方式發(fā)送出去，對(duì)方接納到編碼后，將編碼復(fù)原成字符的過(guò)程，稱為哈夫曼解〔譯〕碼。解碼:從根結(jié)點(diǎn)起，每輸入一個(gè)數(shù)碼即沿二叉樹下移一層，數(shù)碼為0時(shí)移向左分支，數(shù)碼為1時(shí)移向右分支，待到達(dá)葉子結(jié)點(diǎn)時(shí)即譯出一個(gè)字符，再輸入的數(shù)碼又從根結(jié)點(diǎn)開場(chǎng)重新做起。反復(fù)由根出發(fā)，直到譯碼完成。5.1.1遺傳算法的根本機(jī)理5.1遺傳算法遺傳算法的根本概念遺傳操作〔GeneticOperator〕：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。包括以下3種根本方式：選擇〔Selection〕交叉〔Crosssover〕變異〔Mutation〕5.1.1遺傳算法的根本機(jī)理5.1遺傳算法遺傳算法的根本概念遺傳操作選擇操作也叫復(fù)制〔reproduction〕操作，根據(jù)個(gè)體的順應(yīng)度函數(shù)值所度量的優(yōu)劣程度決議它在下一代是被淘汰還是被遺傳。交叉操作的簡(jiǎn)一方式是將被選擇出的兩個(gè)個(gè)體P1和P2作為父母?jìng)€(gè)體，將兩者的部分碼值進(jìn)展交換。變異操作的簡(jiǎn)一方式是改動(dòng)數(shù)碼串的某個(gè)位置上的數(shù)碼。二進(jìn)制編碼表示的簡(jiǎn)單變異操作是將0與1互換：0變異為1，1變異為0。選擇算子模擬生物界優(yōu)勝劣汰的自然選擇法那么的一種染色體運(yùn)算從種群中選擇順應(yīng)度較高的染色體進(jìn)展復(fù)制，以生成下一代種群算法：個(gè)體順應(yīng)度計(jì)算在被選集中每個(gè)個(gè)體具有一個(gè)選擇概率選擇概率取決于種群中個(gè)體的順應(yīng)度及其分布個(gè)體順應(yīng)度計(jì)算，即個(gè)體選擇概率計(jì)算個(gè)體選擇方法按照順應(yīng)度進(jìn)展父代個(gè)體的選擇交叉算子交換、交配、雜交互換兩個(gè)染色體某些位上的基因隨機(jī)化算子，生成新個(gè)體變異算子突變改動(dòng)染色體某個(gè)/些位上的基因隨機(jī)化算子，生成新個(gè)體次要算子，但在恢復(fù)群體中失去的多樣性方面具有潛在的作用生物進(jìn)化與遺傳算法之間的對(duì)應(yīng)關(guān)系生物進(jìn)化中的概念遺傳算法中的作用環(huán)境適應(yīng)性適者生存?zhèn)€體染色體基因種群(群體)交叉變異生物進(jìn)化與遺傳算法之間的對(duì)應(yīng)關(guān)系生物進(jìn)化中的概念遺傳算法中的作用環(huán)境適應(yīng)函數(shù)適應(yīng)性函數(shù)適應(yīng)值適者生存適應(yīng)函數(shù)值最大的解被保留的概率最大個(gè)體問(wèn)題的一個(gè)解染色體解的編碼基因編碼的元素種群(群體)根據(jù)適應(yīng)函數(shù)選擇的一組解交叉以一定的方式由雙親產(chǎn)生后代的過(guò)程變異編碼的某些分量發(fā)生變化的過(guò)程5.1.2遺傳算法的求解步驟遺傳算法的主要特點(diǎn)5.1遺傳算法(1)

遺傳算法利用目的函數(shù)的順應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來(lái)指點(diǎn)搜索；(2)

遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)那么進(jìn)展隨機(jī)操作。遺傳算法對(duì)種群中的染色體反復(fù)做三種遺傳操作使其朝著順應(yīng)度增高的方向不斷更新?lián)Q代，直至出現(xiàn)了順應(yīng)度滿足目的條件的染色體為止遺傳算法參數(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染色體編碼長(zhǎng)度L

遺傳算法流程圖(1)初始化群體;5.1遺傳算法(2)計(jì)算群體上每個(gè)個(gè)體的順應(yīng)度值;(3)按由個(gè)體順應(yīng)度值所決議的某個(gè)規(guī)那么選擇將進(jìn)入下一代的個(gè)體;(4)按概率Pc進(jìn)展交叉操作;

(5)按概率Pc進(jìn)展變異操作;

(6)假設(shè)沒有滿足某種停頓條件，那么轉(zhuǎn)第(2)步，否那么進(jìn)入下一步。(7)輸出群體中順應(yīng)度值最優(yōu)的染色體作為問(wèn)題的稱心解或最優(yōu)解。GA算法框圖普通遺傳算法的主要步驟如下：(1)隨機(jī)產(chǎn)生一個(gè)由確定長(zhǎng)度的特征字符串組成的初始群體。5.1遺傳算法(2)

對(duì)該字符串群體迭代地執(zhí)行下面的步驟①和②，直到滿足停頓規(guī)范：①計(jì)算群體中每個(gè)個(gè)體字符串的順應(yīng)值；②運(yùn)用選擇、交叉、變異等遺傳算子產(chǎn)生下一代群體。(3)

把在后代中出現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問(wèn)題的一個(gè)解。產(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é)果終了是否是否變異復(fù)制交叉5.1遺傳算法流程圖例：求函數(shù)的最大值例：求函數(shù)的最大值其中x為[0,31]間的整數(shù)編碼：采用二進(jìn)制方式編碼由于x的定義域是[0,31]間的整數(shù)，剛好可以用5位二進(jìn)制數(shù)表示，因此可以用5位二進(jìn)制數(shù)表示該問(wèn)題的解，即染色體。如00000表示x＝0，10101表示x＝21，11111表示x＝31等問(wèn)題：求〔1〕編碼：此時(shí)取均長(zhǎng)為5，每個(gè)染色體〔2〕初始群體生成：群體大小視情況而定，此處設(shè)置為4，隨機(jī)產(chǎn)生四個(gè)個(gè)體：編碼：01101，11000，01000，10011解碼：1324819順應(yīng)度：16957664361〔3〕順應(yīng)度評(píng)價(jià)：〔4〕選擇：選擇概率個(gè)體：01101，11000，01000，10011順應(yīng)度：16957664361選擇概率：0.140.490.060.31選擇結(jié)果：01101，11000，11000，10011〔5〕交叉操作：發(fā)生交叉的概率較大，變異概率很小。哪兩個(gè)個(gè)體配對(duì)交叉是隨機(jī)的。交叉點(diǎn)位置的選取是隨機(jī)的〔單點(diǎn)交叉〕0110101100110001101111000110011001110000假設(shè)采用輪盤式選擇個(gè)體，四個(gè)個(gè)體依次選中次數(shù)為1，2，0，1。染色體11001在種群中出現(xiàn)了2次，而原染色體01000那么因順應(yīng)值太小而被淘汰。輪盤式選擇首先計(jì)算每個(gè)個(gè)體i被選中的概率然后根據(jù)概率的大小將圓盤分為n個(gè)扇形。選擇時(shí)轉(zhuǎn)動(dòng)輪盤，參考點(diǎn)r落到扇形i，那么選擇個(gè)體i。......p1p2pir從統(tǒng)計(jì)角度看，個(gè)體的順應(yīng)度值越大，其對(duì)應(yīng)的扇區(qū)的面積越大，被選中的能夠性也越大。這種方法有點(diǎn)類似于發(fā)放獎(jiǎng)品運(yùn)用的輪盤，并帶有某種賭博的意思，因此亦被稱為賭輪選擇。交叉操作交叉〔Crossover〕操作是指按照某種方式對(duì)選擇的父代個(gè)體的染色體的部分基因進(jìn)展交配重組，從而構(gòu)成新的個(gè)體。交配重組是自然界中生物遺傳進(jìn)化的一個(gè)主要環(huán)節(jié)，也是遺傳算法中產(chǎn)生新的個(gè)體的最主要方法。

根本遺傳操作單點(diǎn)交叉單點(diǎn)交叉也稱簡(jiǎn)單交叉，它是先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，然后對(duì)這兩個(gè)父代個(gè)體交叉點(diǎn)前面或后面部分的基因進(jìn)展交換，并生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn隨機(jī)選擇第k位為交叉點(diǎn)，假設(shè)采用對(duì)交叉點(diǎn)后面的基因進(jìn)展交換的方法，交叉后生成的兩個(gè)新的個(gè)體是：X’=x1x2…xkyk+1…ynY’=y1y2…ykxk+1…xn

例設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，假設(shè)隨機(jī)交叉點(diǎn)為4，那么交叉后生成的兩個(gè)新的個(gè)體是：A’=001110B’=110001〔4〕選擇：選擇概率個(gè)體：01101，11000，01000，10011順應(yīng)度：16957664361選擇概率：0.140.490.060.31選擇結(jié)果：01101，11000，11000，10011〔5〕交叉操作：發(fā)生交叉的概率較大，變異概率很小。哪兩個(gè)個(gè)體配對(duì)交叉是隨機(jī)的。交叉點(diǎn)位置的選取是隨機(jī)的〔單點(diǎn)交叉〕0110101100110001101111000110011001110000假設(shè)采用輪盤式選擇個(gè)體，四個(gè)個(gè)體依次選中次數(shù)為1，2，0，1。染色體11001在種群中出現(xiàn)了2次，而原染色體01000那么因順應(yīng)值太小而被淘汰?！?〕變異：發(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ù)上述操作。闡明：GA的終止條件普通人為設(shè)置；GA只能求次優(yōu)解或稱心解。分析：按第二代新群體進(jìn)展遺傳操作，假設(shè)無(wú)變異，永遠(yuǎn)也找不到最優(yōu)解——擇優(yōu)取代有問(wèn)題。假設(shè)隨機(jī)地將個(gè)體01101選入新群體中，有能夠找到最優(yōu)解。在經(jīng)過(guò)編碼以后，遺傳算法幾乎不需求任何與問(wèn)題有關(guān)的知識(shí)，獨(dú)一需求的信息是順應(yīng)值的計(jì)算。也不需求運(yùn)用者對(duì)問(wèn)題有很深化的了解和求解技巧，經(jīng)過(guò)選擇、交叉和變異等簡(jiǎn)單的操作求解復(fù)雜的問(wèn)題，是一個(gè)比較通用的優(yōu)化算法。收斂性定理假設(shè)在代的進(jìn)化過(guò)程中，遺傳算法每次保管到目前為止的最好解，并且算法以交叉和變異為其隨機(jī)化操作，那么對(duì)于一個(gè)全局最優(yōu)化問(wèn)題，當(dāng)進(jìn)化代數(shù)趨于無(wú)窮時(shí)，遺傳算法找到最優(yōu)解的概率為1。遺傳算法圖搜索解空間搜索問(wèn)題空間搜索->解隨機(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)知識(shí)全局搜索約束較多算法比較遺傳算法的實(shí)現(xiàn)5.1遺傳算法遺傳算法是一種自創(chuàng)生物界自然選擇和進(jìn)化機(jī)制開展起來(lái)的高度并行、隨機(jī)、自順應(yīng)的搜索方法。MATLAB通用遺傳算法工具箱GAOT運(yùn)用群體搜索技術(shù)，將種群代表一組問(wèn)題的解，經(jīng)過(guò)對(duì)當(dāng)前種群施加選擇、交叉和變異等一系列遺傳操作，從而得到新的一代種群，并逐漸使種群進(jìn)化到包含近似最優(yōu)解形狀。第五章計(jì)算智能(2)5.1遺傳算法5.2進(jìn)化戰(zhàn)略5.3進(jìn)化編程5.4人工生命5.2進(jìn)化戰(zhàn)略進(jìn)化戰(zhàn)略(EvolutionStrategies，ES)是一類模擬自然進(jìn)化原理以求解參數(shù)優(yōu)化問(wèn)題的算法。它是由雷切伯格〔Rechenberg〕、施韋費(fèi)爾〔Schwefel〕和彼得·比納特〔PeterBienert〕于1964年提出的，并在德國(guó)共同建立的。5.2.1進(jìn)化戰(zhàn)略的算法模型尋求與函數(shù)極值關(guān)聯(lián)的實(shí)n維矢量x。隨機(jī)選擇父矢量的初始群體?！搽p親向量的初始群體〕父矢量xi,i=1,…,p產(chǎn)生子代矢量xi?！沧訉O向量的創(chuàng)建〕對(duì)誤差(i=1,…,p)排序以選擇和決議堅(jiān)持哪些矢量。繼續(xù)產(chǎn)生新的實(shí)驗(yàn)數(shù)據(jù)以及選擇最小誤差矢量。該過(guò)程將繼續(xù)到找到符合條件的答案或者一切的計(jì)算曾經(jīng)全部完成為止。5.2進(jìn)化戰(zhàn)略最簡(jiǎn)單方式的進(jìn)化戰(zhàn)略可描畫如下：5.2.2進(jìn)化戰(zhàn)略和遺傳算法的區(qū)別進(jìn)化戰(zhàn)略和遺傳算法有著很強(qiáng)的類似性，它們都是一類模擬自然進(jìn)化原理的算法。5.2進(jìn)化戰(zhàn)略兩者也存在著區(qū)別，其中最根本的區(qū)別是它們的研討領(lǐng)域不同。進(jìn)化戰(zhàn)略是一種數(shù)值優(yōu)化的方法，它采用一個(gè)具有自順應(yīng)步長(zhǎng)和傾角的特定爬山方法。遺傳算法從廣義上說(shuō)是一種自順應(yīng)搜索技術(shù)。5.2.2進(jìn)化戰(zhàn)略和遺傳算法的區(qū)別除了研討和運(yùn)用領(lǐng)域外，進(jìn)化戰(zhàn)略和遺傳算法還有以下區(qū)別：(1)進(jìn)化戰(zhàn)略和遺傳算法表示個(gè)體的方式不同，

進(jìn)化戰(zhàn)略在浮點(diǎn)矢量上運(yùn)轉(zhuǎn)，而遺傳算法普通運(yùn)轉(zhuǎn)在二進(jìn)制矢量上。

5.2進(jìn)化戰(zhàn)略(2)進(jìn)化戰(zhàn)略和遺傳算法的選擇過(guò)程不同。(3)進(jìn)化戰(zhàn)略和遺傳算法的復(fù)制參數(shù)不同，遺傳算法的復(fù)制參數(shù)(交叉和變異的能夠性)在進(jìn)化過(guò)程中堅(jiān)持恒定，而進(jìn)化戰(zhàn)略時(shí)時(shí)改動(dòng)它們。隨著技術(shù)的開展，進(jìn)化戰(zhàn)略和遺傳算法以上的差別越來(lái)越不明顯。第五章計(jì)算智能(2)5.1遺傳算法5.2進(jìn)化戰(zhàn)略5.3進(jìn)化編程5.4人工生命5.3進(jìn)化編程進(jìn)化編程(EvolutionaryProgramming，EP)，又稱為進(jìn)化規(guī)劃〔EvolutionaryPlanning〕，是由福格爾〔Fogel〕在1962年提出的一種模擬人類智能的方法。進(jìn)化編程根據(jù)正確預(yù)測(cè)的符號(hào)數(shù)來(lái)度量順應(yīng)值。經(jīng)過(guò)變異，為父代群體中的每個(gè)機(jī)器形狀產(chǎn)生一個(gè)子代。父代和子代中最好的部分被選擇生存下來(lái)。它的提出是受自然生物進(jìn)化機(jī)制的啟發(fā)。5.3.1進(jìn)化編程的機(jī)理與表示進(jìn)化編程的過(guò)程，可了解為從一切能夠的計(jì)算機(jī)程序構(gòu)成的空間中，搜索具有高的順應(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ī)程序群體開場(chǎng)，群體中每個(gè)計(jì)算機(jī)程序個(gè)體是用順應(yīng)度來(lái)評(píng)價(jià)的，該順應(yīng)值與特定的問(wèn)題領(lǐng)域有關(guān)。5.3.2進(jìn)化編程的步驟進(jìn)化編程分為三個(gè)步驟：產(chǎn)生初始群體。它由關(guān)于問(wèn)題(計(jì)算機(jī)程序)的函數(shù)隨機(jī)組合而成。5.3進(jìn)化編程迭代完成下述子步驟，直至滿足選中規(guī)范為止：執(zhí)行群體中的每個(gè)程序，根據(jù)它處理問(wèn)題的才干，給它指定一個(gè)順應(yīng)值。運(yùn)用變異等操作發(fā)明新程序群體?；陧槕?yīng)值根據(jù)概率從群體中選出一個(gè)計(jì)算機(jī)程序個(gè)體，然后用適宜的操作作用于該計(jì)算機(jī)程序個(gè)體。把現(xiàn)有的計(jì)算機(jī)程序復(fù)制到新的群體中。經(jīng)過(guò)遺傳隨機(jī)重組兩個(gè)現(xiàn)有的程序,發(fā)明出新的計(jì)算機(jī)程序個(gè)體。在后代中順應(yīng)值最高的計(jì)算機(jī)程序個(gè)體被指定為進(jìn)化編程的結(jié)果。這一結(jié)果能夠是問(wèn)題的解或近似解。變異和發(fā)明子代評(píng)價(jià)已存在的FSM用最好的形狀機(jī)預(yù)測(cè)和添加符號(hào)選擇父代初始化觀測(cè)順序是否能否預(yù)測(cè)初始化群體圖進(jìn)化編程的根本過(guò)程5.3進(jìn)化編程FSM〔FiniteStateMachine，有限形狀機(jī)〕進(jìn)化計(jì)算的三種算法即遺傳算法、進(jìn)化戰(zhàn)略和進(jìn)化編程都是模擬生物界自然進(jìn)化過(guò)程而建立的魯棒性計(jì)算機(jī)算法。在一致框架下對(duì)三種算法進(jìn)展比較，可以發(fā)現(xiàn)它們有許多類似之處，同時(shí)也存在較大的差別。進(jìn)化戰(zhàn)略和進(jìn)化編程都把變異作為主要搜索算子，而在規(guī)范的遺傳算法中，變異只處于次要位置。交叉在遺傳算法中起著重要作用，而在進(jìn)化編程中卻被完全省去，在進(jìn)化戰(zhàn)略中與自順應(yīng)結(jié)合運(yùn)用，起了很重要的作用。規(guī)范遺傳算法和進(jìn)化編程都強(qiáng)調(diào)隨機(jī)選擇機(jī)制的重要性，而從進(jìn)化戰(zhàn)略的角度看，選擇〔復(fù)制〕是完全確定的。進(jìn)化戰(zhàn)略和進(jìn)化編程確定地把某些個(gè)體排除在被選擇〔復(fù)制〕之外，而規(guī)范遺傳算法普通都對(duì)每個(gè)個(gè)體指定一個(gè)非零的選擇概率。第五章計(jì)算智能(2)5.1遺傳算法5.2進(jìn)化戰(zhàn)略5.3進(jìn)化編程5.4人工生命5.4人工生命自然界是生命之源。自然生命千千萬(wàn)萬(wàn)，千姿百態(tài)，千差萬(wàn)別，巧奪天工，奇妙無(wú)窮。人工生命〔ArtificialLife，AL〕試圖經(jīng)過(guò)人工方法建造具有自然生命特征的人造系統(tǒng)。人工生命是生命科學(xué)、信息科學(xué)和系統(tǒng)科學(xué)等學(xué)科交叉研討的產(chǎn)物，其研討成果必將促進(jìn)人工智能的開展。5.4.1人工生命研討的來(lái)源和開展人類長(zhǎng)期以來(lái)不斷力圖用科學(xué)技術(shù)方法模擬自然界，包括人腦本身。1943年麥卡絡(luò)奇和皮茨提出了M－P神經(jīng)學(xué)網(wǎng)絡(luò)模型。5.4人工生命人工生命的許多早期研討任務(wù)也源于人工智能。20世紀(jì)70年代以來(lái)，康拉德〔Conrad〕等提出不斷完善的“人工世界〞模型。20世紀(jì)80年代，人工神經(jīng)網(wǎng)絡(luò)再度興起促進(jìn)人工生命的開展。在1987年第一次人工生命研討會(huì)上，美國(guó)圣塔菲研討所〔SantaFeInstitute，SFI〕非線性研討組的蘭頓〔Langton〕正式提出人工生命的概念，建立起人工生命新學(xué)科。以后，人工生命研討進(jìn)入一個(gè)蓬勃開展的新時(shí)期。5.4.2人工生命的定義和研討意義人工生命是一項(xiàng)籠統(tǒng)地提取控制生物景象的根本動(dòng)態(tài)原理，并且經(jīng)過(guò)物理媒介〔如計(jì)算機(jī)〕來(lái)模擬生命系統(tǒng)動(dòng)態(tài)開展過(guò)程的研討任務(wù)。5.4人工生命通俗地講，人工生命即人造的生命，非自然的生命。然而，要對(duì)人工生命做出嚴(yán)厲的定義，卻需求對(duì)問(wèn)題進(jìn)展深化研討。人工生命系統(tǒng)1987年蘭德提出的人工生命定義為：“人工生命是研討可以演示出自然生命系統(tǒng)特征行為的人造系統(tǒng)〞。5.4人工生命經(jīng)過(guò)計(jì)算機(jī)或其它機(jī)器對(duì)類似生命的行為進(jìn)展綜合研討，以便對(duì)傳統(tǒng)生物科學(xué)起互補(bǔ)作用。蘭德在計(jì)算機(jī)上演示了他們研制的具有生命特征的軟件系統(tǒng)，并把這類具有生命景象和特征的人造系統(tǒng)稱為人工生命系統(tǒng)。自然生命的共同特征和景象自繁衍、自進(jìn)化、自尋優(yōu)自生長(zhǎng)、自學(xué)習(xí)、自組織自穩(wěn)定、自順應(yīng)、自協(xié)調(diào)物質(zhì)構(gòu)造能量轉(zhuǎn)換信息處置5.4人工生命研討人工生命的意義人工生命是自然生命的模擬、延伸與擴(kuò)展，其研討開發(fā)有艱苦的科學(xué)意義和廣泛的運(yùn)用價(jià)值。5.4人工生命

開發(fā)基于人工生命的工程技術(shù)新方法、新系統(tǒng)、新產(chǎn)品為自然生命的研討提供新模型、新工具、新環(huán)境延伸人類壽命、減緩衰老、防治疾病擴(kuò)展自然生命，人工進(jìn)化、優(yōu)生優(yōu)育促進(jìn)生命、信息、系統(tǒng)科學(xué)的交叉與開展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)境順應(yīng)系統(tǒng)和遺傳進(jìn)化系統(tǒng)等。人工生命的科學(xué)框架生命景象仿生系統(tǒng)生命景象的建模與仿真進(jìn)化動(dòng)力學(xué)人工生命的計(jì)算實(shí)際和工具進(jìn)化機(jī)器人進(jìn)化和學(xué)習(xí)等的結(jié)合人工生命的運(yùn)用5.4人工生命人工生命的研討方法〔1〕信息模型法根據(jù)內(nèi)部和外部系統(tǒng)所表現(xiàn)的生命行為來(lái)建造信息模型。5.4人工生命〔2〕任務(wù)原理法生命行為所顯示的自律分?jǐn)?shù)和非線性行為，其任務(wù)原理是混沌和分形，以此為根底研討人工生命的機(jī)理。人工生命的研討技術(shù)途徑

(1)工程技術(shù)途徑利用計(jì)算機(jī)、自動(dòng)化、微電子、精細(xì)機(jī)械、光電通訊、人工智能、神經(jīng)網(wǎng)絡(luò)等有關(guān)工程技術(shù)方法和途徑，研討開發(fā)、設(shè)計(jì)制造人工生命。經(jīng)過(guò)計(jì)算機(jī)屏幕，以及三維動(dòng)畫，虛擬現(xiàn)實(shí)的軟件方法或采用光機(jī)電一體化的硬件安裝來(lái)演示和表達(dá)人工生命。5.4人工生命(2)生物科學(xué)途徑利用生物科學(xué)方法和技術(shù)，經(jīng)過(guò)人工合成、基因控制，無(wú)性繁衍過(guò)程，培育生成人工生命。5.4人工生命由于倫理學(xué)、社會(huì)學(xué)、人類學(xué)等方面的問(wèn)題，經(jīng)過(guò)生物科學(xué)途徑生成的人工生命，如克隆人引起了不少爭(zhēng)論。需求研討和制定相應(yīng)的社會(huì)監(jiān)視、國(guó)家法律和國(guó)際公約。5.4.4人工生命的實(shí)例人工腦波蘭人工智能和心思學(xué)教授安奇·布勒〔AndrzejBuller〕及一些日本學(xué)者在日本現(xiàn)代通訊研討所進(jìn)化系統(tǒng)研討室對(duì)人工腦的研討，已獲得重要進(jìn)展。5.4人工生命計(jì)算機(jī)病毒計(jì)算機(jī)進(jìn)程細(xì)胞自動(dòng)機(jī)人工核苷酸在計(jì)算機(jī)病毒出現(xiàn)以前，病毒不斷是一個(gè)純生物學(xué)的概念。它是指具有一定生物學(xué)構(gòu)造的最小的生命單位，是一團(tuán)可以自主復(fù)制的遺傳物質(zhì)。自然界的生物病毒有很多種，總共1000多種，是自然界普遍存在的一種生命景象。

普通以為，計(jì)算機(jī)病毒這一概念是在1983年由美國(guó)專家科恩〔FredCohen〕在一次計(jì)算機(jī)平安學(xué)術(shù)會(huì)議上正式提出的，并獲準(zhǔn)進(jìn)展了實(shí)驗(yàn)演示，從而證明了計(jì)算機(jī)病毒的存在。世界上最早發(fā)現(xiàn)的計(jì)算機(jī)病毒是“巴基斯坦〞病毒，時(shí)間是1986年1月。1987年和1988年，計(jì)算機(jī)病毒肆虐歐美，1989年計(jì)算機(jī)病毒悄然登陸中華大地。截止目前，估計(jì)世界上已有的計(jì)算機(jī)病毒達(dá)6000余種，并越來(lái)越嚴(yán)重地要挾著計(jì)算機(jī)系統(tǒng)的平安，使得計(jì)算機(jī)用戶談毒色變、惶恐不安。于是人們一致地對(duì)計(jì)算機(jī)病毒采取了消滅與預(yù)防的戰(zhàn)略和方針。計(jì)算機(jī)病毒能夠并非人們通常所以為的那樣只需消極作用、破壞性作用，假設(shè)我們可以哲學(xué)地思索與對(duì)待計(jì)算機(jī)病毒，那么我們就會(huì)發(fā)現(xiàn)它所潛在的一些非常有益的作用、建立性的作用。計(jì)算機(jī)病毒有能夠?qū)θ祟愄角笊膴W妙發(fā)揚(yáng)非常獨(dú)特而積極的作用。

根據(jù)科恩于1983年給計(jì)算機(jī)病毒下的定義：計(jì)算機(jī)病毒是一種程序。它用修正其他程序的方法將本身的準(zhǔn)確拷貝或者能夠演化的拷貝放入其他程序，從而感染其