Hopfield神經(jīng)網(wǎng)絡在TSP問題中的應用.pdf

1、旅行商問題是組合優(yōu)化領域中的一個典型問題，該問題的核心就是要求出一個包含所有n個城市的具有最短路程的環(huán)路。雖然它陳述起來很簡單，但求解卻很困難，并且已經(jīng)被證明是NP完全問題。但它確實廣泛存在，且是諸多領域內(nèi)出現(xiàn)的多種復雜問題的集中概括和簡化形式。因此提出一種有效地解決TSP問題的算法有著較高的理論意義和實際應用價值。 本文首先從現(xiàn)有求解TSP的算法入手，通過研究大量的參考文獻，了解了各種算法的主要思想，并對各種算法進行了整理和分

2、類。研究發(fā)現(xiàn)遺傳算法、模擬退火算法和蟻群算法這三種算法在解決TSP問題中表現(xiàn)出了一定的優(yōu)勢，并且在實際的問題的求解中得到了廣泛的應用。接下來本文就對這三種算法進行了深入的研究，并進行了編程實現(xiàn)。文中分別用這三種算法解決了48個城市的TSP問題。從結(jié)果中作者發(fā)現(xiàn)模擬退火算法的優(yōu)化過程較長；蟻群算法同樣是搜索時間比較長，也容易陷于局部最優(yōu)解，使搜索停滯。遺傳算法實際應用時易出現(xiàn)早熟收斂和收斂性差等缺點。如何快速準確的解決TSP問題成為了現(xiàn)在

3、TSP算法研究中的一個難點。作者提出了一種基于Hopfield神經(jīng)網(wǎng)絡的算法，由于神經(jīng)網(wǎng)絡是并行計算的，其計算量不隨維數(shù)的增加而發(fā)生指數(shù)性“爆炸”，因而對于優(yōu)化問題的高速計算特別有效。在實際的實驗過程中作者發(fā)現(xiàn)該算法從在一個致命的缺點就是網(wǎng)絡極不穩(wěn)定，經(jīng)常得不到結(jié)果。為此，作者在對現(xiàn)有算法進行了改進。經(jīng)過研究發(fā)現(xiàn)最終結(jié)果的準確性很大程度上取決于初始參數(shù)的設置。在認識到這一點后，對每個參數(shù)對結(jié)果的影響進行了分析，最后給出了參數(shù)的合理設置方

4、法。本文還對能量函數(shù)進行了改進，使得問題的求解更加快速準確。對‘出現(xiàn)重復解的問題’進行了解決采用了一種從固定起點出發(fā)的辦法。最后應用該算法解決了西安旅游問題，首先結(jié)合西安旅游地圖，根據(jù)具體的旅游問題給出了網(wǎng)絡的能量函數(shù)，進而構(gòu)建了一個Hopfield神經(jīng)網(wǎng)絡。選取了西安的著名旅游景點，對景點進行了變換和歸一化，對算法編程進行實驗。實驗結(jié)果表明，該方法對10個景點和15個景點的迭代次數(shù)大都集中在250～350之間，說明該方法對于處理旅游路