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

模拟退火算法求解TSP问题C++模拟退火算法求解TSP问题C++ 模拟退火算法的应用 —Travelling Salesman Problem 作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem， :设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离简记为TSP) 为d(i，j) i, j=1,…,n(TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。将城市编号及其对应的坐标信息放入TSP.txt文件中，由程序读出，进行模拟退火算法的计算，找到最优解并且保存在.tx...

模拟退火算法求解TSP问题C++ 模拟退火算法的应用 —Travelling Salesman Problem 作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem， :设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离简记为TSP) 为d(i，j) i, j=1,…,n(TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。将城市编号及其对应的坐标信息放入TSP.txt文件中，由程序读出，进行模拟退火算法的计算，找到最优解并且保存在.txt文本中，涉及到的TSP.txt文本信息格式如下: 主要程序变量定义及其功能函数如下: ////////////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include //////////////////////////////////////////////////////////////////////////////////////// // 模板输出函数 template void Print(const T *pData, int nsize) { for (int i=0; i> dData; // 读出城市序号 for (int j=0; j<2; j++) { if (!(infile >> 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; i 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; i= TSPN) break; } return s0; } /********************************************************************** * 函数名称:FindNextAnswer() * 输入参数:s0 -解 * 返回值:ANSWER -解 * 说明:在解得邻域找到另一个随机的解 ***********************************************************************/ ANSWER FindNextAnswer(ANSWER s0) { ANSWER answer; answer.pAnswer = new int[TSPN]; memset(answer.pAnswer, 0, sizeof(int)*TSPN); answer.pData = new double[TSPN*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; i "; } 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; i 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) && ((Rk-R_CONST) > -R_MIN)) break; if ((R0 < R_CONST) && (Rk < R_CONST)) { k++; t = t + T_CONST; } if ((R0 >= 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) && (Rk >= 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; i"; } 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 int[TSPN]; memset(localAnswer.pAnswer, 0, sizeof(int)*TSPN); localAnswer.pData = new double[TSPN*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 <= 0) // 接受 { Equal(s0, s1); nAccept++; } else { if (exp(-dTmp/t) > double(rand())/RAND_MAX) // 接受 { Equal(s0, s1); nAccept++; } } nIn++; // 内循环终止条件 if (nIn <= TSPN) { if ((double)nAccept / TSPN >= R_ACCEPT) { break; } } if (nAccept >= 2*TSPN) { break; } } t = K_T * t; // 降温 k++; // 外循环终止条件 if (t <= T_ZERO) { cout << "得到解，满足零度法!" << endl; break; } if (k >= TSPN*TSPN) { cout << "迭代次数达到上限～" << endl; break; } dTmp = Function(s0) - Function(localAnswer); if (dTmp >= 0) { nLocal++; if (nLocal >= TSPN) { cout << "陷入局部最优!" << endl; break;} } else { nLocal = 0; Equal(localAnswer, s0); } } time_t t1 = clock(); PrintAnswer(localAnswer); TSPWrite("XXX.txt", localAnswer); delete [] s0.pAnswer; s0.pAnswer = NULL; delete [] s0.pData; s0.pData = NULL; delete [] s1.pAnswer; s1.pAnswer = NULL; delete [] s1.pData; s1.pData = NULL; delete [] localAnswer.pAnswer; localAnswer.pAnswer = NULL; delete [] localAnswer.pData; localAnswer.pData = NULL; return t1 - t0; } ///////////////////////////////////////////////////////////////////////////////////////// // main void main(void) { srand((unsigned)time(NULL)); char filename[64] = "TSP.txt"; int time = SA(filename); cout << "处理时间:" << time << "ms" <

                    本文档为【模拟退火算法求解TSP问题C++】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

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

你可能还喜欢