第7章

循環網絡主要內容Hopfield網絡實現的自相聯存儲穩定性分析統計Hopfield網與Boltzmann機根本雙聯存儲器(BAM)的結構與訓練幾種相聯存儲網絡用Hopfield網解決TSP問題。6/1/20251第一頁，共七十三頁。第7章

循環網絡重點Hopfield網絡實現的自相聯存儲根本雙聯存儲器的結構與訓練。難點穩定性分析用Hopfield網解決TSP問題6/1/20252第二頁，共七十三頁。第7章

循環網絡7.1循環網絡的組織

7.2穩定性分析

7.3統計Hopfield網與Boltzmann機

7.4雙聯存儲器的結構

7.5異相聯存儲

7.6其它的雙聯存儲器

7.7Hopfield網用于解決TSP問題

6/1/20253第三頁，共七十三頁。第7章

循環網絡

循環網絡稱為Hopfield網

循環網絡對輸入信號的處理是一個逐漸“修復〞、“加強〞的過程。強烈變化較弱的變化不變化6/1/20254第四頁，共七十三頁。7.1循環網絡的組織網絡結構

X1Xno1om………………6/1/20255第五頁，共七十三頁。7.1循環網絡的組織聯接：神經元之間都是互聯的wij，每個神經元都沒有到自身的聯接wii=0。神經元個數h，輸入向量維數n，輸出向量維數m。h≥n，h≥m，n≥1，m≥1。神經元：輸入、輸出、隱藏狀態變化：非同步、同步輸入向量：X=(x1，x2，…，xn)輸出向量：O=(o1，o2，…，om)

6/1/20256第六頁，共七十三頁。7.1循環網絡的組織神經元的網絡輸入：

閾值函數：oj=1 ifnetj>θj0 ifnetj<θj

oj ifnetj=θj6/1/20257第七頁，共七十三頁。最根本的Hopfield網o1ono2x2x1xnW……n=m=h 6/1/20258第八頁，共七十三頁。最根本的Hopfield網希望網絡的聯接矩陣存放的是一組這樣的樣本，在聯想過程中實現對信息的“修復〞和“加強〞，要求：它的輸入向量和輸出向量是相同的向量，即，X=Y樣本集：S={Y1，Y2，…，Ys}6/1/20259第九頁，共七十三頁。最根本的Hopfield網

wii=0 1≤i≤nW是一個對角線元素為0的對稱矩陣： W=Y1T╳Y1+Y2T╳Y2+…+YsT╳Ys-W0W是各個樣本向量自身的外積的和——網絡實現的是自相聯映射。

權矩陣：wij=i≠j6/1/202510第十頁，共七十三頁。最根本的Hopfield網6/1/202511第十一頁，共七十三頁。6/1/202512第十二頁，共七十三頁。由式7一3知，對任意的i和j(i≠j),所以，W是一個對角線元素為0的對稱矩陣。與前面遇到過的訓練方法不同，在這里是根據樣本集直接地計算出網絡的聯接矩陣。顯然，這種訓練方法效率要高許多。另外，由于W是各個樣本向量自身的外積的和，所以，有時稱該網絡實現的是自相聯映射。6/1/202513第十三頁，共七十三頁。最根本的Hopfield網激活函數： 改為S形函數后，系統就成為一個連續系統多級循環網絡 除輸出向量被反響到輸入層外，其它各層之間的信號傳送均執行如下規定：第i-1層神經元的輸出經過第i個連接矩陣被送入第i層。 一般不考慮越層的信號傳送、中間的信號反響和同層的神經元之間進行信號的直接傳送6/1/202514第十四頁，共七十三頁。

網絡的異步工作方式

