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

第7章

循環(huán)網(wǎng)絡主要內容Hopfield網(wǎng)絡實現(xiàn)的自相聯(lián)存儲穩(wěn)定性分析統(tǒng)計Hopfield網(wǎng)與Boltzmann機基本雙聯(lián)存儲器(BAM)的結構與訓練幾種相聯(lián)存儲網(wǎng)絡用Hopfield網(wǎng)解決TSP問題。7/27/20231第7章循環(huán)網(wǎng)絡主要內容7/26/20231第7章

循環(huán)網(wǎng)絡重點Hopfield網(wǎng)絡實現(xiàn)的自相聯(lián)存儲基本雙聯(lián)存儲器的結構與訓練。難點穩(wěn)定性分析用Hopfield網(wǎng)解決TSP問題

7/27/20232第7章循環(huán)網(wǎng)絡重點7/26/20232第7章

循環(huán)網(wǎng)絡7.1循環(huán)網(wǎng)絡的組織

7.2穩(wěn)定性分析

7.3統(tǒng)計Hopfield網(wǎng)與Boltzmann機

7.4雙聯(lián)存儲器的結構

7.5異相聯(lián)存儲

7.6其它的雙聯(lián)存儲器

7.7Hopfield網(wǎng)用于解決TSP問題

7/27/20233第7章循環(huán)網(wǎng)絡7.1循環(huán)網(wǎng)絡的組織7/26/2023第7章

循環(huán)網(wǎng)絡

循環(huán)網(wǎng)絡稱為Hopfield網(wǎng)

循環(huán)網(wǎng)絡對輸入信號的處理是一個逐漸“修復”、“加強”的過程。強烈變化較弱的變化不變化7/27/20234第7章循環(huán)網(wǎng)絡循環(huán)網(wǎng)絡稱為Hopfield網(wǎng)循環(huán)7.1循環(huán)網(wǎng)絡的組織網(wǎng)絡結構

X1Xno1om………………7/27/202357.1循環(huán)網(wǎng)絡的組織網(wǎng)絡結構

X1Xno1om…………7.1循環(huán)網(wǎng)絡的組織聯(lián)接：神經(jīng)元之間都是互聯(lián)的wij，每個神經(jīng)元都沒有到自身的聯(lián)接wii=0。神經(jīng)元個數(shù)h，輸入向量維數(shù)n，輸出向量維數(shù)m。h≥n，h≥m，n≥1，m≥1。神經(jīng)元：輸入、輸出、隱藏狀態(tài)變化：非同步、同步輸入向量：X=(x1，x2，…，xn)輸出向量：O=(o1，o2，…，om)

7/27/202367.1循環(huán)網(wǎng)絡的組織聯(lián)接：神經(jīng)元之間都是互聯(lián)的wij，7.1循環(huán)網(wǎng)絡的組織神經(jīng)元的網(wǎng)絡輸入：

閾值函數(shù)：oj=1 ifnetj>θj0 ifnetj<θj

oj ifnetj=θj7/27/202377.1循環(huán)網(wǎng)絡的組織神經(jīng)元的網(wǎng)絡輸入：閾值函數(shù)：oj=最基本的Hopfield網(wǎng)

o1ono2x2x1xnW……n=m=h 7/27/20238最基本的Hopfield網(wǎng)o1ono2x2x1xnW……n最基本的Hopfield網(wǎng)希望網(wǎng)絡的聯(lián)接矩陣存放的是一組這樣的樣本，在聯(lián)想過程中實現(xiàn)對信息的“修復”和“加強”，要求：它的輸入向量和輸出向量是相同的向量，即，X=Y

樣本集：S={Y1，Y2，…，Ys}

7/27/20239最基本的Hopfield網(wǎng)希望網(wǎng)絡的聯(lián)接矩陣存放的是一組這樣最基本的Hopfield網(wǎng)

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

