模拟退火算法求解TSP问题C++.doc

模拟退火算法的应用 Travelling Salesman Problem 作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,n代表。城市i和城市j之间的距离为d(i，j) i, j=1,nTSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。 将城市编号及其对应的坐标信息放入TSP.txt文件中，由程序读出，进行模拟退火算法的计算，找到最优解并且保存在.txt文本中，涉及到的TSP.txt文本信息格式如下：主要程序变量定义及其功能函数如下：/#include #include #include #include #include #include / 模板输出函数template void Print(const T *pData, int nsize)for (int i=0; insize; i+)cout *(pData+) ;cout endl;/#define TSPN 60 / TSP中的城市数目#define T_CONST 10 / 初始化温度时给定的常数温度#define T_INIT 500 / 初始化温度时给定的初始温度 #define R_CONST 0.9 / 初始化温度时给定的常数#define R_MIN 0.05 / 初始化温度时的终止条件#define STEPN 400 / 初始化温度时退火的迭代步数#define K_T 0.9 / 降温时的降温参数#define R_ACCEPT 0.3 / 内循环的接受比率指标#define T_ZERO 0.5 / 零度法中的最小温度/ 解状态，根据不同问题设定struct ANSWERint *pAnswer;double *pData;/* 函数名称：TSPRead()* 输入参数：*pfile -文件名 TSPN* 返回值：double* -指向坐标文件的一维数组* 说明：读取TSP坐标文件*/double* TSPRead(char *pfile)double *pBuf, dData, *pData;pBuf = new doubleTSPN*2;if (pBuf = NULL)cout 分配内存出错！ endl;exit(1);memset(pBuf, 0, TSPN*2);/ 读文件ifstream infile(pfile, ios:in|ios:nocreate);if (!infile)cout 不能打开文件 endl;exit(1);pData = pBuf;for (int i=0; i dData; / 读出城市序号for (int j=0; j dData) break;*(pData+) = dData;infile.close();return pBuf;/* 函数名称：TSPDistance()* 输入参数：x y -城市序号0开始， *pData -城市坐标数组* 返回值：double -两城市间的距离* 说明：计算两个城市间的距离*/double TSPDistance(int x, int y, const double *pData)double distance;distance = sqrt(*(pData+x*2) - *(pData+y*2) * (*(pData+x*2) - *(pData+y*2) +(*(pData+x*2+1) - *(pData+y*2+1) * (*(pData+x*2+1) - *(pData+y*2+1);return distance;/* 函数名称：TSPDeta()* 输入参数：*pfile -文件名* 返回值：double -最大距离与最小距离的估计值* 说明：计算TSP中的最大距离与最小距离的估计值*/double TSPDeta(char *pfile)double *pFile = TSPRead(pfile);Print(pFile, 2*TSPN);double dTmp, dMax, dMin, dSum;dSum = 0.0;for (int i=0; iTSPN; i+)dMax = TSPDistance(i, (i+1)%TSPN, pFile);dMin = TSPDistance(i, (i+1)%TSPN, pFile);for (int j=1; j dMax) dMax = dTmp;if (dTmp dMin) dMin = dTmp;dSum += dMax - dMin;delete pFile;pFile = NULL;return dSum;/* 函数名称：Equal()* 输入参数：s0 -源目标解 s1 -目的解* 返回值：* 说明：两个解之间的复制*/void Equal(ANSWER s1, ANSWER s0)memcpy(s1.pAnswer, s0.pAnswer, TSPN * sizeof(int);memcpy(s1.pData, s0.pData, TSPN * 2 * sizeof(double);/* 函数名称：Function()* 输入参数：s0 -解* 返回值：double -解的函数值* 说明：求解的函数值*/double Function(ANSWER s0)double dFunc;dFunc = 0.0;for (int i=0; iTSPN-1; i+)/ 距离求和dFunc += TSPDistance(*(s0.pAnswer), *(s0.pAnswer + 1), s0.pData);s0.pAnswer+;return dFunc;/* 函数名称：InitAnswer()* 输入参数：pfilename -文件名* 返回值：ANSWER -解* 说明：随机产生一个解*/ANSWER InitAnswer(char *pfilename)ANSWER s0;s0.pData = TSPRead(pfilename);s0.pAnswer = new intTSPN;if (s0.pAnswer = NULL)cout 分配内存出错！ endl;exit(1);memset(s0.pAnswer, 0, TSPN);int *p, *q, num = 0, nflag = 0;p = s0.pAnswer;while (true)int nRand;nRand = rand() % TSPN;q = s0.pAnswer;while (q = TSPN) break;return s0;/* 函数名称：FindNextAnswer()* 输入参数：s0 -解* 返回值：ANSWER -解* 说明：在解得邻域找到另一个随机的解*/ANSWER FindNextAnswer(ANSWER s0)ANSWER answer;answer.pAnswer = new intTSPN;memset(answer.pAnswer, 0, sizeof(int)*TSPN);answer.pData = new doubleTSPN*2;memset(answer.pData, 0, sizeof(double)*TSPN*2);Equal(answer, s0);/ 逆序操作int nHead, nTail, *pHead, *pTail;nHead = rand() % TSPN;do nTail = rand() % TSPN; while (nTail = nHead);if (nHead nTail)nHead = nHead + nTail;nTail = nHead - nTail;nHead = nHead - nTail;pHead = answer.pAnswer + nHead;pTail = answer.pAnswer + nTail;while (pHead pTail)*pHead = *pHead + *pTail;*pTail = *pHead - *pTail;*pHead = *pHead - *pTail;pHead+;pTail-;return answer;/* 函数名称：PrintAnswer()* 输入参数：s0 -解* 返回值：* 说明：输出解*/void PrintAnswer(ANSWER s0)cout 目标函数值： Function(s0) endl;cout 城市序列：;for (int i=0; iTSPN; i+)cout *(s0.pAnswer+) ;cout END endl;/* 函数名称：Annealing()* 输入参数：s0 -解 t -温度 STEPN -宏定义值* 返回值：double -接受状态和迭代步数的比率* 说明：退火*/double Annealing(ANSWER s0, double t)double rate; / 接受状态和迭代步数的比率int nAccept; / 状态接受数double dTmp;ANSWER s1;nAccept = 0;/ 退火for (int i=0; iSTEPN; i+)s1 = FindNextAnswer(s0); / 找到下一个解dTmp = Function(s1) - Function(s0);if (dTmp dRand) / 接受Equal(s0, s1);nAccept+;rate = (double)nAccept / STEPN;delete s1.pAnswer;s1.pAnswer = NULL;delete s1.pData;s1.pData = NULL;return rate;/* 函数名称：InitTemperature()* 输入参数：s0 -初始解 T_INIT R_CONST R_MIN T_CONST -宏定义值* 返回值：double -初始温度* 说明：根据初始解产生初始温度*/double InitTemperature(ANSWER s0)double R0 = 0.0;double Rk;double t;int k = 0;t = T_INIT;while (true)Rk = Annealing(s0, t);if (Rk-R_CONST) -R_MIN) break;if (R0 R_CONST) & (Rk = R_CONST) & (Rk = R_CONST)k+;t = t - T_CONST;if (R0 = R_CONST) & (Rk = R_CONST)k+;t = t + (double)T_CONST / 2;if (R0 = R_CONST)k+;t = t - (double)T_CONST / 2;R0 = Rk;return t;/* 函数名称：TSPWrite()* 输入参数：*pFile -文件名 s0 -解 TSPN* 返回值：* 说明：输出TSP解到文本文件*/void TSPWrite(char *pFile, ANSWER s0)ofstream outfile(pFile, ios:app);if (!outfile)cout 不能写入文件 endl;exit(1);outfile 函数目标值为：;double dDistance = Function(s0);outfile dDistance n;outfile 城市序列：;for (int i=0; iTSPN; i+)int num = *(s0.pAnswer+);outfile num;outfile ;outfile END;outfile n;outfile.close();/* 函数名称：SA()* 输入参数：K_T -宏定义值 pfilename -文件名* 返回值：int -时间* 说明：模拟退火算法*/int SA(char *pfilename)ANSWER s0, s1, localAnswer;double t, dTmp;int k, nAccept, nLocal, nIn;localAnswer.pAnswer = new intTSPN;memset(localAnswer.pAnswer, 0, sizeof(int)*TSPN);localAnswer.pData = new doubleTSPN*2;memset(localAnswer.pData, 0, sizeof(double)*TSPN*2);time_t t0 = clock();s0 = InitAnswer(pfilename); / 任选一个初始解t = InitTemperature(s0); / 初始温度cout 初始温度： t endl;Equal(localAnswer, s0);k = 0;nLocal = 0;/ 外循环while (true)nAccept = 0;nIn = 0;/ 内循环while (true)s1 = FindNextAnswer(s0);dTmp = Function(s1) - Function(s0);if (dTmp double(rand()/RAND_MAX) / 接受Equal(s0, s1);nAccept+;nIn+;/ 内循环终止条件if (nIn = R_ACCEPT) break; if (nAccept = 2*TSPN) break; t = K_T * t; / 降温k+;/ 外循环终止条件if (t