人工神經(jīng)網(wǎng)絡(luò)第七章-資料下載頁
2025-09-22 10:25本頁面
【正文】 距離； ? vxi—— 城市 X的第 i個神經(jīng)元的狀態(tài)： 1 城市 X在第 i個被訪問 vxi= 0 城市 X不在第 i個被訪問 ? wxi,yj—— 城市 X的第 i個神經(jīng)元到城市 Y的第j個神經(jīng)元的連接權(quán)。 3/10/2024 60 第六十頁，共七十三頁。 Hopfield網(wǎng)用于解決 TSP問題 例如：四個城市 X、 Y、 Z、 W 城市名 訪問順序標示 1 2 3 4 X 0 1 0 0 Y 0 0 0 1 Z 1 0 0 0 W 0 0 1 0 3/10/2024 61 第六十一頁，共七十三頁。 能量函數(shù)設(shè)計 用 CHNN求解 TSP問題的關(guān)鍵是構(gòu)造一個適宜的能量函數(shù)。 TSP問題的能量函數(shù)由 4局部組成： (1)能量 E1———城市行約束 當每個城市行中的 1不多于一個時，應有第 x行的全部元素 vxi按順序兩兩相乘之和為 0，即 從而全部 n行的所有元素按順序兩兩相乘之和也應為零，即 11 1 10n n nx i x jx i j ivv?? ? ? ??? ? ?111nnx i x ji j ivv?? ? ??? =0 3/10/2024 62 第六十二頁，共七十三頁。 按此約束可定義能量 E1為 式中 A為正常數(shù)。顯然，當 E1＝ 0時可保證對每個城市訪問的次數(shù)不超過一次。 (2)能量 E2———位置列約束 同理，當每個位置列中的 1不多于一個時，應有第 i列的全部元素 vxi按順序兩兩相乘之和為 0，即 因此，全部 n列的所有元素按順序兩兩相乘之和也應為零，即 11 1 112n n nx i x jx i j iEA vv?? ? ? ?? ? ? ?111nnx i y ix y xvv?? ? ???=0 3/10/2024 63 第六十三頁，共七十三頁。 按此約束可定義能量 E2為 式中 B為正常數(shù)。顯然，當 E2＝ 0時就能確保每次訪問的城市數(shù)不超過一個。 (3)能量 E3—換位陣全局約束 E1＝ 0和 E2＝ 0只是換位陣有效的必要條件，但不是充分條件。容易看出，當換位陣中各元素均為“ 0〞時，也能滿足 El＝ 0和 E2＝ 0，但這顯然是無效的。因此，還需引入第三個約束條件 ——全局約束條件，以確保換位陣中 1的數(shù)目等于城市數(shù) n，即 121 1 112n n nx i y ii x y xB vvE?? ? ? ?? ? ? ?111nnxixinv??????3/10/2024 64 第六十四頁，共七十三頁。 因此定義能量 E 為 式中 C為正常數(shù)。那么 E3＝ 0可保證換位陣中 1的數(shù)目正好等于 n。 22???????? ?x ixi nvC3/10/2024 65 第六十五頁，共七十三頁。 (4)能量 E4—旅行路線長度 同時滿足以上 3個約束條件只能說明路線是有效的，但不一定是最優(yōu)的。依題意，在路線有效的前提下，其總長度應最短。為此在能量函數(shù)中尚須引入一個能反映路線總長度的分量E4，其定義式要能保證 E4隨路線總長度的縮短而減小。為設(shè)計E4，設(shè)任意兩城市 x與 y間的距離為 dxy 。訪問這兩個城市有兩種途徑，從 x到 y，相應的表達式為 dxy(vxi ,vy,i+1)；從 y到 x，那么相應的表達式為 dyx(vxi ,vy,i－ 1) 。如果城市 x和 y在旅行順序中相鄰，那么當 (vxi ,vy,i+1) ＝ 1時，必有 (vxi ,vy,i－ 1) ＝ 0；反之亦然。因此，有 dxy[(vxi,vy,i＋ 1) ＋ (vxi,vy,i－ 1]＝ dxy。假設(shè)定義 n個城市各種可能的旅行路線長度為 3/10/2024 66 第六十六頁，共七十三頁。 式中 D為正常數(shù)，當 E4最小時旅行路線最短。 綜合以上 4項能量，可得 TSP問題的能量函數(shù)如下： 4 , 1 , 11 1 11 [( , ) ( , )]2n n nxy xi y i xi y ix y iD d v v v vE ??? ? ??????() 3/10/2024 67 第六十七頁，共七十三頁。 網(wǎng)絡(luò)的能量函數(shù) ? ?? ? ?? ?? ? ?? ? ??????????????????x xz izizixixzx ixii x zxzixix i ijxjxivvvdDnvCvvBvvAE11222223/10/2024 68 第六十八頁，共七十三頁。 Hopfield網(wǎng)用于解決 TSP問題 ? 聯(lián)接矩陣 wxi,yj= Aδ xy(1δ ij) –Bδ ij(1δ xy) –C –ζ dxy(δ ji+1+δ ji1) 1 如果 i=j δ ij= 0 如果 i≠ j 3/10/2024 69 第六十九頁，共七十三頁。 圖給出用 CHNN網(wǎng)解決 10城市 TSP問題的結(jié)果。圖 (a)為最優(yōu)解，圖 (b)為較佳解。 3/10/2024 70 第七十頁，共七十三頁。 按照窮舉法，我國 31個 (尚未計入香港特區(qū) )直轄市、省會和自治區(qū)首府的巡回路徑應有約 1032種。我國學者對中國旅行商CTSP(Chinese TSP)問題進行了大量的研究，最新成果已到達 15 449km。所得最短巡回路徑為 17102km。采用 Hopfield經(jīng)典算法，所得到的 400個解中最短路徑為 21 777km。在 Hopfield經(jīng)典算法根底上增加約束條件，最短路徑為 16262km。在 Hopfield經(jīng)典算法根底上將所有城市分成 3局部后，求得最短路徑為15 904km。 3/10/2024 71 第七十一頁，共七十三頁。 3/10/2024 72 第七十二頁，共七十三頁。 內(nèi)容總結(jié) 第 7章 循環(huán)網(wǎng)絡(luò)。狀態(tài)變化：非同步、同步。 1 if jθj。 0 if jθj。 oj if j=θj。改為 S形函數(shù)后，系統(tǒng)就成為一個連續(xù)系統(tǒng)。 Δwij=α(Pij+Pij)。 1 如果 i=j。 0 如果 i≠j。72 第七十三頁，共七十三頁。
數(shù)學相關(guān)推薦
鄂ICP備17016276號-1