基于遺傳算法的tsp問題研究(一)

基于遺傳算法的tsp問題研究

一、論文觀點來源

TSP問題又稱為貨郎擔問題。TSP是一個典型的優化組合問題，它需要求出旅行商從某一城市出發經過所有城市所走路程的最短路徑，其可能的路徑數與城市個數成指數關系增長。找出有效的近似求解算法具有重要的意義。

選擇用遺傳算法去解決TSP問題。本論文對各個算子分別選擇的是基于序的評估函數、輪盤賭選擇法、兩點交叉法、兩點區間隨機排序變異法，并且通過30個城市的實際的例子來驗證，結果求出最短路徑為421.5977，優于二叉樹描述法的結果428.90，啟發式搜索法的結果436.01，表明遺傳算法在求解TSP問題上是有效的。

二、論文基本觀點

以遺傳算法的思想去解決TSP問題，即要在眾多的城市路徑中找到一個最短的，我們模擬生物進化的程序，即遺傳的方式，我們先以一定的方式生成一個初始化群體，為每個染色體計算評價函數，然后群體競爭選擇，種群交叉種群變異，如此迭代下去直到迭代代數達到要求找到最短的路徑。

三、論文主要內容結構

1、算法設計

目前，求解TSP問題的較為常用的方法有二叉樹描述法、啟發式搜索法、最近鄰法、神經網絡法、模擬退火法、遺傳算法等。遺傳算法是模擬生物在自然界中的遺傳和進化過程而形成的一種自適應全局概率搜索算法，具有良好的全局尋優能力，成為解決TSP問題的有效方法之一。

2、遺傳編碼

遺傳算法的編碼時將待求問題的解的形式變換成遺傳算法所面對的基本編碼竄對象，以便于遺傳運算。對于最短路徑問題，其可行解的形式一般為結點下標聯結成的數字串，因此在遺傳算法中的編碼方式一般為符號編碼。具體可以分為以下幾種：近鄰編碼、序編碼(Grefenstette 編碼)、邊編碼、自然編碼等。在本設計中用到的是自然編碼。

本系統使用vc++編寫，將遺傳算法和界面程序分開編寫，這樣修改起來就比較方便，并且程序的結構看起來也很清晰，理解也很容易。在本程序中有一個功能模塊，通過這個模塊我們可以讀取已經保存好在文件中的城市坐標文件，然后可以通過運行遺傳算法來計算給出的數據并得出所要求的結果。

本論文通過調用OpenDataFile（）函數讀取城市坐標信息。該函數輸入參數是strFileName，表示文件名稱字符串引用，函數返回值是文件中所含城市個數。其中，城市坐標文件的格式要求為：

城市名稱  X軸坐標  Y軸坐標

讀取城市坐標文件的內容到一個容器名為vecCity的結構中，主要代碼如圖2.1所示。