#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?

#define?PMX
#define?PC????????0.70????????????//雜交率
#define?PM????????0.04?????????????//變異率
#define?CITY_SIZE?50??????????????//城市數(shù)
#define?POP_SIZE??1000??????????????//種群規(guī)模
#define?NEW_SIZE??（POP_SIZE/2）??????//用于重組的個體數(shù)
#define?GEN_TOTAL?10000?????????????//總遺傳代數(shù)

void?Initialize（int?Pop[][CITY_SIZE]?int?Count）;
void?Evaluate（int?Pop[][CITY_SIZE]?int?EvalVal[]?int?Count）;
void?ParentSelect（int?Pop[][CITY_SIZE]?int?EvalVal[]?int?Count）;
void?Recombine（int?Pop[][CITY_SIZE]?int?Count）;
void?Mutate（int?Pop[][CITY_SIZE]?int?Count）;
int??GetBestPathIndex（int?EvalVal[]?int?Count）;
void?ShowBestResult（int?Path[]?int?Len?int?Gen）;
void?ShowPath（int?Path[][CITY_SIZE]?int?Count）;
void?TSPProc（）;

int?main（int?argc?char?*argv[]）
{
??void?TSPProc（）;
??TSPProc（）;
??printf（“\nFinish?searching!“）;
??getch（）;
??return?0;
}

void?TSPProc（）
{
??//使用一個整型數(shù)組表示每條路徑??
??int?Pop[POP_SIZE][CITY_SIZE];
??int?BestEval?BestPath[CITY_SIZE];
??//對路徑的評估使用整型數(shù)表示，忽略小數(shù)部分
??int?EvalVal[POP_SIZE];

??Initialize（Pop?POP_SIZE）;
??Evaluate（Pop?EvalVal?POP_SIZE）;
??
??int?t?=?GetBestPathIndex（EvalVal?POP_SIZE）;??
??memmove（BestPath?Pop[t]?sizeof（int）?*?CITY_SIZE）;
??BestEval?=?EvalVal[t];
??ShowBestResult（BestPath?BestEval?0）;

??t?=?1;
??while（t???{
????ParentSelect（Pop?EvalVal?POP_SIZE）;
????Recombine（Pop?POP_SIZE）;
????Mutate（Pop?POP_SIZE）;
????Evaluate（Pop?EvalVal?POP_SIZE）;

????printf（“\rCurrent?generation:%d“?t）;
????int?Index?=?GetBestPathIndex（EvalVal?POP_SIZE）;
????if（EvalVal[Index]?????{??????
??????BestEval?=?EvalVal[Index];
??????memmove（BestPath?Pop[Index]?sizeof（int）?*?CITY_SIZE）;
??????printf（“\r“）;
??????ShowBestResult（BestPath?BestEval?t）;
????}????
????t++;
??}
}

//初始化種群
void?Initialize（int?Pop[][CITY_SIZE]?int?Count）
{
??int?i?j;
??int?Seed[CITY_SIZE];??

??srand（time（NULL））;
??for（i?=?0;?i???{
????for（j?=?0;?j???????Seed[j]?=?j;?

????//隨機產(chǎn)生一條路徑
????for（j?=?0;?j?????{
??????int?RandIdx?=?rand（）?%?（CITY_SIZE?-?j）;
??????Pop[i][j]?=?Seed[RandIdx];
??????Seed[RandIdx]?=?Seed[CITY_SIZE?-?j?-?1];
????}
??}
}

//評估路徑Pop，結(jié)果放入EvalVal
void?Evaluate（int?Pop[][CITY_SIZE]?int?EvalVal[]?int?Count）
{
??static?int?Matrix[CITY_SIZE][CITY_SIZE];
??static?bool?bInitMatrix;

??int?i?j;
??char?Str[256];
??//先檢查鄰接矩陣是否已初始化
??if（!bInitMatrix）
??{
????bool?bInit?=?false;
????FILE?*pFile?=?fopen（“d:\\tsp.txt“?“r“）;
????if（pFile）
????{
??????bInit?=?true;
??????for（i?=?0;?i???????{
????????for（j?=?0;?j?????????{??????????
??????????if（!fgets（Str?64?pFile））
??????????{
????????????bInit?=?false;
????????????break;
??????????}
??????????Matrix[i][j]?=?atoi（Str）;//將字符串轉(zhuǎn)換