求解TSP问题的混合演化算法研究

论文摘要

TSP问题(Traveling Salesman Problem)是一个组合优化方面的问题,已经成为并将继续成为测试组合优化混合演化算法的标准问题。从理论上讲,使用穷举法不但可以求解TSP问题,而且还可以求出该问题的最优解。但是对现有的计算机来说,使用常规的穷举法在如此庞大的搜索空间中寻求最优解,几乎是不可能的。所以,各种求TSP问题近似解的优化算法应运而生了,本文所用到的混合演化算法也在其中。 演化算法是一种模拟自然界自适应演化过程而发展起来的通用问题求解方法。它采用简单的编码技术来表示各种复杂的结构,并通过对编码进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。简单的遗产操作和优胜劣汰的自然选择机制使演化算法具有不受搜索条件的限制、不需要其它辅助信息的特点。它采用的种群搜索模式,有利于搜索到全局最优解,能较好的解决解的局部性问题。因此,演化算法被广泛的用来求解具有挑战性的问题。 这里本文为解决TSP的演化算法提出了一种新的双近邻表示法,因为传统的路径表示方法是不适合演化过程处理的。这种能够将每个路径唯一表示的新的方法提高了演化算子的继承能力。这种表示法的性质和操作,构成了新的混合演化算法的参数和演化算子。然后为了提高收敛速度,演化算法混合了局部优化算法。 局部优化算法是常用的解决TSP问题的算法,也常是其它方法的一个部分。它具有非常高的运行效率。不同的局部优化算子的性能也在文中做了分析。本文提出的混合局部优化算法,虽然是混合演化算法的一个部分,但它也能独立的解决TSP问题。 大量的标准测试问题的实验结果表明本文提出的算法能够全部达到或更优于现存最优解。而在效率测试中,虽然混合局部优化具有很好的运行效率,而新的混合演化算法能得到更好的解,并且效率还不错。实验部分也实现了多线程并行的混合演化算法。从实验结果来看,达到了并行效果,也揭示了演化算法本质的并行性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 问题的提出
• 1.2 研究背景
• 1.3 本文组织结构
• 第二章 混合局部优化
• 2.1 概述
• 2.2 局部优化算子
• 2.2.1 反序
• 2.2.2 三交换
• 2.2.3 跳动
• 2.2.4 互换
• 2.3 算子性能
• 2.4 混合局部优化算子
• 2.5 小结
• 第三章 路径的表示方法
• 3.1 概述
• 3.2 路径的常见表示法
• 3.2.1 自然表示法
• 3.2.2 次序表示法
• 3.2.3 近邻表示法
• 3.3 双近邻表示法
• 3.3.1 双近邻表示法定义
• 3.3.2 片断的双近邻表示法
• 3.3.3 片断的性质
• 3.3.4 收集操作
• 3.3.5 连接操作
• 3.3.6 截断操作
• 3.3.7 路径的相似度
• 3.4 小结
• 第四章 混合演化算法
• 4.1 优化算法
• 4.1.1 基本概念和术语
• 4.1.2 优化算法
• 4.1.3 演化算法
• 4.2 混合演化算法
• 4.2.1 混合演化算法的设计与框架
• 4.2.2 混合演化杂交算子
• 4.2.3 禁止相似个体繁殖的改进杂交算子
• 4.2.4 混合演化变异算子
• 4.3 小结
• 第五章 实验与分析
• 5.1 算法实现
• 5.1.1 软硬件技术平台
• 5.1.2 功能
• 5.2 样例和参数选择
• 5.3 混合演化算法实验与分析
• 5.3.1 与现存最优解的比较
• 5.3.2 收敛性与拓展性分析
• 5.3.3 参数分析
• 5.4 混合局部优化实验与分析
• 5.4.1 不同的混合局部优化算子
• 5.4.2 混合演化算法和混合局部优化的实验与分析
• 5.5 混合演化算法的并行实现
• 5.5.1 多线程算法框架
• 5.5.2 测试结果
• 5.5.3 测试结果分析
• 第六章 总结与展望
• 参考文献
• 读研期间发表的学术论文
• 致谢