遺傳算法在求解TSP問題畢業(yè)論文

論文字數(shù):16343,頁數(shù):45
摘  要
TSP (Traveling Salesman Problem)旅行商問題是一類典型的NP完全問題，遺傳算法是解決NP問題的一種較理想的方法。文章首先介紹了基本遺傳算法的基本原理、特點及其基本實現(xiàn)技術；接著針對TSP 問題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應用情況，分別指出幾種常用的編碼方法的優(yōu)點和缺點，并且結(jié)合TSP的運行實例詳細分析了基本遺傳算法的4個運行參數(shù)群體大小、遺傳算法的終止進化代數(shù)、交叉概率、變異概率，對遺傳算法的求解結(jié)果和求解效率的影響，經(jīng)過多次的測試設定出了它們一組比較合理的取值。最后，簡單說明了混合遺傳算法在求解TSP問題中的應用并對遺傳算法解決TSP問題的前景提出了展望。
關鍵詞：TSP  遺傳算法  遺傳算子   編碼

目  錄
摘要 I
Abstract II
引 言 1
第一章  基本遺傳算法 2
1.1 遺傳算法的產(chǎn)生及發(fā)展 3
1.2 基本原理 3
1.3 遺傳算法的特點 3
1.4 基本遺傳算法描述 5
1.5 遺傳算法構造流程 6
第二章  遺傳算法的實現(xiàn)技術 6
2.1  編碼方法 7
2.1.1 二進制編碼 7
2.1.2 格雷碼編碼 7
2.1.3 符點數(shù)編碼 8
2.1.4 參數(shù)編碼 8
2.2  適應度函數(shù) 10
2.3  選擇算子 10
2.4  交叉算子 10
2.4.1 單點交叉算子 10
2.4.2 雙點交叉算子 11
2.4.3 均勻交叉算子 11
2.4.4 部分映射交叉 11
2.4.5 順序交叉 12
2.5  變異算子 12
2.6  運行參數(shù) 12
2.7  約束條件的處理方法 13
2.8 遺傳算法流程圖 14
第三章  遺傳算法在TSP上的應用 15
3.1　TSP問題的建模與描述 15
3.2  對TSP的遺傳基因編碼方法 16
3.3  針對TSP的遺傳操作算子 17
3.3.1 選擇算子 17
3.3.1.1　輪盤賭選擇 17
3.3.1.2　最優(yōu)保存策略選擇 17
3.3.2 交叉算子 20
3.3.2.1 單點交叉 20
3.3.2.2 部分映射交叉 21
3.3.3 變異算子 23
3.4 TSP的混和遺傳算法 26
第四章  實例分析 27
4.1  測試數(shù)據(jù) 27
4.2  測試結(jié)果 27
4.3  結(jié)果分析 27