第九章人工生命與智能計算9.1人任務生命概述9.2遺傳算法9.3粒子群優化算法9.4元胞自動機9.5蟻群算法1人工生命人工生命是指用計算機和精細機械等生成或構造表現自然生命系統行為特點的仿真系統或模型系統。自然生命系統的行為特點表現為自組織、自修復、自復制的根本性質，以及構成這些性質的混沌動力學、環境順應和進化。在現實世界中，普遍地存在著各類復雜系統，普通以為，非線性、不穩定性、不確定性是呵斥復雜性的根源。復雜事物只能照它復雜的容顏來了解。2第九章人工生命定義1:研討具有自然生命系統行為的人造系統。定義2:人工生命是研討怎樣經過抽取生物景象中的根本動力規那么來了解生命，并且在物理媒體如計算機上重建這些景象，使它們成為新的實驗方式和受支配。定義3:在人工生命中的一切存在或將會存在的事物中，我們至少可以說這一領域從總體來說，代表了一種嘗試，就是加重了生物學中合成實際的分量。3第一次會議“人工生命——關于生命系統合成與模擬的跨學科研討會〞。本次會議于1987年9月在美國新墨西哥的羅斯阿拉莫斯舉行。本次會議的論文集共收錄了24篇論文，內容主要分布在：人工生命研討的實際、生命景象的仿真、細胞自動機〔簡稱CA〕、遺傳算法、進化仿真等5個方面，蘭頓發表了題為“人工生命〞的開辟性論文，他在文中提出了人工生命的概念，并討論了它作為一門新興的研討領域或學科存在的意義。蘭頓被公以為人工生命研討的創建者。這次會議標志著人工生命研討領域的誕生。4研討人工生命的緣由人工生命的研討可使我們更好地了解突發特征，個體在低級組織中的集合，經過我們的相互作用，常可產生特征。人工生命將會成為研討生物的一個特別有用的工具。對于開展新技術及加強我們控制自然的才干，人工生命系統是很有潛力的。人工生命的另一顯著運用是遺傳工程。5人工生命的探求20世紀初，邏輯在算術機械運算中的運用，導致過程的籠統方式化。40年代末，50年代初，馮.諾伊曼提出了機器自增長的能夠性實際。以計算機為工具，迎來了信息科學的開展。70年代以來，科拉德(Conrad)和他的同事研討人工仿生系統中的自順應、進化和群體動力學，提出了不斷完善的“人工世界〞模型。80年代，人工神經網絡又興起，出現了許多神經網絡模型和學習算法。與此同時，人工生命的研討也逐漸興起。1987年召開了第一屆國際人工生命會議。6人工生命的模型1)計算機病毒2)計算機的進程3)生物統計學和個體胎生學4)機器人5)自催化(autocatalytic)網絡6)細胞自動機7)人工核苷酸7人工生命的研討方法和戰略按照人工生命的組織機構，人工生命的內容大致可以分成兩類：構成生物體的內部系統，包括腦、神經系統、內分泌系統、免疫系統、遺傳系統、酶系統、代謝系統等。在生物體及其群體中表現的外部系統。生物群體中環境順應系統和遺傳進化系統等。8模型法。根據內部和外部系統所表現的生命行為，建造信息模型。任務原理法。生命行為所顯示的自律分散和非線性的行為，它的任務原理是混沌和分形，據此研討它的機理。人工生命研討的方法9采用以計算機等信息處置機器為中心的硬件生成生命行為。一種是采用已有的信息處置機器和執行安裝，實現具有人工生命行為的系統。另一種是用生物器件構造生命系統。這些都通稱為生物計算機，是一種向人工生命接近的方法。用計算機仿真，研討開發顯示生命體特征行為的模型軟件。簡單地說，神經網絡系統和遺傳算法等，都是采用信息數學模型，模擬人工生命的生成。基于任務原理，利用計算機仿真生成生命體。生命景象的根底是隨物理熵的增大而雜亂無章。生成這種景象的原理是混沌的分形、耗散構造、協同反響等，采用這些產生生命景象。經過計算機仿真，分析生命特有的行為生成，建立新的實際。利用上面3個戰略，得到生命行為共同的普通性質，經過概括，建立生命的根本實際。這種戰略構成自組織、超并行處置等實際。人工生命研討的戰略109.2遺傳算法及運用遺傳算法的提出及開展遺傳算法的根本原理遺傳算法的構成要素遺傳算法的實現步驟遺傳算法的運用111遺傳算法的提出及開展遺傳算法(Genetic

Algorithm，GA)是一種基于進化論優勝劣汰、適者生存的物種遺傳機制的隨機化搜索算法。它是生物學和計算機科學結合的產物。它最早由美國密執根大學J.Holland教授提出，其主要特點是群體搜索戰略和群體中個體之間的信息交換，搜索不依賴于梯度信息。在人工智能研討中，以為“遺傳算法、自順應系統、細胞自動機、混沌實際與人工智能一樣，都是對今后十年的計算技術有艱苦影響的關鍵技術〞12遺傳算法的開展20世紀60年代，美國密植安大學的Holland教授及其學生們遭到生物模擬技術的啟發，發明出了一種基于生物遺傳和進化機制的適宜于復雜系統計算優化的自順應概率優化技術-----遺傳算法。下面是在遺傳算法的開展進程中一些關鍵人物所做出的一些主要奉獻。13J.H.Holland20世紀60年代，Holland認識到了生物的遺傳和自然進化景象與人工自順應系統的類似關系，運用生物遺傳和進化的思想來研討自然和人工自順應系統的生成以及它們與環境的關系，提出在研討和設計人工自順應系統時，可以自創生物遺傳的機制，以群體的方法進展自順應搜索，并且充分認識到了交叉、變異等運算戰略在自順應系統中的重要性。遺傳算法的開展14J.D.Bagley1967年，Holland的學生Bagley在其博士論文中初次提出了“遺傳算法〞一詞，并發表了遺傳算法運用方面的第一篇論文。他開展了復制、交叉、變異、顯性、倒位等遺傳算子，在個體編碼上運用了雙倍體的編碼方法。這些都與目前遺傳算法中所運用的算子和方法類似。他還敏銳地認識到了在遺傳算法執行的不同階段可以運用不同的選擇率，這將有利于防止遺傳算法的早熟景象，從而創建了自順應遺傳算法的概念。遺傳算法的開展1520世紀70年代，Holland提出了遺傳算法的根本定理---方式定理(SchemaTheorem),奠定了遺傳算法的實際根底。1975年，Holland出版了第一本系統論述遺傳算法和人工自順應系統的專著<自然系統和人工系統的自順應性〔AdaptationinNaturalandArtificialSystems〕>。遺傳算法的開展1620世紀80年代，Holland實現了第一個基于遺傳算法的機器學習系統----分類器系統，開創了基于遺傳算法學習的新概念，為分類器系統構造出了一個完好的框架。遺傳算法的開展17D.J.Goldberg1989年，Goldberg出版了專著<搜索、優化和機器學習中的遺傳算法>。該書系統總結了遺傳算法的主要研討成果，全面而完好地論述了遺傳算法的根本原理及其運用。遺傳算法的開展18J.R.Koza1992年，Koza將遺傳算法運用于計算機程序的優化設計及自動生成，，提出了遺傳編程的概念。Koza勝利地將提出的遺傳編程方法運用于人工智能、機器學習、符號處置等方面。遺傳算法的開展192遺傳算法的根本原理遺傳算法的根本思想是基于Darwin進化論和Mendel的遺傳學說。Darwin進化論最重要的是適者生存原理。它以為每一物種在開展中越來越順應環境。物種每個個體的根本特征由后代所承繼，但后代又會產生一些異于父代的新變化。在環境變化時，只需那些能順應環境的個體特征方能保管下來。Mendel遺傳學說最重要的是基因遺傳原理。以為遺傳以密碼方式存在細胞中，并以基因方式包含在染色體內。每個基因有特殊的位置并控制某種特殊性質；所以，每個基因產生的個體對環境具有某種順應性。基因突變和基因雜交可產生更順應于環境的后代。經過存優去劣的自然淘汰，順應性高的基因構造得以保管下來。20遺傳算法與傳統優化算法的主要不同遺傳算法不是直接作用在參變量集上,而是利用參變量集的某種編碼;遺傳算法不是從單個點,而是在群體中從一個點開場搜索;遺傳算法利用順應值信息,無需導數或其它輔助信息;遺傳算法利用概率轉移規那么,而非確定性規那么。21遺傳算法的缺陷編碼不規范及編碼存在表示的不準確性。單一的遺傳算法編碼不能全面地將優化問題的約束表示出來。易于墮入部分最優點，導致早熟。223遺傳算法的構成要素3.1染色體編碼方法。根本遺傳算法運用固定長度的二進制符號串表示群體的個體，其等位基因是由二值符號{0，1}所組成的。初始群體中各個個體的基因值可用均勻分布的隨機數生成，如：x=1001110010就可以表示一個個體，該個體的染色體長度是n=10。3.2個體順應度評價根本遺傳算法按與個體適用度成正比的概率來決議當前群體中每個個體遺傳到下一代群體中的時機多少。為正確計算這個概率，這里要求一切個體的順應度必需為正數或零。根據不同種類的問題，必需預先確定好由目的函數值到個體順應度的轉換規那么。233遺傳算法的構成要素3.3遺傳算子?選擇算子(selection)：又稱為復制算子。按照某種戰略從父代中挑選個體進入下一代，如運用比例選擇、輪盤式選擇。?交叉算子(crossover)：又稱為雜交算子。將從群體中選擇的兩個個體，按照某種戰略使兩個個體相互交換部分染色體，從而構成兩個新的個體。如運用單點一致交叉。?變異算子(mutation)：按照一定的概率〔普通較小〕，改動染色體中某些基因的值。243遺傳算法的構成要素3.4、運轉參數N：群體大小，即群體中包含的個體的數量。T：遺傳算法終止的進化代數。Pc：交叉概率，普通取為0.4～0.99。Pm：變異概率，普通取為0.0001～0.1。25遺傳算法與傳統優化算法的主要不同遺傳算法不是直接作用在參變量集上,而是利用參變量集的某種編碼;遺傳算法不是從單個點,而是在群體中從一個點開場搜索;遺傳算法利用順應值信息,無需導數或其它輔助信息;遺傳算法利用概率轉移規那么,而非確定性規那么。264遺傳算法的運用步驟遺傳算法提供了一種求解復雜系統優化問題的通用框架，它不依賴于問題的領域和種類。對一個需求進展優化和計算的實踐運用問題，普通可按下述步驟來求解問題的遺傳算法。遺傳算法的預備任務：1〕確定表示方案;2〕確定順應值的度量;3〕確定控制該算法的參數和變量;4〕確定怎樣指定結果及程序運轉終了的規范。274遺傳算法的運用步驟遺傳算法提供了一種求解復雜系統優化問題的通用框架。對于詳細問題，可按下述步驟來構造：①確定決策變量及其各種約束條件，即確定出個體的表現型X和問題的解空間；②建立優化模型，即描畫出目的函數的類型及其數學描畫方式或量化方法；284遺傳算法的運用步驟③確定表示可行解的染色體編碼方法，即確定出個體的基因型X及遺傳算法的搜索空間；④確定解碼方法，即確定出由個體基因型X到個體表現型X的對應關系或轉換方法；⑤確定個體順應度的量化評價方法，即確定出由目的函數值到個體順應度的轉換規那么；294遺傳算法的運用步驟⑥設計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的詳細操作方法；⑦確定遺傳算法的有關運轉參數，即確定出遺傳算法的等參數。30根本遺傳算法流程圖引入新個體變異隨機創建初始群體自然選擇復制、雜交顯示結果終了是否能否滿足選中規范？計算群體中每個個體的順應值31遺傳算法舉例問題：求〔1〕編碼：此時取均長為5，每個染色體〔2〕初始群體生成：群體大小視情況而定，此處設置為4，隨機產生四個個體：編碼：01101，11000，01000，10011解碼：1324819順應度：16957664361〔3〕順應度評價：32〔4〕選擇：選擇概率個體：01101，11000，01000，10011順應度：16957664361選擇概率：0.140.490.060.31選擇結果：01101，11000，11000，10011〔5〕交叉操作：發生交叉的概率較大哪兩個個體配對交叉是隨機的交叉點位置的選取是隨機的〔單點交叉〕011010110011000110111100011001100111000033〔6〕變異：發生變異的概率很小〔7〕新群體的產生：保管上一代最優個體，普通為10%左右，至少1個用新個體取代舊個體，隨機取代或擇優取代。11000，11011，11001，10011〔8〕反復上述操作：闡明：GA的終止條件普通人為設置；GA只能求次優解或稱心解。分析：按第二代新群體進展遺傳操作，假設無變異，永遠也找不到最優解——擇優取代有問題。假設隨機的將個體01101選入新群體中，有能夠找到最優解。34第一代種群S1中各染色體的情況35選擇-復制設從區間［0,1］中產生4個隨機數如下:r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503按賭輪選擇法，染色體s1,s2,s3,s4的被選中次數依次為：1,2,0,1。于是，經復制得群體：s1’=11000〔24〕,s2’=01101〔13〕,s3’=11000〔24〕,s4’=10011〔19〕可以看出，在第一輪選擇中順應度最高的染色體s2被選中兩次，因此被復制兩次；而順應度最低的染色體s3一次也沒有選中而遭淘汰。36交叉設交叉率pc=100%，即S1中的全體染色體都參與交叉運算。設s1’與s2’配對，s2’與s4’配對。分別交換后兩位基因，得新染色體：s1’’=11001〔25〕,s2’’=01100〔12〕,s3’’=11011〔27〕,s4’’=10000〔16〕變異設變異率pm=0.001。這樣，群體S1中共有540.001=0.02位基因可以變異。0.02位顯然缺乏1位，所以本輪遺傳操作不做變異。如今，我們得到了第二代種群S2：s1=11001〔25〕,s2=01100〔12〕,s3=11011〔27〕,s4=10000〔16〕37第二代種群S2中各染色體的情況38假設這一輪選擇-復制操作中，種群S2中的4個染色體都被選中〔由于選擇概率畢竟只是一種幾率，所以4個染色體恰好都被選中的情況是存在的〕，我們得到群體：s1’=11001〔25〕,s2’=01100〔12〕,s3’=11011〔27〕,s4’=10000〔16〕然后，做交叉運算，讓s1’與s2’，s3’與s4’分別交換后三位基因，得s1’’=11100〔28〕,s2’’=01001〔9〕,s3’’=11000〔24〕,s4’’=10011〔19〕這一輪依然不會發生變異。于是，得第三代種群S3：s1=11100〔28〕,s2=01001〔9〕,s3=11000〔24〕,s4=10011〔19〕39第三代種群S4中各染色體的情況40設這一輪的選擇-復制結果為：s1’=11100〔28〕,s2’=11100〔28〕,s3’=11000〔24〕,s4’=10011〔19〕然后，做交叉運算，讓s1’與s4’，s2’與s3’分別交換后兩位基因，得s1’’=11111〔31〕,s2’’=11100〔28〕,s3’’=11000〔24〕,s4’’=10000〔16〕這一輪依然不會發生變異。于是，得第四代種群S4：s1=11111〔31〕,s2=11100〔28〕,s3=11000〔24〕,s4=10000〔16〕41顯然，在這一代種群中曾經出現了順應度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111〞作為最終結果輸出。然后，將染色體“11111〞解碼為表現型，即得所求的最優解：31。將31代入函數y=x2中，即得原問題的解，即函數y=x2的最大值為961。425遺傳算法的運用應用領域具體說明控制煤氣管道控制，防避導彈控制，機器人控制規劃生產規劃，并行任務分配設計VLSI布局，背包問題，圖劃分問題圖像處理模式識別，特征抽取信號處理濾波器設計機器人路徑規劃人工生命生命的遺傳進化人工神經網絡權值訓練和網絡結構生成43遺傳算法的運用遺傳算法提供了一種求解復雜系統優化問題的通用框架，它不依賴于問題的詳細領域，對問題的種類有很強的魯棒性，所以廣泛運用于很多學科。下面列舉一些遺傳算法的主要運用領域。44函數優化是遺傳算法的經典運用領域，也是對遺傳算法進展性能測試評價的常用算例。對于一些非線性、多模型、多目的的函數優化問題，用其他優化方法較難求解，而遺傳算法卻可以方便地得到較好的結果。函數優化45組合優化遺傳算法是尋求組合優化問題稱心解的最正確工具之一，實際證明，遺傳算法對于組合優化問題中的NP完全問題非常有效。46消費調度問題消費調度問題在很多情況下所建立起來的數學模型難以準確求解，即使經過一些簡化之后可以進展求解也會因簡化得太多而使求解結果與實踐相差太遠。如今遺傳算法曾經成為處理復雜調度問題的有效工具。47自動控制遺傳算法曾經在自動控制領域中得到了很好的運用，例如基于遺傳算法的模糊控制器的優化設計、基于遺傳算法的參數辨識、基于遺傳算法的模糊控制規那么的學習、利用遺傳算法進展人工神經網絡的構造優化設計和權值學習等。48機器人學機器人是一類復雜的難以準確建模的人工系統，而遺傳算法的來源就來自于對人工自順應系統的研討，所以機器人學自然成為遺傳算法的一個重要運用領域。49圖象處置圖像處置是計算機視覺中的一個重要研討領域。在圖像處置過程中，如掃描、特征提取、圖像分割等不可防止地存在一些誤差，這些誤差會影響圖像處置的效果。如何使這些誤差最小是使計算機視覺到達適用化的重要要求，遺傳算法在這些圖像處置中的優化計算方面得到了很好的運用。50人工生命人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統特有行為的人造系統。自組織才干和自學習才干是人工生命的兩大重要特征。人工生命與遺傳算法有著親密的關系，基于遺傳算法的進化模型是研討人工生命景象的重要實際根底。519.3粒子群優化算法粒子群優化(ParticleSwarmOptimization,PSO)，又稱微粒群算法，是由J.Kennedy和RCEberhart等于1995年開發的一種演化機制。粒子(particle)〞是一個折衷的選擇,由于既需求將群體中的成員描畫為沒有質量、沒有體積的,同時也需求描畫它的速度和加速形狀。PSO模擬鳥群的捕食行為。想象這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只需一塊食物。一切的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優戰略是什么呢。最簡單有效的就是搜索目前離食物最近的鳥的周圍區域。PSO從這種模型中得到啟示并用于處理優化問題。PSO中，每個優化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子〞。一切的例子都有一個由被優化的函數決議的順應值(fitnessvalue)，每個粒子還有一個速度決議他們飛翔的方向和間隔。然后粒子們就跟隨當前的最優粒子在解空間中搜索。52特點分布式搜索具記憶性組件較少，容易實現適宜在延續性的范圍內搜索53演算法引見每個尋優的問題解都被想象成一只鳥，我們也稱為“Particle〞。一切的Particle都有一個fitnessfunction以判別目前的位置之好壞，每一個Particle必需賦予記憶性，能記得所搜索到最正確位置。每一個Particle還有一個速度以決議飛行的間隔與方向。54算法流程1.Initial將群族