实验三：模拟退火算法
一、实验目的
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′<0则接受S′作为新的当前解S，否则以概率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 五、实验核心代码 /************************************************************ 产生新路径方法
相关推荐：
loading