神经网络解决旅行商问题的VC算法

神经网络课程设计控制科学与工程学院刘玉建200912829旅行商问题(TravellingSalesmanProblem),是数学领域中的一个经典问题.假设一个旅行商要遍布N个城市,如何在每个城市只寻访一遍的前提下使总路程最短是本问题核心所在.本程序采用VisualC++基于对话框构架编制,编制了5个城市节点的TSP问题解决方法.程序中包含遍历算法,模拟退火两种方法,程序界面如图1:图1程序主界面其中界面主要包括如下几个部分:1)城市节点输入部分:城市节点的分布,可以通过以下三种方式:单击城市节点显示部分,通过捕获左键单击,获取城市节点坐标;编辑框中通过输入A-E五个城市的X,Y坐标输入;通过”载入”键,读取txt文档中的坐标数据,数据格式如图2.图2城市坐标格式具体格式为每行对应一个城市坐标,每行数据分别为其X,Y坐标,数据用空格隔开.随意的城市分布,可以通过对应的变化,将坐标范围限制在0-250之间(0).2)城市节点显示部分:左侧的坐标区域,既可以通过捕捉鼠标左键得到城市节点坐标,又可以将城市节点的分布直观的显示出来.3)算法部分:按键”遍历算法”及”模拟退火”,分别对应路径计算的两个算法.输入完5个节点后,便可以通过这两种方法得到运算结果.”重置”按钮,将所有运算数据清零,可以起到程序复位的作用.现分别介绍两个算法的主要部分.1)遍历算法:通过穷举的方法即排列组合的方法,分别计算所有可行的路径并逐一比较,其中最小者,即为符合要求的解法.为简化运算,默认从A城市出发,最终回到A城市,此假设不影响最小路径的生成.遍历算法,当城市节点较少时,可以采用.但当城市增加到一定数目,求解时间难以估计,以指数增长.本程序中,遍历算法如下:voidCTSPDlg::OnCover(){BOOLenPoint=FALSE;//有5个点if(m_nPoint[0].x!=0&&m_nPoint[0].y!=0&&m_nPoint[1].x!=0&&m_nPoint[1].y!=0&&m_nPoint[2].x!=0&&m_nPoint[2].y!=0&&m_nPoint[3].x!=0&&m_nPoint[3].y!=0&&m_nPoint[4].x!=0&&m_nPoint[4].y!=0){enPoint=TRUE;}if(enPoint)//当城市节点数目达到要求时,方可执行运算{inti,j,k,l;//辅助完成遍历算法inttempDist;//每次遍历的当前路径长度m_nCityh=0;NDistance=0;for(i=0;i4;i++){NDistance+=Distance(m_nPoint[i],m_nPoint[i+1]);}NDistance+=Distance(m_nPoint[4],m_nPoint[0]);//以A-..-E-A为初值for(i=1;i=4;i++){for(j=1;j=4;j++){if(j!=i){for(k=1;k=4;k++){if(k!=i&&k!=j){for(l=1;l=4;l++){if(l!=i&&l!=j&&l!=k){tempDist=Distance(m_nPoint[0],m_nPoint[i])+Distance(m_nPoint[i],m_nPoint[j])+Distance(m_nPoint[j],m_nPoint[k])+Distance(m_nPoint[k],m_nPoint[l])+Distance(m_nPoint[l],m_nPoint[0]);if(tempDist=NDistance)//如果当前路径{//更小,则保存NDistance=tempDist;m_nCityi=i;m_nCityj=j;m_nCityk=k;m_nCityl=l;}}}}}}}}m_nResultDist=NDistance;m_bRouterPaint=TRUE;//路径计算完毕,可以绘制Invalidate();}}程序运行结果如图3.图3遍历算法解决TSP问题2)模拟退火:模拟退火方法是解决TSP问题的有效方法之一,算法来源于固体退火原理.将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小.用固体退火模拟组合优化问题,将内能E模拟为目标函数值f，温度T演化成控制参数t.即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始,对当前解重复”产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值，算法终止时的当前解即为所得近似最优解.求解TSP的模拟退火算法模型可描述如下:解空间:解空间S是遍访每个城市恰好一次的所有路经，解可以表示为{w1,w2,……,wn},w1,……,wn是1,2,……,n的一个排列,表明w1城市出发,依次经过w2,……,wn城市,再返回w1城市.初始解可选为(1,……,n).目标函数:目标函数为访问所有城市的路径总长度.我们要求的最优路径为目标函数为最小值时对应的路径.新路径的产生:随机产生1和n之间的两相异数k和m,则将原路径(w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn)变为新路径:(w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射.本程序中,遍历算法如下:voidCTSPDlg::OnSimAnn(){BOOLenPoint=FALSE;//有5个点if(m_nPoint[0].x!=0&&m_nPoint[0].y!=0&&m_nPoint[1].x!=0&&m_nPoint[1].y!=0&&m_nPoint[2].x!=0&&m_nPoint[2].y!=0&&m_nPoint[3].x!=0&&m_nPoint[3].y!=0&&m_nPoint[4].x!=0&&m_nPoint[4].y!=0){enPoint=TRUE;}if(enPoint){intMaxDist;//最大城市间距离intMinDist;//最小城市间距离doubleNowTemp;//当前温度值温度doubleexpJudge;//第二次判断用intInnerLoop;//内层循环intNowRouter[5]={0,1,2,3,4};intNewRouter[5]={0,1,2,3,4};intSubRouter;//路径差值inti;//城市两两之间的距离矩阵intDistMatirc[10]={Distance(m_nPoint[0],m_nPoint[1]),Distance(m_nPoint[0],m_nPoint[2]),Distance(m_nPoint[0],m_nPoint[3]),Distance(m_nPoint[0],m_nPoint[4]),Distance(m_nPoint[1],m_nPoint[2]),Distance(m_nPoint[1],m_nPoint[3]),Distance(m_nPoint[1],m_nPoint[4]),Distance(m_nPoint[2],m_nPoint[3]),Distance(m_nPoint[2],m_nPoint[4]),Distance(m_nPoint[3],m_nPoint[4])};for(i=0,MaxDist=DistMatirc[0],MinDist=DistMatirc[0];i10;i++){if(DistMatirc[i]MaxDist)MaxDist=DistMatirc[i];if(DistMatirc[i]MinDist)MinDist=DistMatirc[i];}NowTemp=20*(MaxDist-MinDist);//初始温度for(;NowTemp=0.01;){for(InnerLoop=0;InnerLoop125;InnerLoop++)//内层计数(5*5*5){RouteSwap(&NewRouter[0]);//2-OPT法产生新路径SubRouter=(Distance(m_nPoint[NewRouter[0]],m_nPoint[NewRouter[1]])+Distance(m_nPoint[NewRouter[1]],m_nPoint[NewRouter[2]])+Distance(m_nPoint[NewRouter[2]],m_nPoint[NewRouter[3]])+Distance(m_nPoint[NewRouter[3]],m_nPoint[NewRouter[4]])+Distance(m_nPoint[NewRouter[4]],m_nPoint[NewRouter[0]]))-(Distance(m_nPoint[NowRouter[0]],m_nPoint[NowRouter[1]])+Distance(m_nPoint[NowRouter[1]],m_nPoint[NowRouter[2]])+Distance(m_nPoint[NowRouter[2]],m_nPoint[NowRouter[3]])+Distance(m_nPoint[NowRouter[3]],m_nPoint[NowRouter[4]])+Distance(m_nPoint[NowRouter[4]],m_nPoint[NowRouter[0]]));if(SubRouter0)//如果新路径短于原来路径{for(i=0;i5;i++){NowRouter[i]=NewRouter[i];}}else{//虽然新路径比原来的长,但expJudge值0-1之间的随机数expJudge=exp(-(SubRouter/NowTemp));if(expJudge((rand()%10000)/10000.0)){for(i=0;i5;i++){NowRouter[i]=NewRouter[i];}}}}NowTemp*=0.9;//退温}m_nResultDist=Distance(m_nPoint[NowRouter[0]],m_nPoint[NowRouter[1]])+Distance(m_nPoint[NowRouter[1]],m_nPoint[NowRouter[2]])+Distance(m_nPoint[NowRouter[2]],m_nPoint[NowRouter[3]])+Distance(m_nPoint[NowRouter[3]],m_nPoint[NowRouter[4]])+Distance(m_nPoint[NowRouter[4]],m_nPoint[NowRouter[0]]);m_nCityh=NowRouter[0];m_nCityi=NowRouter[1];m_nCityj=NowRouter[2];m_nCityk=NowRouter[3];m_nCityl=NowRouter[4];m_bRouterPaint=TRUE;Invalidate();}}程序运行结果如图4.图4模拟退火算法解决TSP问题由于节点较少的问题,本程序中模拟退火解决问题的速度优越性并未体现,但通过之前的研究数据,我们可以知道,基于模拟退火算法的TSP问题解决方案能保证得到近似最优解的前提下,大大提升运算速度,具有遍历法无法比拟的优越性.本程序调试环境:WindowsXPSP3Pro+VisualC++6.0.完整代码下载：