神經(jīng)網(wǎng)絡優(yōu)化計算（論文資料）.ppt

1、1,第五章 神經(jīng)網(wǎng)絡優(yōu)化計算,2,5.1 人工神經(jīng)網(wǎng)絡的基本概念 5.1.1 發(fā)展歷史 5.1.2 McCulloch-Pitts神經(jīng)元 5.1.3 網(wǎng)絡結構的確定 5.1.4 關聯(lián)權值的確定 5.1.5 工作階段 5.2 多層前向神經(jīng)網(wǎng)絡 5.2.1 一般結構 5.2.2 反向傳播算法 5.3 反饋型神經(jīng)網(wǎng)絡 5.3.1 離散Hopfield神經(jīng)網(wǎng)絡 5.3.2 連續(xù)Hopfield神經(jīng)網(wǎng)絡 5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,3,5.1 人工神經(jīng)網(wǎng)絡的基本概念,“神經(jīng)網(wǎng)絡”與“人工神經(jīng)網(wǎng)絡” 1943年，Warren McCulloch和Walter Pitts建立了第一

2、個人工神經(jīng)網(wǎng)絡模型； 1969年，Minsky和Papert發(fā)表Perceptrons； 20世紀80年代，Hopfield將人工神經(jīng)網(wǎng)絡成功應用在組合優(yōu)化問題。,5.1.1 發(fā)展歷史,4,5.1 人工神經(jīng)網(wǎng)絡的基本概念,重要意義 現(xiàn)代的神經(jīng)網(wǎng)絡開始于McCulloch, Pitts(1943)的先驅工作； 他們的神經(jīng)元模型假定遵循有-無模型律； 如果如此簡單的神經(jīng)元數(shù)目足夠多和適當設置連接權值并且同步操作, McCulloch 一般情況下網(wǎng)絡是對稱的（wij=wji）且無自反饋（wjj=0）; 整個網(wǎng)絡的狀態(tài)可用向量s表示：,5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,18,5.3 反饋型神經(jīng)

3、網(wǎng)絡,工作方式 串行（異步，asynchronous）:任一時刻只有一個單元改變狀態(tài)，其余單元保持不變； 并行（同步，synchronous）：某一時刻所有神經(jīng)元同時改變狀態(tài)。 穩(wěn)定狀態(tài) 如果從t=0的任一初始態(tài)s(0)開始變化，存在某一有限時刻t，從此以后網(wǎng)絡狀態(tài)不再變化，即s(t+1)=s(t)，則稱網(wǎng)絡達到穩(wěn)定狀態(tài)。,5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,19,5.3 反饋型神經(jīng)網(wǎng)絡,能量函數(shù)的定義 異步方式： 同步方式：,5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,20,5.3 反饋型神經(jīng)網(wǎng)絡,能量函數(shù) 能量是有界的： 從任一初始狀態(tài)開始，若在每次迭代時都滿足E0，則網(wǎng)絡的能量將越來

4、越小，最后趨向于穩(wěn)定狀態(tài)E0 。,5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,21,5.3 反饋型神經(jīng)網(wǎng)絡,能量函數(shù) 分析異步（且網(wǎng)絡對稱wij=wji）情況下： 假設只有神經(jīng)元i改變狀態(tài),5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,同號,同號,22,5.3 反饋型神經(jīng)網(wǎng)絡,能量函數(shù) 分析異步（且網(wǎng)絡對稱wij=wji）情況下： 假設只有神經(jīng)元i改變狀態(tài),5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,23,5.3 反饋型神經(jīng)網(wǎng)絡,能量函數(shù) 分析同步（且網(wǎng)絡對稱wij=wji）情況下：,5.3.1 離散Hopfield神經(jīng)網(wǎng)絡,24,5.3 反饋型神經(jīng)網(wǎng)絡,網(wǎng)絡結構 與電子線路對應：,5.3.2 連續(xù)H

5、opfield神經(jīng)網(wǎng)絡,25,5.3 反饋型神經(jīng)網(wǎng)絡,網(wǎng)絡的微分方程,5.3.2 連續(xù)Hopfield神經(jīng)網(wǎng)絡,Gi,輸入,輸出,26,網(wǎng)絡的微分方程 ze是動力系統(tǒng)的平 衡點，稱吸引子。,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.2 連續(xù)Hopfield神經(jīng)網(wǎng)絡,27,能量函數(shù) 可證明，若a-1為單調增且連續(xù)，Ci0，wji=wij，則有dE/dt0，當且僅當dzi/dt=0時dE/dt=0。,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.2 連續(xù)Hopfield神經(jīng)網(wǎng)絡,28,5.3 反饋型神經(jīng)網(wǎng)絡,能量函數(shù) 當從某一初始狀態(tài)變化時，網(wǎng)絡的演變是使E下降，達到某一局部極小時就停止變化。這些能量的局部極小點就是網(wǎng)絡

