模拟退火算法解决TSP问题要点.pdf
《模拟退火算法解决TSP问题要点.pdf》由会员分享,可在线阅读,更多相关《模拟退火算法解决TSP问题要点.pdf(16页珍藏版)》请在三一文库上搜索。
1、智能优化方法 课题报告 专业班级:电子信息科学与技术12-3 班 课题名称:模拟退火算法解决TSP问题 指导教师:姚睿 学生姓名:蒋文斌 学号: 08123453 (课题设计时间:2015 年 3 月 28 日 2015年 4 月 13 日) 中国矿业大学计算机学院 一、问题描述 旅行商问题( Traveling monituihuolesman Problem,简称 TSP )又名货 郎担问题,是威廉哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于 19世 纪初提出的一个数学问题,也是著名的组合优化问题。问题是这样描述的:一 名商人要到若干城市去推销商品,已知城市个数和各城市间的路
2、程(或旅费), 要求找到一条从城市1 出发,经过所有城市且每个城市只能访问一次,最后回 到城市 1 的路线,使总的路程(或旅费)最小。TSP刚提出时,不少人认为这 个问题很简单。后来人们才逐步意识到这个问题只是表述简单,易于为人们所 理解,而其计算复杂性却是问题的输入规模的指数函数,属于相当难解的问题。 这个问题数学描述为:假设有n 个城市,并分别编号,给定一个完全无向图G= (V,E), V=1,2,n,n1。 其每一边 (i,j)E有一非负整数耗费 Ci,j(即 上的权记为 Ci,j ,i ,jV)。并设 1,ij 0 ij X 边( , )在最优线路上 ,其他 G的一条巡回路线是经过V中
3、的每个顶点恰好一次的回路。一条巡回路线的耗费 是这条路线上所有边的权值之和。TSP问题就是要找出G的最小耗费回路。 人们在考虑解决这个问题时,一般首先想到的最原始的一种方法就是: 列出 每一条可供选择的路线 ( 即对给定的城市进行排列组合) , 计算出每条路线的总里 程,最后从中选出一条最短的路线。假设现在给定的4 个城市分别为 A、B、C 和 D,各城市之间的耗费为己知数,如图1-1 所示。我们可以通过一个组合的状 态空间图来表示所有的组合,如图1-2 所示。 (1-1 ) 图 1-1 顶点带权图图 1-2 TSP 问题的解空间树 1. 模拟退火是什么 ? 首先, 让我们看看模拟退火是如何工
4、作的, 以及为什么它是善于解决旅行商 问题。模拟退火( Simulated Annealing,简称 monituihuo )是一种通用概率 算法,用来在一个大的搜寻空间内找寻命题的最优解。该算法是源于对热力学 中退火过程的模拟,在某一给定初温下,通过缓慢下降温度参数,使算法能够 在多项式时间内给出一个近似最优解。退火与冶金学上的“退火”相似,而与 冶金学的淬火有很大区别,前者是温度缓慢下降,后者是温度迅速下降。我们 将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子; 分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样 带有“能量”,以表示该点对命题的合适程
5、度。算法先以搜寻空间内一个任意 点作起始:每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居” 的概率。 2. 模拟退火的优点 先来说下爬山算法:爬山算法是一种简单的贪心搜索算法,该算法每次从当 前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。 爬 山算法实现很简单, 其主要缺点是会陷入局部最优解,而不一定能搜索到全局最 优解。如图 1-3 所示:假设 C点为当前解, 爬山算法搜索到 A点这个局部最优解 就会停止搜索, 因为在 A点无论向那个方向小幅度移动都不能得到更优的解。爬 山法是完完全全的贪心法, 每次都鼠目寸光的选择一个当前最优解,因此只能搜 索到局部的最优值
6、。 图 1-3 爬山算法 模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟 退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局 部的最优解, 达到全局的最优解。 以图 1-3 为例,模拟退火算法在搜索到局部最 优解 A后,会以一定的概率接受到E的移动。 也许经过几次这样的不是局部最优的移动后会到达D点, 于是就跳出了局部 最大值 A。 3. 模拟退火算法描述: 若 J(Y(i+1)=J(Y(i)(即移动后得到更优解 ),则总是接受该移动。 若 J(Y(i+1)0,然后转第 2 步。 6. 模拟退火算法的流程 7. 算法过程描述 (1) 首先, 需要设置初始
7、温度和创建一个随机的初始解。 (2) 然后开始循环 , 直到满足停止条件。通常系统充分冷却, 或找到一个足 够好的解决方案。 (3) 把当前的解决方案做一些小的改变,然后选择一个新的相邻的方案。 (4) 决定是否移动到相邻的解决方案。 (5) 降低温度 , 继续循环 二、程序代码实现 1.City类,用来描述城市的基本坐标信息,以及计算两城市之间的 距离。 package monituihuo; publicclass City intx; / 保存城市的 X坐标 int y;/保存城市的 Y坐标 String name;/ / 保存城市的名称 / 生成一个随机的城市 public City(
8、) this. x = (int)(Math.random ()*200); this. y = (int)(Math.random ()*200); this. name = null; / 初始化一个城市的坐标 public City(intx, inty ,String name) this. x = x; this. y = y; this.name = name; / 获取城市的X坐标 publicint getX() returnthis. x; / 获取城市的Y坐标 publicint getY() returnthis. y; / 计算两个城市之间的距离 publicdoubl
9、e distanceTo(City city) intxDistance = Math.abs (getX() - city.getX(); intyDistance = Math.abs (getY() - city.getY(); doubledistance = Math.sqrt( (xDistance* xDistance) + ( yDistance* yDistance) ); returndistance; / 重写 toString方法 Override public String toString() return getX()+“, “+getY()+“ “+name;
10、2.Tour类,用来初始化旅行商路径,完成路径的解决方案。 package monituihuo; import java.util.ArrayList; import java.util.Collections; public class Tour / 保存城市的列表 private ArrayList tour = new ArrayList(); / 保存距离 private int distance = 0; / 生成一个空的路径 public Tour() for (int i = 0; i allCitys = new ArrayList(); /计算接受的概率(依据热力学原理P(
11、dE) = exp(dE/(kT)) public static double acceptanceProbability(int energy, int newEnergy, double temperature) / 如果新的解决方案较优,就接受 if (newEnergy 1) / 生成一个邻居 Tour newSolution = new Tour(currentSolution.getTour(); / 获取随机位置 int tourPos1 = (int) (newSolution.tourSize() * Math.random(); int tourPos2 = (int) (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 解决 TSP 问题 要点
链接地址:https://www.31doc.com/p-5209487.html