離散系統(tǒng)神經(jīng)網(wǎng)絡(luò)

1、人工神經(jīng)網(wǎng)絡(luò)1.離散系統(tǒng)神經(jīng)網(wǎng)絡(luò)離散系統(tǒng)神經(jīng)網(wǎng)絡(luò)的輸出值一般有如下關(guān)系： 其中式中，如采用符號函數(shù)的反饋神經(jīng)網(wǎng)絡(luò)，其關(guān)系為：記 在離散動力系統(tǒng)中，可以用輸出值的特性定義平衡點。 則稱為離散系統(tǒng)的平衡狀態(tài)。在離散系統(tǒng)的神經(jīng)網(wǎng)絡(luò)中，當(dāng)采用符號激活函數(shù)時，建立的能量函數(shù)（5.30）變?yōu)椋浩渲校?，為符號函數(shù)，為和神經(jīng)元的權(quán)數(shù)，為第個神經(jīng)元的接受值，為外部輸入值。 由（5.43），得到能量函數(shù)（5.44）對應(yīng)的一個動力系統(tǒng)為：（5.45）的動力系統(tǒng)方程轉(zhuǎn)化為：其中如（5.42）的符號函數(shù)。異步算法是指每次只調(diào)整一個神經(jīng)元，可表達為：它的含義是：在一步迭代中，只有第個神經(jīng)元發(fā)生變化，而其他神經(jīng)元保持不變

2、。每次被調(diào)整的神經(jīng)元隨機選定。同步算法指同一時刻對所有神經(jīng)元同時調(diào)整，表達式為：例5.6：三個神經(jīng)元的反饋網(wǎng)絡(luò)的權(quán)數(shù)為： 在時刻，一組輸出，每個神經(jīng)元的閾值都為3。在第時刻，同步算法使得每個神經(jīng)元接受到的值為： 同步算法在時刻的輸出為： 異步算法的計算為：當(dāng)步迭代選擇第一個神經(jīng)元時，它的接受值為：若步迭代選擇第二個神經(jīng)元變化時，所以 ， 若步迭代選擇第三個神經(jīng)元變化時，所以 ， 雖說異步算法采用上面例中相鄰的三次迭代達到同步算法對三個神經(jīng)元進行的計算，但輸出結(jié)果（0，0，0）與同步算法輸出結(jié)果（0，1，0）的差別是顯而易見的。 定理5.3：若（5.44）中的權(quán)數(shù)是正定矩陣，采用符號函數(shù)的同步算

3、法的平衡點是系統(tǒng)（5.45）的穩(wěn)定點。 離散系統(tǒng)的異步算法有別于連續(xù)系統(tǒng)的神經(jīng)網(wǎng)絡(luò)，我們在此專門討論。在以下的討論中，特假定下列條件滿足：1.是對稱的階方陣，且；2. ；3.符號函數(shù)為： 此處的符號函數(shù)有別于前面的函數(shù)定義，它把的點賦予值1。 定理5.4：若能量函數(shù)（5.44）有下界，則對任意的初始狀態(tài)，滿足上面假設(shè)的異步算法，最終收斂到一個平衡狀態(tài)。 定義5.5：的鄰域為，其中，表示第個分量為1其他分量為0的維向量， 若能量函數(shù)在滿足：則稱為鄰域的能量極小點，簡稱能量極小點。 定理5.5：若時，定義，則每個能量極小點為平衡點。證明： 若為平衡點，則結(jié)論成立。當(dāng)某一個神經(jīng)元不平衡時，記神經(jīng)元的

4、能量變化為，則由（5.48）有 按定理5.4證明中討論的三種情況和時，定義，不平衡的可能有：CASE1:時，則，由的條件，推出，進而推出： 于是，與不平衡矛盾。CASE2：時，則，進而推出： 于是，與不平衡矛盾。綜合CASE1 和CASE2的討論，得到是一個平衡點。定理5.6：若離散系統(tǒng)神經(jīng)網(wǎng)絡(luò)的權(quán)矩陣對角線還滿足，則網(wǎng)絡(luò)的所有平衡點為能量函數(shù)極小點。證明：記平衡點，從的鄰域中任選一點，不妨設(shè)為第 個神經(jīng)元變化，則由（5.48）能量變化為：當(dāng)時，由平衡點性質(zhì)，知。由此得到。當(dāng)時，由平衡點性質(zhì)，知。由此得到。綜合上面兩點，平衡點為能量函數(shù)極小點。 神經(jīng)網(wǎng)絡(luò)異步算法的基本步驟為： STEP1：任意

