求解TSP问题的遗传算法研究

摘要

遗传算法(Genetic Algorithms)是一种模仿生物自然进化过程的随机搜索和优化算法,其优势在于可以高效的处理传统搜索方法难以求解决的非线性问题.遗传算法具有全局优化性和易操作性,由于其不受搜索空间的限制性假设的约束,具有广泛的适应性、并行性等特点,目前被广泛应用于函数优化、机器学习、模式识别等众多领域,并逐渐成为人工智能领域的一个研究热点.
　　TSP问题是一个经典的组合优化问题中的NP难问题,有效地解决TSP问题在可计算理论上有着重要的理论价值,同时也有着极高的实际应用价值.而且遗传算法在 TSP问题求解问题的应用研究,对于构造合适的遗传算法框架、建立有效的遗传操作等都有重要意义.
　　本文从求解TSP问题出发对遗传算法作了细致地分析及研究.首先介绍了遗传算法的理论及应用领域;然后针对TSP问题的求解进一步指出遗传算法求解TSP问题一大难题是如何快速收敛到最优解并防止”早熟”现象发生.为了解决这一难题,本文对群体、遗传算子作了详细地讨论,得出解决”早熟”现象的一些微观策略;对于遗传算法在进化后期局部搜索能力较差,可以适当的加入局部搜索算法提高其运行效率.根据这些策略对遗传算法进行改进:结合TSP问题最优路径中一般包含城市与其最近城市相连的特点,提出了两点插入变异算子,改进了启发式交叉算子,并根据个体适应度与群体平均适应度的比较赋予不同的变异概率,使得较好的个体探测路径,较差的个体开发新个体.另外,对初始群体进行局部优化提高其质量加快算法的收敛速度;若最优个体连续几代一直保留,则采用局部微调对其进行局部搜索,从而使得子代中最优个体跳离局部解.通过仿真实验,改进的算法能较快地收敛到TSP问题的已知最优解;其测试结果与国际标准测试库TSPLIB中的最优路径相比,或接近或优于。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1 研究背景及研究意义

§1.2 本文的主要工作及创新点

§1.3 本文篇章组织

第二章 遗传算法简介

§2.1 遗传算法的产生与发展

§2.2 遗传算法的基本描述

§2.3 遗传算法的模式定理

§2.4 遗传算法的特点

§2.5 遗传算法的应用领域

第三章 旅行商问题

§3.1 旅行商问题概述

§3.2 TSP问题的求解方法

第四章 遗传算子的分析与设计

§4.1 群体的分析与设计

§4.2 选择算子的性质分析

§4.3 交叉算子的性质分析

§4.4 变异算子的性质分析

§4.5 适应性微观遗传策略的设计

§4.6 微观策略与早熟问题

§4.7 宏观策略

§4.8 本章小结

第五章 改进遗传算法及在TSP问题上应用

§5.1 2-opt局部搜索算法

§5.2 主要的改进操作

§5.3 改进遗传算法的实现

§5.4 仿真实验及分析

第六章 结论与展望

参考文献

致谢

作者在攻读硕士期间的主要研究成果