錄
摘要
i
abstract
ii
引
言
1
第壹章
基本遺傳算法
2
1.1
遺傳算法的產生及發展
3
1.2
基本原理
3
1.3
遺傳算法的特點
3
1.4
基本遺傳算法描述
5
1.5
遺傳算法構造流程
6
第二章
遺傳算法的實現技術
6
2.1
編碼方法
7
2.1.1
二進制編碼
7
2.1.2
格雷碼編碼
7
2.1.3
符點數編碼
8
2.1.4
參數編碼
8
2.2
適應度函數
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
運行參數
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
最優保存策略選擇
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
測試數據
27
4.2
測試結果
27
4.3
結果分析
27
摘
要
tsp
(traveling
salesman
problem)旅行商問題是壹類典型的np完全問題，遺傳算法是解決np問題的壹種較理想的方法。文章首先介紹了基本遺傳算法的基本原理、特點及其基本實現技術；接著針對tsp
問題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應用情況，分別指出幾種常用的編碼方法的優點和缺點，並且結合tsp的運行實例詳細分析了基本遺傳算法的4個運行參數群體大小、遺傳算法的終止進化代數、交叉概率、變異概率，對遺傳算法的求解結果和求解效率的影響，經過多次的測試設定出了它們壹組比較合理的取值。最後，簡單說明了混合遺傳算法在求解tsp問題中的應用並對遺傳算法解決tsp問題的前景提出了展望。
關鍵詞：tsp
遺傳算法
遺傳算子
編碼
@@@需要的話按我的名字找我吧