權矩陣：wij=i≠j7/27/202310最基本的Hopfield網(wǎng) wii=0 1≤i≤n最基本的Hopfield網(wǎng)7/27/202311最基本的Hopfield網(wǎng)7/26/2023117/27/2023127/26/202312由式7一3知，對任意的i和j(i≠j),所以，W是一個對角線元素為0的對稱矩陣。與前面遇到過的訓練方法不同，在這里是根據(jù)樣本集直接地計算出網(wǎng)絡的聯(lián)接矩陣。顯然，這種訓練方法效率要高許多。另外，由于W是各個樣本向量自身的外積的和，所以，有時稱該網(wǎng)絡實現(xiàn)的是自相聯(lián)映射。7/27/202313由式7一3知，對任意的i和j(i≠j),所以，W是一個對角線最基本的Hopfield網(wǎng)激活函數(shù)： 改為S形函數(shù)后，系統(tǒng)就成為一個連續(xù)系統(tǒng)

多級循環(huán)網(wǎng)絡 除輸出向量被反饋到輸入層外，其它各層之間的信號傳送均執(zhí)行如下規(guī)定：第i-1層神經(jīng)元的輸出經(jīng)過第i個連接矩陣被送入第i層。 一般不考慮越層的信號傳送、中間的信號反饋和同層的神經(jīng)元之間進行信號的直接傳送

7/27/202314最基本的Hopfield網(wǎng)激活函數(shù)：7/26/202314

網(wǎng)絡的異步工作方式

網(wǎng)絡的異步工作方式是一種串行方式。網(wǎng)絡運行時每次只有一個神經(jīng)元i按下式進行狀態(tài)的調整計算，其他神經(jīng)元的狀態(tài)均保持不變，即7/27/202315網(wǎng)絡的異步工作方式7/26/202315神經(jīng)元狀態(tài)的調整次序可以按某種規(guī)定的次序進行，也可以隨機選定。每次神經(jīng)元在調整狀態(tài)時，根據(jù)其當前凈輸入值的正負決定下一時刻的狀態(tài)，因此其狀態(tài)可能會發(fā)生變化，也可能保持原狀。下次調整其他神經(jīng)元狀態(tài)時，本次的調整結果即在下一個神經(jīng)元的凈輸入中發(fā)揮作用。

網(wǎng)絡的同步工作方式

網(wǎng)絡的同步工作方式是一種并行方式，所有神經(jīng)元同時調整狀態(tài)，即xj(t+1)＝sgn[netj(t)]j＝1，2,…,n7/27/202316神經(jīng)元狀態(tài)的調整次序可以按某種規(guī)定的次序進行7.2穩(wěn)定性分析網(wǎng)絡的穩(wěn)定性是與收斂性不同的問題

Cohen和Grossberg[1983年]:Hopfield網(wǎng)絡的穩(wěn)定性定理

如果Hopfield網(wǎng)絡的聯(lián)接權矩陣是對角線為0的對稱矩陣，則它是穩(wěn)定的

用著名的Lyapunov函數(shù)作為Hopfield網(wǎng)絡的能量函數(shù)

網(wǎng)絡的穩(wěn)定性與吸引子7/27/2023177.2穩(wěn)定性分析網(wǎng)絡的穩(wěn)定性是與收斂性不同的問題7/反饋網(wǎng)絡是一種能存儲若干個預先設置的穩(wěn)定點(狀態(tài))的網(wǎng)絡。運行時，當向該網(wǎng)絡作用一個起原始推動作用的初始輸入模式后，網(wǎng)絡便將其輸出反饋回來作為下次的輸入。經(jīng)若干次循環(huán)(迭代)之后，在網(wǎng)絡結構滿足一定條件的前提下，網(wǎng)絡最終將會穩(wěn)定在某一預先設定的穩(wěn)定點。設X(0)為網(wǎng)絡的初始激活向量，它僅在初始瞬間t＝0時作用于網(wǎng)絡，起原始推動作用。X(0)移去之后，網(wǎng)絡處于自激狀態(tài)，即由反饋回來的向量X(1)作為下一次的輸入取而代之。反饋網(wǎng)絡作為非線性動力學系統(tǒng)，具有豐富的動態(tài)特性，如穩(wěn)定性、有限環(huán)狀態(tài)和混沌(chaos)狀態(tài)等。

7/27/2023187/26/202318

1．網(wǎng)絡的穩(wěn)定性

