模拟退火算法求解TSP问题C++.docx
- 文档编号:6856435
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:17
- 大小:140.48KB
模拟退火算法求解TSP问题C++.docx
《模拟退火算法求解TSP问题C++.docx》由会员分享,可在线阅读,更多相关《模拟退火算法求解TSP问题C++.docx(17页珍藏版)》请在冰点文库上搜索。
模拟退火算法求解TSP问题C++
模拟退火算法的应用
—TravellingSalesmanProblem
作为模拟退火算法应用,讨论货郎担问题(TravellingSalesmanProblem,简记为TSP):
设有n个城市,用数码1,…,n代表。
城市i和城市j之间的距离为d(i,j)i,j=1,…,n.TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短.。
将城市编号及其对应的坐标信息放入TSP.txt文件中,由程序读出,进行模拟退火算法的计算,找到最优解并且保存在.txt文本中,涉及到的TSP.txt文本信息格式如下:
主要程序变量定义及其功能函数如下:
//////////////////////////////////////////////////////////////////////////////////////
#include
#include
#include
#include
#include
#include
////////////////////////////////////////////////////////////////////////////////////////
//模板输出函数
template
voidPrint(constT*pData,intnsize)
{
for(inti=0;i { cout<<*(pData++)<<""; } cout< } //////////////////////////////////////////////////////////////////////////////////////// #defineTSPN60//TSP中的城市数目 #defineT_CONST10//初始化温度时给定的常数温度 #defineT_INIT500//初始化温度时给定的初始温度 #defineR_CONST0.9//初始化温度时给定的常数 #defineR_MIN0.05//初始化温度时的终止条件 #defineSTEPN400//初始化温度时退火的迭代步数 #defineK_T0.9//降温时的降温参数 #defineR_ACCEPT0.3//内循环的接受比率指标 #defineT_ZERO0.5//零度法中的最小温度 //解状态,根据不同问题设定 structANSWER { int*pAnswer; double*pData; }; /********************************************************************** *函数名称: TSPRead() *输入参数: *pfile-文件名TSPN *返回值: double*-指向坐标文件的一维数组 *说明: 读取TSP坐标文件 ***********************************************************************/ double*TSPRead(char*pfile) { double*pBuf,dData,*pData; pBuf=newdouble[TSPN*2]; if(pBuf==NULL) { cout<<"分配内存出错! "< exit (1); } memset(pBuf,0,TSPN*2); //读文件 ifstreaminfile(pfile,ios: : in|ios: : nocreate); if(! infile) { cout<<"不能打开文件"< exit (1); } pData=pBuf; for(inti=0;i { infile>>dData;//读出城市序号 for(intj=0;j<2;j++) { if(! (infile>>dData))break; *(pData++)=dData; } } infile.close(); returnpBuf; } /********************************************************************** *函数名称: TSPDistance() *输入参数: xy-城市序号0开始,*pData-城市坐标数组 *返回值: double-两城市间的距离 *说明: 计算两个城市间的距离 ***********************************************************************/ doubleTSPDistance(intx,inty,constdouble*pData) { doubledistance; 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))); returndistance; } /********************************************************************** *函数名称: TSPDeta() *输入参数: *pfile-文件名 *返回值: double-最大距离与最小距离的估计值 *说明: 计算TSP中的最大距离与最小距离的估计值 ***********************************************************************/ doubleTSPDeta(char*pfile) { double*pFile=TSPRead(pfile); Print(pFile,2*TSPN); doubledTmp,dMax,dMin,dSum; dSum=0.0; for(inti=0;i { dMax=TSPDistance(i,(i+1)%TSPN,pFile); dMin=TSPDistance(i,(i+1)%TSPN,pFile); for(intj=1;j { dTmp=TSPDistance(i,(i+1+j)%TSPN,pFile); if(dTmp>dMax)dMax=dTmp; if(dTmp } dSum+=dMax-dMin; } delete[]pFile; pFile=NULL; returndSum; } /********************************************************************** *函数名称: Equal() *输入参数: s0-源目标解s1-目的解 *返回值: *说明: 两个解之间的复制 ***********************************************************************/ voidEqual(ANSWERs1,ANSWERs0) { memcpy(s1.pAnswer,s0.pAnswer,TSPN*sizeof(int)); memcpy(s1.pData,s0.pData,TSPN*2*sizeof(double)); } /********************************************************************** *函数名称: Function() *输入参数: s0-解 *返回值: double-解的函数值 *说明: 求解的函数值 ***********************************************************************/ doubleFunction(ANSWERs0) { doubledFunc; dFunc=0.0; for(inti=0;i { //距离求和 dFunc+=TSPDistance(*(s0.pAnswer),*(s0.pAnswer+1),s0.pData); s0.pAnswer++; } returndFunc; } /********************************************************************** *函数名称: InitAnswer() *输入参数: pfilename-文件名 *返回值: ANSWER-解 *说明: 随机产生一个解 ***********************************************************************/ ANSWERInitAnswer(char*pfilename) { ANSWERs0; s0.pData=TSPRead(pfilename); s0.pAnswer=newint[TSPN]; if(s0.pAnswer==NULL) { cout<<"分配内存出错! "< exit (1); } memset(s0.pAnswer,0,TSPN); int*p,*q,num=0,nflag=0; p=s0.pAnswer; while(true) { intnRand; nRand=rand()%TSPN; q=s0.pAnswer; while(q { if(*(q++)==nRand){nflag=1;break;} } if(nflag==1){nflag=0;continue;} *(p++)=nRand; num++; if(num>=TSPN)break; } returns0; } /********************************************************************** *函数名称: FindNextAnswer() *输入参数: s0-解 *返回值: ANSWER-解 *说明: 在解得邻域找到另一个随机的解 ***********************************************************************/ ANSWERFindNextAnswer(ANSWERs0) { ANSWERanswer; answer.pAnswer=newint[TSPN]; memset(answer.pAnswer,0,sizeof(int)*TSPN); answer.pData=newdouble[TSPN*2]; memset(answer.pData,0,sizeof(double)*TSPN*2); Equal(answer,s0); //逆序操作 intnHead,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 { *pHead=*pHead+*pTail; *pTail=*pHead-*pTail; *pHead=*pHead-*pTail; pHead++; pTail--; } returnanswer; } /********************************************************************** *函数名称: PrintAnswer() *输入参数: s0-解 *返回值: *说明: 输出解 ***********************************************************************/ voidPrintAnswer(ANSWERs0) { cout<<"目标函数值: "< cout<<"城市序列: "; for(inti=0;i { cout<<*(s0.pAnswer++)<<"-->"; } cout<<"END"< } /********************************************************************** *函数名称: Annealing() *输入参数: s0-解t-温度STEPN-宏定义值 *返回值: double-接受状态和迭代步数的比率 *说明: 退火 ***********************************************************************/ doubleAnnealing(ANSWERs0,doublet) { doublerate;//接受状态和迭代步数的比率 intnAccept;//状态接受数 doubledTmp; ANSWERs1; nAccept=0; //退火 for(inti=0;i { s1=FindNextAnswer(s0);//找到下一个解 dTmp=Function(s1)-Function(s0); if(dTmp<=0)//接受 { Equal(s0,s1); nAccept++; } else { doubledRand=double(rand())/RAND_MAX; if(exp(-dTmp/t)>dRand)//接受 { Equal(s0,s1); nAccept++; } } } rate=(double)nAccept/STEPN; delete[]s1.pAnswer; s1.pAnswer=NULL; delete[]s1.pData; s1.pData=NULL; returnrate; } /********************************************************************** *函数名称: InitTemperature() *输入参数: s0-初始解T_INITR_CONSTR_MINT_CONST-宏定义值 *返回值: double-初始温度 *说明: 根据初始解产生初始温度 ***********************************************************************/ doubleInitTemperature(ANSWERs0) { doubleR0=0.0; doubleRk; doublet; intk=0; t=T_INIT; while(true) { Rk=Annealing(s0,t); if(((Rk-R_CONST) if((R0 { 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; } returnt; } /********************************************************************** *函数名称: TSPWrite() *输入参数: *pFile-文件名s0-解TSPN *返回值: *说明: 输出TSP解到文本文件 ***********************************************************************/ voidTSPWrite(char*pFile,ANSWERs0) { ofstreamoutfile(pFile,ios: : app); if(! outfile) { cout<<"不能写入文件"< exit (1); } outfile<<"函数目标值为: "; doubledDistance=Function(s0); outfile< outfile<<"城市序列: "; for(inti=0;i { intnum=*(s0.pAnswer++); outfile< outfile<<"-->"; } outfile<<"END"; outfile<<'\n'; outfile.close(); } /********************************************************************** *函数名称: SA() *输入参数: K_T-宏定义值pfilename-文件名 *返回值: int-时间 *说明: 模拟退火算法 ***********************************************************************/ intSA(char*pfilename) { ANSWERs0,s1,localAnswer; doublet,dTmp; intk,nAccept,nLocal,nIn; localAnswer.pAnswer=newint[TSPN]; memset(localAnswer.pAnswer,0,sizeof(int)*TSPN); localAnswer.pData=newdouble[TSPN*2]; memset(localAnswer.pData,0,sizeof(double)*TSPN*2); time_tt0=clock(); s0=InitAnswer(pfilename);//任选一个初始解 t=InitTemperature(s0);//初始温度 cout<<"初始温度: "< 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<<"得到解,满足零度法! "< if(k>=TSPN*TSPN){cout<<"迭代次数达到上限! "< dTmp=Function(s0)-Function(localAnswer); if(dTmp>=0) { nLoca
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟退火算法求解TSP问题 C+ 模拟 退火 算法 求解 TSP 问题