人工智能[第九章神經(jīng)網(wǎng)絡(luò)與遺傳算法]山東大學(xué)期末考試知識點復(fù)習(xí)

1、第九章神經(jīng)網(wǎng)絡(luò)與遺傳算法11人工神經(jīng)網(wǎng)絡(luò)概述從廣義上講，神經(jīng)網(wǎng)絡(luò)是泛指生物神經(jīng)網(wǎng)絡(luò)與人工神經(jīng)網(wǎng)絡(luò)這兩個方面。所謂生物神經(jīng)網(wǎng)絡(luò)是指由中樞神經(jīng)系統(tǒng)(腦和脊髓)及周圍神經(jīng)系統(tǒng)(感覺神經(jīng)、運動神經(jīng)、交感神經(jīng)、副交感神經(jīng)等)所構(gòu)成的錯綜復(fù)雜的神經(jīng)網(wǎng)絡(luò)，它負責(zé)對動物肌體各種活動的管理，其中最重要的是腦神經(jīng)系統(tǒng)。所謂人工神經(jīng)網(wǎng)絡(luò)是指模擬人腦神經(jīng)系統(tǒng)的結(jié)構(gòu)和功能，運用大量的處理部件，由人工方式建立起來的網(wǎng)絡(luò)系統(tǒng)。1人工神經(jīng)網(wǎng)絡(luò)的組成及特征人工神經(jīng)網(wǎng)絡(luò)(ArtificialNeuralNets,ANN)是由大量處理單元經(jīng)廣泛互連而組成的人工網(wǎng)絡(luò)，用來模擬腦神經(jīng)系統(tǒng)的結(jié)構(gòu)和功能，這些處理單元稱作人工神經(jīng)元。圖9.

2、1表示人工神經(jīng)網(wǎng)絡(luò)(ANN)的組成略圖，它由多個人工神經(jīng)元相互連接組成。圖9.2表示每個神經(jīng)元模型，圖中，圓表示神經(jīng)元的細胞體；xi表示該神經(jīng)元的外部輸入，對應(yīng)于生物神經(jīng)元的樹突；3i為該神經(jīng)元分別與各輸入間的連接強度，稱為連接權(quán)值；0表示神經(jīng)元的閾值；y表示神經(jīng)元的輸出，它對應(yīng)于生物神經(jīng)元的軸突。人工神經(jīng)網(wǎng)絡(luò)中，各神經(jīng)元的連接方式一般有很多種，不同的連接方式就構(gòu)成了網(wǎng)絡(luò)的不同連接模型。常見的連接模型有前向網(wǎng)絡(luò)、從輸入層到輸出層有反人工神經(jīng)網(wǎng)絡(luò)具有以下主要特征：能較好的模擬人的形象思維。具有大規(guī)模并行協(xié)同處理能力。具有較強的學(xué)習(xí)能力。具有較強的容錯能力和聯(lián)想能力。是一個大規(guī)模自組織、自適應(yīng)的非

