遗传算法在TSP问题上的应用

论文摘要

旅行商问题(Travelling Salesman Problem,TSP)是一个经典的组合优化问题,也是一个NP完全题,其在实际中的应用非常广泛,例如在超大规模集成芯片制造、印刷电路板制造、机器人控制等领域。因此,研究者一直在努力寻找一种既有高质量的解,又能快速收敛的最佳或近似算法。传统的求解方法有贪婪算法、局部搜索法、分支定界法、多边交换调整法、支撑树加倍法等。近年来,出现了一些仿生类优化算法,如遗传算法、蚂蚁算法、模拟退火、神经网络等。这些算法与一些经典组合优化算法的有机结合在很大程度上改进了算法的收敛速度,提高了解的质量。本文探索将遗传算法融合在TSP问题的求解中,主要工作如下:(1)概述了旅行商问题的研究背景、研究现状、目的、意义及本文的主要工作,阐述了遗传算法及其特点、基础理论以及其研究现状。(2)概述了旅行商问题的定义、数学模型及分类,重点讨论了几种经典的旅行商问题的求解算法。(3)提出一种基于遗传算法和优化策略的求解TSP问题的混合算法,算法中设计两种交叉算子并且采用两算子结合使用的方法,使子代更好继承了父代的优秀基因,实验及分析表明了该算法的有效性。

论文目录

• 摘要
• Abstract
• 致谢
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 研究目的和意义
• 1.4 本文研究内容
• 第二章 旅行商问题
• 2.1 旅行商问题概述
• 2.1.1 定义
• 2.1.2 数学模型
• 2.2 旅行商问题的分类
• 2.3 旅行商问题的扩展
• 2.4 旅行商问题的求解算法概述
• 2.4.1 精确求解算法
• 2.4.2 近似求解算法
• 2.5 小结
• 第三章 遗传算法
• 3.1 遗传算法简介
• 3.2 遗传算法的特点
• 3.3 遗传算法的基础理论研究
• 3.4 遗传算法的发展和研究现状
• 3.5 小结
• 第四章 基于遗传算法的TSP问题的求解方法研究
• 4.1 混合遗传算法简介
• 4.2 一种求解旅行商问题的混合遗传算法
• 4.2.1 初始化种群
• 4.2.2 变异算子的设计
• 4.2.3 交叉算子的设计
• 4.2.4 算法流程
• 4.2.5 算法框架
• 4.3 实验与分析
• 4.3.1 本算法与其他算法的比较
• 4.3.2 本算法两种交叉算子的结合使用
• 4.4 小结
• 第五章 结束语
• 5.1 本文工作总结
• 5.2 未来工作展望
• 参考文献
• 攻读硕士学位期间发表论文