模拟退火算法在旅行商问题中的应用 毕业论文论文

《模拟退火算法在旅行商问题中的应用 毕业论文论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、四川理工学院毕业论文模拟退火算法在旅行商问题中的应用学生：学号：08071030223专业：信息与计算科学班级：信计2008.2指导教师：四川理工学院理学院二O一二年五月四川理工学院毕业设计（论文）任务书设计（论文）题目：模拟退火算法在旅行商问题中的应用学院：理学院专业：信息与计算科学班级：2008级2班学号：08071030223学生：吴春伶指导教师：高媛媛接受任务时间2012年3月15日教研室主任（签名）　　二级学院院长（签名）1．毕业设计（论文）的主要内容及基本要求主要内容：利用模拟退火算法和MATLAB工具箱建立求解TSP问题的模型，并在多项式时间内找到TSP问题

2、的最优解。基本要求：1)熟读参考文献；2)掌握模拟退火算法的基本理论和结构；3)能够利用MATLAB工具箱建立模型。2．指定查阅的主要参考文献及说明1)MATLAB在数学建模中的应用（卓金武主编）；它以数学建模为主，比较全面的讲解了模拟退火算法以及MATLAB的相关知识;2)神经网络、模糊系统及其在运动控制中的应用（丛爽主编）；它主要系统的讲述了模拟退火算法的理论知识，全面的介绍的模拟退火算法的模型以及相关知识;3)基于MATLAB的模拟退火算法的实现（曲强，陈雪波）；阐述了模拟退火算法的基本原理及实现过程，运用MATLAB语言实现模拟退火算法，并将其用于解决TSP问题。

3、3．进度安排设计（论文）各阶段名称起止日期1确定论文题目，接受任务2012年3月15日2查阅文献资料，完成文献综述和开题报告2012年3月25日3完成论文初稿2012年5月12日4修改并完成论文直至定稿2012年5月23日5论文答辩2012年5月29日注：本表在学生接受任务时下达摘要摘要旅行商问题（即TSP问题）是组合优化中著名的NPhard问题,而模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的势，因此它也是解决TSP的有效方法之一。这里介绍和描述模拟退火算法的原理及其基本框架结构，并应用模拟退火算法对TSP问题进行研究,给出用模拟退火算

4、法求解TSP问题的具体实现方法，同时为MATLAB语言编程提供了程序设计思路，并且分析说明模拟退火算法的优缺点。关键词：模拟退火算法;组合优化;旅行商问题;MATLABIABSTRACTTravelingsalesmanproblem（TSP）isafamousNP-hardprobleminthetheoryofcombinationoptimization.However,simulatedannealingalgorithmhasobviouscomparativeadvantageinsolvingthedifficultproblems,suchasglobal

5、optimizationanddiscretevariablesoptimization.SosimulatedannealingalgorithmisaneffectivemethodforsolvingTSP.Frameworkandprincipleofsimulatedannealingalgorithmweredescribed,computationalmethodtosolveTSPproblemwasgiven,programdesignideasoftheMATLABprogramminglanguagewereprovidedaswell,andthe

6、advantagesanddisadvantagesofsimulatedannealingalgorithmwerealsoshowninthispaper.Keywords:simulatedannealingalgorithm;combinatorialoptimization;travelingsalesmanproblem;MATLABI目录目录摘要IABSTRACTII目录III第一章前言1第二章模拟退火算法及其应用32.1Metropolis准则与模拟退火算法[5]32.1.1Metropolis准则32.1.2模拟退火算法42.2模拟退火算法的原理42.2

7、.1物理退火过程52.2.2模拟退火的原理和物理退火的原理的相似性52.3模拟退火算法模型62.3.1模拟退火算法的基本思想62.3.2算法新解的产生和接受72.3.3冷却进度表82.4模拟退火算法的应用8第三章旅行商问题103.1组合优化问题简述103.2TSP问题简述113.2.1TSP问题的基本概念113.2.2TSP问题的发展趋势113.2.3旅行商问题的应用12第四章基于模拟退火算法求解TSP问题144.1TSP问题的模拟退火算法实现144.1.1TSP算法描述144.1.2TSP算法流程164.2TSP问题的MAT