1．内容：
在Visual C++ 编译环境下，模拟退火算法程序，并利用它们求解了48个城市的TSP问题。
2．程序说明
由于篇幅有限，且程序中还包括界面实现和计算线程处理等一些与算法无关的代码。为方便阅读，程序清单只介绍实现算法的流程控制函数和一些功能函数，具体的代码可参见源程序。
模拟退火算法的源程序在[TspSA]目录中，与算法相关的代码主要在如下三个文件中：
1）sacode.h 算法中所需结构体的定义，包括SYCoordinate、SYCity、SYCityDistance、SYRouter。
2） sacode.cpp 算法中所有功能函数的实现，主要包括InitialSA、CountCityDistance、CreateCityRouter2opt、CountTotalDistance、CountDownTemperature等等。后面将分别介绍这些功能函数的作用。
3）MainFrm.cpp流程控制函数的实现，该函数是SACompution。后面将详细介绍该函数的流程。
流程控制函数和功能函数的介绍
流程控制函数SACompution控制循环的迭代和结束，其主要代码如下：
UINT SACompution(LPVOID pParam)
{
while(1) { double deltatotaldis = 0.0; while(1) {
SYRouter SelRouter( ResultRouter.m_CityRouter, NowTemperature, NowExternalIterNumber, NowInnerIterNumber ); //从某路径的邻域中随机选择一个新的路径，邻域映射为2-opt
deltatotaldis = SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance; //计算新路径与当前路径的路程长度差值 if( deltatotaldis random ) ResultRouter = SelRouter; //如果新路径长于当前路径，但exp(-Δf/t) > random(0,1)，则仍然替换当//如果新路径的路程短，则用它替换当前路径 前路径 } if( JudgeOverInnerLoop(0) ) break; //判断内循环是否结束，结束则跳出当前温度的内循环
else NowInnerIterNumber++; //判断内循环是否结束，不结束则继续内循环 } if( JudgeOverExternalLoop(0) ) break; //判断外循环是否结束，结束则结束模拟退火计算 else { } NowTemperature = CountDownTemperature( NowTemperature, 0 ); NowExternalIterNumber++; NowInnerIterNumber = 0; //判断外循环是否结束，不结束则计算出下降后的温度，并继续循环
}
}
SACompution有两个while循环，分别对应模拟退火算法中的某一温度下的内循环和温度下降的外循环。为阅读方便，各步骤代码说明已用注释方式写在相应的位置，下同。
下面是一些重要的功能函数的说明：
InitialSA() 模拟退火算法的初始化，包括两部分工作，一是根据直角坐标生成城市距离矩阵；二是计算初始温度。
CountCityDistance() 计算城市之间的距离。
CountInitialTemperatureMaxMin() 计算起始温度，计算方法请参见《现代优化计算方法》（邢文训等编著） p117。
CreateCityRouter2opt() 从某路径的邻域中随机选择一个新的路径，邻域映射为2-opt。 CountTotalDistance() 根据给定路径计算该路径对应的总路程。
CountDownTemperature() 计算外层循环的下降后的温度，温度下降方式为 T（k+1） = K*T（k），K=0.95。
JudgeOverInnerLoop() 判断是否结束某一温度下的内层循环，某一温度下的循环次数是固定的，即城市个数的三次方。
JudgeOverExternalLoop() 判断是否结束模拟退火算法，使用“零度法”的判断方式，T（k）
程序使用方法
程序处理的TSP问题可按用户的具体要求，只需用户依照格式要求提供城市坐标文件即可，坐标文件的格式如下
1 6734 1453
2 2233 10
3 5530 1424
„„„„„
文件的每一行表示一个城市的信息，即，城市名称+空格+X坐标+空格+Y坐标。
点击菜单栏的[文件]-[打开„]，可打开指定的城市坐标文件。
指点城市文件打开后，程序会读入文件里的各城市坐标信息，并初始化城市距离矩阵。 点击菜单栏的[文件]-[开始计算]，即可进行计算。
城市计算结束后，会在C盘的根目录生成两个文件，一是sacitysfile.txt，它记录了计算得到的最优路径信息；二是saitersfile.txt，它记录了计算过程中的迭代信息。
可利用作者提供的Matlab的M文件satspsta.m读取以上两个文件，画出路径优化过程图和求解路径图。
程序算例
程序对48个城市的TSP问题（城市坐标文件对应于48.txt）进行计算，求解路径和最优路径图如下。
48个城市结果，大的红*表示路径开始城市，途经城市依次用蓝色方块和红色*标示。
求得最短路径为
3．源码获取
上面两个算法的程序源码都可到http://www.huisoft.com.cn/下载。
4．更新记录
2005年6月6日 加入读取距离矩阵文件的功能：
加入读取距离矩阵文件的功能，为了区别城市坐标文件和距离矩阵文件，在读入文件的第一行标示出文件的类型，如果是城市坐标文件，则文件的第一行以“coordinate”标识；如果是距离矩阵文件，则文件的第一行以“distancematrix”标识。具体可参见数据文件范例。