人工神經(jīng)網(wǎng)絡(luò)第七章

1、第7章 循環(huán)網(wǎng)絡(luò)主要內(nèi)容Hopfield網(wǎng)絡(luò)實(shí)現(xiàn)的自相聯(lián)存儲(chǔ)穩(wěn)定性分析統(tǒng)計(jì)Hopfield網(wǎng)與Boltzmann機(jī)根本雙聯(lián)存儲(chǔ)器(BAM)的結(jié)構(gòu)與訓(xùn)練幾種相聯(lián)存儲(chǔ)網(wǎng)絡(luò)用Hopfield網(wǎng)解決TSP問題。9/4/20221第一頁，共七十三頁。第7章 循環(huán)網(wǎng)絡(luò)重點(diǎn)Hopfield網(wǎng)絡(luò)實(shí)現(xiàn)的自相聯(lián)存儲(chǔ)根本雙聯(lián)存儲(chǔ)器的結(jié)構(gòu)與訓(xùn)練。難點(diǎn)穩(wěn)定性分析用Hopfield網(wǎng)解決TSP問題 9/4/20222第二頁，共七十三頁。第7章 循環(huán)網(wǎng)絡(luò)7.1 循環(huán)網(wǎng)絡(luò)的組織 7.2 穩(wěn)定性分析 7.3 統(tǒng)計(jì)Hopfield網(wǎng)與Boltzmann機(jī) 7.4 雙聯(lián)存儲(chǔ)器的結(jié)構(gòu) 7.5 異相聯(lián)存儲(chǔ) 7.6 其它的雙聯(lián)存儲(chǔ)器 7

2、.7 Hopfield網(wǎng)用于解決TSP問題 9/4/20223第三頁，共七十三頁。第7章 循環(huán)網(wǎng)絡(luò) 循環(huán)網(wǎng)絡(luò)稱為Hopfield網(wǎng) 循環(huán)網(wǎng)絡(luò)對(duì)輸入信號(hào)的處理是一個(gè)逐漸“修復(fù)、“加強(qiáng)的過程。強(qiáng)烈變化較弱的變化不變化9/4/20224第四頁，共七十三頁。7.1 循環(huán)網(wǎng)絡(luò)的組織 網(wǎng)絡(luò)結(jié)構(gòu)X1Xno1om9/4/20225第五頁，共七十三頁。7.1 循環(huán)網(wǎng)絡(luò)的組織 聯(lián)接：神經(jīng)元之間都是互聯(lián)的wij，每個(gè)神經(jīng)元都沒有到自身的聯(lián)接wii=0。神經(jīng)元個(gè)數(shù)h，輸入向量維數(shù)n，輸出向量維數(shù)m。hn，hm，n1，m1。神經(jīng)元：輸入、輸出、隱藏狀態(tài)變化：非同步、同步輸入向量：X=(x1，x2，xn) 輸出向量：O=

3、(o1，o2，om) 9/4/20226第六頁，共七十三頁。7.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 9/4/202240第四十頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練 Boltzmann機(jī)是多級(jí)循

4、環(huán)網(wǎng)絡(luò)，是Hopfield網(wǎng)的一種擴(kuò)展。神經(jīng)元ANi實(shí)際輸出狀態(tài)oi=1的概率為： T趨近于0時(shí)，神經(jīng)元的狀態(tài)不再具有隨機(jī)性，Boltzmann機(jī)退化成一般Hopfield網(wǎng)。 9/4/202241第四十一頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練 9/4/202242第四十二頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練 9/4/202243第四十三頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練 Boltzmann機(jī)是多級(jí)循環(huán)網(wǎng)絡(luò)，是Hopfield網(wǎng)的一種擴(kuò)展。神經(jīng)元ANi網(wǎng)絡(luò)輸入為： T趨近于0時(shí)，神經(jīng)元的狀態(tài)不再具有隨機(jī)性，Boltzmann機(jī)退化成一般Hopfield網(wǎng)。 9/4/20224

5、4第四十四頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練 神經(jīng)元ANi實(shí)際輸出狀態(tài)oi=1的概率為神經(jīng)元ANi實(shí)際輸出狀態(tài)oi=0的概率為顯然 越大，那么 oi 取1的概率越大9/4/202245第四十五頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練神經(jīng)元ANi在運(yùn)行中狀態(tài)發(fā)生了變化 Boltzmann機(jī)的能量函數(shù)(一致性函數(shù) )9/4/202246第四十六頁，共七十三頁。Boltzmann機(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)

