向量编码遗传算法求解TSP问题的研究

论文摘要

本文首先对遗传算法的原理、技术、理论做了介绍,然后描述了TSP问题,并给出其数学模型.在提出改进的遗传算法之前,先对求解TSP问题常用的遗传算法技术进行介绍,充分分析了矩阵编码的缺点之后,提出了一种新的编码技术——向量编码,并利用基于向量编码的遗传算法求解了TSP问题。作者编写了基于向量编码遗传算法的Matlab程序,试验表明,向量编码遗传算法对求解TSP问题效果较为理想。在改进的遗传算法编码方案中,提出了Hamilton矩阵的概念;根据向量编码的形式,提出一种比较好的不可行解修正技术,这种技术的优点是尽最大程度不破坏染色体的结构,尽力保持父代和子代个体相似度,以便染色体结构遗传到下一代,使得优良模式生存下去;为了使读者能够更加深刻地理解本文提出向量编码方案的动机,也为了让读者不至于混淆向量编码和矩阵编码,在提出向量编码遗传算法和相关的技术之后,将向量编码遗传算法和矩阵编码遗传算法在理论上作了比较,并对矩阵编码遗传算法的缺点和向量编码的优点进行了分析。最后,本文采用改进的遗传算法对TSP问题的求解过程进行了算法设计和实现,通过试验,得出了一个较理想的结果,验证了本文提出的遗传编码方案的正确性和可行性。

论文目录

• 摘要
• Abstract
• 第1章 遗传算法原理
• 1.1 基本遗传算法
• 1.1.1 遗传算法思想
• 1.1.2 遗传算法运行过程
• 1.1.3 基本遗传算法的步骤
• 1.2 遗传算法的特点
• 1.3 遗传算法存在的问题
• 1.3.1 欺骗性问题
• 1.3.2 未成熟收敛问题
• 第2章 遗传算法技术及理论
• 2.1 遗传算法基本技术
• 2.2 遗传算法改进途径
• 2.3 遗传算法改进技术
• 2.4 遗传算法数学理论
• 2.4.1 模式定理
• 2.4.2 积木块假设
• 第3章 求解 TSP 问题的常用遗传算法技术
• 3.1 TSP 问题
• 3.2 TSP 问题数学模型
• 3.3 求解 TSP 问题的若干遗传算法技术
• 3.3.1 常用编码技术和遗传算子
• 3.3.2 矩阵编码遗传算法求解 TSP 问题相关技术
• 第4章 向量编码遗传算法求解 TSP 问题
• 4.1 向量编码遗传算法的提出
• 4.2 向量编码遗传算法基本技术
• 4.3 向量编码遗传算法求解 TSP 问题的相关技术
• 4.4 向量编码与矩阵编码遗传算法相关技术比较
• 第5章 算法实现与验证
• 5.1 算法步骤
• 5.2 试验
• 总结与展望
• 参考文献
• 致谢
• 附录一
• 附录二