3、線性動力系統(tǒng)。2人工神經(jīng)元的工作過程假設(shè)來自其他處理單元(神經(jīng)元)i的信息為xi,它們與本處理單元的互相作用強度即連接權(quán)值為3i,i=0,1,，n1,處理單元的內(nèi)部閾值為8。那么本神經(jīng)元的輸入為而處理單元的輸出為其中，xi為第i個元素的輸入，3i為第i個處理單元與本處理單元的互聯(lián)權(quán)重。f稱為激發(fā)函數(shù)或作用函數(shù)，它決定節(jié)點(神經(jīng)元)的輸出。該輸出為1或0取決于其輸入之和大于或小于內(nèi)部閾值e。令。=-，稱為激活值。激發(fā)函數(shù)一般具有非線性特性。常用的非線性激發(fā)函數(shù)有閾值型、分段線性型、Sigmoid函數(shù)型(簡稱S型)和雙曲正切型。如圖9.3所示。圖乩3常用的溢岌函散兇祠迫樂(切廿用毀性也(c)Sig

4、moidft但】取曲正切期3人工神經(jīng)網(wǎng)絡(luò)的分類從不同的角度進行劃分，可以得到神經(jīng)網(wǎng)絡(luò)模型不同的分類結(jié)果。若按網(wǎng)絡(luò)的性能劃分，可分為連續(xù)型和離散型網(wǎng)絡(luò)，又可分為確定型和隨機型網(wǎng)絡(luò)；若按網(wǎng)絡(luò)的拓撲結(jié)構(gòu)劃分，則可分為有反饋網(wǎng)絡(luò)和無反饋網(wǎng)絡(luò)；若按網(wǎng)絡(luò)的學(xué)習(xí)方法劃分，則可分為有教師的學(xué)習(xí)網(wǎng)絡(luò)和無教師的學(xué)習(xí)網(wǎng)絡(luò)；若按連接突觸的性質(zhì)劃分，則可分為一階線性關(guān)聯(lián)網(wǎng)絡(luò)和高階非線性關(guān)聯(lián)網(wǎng)絡(luò)。12基于反向傳播的網(wǎng)絡(luò)模型1反向傳播模型及其網(wǎng)絡(luò)結(jié)構(gòu)反向傳播模型也稱B-P(Back-Propagation)模型，是一種用于前向多層神經(jīng)網(wǎng)絡(luò)的反向傳播學(xué)習(xí)算法。由魯梅爾哈特(D.Rumelhart)和麥克萊倫德(MeClell

5、and)于1985年提出的。目前，B-P算法已經(jīng)成為應(yīng)用最多且最主要的一種訓(xùn)練前向人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法，也是前向網(wǎng)絡(luò)得以廣泛應(yīng)用的基礎(chǔ)。BP算法的網(wǎng)絡(luò)結(jié)構(gòu)是一個前向多層網(wǎng)絡(luò)，網(wǎng)絡(luò)中不僅含有輸入節(jié)點和輸出節(jié)點，而且含有一層或多層隱(層)節(jié)點，如圖9.4所示。2.BP算法的學(xué)習(xí)過程ffi9,也P阻站BP算法的學(xué)習(xí)目的是對網(wǎng)絡(luò)的連接權(quán)值進行調(diào)整，使得調(diào)整后的網(wǎng)絡(luò)對任一輸入都能得到所期望的輸出。學(xué)習(xí)過程由正向傳播和反向傳播組成。正向傳播用于對前向網(wǎng)絡(luò)進行計算，即對某一輸入信息，經(jīng)過網(wǎng)絡(luò)計算后求出它的輸出結(jié)果；反向傳播用于逐層傳遞誤差，修改神經(jīng)元間的連接權(quán)值，以使網(wǎng)絡(luò)對輸入信息經(jīng)過計算后所得到的輸出能

6、達到期望的誤差要求。學(xué)習(xí)的方法是使用一組訓(xùn)練樣例對網(wǎng)絡(luò)的連接權(quán)值進行訓(xùn)練，每一個樣例中，都包括輸入及期望的輸出兩部分。在正向傳播過程中，首先將訓(xùn)練樣例的輸入信息輸入到網(wǎng)絡(luò)中，輸入信息從輸入層經(jīng)隱層節(jié)點逐層計算處理后，傳至輸出層。在計算處理過程中，每一層神經(jīng)元的狀態(tài)只影響下一層神經(jīng)元的狀態(tài)，如果在輸出層得到的結(jié)果不是所期望的輸出，那么就轉(zhuǎn)為反向傳播。反向傳播把誤差信號沿原連接路徑返回，并按一定的原則對各層神經(jīng)元的連接權(quán)值進行適當(dāng)修改，直至第一個隱層，這時再開始進行正向傳播，利用剛才的輸入信息進行正向網(wǎng)絡(luò)計算，如果網(wǎng)絡(luò)的輸出達到了誤差要求，則學(xué)習(xí)過程結(jié)束，如果達不到誤差要求，則再進行反向傳播的連接

7、權(quán)值調(diào)整。這一過程不斷往復(fù)，直到網(wǎng)絡(luò)正向計算的輸出結(jié)果達到誤差要求為止，這時學(xué)習(xí)過程就告結(jié)束。一旦網(wǎng)絡(luò)進行訓(xùn)練之后，在用于求解實際問題時就只需使用正向傳播，而不需要再進行反向傳播了。BP算法的學(xué)習(xí)過程如下：選擇一組訓(xùn)練樣例，每一個樣例由輸入信息和期望的輸出結(jié)果兩部分組成。從訓(xùn)練樣例集中取一樣例，把輸入信息輸入到網(wǎng)絡(luò)中。分別計算經(jīng)神經(jīng)元處理后的各層節(jié)點的輸出。計算網(wǎng)絡(luò)的實際輸出和期望輸出的誤差。從輸出層反向計算到第一個隱層，并按照某種能使誤差向減小方向發(fā)展的原則，調(diào)整網(wǎng)絡(luò)中各神經(jīng)元的連接權(quán)值。對訓(xùn)練樣例集中的每一個樣例重復(fù)的步驟，直到對整個訓(xùn)練樣例集的誤差達到要求時為止。在以上的學(xué)習(xí)過程中，第步

8、是最重要的，如何確定一種調(diào)整連接權(quán)值的原則，使誤差沿著減小的方向發(fā)展，是B-P學(xué)習(xí)算法必須解決的問題。B-P是一個在解決實際問題時很有效的算法，由于它理論基礎(chǔ)牢固，推導(dǎo)過程嚴謹，物理概念清晰及通用性好等優(yōu)點。所以，它是目前用來訓(xùn)練前向多層網(wǎng)絡(luò)較好的算法。然而BP算法也有一些缺點，主要表現(xiàn)在：該學(xué)習(xí)算法的收斂速度慢，常常需要成千上萬次的迭代，而且隨著訓(xùn)練樣例維數(shù)的增加，網(wǎng)絡(luò)性能會變差。網(wǎng)絡(luò)中隱節(jié)點個數(shù)的選取尚無理論上的指導(dǎo)。從數(shù)學(xué)角度看，B-P算法是一種梯度最速下降法，這就可能出現(xiàn)局部極小的問題。當(dāng)出現(xiàn)局部極小時，從表面上看，誤差符合要求，但這時所得到的解并不一定是問題的真正解。所以B-P算法是

9、不完備的。所謂算法的完備性是指，若問題有解，則運用算法就一定能夠求得它的解。對于B-P算法的這些缺點，目前已提出了一些解決的辦法，并且對BP算法的研究還在不斷進行中。13Hopfield網(wǎng)絡(luò)模型由于在反饋網(wǎng)絡(luò)中，網(wǎng)絡(luò)的輸出要反復(fù)地作為輸入再送入網(wǎng)絡(luò)中，這就使得網(wǎng)絡(luò)具有了動態(tài)性，網(wǎng)絡(luò)的狀態(tài)在不斷的改變之中，因而就提出了網(wǎng)絡(luò)的穩(wěn)定性問題。所謂一個網(wǎng)絡(luò)是穩(wěn)定的是指從某一時刻開始，網(wǎng)絡(luò)的狀態(tài)不再改變。設(shè)用X(t)表示網(wǎng)絡(luò)在時刻t的狀態(tài)，如果從t=0的任一初態(tài)X(0)開始，存在一個有限的時刻t，使得從此時刻開始神經(jīng)網(wǎng)絡(luò)的狀態(tài)不再發(fā)生變化，即X(t+t)=X(t)t0(9.3)就稱此網(wǎng)絡(luò)是穩(wěn)定的。離散網(wǎng)絡(luò)

10、模型是一個離散時間系統(tǒng)，每個神經(jīng)元只有兩個狀態(tài)，可以用1和0來表示，由連接權(quán)值Wjj所構(gòu)成的矩陣是一個對角線為0的對稱矩陣，即如果用x(t)表示整個網(wǎng)絡(luò)在時刻的狀態(tài)，則X是一個向量，它包含了網(wǎng)絡(luò)中每個人工神經(jīng)元的狀態(tài)。所以，狀態(tài)向量X中的分量個數(shù)就是網(wǎng)絡(luò)中人工神經(jīng)元的個數(shù)。假設(shè)網(wǎng)絡(luò)中的節(jié)點(人工神經(jīng)元)個數(shù)為n則向量X的構(gòu)成如下:XT(t)=x1(t)，x2(t)，xi(t)，xn(t)(95)xi(t)表示節(jié)點i(第i個神經(jīng)元)在t時刻的狀態(tài),該節(jié)點在時刻t+1的狀態(tài)由式(9.6)決定：這里，二，其中的Wi.為節(jié)點i到節(jié)點j的連接權(quán)值；e.為節(jié)點j的閾值。如果設(shè)Y(t)是網(wǎng)絡(luò)輸出層節(jié)點在時刻

11、t的狀態(tài)向量，它是X(t)向量的一個子向量，其中每個分量都為輸出層的一個節(jié)點。如果輸出層有兩個節(jié)點，并且用1和0分別表示每個節(jié)點的狀態(tài)，則整個網(wǎng)絡(luò)就有4種狀態(tài)，分別為：00、01、10和11。如果輸出層有3個節(jié)點，則整個網(wǎng)絡(luò)就有8種狀態(tài)，分別是000、001、010、011、100、101、110和111。一般情況下，如果輸出層有m個神經(jīng)元，則整個網(wǎng)絡(luò)的輸出狀態(tài)就可能有2m個。當(dāng)輸入向量信息進入網(wǎng)絡(luò)后，網(wǎng)絡(luò)的迭代計算過程就使得輸出從一個狀態(tài)轉(zhuǎn)向另一個狀態(tài)，直到穩(wěn)定或趨于穩(wěn)定于某一個狀態(tài)為止。Hopfield網(wǎng)絡(luò)離散模型有兩種工作模式：一種稱為串行或異步方式，另一種稱為并行或同步方式。所謂串行方

12、式，是指在任一時刻t，只有一個神經(jīng)元i發(fā)生狀態(tài)變化，而其余的神經(jīng)元保持狀態(tài)不變。所謂并行方式，是指在任一時刻t，都有部分或全體神經(jīng)元同時改變狀態(tài)。有關(guān)離散的Hopfield網(wǎng)絡(luò)的穩(wěn)定性問題，已于1983年由Cohen和Grossberg給予了證明。而Hopfield等人又進一步證明，只要連接權(quán)值構(gòu)成的矩陣是非負對角元的對稱矩陣，則該網(wǎng)絡(luò)就具有串行穩(wěn)定性。由于離散的Hopfield網(wǎng)絡(luò)模型中，各神經(jīng)元的狀態(tài)只有兩種，即0和1，這與通常人類的大腦神經(jīng)元具有較大的差異，因為人腦神經(jīng)元的輸入和輸出是一些連續(xù)的信號，且人腦神經(jīng)元存在時延。所以，為了更好地用人工神經(jīng)元模擬人腦神經(jīng)元，1984年，Hopfi

13、eld又提出了連續(xù)時間的神經(jīng)網(wǎng)絡(luò)，在這種神經(jīng)網(wǎng)絡(luò)中，各節(jié)點可在01的區(qū)間內(nèi)取任一實數(shù)值。2Hopfield網(wǎng)絡(luò)學(xué)習(xí)算法設(shè)置互連權(quán)值。I。IJ其中xis是s類樣例的第i個分量，它可以為1或0,樣例類別數(shù)為m,節(jié)點數(shù)為n。未知類別樣本初始化。yi(0)=xi0WiWn1(9.8)其中，yi(t)為節(jié)點i在t時刻的輸出，當(dāng)t=0時，yi(0)就是節(jié)點i的初始值，xi為輸入樣本的第i個分量。迭代直到收斂。式(9.9)中f為閾值型激發(fā)函數(shù)。該過程一直迭代到不再改變節(jié)點的輸出為止。這時各節(jié)點的輸出與輸入樣例達到最佳匹配。否則轉(zhuǎn)繼續(xù)。1.4遺傳算法的概念與原理遺傳算法(GeneticAlgorithm，GA

14、)是一種受進化論思想啟發(fā)而得出的一種全局優(yōu)化搜索算法。1975年，美國密執(zhí)根大學(xué)的霍勒德(J.H.Holland)提出了模擬自然進化過程的遺傳算法，開創(chuàng)性地對遺傳算法的理論和方法進行了系統(tǒng)性地研究，其當(dāng)時的主要目的是為了說明自然和人工系統(tǒng)的自適應(yīng)過程。由于遺傳算法的本質(zhì)是一種不依賴具體問題的直接搜索方法，因此，近年來在模式識別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會科學(xué)等領(lǐng)域都得到了廣泛的應(yīng)用，并且有人認為，遺傳算法將是未來十年對計算技術(shù)有重大影響的關(guān)鍵技術(shù)之一。1.遺傳算法的基本概念遺傳算法的基本思想源于達爾文(C.R.Darwin)的進化論和門德爾(G.J.

15、Mendel)的遺傳學(xué)說。在遺傳算法的理論中要涉及各種進化和遺傳學(xué)的概念，這些概念包括：串：以二進制數(shù)碼表示的數(shù)字串，是個體的表示形式。對應(yīng)于遺傳學(xué)中的染色體。群體：個體的集合稱為群體。群體的元素是個體，其表現(xiàn)形式為串。群體大?。涸谌后w中個體的數(shù)量稱為群體的大小?；颍夯蚴谴械脑兀蛴糜诒硎緜€體的特征。例如有一個串S=1011,則其中的1、0、1、1這4個元素分別稱為基因?；蛭恢茫阂粋€基因在串中的位置稱為基因位置，有時也簡稱基因位?；蛭恢糜纱淖筮呄蛴疫呌嬎悖缭诖甋=1101中，0的基因位置是3?；蛭恢脤?yīng)于遺傳學(xué)中的地點?；蛱卣髦担涸谟么硎菊麛?shù)時，基因的特征值與二進制數(shù)