網絡的異步工作方式是一種串行方式。網絡運行時每次只有一個神經元i按下式進行狀態的調整計算，其他神經元的狀態均保持不變，即6/1/202515第十五頁，共七十三頁。神經元狀態的調整次序可以按某種規定的次序進行，也可以隨機選定。每次神經元在調整狀態時，根據其當前凈輸入值的正負決定下一時刻的狀態，因此其狀態可能會發生變化，也可能保持原狀。下次調整其他神經元狀態時，本次的調整結果即在下一個神經元的凈輸入中發揮作用。

網絡的同步工作方式

網絡的同步工作方式是一種并行方式，所有神經元同時調整狀態，即xj(t+1)＝sgn[netj(t)]j＝1，2,…,n6/1/202516第十六頁，共七十三頁。7.2穩定性分析網絡的穩定性是與收斂性不同的問題Cohen和Grossberg[1983年]:Hopfield網絡的穩定性定理如果Hopfield網絡的聯接權矩陣是對角線為0的對稱矩陣，那么它是穩定的用著名的Lyapunov函數作為Hopfield網絡的能量函數網絡的穩定性與吸引子6/1/202517第十七頁，共七十三頁。反響網絡是一種能存儲假設干個預先設置的穩定點(狀態)的網絡。運行時，當向該網絡作用一個起原始推動作用的初始輸入模式后，網絡便將其輸出反響回來作為下次的輸入。經假設干次循環(迭代)之后，在網絡結構滿足一定條件的前提下，網絡最終將會穩定在某一預先設定的穩定點。設X(0)為網絡的初始激活向量，它僅在初始瞬間t＝0時作用于網絡，起原始推動作用。X(0)移去之后，網絡處于自激狀態，即由反響回來的向量X(1)作為下一次的輸入取而代之。反響網絡作為非線性動力學系統，具有豐富的動態特性，如穩定性、有限環狀態和混沌(chaos)狀態等。

6/1/202518第十八頁，共七十三頁。1．網絡的穩定性由網絡工作狀態的分析可知，DHNN網實質上是一個離散的非線性動力學系統。網絡從初態X(0)開始，假設能經有限次遞歸后，其狀態不再發生變化，即X(t+1)＝X(t)，那么稱該網絡是穩定的6/1/202519第十九頁，共七十三頁。如果網絡是穩定的，它可以從任一初態收斂到一個穩態，如圖6．2(a)所示；假設網絡是不穩定的，由于DHNN網每個節點的狀態只有1和-l兩種情況，網絡不可能出現無限發散的情況，而只可能出現限幅的自持振蕩，這種網絡稱為有限環網絡，圖6．2(b)給出了它的相圖。如果網絡狀態的軌跡在某個確定的范圍內變遷，但既不重復也不停止，狀態變化為無窮多個，軌跡也不發散到無窮遠，這種現象稱為混沌，其相圖如圖6．2(c)所示。對于DHNN網，由于網絡的狀態是有限的，因此不可能出現混沌現象。6/1/202520第二十頁，共七十三頁。網絡的穩定性與下面將要介紹的能量函數密切相關，利用網絡的能量函數可實現優化求解功能。網絡的能量函數在網絡狀態按一定規那么變化時，能自動趨向能量的極小點。如果把一個待求解問題的目標函數以網絡能量函數的形式表達出來，當能量函數趨于最小時，對應的網絡狀態就是問題的最優解。網絡的初態可視為問題的初始解，而網絡從初態向穩態的收斂過程便是優化計算過程，這種尋優搜索是在網絡演變過程中自動完成的。6/1/202521第二十一頁，共七十三頁。2．吸引子與能量函數網絡到達穩定時的狀態X，稱為網絡的吸引子。一個動力學系統的最終行為是由它的吸引子決定的，吸引子的存在為信息的分布存儲記憶和神經優化計算提供了根底。如果把吸引子視為問題的解，那么從初態朝吸引子演變的過程便是求解計算的過程。假設把需記憶的樣本信息存儲于網絡不同的吸引子，當輸入含有局部記憶信息的樣本時，網絡的演變過程便是從局部信息尋找全部信息，即聯想回憶的過程。

