Hopfield神經網絡優(yōu)化方法課件

1、第10章 Hopfield神經網絡優(yōu)化方法1Hopfield神經網絡優(yōu)化方法10.1 人工神經網絡模型10.2 Hopfield神經網絡10.3 Hopfield網絡與最優(yōu)化問題2 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法人工神經網絡人工神經網絡是指由大量簡單人工神經元互聯而成的一種計算結構。它可以在某種程度上模擬生物神經系統(tǒng)的工作過程，從而具備解決實際問題的能力。人工神經網絡由于其大規(guī)模并行處理、學習、聯想和記憶等功能，以及它高度的自組織和自適應能力，已成為解決許多工程問題的有力工具，近年來得到了飛速的發(fā)展。 3 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法生物神經系統(tǒng) 生物神經

2、系統(tǒng)是一個有高度組織和相互作用的數目龐大的細胞組織群體。這些細胞被稱為神經細胞，也稱作神經元。4 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法人工神經元模型 人工神經元是構成人工神經網絡的基本單元，是對生物神經元特性及功能的一種數學抽象，通常為一個多輸入單輸出器件。 5 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法人工神經元模型 權值：給不同的輸入的信號一定的權值，用wij表示。一般權值為+表示激活，為-表示抑制； 7 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法人工神經元模型 求和器：用表示，以計算各輸入信號的加權和，其效果等同于一個線性組合； 8 Hopfield神經網絡優(yōu)化方

3、法神經網絡優(yōu)化方法人工神經元模型 閾值：控制激活函數輸出的開關量，用i表示。 10 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法人工神經元模型 上述作用可用數學方式表示如下： i=1, 2, n 式中，sj為輸入信號；wij為神經元i對輸入信號sj的權值；ui為線性組合結果；i為閾值；f()為激活函數；vi為神經元i的輸出。 11 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法激活函數的若干形式 （1）閾值函數，即階躍函數 于是神經元i的相應輸出為： 式中， 12 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法激活函數的若干形式 （3）sigmoid函數 式中，c為大于0的參數，可控制

4、曲線斜率 14 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法10.1.3 人工神經網絡的互連模式 根據連接方式的不同，將現有的各類神經網絡分為如下2種形式：前饋型網絡 ，反饋型網絡（1）前饋型網絡 各神經元接受前一層的輸入，并輸出給下一層，沒有反饋。結點分為兩類，即輸入單元和計算單元，每一計算單元可有任意個輸入，但只有一個輸出（它可耦合到任意多個其他結點作為輸入）。可分為不同的層，第i-1層輸出是第i層的輸入，輸入和輸出結點與外界相連，而其他中間層稱為隱層。 主要起函數映射作用，常用于模式識別和函數逼近 。15 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法10.2 Hopfield神經

5、網絡 - HNN 網絡中引入了反饋，所以它是一個非線性動力學系統(tǒng) .非線性動力學系統(tǒng)著重關心的是系統(tǒng)的穩(wěn)定性問題。 在Hopfield模型中，神經網絡之間的聯系總是設為對稱的，這保證了系統(tǒng)最終會達到一個固定的有序狀態(tài)，即穩(wěn)定狀態(tài)。 特點：17 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法Hopfield網絡基本結構: 其中，I1, I2,., In是外部對網絡的輸入；v1, v2,., vn是網絡系統(tǒng)的輸出；u1, u2, ., un是對相應神經元輸入，wij是從第j個神經元對第i個神經元的輸入的權值，wji=wij，wii=0。f()是特性函數，決定了網絡是離散的還是連續(xù)的。 18 Ho

6、pfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法離散型Hopfield網絡 定義：對圖10-8中的特性函數f()取閾值函數（見圖10-3）等硬限函數，使神經元的輸出取離散值，就得到離散型Hopfield神經網絡。 工作原理：設有n個神經元，v為神經網絡的狀態(tài)矢量，為第i個神經元的輸出，輸出取值為0或者為l的二值狀態(tài)。對任一神經元i， 為第i個神經元的內部未加權輸入，它們對該神經元的影響程度用連接權wij表示。 為第i個神經元的閾值。 （10-6） 19 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法離散型Hopfield網絡 2種狀態(tài)更新方式：異步方式：在任一時刻t，只有某一個神經元按式（10-

