第三章神經(jīng)網(wǎng)絡優(yōu)化計算

1、 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w教學重點 掌握bp神經(jīng)網(wǎng)絡的結構 掌握bp神經(jīng)網(wǎng)絡的算法原理 理解hopfield網(wǎng)絡的原理w教學難點 bp神經(jīng)網(wǎng)絡的算法原理 hopfield網(wǎng)絡的原理另外，算法的實現(xiàn)請參閱程序文件 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w“神經(jīng)網(wǎng)絡神經(jīng)網(wǎng)絡”與與“人工神經(jīng)網(wǎng)絡人工神經(jīng)網(wǎng)絡”w1943年，年，warren mcculloch和和walter pitts建立了建立了第一個人工神經(jīng)網(wǎng)絡模型；第一個人工神經(jīng)

2、網(wǎng)絡模型；w1969年，年，minsky和和papert發(fā)表發(fā)表perceptrons；w20世紀世紀80年代，年代，hopfield將人工神經(jīng)網(wǎng)絡成功應用將人工神經(jīng)網(wǎng)絡成功應用在組合優(yōu)化問題。在組合優(yōu)化問題。 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年w重要意義重要意義 現(xiàn)代的神經(jīng)網(wǎng)絡開始于現(xiàn)代的神經(jīng)網(wǎng)絡開始于mcculloch, pitts(1943)的先的先驅(qū)工作；驅(qū)工作； 他們的神經(jīng)元模型假定遵循有他們的神經(jīng)元模型假定遵循有-無模型律；無模型律； 如果如此簡單的神經(jīng)元數(shù)目足夠多和適當設置連接如果如此簡單的神經(jīng)元數(shù)目足夠多和適當設置連接權值并且同步操作權值

