论文部分内容阅读
本文从现有的求解TSP的算法入手,介绍了几种常见算法的主要思想。研究表明,遗传算法和模拟退火算法在解决TSP的过程中表现出了一定的优势,并且在实际问题的求解中得到了广泛的应用。本文针对这两种算法进行了深入研究并编程实现,发现了基于全局搜索的遗传算法和基于局部搜索的模拟退火算法在求解TSP上的不足。于是在这两种算法的基础上,分别提出了两种算法的改进方法,并验证了改进后算法的有效性。同时基于两种改进算法,提出了一种混合遗传模拟退火算法,用于求解旅行商问题。首先,混合算法采用混合方法产生初始种群,提高了初始群体的质量,增大了搜索到最优解的概率。另一方面,算法通过海选择优的方式,充分发挥了优秀基因的特性,大大减少了遗传的代数,提高了收敛速度,并有效防止种群早熟现象,避免陷入局域最优解;最后,算法通过模拟退火过程,提升了获得更优解的概率,并对路径进行优化处理,使得到的解尽可能更优。相比单一的遗传算法或模拟退火算法求解,该混合算法在实例中表现出了更优异的可行性和有效性。