7、6）發(fā)生變化，而其余n-1個神經元的狀態(tài)保持不變。同步方式：在任一時刻t，有部分神經元按式（10-6）變化（部分同步）或所有神經元按式（10-6）變化（全并行方式）。 一旦給出Hopfield網絡的權值和神經元的閾值，則網絡的狀態(tài)轉移序列就確定了。 20 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法離散型Hopfield網絡 定義10.1 若神經元i在更新過程中，輸出變量v不再變化，則稱神經元i已穩(wěn)定。若Hopfield網絡從t=0的任意一個初始輸出狀態(tài)開始，存在一個有限的時間，此時間點后系統(tǒng)中所有神經元都是穩(wěn)定的，即網絡狀態(tài)不再發(fā)生變化，則稱該系統(tǒng)是穩(wěn)定的，即： ，對所有 。 21 Ho

8、pfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法離散型Hopfield網絡 定理10.1 若神經網絡的連接權矩陣W是零主對角元素的對稱矩陣，即滿足wij=wji且wii0，il，2，n，網絡狀態(tài)按串行異步方式更新，則網絡必收斂于狀態(tài)空間中的某一穩(wěn)定狀態(tài)。 能量函數與穩(wěn)定性之間的關系 ：如果網絡是穩(wěn)定的，則在滿足一定的參數條件下，某種能量函數在網絡運行過程中是不斷降低并最后趨于穩(wěn)定平衡狀態(tài)的網絡中任意一個神經元節(jié)點狀態(tài)發(fā)生變化時，能量E都將減小。 22 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法能量函數與穩(wěn)定性容易證明它滿足Lyapunov函數的三個條件：函數連續(xù)可導；函數正定以及；函數的導數

9、半負定。 從可以看出E對于所有V的分量是連續(xù)的。 嚴格來說，式（10-9）并不能滿足Lyapunov函數的正定條件。但是，對于神經元有界的神經網絡的穩(wěn)定性來說，正定條件可以退化為只要求該函數有界。即前面已討論過的“E隨狀態(tài)變化而嚴格單調遞減”24 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法能量函數與穩(wěn)定性W和（由n個i構成的列向量）都是有確定值的矩陣和向量，且有界，因此E有下界： 因為式（10-9）的E是有界函數，從而可知式（10-9）是正定的，即網絡將最終達到穩(wěn)定狀態(tài)。訂正：P15525 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法能量函數與穩(wěn)定性例10-1 試計算一個有8個神經元

10、的離散Hopfield網絡， 其網絡權值W和閾值向量如下： 試確定網絡最后的平衡狀態(tài)。 27 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法能量函數與穩(wěn)定性例10-1 試計算一個有8個神經元的離散Hopfield網絡， 其網絡權值W和閾值向量如下： 解：1計算步驟如下：（1）按式（10-9）確定如下能量函數： （2）隨機選取神經元i，按下式判斷該神經元輸出狀態(tài)vi（即采用了閾值為0的雙極硬限函數），按串行工作方式，直至狀態(tài)不變，計算終止： 若神經元i的狀態(tài) 0，則取vi=1若記憶模式較少，同時模式之間的差異較大，則聯想的結果就比較正確；而當需記憶的模式較多時，網絡到達的穩(wěn)定狀態(tài)往往不是己記憶

11、的模式，亦即容易引起混淆； 再者，當模式間差異較小時，網絡可能無法辨別出正確的模式，此時即便采用已記憶的模式作為聯想模式（自聯想），也仍可能出錯，如本例所示。注意：本例m1和m2是該網絡的兩個穩(wěn)定狀態(tài)?？沈炞C，對于該網絡的其余6個網絡狀態(tài)中的任何一個，都可在一次運行后收斂于這兩個狀態(tài)中的一個。解畢。 35 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法10.2.3 連續(xù)型Hopfield網絡將離散的Hopfield神經網絡模型擴展到連續(xù)時間的動力學模型，其網絡的連接方式不變，仍然是全互連對稱結構，特性函數f()選用Sigmoid函數，使神經元的輸出取連續(xù)值。連續(xù)的Hopfield網絡可與一電