6/1/202522第二十二頁，共七十三頁。下面給出DHNN網吸引子的定義和定理。定義7．1假設網絡的狀態X滿足X＝f(WX—T)，那么稱X為網絡的吸引子。

能使網絡穩定在同一吸引子的所有初態的集合，稱為該吸引子的吸引域。下面給出關于吸引域的兩個定義。定義7．2假設Xa是吸引子，對于異步方式，假設存在一個調整次序，使網絡可以從狀態X演變到Xa，那么稱X弱吸引到Xa；假設對于任意調整次序，網絡都可以從狀態X演變到Xa，那么稱X強吸引到Xa。6/1/202523第二十三頁，共七十三頁。定義7．3假設對某些X，有X弱吸引到吸引子Xa，那么稱這些X的集合為Xa的弱吸引域；假設對某些X，有X強吸引到吸引子Xa，那么稱這些X的集合為Xa的強吸引域。欲使反響網絡具有聯想能力，每個吸引子都應該具有一定的吸引域。只有這樣，對于帶有一定噪聲或缺損的初始樣本，網絡才能經過動態演變而穩定到某一吸引子狀態，從而實現正確聯想。反響網絡設計的目的就是要使網絡能落到期望的穩定點(問題的解)上，并且還要具有盡可能大的吸引域，以增強聯想功能。6/1/202524第二十四頁，共七十三頁。例6．2有一DHNN網，n＝4，Tj＝0，j＝l，2，3，4，向量Xa、Xb和權值矩陣W分別為檢驗Xa和Xb是否為網絡的吸引子，并考察其是否具有聯想記憶能力。6/1/202525第二十五頁，共七十三頁。解本例要求驗證吸引子和檢查吸引域，下面分兩步進行。①檢驗吸引子

由吸引子定義6/1/202526第二十六頁，共七十三頁。所以Xa是網絡的吸引子，因為Xb＝－Xa，由吸引子的性質1知，Xb也是網絡的吸引子。②考察聯想記憶能力設有樣本Xl＝(－1，1，1，1)T、X2＝(1，－1，－1，－1)T、X3＝(1，1，－1，－1)T，試考察網絡以異步方式工作時兩個吸引子對3個樣本的吸引能力。令網絡初態X(0)＝X1＝(－1，1，1，1)T。設神經元狀態調整次序為1→2→3→4，有X(0)＝(－1，1，1，1)T→X(1)＝(1，1，1，1)T＝Xa可以看出該樣本比較接近吸引子Xa，事實上只按異步方式調整了一步，樣本X1即收斂于Xa。6/1/202527第二十七頁，共七十三頁。令網絡初態X(0)＝X2＝(1，－1，－1，－1)T。設神經元狀態調整次序為1→2→3→4，有X(0)＝(1,－1,－1,－1)T→X(1)＝(－1,－1,－1,－1)T＝Xb可以看出樣本X2比較接近吸引子Xb，按異步方式調整一步后，樣本X2收斂于Xb。令網絡初態X(0)＝X3＝(1,1,－1,－1)T，它與兩個吸引子的海明距離相等。假設設神經元狀態調整次序為1→2→3→4，有X(0)＝(1,1,－1,－1)T→X(1)＝(－1,1,－1,－1)T→X(2)＝(－l,－1,－l,－1)T＝Xb

6/1/202528第二十八頁，共七十三頁。假設將神經元狀態調整次序改為3→4→1→2，那么有X(0)=(1,1,－1,－1)T→X(1)＝(1,1,1,－1)T→X(2)＝(1,1,l,1)T＝Xa從本例可以看出，當網絡的異步調整次序一定時，最終穩定于哪個吸引子與其初態有關；而對于確定的初態，網絡最終穩定于哪個吸引子與其異步調整次序有關。