6、該越小。從而，oi=1的概率為： 9/4/202247第四十七頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練處于狀態(tài)a，b的概率Pa和Pb，對(duì)應(yīng)于oi=1和oi=0，其它的神經(jīng)元在a，b狀態(tài)下不變 Pa=pi Pb =1-pi 當(dāng)系統(tǒng)的溫度較低時(shí)，如果EaPb：網(wǎng)絡(luò)處于較低能量狀態(tài)的概率較大 9/4/202248第四十八頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練網(wǎng)絡(luò)進(jìn)行足夠?qū)掖蔚?，處于某狀態(tài)的概率與此狀態(tài)下的能量和此時(shí)系統(tǒng)的溫度有關(guān)。由于高溫時(shí)網(wǎng)絡(luò)的各個(gè)狀態(tài)出現(xiàn)的概率根本相同，這就給它逃離局部極小點(diǎn)提供了時(shí)機(jī)。9/4/202249第四十九頁，共七十三頁。Boltzmann機(jī)的訓(xùn)練1986年，H

7、inton和Sejnowski訓(xùn)練方法自由概率Pij-：沒有輸入時(shí)ANi和ANj同時(shí)處于激發(fā)狀態(tài)的概率。約束概率Pij+：加上輸入后ANi和ANj同時(shí)處于激發(fā)狀態(tài)的概率。聯(lián)接權(quán)修改量：wij=( Pij+ - Pij-) 9/4/202250第五十頁，共七十三頁。算法7-2 Boltzmann機(jī)訓(xùn)練算法 1計(jì)算約束概率 1.1 對(duì)樣本集中每個(gè)樣本，執(zhí)行如下操作： 1.1.1 將樣本加在網(wǎng)絡(luò)上輸入向量及其對(duì)應(yīng)的輸出向量； 1.1.2 讓網(wǎng)絡(luò)尋找平衡； 1.1.3 記錄下所有神經(jīng)元的狀態(tài)； 1.2 計(jì)算對(duì)所有的樣本，ANi和ANj的狀態(tài)同時(shí)為1的概率Pij+；9/4/202251第五十一頁，共七十

8、三頁。算法7-2 Boltzmann機(jī)訓(xùn)練算法 2 計(jì)算自由概率 2.1 從一個(gè)隨機(jī)狀態(tài)開始，不加輸入、輸出，讓網(wǎng)絡(luò)自由運(yùn)行，并且在運(yùn)行過程中屢次紀(jì)錄網(wǎng)絡(luò)的狀態(tài)； 2.2 對(duì)所有的ANi和ANj，計(jì)算它們的狀態(tài)同時(shí)為1的概率Pij-； 3 對(duì)權(quán)矩陣進(jìn)行調(diào)整wij=(Pij+-Pij-)9/4/202252第五十二頁，共七十三頁。7.7 Hopfield網(wǎng)解決TSP問題1985年，J. J. Hopfield和D. W. Tank用循環(huán)網(wǎng)求解TSP。試驗(yàn)說明，當(dāng)城市的個(gè)數(shù)不超過30時(shí)，多可以給出最優(yōu)解的近似解。而當(dāng)城市的個(gè)數(shù)超過30時(shí)，最終的結(jié)果就不太理想了 設(shè)問題中含有n個(gè)城市,用n*n個(gè)神經(jīng)

9、元構(gòu)成網(wǎng)絡(luò) 9/4/202253第五十三頁，共七十三頁。應(yīng)用CHNN網(wǎng)解決優(yōu)化計(jì)算問題 用CHNN網(wǎng)解決優(yōu)化問題一般需要以下幾個(gè)步驟： (1)對(duì)于特定的問題，要選擇一種適宜的表示方法，使得神經(jīng)網(wǎng)絡(luò)的輸出與問題的解相對(duì)應(yīng)； (2)構(gòu)造網(wǎng)絡(luò)能量函數(shù)，使其最小值對(duì)應(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ò)的電子線路并運(yùn)行，其穩(wěn)態(tài)就是在一定條件下的問題優(yōu)化解。也可以編程模擬網(wǎng)絡(luò)的運(yùn)行方式，在計(jì)算機(jī)上實(shí)現(xiàn)。 9/4/202254第五十四頁，共七十三頁。 TSP問題是一個(gè)經(jīng)典的人工智能