3、并且同步操作, mcculloch & pitts證明這樣構證明這樣構成的網(wǎng)絡原則上可以計算任何可計算函數(shù)；成的網(wǎng)絡原則上可以計算任何可計算函數(shù)； 標志著神經(jīng)網(wǎng)絡和人工智能的誕生。標志著神經(jīng)網(wǎng)絡和人工智能的誕生。 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w結構結構 mcculloch-pitts輸出輸出 函數(shù)定義為：函數(shù)定義為：inputsignalsynapticweightssummingfunctionactivationfunctionoutputyx1x2xnw2wnw1)(f- -0, 00, 1)sgn()sgn()(1xxxxwzfy

4、niii其中， 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w網(wǎng)絡的構建網(wǎng)絡的構建 y=f(x) x1y1輸出層輸出層隱藏層隱藏層輸入層輸入層x2y2ymxnw網(wǎng)絡的拓撲結構網(wǎng)絡的拓撲結構 前向型、反饋型等前向型、反饋型等w神經(jīng)元激活函數(shù)神經(jīng)元激活函數(shù) 階躍函數(shù)階躍函數(shù) 線性函數(shù)線性函數(shù) sigmoid函數(shù)函數(shù) baxxf)(數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 xexf11)(f(x)x0+1w確定的內(nèi)容確定的內(nèi)容 權值權值wi和和w確定的方式確定的方式 學習（訓練）學習（訓練） 有指導的學習：已知一組正確的輸入輸出結果的

5、條有指導的學習：已知一組正確的輸入輸出結果的條件下，神經(jīng)網(wǎng)絡依據(jù)這些數(shù)據(jù)，調(diào)整并確定權值；件下，神經(jīng)網(wǎng)絡依據(jù)這些數(shù)據(jù)，調(diào)整并確定權值； 無指導的學習：只有輸入數(shù)據(jù)，沒有正確的輸出結無指導的學習：只有輸入數(shù)據(jù)，沒有正確的輸出結果情況下，確定權值。果情況下，確定權值。 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w學習與工作的關系學習與工作的關系 先學習先學習再再工作工作 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w多層多層 兩層以上兩層以上w前向前向 無反

6、饋無反饋輸出層輸出層隱藏層隱藏層輸入層輸入層y1y2ymx1x2xn數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w目的目的 確定權值確定權值w方法方法 反向推導反向推導數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w一般結構一般結構 各神經(jīng)元之間存在相互聯(lián)系各神經(jīng)元之間存在相互聯(lián)系w分類分類 連續(xù)系統(tǒng)：激活函數(shù)為連續(xù)函數(shù)連續(xù)系統(tǒng)：激活函數(shù)為連續(xù)函數(shù) 離散系統(tǒng)：激活函數(shù)為階躍函數(shù)離散系統(tǒng)：激活函數(shù)為階躍函數(shù)數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 whopfield神經(jīng)網(wǎng)絡神經(jīng)網(wǎng)絡 1982年提出年提

7、出hopfield反饋神經(jīng)網(wǎng)絡（反饋神經(jīng)網(wǎng)絡（hnn），證明），證明在高強度連接下的神經(jīng)網(wǎng)絡依靠集體協(xié)同作用能自在高強度連接下的神經(jīng)網(wǎng)絡依靠集體協(xié)同作用能自發(fā)產(chǎn)生計算行為。發(fā)產(chǎn)生計算行為。 是典型的是典型的全連接網(wǎng)絡全連接網(wǎng)絡，通過引入能量函數(shù)，使網(wǎng)絡，通過引入能量函數(shù)，使網(wǎng)絡的平衡態(tài)與能量函數(shù)極小值解相對應。的平衡態(tài)與能量函數(shù)極小值解相對應。數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w網(wǎng)絡結構網(wǎng)絡結構 n為網(wǎng)絡節(jié)點總數(shù)。為網(wǎng)絡節(jié)點總數(shù)。 0)( , 10)( , 1) 1(),(sgn) 1( )()(1tvtvtstvtstswtvjjjjjjniijij

8、即s1(t+1)s2(t+1)sn(t+1)s1(t)s2(t)sn(t)w12w1nw21w2nwn1wn2數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年w網(wǎng)絡結構網(wǎng)絡結構 一般認為一般認為vj(t)=0時神經(jīng)元保持不變時神經(jīng)元保持不變sj(t+1)=sj(t); 一般情況下網(wǎng)絡是對稱的（一般情況下網(wǎng)絡是對稱的（wij=wji）且無自反饋（）且無自反饋（wjj=0）; 整個網(wǎng)絡的狀態(tài)可用向量整個網(wǎng)絡的狀態(tài)可用向量s表示：表示：tnssss 21數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w工作方式工作方式 串行（異步，串行（異步，a

9、synchronous）:任一時刻只有一個任一時刻只有一個單元改變狀態(tài)，其余單元保持不變；單元改變狀態(tài)，其余單元保持不變； 并行（同步，并行（同步，synchronous）：某一時刻所有神經(jīng)）：某一時刻所有神經(jīng)元同時改變狀態(tài)。元同時改變狀態(tài)。w穩(wěn)定狀態(tài)穩(wěn)定狀態(tài) 如果從如果從t=0的任一初始態(tài)的任一初始態(tài)s(0)開始變化，存在某一有開始變化，存在某一有限時刻限時刻t，從此以后網(wǎng)絡狀態(tài)不再變化，即，從此以后網(wǎng)絡狀態(tài)不再變化，即s(t+1)=s(t)，則稱網(wǎng)絡達到，則稱網(wǎng)絡達到穩(wěn)定狀態(tài)穩(wěn)定狀態(tài)。數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年w能量函數(shù)的定義能量函數(shù)的定義

10、異步方式：異步方式： 同步方式：同步方式：swss)()()(21)()()(21ttttststswettiiiijjiji)() 1(21)() 1(21 )1()(21)() 1(21tttttstststswettiiiiijjijisswss數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年w能量函數(shù)能量函數(shù) 能量是有界的：能量是有界的： 從任一初始狀態(tài)開始，若在每次迭代時都滿足從任一初始狀態(tài)開始，若在每次迭代時都滿足e0，則網(wǎng)絡的能量將越來越小，最后趨向于穩(wěn)，則網(wǎng)絡的能量將越來越小，最后趨向于穩(wěn)定狀態(tài)定狀態(tài)e0 。iiijijiiiijjijiwssswe|

11、21|21|1)( , 1) 1( , 21)( , 1) 1( , 2)() 1( , 0)() 1()(tststststststststsiiiiiiiii數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w能量函數(shù)能量函數(shù) 分析異步（且網(wǎng)絡對稱分析異步（且網(wǎng)絡對稱wij=wji）情況下：）情況下： 假設只有神經(jīng)元假設只有神經(jīng)元i改變狀態(tài)改變狀態(tài)swss)()()(21)()()(21ttttststswettiiiijjiji0)() 1( )() 1(2121 21212211tstsswsswststswsswsswssswssweiiiiiiijjiji

12、iiiiiijijjiijijijiinjijjinjijij數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w能量函數(shù)能量函數(shù) 分析異步（且網(wǎng)絡對稱分析異步（且網(wǎng)絡對稱wij=wji）情況下：）情況下： 假設只有神經(jīng)元假設只有神經(jīng)元i改變狀態(tài)改變狀態(tài)同號同號swss)()()(21)()()(21ttttststswettiiiijjiji數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w能量函數(shù)能量函數(shù) 分析同步（且網(wǎng)絡對稱分析同步（且網(wǎng)絡對稱wij=wji）情況下：）情況下： 0)1() 1()(21 )1() 1(21)1() 1

