模拟退火算法在tsp问题中的应用研究毕业论文(编辑修改稿)

模拟退火算法在tsp问题中的应用研究毕业论文(编辑修改稿)内容摘要：

模拟退火技术和 群集智能技术等。 1． 人工神经网络算法 “人工神经网络 ”(ARTIFICIAL NEURAL NETWORK，简称 ANN)是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。 早在本世纪 40 年代初期， 心理 学家 McCulloch、 数学 家 Pitts就提出了人工神经网络的第一个数学模型，从此开创了神经科学理论的研模拟退火算法在 TSP问题中的应用研究 第二章 相关知识介绍 7 究时代。 其后， F Rosenblatt、 Widrow 和 J. J .Hopfield 等学者又先后提出了感知模型，使得人工神经网络技术得以蓬勃发展 [7]。 神经系统的基本构造是神经元 (神经细胞 )，它是处理人体内各部分之间相互信息传递的基本单元。 据神经生物学家研究的结果表明，人的一个大脑一般有 1010～ 1011 个神经元。 每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它较短分支 ——树突组成。 轴突 的功能是将本神经元的输出信号 (兴奋 )传递给别的神经元。 其末端的许多神经末梢使得兴奋可以同时传送给多个神经元。 树突的功能是接受来自其它神经元的兴奋。 神经元细胞体将接受到的所有信号进行简单处理 (如：加权求和，即对所有的输入信号都加以考虑且对每个信号的重视程度 ——体现在权值上 ——有所不同 )后由轴突输出。 神经元的树突与另外的神经元的神经末梢相连的部分称为突触 [8]。 2． Hopfield 神经网络 1986 年美国物 理学 家 陆续发表几篇论文，提出了 Hopfiel 神经网络。 他利用非线性动力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性，并利用此方法建立求解优化计算问题的系统方程式。 基本的 Hopfield神经网络是一个由非线性元件构成的全连接型单层反馈系统。 网络中的每一个神经元都将自己的输出通过连接权传送给所有其它神经元，同时又都接收所有其它神经元传递过来的信息。 即：网络中的神经元 t 时刻的输出状态实际上间接地与自己的 t1 时刻的输出状态有关。 所以 Hopfield 神经网络是一个反馈型的网络。 其状态变化可以用差分方程来表征。 反馈型网络的一个重要特点就是它具有稳定状态。 当网络达到稳定状态的时候，也就是它的能量函数达到最小的时候。 这里的能量函数不是 物理 意义上的能量函数，而是在表达形式上与物理意义上的能量概念一致，表征网络状态的变化趋势，并可以依据Hopfield 工作运行规则不断进行状态变化，最终能够达到的某个极小值的目标函数。 网络收敛就是 指能量函数达到极小值 [9]。 如果把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，那么 Hopfield 神经网络就能够用于解决优化组合问题。 3． 遗传算法 遗传算法（ Geic Algorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。 其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。 它是在 70 年代初期由美国密执根（ Michigan）大学的霍兰（ Holland）教授发展起来的。 1975 年霍兰教授发表了第一本比较 系统论述遗传算法的专著《自然系统与人工系统中的适应性》模拟退火算法在 TSP问题中的应用研究 第二章 相关知识介绍 8 （《 Adaptation in Natural and Artificial Systems》）。 遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。 迄今为止，遗传算法是进化算法中最广为人知的算法。 近几年来，遗传算法主要在复杂优化问题求解和 工业 工程领域应用方面，取得了一些令人信服的结果，所以引起了很多人的关注。 在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。 遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、 交通 问题等等。 4． 粒子群优化算法 粒子群优化算法 (PSO)是一种进化计算技术 (Evolutionary Computation)， 有Eberhart 博士和 Kennedy 博士发明。 源于对鸟群捕食的行为研究。 PSO 同遗传算法类似，是一种基于叠代的优化工具。 系统初始化为一组随机解，通过叠代搜寻最优值。 但是并没有遗传算法用的交叉 (crossover)以及变异(mutation)。 而是粒子在解空间追随最优的粒子进行搜索。 同遗传算法比较， PSO 的优势在于简单容易实现并且没有许多参数需要调整。 目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。 粒子群优化算法 (PSO) 也是起源对简单 社会 系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发现 PSO 是一种很好的优化工具。 目前的智能计算研究水平暂时还很难使 “智能机器 ”真正具备人类的常识，但智能计算将在 21 世纪蓬勃发展。 不仅仅只是功能模仿要持有信息机理一致的观点。 即人工脑与生物脑将不只是功能模仿，而是具有相同的特性。 这两者的结合将开辟一个全新的领域，开辟很多新的研究方向。 智能计算将探索智能的新概念，新理论，新方法和新技术，而这一切将在以后的发 展中取得重大成就。 模拟退火算法在 TSP问题中的应用研究 第三章 问题描述与算法分析研究 9 第三章 问题描述与算法分析研究 本章介绍了模拟退火算法解决 TSP 问题的需求分析阶段的内容，是本次程序设计中的关键环节。 主要对系统进行了整体的分析，明确了系统目标，确定了开发环境，构建了基本的框架结构和功能模块。 并且确定了模拟退火算法在 TSP问题中的应用研究的主要设计思想。 应用研究整体规划 通过对程序的理解和分析，这个课题项目应该分为 2 个阶段进行。 第一阶段是模拟退火算法的描述和实现；第二阶段是在 TSP 问题中应用模拟退火算法解决问题，即模拟退火算法在 TSP 问题中的具 体实现。 应用开发环境 完成一个完整并且优秀的程序，为其配置一个良好的系统开发环境是十分必要的，接下来是介绍模拟退火算法解决 TSP 问题所需要配置的环境要求。 接下来为开发语言和系统运行平台做下简介。 开发语言 开发语言必须是 一种优秀的面向对象程序设计语言 并且 适合于系统程序设计。 C++语言是一种优秀的面向对象程序设计语言，它在 C 语言的基础上发展而来 C++以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。 面向对象的设计思想是在原来结构化程 序设计方法基础上的一个质的飞跃， C++完美地体现了面向对象的各种特性。 因此采用 c++语言进行编写程序。 开发平台 本课题开发语言选用 c++语言，可以选用的开发平台可以从 c++语言平台中选择一种出来，本课题选用 visual C++。 TSP 问题的描述和分析 旅行商问题，即 TSP 问题（ Travelling Salesman Problem）是数学领域中著名模拟退火算法在 TSP问题中的应用研究 第三章 问题描述与算法分析研究 10 问题之一。 假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。 路 径的选择目标是要求得的路径路程为所有路径之中的最小值。 一个实例如图 所示 图 TSP 问题的示意图 从图。 TSP问题的目的就是选择出 路径路程为所有路径之中的最小值 的路径。 目前人们已经构造出了许多近似求解法，如遗传法、蚁群算法、模拟退火算法等 [10]。 模拟退火算法的分析 下面介绍并且分析模拟退火算法的模型和组合优化 的问题。 模拟退火算法模型 模拟退火算法起源于物理退火。 物理退火过程： （ 1） 加温过程 （ 2） 等温过程 （ 3） 冷却过程 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想 : (1) 初始化：初始温度 T(充分大 )，初始解状态 S(是算法迭代的起点 )， 每 个 T 值的迭代次数 L。 模拟退火算法在 TSP问题中的应用研究 第三章 问题描述与算法分析研究 11 (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 逐渐减少，且 T0，然后转第 2 步。 模拟退火算法与优化问题分析 模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性 [11]。 模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程 与一般优化问题的相似性。 算法的基本思想是从一给定解开始的，从邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变坏。 它由一控制参数 t决定，其作用类似于物理过程中的温度 T，对于控制参数 t的每一取值，算法持续进行“产生新解 —— 判断 —— 接受或舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。 经过大量的解变换后，可以求得给定控制参数 t值时优化问题的相对最优解。 然后减小控制参数 t的值，重复执行上述迭代过程。 当控制参数逐渐减小并趋于零时，系统亦越来越趋于平衡状态，最后系统状态对应于优化问题的整体最优解。 应用研究方案分析 根据该课题要求，研究模拟退化算法的基本原理以及 TSP组合优化问题，用一种程序语言实现基于模拟退火算法的 TSP问题求解方法。 并且在 1个 TSP问题，问题的目标是选择出 路径路程为所有路径之中的最小值 的路径。 通过 C++语言编写并且实现出模拟退火算法。 在利用编写出的模拟退火算法模型去解决之前所建立的 TSP问题模型。 模 拟退火算法在 TSP问题中的应用研究 第四章 算法具体设计与编码实现 12 第四章 算法具体设计与编码实现 前面的章节主要介绍了问题描述与算法分析研究的内容，而本章主要是对该系统的具体实现进行了详细设计。 描绘出模拟退火算法的流 程图，了解该算法的运行机制，明确算法在系统整体设计中的具体功能和应用，并且对应用模拟退火算法求解 TSP问题做个详细的划分和描述。 具体分为基于模拟退火算法求解 TSP问题详细设计和求解 TSP问题的算法主体模块详细设计。 基于模拟退火算法求解 TSP 问题详细设计 第三章提供了模拟退火算法的大体框架和组合优化要注意的问题，这节将了解模拟退火算法的具体流程图和算法模型描述以及 模拟退火算法的参数控制问题。 模拟退火算法的应用很广泛 ， 可以求解 NP 完全问题 ， 但其参数难以控制 ，其主要问题有以下三点温度 T 的初始值设置问题 ， 退火速度问题 ， 温度管理问题。 并且这部分包括一些关键代码。 求解 TSP 问题的模拟退火算法及流程图 模拟退火算法是解决 TSP问题的有效方法之一，其最初的思想由 Metropolis在 1953年提出， Kirkpatrick在 1983年成功地将其应用在组合最优化问题中。 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 用固体退火模拟组合优化问题，将内能 E模 拟为目标函数值 f，温度 T演化成控制参数 t，即得到解组合优化问题的模拟退火算法：由初始解 i和控制参数初值 t开始，对当前解重复 “产生新解 → 计算目标函数差 → 接受或舍弃 ”的迭代，并逐步衰减 t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。 求解 TSP的模拟退火算法模型可描述如下 : 解空间：解空间 S是遍访每个城市恰好一次的所有路经，解可以表示为{w1,w2 ,……, wn} ， w1, ……, wn 是 1,2,……,n 的一个排列，表明 w1城市出发，依次经过 w2, ……, wn 城 市，再返回 w1城市。 初始解可选为 (1,……, n)。 目标函数：目标函数为访问所有城市的路径总长度。 模 拟退火算法在 TSP问题中的应用研究。