【正文】 生物進(jìn)化中的概念 遺傳算法中的作用 環(huán)境 適應(yīng)性 適者生存 個體 染色體 基因 種群 (群體 ) 交叉 變異 生物進(jìn)化與遺傳算法之間的對應(yīng)關(guān)系 生物進(jìn)化中的概念 遺傳算法中的作用 環(huán)境 適應(yīng)函數(shù) 適應(yīng)性 函數(shù)適應(yīng)值 適者生存 適應(yīng)函數(shù)值最大的解被保留的 概率最大 個體 問題的一個解 染色體 解的編碼 基因 編碼的元素 種群 (群體 ) 根據(jù)適應(yīng)函數(shù)選擇的一組解 交叉 以一定的方式由雙親產(chǎn)生后代 的過程 變異 編碼的某些分量發(fā)生變化的過 程 遺傳算法的求解步驟 遺傳算法的主要特點 遺傳算法 (1) 遺傳算法 利用目標(biāo)函數(shù)的適應(yīng)度 這一信息而非利用導(dǎo)數(shù)或其它輔助信息來指導(dǎo)搜索； (2) 遺傳算法 利用選擇 、 交叉 、 變異等算子 而不是利用確定性規(guī)則進(jìn)行隨機操作 。 ?GA算法框圖 一般遺傳算法的主要步驟如下： (1) 隨機產(chǎn)生一個由確定長度的特征字符串組成的 初始群體 。 輪盤式選擇 ?首先計算每個個體 i 被選中的概率 ?然后根據(jù)概率的大小將圓盤分為 n個扇形。 哪兩個個體配對交叉是隨機的。 分析： 按第二代新群體進(jìn)行遺傳操作， 若無變異，永遠(yuǎn)也找不到最優(yōu)解 ——擇優(yōu)取代有問題。 ?它是由雷切伯格（ Rechenberg）、施韋費爾（ Schwefel）和彼得 進(jìn)化策略 最簡單形式的進(jìn)化策略可描述如下： 進(jìn)化策略和遺傳算法的區(qū)別 ?進(jìn)化策略和遺傳算法有著 很強的相似性 ，它們都是一類模仿自然進(jìn)化原理的算法。 第五章 計算智能 (2) 遺傳算法 進(jìn)化策略 進(jìn)化編程 人工生命 進(jìn)化編程 ?進(jìn)化編程 (Evolutionary Programming， EP)，又稱為 進(jìn)化規(guī)劃 （ Evolutionary Planning），是由福格爾（ Fogel）在 1962年提出的一種模仿人類智能的方法。 進(jìn)化編程的步驟 進(jìn)化編程分為 三個步驟 ： ? 產(chǎn)生初始群體 。 這一結(jié)果可能是問題的解或近似解 。自然生命千千萬萬，千姿百態(tài)，千差萬別，巧奪天工，奇妙無窮。在 1987年第一次人工生命研討會上，美國圣塔菲研究所（ Santa Fe Institute， SFI）非線性研究組的 蘭頓（ Langton）正式提出人工生命的概念，建立起人工生命新學(xué)科。 自然生命的共同特征和現(xiàn)象 ?自繁殖、自進(jìn)化、自尋優(yōu) ?自成長、自學(xué)習(xí)、自組織 ?自穩(wěn)定、自適應(yīng)、自協(xié)調(diào) ?物質(zhì)構(gòu)造 ?能量轉(zhuǎn)換 ?信息處理 人工生命 研究人工生命的意義 人工生命 是自然生命的模擬、延伸與擴展，其研究開發(fā)有重大的科學(xué)意義和廣泛的應(yīng)用價值。 人工生命 ?由于倫理學(xué)、社會學(xué)、人類學(xué)等方面的問題， 通過生物科學(xué)途徑生成的人工生命，如克隆人引起了不少爭論。世界上最早發(fā)現(xiàn)的計算機病毒是 “巴基斯坦 ”病毒，時間是 1986年 1月。由于這種感染特性，病毒可以在信息流的過渡途徑中傳播，從而破壞信息的完整性。 破壞性 。自 20世紀(jì)80年代以來，隨著人類基因組計劃、遺傳算法理論、人工生命科學(xué)和 DNA計算機理論的相繼提出和發(fā)展，使得人們對生命是什么這個永恒的問題有了全新的認(rèn)識： 生命就是由一系列復(fù)雜的計算組成的，是按算法規(guī)則進(jìn)化的。這為我們把計算機病毒看作是一種可能的生命提供了充足的證據(jù)?？寺∝i、克隆猴、克隆牛 …… 紛紛問世。 克隆羊多莉的誕生 ，引發(fā)了世界范圍內(nèi)關(guān)于動物克隆技術(shù)的熱烈爭論。在此， 自然系統(tǒng)相當(dāng)于計算機的硬件、自然規(guī)律相當(dāng)于計算機的軟件，而自然過程就是計算機的計算過程。 計算機病毒確實可以在計算機控制的空間和計算機網(wǎng)絡(luò)上生存下去。 計算機病毒 與 生物病毒 是兩個不同范疇的概念，前者是人為制造的，后者是宇宙進(jìn)化的產(chǎn)物；前者采用的是機器語言，少數(shù)采用高級語言，后者采用的是核酸編碼，少數(shù)采用氨基酸編碼；前者結(jié)構(gòu)上采用指令程序的物理存儲，后者則以化學(xué)固化存儲方式為主。 計算機病毒可能并非人們通常所認(rèn)為的那樣只有消極作用、破壞性作用，如果 我們能夠哲學(xué)地思考與看待計算機病毒 ，那么我們就會發(fā)現(xiàn)它所潛在的一些十分有益的作用、建設(shè)性的作用。 人工生命 ?計算機病毒 ?計算機進(jìn)程 ?細(xì)胞自動機 ?人工核苷酸 在計算機病毒出現(xiàn)以前， 病毒 一直是一個純生物學(xué)的概念。 人工生命 （ 2） 工作原理法 生命行為所顯示的自律分?jǐn)?shù)和非線性行為 ， 其工作原理是混沌和分形 ， 以此為基礎(chǔ)研究人工生命的機理 。然而，要對人工生命做出嚴(yán)格的定義，卻需要對問題進(jìn)行深入研究。 1943年麥卡絡(luò)奇和皮茨提出了 M－ P神經(jīng)學(xué)網(wǎng)絡(luò)模型 。 交叉 在遺傳算法中起著重要作用，而在進(jìn)化編程中卻被完全省去，在進(jìn)化策略中與自適應(yīng)結(jié)合使用，起了很重要的作用。 基于適應(yīng)值根據(jù)概率從群體中選出一個計算機程序個體 ， 然后用合適的操作作用于該計算機程序個體 。 ?它的提出是受 自然生物進(jìn)化機制 的啟發(fā)。 進(jìn)化策略和遺傳算法的區(qū)別 除了研究和應(yīng)用領(lǐng)域外， 進(jìn)化策略和遺傳算法還有以下區(qū)別 ： (1) 進(jìn)化策略和遺傳算法 表示個體的方式 不同， 進(jìn)化策略在浮點矢量上運行，而遺傳算法一般運行在二進(jìn)制矢量上。（雙親向量的初始群體） ? 父矢量 xi, i=1,…, p產(chǎn)生 子代矢量 xi。 收斂性定理 如果在代的進(jìn)化過程中， 遺傳算法 每次保留到目前為止的最好解，并且算法以交叉和變異為其隨機化操作，則對于一個全局最優(yōu)化問題，當(dāng)進(jìn)化代數(shù)趨于無窮時，遺傳算法找到最優(yōu)解的概率為 1。假設(shè)本次沒有發(fā)生變異，則變異前的種群即為進(jìn)化后所得到的第 1代種群。 交叉操作 交叉（ Crossover）操作 是指按照某種方式對選擇的父代個體的染色體的部分基因進(jìn)行交配重組，從而形成新的個體。如 00000表示 x＝ 0，10101表示 x＝ 21， 11111表示 x＝ 31等 問題 ：求 （ 1） 編碼 ： 此時取均長為 5，每個染色體 （ 2） 初始群體生成 ：群體大小視情況而定，此處設(shè)臵為 4，隨機產(chǎn)生四個個體： 編碼： 01101， 11000， 01000， 10011 解碼： 13 24 8 19 適應(yīng)度： 169 576 64 361 （ 3） 適應(yīng)度評價 ： ]31,0[,)( 2 ?? xxxfMa x 11111~00000?x 5}1,0{2)( xxfitness ?（ 4） 選擇 ：選擇概率 個體： 01101， 11000， 01000， 10011 適應(yīng)度： 169 576 64 361 選擇概率： 選擇結(jié)果： 01101， 11000， 11000， 10011 ffP ii ?? /1170?? f（ 5） 交叉操作 ：發(fā)生交叉的概率較大， 變異概率很小。 (4) 按概率 Pc進(jìn)行交叉操作 。 ?包括以下 3種基本形式 ： ? 選擇（ Selection） ? 交叉（ Crosssover） ? 變異（ Mutation） 遺傳算法的基本機理 遺傳算法 遺傳算法的基本概念 遺傳操作 ?選擇操作 也叫 復(fù)制 （ reproduction） 操作 ，根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。 ? Huffman編碼方法是一種效率高、方法簡單的編