蔡霞开题报告

《蔡霞开题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京邮电大学通达学院毕业设计（论文）开题报告题目基于模拟退火算法的TSP问题研究与仿真学生姓名班级学号专业对指导教师下达的课题任务的学习与理解本次毕业设计主要任务是以TSP问题为背景，在掌握模拟退火算法的基础上，完成基于模拟退火算法的TSP问题研究，同时利用matlab软件对设计方案进行仿真验证。对其中相关细节要求如下：1.为TSP问题建立数学模型；2.学习并掌握模拟退火算法，并对改算法进行研究，找出其优点及存在问题；3.对该算法进行改进并仿真；4.在Windows2000/XP平台上，用VisualC

2、++6.0或者matlab仿真。阅读文献资料进行调研的综述目的：本文的主要研究目标就是用改进的模拟退火算法更好地解决TSP这个有意义的NP难问题，在分析了TSP问题的求解现状及基本模拟退火算法对TSP的求解理论、思路及成果的基础上，再提出一种改进的模拟退火算法进行求解，并且多组数据进行分析与测试，将结果与传统的求解方法加以比较，证实其可能性。旅行商问题(TSP,TravelingSalesmanProblem)：有N个城市，要求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。旅行商

3、问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!)。使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。模拟退火解决TSP的思路：1.产生一条新的遍历路径P(i+1)，计算路径P(i+1)的长度L(P(i+1))2.若L(P(i+1))

4、节点的顺序。2.随机选择2个节点，将路径中这2个节点间的节点顺序逆转。3.随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后面。模拟退火算法的基本原理：模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温

5、时达到基态，内能减为最小。模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。一．作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。　求解

6、TSP的模拟退火算法模型可描述如下： 解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2 ,……，wn)，并记wn+1= w1。初始解可选为(1，……，n)目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数： 　　我们要求此代价函数的最小值。　　新解的产生 随机产生1和n之间的两相异数k和m，若k，则将　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)　　变为：　　(w1, w2 ,…，wm , wm-1 ,…

7、，wk+1 , wk ,…，wn).　　如果是k>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)

8、若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.　　(6)如果满足终止条件则输出当前解作为最优解，结束程序。　　终止条件通常取为连续若干个新解都没有被接受时终止算法。　　(7)T逐渐减少，且T->0，然后转第2步。三．算法对应动态演示：模拟退火算法新解的产生和接受可分为如下四个步骤：　　第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新