反饋神經(jīng)網(wǎng)絡(luò)本章知識結(jié)構(gòu)概述離散Hopfield網(wǎng)絡(luò)連續(xù)Hopfield網(wǎng)絡(luò)連續(xù)Hopfield網(wǎng)絡(luò)的應(yīng)用——優(yōu)化計算3.3連續(xù)Hopfield網(wǎng)絡(luò)連續(xù)Hopfield網(wǎng)絡(luò)(簡稱CHNN)的拓樸結(jié)構(gòu)和DHNN的結(jié)構(gòu)相似.這種拓樸結(jié)構(gòu)和生物的神經(jīng)系統(tǒng)中大量存在的神經(jīng)反饋回路是相一致的.在CHNN中,和DHNN一樣,其穩(wěn)定條件也要求Wij=Wji.CHNN和DHNN不同的地方在于其函數(shù)g不是階躍函數(shù),而是S形的連續(xù)函數(shù).一般取g(u)=1/(1+e-u)

(4)3.3連續(xù)Hopfield網(wǎng)絡(luò)下面將簡單介紹CHNN,主要內(nèi)容:工作原理、穩(wěn)定性、在組合優(yōu)化中的應(yīng)用.3.3.1CHNN的工作原理CHNN在時間上是連續(xù)的.所以,網(wǎng)絡(luò)中各神經(jīng)元是處于同步方式工作的.考慮對于一個神經(jīng)細胞,即神經(jīng)元i,其內(nèi)部膜電位狀態(tài)用uj表示,生物神經(jīng)元的動態(tài)(微分系統(tǒng))由運算放大器來模擬,其中微分電路中細胞膜輸入電容為Ci,細胞膜的傳遞電阻為Ri,輸出電壓為Vi,外部輸入電流用Ii表示,3.3.1CHNN的工作原理神經(jīng)元的狀態(tài)滿足如下動力學方程.則CHNN可用圖6所示的電路來模擬實現(xiàn).3.3.1CHNN的工作原理圖6CHNN的電路形式3.3.1CHNN的工作原理電路中微分系統(tǒng)的暫態(tài)過程的時間常數(shù)通過電容Ci和電阻Ri并聯(lián)實現(xiàn),跨導Tij模擬神經(jīng)元之間互連的突觸特性運算放大器模擬神經(jīng)元的非線性特性Hopfield用模擬電路設(shè)計了一個CHNN的電路模型，如下圖所示：3.3.1CHNN的工作原理

取參數(shù)3.3.1CHNN的工作原理得：過程：先設(shè)定初態(tài)（），運行至穩(wěn)定，得到穩(wěn)定狀態(tài)。對應(yīng)輸出：3.3.1CHNN的工作原理在Hopfield網(wǎng)絡(luò)中,由于反饋的存在,其加權(quán)輸入和ui,i=1~n為網(wǎng)絡(luò)狀態(tài),網(wǎng)絡(luò)的輸出為y1~yn,則u,y的變化過程為一個非線性動力學系統(tǒng).對連續(xù)的非線性動力學系統(tǒng),可用非線性微分方程來描述.連續(xù)非線性動力學系統(tǒng),一般存在多個平衡態(tài).3.3.2CHNN的穩(wěn)定性其中g(shù)-1(v)是Vi(t)＝gi(Ui(t))的反函數(shù).如果CHNN中神經(jīng)元激發(fā)函數(shù)是單調(diào)增長的連續(xù)并有界函數(shù),并且Wij=Wji,則有dE(t)/dt0當且僅當dVi(t)/dt=0時,有dE(t)/dt=03.3.2CHNN的穩(wěn)定性因此,對于CHNN,分析其穩(wěn)定性及平衡態(tài)問題是非常重要的.Hopfield給出如下穩(wěn)定性定理:定理

給出能量函數(shù)E(t)這個定理的意義可以解釋如下:當網(wǎng)絡(luò)神經(jīng)元的激發(fā)函數(shù)是S函數(shù),并且網(wǎng)絡(luò)權(quán)系數(shù)矩陣對稱,則隨時間的變化網(wǎng)絡(luò)的能量會下降或不變.而且僅當輸出電位隨時間變化不變時,網(wǎng)絡(luò)的能量才會不變.換而言之,在上述條件下的網(wǎng)絡(luò)是能量不變或下降的.這個定理的證明過程如下:3.3.2CHNN的穩(wěn)定性證明

