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

摘要

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

目录

文摘

英文文摘

独创性声明及关于论文使用授权的说明

第一章绪论

第二章混合局部优化

第三章路径的表示方法

第四章混合演化算法

第五章实验与分析

第六章总结与展望

参考文献

读研期间发表的学术论文

致谢