蔡霞开题报告.doc

南京邮电大学通达学院毕业设计（论文）开题报告题目基于模拟退火算法的TSP问题研究与仿真学生姓名班级学号专业对指导教师下达的课题任务的学习与理解本次毕业设计主要任务是以TSP问题为背景，在掌握模拟退火算法的基础上，完成基于模拟退火算法的TSP问题研究，同时利用matlab软件对设计方案进行仿真验证。对其中相关细节要求如下：1.为TSP问题建立数学模型；2.学习并掌握模拟退火算法，并对改算法进行研究，找出其优点及存在问题；3.对该算法进行改进并仿真；4.在Windows 2000/XP平台上，用Visual C+ 6.0或者matlab仿真。阅读文献资料进行调研的综述目的：本文的主要研究目标就是用改进的模拟退火算法更好地解决TSP这个有意义的NP难问题，在分析了TSP问题的求解现状及基本模拟退火算法对TSP的求解理论、思路及成果的基础上，再提出一种改进的模拟退火算法进行求解，并且多组数据进行分析与测试，将结果与传统的求解方法加以比较，证实其可能性。 旅行商问题 ( TSP , Traveling Salesman Problem ) ：有N个城市，要求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。旅行商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!) 。使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。模拟退火解决TSP的思路：1. 产生一条新的遍历路径P(i+1)，计算路径P(i+1)的长度L( P(i+1) )2. 若L(P(i+1) m，则将(w1,w2,，wk,wk+1,，wm,，wn)变为：(wm,wm-1,，w1,wm+1,，wk-1,wn,wn-1,，wk).二模拟退火的基本思想: (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L (2) 对k=1，L做第(3)至第6步： (3) 产生新解S (4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数 (5) 若t0，然后转第2步。三算法对应动态演示：模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则:若t0则接受S作为新的当前解S，否则以概率exp(-t/T)接受S作为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。四模拟退火算法可以分解为解空间、目标函数和初始解三部分。 解空间：对所有可能解均为可行解的问题定义为可能解的集合，对存在不可行解的问题，或限定解空间为所有可行解的集合，或允许包含不可行解但在目标函数中用罚函数惩罚以至完全排除不可行解； 目标函数：对优化目标的量化描述，是解空间到某个数集的映射。通常表为优化目标的一个和式，应正确体现问题的整体优化要求切易计算，当解空间包含不可行解时还应包含罚函数项；初始解：是算法迭代的起点，试验表明，模拟退火算法是健壮的，即最终解的求得不十分依赖初始解的选取，从而可任意选取一个初始解。五模拟退火算法的要素：1.状态空间和状态产生函数（邻域函数）2.状态转移概率（接受概率）3.冷却进度表T（t）4.初始温度T（0）5.内循环终止原则6.外循环终止原则六算法评价 模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。如果参数设置得当，模拟退火算法搜索效率比穷举法要高。课题的主要内容主要内容：TSP 问题是一个NP问题难题，采用传统的方法很难求出问题的最优解。TSP搜索随着城市数n的增加而增加，所以的旅程路线组合数为（n-1）！/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多困难。借助于模拟退火算法的搜索能力解决TSP问题，是一个很好的想法。根据问题的规模，制定用户的需求计划，再根据需要进行源代码开发，具体内容包括：1.学习模拟退火算法原理及其使用，并对改算法进行研究，找出其优点及存在问题。2.学习C/C+语言。3.接受各自的设计任务，开发相关源代码程序。4.总结毕业设计成果，编写有关材料。5.准备毕业答辩。应用模拟退火算法解决TSP问题，通过编程来验证。在研究过程中了解浮点数编码、适应度函数、交叉算子和变异算子及模拟退火算法的三个基本运算（选择、交叉、变异）等问题。根据任务书的任务及文献调研结果，初步拟定的执行（实施）方案（含具体进度计划）1认真学习和理解毕业设计任务书的要求，完成开题报告。 第七学期第14-15周2查阅关于模拟退火算法的相关书，掌握其原理及其使用。 第七学期第16-20周 3. 查找相关外文资料，完成外文资料翻译，完成中期报告。 第八学期第1-3周4熟悉Visual C+ 6.0或matlab仿真软件，编写相关程序，测试。第八学期第4-9周5按要求认真撰写毕业报告。 第八学期第10-12周 6整理资料、准备答辩。 第八学期第13-17周主要参考文献及资料：1 王凌著.智能优化算法及其应用.北京:清华大学出版社,20012 黄友锐.智能优化算法及其应用.北京:国防工业出版社,20083 汪定伟.智能优化方法.北京:高等教育出版社,20074 刁成嘉.面向对象C+程序设计.北京:机械工业出版社，20045 刘瑞新,曹建春，沈淑娟. Visual C+面向对象程序设计程.张连堂机械工业出版社，20046 陈文宇,张松梅. C+语言教程.电子科技大学出版社，20047 LIHUA WU and YUYUN WANG.An Introduction to SimulatedAnnealing Algorithms for the Computation of Economic Equilibrium.Institute of Sysyem Science, Academia Sinica, Beijing 100080,P.R china, 19978D S Johnson, C R Aragon, L A McGeoch.C Schevon.Optimizationby simulated annealing:an experimental evaluation, Part1,AT&T bell Laboratories, Murray Hill(NJ) , 1999.9P J MVanlaarhoven, E H L Aarts.simulated annenling:theoryand applications, D Reidel, 1987计算复杂性概论, 北京气象出版社,指导教师批阅意见 指导教师（签名）： 年 月 日