【文章內(nèi)容簡介】 ym Y2 Y1 x1 … … x2 xn 輸入層 輸出層 在 Hopfidld網(wǎng)絡(luò)中，雖然神經(jīng)元自身無連接，但由于每個神經(jīng)元都與其他神經(jīng)元相連，即每個神經(jīng)元的輸出都將通過突觸連接權(quán)值傳遞給別的神經(jīng)元，同時每個神經(jīng)元又都接受其他神經(jīng)元傳來的信息，這樣對每個神經(jīng)元來說，其輸出經(jīng)過其他神經(jīng)元后又有可能反饋給自己，因此 Hopfidld網(wǎng)絡(luò)是一種反饋神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò)的典型模型 2. Hopfield網(wǎng)絡(luò)模型 (2/2) 37 進化計算（ Evolutionary Computation,EC）是在達爾文（ Darwin）的進化論和孟德爾（ Mendel）的遺傳變異理論的基礎(chǔ)上產(chǎn)生的一種在基因和種群層次上模擬自然界生物進化過程與機制的問題求解技術(shù)。它主要包括 遺傳算法（ Geic Algorithm， GA） 進化策略（ Evolutionary Strategy,ES） 進化規(guī)劃（ Evolutionary Programming,EP） 遺傳規(guī)劃（ Geic Programming,GP）四大分支。 其中，第一個分支是進化計算中最初形成的一種具有普遍影響的模擬進化優(yōu)化算法。因此我們主要討論遺傳算法。 進化計算 38 進化計算是一種模擬自然界生物進化過程與機制進行問題求解的自組織、自適應(yīng)的隨機搜索技術(shù)。它以達爾文進化論的“物竟天擇、適者生存”作為算法的進化規(guī)則，并結(jié)合孟德爾的遺傳變異理論，將生物進化過程中的 繁殖（ Reproduction） 變異（ Mutation） 競爭（ Competition） 選擇（ Selection） 引入到了算法中。 進化計算概述 1. 進化計算及其生物學(xué)基礎(chǔ) (1/3) (1) 什么是進化計算 39 (2) 進化計算的生物學(xué)基礎(chǔ) 自然界生物進化過程是進化計算的生物學(xué)基礎(chǔ)，它主要包括遺傳(Heredity)、變異 (Mutation)和進化 (Evolution)理論。 ① 遺傳理論 遺傳是指父代（或親代）利用遺傳基因?qū)⒆陨淼幕蛐畔鬟f給下一代（或子代），使子代能夠繼承其父代的特征或性狀的這種生命現(xiàn)象。正是由于遺傳的作用，自然界才能有穩(wěn)定的物種。 在自然界，構(gòu)成生物基本結(jié)構(gòu)與功能的單位是細胞（ Cell）。 細胞中含有一種包含著所有遺傳信息的復(fù)雜而又微小的絲狀化合物，人們稱其為染色體（ Chromosome）。 在染色體中，遺傳信息由基因（ Gene）所組成，基因決定著生物的性狀，是遺傳的基本單位。 染色體的形狀是一種雙螺旋結(jié)構(gòu)，構(gòu)成染色體的主要物質(zhì)叫做脫氧核糖核酸 (DNA)，每個基因都在 DNA長鏈中占有一定的位置。 一個細胞中的所有染色體所攜帶的遺傳信息的全體稱為一個基因組(Genome)。 細胞在分裂過程中，其遺傳物質(zhì) DNA通過復(fù)制轉(zhuǎn)移到新生細胞中，從而實現(xiàn)了生物的遺傳功能。 進化計算概述 1. 進化計算及其生物學(xué)基礎(chǔ) (2/3) 40 ② 變異理論 變異是指子代和父代之間，以及子代的各個不同個體之間產(chǎn)生差異的現(xiàn)象。變異是生物進化過程中發(fā)生的一種隨機現(xiàn)象，是一種不可逆過程，在生物多樣性方面具有不可替代的作用。引起變異的主要原因有以下兩種： 雜交，是指有性生殖生物在繁殖下一代時兩個同源染色體之間的交配重組，即兩個染色體在某一相同處的 DNA被切斷后再進行交配重組，形成兩個新的染色體。 復(fù)制差錯，是指在細胞復(fù)制過程中因 DNA上某些基因結(jié)構(gòu)的隨機改變而產(chǎn)生出新的染色體。 ③ 進化論 進化是指在生物延續(xù)生存過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良的這種生命現(xiàn)象。遺傳和變異是生物進化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進化的基本規(guī)律。 達爾文的自然選擇學(xué)說認為：在生物進化中，一種基因有可能發(fā)生變異而產(chǎn)生出另一種新的生物基因。這種新基因?qū)⒁罁?jù)其與生存環(huán)境的適應(yīng)性而決定其增殖能力。一般情況下，適應(yīng)性強的基因會不斷增多，而適應(yīng)性差的基因則會逐漸減少。通過這種自然選擇，物種將逐漸向適應(yīng)于生存環(huán)境的方向進化，甚至?xí)葑兂蔀榱硪粋€新的物種，而那些不適應(yīng)于環(huán)境的物種將會逐漸被淘汰。 進化計算概述 1. 進化計算及其生物學(xué)基礎(chǔ) (3/3) 41 進化計算自 20世紀 50年代以來，其發(fā)展過程大致可分為三個階段。 ① 萌芽階段 這一階段是從 20世紀 50年代后期到 70年代中期。 20世紀 50年代后期，一些生物學(xué)家在研究如何用計算機模擬生物遺傳系統(tǒng)中，產(chǎn)生了 遺傳算法 的基本思想，并于 1962年由美國密執(zhí)安（ Michigan）大學(xué)霍蘭德（ Holland）提出。 1965年德國數(shù)學(xué)家雷切伯格（ Rechenberg）等人提出了一種只有單個個體參與進化，并且僅有變異這一種進化操作的 進化策略 。同年，美國學(xué)者弗格爾（ Fogel）提出了一種具有多個個體和僅有變異一種進化操作的 進化規(guī)劃 。 1969年美國密執(zhí)安（ Michigan）大學(xué)的霍蘭德（ Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調(diào)的遺傳算法。至此，進化計算的 三大分支基本形成 。 ② 成長階段 這一階段是從 20世紀 70年代中期到 80年代后期。 1975年，霍蘭德出版專著《自然和人工系統(tǒng)的適應(yīng)性（ Adaptation in Natural and Artificial System）》，全面介紹了遺傳算法。同年，德國學(xué)者施韋費爾（ Schwefel）在其博士論文中提出了一種由多個個體組成的群體參與進化的，并且包括了變異和重組這兩種進化操作的進化策略。 1989年，霍蘭德的學(xué)生戈爾德伯格（ Goldberg）博士出版專著《遺傳算法 搜索、優(yōu)化及機器學(xué)習(xí)（ Geic Algorithmin Search Optimization and Machine Learning）》，使遺傳算法得到了普及與推廣。 進化計算概述 2. 進化計算的產(chǎn)生與發(fā)展 (1/2) 42 ③ 發(fā)展階段 這一階段是從 20世紀 90年代至今。 1989年，美國斯坦福（ Stanford）大學(xué)的科扎（ Koza）提出了遺傳規(guī)劃的新概念，并于 1992年出版了專著《遺傳規(guī)劃 應(yīng)用自然選擇法則的計算機程序設(shè)計（ Geic Programming :on the Programming of Computer by Means of Natural Selection）》該書全面介紹了遺傳規(guī)劃的基本原理及應(yīng)用實例，標志著遺傳規(guī)劃作為計算智能的一個分支已基本形成。 進入 20世紀 90年代以來，進化計算得到了眾多研究機構(gòu)和學(xué)者的高度重視，新的研究成果不斷出現(xiàn)、應(yīng)用領(lǐng)域不斷擴大。目前，進化計算已成為人工智能領(lǐng)域的又一個新的研究熱點。 進化計算概述 2. 進化計算的產(chǎn)生與發(fā)展 (2/2) 43 進化計算盡管有多個重要分支，并且不同分支的編碼方案、選擇策略和進化操作也有可能不同，但它們卻有著共同的進化框架。若假設(shè) P為種群(Population，或稱為群體 )， t為進化代數(shù)， P(t)為第 t代種群 , 則進化計算的基本結(jié)構(gòu)可粗略描述如下： { 確定編碼形式并生成搜索空間； 初始化各個進化參數(shù)，并設(shè)置進化代數(shù) t=0； 初始化種群 P(0)。 對初始種群進行評價（即適應(yīng)度計算）； while（不滿足終止條件） do { t=t+1。 利用選擇操作從 P(t1)代中選出 P(t)代群體； 對 P(t)代種群執(zhí)行進化操作； 對執(zhí)行完進化操作后的種群進行評價（即適應(yīng)度計算）； } } 可以看出，上述基本結(jié)構(gòu)包含了生物進化中所必需的選擇操作、進化操作和適應(yīng)度評價等過程。 進化計算概述 3. 進化計算的基本結(jié)構(gòu) 44 遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進化，直到滿足目標為止。遺傳算法所涉及到的基本概念主要有以下幾個： 種群 （ Population）：種群是指用遺傳算法求解問題時，初始給定的多個解的集合。遺傳算法的求解過程是從這個子集開始的。 個體 （ Individual）：個體是指種群中的單個元素，它通常由一個用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來表示。例如，可以用 0、 1組成的長度為 l的串來表示個體。 染色體 （ Chromos）：染色體是指對個體進行編碼后所得到的編碼串。染色體中的每 1位稱為基因，染色體上由若干個基因構(gòu)成的一個有效信息段稱為基因組。 適應(yīng)度 （ Fitness）函數(shù)：適應(yīng)度函數(shù)是一種用來對種群中各個個體的環(huán)境適應(yīng)性進行度量的函數(shù)。其函數(shù)值是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據(jù) 遺傳操作 （ Geic Operator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。 標準的遺傳操作包括以下 3種基本形式： 選擇 （ Selection） 交叉 （ Crosssover） 變異 （ Mutation） 遺傳算法 1. 遺傳算法的基本概念 45 遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳操作設(shè)計等幾大部分所組成，其算法主要內(nèi)容和基本步驟可描述如下： (1) 選擇編碼策略，將問題搜索空間中每個可能的點用相應(yīng)的編碼策略表示出來，即形成染色體； (2) 定義遺傳策略，包括種群規(guī)模 N，交叉、變異方法，以及選擇概率 Pr、交叉概率 Pc、變異概率 Pm等遺傳參數(shù)； (3) 令 t=0，隨機選擇 N個染色體初始化種群 P(0)； (4) 定義適應(yīng)度函數(shù) f（ f0）； (5) 計算 P(t)中每個染色體的適應(yīng)值； (6) t=t+1； (7) 運用選擇算子，從 P(t1)中得到 P(t)； (8) 對 P(t)中的每個染色體，按概率 Pc參與交叉； (9) 對染色體中的基因，以概率 Pm參與變異運算； (10) 判斷群體性能是否滿足預(yù)先設(shè)定的終止標準，若不滿足則返回 (5)。 遺傳算法 2. 遺傳算法的基本結(jié)構(gòu) (1/2) 46 計算種群中各個個體的適應(yīng)度 ， 并進行評價 滿足終止條件嗎 ？ 終止 選擇 交叉 變異 Y 圖 518 基本遺傳算法的算法流程圖 編碼和生成初始種群 N 選擇 其算法流程如圖 518所示。 遺傳算法 2. 遺傳算法的基本結(jié)構(gòu) (2/2) 47 常用的遺傳編碼算法有霍蘭德二進制碼、格雷碼（ Gray Code）、實數(shù)編碼和字符編碼等。 (1)二進制編碼（ Binary encoding） 二進制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。在二進制編碼中，首先要確定二進制字符串的長度 l，該長度與變量的定義域和所求問題的計算精度有關(guān)。 例 假設(shè)變量 x的定義域為 [5， 10]，要求的計算精度為 105，則需要將 [5，10]至少分為 600000個等長小區(qū)間，每個小區(qū)間用一個二進制串表示。于是，串長至少等于 20，原因是： 524288=219600000220=1048576 這樣，對應(yīng)于區(qū)間 [5， 10]內(nèi)滿足精度要求的每個值 x，都可用一個 20位編碼的二進制串 b19,b18,…,b0 來表示。 二進制編碼存在的主要缺點 是漢明（ Hamming）懸崖。 例如， 7和 8的二進制數(shù)分別為 0111和 1000，當算法從 7改進到 8時，就必須改變所有的位。 遺傳算法 3. 遺傳編碼 (1/3) 48 遺傳算法 3. 遺傳編碼 (2/3) (2) 格雷編碼（ Gray encoding） 格雷編碼是對二進制編碼進行變換后所得到的一種編碼方法。這種編碼方法要求兩個連續(xù)整數(shù)的編碼之間只能有一個碼位不同，其余碼位都是完全相同的。它有效地解決了漢明懸崖問題，其基本原理如下： 設(shè)有二進制串 b1,b2,…,bn ，對應(yīng)的格雷串為 a1,a2,…,an ，則從二進制編碼到格雷編碼的變換為： 其中， ⊕ 表示模 2加法。而從一個格雷串到二進制串的變換為： 例 十進制數(shù) 7和 8的二進制編碼分別為 0111和 1000，而其格雷編碼分別為0100和 1100。 11,1 ( 5 7 )1i iibiab b i????????? )85()2(mod1?? ??ijii ab49 (3) 實數(shù)編碼（ Real encoding）