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