利用遺傳算法求解了48個城市的TSP問題(VC++ 代碼)

在Visual C++ 編譯環境下，遺傳算法的程序，并利用它們求解了48個城市的TSP問題。~..~

程序說明
由于篇幅有限，且程序中還包括界面實現和計算線程處理等一些與算法無關的代碼。為方便閱讀，程序清單只介紹實現算法的流程控制函數和一些功能函數，具體的代碼可參見源程序。
為了將算法和程序界面分離，程序將算法功能用DLL方式進行封裝。遺傳算法的源程序分別在[TspGA]和[GAApp]目錄中，與算法相關的代碼主要在如下三個文件中：
1）gacode.h 算法中所需結構體的定義，包括SYCoordinate、SYCity、SYCityDistance、SYRouter
2） gacode.cpp 算法中所有功能函數的實現，主要包括InitialGA、CountCityDistance、CreateCityRouter2opt、CountTotalDistance、CreateFitnessofPop、SelectPop、CrossoverPop、Crossover、MutationPop、OneIterGACompution等等。后面將分別介紹這些功能函數的作用。
3）MainFrm.cpp流程控制函數的實現，該函數是GACompution。后面將詳細介紹該函數的流程。

流程控制函數和功能函數的介紹
流程控制函數GACompution控制循環的迭代和結束，其主要代碼如下：
UINT GACompution(LPVOID pParam)
{
int totalgen = GetTotalGeneration(); //獲取遺傳算法的迭代總代數
int nowiter = 0;
while( nowiter <= totalgen && nowiter >= 0 ) //判斷迭代次數是否大于迭代總代數，大于則停止計算
{
nowiter = OneIterGACompution(); //進行一代計算，包括競爭選擇、交叉和變異
}
}
下面是一些重要的功能函數的說明：
OneIterGACompution() 最重要的功能函數是，它完成一代的計算，包括競爭選擇、交叉和變異，在gacode.cpp中實現，其主要代碼如下
int OneIterGACompution()
{
CreateFitnessofPop(FITNESS_MODE); //為每個染色體計算評價函數
SelectPop(); //群體競爭選擇
CrossoverPop(CROSSOVER_MODE); //種群交叉
MutationPop(MUTATION_MODE); //種群變異
NowGenNumber++; //當前代數遞增
return NowGenNumber;
}
CreateFitnessofPop() 對群體中的每個染色體計算適應函數/評價函數，采用基于序的計算方法。
SelectPop() 輪盤賭方式競爭選擇染色體。
Crossover() 兩染色體的交叉實現，提供兩種交叉方式，分別如下：
1、常規交叉方式，該方式比《現代計算方法》（邢文訓等編著）p178給出的"非常規碼的常規交配法"稍復雜些。書中只隨機選擇一個交配位，兩個后代交配位之前的基因分別繼承雙親的交配位之前的基因。本程序中，是隨機選擇兩個不相同的交配位，后代在這兩個交配位之間繼承雙親在這兩個交配位之間的基因
如 父A 1 2 3 | 4 5 6 7 | 8 9 10
  父B 4 7 8 | 3 2 5 9 | 1 6 10
  子A 8 3 2 | 4 5 6 7 | 9 1 10
  子B 1 4 6 | 3 2 5 9 | 7 8 10
2、貪心交叉方式（Greedy Crossover），具體算法可參見 謝勝利等.求解TSP問題的一種改進的遺傳算法. 計算機工程與應用, 2002(8):58～245。
CrossoverPop() 種群交叉。
MutationPop() 種群變異，提供兩種變異方式，一是取兩個不同的隨機數，對這兩個數確定的基因區間進行隨機排序；二是在染色體的2-opt鄰域中隨機取出一個染色體。

程序使用方法
程序處理的TSP問題可按用戶的具體要求，只需用戶依照格式要求提供城市坐標文件即可，坐標文件的格式如下
1 6734 1453
2 2233 10
3 5530 1424
……………
文件的每一行表示一個城市的信息，即，城市名稱+空格+X坐標+空格+Y坐標。
點擊菜單欄的[文件]-[打開…]，可打開指定的城市坐標文件。
指點城市文件打開后，程序會讀入文件里的各城市坐標信息，并初始化城市距離矩陣。
點擊菜單欄的[文件]-[開始計算]，即可進行計算。
城市計算結束后，會在C盤的根目錄生成兩個文件，一是gacitysfile.txt，它記錄了計算得到的最優路徑信息；二是gaitersfile.txt，它記錄了計算過程中的迭代信息。
可利用作者提供的Matlab的M文件gatspsta.m讀取以上兩個文件，畫出路徑優化過程圖和求解路徑圖。

程序算例
程序對48個城市的TSP問題（城市坐標文件對應于48.txt）進行計算，求解路徑和最優路徑圖如下。
48個城市結果，大的紅*表示路徑開始城市，途經城市依次用藍色方塊和紅色*標示，下同。