【正文】 1 y=x1 XOR x2 x1 X2 x12 1 1 1 1 1 1 輸入層 隱層 輸出層 權(quán)值 權(quán)值 圖 “ 異或 ” 問題的多層感知器 閾值 閾值 閾值 (0,1) (0,0) (1,0) 圖 (1,1) 在圖 ，隱層神經(jīng)元 x11所確定的直線方程為 它可以識別一個半平面。所謂正向傳播，是指輸入模式經(jīng)隱層到輸出層，最后形成輸出模式；所謂誤差反向傳播，是指從輸出層開始逐層將誤差傳到輸入層，并修改各層聯(lián)接權(quán)值，使誤差信號為最小的過程 。它主要包括 遺傳算法（ Geic Algorithm， GA） 進化策略（ Evolutionary Strategy,ES） 進化規(guī)劃（ Evolutionary Programming,EP） 遺傳規(guī)劃（ Geic Programming,GP）四大分支。 在自然界，構(gòu)成生物基本結(jié)構(gòu)與功能的單位是 細胞 （ Cell）。 引起變異的主要原因： 雜交， 是指有性生殖生物在繁殖下一代時兩個同源染色體之間的交配重組，即兩個染色體在某一相同處的 DNA被切斷后再進行交配重組，形成兩個新的染色體。 進化計算概述 1. 進化計算及其生物學(xué)基礎(chǔ) (3/3) 41 進化計算自 20世紀(jì) 50年代以來，其發(fā)展過程大致可分為三個階段。 1975年，霍蘭德出版專著《自然和人工系統(tǒng)的適應(yīng)性（ Adaptation in Natural and Artificial System）》，全面介紹了遺傳算法。若假設(shè) P為種群(Population，或稱為群體 )， t為進化代數(shù)， P(t)為第 t代種群 , 則進化計算的基本結(jié)構(gòu)可粗略描述如下： { 確定編碼形式并生成搜索空間； 初始化各個進化參數(shù)，并設(shè)置進化代數(shù) t=0； 初始化種群 P(0)。 染色體 （ Chromos）：染色體是指對個體進行編碼后所得到的編碼串。在二進制編碼中，首先要確定二進制字符串的長度 l，該長度與變量的定義域和所求問題的計算精度有關(guān)。而從一個格雷串到二進制串的變換為： () 例 十進制數(shù) 7和 8的二進制編碼分別為 0111和 1000，而其格雷編碼分別為0100和 1100。例如，在求解極值問題 時， f(x)即為 x的原始適應(yīng)度函數(shù)。如果 fmin(x) 未知，則可用當(dāng)前代或到目前為止各演化代中的 f(x)的最小值來代替。 非線性加速 冪函數(shù)變換方法 f’(x)=f(x)k () 指數(shù)變換方法 f’(x)=exp(βf(x)) () 遺傳算法 4. 適應(yīng)度函數(shù) (5/5) ? ? nxfMxfniiini???????? 11)()(max ??55 遺傳算法中的基本遺傳操作包括選擇、交叉和變異 3種，而每種操作又包括多種不同的方法，下面分別對它們進行介紹。選擇時，假想轉(zhuǎn)動圓盤，若靜止時指針指向第 i個扇區(qū)，則選擇個體 i。 遺傳算法 5. 基本遺傳操作 (4/11) 59 單點交叉 單點交叉也稱簡單交叉，它是先在兩個父代個體的編碼串中隨機設(shè)定一個交叉點，然后對這兩個父代個體交叉點前面或后面部分的基因進行交換，并生成子代中的兩個新的個體。事實上，這種方法對父串中的每一位都是以相同的概率隨機進行交叉的。根據(jù)個體編碼方式的不同，變異操作可分為二進制變異和實值變異兩種類型。 例 設(shè)選中的個體向量 C=20 16 19 12 21 30，若隨機產(chǎn)生的兩個變異位置分別時 2和 4，則變異后的新的個體向量是： C’= 20 12 16 19 21 30 基于次序的變異 該方法是先隨機地產(chǎn)生兩個變異位置，然后交換這兩個變異位置上的基因。 (2) 生成初始種群 若假設(shè)給定的種群規(guī)模 N=4，則可用 4個隨機生成的長度為 5的二進制串作為初始種群。 表 46 初始種群的交叉情況表 編號 個體串（染色體） 交叉對象 交叉位 子代 適應(yīng)值 S’01 10010 S’02 3 10001 289 S’02 11001 S’01 3 11010 676 S’03 01101 S’04 N 01101 169 S’04 11001 S’03 N 11001 625 遺傳算法 6. 遺傳算法應(yīng)用簡例 (4/10) 可見，經(jīng)交叉后得到的新的種群為： S’’01=10001 S’’02=11010 S’’03=01101 S’’04=11001 70 (6) 變異 變異概率 Pm一般都很小，假設(shè)本次循環(huán)中沒有發(fā)生變異，則變異前的種群即為進化后所得到的第 1代種群。 表 48 第 1代種群的交叉情況表 73 它是通過對 S’’14的第 3位的變異來實現(xiàn)的。它主要用來處理現(xiàn)實世界中因模糊而引起的不確定性。 假設(shè)對論域 U中的元素 ， 其隸屬函數(shù)值分別為： 則可得到刻畫模糊概念 “ 年輕 ” 的模糊集 F={ 1, , , , 0} 說明其含義。 ② μF(u)的值表示 u隸屬于 F的程度，其值越大，表示 u隸屬于 F的程度越高。 表 410 第 2代種群的選擇情況表 75 這時，函數(shù)的最大值已經(jīng)出現(xiàn)，其對應(yīng)的染色體為 11111，經(jīng)解碼后可知問題的最優(yōu)解是在點 x=31處。 表 47 第 1代種群的選擇情況表 72 可見，經(jīng)雜交后得到的新的種群為： S’’11=10010 S’’12=11001 S’’13=11001 S’’14=11010 可以看出，第 3位基因均為 0，已經(jīng)不可能通過交配達到最優(yōu)解。根據(jù)此函數(shù)，初始種群中各個個體的適應(yīng)值及其所占比例如表 45所示。 按照遺傳算法，其求解過程如下： (1) 編碼 由于 x的定義域是區(qū)間 [0， 31]上的整數(shù)，由 5位二進制數(shù)即可全部表示。 變異后的新的個體是 A’= 0 1 1 1 0 1 。 整體交叉 則是對兩個父代個體的編碼向量中的所有分量，都以 1/2的概率進行交換，從而生成子代中的兩個新的個體。 當(dāng) m為奇數(shù)時，對前 (m1)個交叉點依次進行兩兩配對，構(gòu)成 (m1)/2個交叉段，而第 m個交叉點則按單點交叉方法構(gòu)成一個交叉段。 遺傳算法 5. 基本遺傳操作 (3/11) 58 (2)交叉操作 交叉（ Crossover）操作是指按照某種方式對選擇的父代個體的染色體的部分基因進行交配重組，從而形成新的個體。 常用的比例選擇策略包括 輪盤賭選擇 繁殖池選擇 遺傳算法 5. 基本遺傳操作 (1/11) 56 ②輪盤賭選擇 輪盤賭選擇法又被稱為轉(zhuǎn)盤賭選擇法或輪盤選擇法。即 （ ） 其中， xi(i=1,…,n) 為當(dāng)前代中的染色體。例如下面的極小化和極大化問題： 極小化問題 對極小化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為 () 其中， fmax (x)是原始適應(yīng)函數(shù) f(x)的一個上界。 實數(shù)編碼適應(yīng)于那種多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題。 例如， 7和 8的二進制數(shù)分別為 0111和 1000，當(dāng)算法從 7改進到 8時，就必須改變所有的位。 標(biāo)準(zhǔ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è)定的終止標(biāo)準(zhǔn)，若不滿足則返回 (5)。遺傳算法所涉及到的基本概念主要有以下幾個： 種群 （ Population）：種群是指用遺傳算法求解問題時，初始給定的多個解的集合。 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)用實例，標(biāo)志著遺傳規(guī)劃作為計算智能的一個分支已基本形成。同年，美國學(xué)者弗格爾（ Fogel）提出了一種具有多個個體和僅有變異一種進化操作的 進化規(guī)劃 。 達爾文的自然選擇學(xué)說： 在生物進化中，一種基因有可能發(fā)生變異而產(chǎn)生出另一種新的基因。 一個細胞中的所有染色體所攜帶的遺傳信息的全體稱為一個 基因組(Genome)。它以達爾文進化論的“物竟天擇、適者生存”作為算法的進化規(guī)則，并結(jié)合孟德爾的遺傳變異理論，將生物進化過程中的 繁殖（ Reproduction） 變異（ Mutation） 競爭（ Competition） 選擇（ Selection） 引入到了算法中。一個典型的離散 Hopfidld網(wǎng)絡(luò)結(jié)構(gòu)如圖 417所示。 BP網(wǎng)絡(luò)的網(wǎng)絡(luò)拓撲結(jié)構(gòu)是多層前向網(wǎng)絡(luò)，如圖 。其拓撲結(jié)構(gòu)與圖 ，差別也在于其計算節(jié)點的連接權(quán)值是可變的。后面約定相同。 單層感知器的輸出層的每個神經(jīng)元都只有一個輸出，且該輸出僅與本神經(jīng)元的輸入及聯(lián)接權(quán)值有關(guān)，而與其他神經(jīng)元無關(guān)。 反饋網(wǎng)絡(luò)的典型例子是后面將要介紹的 Hopfield網(wǎng)絡(luò) 22 人工神經(jīng)網(wǎng)絡(luò)模型 人工神經(jīng)網(wǎng)絡(luò)模型是指對網(wǎng)絡(luò)結(jié)構(gòu)、聯(lián)結(jié)權(quán)值和學(xué)習(xí)能力的總括。 隱含層是指由那些既不屬于輸入層又不屬于輸出層的神經(jīng)元所構(gòu)成的處理層 ,也被稱為中間層。它反映的是神經(jīng)元的飽和特性 . 子閾累積型 (Subthreshold Summation) 也是一個非線性函數(shù)，當(dāng)產(chǎn)生的激活值超過 T值時，該神經(jīng)元被激活產(chǎn)生個反響。 1. 生物神經(jīng)系統(tǒng)簡介 2. 人工神經(jīng)網(wǎng)絡(luò)簡介 (1) 人工神經(jīng)元的結(jié)構(gòu) (2) 常用的人工神經(jīng)元模型 (3) 人工神經(jīng)網(wǎng)絡(luò)及其分類 14 θ … x1 x2 xn w1 w2 wn y MP模型是美國心理學(xué)家麥克洛奇 ( ulloch)和數(shù)理邏輯學(xué)家皮茨() 根據(jù)生物神經(jīng)元的功能和結(jié)構(gòu)，于 1943年提出的一種將神經(jīng)元看作二進制閾值元件的簡單模型。 8 神經(jīng)計算基礎(chǔ) 生物神經(jīng)系統(tǒng)是人工神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)。 按照貝慈德克的觀點， CNN是指按生物激勵模型構(gòu)造的 NN， ANN是指CNN+知識， BNN是指人腦，即 ANN包含了 CNN， BNN又包含了 ANN。 1998年 5月，在美國阿拉斯加州的安克雷奇市又召開了第 2屆計算智能國際會議 WCCI’ 98。 進化計算 是一種對人類智能的演化模擬方法，它是通過對生