摘要：
本實驗采用遺傳算法實作了旅行商問題的模拟求解，并在同等規模問題上用最小生成樹算法做了一定的對比工作。遺傳算法在計算時間和占用記憶體上，都遠遠優于最小生成樹算法。
程式采用Microsoft visual studio 2008 結合MFC基本對話框類庫開發。32位windows 7系統下調試運作。
引言
遺傳算法（Genetic Algorithm）是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模拟自然進化過程搜尋最優解的方法，由密歇根大學的約翰•霍蘭德和他的同僚于二十世紀六十年代在對細胞自動機（英文：cellular automata）進行研究時率先提出, 并于1975年出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，約翰•霍蘭德教授所提出的GA通常為簡單遺傳算法（SGA）。在二十世紀八十年代中期之前，對于遺傳算法的研究還僅僅限于理論方面，直到在伊利諾伊大學召開了第一屆世界遺傳算法大會。随着計算機計算能力的發展和實際應用需求的增多，遺傳算法逐漸進入實際應用階段。1989年，紐約時報作者約翰•馬科夫寫了一篇文章描述第一個商業用途的遺傳算法--進化者（英文：Evolver）。之後，越來越多種類的遺傳算法出現并被用于許多領域中，财富雜志500強企業中大多數都用它進行時間表安排、資料分析、未來趨勢預測、預算、以及解決很多其他組合優化問題。
遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其内部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特征是由染色體中控制這一特征的某種基因組合決定的。是以，在一開始需要實作從表現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很複雜，我們往往進行簡化，如二進制編碼，初代種群産生之後，按照适者生存和優勝劣汰的原理，逐代（generation）演化産生出越來越好的近似解，在每一代，根據問題域中個體的适應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），産生出代表新的解集的種群。這個過程将導緻種群像自然進化一樣的後生代種群比前代更加适應于環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解[1]。
遺傳算法是借鑒生物界的進化規律（适者生存，優勝劣汰遺傳機制）演化而來的。其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有内在的隐并行性和更好的全局尋優能力；采用機率化的尋優方法，能自動擷取和指導優化的搜尋空間，自适應地調整搜尋方向，不需要确定的規則。遺傳算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信号處理、自适應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。
綜述：
程式總體流程圖：
這個程式的思想是，随機生成“地點數”編輯框輸入的數字的地點，存儲在一個vector裡。然後用一個“基因類”表示該基因代表第幾個點，接着一個“基因組類”有序包含了很多“基因類”，如果一個“基因組類”包含的基因類順序為：基因組.基因[0].data = 第二個點；基因組.基因[1].data = 第三個點；基因組.基因[3].data = 第一個點；就說明該基因組表示的連線順序是從第二點連到第三個點再連到第一個點。給每個城市一個固定的基因編号，例如10個城市為 0 1 2 3 4 5 6 7 8 9 ，随機地組成一個染色體（以下所有情況都以10個城市為例說明）。約定這10個城市之間的行走路線為：
(其餘基因序列的路線同樣道理)
接着有一個“遺傳機器類”包含了很多基因組。基因組的數量由“基因組數”編輯框決定。初始化的時候，每個基因組的基因順序是随機決定的。進行第一代進化的時候，周遊vector<基因組>，計算每個基因組代表的連線方式的連線長度。連線長度越長，說明這個基因組越差勁，因為我們要計算以何種方式連線連線長度最短。
我們用不适應度來記錄連線長度。接着就是選擇哪個基因組可以生育，遺傳給下一代。我采用了一個輪盤賭的政策，盡可能選擇不适應度低的基因組進行生育。選擇出的基因組進行交換變異後，就把這個基因組複制給下一代。
最後，選擇兩個最好的基因組，不進行任何變異，直接複制到下一代。這樣循環反複，疊代“代數”編輯框輸入的代數次數之後，就可以輸出結果了。
結果就是最後一代最優秀的那個基因組代表的連線方式。
主要代碼：
實驗結果：
使用上圖随機生成的節點采用最小生成樹
采用50個基因組，100次疊代進化，0.5的基因變異率
依次生成50個點，100個點，150個點，200個點，250個點的規模問題運作時間的對比：release版本程式
随着節點數的增加遺傳算法的運作時間基本保持在100ms左右
占用記憶體對比：
發現的問題：
1. 雖然遺傳算法在性能上優勢很大，但是有時候基本是收斂在局部最優解上了，找全局最優解需要改進的遺傳算法。
2. 每次發現的解有很大的不确定性，看人品的算法。
未來的工作：
1. 參照《最小生成樹算法在旅行商問題中的應用》實作最小生成樹的TSP解法法。
2. 改進遺傳算法，引入災變的思想，得到全局最優解。
3. 進一步了解其他智能算法的TSP問題解決方案
參考文獻：
1.
<a target="_blank" href="http://simplesource.blog.163.com/blog/static/1034140620076104130312/">點選打開連結</a>
2.
<a target="_blank" href="http://wenku.baidu.com/link?url=rIwbij4RI2FXqCaFVHAOHP1ge-SD51eTLQlR_C5DdqvkT2bBn9irvv-u2PvvLv_krQnytELPR6Z7QnH-AscSXuU_izkucDsHb8Zb7ALH2wW">點選打開連結</a>
工程代碼下載下傳位址：
<a target="_blank" href="http://download.csdn.net/detail/wangyaninglm/6705587">http://download.csdn.net/detail/wangyaninglm/6705587</a>
其他算法：