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