16、的權(quán)一致；例如在串S=1011中，基因位置3中的1,它的基因特征值為2；基因位置1中的1，它的基因特征值為8。串結(jié)構(gòu)空間Ss：串結(jié)構(gòu)空間是指，串中各基因任意組合所構(gòu)成的串的集合。基因操作是在結(jié)構(gòu)空間中進行的。串結(jié)構(gòu)空間對應(yīng)于遺傳學(xué)中的基因型的集合。參數(shù)空間SP：這是串空間在物理系統(tǒng)中的映射。它對應(yīng)于遺傳學(xué)中的表現(xiàn)型的集合。非線性：它對應(yīng)遺傳學(xué)中的異位顯性。適應(yīng)度：表示某一個體對于環(huán)境的適應(yīng)程度。除此之外，遺傳算法還有一些其他的概念，我們將在下面介紹遺傳算法的原理和執(zhí)行過程時再進行說明。2遺傳算法的原理遺傳算法GA把問題的解表示成“染色體”，也即是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出

17、一群“染色體”(串)，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進行復(fù)制，再通過交換、突變等遺傳操作過程，產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。霍勒德提出的遺傳算法也稱簡單遺傳算法(SimpleGeneticAlgorithm，SGA)，是一種基本的遺傳算法，其基本過程可表示如下：begin選擇適當(dāng)表示模式，生成初始群體；通過計算群體中各個體的適應(yīng)度對群體進行評價；cWhile未達到要求的目標dobegina.選擇作為下一代群體的各個體；執(zhí)行交換操

