1、第7章 循環網絡主要內容Hopfield網絡實現的自相聯存儲穩定性分析統計Hopfield網與Boltzmann機根本雙聯存儲器(BAM)的結構與訓練幾種相聯存儲網絡用Hopfield網解決TSP問題。9/4/20221第一頁，共七十三頁。第7章 循環網絡重點Hopfield網絡實現的自相聯存儲根本雙聯存儲器的結構與訓練。難點穩定性分析用Hopfield網解決TSP問題 9/4/20222第二頁，共七十三頁。第7章 循環網絡7.1 循環網絡的組織 7.2 穩定性分析 7.3 統計Hopfield網與Boltzmann機 7.4 雙聯存儲器的結構 7.5 異相聯存儲 7.6 其它的雙聯存儲器 7

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

3、(o1，o2，om) 9/4/20226第六頁，共七十三頁。7.1 循環網絡的組織神經元的網絡輸入： 閾值函數：oj=1if netjj0if netj0，ok=1& ok=0，ok由0變到1，netkk，netk-k0所以，-(netk-k)ok0故0結論：網絡的目標函數總是下降ok0, ok=0& ok=1，ok由1變到0netkk，netk-k0-(netk-k)ok0故r 那么使ANi的狀態為1， 否那么使ANi的狀態為0；3 逐漸降低溫度T，如果溫度足夠低，那么算法結束。否那么，重復2 9/4/202240第四十頁，共七十三頁。Boltzmann機的訓練 Boltzmann機是多級循

4、環網絡，是Hopfield網的一種擴展。神經元ANi實際輸出狀態oi=1的概率為： T趨近于0時，神經元的狀態不再具有隨機性，Boltzmann機退化成一般Hopfield網。 9/4/202241第四十一頁，共七十三頁。Boltzmann機的訓練 9/4/202242第四十二頁，共七十三頁。Boltzmann機的訓練 9/4/202243第四十三頁，共七十三頁。Boltzmann機的訓練 Boltzmann機是多級循環網絡，是Hopfield網的一種擴展。神經元ANi網絡輸入為： T趨近于0時，神經元的狀態不再具有隨機性，Boltzmann機退化成一般Hopfield網。 9/4/20224

5、4第四十四頁，共七十三頁。Boltzmann機的訓練 神經元ANi實際輸出狀態oi=1的概率為神經元ANi實際輸出狀態oi=0的概率為顯然 越大，那么 oi 取1的概率越大9/4/202245第四十五頁，共七十三頁。Boltzmann機的訓練神經元ANi在運行中狀態發生了變化 Boltzmann機的能量函數(一致性函數 )9/4/202246第四十六頁，共七十三頁。Boltzmann機的訓練如果i0，神經元ANi處于狀態1的概率就應該越大，否那么，神經元ANi處于狀態0的概就應該越大。i的值越大，神經元ANi應該處于狀態1的概率就應該越大。反之，i的值越小，神經元ANi應該處于狀態1的概率就應

6、該越小。從而，oi=1的概率為： 9/4/202247第四十七頁，共七十三頁。Boltzmann機的訓練處于狀態a，b的概率Pa和Pb，對應于oi=1和oi=0，其它的神經元在a，b狀態下不變 Pa=pi Pb =1-pi 當系統的溫度較低時，如果EaPb：網絡處于較低能量狀態的概率較大 9/4/202248第四十八頁，共七十三頁。Boltzmann機的訓練網絡進行足夠屢次迭代后，處于某狀態的概率與此狀態下的能量和此時系統的溫度有關。由于高溫時網絡的各個狀態出現的概率根本相同，這就給它逃離局部極小點提供了時機。9/4/202249第四十九頁，共七十三頁。Boltzmann機的訓練1986年，H

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

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

9、元構成網絡 9/4/202253第五十三頁，共七十三頁。應用CHNN網解決優化計算問題 用CHNN網解決優化問題一般需要以下幾個步驟： (1)對于特定的問題，要選擇一種適宜的表示方法，使得神經網絡的輸出與問題的解相對應； (2)構造網絡能量函數，使其最小值對應于問題的最佳答案解； (3)將能量函數與Lyapunov函數標準形式進行比較，可推出神經網絡的權值與偏流的表達式，從而確定了網絡的結構； (4)由網絡結構建立網絡的電子線路并運行，其穩態就是在一定條件下的問題優化解。也可以編程模擬網絡的運行方式，在計算機上實現。 9/4/202254第五十四頁，共七十三頁。 TSP問題是一個經典的人工智能

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

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

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

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

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

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

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

17、y,i1dxy。假設定義n個城市各種可能的旅行路線長度為9/4/202266第六十六頁，共七十三頁。 式中D為正常數，當E4最小時旅行路線最短。 綜合以上4項能量，可得TSP問題的能量函數如下：(6.30)9/4/202267第六十七頁，共七十三頁。網絡的能量函數9/4/202268第六十八頁，共七十三頁。7.7 Hopfield網用于解決TSP問題 聯接矩陣 wxi,yj= -Axy(1-ij) Bij(1-xy) C dxy(ji+1+ji-1) 1如果i=jij= 0如果ij 9/4/202269第六十九頁，共七十三頁。 圖給出用CHNN網解決10城市TSP問題的結果。圖 (a)為最優解，圖 (b)為較佳解。9/4/202270第七十頁，共七十三頁。 按照窮舉法，我國31個(尚未計入香港特區)直轄市、省會和自治區首府的巡回路徑應有約1.3261032種。我國學者對中國旅行商CTSP(Chinese TSP)問題進行了大量的研究，最新成果已到達15 449km。所得最短巡回路徑為17102km。采用Hopfi