Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法

1,第10章Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,2,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,10.1人工神經(jīng)網(wǎng)絡(luò)模型10.2Hopfield神經(jīng)網(wǎng)絡(luò)10.3Hopfield網(wǎng)絡(luò)與最優(yōu)化問題,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,3,人工神經(jīng)網(wǎng)絡(luò),人工神經(jīng)網(wǎng)絡(luò)是指由大量簡單人工神經(jīng)元互聯(lián)而成的一種計算結(jié)構(gòu)。它可以在某種程度上模擬生物神經(jīng)系統(tǒng)的工作過程，從而具備解決實際問題的能力。,人工神經(jīng)網(wǎng)絡(luò)由于其大規(guī)模并行處理、學習、聯(lián)想和記憶等功能，以及它高度的自組織和自適應能力，已成為解決許多工程問題的有力工具，近年來得到了飛速的發(fā)展。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,4,生物神經(jīng)系統(tǒng),生物神經(jīng)系統(tǒng)是一個有高度組織和相互作用的數(shù)目龐大的細胞組織群體。這些細胞被稱為神經(jīng)細胞，也稱作神經(jīng)元。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,5,人工神經(jīng)元模型,人工神經(jīng)元是構(gòu)成人工神經(jīng)網(wǎng)絡(luò)的基本單元，是對生物神經(jīng)元特性及功能的一種數(shù)學抽象，通常為一個多輸入單輸出器件。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,6,人工神經(jīng)元模型,輸入與輸出信號：s1、s2、.sn為輸入，vi為輸出。輸出也稱為單元的狀態(tài)。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,7,人工神經(jīng)元模型,權(quán)值：給不同的輸入的信號一定的權(quán)值，用wij表示。一般權(quán)值為+表示激活，為-表示抑制；,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,8,人工神經(jīng)元模型,求和器：用表示，以計算各輸入信號的加權(quán)和，其效果等同于一個線性組合；,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,9,人工神經(jīng)元模型,激活函數(shù)：圖中的f()，主要起非線性映射作用，另外還可以作為限幅器將神經(jīng)元輸出幅度限制在一定范圍內(nèi)；,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,10,人工神經(jīng)元模型,閾值：控制激活函數(shù)輸出的開關(guān)量，用i表示。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,11,人工神經(jīng)元模型,上述作用可用數(shù)學方式表示如下：,i=1,2,n,式中，sj為輸入信號；wij為神經(jīng)元i對輸入信號sj的權(quán)值；ui為線性組合結(jié)果；i為閾值；f()為激活函數(shù)；vi為神經(jīng)元i的輸出。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,12,激活函數(shù)的若干形式,（1）閾值函數(shù)，即階躍函數(shù),于是神經(jīng)元i的相應輸出為：,式中，,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,13,激活函數(shù)的若干形式,（2）分段線性函數(shù),特點：類似于系數(shù)為1的非線性放大器，當工作于線性區(qū)時它是一個線性組合器，放大系數(shù)趨于無窮大時變成一個閾值單元,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,14,激活函數(shù)的若干形式,（3）sigmoid函數(shù),式中，c為大于0的參數(shù)，可控制曲線斜率,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,15,10.1.3人工神經(jīng)網(wǎng)絡(luò)的互連模式,根據(jù)連接方式的不同，將現(xiàn)有的各類神經(jīng)網(wǎng)絡(luò)分為如下2種形式：前饋型網(wǎng)絡(luò)，反饋型網(wǎng)絡(luò),（1）前饋型網(wǎng)絡(luò),各神經(jīng)元接受前一層的輸入，并輸出給下一層，沒有反饋。結(jié)點分為兩類，即輸入單元和計算單元，每一計算單元可有任意個輸入，但只有一個輸出（它可耦合到任意多個其他結(jié)點作為輸入）?？煞譃椴煌膶?，第i-1層輸出是第i層的輸入，輸入和輸出結(jié)點與外界相連，而其他中間層稱為隱層。,主要起函數(shù)映射作用，常用于模式識別和函數(shù)逼近。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,16,（2）反饋型網(wǎng)絡(luò),所有結(jié)點都是計算單元，同時也可接受輸入，并向外界輸出。若總的單元數(shù)為n，則每一個結(jié)點有n-1個輸入、個輸出，如圖10-7的形式。,反饋網(wǎng)絡(luò)按對能量函數(shù)極小點的利用分為兩類：一類是能量函數(shù)的所有極小點都起作用，主要用作各種聯(lián)想存儲器；第二類只利用全局極小點，主要用于優(yōu)化問題求解。Hopfield模型、波爾茲曼機（BM）模型等可以完成此類計算。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,17,10.2Hopfield神經(jīng)網(wǎng)絡(luò)-HNN,網(wǎng)絡(luò)中引入了反饋，所以它是一個非線性動力學系統(tǒng).非線性動力學系統(tǒng)著重關(guān)心的是系統(tǒng)的穩(wěn)定性問題。在Hopfield模型中，神經(jīng)網(wǎng)絡(luò)之間的聯(lián)系總是設(shè)為對稱的，這保證了系統(tǒng)最終會達到一個固定的有序狀態(tài)，即穩(wěn)定狀態(tài)。,特點：,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,18,Hopfield網(wǎng)絡(luò)基本結(jié)構(gòu):,其中，I1,I2,.,In是外部對網(wǎng)絡(luò)的輸入；v1,v2,.,vn是網(wǎng)絡(luò)系統(tǒng)的輸出；u1,u2,.,un是對相應神經(jīng)元輸入，wij是從第j個神經(jīng)元對第i個神經(jīng)元的輸入的權(quán)值，wji=wij，wii=0。f()是特性函數(shù)，決定了網(wǎng)絡(luò)是離散的還是連續(xù)的。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,19,離散型Hopfield網(wǎng)絡(luò),定義：對圖10-8中的特性函數(shù)f()取閾值函數(shù)（見圖10-3）等硬限函數(shù)，使神經(jīng)元的輸出取離散值，就得到離散型Hopfield神經(jīng)網(wǎng)絡(luò)。工作原理：設(shè)有n個神經(jīng)元，v為神經(jīng)網(wǎng)絡(luò)的狀態(tài)矢量，為第i個神經(jīng)元的輸出，輸出取值為0或者為l的二值狀態(tài)。對任一神經(jīng)元i，為第i個神經(jīng)元的內(nèi)部未加權(quán)輸入，它們對該神經(jīng)元的影響程度用連接權(quán)wij表示。為第i個神經(jīng)元的閾值。,（10-6）,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,20,離散型Hopfield網(wǎng)絡(luò),2種狀態(tài)更新方式：異步方式：在任一時刻t，只有某一個神經(jīng)元按式（10-6）發(fā)生變化，而其余n-1個神經(jīng)元的狀態(tài)保持不變。同步方式：在任一時刻t，有部分神經(jīng)元按式（10-6）變化（部分同步）或所有神經(jīng)元按式（10-6）變化（全并行方式）。,一旦給出Hopfield網(wǎng)絡(luò)的權(quán)值和神經(jīng)元的閾值，則網(wǎng)絡(luò)的狀態(tài)轉(zhuǎn)移序列就確定了。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,21,離散型Hopfield網(wǎng)絡(luò),定義10.1若神經(jīng)元i在更新過程中，輸出變量v不再變化，則稱神經(jīng)元i已穩(wěn)定。若Hopfield網(wǎng)絡(luò)從t=0的任意一個初始輸出狀態(tài)開始，存在一個有限的時間，此時間點后系統(tǒng)中所有神經(jīng)元都是穩(wěn)定的，即網(wǎng)絡(luò)狀態(tài)不再發(fā)生變化，則稱該系統(tǒng)是穩(wěn)定的，即：，對所有。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,22,離散型Hopfield網(wǎng)絡(luò),定理10.1若神經(jīng)網(wǎng)絡(luò)的連接權(quán)矩陣W是零主對角元素的對稱矩陣，即滿足wij=wji且wii0，il，2，n，網(wǎng)絡(luò)狀態(tài)按串行異步方式更新，則網(wǎng)絡(luò)必收斂于狀態(tài)空間中的某一穩(wěn)定狀態(tài)。能量函數(shù)與穩(wěn)定性之間的關(guān)系：如果網(wǎng)絡(luò)是穩(wěn)定的，則在滿足一定的參數(shù)條件下，某種能量函數(shù)在網(wǎng)絡(luò)運行過程中是不斷降低并最后趨于穩(wěn)定平衡狀態(tài)的網(wǎng)絡(luò)中任意一個神經(jīng)元節(jié)點狀態(tài)發(fā)生變化時，能量E都將減小。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,23,能量函數(shù)與穩(wěn)定性,故節(jié)點i的能量可定義為：,對于離散型網(wǎng)絡(luò)方程，Hopfield將網(wǎng)絡(luò)整體能量函數(shù)定義為：,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,24,能量函數(shù)與穩(wěn)定性,容易證明它滿足Lyapunov函數(shù)的三個條件：函數(shù)連續(xù)可導；函數(shù)正定以及；函數(shù)的導數(shù)半負定。,嚴格來說，式（10-9）并不能滿足Lyapunov函數(shù)的正定條件。但是，對于神經(jīng)元有界的神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性來說，正定條件可以退化為只要求該函數(shù)有界。,即前面已討論過的“E隨狀態(tài)變化而嚴格單調(diào)遞減”,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,25,能量函數(shù)與穩(wěn)定性,W和（由n個i構(gòu)成的列向量）都是有確定值的矩陣和向量，且有界，因此E有下界：因為式（10-9）的E是有界函數(shù)，從而可知式（10-9）是正定的，即網(wǎng)絡(luò)將最終達到穩(wěn)定狀態(tài)。,訂正：P155,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,26,能量函數(shù)與穩(wěn)定性,離散Hopfield模型的穩(wěn)定狀態(tài)與能量函數(shù)E在狀態(tài)空間的局部極小點是一一對應的。需要指出：一般在Hopfield神經(jīng)網(wǎng)絡(luò)中，能量函數(shù)可能存在局部最小值，如圖10-9所示。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,27,能量函數(shù)與穩(wěn)定性,例10-1試計算一個有8個神經(jīng)元的離散Hopfield網(wǎng)絡(luò)，其網(wǎng)絡(luò)權(quán)值W和閾值向量如下：,試確定網(wǎng)絡(luò)最后的平衡狀態(tài)。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,28,能量函數(shù)與穩(wěn)定性,例10-1試計算一個有8個神經(jīng)元的離散Hopfield網(wǎng)絡(luò)，其網(wǎng)絡(luò)權(quán)值W和閾值向量如下：,解：1計算步驟如下：（1）按式（10-9）確定如下能量函數(shù)：,（2）隨機選取神經(jīng)元i，按下式判斷該神經(jīng)元輸出狀態(tài)vi（即采用了閾值為0的雙極硬限函數(shù)），按串行工作方式，直至狀態(tài)不變，計算終止：,若神經(jīng)元i的狀態(tài),0，則取vi=1,若記憶模式較少，同時模式之間的差異較大，則聯(lián)想的結(jié)果就比較正確；而當需記憶的模式較多時，網(wǎng)絡(luò)到達的穩(wěn)定狀態(tài)往往不是己記憶的模式，亦即容易引起混淆；再者，當模式間差異較小時，網(wǎng)絡(luò)可能無法辨別出正確的模式，此時即便采用已記憶的模式作為聯(lián)想模式（自聯(lián)想），也仍可能出錯，如本例所示。注意：本例m1和m2是該網(wǎng)絡(luò)的兩個穩(wěn)定狀態(tài)?？沈炞C，對于該網(wǎng)絡(luò)的其余6個網(wǎng)絡(luò)狀態(tài)中的任何一個，都可在一次運行后收斂于這兩個狀態(tài)中的一個。解畢。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,36,10.2.3連續(xù)型Hopfield網(wǎng)絡(luò),將離散的Hopfield神經(jīng)網(wǎng)絡(luò)模型擴展到連續(xù)時間的動力學模型，其網(wǎng)絡(luò)的連接方式不變，仍然是全互連對稱結(jié)構(gòu)，特性函數(shù)f()選用Sigmoid函數(shù)，使神經(jīng)元的輸出取連續(xù)值。連續(xù)的Hopfield網(wǎng)絡(luò)可與一電子線路對應，如圖10-10所示。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,37,10.2.3連續(xù)型Hopfield網(wǎng)絡(luò),圖10-11表示由運算放大器實現(xiàn)的一個節(jié)點的模型。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,38,（10-13）,式中，,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,39,定義10.2對式（10-14）的連續(xù)Hopfield網(wǎng)絡(luò)，其能量函數(shù)E(t)為,（10-15）,證明式（10-15）表示的能量函數(shù)滿足李雅普諾夫函數(shù)的前兩個條件是很容易的事。第三個條件的滿足則可用式（10-15）推導得到。從式（10-15）不難看出：,連續(xù)Hopfield網(wǎng)絡(luò)收斂性,（10-16）,于是，,為Sigmoid函數(shù)時，其逆函數(shù),為非減函數(shù)，即,當,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,40,（10-18）,故,。,注意，式（10-15）的最后一項在Sigmoid函數(shù)值高增益下由于接近限幅器而可以忽略不計。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,41,定理10.2對于連續(xù)Hopfield網(wǎng)絡(luò)，如果f-1()為單調(diào)遞增的連續(xù)函數(shù)，Ci0，wij=wji，則沿系統(tǒng)運動軌道有,（10-19）,當且僅當,時，,，(i=1,2,n),由定理10.2可知，連續(xù)Hopfield網(wǎng)絡(luò)隨時間推移其能量函數(shù)總是在不斷地減少。網(wǎng)絡(luò)的平衡點就是E(t)的極小值點。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,42,連續(xù)Hopfield網(wǎng)絡(luò)的工作方式有如下結(jié)論：,系統(tǒng)過程從任意非平衡狀態(tài)出發(fā)，最終收斂于平衡狀態(tài)，平衡點有限。如果平衡點是穩(wěn)定的，那么一定是漸近穩(wěn)定的。漸近穩(wěn)定平衡點為其能量函數(shù)的極小點；通過適當?shù)膶W習，該網(wǎng)絡(luò)能將任意一級正交矢量存儲起來作為漸近穩(wěn)定平衡點；連續(xù)Hopfield網(wǎng)絡(luò)的信息存儲表現(xiàn)為神經(jīng)元之間互連的分布動態(tài)存儲；連續(xù)Hopfield網(wǎng)絡(luò)以大規(guī)模非線性連續(xù)時間并行方式處理信息，其計算時間就是系統(tǒng)趨于平衡點的時間。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,43,連續(xù)Hopfield網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)迭代過程的框圖,計算,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,44,10.3Hopfield網(wǎng)絡(luò)與最優(yōu)化問題,如果把一個動態(tài)系統(tǒng)的穩(wěn)定點視為個能量函數(shù)的極小點，而把能量函數(shù)視為一個優(yōu)化問題的目標函數(shù)，那么從初態(tài)朝這個穩(wěn)定點的演變過程就是一個求解該優(yōu)化問題的過程。反饋網(wǎng)絡(luò)用于優(yōu)化計算和作為聯(lián)想存儲這兩個問題是對偶的：用于優(yōu)化計算時權(quán)矩陣W已知，目的是尋找E以達到最小的穩(wěn)定狀態(tài)；而作聯(lián)想存儲時穩(wěn)定狀態(tài)則是給定的（對應于待存的模式向量），要通過學習來尋找合適的W。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,45,旅行商問題（TSP）,給定N個城市和它們兩兩之間的直達距離，找出一個閉合旅程，使每個城市只經(jīng)過一次，且總的旅行距離必須為最短。Hopfield與Tank將N城市TSP問題映射到連續(xù)Hopfield網(wǎng)絡(luò)中，通過這N個城市的一個旅程次序表給出問題的一個可行解。在旅程次序表中，一個旅程的城市次序由一組神經(jīng)元的輸出狀態(tài)表示。建立能量方程使最優(yōu)旅程次序表對應網(wǎng)絡(luò)的穩(wěn)定終止狀態(tài)。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,46,旅行商問題（TSP）,對一個N城市的TSP問，因為有N個城市，并對應有N種次序，所以要有NN個神經(jīng)元。在圖10-13（a）給出了一個路徑，其旅程總距離d為d=dBH+dHS+dSG+dGC+dCX+dXB，其中B是第一個被訪問的，隨后依次為H、S、G、C和X。這里，dIJ表示從I市到J市的直達距離。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,47,旅行商問題（TSP）,用換位矩陣來表示TSP一條路徑的方法：,在該矩陣中，每一列只有一個元素為l，其余為0，列的大小表示對某城市訪問的次序。同樣每一行也只有一個元素為1，其余為0。通過這樣的矩陣，可惟一地確定一條旅行路線。,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,48,對于用Hopfield網(wǎng)絡(luò)來求解TSP問題，就是要恰當?shù)貥?gòu)造一個能量函數(shù)，使得Hopfield網(wǎng)絡(luò)中的n個神經(jīng)元能夠求得問題的解，并使其能量處于最低狀態(tài)。為此，構(gòu)造能量函數(shù)需考慮以下兩個問題：（1）能量函數(shù)要具有適合于換位矩陣的穩(wěn)定狀態(tài)（約束條件）。（2）能量函數(shù)要有利于表達在TSP所有合法旅行路線中最短路線的解（目標函數(shù)）。能量函數(shù)的合法形式可以通過考慮神經(jīng)元的輸出是0或1來實現(xiàn)。先考慮第（2）個問題。,定義優(yōu)化目標函數(shù)為：,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,49,旅行商問題（TSP）,TSP可表示為如下優(yōu)化問題：,（10-21）,（10-22）,（10-23）,(10-24),s.t.,糾正P162yj,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,50,旅行商問題（TSP）,寫在一起，其目標函數(shù)為,（10-25）,此即描述TSP的Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)。,糾正P162yj,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,51,旅行商問題（TSP）,比較式（10-25）與式（10-15）同一變量兩端的系數(shù)，可得到網(wǎng)絡(luò)連接權(quán)和閾值的表達式（這里需要注意的是，因為網(wǎng)絡(luò)是二維的，每個變量有兩個下標，而且求和符號也相應增加一倍）：,（10-26）,式中，,為Kronecker函數(shù)，,糾正P163xi,yj-Cn,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,52,旅行商問題（TSP）,相應的神經(jīng)網(wǎng)絡(luò)動力學方程為,（10-27）,選擇合適的參數(shù)A，B，C，D和初始狀態(tài),，用式（10-27）引導網(wǎng)絡(luò)狀態(tài)的變化，就可得到用其穩(wěn)定的網(wǎng)絡(luò)狀態(tài)所表示的TSP的最優(yōu)解。,糾正P163,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,53,二分圖最優(yōu)化問題,定義：給定n（n為偶數(shù)）個節(jié)點，選擇任意兩節(jié)點進行相互連線，由此連成一個線圖；對于此線圖，用分割線將所有節(jié)點分為二等份，從而獲得一個二分圖，要求該分割線跨越這兩組之間的連線最少。如圖10-14的線圖中，給出了兩種不同的分割方式，分割1有10條跨越連線，分割2有2條跨越連線（此為最小值）。二分圖問題的在超大規(guī)模集成電路（VLSI）的布線設(shè)計中有廣泛應用。,圖10-14二分圖示例,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,54,二分圖最優(yōu)化問題,可用如下連接矩陣表示圖10-14的連接方式：,（10-28）,式中，,糾正P164,Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,