13、()(21 )1()(21) 1()(21)() 1(21)() 1(21ttttttttttttttttettttttttsswssssswssswsssswss同號同號數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w網(wǎng)絡結構網(wǎng)絡結構 與電子線路對應：與電子線路對應： 放大器放大器神經(jīng)元神經(jīng)元 電阻、電容電阻、電容神經(jīng)元的時間常數(shù)神經(jīng)元的時間常數(shù) 電導電導權系數(shù)權系數(shù)數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w網(wǎng)絡的微分方程網(wǎng)絡的微分方程w能量函數(shù)能量函數(shù) 可證明，若可證明，若g-1為單調(diào)增且連續(xù)，為單調(diào)增且連續(xù)，cj0，tji

14、=tij，則，則有有de/dt0，當且僅當，當且僅當dvi/dt=0時時de/dt=0。 )(1jjjjjniijijjvgsirvstdtdvcnjsjjjjnjjjninjjiijjdvvgrsisste101111)(121數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w能量函數(shù)能量函數(shù) 隨著時間的增長，神經(jīng)網(wǎng)絡在狀態(tài)空間中的解軌跡隨著時間的增長，神經(jīng)網(wǎng)絡在狀態(tài)空間中的解軌跡總是向能量函數(shù)減小的方向變化，且網(wǎng)絡的穩(wěn)定點總是向能量函數(shù)減小的方向變化，且網(wǎng)絡的穩(wěn)定點就是能量函數(shù)的極小點。就是能量函數(shù)的極小點。數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 20132

15、0132013年年年 w能量函數(shù)能量函數(shù) 將動力系統(tǒng)方程將動力系統(tǒng)方程 簡單記為：簡單記為： 如果如果 ，則稱，則稱ve是動力系統(tǒng)的平衡點，也是動力系統(tǒng)的平衡點，也稱稱ve為吸引子。為吸引子。 )(1jjjjjniijijjvgsirvstdtdvc),(tvqdtdvttvqe , 0),(數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w能量函數(shù)能量函數(shù) 當從某一初始狀態(tài)變化時，網(wǎng)絡的演變是使當從某一初始狀態(tài)變化時，網(wǎng)絡的演變是使e下降，下降，達到某一局部極小時就停止變化。這些能量的局部達到某一局部極小時就停止變化。這些能量的局部極小點就是網(wǎng)絡的極小點就是網(wǎng)絡的

16、穩(wěn)定點穩(wěn)定點或稱或稱吸引子吸引子。數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 whopfield網(wǎng)絡設計網(wǎng)絡設計 當當hopfield用于優(yōu)化計算時，網(wǎng)絡的權值是確定用于優(yōu)化計算時，網(wǎng)絡的權值是確定的，應將目標函數(shù)與能量函數(shù)相對應，通過網(wǎng)絡的，應將目標函數(shù)與能量函數(shù)相對應，通過網(wǎng)絡的運行使能量函數(shù)不斷下降并最終達到最小，從的運行使能量函數(shù)不斷下降并最終達到最小，從而得到問題對應的極小解。而得到問題對應的極小解。數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 whopfield網(wǎng)絡設計網(wǎng)絡設計 通常需要以下幾方面的工作：通常需要以下幾方

17、面的工作： （1）選擇合適的問題表示方法，使神經(jīng)網(wǎng)絡的輸）選擇合適的問題表示方法，使神經(jīng)網(wǎng)絡的輸出與問題的解相對應；出與問題的解相對應； （2）構造合適的能量函數(shù)，使其最小值對應問題）構造合適的能量函數(shù)，使其最小值對應問題的最優(yōu)解；的最優(yōu)解； 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 whopfield網(wǎng)絡設計網(wǎng)絡設計 通常需要以下幾方面的工作：通常需要以下幾方面的工作： （3）由能量函數(shù)和穩(wěn)定條件設計網(wǎng)絡參數(shù)，如連）由能量函數(shù)和穩(wěn)定條件設計網(wǎng)絡參數(shù)，如連接權值和偏置參數(shù)等；接權值和偏置參數(shù)等； （4）構造相應的神經(jīng)網(wǎng)絡和動態(tài)方程；）構造相應的神經(jīng)網(wǎng)絡和動態(tài)方

18、程； （5）用硬件實現(xiàn)或軟件模擬。）用硬件實現(xiàn)或軟件模擬。數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 wtsp問題的表示問題的表示 將將tsp問題用一個問題用一個nn矩陣表示，矩陣的每個元素矩陣表示，矩陣的每個元素代表一個神經(jīng)元。代表一個神經(jīng)元。 代表商人行走順序為：代表商人行走順序為：3124 每一行、每一列的和各為每一行、每一列的和各為1。1為是，為是，0為否為否第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001w能量函數(shù)的構建能量函數(shù)的構建 每個神經(jīng)元接收到的值為每個神經(jīng)元接收到的值為zij，其

19、輸出值為，其輸出值為yij，激活，激活函數(shù)采用函數(shù)采用sigmoid函數(shù)，記兩個城市函數(shù)，記兩個城市x和和y的距離是的距離是dxy。 1）希望每一行的和為）希望每一行的和為1，即，即 最小，每一行最多有一個最小，每一行最多有一個1時，時，e10。nuniijujuiyye111數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001w能量函數(shù)的構建能量函數(shù)的構建 2）希望每一列的和為）希望每一列的和為1，即，即 最小，每一列最多有一個最小，每一列最多有一個1時，時

20、，e20。 3）希望每一行每一列正好有一個）希望每一行每一列正好有一個1，則，則 為零。為零。ninuuvviuiyye112數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年2113nyeninjij第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001w能量函數(shù)的構建能量函數(shù)的構建 4）e1，e2，e3只能保證只能保證tsp的一個可行解，為了的一個可行解，為了得到得到tsp的最小路徑，當?shù)淖钚÷窂剑攄uv=dvu時，希望時，希望 最小，其中，最小，其中，yu0=yun，yu(n+1)=yu1。duvyuiy

