模拟退火算法解决TSP问题要点

智能优化方法课题报告 专业班级： 电子信息科学与技术12-3班 课题名称： 模拟退火算法解决TSP问题 指导教师： 姚 睿 学生姓名： 蒋文斌 学 号： （课题设计时间：2015年3月28日2015年 4月13日）中国矿业大学计算机学院一、问题描述旅行商问题（Traveling monituihuolesman Problem，简称TSP）又名货郎担问题，是威廉哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于19世纪初提出的一个数学问题，也是著名的组合优化问题。问题是这样描述的：一名商人要到若干城市去推销商品，已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小。TSP刚提出时，不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。这个问题数学描述为：假设有n个城市，并分别编号，给定一个完全无向图G=（V，E），V=1，2，n，n1。其每一边(i,j)E有一非负整数耗费 Ci,j(即上的权记为Ci,j，i，jV)。并设 G的一条巡回路线是经过V中的每个顶点恰好一次的回路。一条巡回路线的耗费是这条路线上所有边的权值之和。TSP问题就是要找出G的最小耗费回路。人们在考虑解决这个问题时，一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合)，计算出每条路线的总里程，最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D，各城市之间的耗费为己知数，如图1-1所示。我们可以通过一个组合的状态空间图来表示所有的组合，如图1-2所示。 图 1-1 顶点带权图 图 1-2 TSP问题的解空间树1.模拟退火是什么?首先,让我们看看模拟退火是如何工作的,以及为什么它是善于解决旅行商问题。模拟退火（Simulated Annealing，简称monituihuo）是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。该算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。退火与冶金学上的“退火”相似，而与冶金学的淬火有很大区别，前者是温度缓慢下降，后者是温度迅速下降。我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。2.模拟退火的优点先来说下爬山算法：爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1-3所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。 图1-3 爬山算法模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1-3为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。 也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。3.模拟退火算法描述：若J(Y(i+1)=J(Y(i)(即移动后得到更优解)，则总是接受该移动。若J(Y(i+1) J(Y(i)(即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：P(dE) = exp(dE/(kT)其中k是一个常数，exp表示自然指数，且dE0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。 又由于dE总是小于0（否则就不叫退火了），因此dE/kT 0 ，所以P(dE)的函数取值范围是(0,1) 。 随着温度T的降低，P(dE)会逐渐降低。我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。关于爬山算法与模拟退火，有一个有趣的比喻：爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。4.接受函数接受函数决定选择哪一个解决方案，从而可以避免掉一些局部最优解。首先我们检查如果相邻的解决方案是比我们目前的解决方案好，如果是，我们接受它。否则的话，我们需要考虑的几个因素：1) 相邻的解决方案有多不好; 2) 当前的温度有多高。在高温系统下更有可能接受较糟糕的解决方案。这里是简单的数学公式：exp( (solutionEnergy neighbourEnergy) / temperature )，即上面的P(dE) = exp( dE/(kT) )5.模拟退火的基本思想它可以分解为解空间、目标函数和初始解三部分。(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L(2) 对k=1，L做第(3)至第6步：(3) 产生新解S(4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数(5) 若t0，然后转第2步。6.模拟退火算法的流程7.算法过程描述（1) 首先,需要设置初始温度和创建一个随机的初始解。（2) 然后开始循环,直到满足停止条件。通常系统充分冷却,或找到一个足够好的解决方案。（3) 把当前的解决方案做一些小的改变，然后选择一个新的相邻的方案。（4) 决定是否移动到相邻的解决方案。（5) 降低温度,继续循环二、程序代码实现1.City类，用来描述城市的基本坐标信息，以及计算两城市之间的距离。package monituihuo;public class City int x;/保存城市的X坐标int y;/保存城市的Y坐标String name;/保存城市的名称 / 生成一个随机的城市 public City() this.x = (int)(Math.random()*200); this.y = (int)(Math.random()*200); =null; /初始化一个城市的坐标 public City(int x, int y,String name) this.x = x; this.y = y; = name; /获取城市的X坐标 public int getX() return this.x; /获取城市的Y坐标 public int getY() return this.y; / 计算两个城市之间的距离 public double distanceTo(City city) int xDistance = Math.abs(getX() - city.getX(); int yDistance = Math.abs(getY() - city.getY(); double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) ); return distance; / 重写toString方法 Override public String toString() return getX()+, +getY()+ +name; 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 SimulatedAnnealing.allCitys.size(); i+) tour.add(null); / 复杂路径 public Tour(ArrayList tour) this.tour = (ArrayList) tour.clone(); / 获取路径 public ArrayList getTour() return tour; / Creates a random individual public void generateIndividual() for (int cityIndex = 0; cityIndex SimulatedAnnealing.allCitys.size(); cityIndex+) setCity(cityIndex, SimulatedAnnealing.allCitys.get(cityIndex); / 随机的打乱 Collections.shuffle(tour); / 获取一个城市 public City getCity(int tourPosition) return (City)tour.get(tourPosition); public void setCity(int tourPosition, City city) tour.set(tourPosition, city); / 重新计算距离 distance = 0; / 获得当前的总距离 public int getDistance() if (distance = 0) int tourDistance = 0; for (int cityIndex=0; cityIndex tourSize(); cityIndex+) City fromCity = getCity(cityIndex); City destinationCity; if(cityIndex+1 tourSize() destinationCity = getCity(cityIndex+1); else destinationCity = getCity(0); tourDistance += fromCity.distanceTo(destinationCity); distance = tourDistance; return distance; / 获得当前路径中城市的数量 public int tourSize() return tour.size(); public String toString() String printString = |; for (int i = 0; i tourSize(); i+) printString += getCity(i)+|; return printString; 3. SimulatedAnnealing主类，是算法的实现类，也是模拟退火算法解决TSP问题相应的测试。package monituihuo;import java.util.ArrayList;import java.util.List;public class SimulatedAnnealing public static List allCitys = new ArrayList(); /计算接受的概率（依据热力学原理P(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) (newSolution.tourSize() * Math.random(); City citySwap1 = newSolution.getCity(tourPos1); City citySwap2 = newSolution.getCity(tourPos2); / 交换两个城市 newSolution.setCity(tourPos2, citySwap1); newSolution.setCity(tourPos1, citySwap2); / 获得新的解决方案的总路程 int currentEnergy = currentSolution.getDistance(); int neighbourEnergy = newSolution.getDistance(); / 决定是否接受新的方案 if (acceptanceProbability(currentEnergy, neighbourEnergy, temp) Math.random() currentSolution = new Tour(newSolution.getTour(); / 更新最优方案 if (currentSolution.getDistance() best.getDistance() best = new Tour(currentSolution.getTour(); / 冷却（即更新当前系统温度） temp *= 1-coolingRate; return best; /初始化20个城市，并将他们保存到allCitys。 private static void init() City city = new City(60, 200,北京); allCitys.add(city); City city2 = new City(180, 200,上海); allCitys.add(city2); City city3 = new City(80, 180,广州); allCitys.add(city3); City city4 = new City(140, 180,深圳); allCitys.add(city4); City city5 = new City(20, 160,长沙); allCitys.add(city5); City city6 = new City(100, 160,武汉); allCitys.add(city6); City city7 = new City(200, 160,南京); allCitys.add(city7); City city8 = new City(140, 140,重庆); allCitys.add(city8);City city9 = new City(40, 120,西安); allCitys.add(city9); City city10 = new City(100, 120,徐州); allCitys.add(city10); City city11 = new City(180, 100,成都); allCitys.add(city11); City city12 = new City(60, 80,天津); allCitys.add(city12); City city13 = new City(120, 80,苏州); allCitys.add(city13); City city14 = new City(180, 60,南昌); allCitys.add(city14); City city15 = new City(20, 40,郑州); allCitys.add(city15); City city16 = new City(100, 40,大连); allCitys.add(city16); City city17 = new City(200, 40,海口); allCitys.add(city17); City city18 = new City(20, 20,香港); allCitys.add(city18); City city19 = new City(60, 20,澳门); allCitys.add(city19); City city20 = new City(160, 20,台湾)； allCitys.add(city20); *运行结果:(一) Java运行结果（1）Initial solution distance: 2101Final solution distance: 919Tour: |80,180 广州|100,160 武汉|140,180 深圳|180,200 上海|200,160 南京|140,140 重庆|180,100 成都|180,60 南昌|200,40 海口|160,20 台湾|120,80 苏州|100,120 徐州|100,40 大连|60,20 澳门|20,20 香港|20,40 郑州|60,80 天津|40,120 西安|20,160 长沙|60,200 北京|（2）Initial solution distance: 2178Final solution distance: 906Tour: |100,40 大连|160,20 台湾|200,40 海口|180,60 南昌|180,100 成都|140,140 重庆|200,160 南京|180,200 上海|140,180 深圳|100,160 武汉|80,180 广州|60,200 北京|20,160 长沙|40,120 西安|100,120 徐州|120,80 苏州|60,80 天津|20,40 郑州|20,2