由網(wǎng)絡工作狀態(tài)的分析可知，DHNN網(wǎng)實質上是一個離散的非線性動力學系統(tǒng)。網(wǎng)絡從初態(tài)X(0)開始，若能經(jīng)有限次遞歸后，其狀態(tài)不再發(fā)生變化，即X(t+1)＝X(t)，則稱該網(wǎng)絡是穩(wěn)定的7/27/2023191．網(wǎng)絡的穩(wěn)定性7/26/20231如果網(wǎng)絡是穩(wěn)定的，它可以從任一初態(tài)收斂到一個穩(wěn)態(tài)，如圖6．2(a)所示；若網(wǎng)絡是不穩(wěn)定的，由于DHNN網(wǎng)每個節(jié)點的狀態(tài)只有1和-l兩種情況，網(wǎng)絡不可能出現(xiàn)無限發(fā)散的情況，而只可能出現(xiàn)限幅的自持振蕩，這種網(wǎng)絡稱為有限環(huán)網(wǎng)絡，圖6．2(b)給出了它的相圖。如果網(wǎng)絡狀態(tài)的軌跡在某個確定的范圍內變遷，但既不重復也不停止，狀態(tài)變化為無窮多個，軌跡也不發(fā)散到無窮遠，這種現(xiàn)象稱為混沌，其相圖如圖6．2(c)所示。對于DHNN網(wǎng)，由于網(wǎng)絡的狀態(tài)是有限的，因此不可能出現(xiàn)混沌現(xiàn)象。7/27/202320如果網(wǎng)絡是穩(wěn)定的，它可以從任一初態(tài)收斂到一個穩(wěn)態(tài)，如圖6．網(wǎng)絡的穩(wěn)定性與下面將要介紹的能量函數(shù)密切相關，利用網(wǎng)絡的能量函數(shù)可實現(xiàn)優(yōu)化求解功能。網(wǎng)絡的能量函數(shù)在網(wǎng)絡狀態(tài)按一定規(guī)則變化時，能自動趨向能量的極小點。如果把一個待求解問題的目標函數(shù)以網(wǎng)絡能量函數(shù)的形式表達出來，當能量函數(shù)趨于最小時，對應的網(wǎng)絡狀態(tài)就是問題的最優(yōu)解。網(wǎng)絡的初態(tài)可視為問題的初始解，而網(wǎng)絡從初態(tài)向穩(wěn)態(tài)的收斂過程便是優(yōu)化計算過程，這種尋優(yōu)搜索是在網(wǎng)絡演變過程中自動完成的。7/27/2023217/26/202321

2．吸引子與能量函數(shù)網(wǎng)絡達到穩(wěn)定時的狀態(tài)X，稱為網(wǎng)絡的吸引子。一個動力學系統(tǒng)的最終行為是由它的吸引子決定的，吸引子的存在為信息的分布存儲記憶和神經(jīng)優(yōu)化計算提供了基礎。如果把吸引子視為問題的解，那么從初態(tài)朝吸引子演變的過程便是求解計算的過程。若把需記憶的樣本信息存儲于網(wǎng)絡不同的吸引子，當輸入含有部分記憶信息的樣本時，網(wǎng)絡的演變過程便是從部分信息尋找全部信息，即聯(lián)想回憶的過程。

7/27/2023227/26/202322下面給出DHNN網(wǎng)吸引子的定義和定理。

定義7．1若網(wǎng)絡的狀態(tài)X滿足X＝f(WX—T)，則稱X為網(wǎng)絡的吸引子。

能使網(wǎng)絡穩(wěn)定在同一吸引子的所有初態(tài)的集合，稱為該吸引子的吸引域。下面給出關于吸引域的兩個定義。

定義7．2若Xa是吸引子，對于異步方式，若存在一個調整次序，使網(wǎng)絡可以從狀態(tài)X演變到Xa，則稱X弱吸引到Xa；若對于任意調整次序，網(wǎng)絡都可以從狀態(tài)X演變到Xa，則稱X強吸引到Xa。7/27/202323下面給出DHNN網(wǎng)吸引子的定義和定理。7/26/202

定義7．3若對某些X，有X弱吸引到吸引子Xa，則稱這些X的集合為Xa的弱吸引域；若對某些X，有X強吸引到吸引子Xa，則稱這些X的集合為Xa的強吸引域。

