遗传算法及其在TSP问题中的应用研究

论文摘要

遗传算法（Genetic Algorithms,简称GA）是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及其应用的研究是目前智能计算的研究热点之一。TSP问题（Traveling Salesman Problem）是已知有n个城市,现有一推销员必须遍访这n个城市,且每个城市只能访问一次,最后又必须返回出发城市。要安排其访问次序,使其旅行路线的总长度最短。TSP是经典的NP-hard组合优化问题之一,也是一个测试算法优劣性的标准问题,且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时,很不容易得到最优解。近年来,研究者们陆续采用了一些新的算法,如遗传算法、模拟退火、神经网络和蚂蚁算法等,取得了较好的效果。本文的主要工作和创新点:1、在设计交叉算子和变异算子的过程中,利用了最短路径的数学性质和统计学规律,设计出改进的启发式顺序交叉算子和启发式变异算子,并与既有的OX、CX、ERC等算子进行了比较和分析。对基因规模、变异概率和交叉概率随着代数的增加而变化的动态性质进行了实验。并对遗传算子、每代最优解的进入和退出演化过程的性能进行了分析。2、在程序实现时,大量利用了STL和Boost的既有数据结构和算法,并利用了设计模式的知识,使程序的实现更加灵活高效。3、将改进的遗传算法应用于机械加工的孔群加工顺序模拟中,取得了良好的效果。

论文目录

• 摘要
• Summary
• 第一章 绪言
• 1.1 课题研究的目的与意义
• 1.2 国内外研究现状
• 1.3 本文的组织
• 第二章 遗传算法理论概述
• 2.1 遗传算法起源和发展
• 2.2 遗传算法思想及特点
• 2.3 遗传算法原理与基本要素
• 2.3.1 遗传算法的实现涉及5个主要因素
• 2.3.2 基本原理
• 2.4 基本遗传算法
• 2.4.1 基本遗传算法的数学模型
• 2.4.2 基本遗传算法的步骤
• 第三章 TSP问题概述
• 3.1 问题的定义
• 3.2 组合优化与TSP
• 3.3 TSP的应用与价值
• 3.4 目前TSP的解法
• 3.4.1 精确算法
• 3.4.2 近似算法
• 3.4.3 智能优化算法
• 3.5 遗传算法（GA）在TSP中的应用
• 3.5.1 编码与适应度函数
• 3.5.2 交叉算子
• 3.5.3 选择算子
• 3.5.4 变异算子
• 3.6 TSP的算法评价标准
• 第四章 改进遗传算法求解TSP问题
• 4.1 改进的遗传算法
• 4.1.1 初始基因的生成
• 4.1.2 改进的启发式顺序交叉算子
• 4.2 程序实现
• 4.2.1 基本数据结构
• 4.2.2 生成初始基因
• 4.2.3 交叉算子的实现
• 4.3 应用于机械加工的孔群加工顺序模拟
• 4.3.1 孔群加工模型
• 4.3.2 计算实例
• 4.3.3 各运行参数对遗传算法效率的影响
• 4.3.4 结论
• 第五章 总结与展望
• 5.1 全文总结
• 5.2 研究展望
• 致谢
• 参考文献
• 附录