醫(yī)學(xué)專題人工神經(jīng)網(wǎng)絡(luò)第七章

1、第7章 循環(huán)網(wǎng)絡(luò)主要內(nèi)容Hopfield網(wǎng)絡(luò)實現(xiàn)的自相聯(lián)存儲穩(wěn)定性分析統(tǒng)計Hopfield網(wǎng)與Boltzmann機(jī)基本雙聯(lián)存儲器(BAM)的結(jié)構(gòu)與訓(xùn)練幾種相聯(lián)存儲網(wǎng)絡(luò)用Hopfield網(wǎng)解決TSP問題。2021/7/19 星期一1第7章 循環(huán)網(wǎng)絡(luò)重點Hopfield網(wǎng)絡(luò)實現(xiàn)的自相聯(lián)存儲基本雙聯(lián)存儲器的結(jié)構(gòu)與訓(xùn)練。難點穩(wěn)定性分析用Hopfield網(wǎng)解決TSP問題 2021/7/19 星期一2第7章 循環(huán)網(wǎng)絡(luò)7.1 循環(huán)網(wǎng)絡(luò)的組織 7.2 穩(wěn)定性分析 7.3 統(tǒng)計Hopfield網(wǎng)與Boltzmann機(jī) 7.4 雙聯(lián)存儲器的結(jié)構(gòu) 7.5 異相聯(lián)存儲 7.6 其它的雙聯(lián)存儲器 7.7 Hopfiel

2、d網(wǎng)用于解決TSP問題 2021/7/19 星期一3第7章 循環(huán)網(wǎng)絡(luò) 循環(huán)網(wǎng)絡(luò)稱為Hopfield網(wǎng) 循環(huán)網(wǎng)絡(luò)對輸入信號的處理是一個逐漸“修復(fù)”、“加強(qiáng)”的過程。強(qiáng)烈變化較弱的變化不變化2021/7/19 星期一47.1 循環(huán)網(wǎng)絡(luò)的組織 網(wǎng)絡(luò)結(jié)構(gòu)X1Xno1om2021/7/19 星期一57.1 循環(huán)網(wǎng)絡(luò)的組織 聯(lián)接：神經(jīng)元之間都是互聯(lián)的wij，每個神經(jīng)元都沒有到自身的聯(lián)接wii=0。神經(jīng)元個數(shù)h，輸入向量維數(shù)n，輸出向量維數(shù)m。hn，hm，n1，m1。神經(jīng)元：輸入、輸出、隱藏狀態(tài)變化：非同步、同步輸入向量：X=(x1，x2，xn) 輸出向量：O=(o1，o2，om) 2021/7/19 星期

3、一67.1 循環(huán)網(wǎng)絡(luò)的組織神經(jīng)元的網(wǎng)絡(luò)輸入： 閾值函數(shù)：oj=1if netjj0if netj0，ok=1& ok=0，ok由0變到1，netkk，netk-k0所以，-(netk-k)ok0故0結(jié)論：網(wǎng)絡(luò)的目標(biāo)函數(shù)總是下降ok0, ok=0& ok=1，ok由1變到0netkk，netk-k0-(netk-k)ok0故r 則使ANi的狀態(tài)為1， 否則使ANi的狀態(tài)為0；3 逐漸降低溫度T，如果溫度足夠低，則算法結(jié)束。否則，重復(fù)2 2021/7/19 星期一40Boltzmann機(jī)的訓(xùn)練 Boltzmann機(jī)是多級循環(huán)網(wǎng)絡(luò)，是Hopfield網(wǎng)的一種擴(kuò)展。神經(jīng)元ANi實際輸出狀態(tài)oi=1的概

4、率為： T趨近于0時，神經(jīng)元的狀態(tài)不再具有隨機(jī)性，Boltzmann機(jī)退化成一般Hopfield網(wǎng)。 2021/7/19 星期一41Boltzmann機(jī)的訓(xùn)練 2021/7/19 星期一42Boltzmann機(jī)的訓(xùn)練 2021/7/19 星期一43Boltzmann機(jī)的訓(xùn)練 Boltzmann機(jī)是多級循環(huán)網(wǎng)絡(luò)，是Hopfield網(wǎng)的一種擴(kuò)展。神經(jīng)元ANi網(wǎng)絡(luò)輸入為： T趨近于0時，神經(jīng)元的狀態(tài)不再具有隨機(jī)性，Boltzmann機(jī)退化成一般Hopfield網(wǎng)。 2021/7/19 星期一44Boltzmann機(jī)的訓(xùn)練 神經(jīng)元ANi實際輸出狀態(tài)oi=1的概率為神經(jīng)元ANi實際輸出狀態(tài)oi=0的概率

