模拟退火算法及其应用

内蒙古工业大学本科毕业论文摘要生活中存在许多需要使用优化的情况，而为了解决这种情况便出现了很多的优化算法.模拟退火算法就是多种优化组合算法中的一种，它一直以来都是一个优化领域的热点，收到广大研究者的关注.作为优化组合算法中的佼佼者，它拥有相较于早期其他优化算法更便于计算，使用灵活适用于并行运算的优点，解决了部分传统算法无法规避大规模问题的不可行因素.模拟退火算法来源于模拟退火的过程，在1953年被Metropofis提出这种先进的思想，而后被Kirkpatrick等人于1983年引入到优化组合领域中，从此模拟退火算法就成为了许多优化算法中的一种.当然对于这种优越的算法并不仅仅是用于简单的优化问题中，它可用于的领域包括着工程科学在内的多种领域中.(删掉,摘要里不需要写这些)模拟退火算法虽然在各个领域中有着十分的成就，但它在组合优化上还是占有着非常重要的地位.本文中将会对于模拟退火算法的背景做出简述，并对模拟退火算法的原理内容做出介绍.为了更加清楚的了解模拟退火算法的性能，本文中对其举出例子来演示其在优化问题中的表现.在组合优化领域中NP(NP-Hard)问题一直都是一个麻烦的问题，尤其其中著名的旅行商问题有着简单、麻烦的特点.简单是指它的问题描述最为简化时，就是在几个点中找出最为短的路径；麻烦却是当几个点增长到一定程度是就很难得出一个准确的解.而模拟退火算法却在这种难题中有着不俗的表现.关键词：模拟退火算法；组合优化问题；TSP问题内蒙古工业大学本科毕业论文AbstractManyrequiretheuseofoptimizationconditionexistsinlife,andinordertoresolvethissituationoccursmanyoptimizationalgorithm.Simulationisacombinationofseveraloptimizationalgorithmofsimulatedannealingalgorithm,itisalwaysahotoneoptimizationfield,receivedthemajorityofresearchers.Asaleaderincombinationoptimizationalgorithm,ithascomparedtootherearlyoptimizationalgorithmmoreeasytocalculate,theuseofflexibleadvantagesofparallelcomputing,solvetheinfeasiblefactorpartoftraditionalalgorithmcannotavoidlarge-scaleproblems.Simulatedannealingalgorithmderivedfromthesimulatedannealingprocess,in1953Metropofisproposedtheadvancedideas,andthenbyKirkpatricketalin1983intotheoptimizationinthefield,thenthesimulatedannealingalgorithmisoneofmanyintheoptimizationalgorithm.Ofcourse,thisalgorithmisnotonlysuperiortosimpleoptimizationproblemsinvariousfields,whichcanbeusedinfieldsincludingengineeringsciencein.Simulatedannealingalgorithmisverysuccessineveryfield,butitisinthecombinatorialoptimizationandoccupiesaveryimportantposition.Thispaperwillmakeabriefforthesimulatedannealingalgorithmtomakethebackground,principleandcontentofthesimulatedannealingalgorithm.Inordertomoreclearlyunderstandtheperformanceofsimulatedannealing,todemonstratetheoptimizationproblemintheperformancefortheexamplesinthisarticle.InthefieldofcombinatorialoptimizationprobleminNPisalwaysadifficultproblem,especiallythewell-knowntravelingsalesmanproblemwhichhasthecharacteristicsofsimple,trouble.Simplereferstothedescriptionoftheproblemisthemostsimple,isatseveralpointsoutthemostshortpath;thetroubleiswhenseveralpointsuptoacertainextentishardlyanaccuratesolution.Thesimulatedannealingalgorithmhasagoodperformanceinthisproblem.Keywords:thesimulatedannealingalgorithm;combinatorialoptimization;TSP内蒙古工业大学本科毕业论文目录第1章引言............................................错误!未定义书签。1.1问题概述.......................................错误!未定义书签。1.2算法提出.......................................错误!未定义书签。1.3模拟退火算法的研究内容及现状...................................2第2章模拟退火算法的原理及应用........................................52.1模拟退火算法的基本原理.........................................52.2模拟退火算法的模型.............................................62.3模拟退火算法的可行性...........................................72.4冷却进度表.....................................................7第3章模拟退火算法求解组合优化问题....................................83.1模拟退火算法详解...............................................83.2模拟退火算法解决组合优化问题算例..............................11第4章TSP问题以及模拟退火算法的一个实际应用..........................124.1旅行商问题简介................................................124.2模拟退火算法应用..............................................134.3实际应用......................................................16总结..................................................................17参考文献..............................................................18谢辞..................................................................19内蒙古工业大学本科毕业论文1第一章引言1.1问题概述在自然科学以及大多数科学当中和社会生活里经常出现最大或最小的问题，我们从小学开始学习大小比较，一直到高中大学时的最优解问题，都是一种名为最优化问题.最优化问题在大多是领域中都有重要的地位，例如管理科学、计算机科学、图像处理等等需要大量数据的学科中都存在着需要解决的组合优化问题.用我们比较容易理解的说法就是已知一组固定的函数，令这组函数所对应的函数到达最大或最小值.而我们所想到的最简单的方法便是穷举法，然而这种方式存在这大量的数据计算穷举的缺点.优化组合问题中的NP问题是一个很麻烦的问题，它解得规模会随着问题的规模增大而增大，求解所需的时间也会随问题的规模增大而成指数级增长，而当规模过大时就会因为时间的限制而失去了可行性.旅行商问题（TSP）是优化组合问题中最为著名的一个问题，它的特点是容易描述却难于求解.这是一个经典的图论问题，假设有n个城市，用表示.城市之间距离为，i，j=1，2，3，···，n，假设所有城市之间两两连通，要求从一个城市出发，把所有城市都走一遍，而TSP问题就是恰好所有城市都走一遍，而所走路径形成回路且路径最短.将这个问题对应在一个n个顶点的完全图上，假设图为对称图，则要从个可能的解当中找到最小的解，需要的对比则要进行次，当的数值增大时，那么需要的次数也会随之以几何数倍增长，例如每秒运算一亿次的计算机，当需要的时间也只是0.0018秒，当需要的时间却是17年，可当时所需的时间却猛增到年，这个结果是我们所不想看到的.优化组合问题的目标函数是从组合优化问题的可行解集当中求出最优解.组合优化问题有三个基本要素：变量，约束和目标函数，在求解过程中选定的基本参数成为标量，对于变量的取值的所有限制称之为约束，表示可行的方案的标准的函数称之为目标函数.随着问题种类的不同以及问题规模的扩大，要找到一种能够已有限代价来求解最优化问题的通用方法一直都是一个难题，建立用最大的可能性求解全局解一直是一个重要问题.但是传统方式却有以下难以处理的问题：（1）非凸可行域和具有多个局部极值问题；（2）不连通的可行域；（3）变量全部或部分是离散的、整型的；（4）目标具有多个极值；（5）难于求解目标函数和约束函数的梯度.于是在这样的环境下出现了一种可以处理以上难题的方式模拟退火法.内蒙古工业大学本科毕业论文21.2算法的提出模拟退火法最早是由Metropolis在1953年提出的，而在1983年由Kirkpatrick等人成功的引入到了组合优化领域并目前已经在工程当中得到了广泛的应用.模拟退火算法的思想是来源于冶金当中的退火过程，是对于固体退货降温过程的模拟.退火过程就是将材料加热后再让其慢慢的冷却，它的目的是增大晶体的体积，减小晶体的缺陷.而在加热固体的过程中使其原子的热运动加强，内能增大，随着热量的不断增加，原子会离开原来的位置而随机在其他的位置中移动.冷却时，粒子运动速率较慢，慢慢到达平衡，最后到达常温下的基态，内能降低为最小状态.模拟退火的原理与金属冶炼退货的原理相似：我们可以将热力学的理论利用在统计运筹当中，将搜寻空间中的每一个点想象成空气内的分子；分子的能量即它的动能；搜寻空间内的每一点，也像空气分子一样带有能量，以表示该点对于命题的合适程度.算法以任意点作为起始：每一步先选择一个邻点，然后计算到达邻点的概率.可以说明，模拟退火法所得解根据概率收敛到全局最优解.1.3模拟退火算法的研究内容及现状模拟退火法的思想在1983年被引入到组合优化领域之后，在实际应用当中以其在解