6/1/202529第二十九頁，共七十三頁。定理7．1對于DHNN網，假設按異步方式調整網絡狀態，且連接權矩陣W為對稱陣，那么對于任意初態，網絡都最終收斂到一個吸引子。下面通過對能量函數的分析對定理7．1進行證明。

定義網絡的能量函數為：6/1/202530第三十頁，共七十三頁。6/1/202531第三十一頁，共七十三頁。6/1/202532第三十二頁，共七十三頁。Lyapunov函數——能量函數作為網絡的穩定性度量wijoioj：網絡的一致性測度。xjoj：神經元的輸入和輸出的一致性測度。θjoj：神經元自身的穩定性的測度。

6/1/202533第三十三頁，共七十三頁。當ANk的狀態從ok變成ok′1、ANk是輸入神經元

6/1/202534第三十四頁，共七十三頁。當ANk的狀態從ok變成ok′wkk=06/1/202535第三十五頁，共七十三頁。ΔΕ=-(netk-θk)ΔokANk狀態的變化：Δok=(ok′-ok)Δok=0，ΔΕ=0Δok>0，ok′=1&ok=0，ok由0變到1，netk>θk，netk-θk>0所以，-(netk-θk)Δok<0故ΔΕ<0結論：網絡的目標函數總是下降Δok<0,ok′=0&ok=1，ok由1變到0netk<θk，netk-θk<0-(netk-θk)Δok<0故ΔΕ<06/1/202536第三十六頁，共七十三頁。當ANk的狀態從ok變成ok′2、ANk不是輸入神經元

6/1/202537第三十七頁，共七十三頁。當ANk的狀態從ok變成ok′無論ANk的狀態是如何變化的，總有ΔΕ≤0

6/1/202538第三十八頁，共七十三頁。7.3統計Hopfield網與Boltzmann機統計Hopfield網在網絡運行中，神經元狀態與“人工溫度〞確定的概率相關網絡運行模擬金屬退火過程pi：ANi的狀態取1的概率neti：ANi所獲網絡輸入；θi：ANi的閾值；T：系統的人工溫度。

6/1/202539第三十九頁，共七十三頁。算法7-1統計Hopfield網運行算法

1

取一個很大的值作為人工溫度T的初值；2

對網絡中每一個神經元ANi，2.1

按照相應式子計算相應的概率pi；2.2

按照均勻分布，在[0，1]中取一個隨機數r；2.3

如果pi>r那么使ANi的狀態為1， 否那么使ANi的狀態為0；3逐漸降低溫度T，如果溫度足夠低，那么算法結束。否那么，重復26/1/202540第四十頁，共七十三頁。Boltzmann機的訓練

Boltzmann機是多級循環網絡，是Hopfield網的一種擴展。神經元ANi實際輸出狀態oi=1的概率為：

T趨近于0時，神經元的狀態不再具有隨機性，Boltzmann機退化成一般Hopfield網。6/1/202541第四十一頁，共七十三頁。Boltzmann機的訓練

6/1/202542第四十二頁，共七十三頁。Boltzmann機的訓練

6/1/202543第四十三頁，共七十三頁。Boltzmann機的訓練

Boltzmann機是多級循環網絡，是Hopfield網的一種擴展。神經元ANi網絡輸入為：

T趨近于0時，神經元的狀態不再具有隨機性，Boltzmann機退化成一般Hopfield網。6/1/202544第四十四頁，共七十三頁。Boltzmann機的訓練

神經元ANi實際輸出狀態oi=1的概率為神經元ANi實際輸出狀態oi=0的概率為顯然越大，那么oi取1的概率越大6/1/202545第四十五頁，共七十三頁。Boltzmann機的訓練神經元ANi在運行中狀態發生了變化