12、子線路對應，如圖10-10所示。 36 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法10.2.3 連續(xù)型Hopfield網絡圖10-11表示由運算放大器實現的一個節(jié)點的模型。 對于該模型，其電路方程可寫為： （10-12） 37 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法式中，為系統(tǒng)的外部激勵。經過整理，得： （10-13） 式中， 令 ，有： 38 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法定義10.2 對式（10-14）的連續(xù)Hopfield網絡，其能量函數E(t)為（10-15） 證明式（10-15）表示的能量函數滿足李雅普諾夫函數的前兩個條件是很容易的事。第三個條件的滿

13、足則可用式（10-15）推導得到。從式（10-15）不難看出： 連續(xù)Hopfield網絡收斂性（10-16） 于是， 為Sigmoid函數時，其逆函數 為非減函數，即 當 39 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法（10-18） 故 。 注意，式（10-15）的最后一項在Sigmoid函數值高增益下由于接近限幅器而可以忽略不計。 40 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法定理10.2 對于連續(xù)Hopfield網絡，如果f- -1()為單調遞增的連續(xù)函數，Ci0，wij= wji，則沿系統(tǒng)運動軌道有 （10-19） 當且僅當時，(i=1,2,n) 由定理10.2可知，連續(xù)

14、Hopfield網絡隨時間推移其能量函數總是在不斷地減少。網絡的平衡點就是E(t)的極小值點。 41 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法連續(xù)Hopfield網絡的工作方式有如下結論： 系統(tǒng)過程從任意非平衡狀態(tài)出發(fā)，最終收斂于平衡狀態(tài)，平衡點有限。如果平衡點是穩(wěn)定的，那么一定是漸近穩(wěn)定的。漸近穩(wěn)定平衡點為其能量函數的極小點；通過適當的學習，該網絡能將任意一級正交矢量存儲起來作為漸近穩(wěn)定平衡點；連續(xù)Hopfield網絡的信息存儲表現為神經元之間互連的分布動態(tài)存儲；連續(xù)Hopfield網絡以大規(guī)模非線性連續(xù)時間并行方式處理信息，其計算時間就是系統(tǒng)趨于平衡點的時間。 42 Hopfiel

15、d神經網絡優(yōu)化方法神經網絡優(yōu)化方法連續(xù)Hopfield網絡神經網絡迭代過程的框圖 初始化在每個周期（掃描）重復下列步驟：是否到達穩(wěn)定狀態(tài)隨機抽取一個在此周期中尚未更新的神經元。 vi+=sgm( ui+)。停止否是計算43 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法10.3 Hopfield網絡與最優(yōu)化問題 如果把一個動態(tài)系統(tǒng)的穩(wěn)定點視為個能量函數的極小點，而把能量函數視為一個優(yōu)化問題的目標函數，那么從初態(tài)朝這個穩(wěn)定點的演變過程就是一個求解該優(yōu)化問題的過程。反饋網絡用于優(yōu)化計算和作為聯想存儲這兩個問題是對偶的：用于優(yōu)化計算時權矩陣W已知，目的是尋找E以達到最小的穩(wěn)定狀態(tài)；而作聯想存儲時穩(wěn)

16、定狀態(tài)則是給定的（對應于待存的模式向量），要通過學習來尋找合適的W。 44 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP） 給定N個城市和它們兩兩之間的直達距離，找出一個閉合旅程，使每個城市只經過一次，且總的旅行距離必須為最短。Hopfield與Tank將N城市TSP問題映射到連續(xù)Hopfield網絡中，通過這N個城市的一個旅程次序表給出問題的一個可行解。在旅程次序表中，一個旅程的城市次序由一組神經元的輸出狀態(tài)表示。建立能量方程使最優(yōu)旅程次序表對應網絡的穩(wěn)定終止狀態(tài)。 45 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP）對一個N城市的TSP問，因為有

