求解旅行商问题的进化算法

论文摘要

进化算法是人们从大自然的生物进化过程所得到的灵感中发展起来的一种现代优化方法,它作为一种新型的、模拟生物进化过程的随机化搜索、优化方法,具有全局优化,隐并行性,鲁棒性强,操作简单等特点,近十几年来在组合优化领域得到了相当广泛的应用,并已在解决诸多典型的组合优化问题(如旅行商问题)中显示了良好的性能和效果。首先,针对一类特殊的大规模旅行商问题,比如说城市可以分为若干组、而且各组内城市之间的距离较小的问题,本文提出了一种基于聚类以及局部搜索技术的新进化策略来进行求解,并且证明了该算法的全局收敛性。其次,针对对称型的旅行商问题,本文设计了一个新的进化算法进行求解,该算法设计了新的交叉算子和变异算子来产生后代以及一种局部搜索方法来改善解的质量,同时被证明是全局收敛的。最后,数值模拟实验结果表明,本文所提出的这两个算法都是有效的。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 进化算法的产生与发展
• 1.3 进化算法的应用
• 1.4 本文的主要工作与结构安排
• 第二章 旅行商问题
• 2.1 旅行商问题的发展历史
• 2.2 旅行商问题的定义
• 2.3 旅行商问题的应用和价值
• 2.4 旅行商问题的计算复杂性
• 2.5 求解旅行商问题的已有算法
• 第三章 进化算法介绍
• 3.1 进化算法的基本概念
• 3.2 进化算法的主要分支
• 3.3 进化算法的收敛性
• 3.4 进化算法设计的原则与步骤
• 3.5 用进化算法求解TSP
• 第四章 求解旅行商问题的一种基于聚类及局部搜索技术的进化策略
• 4.1 用聚类方法把所有的城市分成若干组
• 4.2 局部搜索
• 4.3 连接聚类的策略
• 4.4 变异算子
• 4.5 基于聚类及局部搜索的进化策略
• 4.6 全局收敛性
• 4.7 数值模拟
• 4.8 结论
• 第五章 求解旅行商问题的一个新进化算法
• 5.1 编码方式
• 5.2 适应度函数
• 5.3 交叉算子
• 5.4 局部搜索
• 5.5 变异算子
• 5.6 求解旅行商问题新的进化算法
• 5.7 全局收敛性
• 5.8 数值模拟
• 5.9 结论
• 结束语
• 致谢
• 参考文献
• 在读期间的研究成果