離散系統(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)中，可以用輸出值的特性定義平衡點(diǎn)。 則稱為離散系統(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)元，可表達(dá)為：它的含義是：在一步迭代中，只有第個神經(jīng)元發(fā)生變化，而其他神經(jīng)元保持不變

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

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

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

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

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

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

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

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