改进的TSP进化求解算法研究

论文摘要

遗传算法是一种模拟自然界生物进化的搜索算法,粒子群算法是群体智能的体现,模仿鱼群和鸟群觅食行为发展起来的,均属于进化算法。两者之间有很多相似之处,均简单易行、鲁棒性强,不需要专门的领域知识而仅用适应度函数做评价来指导搜索过程,从而得到了广泛的应用,引起了专家学者的广泛关注,得到了很多显著的成果。TSP问题是一个典型的NP难题,它的思想在生活生产中运用很广,提高TSP问题的解决效率有着现实的意义。因为NP问题不能在多项式时间内得到最优解。因此设计出相应的算法尽快的得到近似解和满意解是很现实的。智能算法就是在这样的思想指导下被运用于TSP问题的。本文对遗传算法和粒子群算法的理论与运用做了一些探讨。首先介绍了两种算法的原理和应用,其次分析了TSP问题的研究现状、数学模型和解决方案。接着介绍了两种算法在求解TSP问题中的应用和发展。在此基础上,针对TSP问题、遗传算法和粒子群算法进化求解的特点,提出了环路插入方法生成初始种群。并从遗传算法和粒子群算法的理论基础入手证明了该方法产生的种群对算法的有效性。在MATLAB环境下对UCI标准数据库中的数据进行了实验,结果表明了该方法产生初始群体的合理性,本文将使用该方法产生初始种群(粒子群)的算法与其他几种初始化方法进行了比较,实例仿真证明了该算法的可行性和有效性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 遗传算法与粒子群算法概述
• 1.1.2 TSP 问题
• 1.2 本文研究内容
• 第二章 遗传算法与粒子群算法
• 2.1 遗传算法
• 2.1.1 遗传算法的起源和发展
• 2.1.2 遗传算法的步骤和流程图
• 2.1.3 遗传算法的数学基础
• 2.1.4 遗传算法的基本技术
• 2.1.5 遗传算法的特点
• 2.2 粒子群算法
• 2.2.1 粒子群算法的起源与发展
• 2.2.2 粒子群算法的步骤和流程图
• 2.2.3 粒子群算法特点
• 2.3 算法的应用
• 2.4 小结
• 第三章 TSP 问题
• 3.1 TSP 问题概述
• 3.1.1 TSP 问题的定义和数学模型
• 3.1.2 TSP 问题的分类
• 3.1.3 TSP 问题的扩展
• 3.1.4 研究TSP 问题的意义
• 3.2 TSP 问题的求解
• 3.2.1 精确解法
• 3.2.2 启发式算法
• 3.3 小结
• 第四章 求解TSP 问题
• 4.1 遗传算法求解TSP 问题的基本方法
• 4.1.1 编码
• 4.1.2 初始群体
• 4.1.3 适应度函数
• 4.1.4 选择算子
• 4.1.5 交叉算子
• 4.1.6 变异算子
• 4.1.7 终止条件
• 4.1.8 算法步骤
• 4.2 粒子群算法解决TSP 问题
• 4.2.1 粒子编码和初始种群的生成
• 4.2.2 适应度函数
• 4.2.3 群体更新
• 4.2.4 终止条件
• 4.2.5 算法步骤
• 4.4 小结
• 第五章 求解TSP 问题的进化算法改进
• 5.1 常用初始种群生成方法的分析
• 5.2 改进的初始种群方法
• 5.2.1 环路插入法介绍
• 5.2.2 环路插入法的理论分析
• 5.3 实例仿真
• 5.3.1 环路插入法有效性实验
• 5.3.2 环路插入法在遗传算法中的应用
• 5.3.3 环路插入法在粒子群算法中的应用
• 5.4 小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 工作展望
• 参考文献
• 成果目录
• 致谢