蔡霞开题报告.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)) < L(P(i))，则接受P(i+1)为新的路径，否则以模拟退火的那个概率接受P(i+1) ，然后降温
3. 重复步骤1，2直到满足退出条件
产生新的遍历路径的方法有很多，下面列举其中3种：
1. 随机选择2个节点，交换路径中的这2个节点的顺序。
2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。
3. 随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后面。
模拟退火算法的基本原理：模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
一．作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。
　求解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 ,…，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) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
　　(6) 如果满足终止条件则输出当前解作为最优解，结束程序。
　　终止条件通常取为连续若干个新解都没有被接受时终止算法。
　　(7) T逐渐减少，且T->0，然后转第2步。

三．算法对应动态演示：
模拟退火算法新解的产生和接受可分为如下四个步骤：
　　第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
　　第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
　　第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受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] 王凌著.智能优化算法及其应用.北京:清华大学出版社,2001
[2] 黄友锐.智能优化算法及其应用.北京:国防工业出版社,2008
[3] 汪定伟.智能优化方法.北京:高等教育出版社,2007
[4] 刁成嘉.面向对象C++程序设计.北京:机械工业出版社，2004
[5] 刘瑞新,曹建春，沈淑娟. Visual C++面向对象程序设计程.张连堂机械工业出版社，2004
[6] 陈文宇,张松梅. C++语言教程.电子科技大学出版社，2004
[7] LIHUA WU and YUYUN WANG.An Introduction to Simulated
Annealing Algorithms for the Computation of Economic Equilibrium.
Institute of Sysyem Science, Academia Sinica, Beijing 100080,
P.R china, 1997
[8]D S Johnson, C R Aragon, L A McGeoch.C Schevon.Optimization
by simulated annealing:an experimental evaluation, Part1,
AT&T bell Laboratories, Murray Hill(NJ) , 1999.
[9]P J MVanlaarhoven, E H L Aarts.simulated annenling:theory
and applications, D Reidel, 1987计算复杂性概论, 北京气象出版社,,

指导
教师
批阅
意见

指导教师（签名）： 年 月 日