摘要
旅行商問題（Travelling Salesman Problem，簡(jiǎn)稱TSP）是一個(gè)典型的組合優(yōu)化問題，并且是一個(gè)NP難題，其可能的路徑總數(shù)與城市數(shù)目n 是成指數(shù)型增長(zhǎng)的，所以一般很難精確地求出其最優(yōu)解，因而尋找出有效的近似求解算法就具有重要的意義。
遺傳算法（GA）是求解旅行商問題（TSP）的常用方法之一。針對(duì)中國旅行商問題（CTSP），本文利用遺傳算法的全局搜索能力進(jìn)行組合優(yōu)化問題求解，設(shè)計(jì)一種大比例的優(yōu)秀個(gè)體保護(hù)的大變異遺傳算法，并使用MATLAB語言進(jìn)行了實(shí)際的編程求解，編程中的各個(gè)模塊分別實(shí)現(xiàn)了選擇、交叉、變異等關(guān)鍵環(huán)節(jié)。用編制的程序快速求解出了滿足的結(jié)果，用本文設(shè)計(jì)的遺傳算法的思路和編程程序是正確的。用該策略迅速找到了CTSP最優(yōu)解，該路徑長(zhǎng)度為15378km，比目前已知CTSP解更優(yōu)。對(duì)遺傳算法迅速求解TSP最優(yōu)解提供了可行解決方案。



關(guān)鍵詞：遺傳算法；CTSP；最短路徑；MATLAB






















Abstract
The traveling salesman problem (TSP) is a well-known NP complete problem, It’s increased by exponential n. So, it is hard to find a precision result, and it is very important to search for the near result.
The genetic algorithm (GA) is one of the ideal methods in solving it. For CTSP，According to genetic algorithm’s global searching proterty, a kind of big probability variation’s genetic algorithm is put forward, which copies big proportion of fittest. In MATLAB, the typical Chinese traveling salesman problem is computed and the result shows the thought and program is correct. The best path for CTSP is found quickly through the algorithm. The best path 15378km is get, the result is the best so far.

Key words: The Genetic Algorithm (GA); Chinese Traveling Salesman Problem (CTSP); The Shortest Path; MATLAB































目 錄
摘要 I
Abstract II
緒論 1
1 CTSP數(shù)學(xué)模型及常用算法 2
1．1 TSP的數(shù)學(xué)模型 2
1．2 TSP問題的常用求解方法 2
1．2．1 遺傳算法（GA） 2
1．2．2 模擬退火算法（SA） 3
1．2．3 蟻群算法（ACO） 3
1．2．4 禁忌搜索（TS） 4
1．2．5 粒子群優(yōu)化算法（PSO） 4
1．3 CTSP問題的數(shù)學(xué)模型，目前最優(yōu)解 5
1．3．1 CTSP的數(shù)學(xué)建模 5
1．3．2 CTSP目前最優(yōu)解 5
2 用遺傳算法SGA求解CTSP問題 7
2．1 遺傳算法求解框架 7
2．2 種群初始化和計(jì)算適應(yīng)度 8
2．2．1 種群初始化 8
2．2．2 計(jì)算適應(yīng)度 8
2．3 遺傳算子 8
2．3．1 選擇算子 8
2．3．2 交叉算子 8
2．3．3 變異算子 9
2．3．4 終止判斷 9
3 MATLAB簡(jiǎn)介與特點(diǎn) 10
3．1 MATLAB簡(jiǎn)介 10
3．2 MATLAB的特點(diǎn) 10
4 用MATLAB求解CSTP問題 12
4．1 種群初始化 12
4．2 計(jì)算適應(yīng)度 12
4．3　選擇算子 12
4．3．1 計(jì)算選擇算子的過程 12
4．3．2　選擇算子計(jì)算的代碼實(shí)現(xiàn) 13
4．4 交叉算子 15
4．4．1 交叉概率的選擇 15
4．4．2 交叉算法實(shí)現(xiàn) 16
4．5 變異算子 16
4．5．1 變異概率的選擇 16
4．5．2 變異算法實(shí)現(xiàn) 17
4．6 路徑輸出 17
5 實(shí)驗(yàn)結(jié)論及分析 19
5．1 實(shí)驗(yàn)結(jié)論 19
5．2 需要進(jìn)一步解決的問題 20
致 謝 21
主要參考文獻(xiàn) 22