18、作；執(zhí)行突變操作；對群體進行評價；endend由上述過程可以看出，SGA算法主要涉及以下內(nèi)容：表示模式和初始群體生成,群體的評價，個體的選擇，交換操作，突變操作。由上述過程可以看出，SGA算法主要涉及以下內(nèi)容：表示模式和初始群體生成，群體的評價，個體的選擇，交換操作，突變操作。表示模式是遺傳算法的理論基礎(chǔ)，是一個描述群體中串的某些確定位置上具有相似性的串子集的相似性模板。初始群體生成是指生成n個二進制串bi(i=1,2,，n)組成遺傳算法的初始群體。一般可用隨機方法來產(chǎn)生初始群體，當(dāng)然最好能考慮各個體的代表性和分布概率。群體的評價是對群體中各個體的適應(yīng)性進行評價，通常需構(gòu)造一目標函數(shù)或稱適應(yīng)函

19、數(shù)。適應(yīng)函數(shù)的構(gòu)造對參加交換和突變操作的個體選擇極為重要，例如，可以將串中的各元素的和作為適應(yīng)度值來構(gòu)造一個評價函數(shù)。個體選擇就是從群體中選擇出較適應(yīng)環(huán)境的個體，并利用這些選中的個體繁殖下一代。故有時也稱這一操作為再生(Reproduction)。選擇個體的方法通常依據(jù)個體對環(huán)境的適應(yīng)度(Fitness)作為評價依據(jù)。適應(yīng)度(目標函數(shù)值)較大的個體有較高的概率生存，即在下一代群體中再次出現(xiàn)。交換操作又稱交叉操作或雜交操作，是GA中最主要的遺傳操作。該操作在所選中的用于繁殖下一代的個體中，對兩個不同的個體(串對)的相同位置的基因進行交換，從而產(chǎn)生新的個體。突變操作又稱變異操作，一般在交換操作后執(zhí)行。該操作對選中的個體(即串或“染色體”)中