Boltzmann機的能量函數(一致性函數)6/1/202546第四十六頁，共七十三頁。Boltzmann機的訓練如果ΔΕi>0，神經元ANi處于狀態1的概率就應該越大，否那么，神經元ANi處于狀態0的概就應該越大。ΔΕi的值越大，神經元ANi應該處于狀態1的概率就應該越大。反之，ΔΕi的值越小，神經元ANi應該處于狀態1的概率就應該越小。從而，oi=1的概率為：6/1/202547第四十七頁，共七十三頁。Boltzmann機的訓練處于狀態a，b的概率Pa和Pb，對應于oi=1和oi=0，其它的神經元在a，b狀態下不變Pa=γpiPb=γ〔1-pi〕當系統的溫度較低時，如果Ea<Eb，那么Pa>Pb：網絡處于較低能量狀態的概率較大6/1/202548第四十八頁，共七十三頁。Boltzmann機的訓練網絡進行足夠屢次迭代后，處于某狀態的概率與此狀態下的能量和此時系統的溫度有關。由于高溫時網絡的各個狀態出現的概率根本相同，這就給它逃離局部極小點提供了時機。6/1/202549第四十九頁，共七十三頁。Boltzmann機的訓練1986年，Hinton和Sejnowski訓練方法自由概率Pij-：沒有輸入時ANi和ANj同時處于激發狀態的概率。約束概率Pij+：加上輸入后ANi和ANj同時處于激發狀態的概率。聯接權修改量：Δwij=α(Pij+-Pij-)

6/1/202550第五十頁，共七十三頁。算法7-2Boltzmann機訓練算法1

計算約束概率1.1對樣本集中每個樣本，執行如下操作：1.1.1將樣本加在網絡上〔輸入向量及其對應的輸出向量〕；1.1.2讓網絡尋找平衡；1.1.3記錄下所有神經元的狀態；1.2計算對所有的樣本，ANi和ANj的狀態同時為1的概率Pij+；6/1/202551第五十一頁，共七十三頁。算法7-2Boltzmann機訓練算法2

計算自由概率2.1從一個隨機狀態開始，不加輸入、輸出，讓網絡自由運行，并且在運行過程中屢次紀錄網絡的狀態；2.2對所有的ANi和ANj，計算它們的狀態同時為1的概率Pij-；3

對權矩陣進行調整Δwij=α(Pij+-Pij-)6/1/202552第五十二頁，共七十三頁。7.7Hopfield網解決TSP問題1985年，J.J.Hopfield和D.W.Tank用循環網求解TSP。試驗說明，當城市的個數不超過30時，多可以給出最優解的近似解。而當城市的個數超過30時，最終的結果就不太理想了設問題中含有n個城市,用n*n個神經元構成網絡6/1/202553第五十三頁，共七十三頁。

應用CHNN網解決優化計算問題用CHNN網解決優化問題一般需要以下幾個步驟：(1)對于特定的問題，要選擇一種適宜的表示方法，使得神經網絡的輸出與問題的解相對應；(2)構造網絡能量函數，使其最小值對應于問題的最佳答案解；(3)將能量函數與Lyapunov函數標準形式進行比較，可推出神經網絡的權值與偏流的表達式，從而確定了網絡的結構；

(4)由網絡結構建立網絡的電子線路并運行，其穩態就是在一定條件下的問題優化解。也可以編程模擬網絡的運行方式，在計算機上實現。

6/1/202554第五十四頁，共七十三頁。

TSP問題是一個經典的人工智能難題。對n個城市而言，可能的路徑總數為n!／2n。隨著n的增加，路徑數將按指數率急劇增長，即所謂“指數爆炸〞。當n值較大時，用傳統的數字計算機也無法在有限時間內尋得答案。例如，n＝50時，即使用每秒1億次運算速度的巨型計算機按窮舉搜索法，也需要5×1048年時間。即使是n＝20個城市，也需求解350年。