欲使反饋網(wǎng)絡具有聯(lián)想能力，每個吸引子都應該具有一定的吸引域。只有這樣，對于帶有一定噪聲或缺損的初始樣本，網(wǎng)絡才能經(jīng)過動態(tài)演變而穩(wěn)定到某一吸引子狀態(tài)，從而實現(xiàn)正確聯(lián)想。反饋網(wǎng)絡設計的目的就是要使網(wǎng)絡能落到期望的穩(wěn)定點(問題的解)上，并且還要具有盡可能大的吸引域，以增強聯(lián)想功能。

7/27/2023247/26/202324例6．2有一DHNN網(wǎng)，n＝4，Tj＝0，j＝l，2，3，4，向量Xa、Xb和權值矩陣W分別為檢驗Xa和Xb是否為網(wǎng)絡的吸引子，并考察其是否具有聯(lián)想記憶能力。7/27/202325檢驗Xa和Xb是否為網(wǎng)絡的吸引子，并考察其是否具有聯(lián)想記憶能解本例要求驗證吸引子和檢查吸引域，下面分兩步進行。①檢驗吸引子

由吸引子定義7/27/202326解本例要求驗證吸引子和檢查吸引域，下面所以Xa是網(wǎng)絡的吸引子，因為Xb＝－Xa，由吸引子的性質1知，Xb也是網(wǎng)絡的吸引子。②考察聯(lián)想記憶能力設有樣本Xl＝(－1，1，1，1)T、X2＝(1，－1，－1，－1)T、X3＝(1，1，－1，－1)T，試考察網(wǎng)絡以異步方式工作時兩個吸引子對3個樣本的吸引能力。令網(wǎng)絡初態(tài)X(0)＝X1＝(－1，1，1，1)T。設神經(jīng)元狀態(tài)調整次序為1→2→3→4，有X(0)＝(－1，1，1，1)T→X(1)＝(1，1，1，1)T＝Xa

可以看出該樣本比較接近吸引子Xa，事實上只按異步方式調整了一步，樣本X1即收斂于Xa。7/27/202327所以Xa是網(wǎng)絡的吸引子，因為Xb＝－Xa，由令網(wǎng)絡初態(tài)X(0)＝X2＝(1，－1，－1，－1)T。設神經(jīng)元狀態(tài)調整次序為1→2→3→4，有X(0)＝(1,－1,－1,－1)T→X(1)＝(－1,－1,－1,－1)T＝Xb

可以看出樣本X2比較接近吸引子Xb，按異步方式調整一步后，樣本X2收斂于Xb。令網(wǎng)絡初態(tài)X(0)＝X3＝(1,1,－1,－1)T，它與兩個吸引子的海明距離相等。若設神經(jīng)元狀態(tài)調整次序為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

