【正文】 位置，采用雙下標 Yxi，第一個下標x表示城市名，χ＝1，2，…，n；第二個下標i表示該城市在訪問路線中的位置，i＝1，2，…，n。例如，Y46＝1表示旅途中第6站應訪問城市4；若Y46＝0則表示第6 站訪問的不是城市4，而是其他某個城市。 圖7．8中的換位陣所表示的旅行路線為: 4→2→5→8→1→3→7→6→4，旅行路線總長為d42+d25+d58+d81+d13+d37+d76+d64。,第五十九頁，共七十三頁。,11/1/2024,60,7.7 Hopfield網解決(jiěju233。)TSP問題,dxy——城市X與城市Y之間的距離(j249。l237。)； vxi——城市X的第i個神經元的狀態(tài)： 1 城市X在第i個被訪問 vxi= 0 城市X不在第i個被訪問 wxi,yj——城市X的第i個神經元到城市Y的第j個神經元的連接權。,第六十頁，共七十三頁。,11/1/2024,61,7.7 Hopfield網用于解決(jiěju233。)TSP問題,例如(l236。r)：四個城市X、Y、Z、W,第六十一頁，共七十三頁。,11/1/2024,62,能量函數設計 用CHNN求解TSP問題的關鍵是構造一個合適的能量函數。TSP問題的能量函數由4部分組成： (1)能量E1———城市行約束 當每個城市行中的1不多于一個時，應有第x行的全部(qu225。nb249。)元素vxi按順序兩兩相乘之和為0，即,從而全部(qu225。nb249。)n行的所有元素按順序兩兩相乘之和也應為零，即,=0,第六十二頁，共七十三頁。,11/1/2024,63,按此約束(yuēsh249。)可定義能量E1為,式中A為正常數。顯然，當E1＝0時可保證對每個城市訪問的次數(c236。sh249。)不超過一次。 (2)能量E2———位置列約束 同理，當每個位置列中的1不多于一個時，應有第i列的全部元素vxi按順序兩兩相乘之和為0，即,因此，全部n列的所有元素按順序(sh249。nx249。)兩兩相乘之和也應為零，即,=0,第六十三頁，共七十三頁。,11/1/2024,64,按此約束(yuēsh249。)可定義能量E2為,式中B為正常數。顯然(xiǎnr225。n)，當E2＝0時就能確保每次訪問的城市數不超過一個。 (3)能量E3—換位陣全局約束 E1＝0和E2＝0只是換位陣有效的必要條件，但不是充分條件。容易看出，當換位陣中各元素均為“0”時，也能滿足El＝0和E2＝0，但這顯然是無效的。因此，還需引入第三個約束條件——全局約束條件，以確保換位陣中1的數目等于城市數n，即,第六十四頁，共七十三頁。,11/1/2024,65,因此(yīncǐ)定義能量E 為,式中C為正常數。則E3＝0可保證換位陣中1的數目正好(zh232。nghǎo)等于n。,第六十五頁，共七十三頁。,11/1/2024,66,(4)能量E4—旅行路線長度 同時滿足以上3個約束條件只能說明路線是有效的，但不一定是最優(yōu)的。依題意，在路線有效的前提下，其總長度應最短。為此在能量函數中尚須引入一個能反映路線總長度的分量E4，其定義式要能保證E4隨路線總長度的縮短而減小。為設計E4，設任意兩城市x與y間的距離為dxy 。訪問這兩個城市有兩種途徑，從x到y(tǒng)，相應的表達式為 dxy(vxi ,vy,i+1)；從y到x，則相應的表達式為dyx(vxi ,vy,i－1) 。如果城市x和y在旅行順序中相鄰，則當 (vxi ,vy,i+1) ＝1時，必有 (vxi ,vy,i－1) ＝0；反之亦然。因此(yīncǐ)，有dxy[(vxi,vy,i＋1) ＋(vxi,vy,i－1]＝dxy。若定義n個城市各種可能的旅行路線長度為,第六十六頁，共七十三頁。,11/1/2024,67,式中D為正常數，當E4最小時(xiǎosh237。)旅行路線最短。 綜合以上4項能量，可得TSP問題的能量函數如下：,(6.30),第六十七頁，共七十三頁。,11/1/2024,68,網絡(wǎnglu242。)的能量函數,第六十八頁，共七十三頁。,11/1/2024,69,7.7 Hopfield網用于解決(jiěju233。)TSP問題,聯(lián)接矩陣(jǔ zh232。n) wxi,yj= Aδxy(1δij) –Bδij(1δxy) –C –ζdxy(δji+1+δji1) 1 如果i=j δij= 0 如果i≠j,第六十九頁，共七十三頁。,11/1/2024,70,圖給出用CHNN網解決(jiěju233。)10城市TSP問題的結果。圖 (a)為最優(yōu)解，圖 (b)為較佳解。,第七十頁，共七十三頁。,11/1/2024,71,按照窮舉法，我國31個(尚未計入香港特區(qū))直轄市、省會和自治區(qū)首府的巡回路徑應有(yīnɡ yǒu)約1.3261032種。我國學者對中國旅行商CTSP(Chinese TSP)問題進行了大量的研究，最新成果已達到15 449km。所得最短巡回路徑為17102km。采用Hopfield經典算法，所得到的400個解中最短路徑為21 777km。在Hopfield經典算法基礎上增加約束條件，最短路徑為16262km。在Hopfield經典算法基礎上將所有城市分成3部分后，求得最短路徑為15 904km。,第七十一頁，共七十三頁。,11/1/2024,72,第七十二頁，共七十三頁。,內容(n232。ir243。ng)總結,第7章 循環(huán)網絡。狀態(tài)變化：非同步、同步。1 if netjθj。0 if netjθj。oj if netj=θj。改為S形函數后，系統(tǒng)(x236。tǒng)就成為一個連續(xù)系統(tǒng)(x236。tǒng)。Δwij=α(Pij+Pij)。1 如果i=j。0 如果i≠j。72,第七十三頁，共七十三