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

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

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


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