改进的遗传算法求解TSP问题的应用与研究

摘要

旅行商问题是一个经典组合优化方面的问题。随着城市集群的规模迅猛增长，旅行商问题在搜索空间里变得越来越难寻找最优解。同时，过于冗余的改进算法给程序带来更多的负面影响。因此，寻找一个高效和便捷的遗传算法计算框架成了众多学者的研究重点。
　　对于旅行商问题这类完全问题，遗传算法具有全局搜索的优势，而它的局部搜索能力不足以及收敛速度缓慢。在传统精确算法中，它们多为局部搜索算法，一般得到局部较优解，即对小范围的城市群能够准确求出近似解。因此，近年来不断改进的遗传算法有通过和传统算法相结合成混合算法来改进，以便达到优势互补。除此之外，它也有借助相关策略的改进来提高遗传算法的性能。在改进算法中，鲜有人突出提出对于城市信息预处理来克服那些不足，有的是基于数据挖掘算法中的k均值聚类算法与遗传算法的混合算法的提出。聚类算法是以迭代时间的巨大代价来换取遗传算法处理能力的提高。
　　本文出发点依然是围绕传统遗传算法解决旅行商问题所遇到的两大问题，采取一种直接划分地图而形成区域网格的简单方式，通过划分处理城市信息数据进而改进路径编码。改进的遗传算法是将原来城市群的坐标数据根据地图区域网格单位的划分进行数据信息预处理而达到地图压缩和提炼有用信息的目的。改进的遗传算法基于对于原始数据进行域规则的数据预处理，提出了一种对传统路径编码，以及诸算子改进的遗传算法。改进的遗传算法的数据预处理将根据地图区域化特点进行网格区域划分处理，且采用提前培育的局部优秀基因块,再与整体相结合完成分阶段初始化。同时，区域划分必然存在邻近区域，进而有了对于诸算子的发生位置的指导以及发生概率的影响。后续依托数据预处理阶段处理得到的结果信息对初始种群算子，以及选择、交叉和变异等算子进行相应的改进。
　　正因为它运用类似聚类的算法划分，与数据挖掘算法的混合算法相比较而言，前期处理变得简单。研究实现结果表明，通过对城市数据进行域规则的预处理以及配套的策略相结合，可提高遗传算法的收敛速度和精确度。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 选题背景及研究意义

1.2 TSP问题及遗传算法研究现状分析

1.3 研究内容及组织结构

第二章 TSP问题的概述

2.1 TSP问题的概念

2.2 TSP问题的应用与处理算法

2.3 本章小结

第三章 遗传算法的概述

3.1 遗传算法的基础知识

3.2 遗传算法框架

3.3 本章小结

第四章 区域规则化的遗传算法

4.1 遗传算法主要区域化改进思想

4.2 区域规则化下TSP问题的数学模型和改进遗传算法步骤及流程

4.3 区域规则化的遗传算法关键技术

4.4 区域化改进遗传算法算子

4.5 实验与分析

4.6 本章小结

第五章 区域化遗传算法在TSP问题应用

5.1 区域化遗传算法在TSP问题实例应用

5.2 实验与分析

5.3 本章小节

第六章 总结与展望

6.1本文总结

6.2未来展望

参考文献

致谢

攻读学位期间的研究成果