5、為顯然 越大，則 oi 取1的概率越大2021/7/19 星期一45Boltzmann機(jī)的訓(xùn)練神經(jīng)元ANi在運行中狀態(tài)發(fā)生了變化 Boltzmann機(jī)的能量函數(shù)(一致性函數(shù) )2021/7/19 星期一46Boltzmann機(jī)的訓(xùn)練如果i0，神經(jīng)元ANi處于狀態(tài)1的概率就應(yīng)該越大，否則，神經(jīng)元ANi處于狀態(tài)0的概就應(yīng)該越大。i的值越大，神經(jīng)元ANi應(yīng)該處于狀態(tài)1的概率就應(yīng)該越大。反之，i的值越小，神經(jīng)元ANi應(yīng)該處于狀態(tài)1的概率就應(yīng)該越小。從而，oi=1的概率為： 2021/7/19 星期一47Boltzmann機(jī)的訓(xùn)練處于狀態(tài)a，b的概率Pa和Pb，對應(yīng)于oi=1和oi=0，其它的神經(jīng)元在a

6、，b狀態(tài)下不變 Pa=pi Pb =（1-pi） 當(dāng)系統(tǒng)的溫度較低時，如果EaPb：網(wǎng)絡(luò)處于較低能量狀態(tài)的概率較大 2021/7/19 星期一48Boltzmann機(jī)的訓(xùn)練網(wǎng)絡(luò)進(jìn)行足夠多次迭代后，處于某狀態(tài)的概率與此狀態(tài)下的能量和此時系統(tǒng)的溫度有關(guān)。由于高溫時網(wǎng)絡(luò)的各個狀態(tài)出現(xiàn)的概率基本相同，這就給它逃離局部極小點提供了機(jī)會。2021/7/19 星期一49Boltzmann機(jī)的訓(xùn)練1986年，Hinton和Sejnowski訓(xùn)練方法自由概率Pij-：沒有輸入時ANi和ANj同時處于激發(fā)狀態(tài)的概率。約束概率Pij+：加上輸入后ANi和ANj同時處于激發(fā)狀態(tài)的概率。聯(lián)接權(quán)修改量：wij=( Pij

7、+ - Pij-) 2021/7/19 星期一50算法7-2 Boltzmann機(jī)訓(xùn)練算法 1計算約束概率 1.1 對樣本集中每個樣本，執(zhí)行如下操作： 1.1.1 將樣本加在網(wǎng)絡(luò)上（輸入向量及其對應(yīng)的輸出向量）； 1.1.2 讓網(wǎng)絡(luò)尋找平衡； 1.1.3 記錄下所有神經(jīng)元的狀態(tài)； 1.2 計算對所有的樣本，ANi和ANj的狀態(tài)同時為1的概率Pij+；2021/7/19 星期一51算法7-2 Boltzmann機(jī)訓(xùn)練算法 2 計算自由概率 2.1 從一個隨機(jī)狀態(tài)開始，不加輸入、輸出，讓網(wǎng)絡(luò)自由運行，并且在運行過程中多次紀(jì)錄網(wǎng)絡(luò)的狀態(tài)； 2.2 對所有的ANi和ANj，計算它們的狀態(tài)同時為1的概率

