实验三.模拟退火算法
实验三：模拟退火算法
一、实验目的 1. 了解TSP问题的基本概念，解决TSP问题的难点是什么？
2. 掌握模拟退火算法的基本原理和步骤。
3. 复习VC的基本概念、基本语法和编程方法，并熟练使用VC编写程序。
二、实验环境
PC机一台，VC++6.0
三、实验原理 模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能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，不妨假设k
(w1,w2,„,wk,wk+1,„,wm,wm+1,„,wn)
变为新路径：(w1,w2,„,wm,wk+1,„,wk,wm+1,„,wn)上述变换方法就是将
k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。 根据上述描述，模拟退火算法求解TSP问题的流程框图如下：
图1、模拟退火算法求解TSP问题的流程框图
模拟退火算法新解的产生和接受可分为如下四个步骤：
由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若Δt′
exp(-Δt′/T)接受S′作为新的当前解S。
当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
四、实验内容
TSP问题（Travelling Salesman Problem），即旅行商问题是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
分析：
如果利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市时，求解时间长达350年；如果要处理30个城市，则求解时间更长达1+10e16年。如此长的时间，在实际中完成是难以想象的。
实验输入数据：
10//表示城市数量
12 45 /表示第一个城市坐标，以此类推
35 67
58 99
43 78
88 11
87 34
32 23
44 66
67 22
123 67
五、实验核心代码
/************************************************************
产生新路径方法
*************************************************************/ path getnext(path p) //新解产生函数
{
int x, y;
path ret;
ret = p;
do {
x = rand() % N + 1;
y = rand() % N + 1;
}while(x == y);
swap(ret.City[x], ret.City[y]); //交换两城市之间位置顺序
ret.Length = totaldist(ret);
return ret;
}
/****************************************************************
退火和降温过程
******************************************************************/
void sa()
{
double T; //温度
path newpath, curpath; //当前路径和新路径
int i, P_t=0, A_t=0;
double delta;
T = INIT_T; //赋值初始温度
curpath = bestpath;
while(true)
{
for (i=1; i
{
newpath = getnext(curpath); //获取新路径
delta = newpath.Length - curpath.Length;
if (delta
{
curpath = newpath;
P_t = 0;
A_t = 0;
}
else
{
double rnd = rand()%10000 /10000.0;
double p = exp(-delta/T);
if (p > rnd)
curpath = newpath;
P_t++;
}
if (P_t >=P_LIMIT)
{
A_t++;
break;
}
}
if (curpath.Length
bestpath = curpath;
if ( A_t >= OUT_LOOP || T
T = T * RATE; //降温
}
}
实验结果：
六、实验总结
通过本次实验，使我加深了对模拟算法的认识，能够清晰掌握该算法的分析思想及流程，对于解决TSP问题有了明确的思路，我对于算法问题产生了更深厚的兴趣。