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

第7章

循環(huán)網(wǎng)絡(luò)主要內(nèi)容Hopfield網(wǎng)絡(luò)實現(xiàn)的自相聯(lián)存儲穩(wěn)定性分析統(tǒng)計Hopfield網(wǎng)與Boltzmann機基本雙聯(lián)存儲器(BAM)的結(jié)構(gòu)與訓(xùn)練幾種相聯(lián)存儲網(wǎng)絡(luò)用Hopfield網(wǎng)解決TSP問題。3/11/20241第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問題

3/11/20242第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機

7.4雙聯(lián)存儲器的結(jié)構(gòu)

7.5異相聯(lián)存儲

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

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

3/11/20243第7章

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

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

循環(huán)網(wǎng)絡(luò)對輸入信號的處理是一個逐漸“修復(fù)”、“加強”的過程。強烈變化較弱的變化不變化3/11/202447.1循環(huán)網(wǎng)絡(luò)的組織網(wǎng)絡(luò)結(jié)構(gòu)

X1Xno1om………………3/11/202457.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。h≥n，h≥m，n≥1，m≥1。神經(jīng)元：輸入、輸出、隱藏狀態(tài)變化：非同步、同步輸入向量：X=(x1，x2，…，xn)輸出向量：O=(o1，o2，…，om)

3/11/202467.1循環(huán)網(wǎng)絡(luò)的組織神經(jīng)元的網(wǎng)絡(luò)輸入：

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

oj ifnetj=θj3/11/20247最基本的Hopfield網(wǎng)

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

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

3/11/20249最基本的Hopfield網(wǎng)

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

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

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

3/11/202414

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

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

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

網(wǎng)絡(luò)的同步工作方式是一種并行方式，所有神經(jīng)元同時調(diào)整狀態(tài)，即xj(t+1)＝sgn[netj(t)]j＝1，2,…,n3/11/2024167.2穩(wěn)定性分析網(wǎng)絡(luò)的穩(wěn)定性是與收斂性不同的問題

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

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

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

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

3/11/202418

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

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

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

3/11/202422下面給出DHNN網(wǎng)吸引子的定義和定理。

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

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

定義7．2若Xa是吸引子，對于異步方式，若存在一個調(diào)整次序，使網(wǎng)絡(luò)可以從狀態(tài)X演變到Xa，則稱X弱吸引到Xa；若對于任意調(diào)整次序，網(wǎng)絡(luò)都可以從狀態(tài)X演變到Xa，則稱X強吸引到Xa。3/11/202423

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

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

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

由吸引子定義3/11/202426所以Xa是網(wǎng)絡(luò)的吸引子，因為Xb＝－Xa，由吸引子的性質(zhì)1知，Xb也是網(wǎng)絡(luò)的吸引子。②考察聯(lián)想記憶能力設(shè)有樣本Xl＝(－1，1，1，1)T、X2＝(1，－1，－1，－1)T、X3＝(1，1，－1，－1)T，試考察網(wǎng)絡(luò)以異步方式工作時兩個吸引子對3個樣本的吸引能力。令網(wǎng)絡(luò)初態(tài)X(0)＝X1＝(－1，1，1，1)T。設(shè)神經(jīng)元狀態(tài)調(diào)整次序為1→2→3→4，有X(0)＝(－1，1，1，1)T→X(1)＝(1，1，1，1)T＝Xa

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

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

3/11/202428若將神經(jīng)元狀態(tài)調(diào)整次序改為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)絡(luò)的異步調(diào)整次序一定時，最終穩(wěn)定于哪個吸引子與其初態(tài)有關(guān)；而對于確定的初態(tài)，網(wǎng)絡(luò)最終穩(wěn)定于哪個吸引子與其異步調(diào)整次序有關(guān)。

3/11/202429

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

定義網(wǎng)絡(luò)的能量函數(shù)為：3/11/2024303/11/2024313/11/202432Lyapunov函數(shù)——能量函數(shù)作為網(wǎng)絡(luò)的穩(wěn)定性度量wijoioj：網(wǎng)絡(luò)的一致性測度。xjoj：神經(jīng)元的輸入和輸出的一致性測度。θjoj：神經(jīng)元自身的穩(wěn)定性的測度。

3/11/202433當ANk的狀態(tài)從ok變成ok′1、ANk是輸入神經(jīng)元