10、難題。對(duì)n個(gè)城市而言，可能的路徑總數(shù)為n!2n。隨著n的增加，路徑數(shù)將按指數(shù)率急劇增長(zhǎng)，即所謂“指數(shù)爆炸。當(dāng)n值較大時(shí)，用傳統(tǒng)的數(shù)字計(jì)算機(jī)也無法在有限時(shí)間內(nèi)尋得答案。例如，n50時(shí)，即使用每秒1億次運(yùn)算速度的巨型計(jì)算機(jī)按窮舉搜索法，也需要51048年時(shí)間。即使是n20個(gè)城市，也需求解350年。 1985年Hopfield和Tank兩人用CHNN網(wǎng)絡(luò)為解決TSP難題開辟了一條嶄新的途徑，獲得了巨大的成功。9/4/202255第五十五頁，共七十三頁。 其根本思想是把TSP問題映射到CHNN網(wǎng)絡(luò)中去，并設(shè)法用網(wǎng)絡(luò)能量代表路徑總長(zhǎng)。這樣，當(dāng)網(wǎng)絡(luò)的能量隨著模擬電子線路狀態(tài)的變遷，最終收斂于極小值(或最小

11、值)時(shí)，問題的較佳解(或最佳答案解)便隨之求得。此外，由于模擬電子線路中的全部元件都是并行工作的，所以求解時(shí)間與城市數(shù)的多少無關(guān)，僅是運(yùn)算放大器工作所需的微秒級(jí)時(shí)間，顯著地提高了求解速度，充分展示了神經(jīng)網(wǎng)絡(luò)的巨大優(yōu)越性。9/4/202256第五十六頁，共七十三頁。1TSP問題描述 為使CHNN網(wǎng)絡(luò)完成優(yōu)化計(jì)算，必須找到一種適宜的表示旅行路線的方法。鑒于TSP的解是n個(gè)城市的有序排列，因此可用一個(gè)由nn個(gè)神經(jīng)元構(gòu)成的矩陣(稱為換位陣)來描述旅行路線。圖7.5給出8城市TSP問題中的一條可能的有效路線的換位陣。9/4/202257第五十七頁，共七十三頁。 TSP問題描述 為使CHNN網(wǎng)絡(luò)完成優(yōu)化計(jì)

12、算，必須找到一種適宜的表示旅行路線的方法。鑒于TSP的解是n個(gè)城市的有序排列，因此可用一個(gè)由nn個(gè)神經(jīng)元構(gòu)成的矩陣(稱為換位陣)來描述旅行路線。圖給出8城市TSP問題中的一條可能的有效路線的換位陣。9/4/202258第五十八頁，共七十三頁。 由于每個(gè)城市僅能訪問一次，因此換位陣中每城市行只允許且必須有一個(gè)1，其余元素均為0。為了用神經(jīng)元的狀態(tài)表示某城市在某一有效路線中的位置，采用雙下標(biāo) Yxi，第一個(gè)下標(biāo)x表示城市名，1，2，n；第二個(gè)下標(biāo)i表示該城市在訪問路線中的位置，i1，2，n。例如，Y461表示旅途中第6站應(yīng)訪問城市4；假設(shè)Y460那么表示第6 站訪問的不是城市4，而是其他某個(gè)城市。

13、 圖78中的換位陣所表示的旅行路線為: 425813764，旅行路線總長(zhǎng)為d42+d25+d58+d81+d13+d37+d76+d64。9/4/202259第五十九頁，共七十三頁。7.7 Hopfield網(wǎng)解決TSP問題dxy城市X與城市Y之間的距離；vxi城市X的第i個(gè)神經(jīng)元的狀態(tài)： 1城市X在第i個(gè)被訪問vxi= 0城市X不在第i個(gè)被訪問wxi,yj城市X的第i個(gè)神經(jīng)元到城市Y的第j個(gè)神經(jīng)元的連接權(quán)。 9/4/202260第六十頁，共七十三頁。7.7 Hopfield網(wǎng)用于解決TSP問題例如：四個(gè)城市X、Y、Z、W城市名訪問順序標(biāo)示1234X0100Y0001Z1000W00109/4/

