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

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

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

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

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