21、v(i+1)表示城表示城市市u和和v之間的距離（之間的距離（i代表行走順序）。代表行走順序）。nuuvniivivuiuvyyyde11)1()1(4)(數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年第第1站站第第2站站第第3站站第第4站站城市城市10100城市城市20010城市城市31000城市城市40001w能量函數(shù)的構建能量函數(shù)的構建 5）根據(jù)連續(xù)）根據(jù)連續(xù)hopfield神經(jīng)網(wǎng)絡能量函數(shù)，神經(jīng)網(wǎng)絡能量函數(shù)， 最后，能量函數(shù)表示為：最后，能量函數(shù)表示為： a，b，c，d，為非負常數(shù)。為非負常數(shù)。jiyijijdyyfe,015)(數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)

22、學與統(tǒng)計學院 201320132013年年年543212222eedecebeaew能量函數(shù)的構建能量函數(shù)的構建 由動力學方程，由動力學方程， )()()( 1111uiuiuvviviuvnvnjvjuvviijujuiuiuizfyyyddnycybyazyedtdz數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w能量函數(shù)的構建能量函數(shù)的構建 整理后得到：整理后得到：數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年0 , , 0 , 1 )()1 ()1 (1,1,uuijuiijjjuvuvijijuvvjuidjijinciddc

23、baw其中，w10城市城市tsp問題（問題（d*=2.691） 0.4 0.4439; 0.2439 0.1463; 0.1707 0.2293; 0.2293 0.761; 0.5171 0.9414; 0.8732 0.6536; 0.6878 0.5219; 0.8488 0.3609; 0.6683 0.2536; 0.6195 0.2634數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w10城市城市tsp問題（問題（d*=2.691） 流程圖：流程圖： 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年w10城市城市tsp問題（問

24、題（d*=2.691） 初始參數(shù)：初始參數(shù)： 1 abd500，c200 激勵函數(shù)為激勵函數(shù)為sigmoid 其中，其中，00.02數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年0211)(uizuiuiezfyw10城市城市tsp問題（問題（d*=2.691） 初始參數(shù)：初始參數(shù)： 初始的初始的yui 初始的初始的zui =0.0000110110110uiuiy數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 00000001 . 01 . 0 ,9ln2uiuiuizzzzzw10城市城市tsp問題（問題（d*=2.691） 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w10城市城市tsp問題（問題（d*=2.691） 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院 201320132013年年年 w10城市城市tsp問題（