基于SOFM人工神經(jīng)網(wǎng)絡的TSP問題研究

9060字 29頁 原創(chuàng)作品，通過查重系統(tǒng)

摘 要
旅行商問題即Travelling Salesman Problem，簡稱TSP問題，在生產(chǎn)生活中的廣泛應用，使學者對任何能夠求得旅行商問題優(yōu)化結(jié)果的方法都給予了高度的關(guān)注和評價。1981年由芬蘭學者T.Kohonen最早提出了一個稱為自組織特征映射（Self Organization Feature Map-SOM或SOFM）網(wǎng)絡。由于自組織特征映射網(wǎng)絡（SOFM）能保持樣本數(shù)據(jù)的鄰域拓撲性質(zhì)，因此它被成功運用到了求解旅行商問題（TSP）中。之后許多學者在此算法的基礎上不斷改進，在解決TSP的問題中取得了巨大的成就。由于用SOFM算法求解TSP問題得到的結(jié)果只能是最優(yōu)解的逼近值，因此以提高解的精度為目的對算法進行改進，具有重大的意義。
本文也是以提高解的精度為目的，在SOFM算法的基礎上進行改進。在訓練過程中要求神經(jīng)元的數(shù)目保持不變，并且要求每一次迭代的過程中要保持權(quán)的一階矩與原來樣本數(shù)據(jù)的一階矩相同。只有在訓練過程中保持權(quán)值的統(tǒng)計特性不變，才能使網(wǎng)絡很好的保持數(shù)據(jù)樣本的拓撲結(jié)構(gòu)。當一次訓練結(jié)束后，讓每個城市都與一個神經(jīng)元的標號對應。這時，會出現(xiàn)一個神經(jīng)元對應城市的數(shù)目多于一個的問題。為了解決這個問題，本文主要采用將原先的整數(shù)標號進一步精確為小數(shù)標號的方法。經(jīng)過用這種將整數(shù)標號進一步精確化的方法處理后，原先相同的整數(shù)標號就變?yōu)椴煌男?shù)標號也就是使得每一個城市對應著一個唯一的索引標號，城市索引標號的唯一性使得在巡回路徑中城市的位置一定。


關(guān)鍵詞： 旅行商問題； 人工神經(jīng)網(wǎng)絡； 自組織特征映射網(wǎng)絡