改进遗传算法在TSP中的应用

论文摘要

旅商问题(Traveling Salesman Ploblem简称TSP)可描述为:商品推销员打算从驻地出发遍访他要去的每个城市,并且每个城市只能访问一次,最后必须返回出发城市。问如何安排他对这些城市的访问次序,可使其旅行路线的总长度最短?用图论的术语来说,旅商问题就是在赋权完全图上找一个权最小的Hamilton圈的过程,并且由于TSP问题的特性,使之成为比较各种优化算法的标准。TSP问题属于NP完全问题,用传统的数学方法很难求解。遗传算法在处理NP问题上有自己独特的优势,但同时简单遗传算法在处理TSP问题时,会产生“早熟”现象,也就是在收敛到最优解之前,算法停止进化过程。这种现象导致了问题解的质量不高,局部精确搜索能力不够。 通过对遗传算法三种算子(选择、交叉、变异)分析和对模式定理的介绍,分析了产生“早熟”的原因主要是迭代过程中染色体基因信息的丢失。在此基础上,研究了以迭代次数为函数的递减变异算子和主动进化变异算子,并将两种算子结合,形成了新的有效防止“早熟”发生的改进变异算子。 在改善算法局部精确搜索能力方面,首先研究了简单遗传算法的寻优规律,比对了运筹学中动态规划解答TSP问题的方法后,在简单遗传算法基础上,引入了动态规划多阶段方法这一“非自然”规律,并且提出了多阶段遗传算法。 改进变异算子和多阶段遗传算法在理论上和试验中是相互补充的,因此,通过前面的分析研究,构造出改进遗传算法。该算法在处理TSP问题上,很大程度防止了“早熟”现象的产生,提高了解的质量,增强了算法的局部精确搜索能力。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 遗传算法介绍
• 1.1.1 遗传算法理论基础
• 1.1.2 三类遗传算子
• 1.1.3 遗传算法研究现状
• 1.2 TSP问题
• 1.2.1 TSP问题介绍
• 1.2.2 简单遗传算法求解TSP问题及其缺点
• 1.3 本文研究主要内容
• 第二章 改进变异算子研究
• 2.1 早熟现象分析
• 2.1.1 三类算子作用研究
• 2.1.2 模式定理
• 2.1.3 早熟分析
• 2.2 改进变异算子
• 2.2.1 递减变异算子
• 2.2.2 主动进化变异算子
• 2.2.3 改进变异算子
• 第三章 改进遗传算法
• 3.1 简单遗传算法寻优规律分析
• 3.2 运筹学处理TSP问题方法
• 3.2.1 动态规划基本概念
• 3.2.2 动态规划基本思想和最优性原理
• 3.2.3 动态规划求解TSP问题过程
• 3.3 遗传算法中引入非自然规则
• 3.3.1 非自然规律引入研究
• 3.3.2 多阶段进化策略和多阶段遗传算法
• 3.4 改进遗传算法
• 3.4.1 改进变异算子与多阶段算法参数调整
• 3.4.2 改进遗传算法
• 第四章 仿真实验
• 4.1 改进遗传算法在TSP中应用
• 4.1.1 使用软件简介
• 4.1.2 求解TSP问题的数据要求
• 4.1.3 TSP问题的仿真实验主要程序代码
• 4.2 仿真实验结果
• 4.2.1 仿真实验设计方案
• 4.2.2 仿真实验结果分析
• 第五章 结论
• 5.1 改进遗传算法特点
• 5.2 不足与研究展望
• 5.2.1 改进遗传算法不足
• 5.2.2 研究展望
• 致谢
• 参考文献
• 附录A（攻读学位期间发表论文目录）