6、的穩(wěn)定點或稱吸引子。,5.3.2 連續(xù)Hopfield神經(jīng)網(wǎng)絡,29,5.3 反饋型神經(jīng)網(wǎng)絡,Hopfield網(wǎng)絡設計 當Hopfield用于優(yōu)化計算時，網(wǎng)絡的權值是確定的，應將目標函數(shù)與能量函數(shù)相對應，通過網(wǎng)絡的運行使能量函數(shù)不斷下降并最終達到最小，從而得到問題對應的極小解。,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,30,5.3 反饋型神經(jīng)網(wǎng)絡,Hopfield網(wǎng)絡設計 通常需要以下幾方面的工作： （1）選擇合適的問題表示方法，使神經(jīng)網(wǎng)絡的輸出與問題的解相對應； （2）構造合適的能量函數(shù)，使其最小值對應問題的最優(yōu)解；,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,31,

7、5.3 反饋型神經(jīng)網(wǎng)絡,Hopfield網(wǎng)絡設計 通常需要以下幾方面的工作： （3）由能量函數(shù)和穩(wěn)定條件設計網(wǎng)絡參數(shù)，如連接權值和偏置參數(shù)等； （4）構造相應的神經(jīng)網(wǎng)絡和動態(tài)方程； （5）用硬件實現(xiàn)或軟件模擬。,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,32,5.3 反饋型神經(jīng)網(wǎng)絡,TSP問題的表示 將TSP問題用一個nn矩陣表示，矩陣的每個元素代表一個神經(jīng)元。 代表商人行走順序為：3124 每一行、每一列的和各為1。,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,33,能量函數(shù)的構建 每個神經(jīng)元接收到的值為zij，其輸出值為yij，激活函數(shù)采用Sigmoid函數(shù)，記兩個城

8、市x和y的距離是dxy。 1）希望每一行的和為1，即 最小，每一行最多有一個1時，E10。,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,每行的輸出值兩兩相乘之和,34,能量函數(shù)的構建 2）希望每一列的和為1，即 最小，每一列最多有一個1時，E20。 3）希望每一行每一列正好有一個1，則 最小時為零。,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,每列的輸出值兩兩相乘之和,所有的輸出值兩兩相乘之和應該為n,35,能量函數(shù)的構建 4）E1，E2，E3只能保證TSP的一個可行解，為了得到TSP的最小路徑，當duv=dvu時，希望 最小

9、，其中，yu0=yun，yu(n+1)=yu1。duvyuiyv(i+1)表示城市u和v之間的距離（i代表行走順序）。,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,36,能量函數(shù)的構建 5）根據(jù)連續(xù)Hopfield神經(jīng)網(wǎng)絡能量函數(shù)， 最后，能量函數(shù)表示為： A，B，C，D，為非負常數(shù)。,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,37,能量函數(shù)的構建 由動力學方程，,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,38,能量函數(shù)的構建 參照動力學方程，可知：,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 H

10、opfield神經(jīng)網(wǎng)絡在TSP中的應用,39,10城市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,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,40,10城市TSP問題（d*=2.691） 流程圖：,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,41,10城

11、市TSP問題（d*=2.691） 初始參數(shù)： 1 ABD500，C200 激勵函數(shù)為Sigmoid 其中，00.02,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,42,10城市TSP問題（d*=2.691） 初始參數(shù)： 初始的yui 初始的zui =0.00001,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,43,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,44,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield

12、神經(jīng)網(wǎng)絡在TSP中的應用,45,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,46,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,47,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,48,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,49,10城市TSP問題（d*=2.691）,5.3 反饋型神經(jīng)網(wǎng)絡,5.3.3 Hopfield神經(jīng)網(wǎng)絡在TSP中的應用,50,基于Hopfield網(wǎng)絡優(yōu)化的缺陷 用Hopfield網(wǎng)絡優(yōu)化的出發(fā)點建立在： （1）神經(jīng)網(wǎng)絡是穩(wěn)定的，網(wǎng)絡勢必收斂到漸進平衡點； （2）神經(jīng)網(wǎng)絡的漸進平衡點恰好是能量函數(shù)的極小值。,5.3