5、選取一個初始狀態(tài)； STEP2：隨機選取一個神經(jīng)元，按（5.46）更新狀態(tài)； STEP3：檢驗是否為網(wǎng)絡(luò)的平衡點，若是，轉(zhuǎn)STEP4；否則，轉(zhuǎn)STEP2； STEP4：輸出。2.變形算法在中的應(yīng)用 假設(shè)的個城市位置為，其中為空間的維數(shù)。在這個空間中我們給以個臨界點，。我們期望將臨時點同城市位置匹配使得：每個城市僅同一個臨界點匹配且這些臨時點形成的閉路滿足盡量小，其中。若當(dāng)城市同臨時點匹配，則定義一個變量，否則。于是可以給出下列的能量函數(shù) （5.49）的第一項的功能是匹配，需要滿足。當(dāng)已經(jīng)匹配且漸進零的時候，（5.49）的第二項功能是使得這些臨界點的閉路盡量小且點的分布盡量均勻。由于和是變量和求

6、解的難度，用另外一個效能函數(shù)：使其達到最小。 在（5.50）中，從右邊的第一項看出，當(dāng)每一個都有一個臨界點與其匹配時， 其中，表示同匹配的臨時點集合，為同匹配的臨時點個數(shù)。此時，當(dāng)趨向零時，（5.50）右端第一項的值接近零。當(dāng)存在一個，沒有一個臨界點與其匹配時，由推出（5.50）右端第一項隨著的趨向零而增加，因此需要繼續(xù)優(yōu)化。（5.50）右端的第二項要求個臨時點形成的閉路盡量小和盡可能在閉路上均勻分布。（5.50）中只有為決策變量。能量函數(shù)的梯度為： 其中 對變量的下降梯度為：，是不小于零的參數(shù)。的彈性算法如下： STEP1：給定實例個城市的坐標(biāo)； STEP2：選一個比大得多的臨時點數(shù)； ST

7、EP3：選擇合適的參數(shù)、初始溫度和初始步長參數(shù)； STEP4：求初始坐標(biāo)的重心；隨即將，均勻地分布在以重心為圓心的一個小圓周上； STEP5：在算法沒有達到停止條件前，重復(fù)以下計算：.更新臨時坐標(biāo)為，其中由（5.52）計算。.，。3.局部搜索算法組合最優(yōu)化問題：其中為目標(biāo)函數(shù)，為約束方程，為定義域。局部搜索算法 STEP1：選定一個初始可行解；記錄當(dāng)前最優(yōu)解=，令； STEP2：當(dāng)=時，或滿足其他停止運算準則時，輸出計算結(jié)果，停止運算；否則，從中選一集合，得到中的最優(yōu)解；若，則，；否則，；重復(fù)STEP2。 在局部搜索算法中，STEP1的初始可行解選擇可以采用隨機的方法，也可用一些經(jīng)驗的方法或是

8、其他算法所得到的解。STEP2中的集合選取可以大到是 本身，也可以小到只有一個元素，如果用隨機的方法在中選一點。從直觀可以看出，選取得小將使每一步的計算量減少，但可比較的范圍很??；的選取大時每一步計算時間增加，比較的范圍自然增加，這兩種情況的應(yīng)用效果依賴于實際問題，在STEP2中，其他停止準則是除STEP2的其他準則。這寫準則的給出往往取決于人們對算法的計算時間，計算結(jié)果的要求。通過下面的例子來理解局部搜索算法。 例2.1 五個城市的對稱數(shù)據(jù)如圖2.1，其對應(yīng)的距離矩陣為 初始解=(),=45。在本例中，鄰域映射定義為對換兩個城市的。選定城市為起點，我們用兩種情況解釋緝捕搜索算法。 情況1 全

9、鄰域搜索，即 第一循環(huán)：=,相對應(yīng)的目標(biāo)函數(shù)值為：，。 第二循環(huán)：=，相對應(yīng)的目標(biāo)函數(shù)值為：，。 此時，為空集，于是所得解為，目標(biāo)值為43。情況2一步隨機搜索：，第一循環(huán)：由于采用中的一步隨機搜索，可以不再計算中每一點的值。若從中隨機選一點，如。因，所以，。 第二循環(huán)：若從中又隨機選一點，最后得到的解為。 局部搜索算法的優(yōu)點是簡單易行，容易理解，但其缺點是無法保證全局最優(yōu)性。例2.2 四個城市非對稱如圖2.2，距離矩陣為： 若初始解為并且假設(shè)城市為起始點，。鄰域中，其局部最優(yōu)解是。讀者可以按例2.1局部搜索討論的兩種情況進行驗證，該算法終止時的解是局部最優(yōu)解。而全局最優(yōu)解是，。改變局部搜索中只按下降規(guī)則轉(zhuǎn)移狀態(tài)的一個