用遺傳算法求解TSP問(wèn)題.pdf

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

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

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