1985年Hopfield和Tank兩人用CHNN網絡為解決TSP難題開辟了一條嶄新的途徑，獲得了巨大的成功。6/1/202555第五十五頁，共七十三頁。其根本思想是把TSP問題映射到CHNN網絡中去，并設法用網絡能量代表路徑總長。這樣，當網絡的能量隨著模擬電子線路狀態的變遷，最終收斂于極小值(或最小值)時，問題的較佳解(或最佳答案解)便隨之求得。此外，由于模擬電子線路中的全部元件都是并行工作的，所以求解時間與城市數的多少無關，僅是運算放大器工作所需的微秒級時間，顯著地提高了求解速度，充分展示了神經網絡的巨大優越性。

6/1/202556第五十六頁，共七十三頁。1．TSP問題描述為使CHNN網絡完成優化計算，必須找到一種適宜的表示旅行路線的方法。鑒于TSP的解是n個城市的有序排列，因此可用一個由n×n個神經元構成的矩陣(稱為換位陣)來描述旅行路線。圖7.5給出8城市TSP問題中的一條可能的有效路線的換位陣。

6/1/202557第五十七頁，共七十三頁。

TSP問題描述為使CHNN網絡完成優化計算，必須找到一種適宜的表示旅行路線的方法。鑒于TSP的解是n個城市的有序排列，因此可用一個由n×n個神經元構成的矩陣(稱為換位陣)來描述旅行路線。圖給出8城市TSP問題中的一條可能的有效路線的換位陣。

6/1/202558第五十八頁，共七十三頁。由于每個城市僅能訪問一次，因此換位陣中每城市行只允許且必須有一個1，其余元素均為0。為了用神經元的狀態表示某城市在某一有效路線中的位置，采用雙下標Yxi，第一個下標x表示城市名，χ＝1，2，…，n；第二個下標i表示該城市在訪問路線中的位置，i＝1，2，…，n。例如，Y46＝1表示旅途中第6站應訪問城市4；假設Y46＝0那么表示第6站訪問的不是城市4，而是其他某個城市。圖7．8中的換位陣所表示的旅行路線為:4→2→5→8→1→3→7→6→4，旅行路線總長為d42+d25+d58+d81+d13+d37+d76+d64。6/1/202559第五十九頁，共七十三頁。7.7Hopfield網解決TSP問題dxy——城市X與城市Y之間的距離；vxi——城市X的第i個神經元的狀態：

1 城市X在第i個被訪問 vxi= 0 城市X不在第i個被訪問wxi,yj——城市X的第i個神經元到城市Y的第j個神經元的連接權。

6/1/202560第六十頁，共七十三頁。7.7Hopfield網用于解決TSP問題例如：四個城市X、Y、Z、W城市名訪問順序標示1234X0100Y0001Z1000W00106/1/202561第六十一頁，共七十三頁。能量函數設計用CHNN求解TSP問題的關鍵是構造一個適宜的能量函數。TSP問題的能量函數由4局部組成：(1)能量E1———城市行約束當每個城市行中的1不多于一個時，應有第x行的全部元素vxi按順序兩兩相乘之和為0，即從而全部n行的所有元素按順序兩兩相乘之和也應為零，即=0

6/1/202562第六十二頁，共七十三頁。按此約束可定義能量E1為式中A為正常數。顯然，當E1＝0時可保證對每個城市訪問的次數不超過一次。(2)能量E2———位置列約束同理，當每個位置列中的1不多于一個時，應有第i列的全部元素vxi按順序兩兩相乘之和為0，即因此，全部n列的所有元素按順序兩兩相乘之和也應為零，即=06/1/202563第六十三頁，共七十三頁。按此約束可定義能量E2為式中B為正常數。顯然，當E2＝0時就能確保每次訪問的城市數不超過一個。(3)能量E3—換位陣全局約束E1＝0和E2＝0只是換位陣有效的必要條件，但不是充分條件。容易看出，當換位陣中各元素均為“0〞時，也能滿足El＝0和E2＝0，但這顯然是無效的。因此，還需引入第三個約束條件——全局約束條件，以確保換位陣中1的數目等于城市數n，即6/1/202564第六十四頁，共七十三頁。因此定義能