8、Pij-； 3 對權(quán)矩陣進(jìn)行調(diào)整wij=(Pij+-Pij-)2021/7/19 星期一527.7 Hopfield網(wǎng)解決TSP問題1985年，J. J. Hopfield和D. W. Tank用循環(huán)網(wǎng)求解TSP。試驗表明，當(dāng)城市的個數(shù)不超過30時，多可以給出最優(yōu)解的近似解。而當(dāng)城市的個數(shù)超過30時，最終的結(jié)果就不太理想了 設(shè)問題中含有n個城市,用n*n個神經(jīng)元構(gòu)成網(wǎng)絡(luò) 2021/7/19 星期一53應(yīng)用CHNN網(wǎng)解決優(yōu)化計算問題 用CHNN網(wǎng)解決優(yōu)化問題一般需要以下幾個步驟： (1)對于特定的問題，要選擇一種合適的表示方法，使得神經(jīng)網(wǎng)絡(luò)的輸出與問題的解相對應(yīng)； (2)構(gòu)造網(wǎng)絡(luò)能量函數(shù)，使其最

9、小值對應(yīng)于問題的最佳解； (3)將能量函數(shù)與Lyapunov函數(shù)標(biāo)準(zhǔn)形式進(jìn)行比較，可推出神經(jīng)網(wǎng)絡(luò)的權(quán)值與偏流的表達(dá)式，從而確定了網(wǎng)絡(luò)的結(jié)構(gòu)； (4)由網(wǎng)絡(luò)結(jié)構(gòu)建立網(wǎng)絡(luò)的電子線路并運行，其穩(wěn)態(tài)就是在一定條件下的問題優(yōu)化解。也可以編程模擬網(wǎng)絡(luò)的運行方式，在計算機(jī)上實現(xiàn)。 2021/7/19 星期一54 TSP問題是一個經(jīng)典的人工智能難題。對n個城市而言，可能的路徑總數(shù)為n!2n。隨著n的增加，路徑數(shù)將按指數(shù)率急劇增長，即所謂“指數(shù)爆炸”。當(dāng)n值較大時，用傳統(tǒng)的數(shù)字計算機(jī)也無法在有限時間內(nèi)尋得答案。例如，n50時，即使用每秒1億次運算速度的巨型計算機(jī)按窮舉搜索法，也需要51048年時間。即使是n20

10、個城市，也需求解350年。 1985年Hopfield和Tank兩人用CHNN網(wǎng)絡(luò)為解決TSP難題開辟了一條嶄新的途徑，獲得了巨大的成功。2021/7/19 星期一55 其基本思想是把TSP問題映射到CHNN網(wǎng)絡(luò)中去，并設(shè)法用網(wǎng)絡(luò)能量代表路徑總長。這樣，當(dāng)網(wǎng)絡(luò)的能量隨著模擬電子線路狀態(tài)的變遷，最終收斂于極小值(或最小值)時，問題的較佳解(或最佳解)便隨之求得。此外，由于模擬電子線路中的全部元件都是并行工作的，所以求解時間與城市數(shù)的多少無關(guān)，僅是運算放大器工作所需的微秒級時間，顯著地提高了求解速度，充分展示了神經(jīng)網(wǎng)絡(luò)的巨大優(yōu)越性。2021/7/19 星期一561TSP問題描述 為使CHNN網(wǎng)絡(luò)完

11、成優(yōu)化計算，必須找到一種合適的表示旅行路線的方法。鑒于TSP的解是n個城市的有序排列，因此可用一個由nn個神經(jīng)元構(gòu)成的矩陣(稱為換位陣)來描述旅行路線。圖7.5給出8城市TSP問題中的一條可能的有效路線的換位陣。2021/7/19 星期一57 TSP問題描述 為使CHNN網(wǎng)絡(luò)完成優(yōu)化計算，必須找到一種合適的表示旅行路線的方法。鑒于TSP的解是n個城市的有序排列，因此可用一個由nn個神經(jīng)元構(gòu)成的矩陣(稱為換位陣)來描述旅行路線。圖給出8城市TSP問題中的一條可能的有效路線的換位陣。2021/7/19 星期一58 由于每個城市僅能訪問一次，因此換位陣中每城市行只允許且必須有一個1，其余元素均為0。

12、為了用神經(jīng)元的狀態(tài)表示某城市在某一有效路線中的位置，采用雙下標(biāo) Yxi，第一個下標(biāo)x表示城市名，1，2，n；第二個下標(biāo)i表示該城市在訪問路線中的位置，i1，2，n。例如，Y461表示旅途中第6站應(yīng)訪問城市4；若Y460則表示第6 站訪問的不是城市4，而是其他某個城市。 圖78中的換位陣所表示的旅行路線為: 425813764，旅行路線總長為d42+d25+d58+d81+d13+d37+d76+d64。2021/7/19 星期一597.7 Hopfield網(wǎng)解決TSP問題dxy城市X與城市Y之間的距離；vxi城市X的第i個神經(jīng)元的狀態(tài)： 1城市X在第i個被訪問vxi= 0城市X不在第i個被訪問