對能量函數(shù)E(t)求時間的導數(shù)dE(t)/dt,則有3.3.2CHNN的穩(wěn)定性如果存在Wij=Wji,則上式可寫為3.3.2CHNN的穩(wěn)定性從CHNN的動態(tài)方程,有故式(8)式可寫成考慮到Vi(t)＝gi(Ui(t)),有3.3.2CHNN的穩(wěn)定性由于神經(jīng)元的激勵函數(shù)gi(Ui(t))為單調(diào)增函數(shù),因此dUi(t)/dVi(t)0故,有dE(t)/dt0當并且僅當dVi(t)/dt=0時,有dE(t)/dt=0這個定理說明HNN的能量函數(shù)E(t)是單調(diào)下降的,如果E(t)有下界,即有確定的極小值,那么網(wǎng)絡(luò)必定是穩(wěn)定的.而且,可以知道穩(wěn)定點對應(yīng)于能量函數(shù)的下界,即極小值.下一步工作,只需證明能量函數(shù)有下界,那么.就可以證明網(wǎng)絡(luò)是穩(wěn)定的.可以證明,如果CHNN的激發(fā)函數(shù)g是連續(xù)而且有界的,那么,能量函數(shù)E(t)是有界的.因此,該CHNN網(wǎng)絡(luò)必定是穩(wěn)定的.3.3.2CHNN的穩(wěn)定性最后,關(guān)于CHNN的穩(wěn)定性(收斂性)、平衡點、聯(lián)想記憶特性與優(yōu)化問題的應(yīng)用有如下結(jié)論:具有良好的收斂性.當HNN的神經(jīng)元激發(fā)函數(shù)g是連續(xù)且有界的,例如S函數(shù),且網(wǎng)絡(luò)的權(quán)系數(shù)矩陣對稱,則這個CHNN是穩(wěn)定的.對穩(wěn)定的CHNN,具有有限個平衡點;如果平衡點是穩(wěn)定的,那么它也一定是漸進穩(wěn)定的;漸進穩(wěn)定平衡點為其能量函數(shù)的局部極小點;網(wǎng)絡(luò)以大規(guī)模、非線性、連續(xù)時間并行方式處理信息,其計算時間就是網(wǎng)絡(luò)趨于平衡點的時間.3.3.2CHNN的穩(wěn)定性對CHNN的信息存儲與聯(lián)想記憶特性能將任意一組希望存儲的矢量綜合為網(wǎng)絡(luò)的漸進平衡點;網(wǎng)絡(luò)的存儲信息表現(xiàn)為神經(jīng)元之間互連的分布式動態(tài)存儲;其信息存儲與聯(lián)想記憶具有一定的容錯特性,即能對有損失的記憶樣本輸入聯(lián)想出完成的存儲模式.3.3.2CHNN的穩(wěn)定性對在優(yōu)化問題中的應(yīng)用在應(yīng)用中,任何一個系統(tǒng),如果其優(yōu)化問題可以用能量函數(shù)E(t)作為目標函數(shù),那么,總可以用CHNN對其進行求解.由于引入能量函數(shù)E(t),Hopfield使NN和問題優(yōu)化直接對應(yīng),這種工作是具開拓性的.利用NN進行優(yōu)化計算,就是對NN這一動力系統(tǒng)給出初始估計點,即初始條件,然后隨網(wǎng)絡(luò)的運動而找到相應(yīng)極小點.這樣,大量的優(yōu)化問題都可以用CHNN來求解.這也是HNN用于神經(jīng)計算的基本原因.3.3.2CHNN的穩(wěn)定性3.3.3CHNN在組合優(yōu)化中的應(yīng)用組合優(yōu)化問題是一類復雜的優(yōu)化問題,其中許多問題是屬于NP問題,即不存在多項式時間解法的困難問題.這類問題形象地說,就是存在組合爆炸,即該問題求解的時間復雜度與空間復雜度與問題的規(guī)模存在指數(shù)關(guān)系,使得對于大型組合優(yōu)化問題,不能在有效時間內(nèi)求得全局解,達不到優(yōu)化的目的.許多實際問題可以歸結(jié)為組合優(yōu)化問題,如ICdesign(placement,wiring)Graphtheoreticproblems(partitioning,coloring,vertexcovering)3.3.3CHNN在組合優(yōu)化中的應(yīng)用PlanningSchedulingOthercombinatorialoptimizationproblems(knapsack,TSP)由于許多實際問題可以歸結(jié)為組合優(yōu)化問題,且為NP問題,因此研究求解組合優(yōu)化問題的滿意解、次優(yōu)解的有效算法一直是優(yōu)化領(lǐng)域的重點.3.3.3CHNN在組合優(yōu)化中的應(yīng)用1982年,J.Hopfield提出的CHNN為求解組合優(yōu)化提供了一種新思路、新方法.該方法得到廣泛重視不僅是因為它能在較短時間內(nèi)求解滿意解、次優(yōu)解,更重要的是它有著能利用硬件實現(xiàn)的CHNN進行達到硬件運算高效率的組合優(yōu)化問題求解.自HNN誕生以來,廣大研究工作者已將這一誘人的方法廣泛應(yīng)用于許多著名的組合優(yōu)化問題,如旅行者商(TSP)問題指派問題線性規(guī)劃問題

