遗传算法在TSP上的应用及改进

摘要

旅行商问题(TSP)是著名的NP完全难题，也是组合优化、计算机科学界经典的问题之一。因此对TSP寻找出实际而又有效的算法，就具有重要的理论意义和实际应用价值。而遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，具有简单、通用、稳健等特性，能依概率收敛到问题的全局最优解。这就是本文提出的改进遗传算法求解TSP的目的和意义。 本文从旅行商问题的概述出发，介绍了TSP的数学描述与分类，在原有的基础上，对TSP作了更细致的分类；介绍了遗传算法的基本概念、原理、步骤及意义，将遗传算法的一些主要的操作过程用数学形式表示，使其变得简单而又公式化；通过依赖于遗传操作的基本遗传机理的叙述，为以后算法的改进打下理论基础。本文主要工作如下： (1)分析了影响遗传算法性能的一些重要参数，通过基本遗传算法(SGA)对不同种群规模的TSP问题分别进行计算机模拟仿真，讨论了基本遗传算法在求解TSP中存在的不足。 (2)针对现有的遗传算法的不足和TSP本身的特点，提出了三种改进的混合遗传算法(HGA)。 首先提出了混合遗传算法Ⅰ(HGAⅠ)，在HGAⅠ中采用了依概率近邻法，用其生成的初始种群优于随机产生初始种群，较近邻法略差，但个体多样性水平优于近邻法，而且生成的初始种群的随机路径的总长度服从正态分布。将依概率的近邻法和边重组交叉算子与启发式变异算子结合起来得到HGAⅠ。 其次为了进一步改进其性能，保证算法的全局收敛性，混合遗传算法Ⅱ(HGAⅡ)应用改良圈算法及最大容许停滞代数，不仅避免了HGAⅠ中终止进化代数的选取问题，而且大大加快了算法的收敛速度，使算法具有很好的鲁棒性。同时在HGAⅡ中采取杰出者记录与“父子混合”选择策略以及随机因素控制参数α，从理论上保证了算法的全局收敛性。 最后在混合遗传算法Ⅲ(HGAⅢ)中引入多元回归分析中的三均值的概念对遗传算法的控制参数进行动态调整，从而克服用不变的控制参数来控制遗传进化引起的“早熟”，提高了算法的搜索效率，使得算法的性能得到更好的改善。 (3)对设计出的三种混合遗传算法通过数据进行了计算机仿真模拟，对算法的性能进行了分析测试。

目录

文摘

英文文摘

论文独创性声明及论文知识产权权属声明

第一章绪论

第二章TSP的研究现状

第三章遗传算法简介

第四章遗传算法在TSP上的应用

第五章求解TSP的混合遗传算法

结束语

参考文献

攻读硕士学位期间的科研工作

致谢