模拟退火算法求解TSP问题C++Word文档格式.docx
- 文档编号:8238037
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:17
- 大小:140.48KB
模拟退火算法求解TSP问题C++Word文档格式.docx
《模拟退火算法求解TSP问题C++Word文档格式.docx》由会员分享,可在线阅读,更多相关《模拟退火算法求解TSP问题C++Word文档格式.docx(17页珍藏版)》请在冰点文库上搜索。
}
#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)
分配内存出错!
"
<
exit
(1);
memset(pBuf,0,TSPN*2);
//读文件
ifstreaminfile(pfile,ios:
:
in|ios:
nocreate);
if(!
infile)
不能打开文件"
}
pData=pBuf;
TSPN;
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;
dMax=TSPDistance(i,(i+1)%TSPN,pFile);
dMin=TSPDistance(i,(i+1)%TSPN,pFile);
for(intj=1;
TSPN-1;
dTmp=TSPDistance(i,(i+1+j)%TSPN,pFile);
if(dTmp>
dMax)dMax=dTmp;
if(dTmp<
dMin)dMin=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;
//距离求和
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)
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<
p)
if(*(q++)==nRand){nflag=1;
break;
if(nflag==1){nflag=0;
continue;
*(p++)=nRand;
num++;
if(num>
=TSPN)break;
returns0;
FindNextAnswer()
在解得邻域找到另一个随机的解
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<
pTail)
*pHead=*pHead+*pTail;
*pTail=*pHead-*pTail;
*pHead=*pHead-*pTail;
pHead++;
pTail--;
returnanswer;
PrintAnswer()
输出解
voidPrintAnswer(ANSWERs0)
目标函数值:
Function(s0)<
城市序列:
*(s0.pAnswer++)<
-->
END"
Annealing()
s0-解t-温度STEPN-宏定义值
double-接受状态和迭代步数的比率
退火
doubleAnnealing(ANSWERs0,doublet)
doublerate;
//接受状态和迭代步数的比率
intnAccept;
//状态接受数
doubledTmp;
ANSWERs1;
nAccept=0;
//退火
STEPN;
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;
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))
t=t-T_CONST;
t=t+(double)T_CONST/2;
t=t-(double)T_CONST/2;
R0=Rk;
returnt;
TSPWrite()
*pFile-文件名s0-解TSPN
输出TSP解到文本文件
voidTSPWrite(char*pFile,ANSWERs0)
ofstreamoutfile(pFile,ios:
app);
outfile)
不能写入文件"
outfile<
函数目标值为:
doubledDistance=Function(s0);
dDistance<
'
\n'
intnum=*(s0.pAnswer++);
outfile<
num;
-->
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);
//初始温度
初始温度:
t<
Equal(localAnswer,s0);
k=0;
nLocal=0;
//外循环
nAccept=0;
nIn=0;
//内循环
while(true)
s1=FindNextAnswer(s0);
dTmp=Function(s1)-Function(s0);
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 问题