……以及非線性優(yōu)化中去.3.3.3CHNN在組合優(yōu)化中的應(yīng)用HNN優(yōu)化計算的主要思想為:根據(jù)求解的優(yōu)化命題,設(shè)計相應(yīng)的HNN,包括網(wǎng)絡(luò)結(jié)構(gòu)能量函數(shù)公式相應(yīng)的權(quán)值矩陣W在確定權(quán)值矩陣W后,根據(jù)問題的初始狀態(tài),使HNN按照所設(shè)計的非線性NN動力學演化狀態(tài),目的為尋找具有最小能量E的穩(wěn)定狀態(tài),即為該優(yōu)化問題的解.下面將簡單介紹CHNN模型在TSP問題中的應(yīng)用.3.3.3CHNN在組合優(yōu)化中的應(yīng)用TSP問題亦稱郵遞員路徑問題,其問題描述為:假定有n個城市A、B、C、…,已知其相互間距離為dAB、dBC、dCA、…,問題是尋找一條合理的閉合路徑,此路徑經(jīng)過每個城市,且僅經(jīng)過一次,并返回到起始城市,要求總的路徑為最短.3.3.3CHNN在組合優(yōu)化中的應(yīng)用由排列組合知識可知:對城市數(shù)為n的TSP問題,閉合路徑的數(shù)目為(n-1)!/2.從這(n-1)!/2條可能的路徑中求解一條最短路徑,對城市數(shù)n較大的情況,顯然是非易事.現(xiàn)有的TSP問題的求解算法均為指數(shù)時間算法,不存在多項式時間的全局最優(yōu)解算法.下面先介紹一下下面介紹TSP問題的CHNN模型求解所用到的符號.dxy表示城市x到城市y的距離;vxi表示在第i步(次)是否訪問城市x,其值為1時表示訪問;為0時表示第i步不訪問城市x.3.3.3CHNN在組合優(yōu)化中的應(yīng)用3.3.3CHNN在組合優(yōu)化中的應(yīng)用針對TSP問題,有如下約束條件:閉合路徑應(yīng)包括n個城市.每個城市只能訪問一次.每步(次)只能訪問一個城市.上述條件的數(shù)學描述為:閉合路徑應(yīng)包括n個城市該約束條件在運用CHNN求解TSP問題時難于直接使用,故轉(zhuǎn)換為如下求如下目標函數(shù)的極小值.3.3.3CHNN在組合優(yōu)化中的應(yīng)用每個城市只能訪問一次E2保證每個城市訪問不多于一次,其值達到最小E2=0.該約束條件可轉(zhuǎn)換為如下求目標函數(shù)E1與如下目標函數(shù)的聯(lián)合極小值.3.3.3CHNN在組合優(yōu)化中的應(yīng)用每步(次)只能訪問一個城市該約束條件轉(zhuǎn)換為如下求目標函數(shù)E1與如下目標函數(shù)的聯(lián)合極小值.E3保證每步(次)訪問城市不多于一個,其值達到最小E3=0.3.3.3CHNN在組合優(yōu)化中的應(yīng)用TSP問題的優(yōu)化目標為所走過的路徑的距離和最小,即表示為:在目標函數(shù)E1~E3取聯(lián)合極小時,E4取極小值時則對應(yīng)求得最佳路徑.因此,求解TSP問題的CHNN的能量函數(shù)可定義為:3.3.3CHNN在組合優(yōu)化中的應(yīng)用將上式和CHNN電路標準能量函數(shù)公式相比可得到節(jié)點i和節(jié)點j之間的導納值為:(3-14)其中

i.,j和

x,y定義為:其中偏流為Ixi=Cn(3-15)3.3.3CHNN在組合優(yōu)化中的應(yīng)用將式(3.14)和(3.15)代入網(wǎng)絡(luò)狀態(tài)方程(3.5)中,得到:其中uxi為神經(jīng)元的時空綜合輸入,vxi為其對應(yīng)的神經(jīng)元的輸出,兩者關(guān)系為:當網(wǎng)絡(luò)節(jié)點輸出為連續(xù)型時3.3.3CHNN在組合優(yōu)化中的應(yīng)用選擇合適的A、B、C、u0和初始值uxi=1/n,按上式迭代直至收斂即可求得該TSP問題的解.當網(wǎng)絡(luò)節(jié)點輸出為離散型時:3.3.3CHNN在組合優(yōu)化中的應(yīng)用由前面討論的應(yīng)用于TSP優(yōu)化問題的CHNN設(shè)計過程,可總結(jié)出CHNN應(yīng)用于優(yōu)化問題的步驟建立優(yōu)化模型設(shè)計CHNN模型利用CHNN模型求解優(yōu)化問題具體的設(shè)計與應(yīng)用過程為:建立優(yōu)化模型理解問題的背景,理解問題建立優(yōu)化問題的優(yōu)化變量模型、連續(xù)可微的優(yōu)化目標函數(shù)及約束條件3.3.3CHNN在組合優(yōu)化中的應(yīng)用設(shè)計CHNN模型建立用于該優(yōu)化問題的CHNN模型確定神經(jīng)元,包括優(yōu)化變量與神經(jīng)元的關(guān)系,神經(jīng)元的激發(fā)函數(shù)及動力學模型,神經(jīng)元的個數(shù)確定C