7/27/202328令網(wǎng)絡初態(tài)X(0)＝X2＝(1，－1，－1，若將神經(jīng)元狀態(tài)調整次序改為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

從本例可以看出，當網(wǎng)絡的異步調整次序一定時，最終穩(wěn)定于哪個吸引子與其初態(tài)有關；而對于確定的初態(tài)，網(wǎng)絡最終穩(wěn)定于哪個吸引子與其異步調整次序有關。

7/27/202329若將神經(jīng)元狀態(tài)調整次序改為3→4→1→2，則有7/26

定理7．1對于DHNN網(wǎng)，若按異步方式調整網(wǎng)絡狀態(tài)，且連接權矩陣W為對稱陣，則對于任意初態(tài)，網(wǎng)絡都最終收斂到一個吸引子。下面通過對能量函數(shù)的分析對定理7．1進行證明。

定義網(wǎng)絡的能量函數(shù)為：7/27/202330定理7．1對于DHNN網(wǎng)，若按異步方式7/27/2023317/26/2023317/27/2023327/26/202332Lyapunov函數(shù)——能量函數(shù)作為網(wǎng)絡的穩(wěn)定性度量wijoioj：網(wǎng)絡的一致性測度。xjoj：神經(jīng)元的輸入和輸出的一致性測度。θjoj：神經(jīng)元自身的穩(wěn)定性的測度。

7/27/202333Lyapunov函數(shù)——能量函數(shù)作為網(wǎng)絡的穩(wěn)定性度量7/2當ANk的狀態(tài)從ok變成ok′1、ANk是輸入神經(jīng)元

7/27/202334當ANk的狀態(tài)從ok變成ok′1、ANk是輸入神經(jīng)元7/當ANk的狀態(tài)從ok變成ok′wkk=07/27/202335當ANk的狀態(tài)從ok變成ok′wkk=07/26/20233ΔΕ=-(netk-θk)ΔokANk狀態(tài)的變化：Δ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結論：網(wǎng)絡的目標函數(shù)總是下降Δok<0,ok′=0&ok=1，ok由1變到0netk<θk，netk-θk<0-(netk-θk)Δok<0故ΔΕ<07/27/202336ΔΕ=-(netk-θk)ΔokANk狀態(tài)的變化：Δok=(當ANk的狀態(tài)從ok變成ok′2、ANk不是輸入神經(jīng)元

7/27/202337當ANk的狀態(tài)從ok變成ok′2、ANk不是輸入神經(jīng)元7/當ANk的狀態(tài)從ok變成ok′無論ANk的狀態(tài)是如何變化的，總有ΔΕ≤0

7/27/202338當ANk的狀態(tài)從ok變成ok′無論ANk的狀態(tài)是如何變化的，7.3統(tǒng)計Hopfield網(wǎng)與Boltzmann機統(tǒng)計Hopfield網(wǎng)

在網(wǎng)絡運行中，神經(jīng)元狀態(tài)與“人工溫度”確定的概率相關網(wǎng)絡運行模擬金屬退火過程pi：ANi的狀態(tài)取1的概率neti：ANi所獲網(wǎng)絡輸入；θi：ANi的閾值；T：系統(tǒng)的人工溫度。

7/27/2023397.3統(tǒng)計Hopfield網(wǎng)與Boltzmann機統(tǒng)計算法7-1統(tǒng)計Hopfield網(wǎng)運行算法

1

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

對網(wǎng)絡中每一個神經(jīng)元ANi，2.1

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

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

如果pi>r則使ANi的狀態(tài)為1， 否則使ANi的狀態(tài)為0；3逐漸降低溫度T，如果溫度足夠低，則算法結束。否則，重復2

7/27/202340算法7-1統(tǒng)計Hopfield網(wǎng)運行算法1

取一Boltzmann機的訓練

Boltzmann機是多級循環(huán)網(wǎng)絡，是Hopfield網(wǎng)的一種擴展。神經(jīng)元ANi實際輸出狀態(tài)oi=1的概率為：

T趨近于0時，神經(jīng)元的狀態(tài)不再具有隨機性，Boltzmann機退化成一般Hopfield網(wǎng)。7/27/202341Boltzmann機的訓練Boltzmann機是多級循環(huán)網(wǎng)Boltzmann機的訓練

7/27/202342Boltzmann機的訓練7/26/202342Boltzmann機的訓練

7/27/202343Boltzmann機的訓練7/26/202343Boltzmann機的訓練

Boltzmann機是多級循環(huán)網(wǎng)絡，是Hopfield網(wǎng)的一種擴展。神經(jīng)元ANi網(wǎng)絡輸入為：

T趨近于0時，神經(jīng)元的狀態(tài)不再具有隨機性，Boltzmann機退化成一般Hopfield網(wǎng)。7/27/202344Boltzmann機的訓練Boltzmann機是多級循環(huán)網(wǎng)Boltzmann機的訓練

神經(jīng)元ANi實際輸出狀態(tài)oi=1的概率為神經(jīng)元ANi實際輸出狀態(tài)oi=0的概率為顯然越大，則oi取1的概率越大7/27/202345Boltzmann機的訓練神經(jīng)元ANi實際輸出狀態(tài)oi=1Boltzmann機的訓練神經(jīng)元ANi在運行中狀態(tài)發(fā)生了變化

Boltzmann機的能量函數(shù)(一致性函數(shù))7/27/202346Boltzmann機的訓練神經(jīng)元ANi在運行中狀態(tài)發(fā)生了變化Boltzmann機的訓練如果ΔΕi>0，神經(jīng)元ANi處于狀態(tài)1的概率就應該越大，否則，神經(jīng)元ANi處于狀態(tài)0的概就應該越大。ΔΕi的值越大，神經(jīng)元ANi應該處于狀態(tài)1的概率就應該越大。反之，ΔΕi的值越小，神經(jīng)元ANi應該處于狀態(tài)1的概率就應該越小。從而，oi=1的概率為：

7/27/202347Boltzmann機的訓練如果ΔΕi>0，神經(jīng)元ANi處于狀Boltzmann機的訓練處于狀態(tài)a，b的概率Pa和Pb，對應于oi=1和oi=0，其它的神經(jīng)元在a，b狀態(tài)下不變

Pa=γpi

Pb=γ（1-pi）

當系統(tǒng)的溫度較低時，如果Ea<Eb，則Pa>Pb：網(wǎng)絡處于較低能量狀態(tài)的概率較大

7/27/202348Boltzmann機的訓練處于狀態(tài)a，b的概率Pa和Pb，對Boltzmann機的訓練網(wǎng)絡進行足夠多次迭代后，處于某狀態(tài)的概率與此狀態(tài)下的能量和此時系統(tǒng)的溫度有關。由于高溫時網(wǎng)絡的各個狀態(tài)出現(xiàn)的概率基本相同，這就給它逃離局部極小點提供了機會。7/27/202349Boltzmann機的訓練網(wǎng)絡進行足夠多次迭代后，處于某狀態(tài)Boltzmann機的訓練1986年，Hinton和Sejnowski訓練方法自由概率Pij-：沒有輸入時ANi和ANj同時處于激發(fā)狀態(tài)的概率。約束概率Pij+：加上輸入后ANi和ANj同時處于激發(fā)狀態(tài)的概率。聯(lián)接權修改量：Δwij=α(Pij+-Pij-)

7/27/202350Boltzmann機的訓練1986年，Hinton和Sejn算法7-2Boltzmann機訓練算法

1

計算約束概率1.1對樣本集中每個樣本，執(zhí)行如下操作：1.1.1將樣本加在網(wǎng)絡上（輸入向量及其對應的輸出向量）；1.1.2讓網(wǎng)絡尋找平衡；1.1.3記錄下所有神經(jīng)元的狀態(tài)；1.2計算對所有的樣本，ANi和ANj的狀態(tài)同時為1的概率Pij+；7/27/202351算法7-2Boltzmann機訓練算法1

計算法7-2Boltzmann機訓練算法

2

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

對權矩陣進行調整Δwij=α(Pij+-Pij-)7/27/202352算法7-2Boltzmann機訓練算法2

計算自7.7Hopfield網(wǎng)解決TSP問題1985年，J.J.Hopfield和D.W.Tank用循環(huán)網(wǎng)求解TSP。試驗表明，當城市的個數(shù)不超過30時，多可以給出最優(yōu)解的近似解。而當城市的個數(shù)超過30時，最終的結果就不太理想了

設問題中含有n個城市,用n*n個神經(jīng)元構成網(wǎng)絡

7/27/2023537.7Hopfield網(wǎng)解決TSP問題1985年，J.

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

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

7/27/202354

應用CHNN網(wǎng)解決優(yōu)化計算問題7/26/202354

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

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

7/27/202356其基本思想是把TSP問題映射到CHNN網(wǎng)絡1．TSP問題描述

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

7/27/2023571．TSP問題描述7/26/202357

TSP問題描述

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

7/27/202358

TSP問題描述7/26/202358由于每個城市僅能訪問一次，因此換位陣中每城市行只允許且必須有一個1，其余元素均為0。為了用神經(jīng)元的狀態(tài)表示某城市在某一有效路線中的位置，采用雙下標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。7/27/202359由于每個城市僅能訪問一次，因此換位陣中每城市7.7Hopfield網(wǎng)解決TSP問題dxy——城市X與城市Y之間的距離；vxi——城市X的第i個神經(jīng)元的狀態(tài)：

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

7/27/2023607.7Hopfield網(wǎng)解決TSP問題dxy——城市X與7.7Hopfield網(wǎng)用于解決TSP問題例如：四個城市X、Y、Z、W城市名訪問順序標示1234X0100Y0001Z1000W00107/27/2023617.7Hopfield網(wǎng)用于解決TSP問題例如：四個城市能量函數(shù)設計

用CHNN求解TSP問題的關鍵是構造一個合適的能量函數(shù)。TSP問題的能量函數(shù)由4部分組成：(1)能量E1———城市行約束當每個城市行中的1不多于一個時，應有第x行的全部元素vxi按順序兩兩相乘之和為0，即從而全部n行的所有元素按順序兩兩相乘之和也應為零，即=0

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