17、N個城市，并對應有N種次序，所以要有NN個神經元。在圖10-13（a）給出了一個路徑，其旅程總距離d為d=dBH+dHS+dSG+dGC+dCX+dXB，其中B是第一個被訪問的，隨后依次為H、S、G、C和X。這里，dIJ表示從I市到J市的直達距離。 46 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP）用換位矩陣來表示TSP一條路徑的方法 ：在該矩陣中，每一列只有一個元素為l，其余為0，列的大小表示對某城市訪問的次序。同樣每一行也只有一個元素為1，其余為0。通過這樣的矩陣，可惟一地確定一條旅行路線。 47 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法對于用Hopfiel

18、d網絡來求解TSP問題，就是要恰當地構造一個能量函數，使得Hopfield網絡中的n個神經元能夠求得問題的解，并使其能量處于最低狀態(tài)。為此，構造能量函數需考慮以下兩個問題：（1）能量函數要具有適合于換位矩陣的穩(wěn)定狀態(tài)（約束條件）。（2）能量函數要有利于表達在TSP所有合法旅行路線中最短路線的解（目標函數）。能量函數的合法形式可以通過考慮神經元的輸出是0或1來實現。先考慮第（2）個問題。 定義優(yōu)化目標函數為： 48 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP）TSP可表示為如下優(yōu)化問題： （10-21）（10-22）（10-23）(10-24) s.t.糾正P162yj4

19、9 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP）寫在一起，其目標函數為 （10-25） 此即描述TSP的Hopfield神經網絡的能量函數。 糾正P162yj50 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP）比較式（10-25）與式（10-15）同一變量兩端的系數，可得到網絡連接權和閾值的表達式（這里需要注意的是，因為網絡是二維的，每個變量有兩個下標，而且求和符號也相應增加一倍）： （10-26） 式中，為Kronecker函數，糾正P163xi,yj-Cn51 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法旅行商問題（TSP）相應的神經網絡動

20、力學方程為 （10-27） 選擇合適的參數A，B，C，D和初始狀態(tài)，用式（10-27）引導網絡狀態(tài)的變化，就可得到用其穩(wěn)定的網絡狀態(tài)所表示的TSP的最優(yōu)解。 糾正P16352 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法二分圖最優(yōu)化問題 定義：給定n（n為偶數）個節(jié)點，選擇任意兩節(jié)點進行相互連線，由此連成一個線圖；對于此線圖，用分割線將所有節(jié)點分為二等份，從而獲得一個二分圖，要求該分割線跨越這兩組之間的連線最少。如圖10-14的線圖中，給出了兩種不同的分割方式，分割1有10條跨越連線，分割2有2條跨越連線（此為最小值）。二分圖問題的在超大規(guī)模集成電路（VLSI）的布線設計中有廣泛應用。 圖

21、10-14二分圖示例53 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法二分圖最優(yōu)化問題 可用如下連接矩陣表示圖10-14的連接方式： （10-28） 式中， 糾正P16454 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法二分圖最優(yōu)化問題 記分割節(jié)點后形成的兩個區(qū)為A和B，定義一個在節(jié)點i處的神經元為： 式中，n是節(jié)點數，是一個常數（拉格朗日參數），且wij=cij- 。 （10-30） 這一問題的Hopfield網絡能量函數為： （10-31） 糾正P16455 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法二分圖最優(yōu)化問題可證明該函數是李雅普諾夫函數。（10-32） 按二值硬限函數建立更新規(guī)則，有： （10-33） 每個神經元的凈輸入為56 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法二分圖最優(yōu)化問題第一項是目標函數，為所有不同節(jié)點對的目標值之和，相當于試圖把每一個節(jié)點對的兩個節(jié)點都放在同一個分區(qū)里從而避免出現跨越分區(qū)的連線；而第二項為約束條件，它迫使分區(qū)具有相同的大小。 上面的二分圖問題實際上就是下面的最小化問題： （10-34） 57 Hopfield神經網絡優(yōu)化方法神經網絡優(yōu)化方法例10-4 求