人工智能原理
实验报告
模拟退火算法解决TSP问题
目 录
1 旅行商问题和模拟退火算法 ........................................... 错误!未定义书签。 旅行商问题 ................................................................... 错误!未定义书签。 旅行商问题的描述 ................................................. 错误!未定义书签。 模拟退火算法 ............................................................... 错误!未定义书签。 基本思想 ................................................................. 错误!未定义书签。 2 TSP模拟退火算法的实现 ................................................ 错误!未定义书签。 TSP算法实现 ............................................................... 错误!未定义书签。 TSP算法描述 ......................................................... 错误!未定义书签。 TSP算法流程 ......................................................... 错误!未定义书签。 TSP的C实现 .............................................................. 错误!未定义书签。 加载数据文件 ......................................................... 错误!未定义书签。 计算总距离的函数 ................................................. 错误!未定义书签。 交换城市的函数 ..................................................... 错误!未定义书签。 执行模拟退火的函数 ............................................. 错误!未定义书签。 实验结果 ......................................................................... 错误!未定义书签。 小结 ................................................................................. 错误!未定义书签。 3源代码 ................................................................................ 错误!未定义书签。
1 旅行商问题和模拟退火算法
旅行商问题 旅行商问题的描述
旅行商问题（Traveling Salesman Problem，简称TSP）又名货郎担问题，是威廉·哈密尔顿爵士和英国数学家克克曼于19世纪初提出的一个数学问题，也是著名的组合优化问题。问题是这样描述的：一名商人要到若干城市去推销商品，已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小。TSP刚提出时，不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。这个问题数学描述为：假设有n个城市，并分别编号，给定一个完全无向图G=（V，E），V={1，2，…，n}，n>1。其每一边(i,j)?E有一非负整数耗费 Ci,j(即上的权记为Ci,j，i，。?V)（j1-1）并设
????????边（i，j）在最优线路上Xij?{1, 0， ??????其他G的一条巡回路线是经过V中的每个顶点恰好一次的回路。一条巡回路线的耗费是
这条路线上所有边的权值之和。TSP问题就是要找出G的最小耗费回路。
模拟退火算法
模拟退火算法由KirkPatrick于1982提出[7]，他将退火思想引入到组合优化领域,提出一种求解大规模组合优化问题的方法，对于NP-完全组合优化问题尤其有效。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温(即退火)，使之达到能量最低点。反之，如果急速降温(即淬火)则不能达到最低点。加温时，固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(-E/(kT))，其中E为温度T时的内能，?E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复产生“新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子a、每个t值时的迭代次数L和停止条件C。 基本思想
模拟退火算法可以分解为解空间、目标函数和初始解3部分。其基本思想是：
(1)初始化：初始温度T(充分大)，初始解状态s(是算法迭代的起点)，每个T值的迭代次数L；
(2)对k=1，……，L做第(3)至第6步； (3)产生新解s′；
(4)计算增量cost=cost(s′)-cost(s)，其中cost(s)为评价函数；
模拟退火算法的旅行商问题