3/11/202434當ANk的狀態(tài)從ok變成ok′wkk=03/11/202435ΔΕ=-(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結(jié)論：網(wǎng)絡(luò)的目標函數(shù)總是下降Δok<0,ok′=0&ok=1，ok由1變到0netk<θk，netk-θk<0-(netk-θk)Δok<0故ΔΕ<03/11/202436當ANk的狀態(tài)從ok變成ok′2、ANk不是輸入神經(jīng)元

3/11/202437當ANk的狀態(tài)從ok變成ok′無論ANk的狀態(tài)是如何變化的，總有ΔΕ≤0

3/11/2024387.3統(tǒng)計Hopfield網(wǎng)與Boltzmann機統(tǒng)計Hopfield網(wǎng)

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

3/11/202439算法7-1統(tǒng)計Hopfield網(wǎng)運行算法

1

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

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

按照相應(yīng)式子計算相應(yīng)的概率pi；2.2

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

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

3/11/202440Boltzmann機的訓(xùn)練

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

T趨近于0時，神經(jīng)元的狀態(tài)不再具有隨機性，Boltzmann機退化成一般Hopfield網(wǎng)。3/11/202441Boltzmann機的訓(xùn)練

3/11/202442Boltzmann機的訓(xùn)練

3/11/202443Boltzmann機的訓(xùn)練

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

T趨近于0時，神經(jīng)元的狀態(tài)不再具有隨機性，Boltzmann機退化成一般Hopfield網(wǎng)。3/11/202444Boltzmann機的訓(xùn)練

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

Boltzmann機的能量函數(shù)(一致性函數(shù))3/11/202446Boltzmann機的訓(xùn)練如果ΔΕi>0，神經(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的概率為：

3/11/202447Boltzmann機的訓(xùn)練處于狀態(tài)a，b的概率Pa和Pb，對應(yīng)于oi=1和oi=0，其它的神經(jīng)元在a，b狀態(tài)下不變

Pa=γpi

Pb=γ（1-pi）

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

3/11/202448Boltzmann機的訓(xùn)練網(wǎng)絡(luò)進行足夠多次迭代后，處于某狀態(tài)的概率與此狀態(tài)下的能量和此時系統(tǒng)的溫度有關(guān)。由于高溫時網(wǎng)絡(luò)的各個狀態(tài)出現(xiàn)的概率基本相同，這就給它逃離局部極小點提供了機會。3/11/202449Boltzmann機的訓(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+-Pij-)

3/11/202450算法7-2Boltzmann機訓(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+；3/11/202451算法7-2Boltzmann機訓(xùn)練算法

2

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

對權(quán)矩陣進行調(diào)整Δwij=α(Pij+-Pij-)3/11/2024527.7Hopfield網(wǎng)解決TSP問題1985年，J.J.Hopfield和D.W.Tank用循環(huán)網(wǎng)求解TSP。試驗表明，當城市的個數(shù)不超過30時，多可以給出最優(yōu)解的近似解。而當城市的個數(shù)超過30時，最終的結(jié)果就不太理想了

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

3/11/202453

應(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ù)，使其最小值對應(yīng)于問題的最佳解；(3)將能量函數(shù)與Lyapunov函數(shù)標準形式進行比較，可推出神經(jīng)網(wǎng)絡(luò)的權(quán)值與偏流的表達式，從而確定了網(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ò)的運行方式，在計算機上實現(xiàn)。

3/11/202454

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

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

3/11/2024561．TSP問題描述

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

3/11/202457

TSP問題描述

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

3/11/202458由于每個城市僅能訪問一次，因此換位陣中每城市行只允許且必須有一個1，其余元素均為0。為了用神經(jīng)元的狀態(tài)表示某城市在某一有效路線中的位置，采用雙下標Yxi，第一個下標x表示城市名，χ＝1，2，…，n；第二個下標i表示該城市在訪問路線中的位置，i＝1，2，…，n。例如，Y46＝1表示旅途中第6站應(yīng)訪問城市4；若Y46＝0則表示第6站訪問的不是城市4，而是其他某個城市。圖7．8中的換位陣所表示的旅行路線為:4→2→5→8→1→3→7→6→4，旅行路線總長為d42+d25+d58+d81+d13+d37+d76+d64。3/11/2024597.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)元的連接權(quán)。

3/11/2024607.7Hopfield網(wǎng)用于解決TSP問題例如：四個城市X、Y、Z、W城市名訪問順序標示1234X0100Y0001Z1000W00103/11/202461能量函數(shù)設(shè)計

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

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