14、202261第六十一頁，共七十三頁。能量函數(shù)設(shè)計(jì) 用CHNN求解TSP問題的關(guān)鍵是構(gòu)造一個(gè)適宜的能量函數(shù)。TSP問題的能量函數(shù)由4局部組成： (1)能量E1城市行約束 當(dāng)每個(gè)城市行中的1不多于一個(gè)時(shí)，應(yīng)有第x行的全部元素vxi按順序兩兩相乘之和為0，即 從而全部n行的所有元素按順序兩兩相乘之和也應(yīng)為零，即=0 9/4/202262第六十二頁，共七十三頁。 按此約束可定義能量E1為 式中A為正常數(shù)。顯然，當(dāng)E10時(shí)可保證對(duì)每個(gè)城市訪問的次數(shù)不超過一次。 (2)能量E2位置列約束 同理，當(dāng)每個(gè)位置列中的1不多于一個(gè)時(shí)，應(yīng)有第i列的全部元素vxi按順序兩兩相乘之和為0，即 因此，全部n列的所有元素按

15、順序兩兩相乘之和也應(yīng)為零，即=09/4/202263第六十三頁，共七十三頁。 按此約束可定義能量E2為 式中B為正常數(shù)。顯然，當(dāng)E20時(shí)就能確保每次訪問的城市數(shù)不超過一個(gè)。 (3)能量E3換位陣全局約束 E10和E20只是換位陣有效的必要條件，但不是充分條件。容易看出，當(dāng)換位陣中各元素均為“0時(shí)，也能滿足El0和E20，但這顯然是無效的。因此，還需引入第三個(gè)約束條件全局約束條件，以確保換位陣中1的數(shù)目等于城市數(shù)n，即9/4/202264第六十四頁，共七十三頁。 因此定義能量E 為 式中C為正常數(shù)。那么E30可保證換位陣中1的數(shù)目正好等于n。 9/4/202265第六十五頁，共七十三頁。 (4)

16、能量E4旅行路線長(zhǎng)度 同時(shí)滿足以上3個(gè)約束條件只能說明路線是有效的，但不一定是最優(yōu)的。依題意，在路線有效的前提下，其總長(zhǎng)度應(yīng)最短。為此在能量函數(shù)中尚須引入一個(gè)能反映路線總長(zhǎng)度的分量E4，其定義式要能保證E4隨路線總長(zhǎng)度的縮短而減小。為設(shè)計(jì)E4，設(shè)任意兩城市x與y間的距離為dxy 。訪問這兩個(gè)城市有兩種途徑，從x到y(tǒng)，相應(yīng)的表達(dá)式為 dxy(vxi ,vy,i+1)；從y到x，那么相應(yīng)的表達(dá)式為dyx(vxi ,vy,i1) 。如果城市x和y在旅行順序中相鄰，那么當(dāng) (vxi ,vy,i+1) 1時(shí)，必有 (vxi ,vy,i1) 0；反之亦然。因此，有dxy(vxi,vy,i1) (vxi,v

17、y,i1dxy。假設(shè)定義n個(gè)城市各種可能的旅行路線長(zhǎng)度為9/4/202266第六十六頁，共七十三頁。 式中D為正常數(shù)，當(dāng)E4最小時(shí)旅行路線最短。 綜合以上4項(xiàng)能量，可得TSP問題的能量函數(shù)如下：(6.30)9/4/202267第六十七頁，共七十三頁。網(wǎng)絡(luò)的能量函數(shù)9/4/202268第六十八頁，共七十三頁。7.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 9/4/202269第六十九頁，共七十三頁。 圖給出用CHNN網(wǎng)解決10城市TSP問題的結(jié)果。圖 (a)為最優(yōu)解，圖 (b)為較佳解。9/4/202270第七十頁，共七十三頁。 按照窮舉法，我國(guó)31個(gè)(尚未計(jì)入香港特區(qū))直轄市、省會(huì)和自治區(qū)首府的巡回路徑應(yīng)有約1.3261032種。我國(guó)學(xué)者對(duì)中國(guó)旅行商CTSP(Chinese TSP)問題進(jìn)行了大量的研究，最新成果已到達(dá)15 449km。所得最短巡回路徑為17102km。采用Hopfi