用遺傳算法求解TSP問題.pdf

1、巡回旅行商問題(TSP)是一個組合優(yōu)化方面的問題，已經(jīng)成為并將繼續(xù)成為測試組合優(yōu)化新算法的標(biāo)準(zhǔn)問題。從理論上講，使用窮舉法不但可以求解TSP問題，而且還可以求出該問題的最優(yōu)解。但是對現(xiàn)有的計算機來說，使用常規(guī)的窮舉法在如此龐大的搜索空間中尋求最優(yōu)解，幾乎是不可能的。所以，各種求解TSP問題的優(yōu)化算法應(yīng)運而生了，本文所用到的遺傳算法也在其中。 遺傳算法是一種高效智能搜索方法，并行遺傳算法是遺傳算法研究中的一個重要方向。并行遺傳算法

2、能夠提供各種大型計算問題的解決方案。Java語言提供了對并發(fā)的語言級支持，這個特性是Java的偉大創(chuàng)新之一，同時為并行遺傳算法的設(shè)計提供了最佳的技術(shù)支持。在收集國內(nèi)外相關(guān)資料，閱讀了相關(guān)文獻的基礎(chǔ)上，本文系統(tǒng)地闡述了遺傳算法的構(gòu)成原理。介紹了作者借助Java語言實現(xiàn)的一種應(yīng)用“輪盤賭”選擇操作，順序交叉操作以及啟發(fā)式變異操作求解TSP問題的遺傳算法。在了解和掌握并行遺傳算法的基本概念和工作原理后，針對TSP問題，提出了兩種基于并行遺傳算

3、法的求解方法。 第一章介紹了課題的研究背景、研究的可行性和意義，并行遺傳算法的基本理論以及所面對的問題。此外還介紹了TSP問題的研究現(xiàn)狀，并對論文內(nèi)容進行了概括性綜述。 第二章介紹了遺傳算法及并行遺傳算法模型。 第三章介紹了遺傳算法求解TSP問題的基本理論，提出了一種求解TSP問題的串行遺傳算法模型，結(jié)合實例分析了該算法的創(chuàng)新之處。 第四章介紹了兩種求解TSP問題的并行遺傳算法模型，詳細地論述了采用這兩種