13、wxi,yj城市X的第i個神經(jīng)元到城市Y的第j個神經(jīng)元的連接權(quán)。 2021/7/19 星期一607.7 Hopfield網(wǎng)用于解決TSP問題例如：四個城市X、Y、Z、W城市名訪問順序標(biāo)示1234X0100Y0001Z1000W00102021/7/19 星期一61能量函數(shù)設(shè)計 用CHNN求解TSP問題的關(guān)鍵是構(gòu)造一個合適的能量函數(shù)。TSP問題的能量函數(shù)由4部分組成： (1)能量E1城市行約束 當(dāng)每個城市行中的1不多于一個時，應(yīng)有第x行的全部元素vxi按順序兩兩相乘之和為0，即 從而全部n行的所有元素按順序兩兩相乘之和也應(yīng)為零，即=0 2021/7/19 星期一62 按此約束可定義能量E1為 式

14、中A為正常數(shù)。顯然，當(dāng)E10時可保證對每個城市訪問的次數(shù)不超過一次。 (2)能量E2位置列約束 同理，當(dāng)每個位置列中的1不多于一個時，應(yīng)有第i列的全部元素vxi按順序兩兩相乘之和為0，即 因此，全部n列的所有元素按順序兩兩相乘之和也應(yīng)為零，即=02021/7/19 星期一63 按此約束可定義能量E2為 式中B為正常數(shù)。顯然，當(dāng)E20時就能確保每次訪問的城市數(shù)不超過一個。 (3)能量E3換位陣全局約束 E10和E20只是換位陣有效的必要條件，但不是充分條件。容易看出，當(dāng)換位陣中各元素均為“0”時，也能滿足El0和E20，但這顯然是無效的。因此，還需引入第三個約束條件全局約束條件，以確保換位陣中1

15、的數(shù)目等于城市數(shù)n，即2021/7/19 星期一64 因此定義能量E 為 式中C為正常數(shù)。則E30可保證換位陣中1的數(shù)目正好等于n。 2021/7/19 星期一65 (4)能量E4旅行路線長度 同時滿足以上3個約束條件只能說明路線是有效的，但不一定是最優(yōu)的。依題意，在路線有效的前提下，其總長度應(yīng)最短。為此在能量函數(shù)中尚須引入一個能反映路線總長度的分量E4，其定義式要能保證E4隨路線總長度的縮短而減小。為設(shè)計E4，設(shè)任意兩城市x與y間的距離為dxy 。訪問這兩個城市有兩種途徑，從x到y(tǒng)，相應(yīng)的表達(dá)式為 dxy(vxi ,vy,i+1)；從y到x，則相應(yīng)的表達(dá)式為dyx(vxi ,vy,i1) 。

16、如果城市x和y在旅行順序中相鄰，則當(dāng) (vxi ,vy,i+1) 1時，必有 (vxi ,vy,i1) 0；反之亦然。因此，有dxy(vxi,vy,i1) (vxi,vy,i1dxy。若定義n個城市各種可能的旅行路線長度為2021/7/19 星期一66 式中D為正常數(shù)，當(dāng)E4最小時旅行路線最短。 綜合以上4項能量，可得TSP問題的能量函數(shù)如下：(6.30)2021/7/19 星期一67網(wǎng)絡(luò)的能量函數(shù)2021/7/19 星期一687.7 Hopfield網(wǎng)用于解決TSP問題 聯(lián)接矩陣 wxi,yj= -Axy(1-ij) Bij(1-xy) C dxy(ji+1+ji-1) 1如果i=jij= 0如果ij 2021/7/19 星期一69 圖給出用CHNN網(wǎng)解決10城市TSP問題的結(jié)果。圖 (a)為最優(yōu)解，圖 (b)為較佳解。2021/7/19 星期一70 按照窮舉法，我國31個(尚未計