遗传算法在TSP问题上的应用

旅行商问题(Travelling Salesman Problem,TSP)是一个经典的组合优化问题,也是一个NP完全题,其在实际中的应用非常广泛,例如在超大规模集成芯片制造、印刷电路板制造、机器人控制等领域。因此,研究者一直在努力寻找一种既有高质量的解,又能快速收敛的最佳或近似算法。传统的求解方法有贪婪算法、局部搜索法、分支定界法、多边交换调整法、支撑树加倍法等。近年来,出现了一些仿生类优化算法,如遗传算法、蚂蚁算法、模拟退火、神经网络等。这些算法与一些经典组合优化算法的有机结合在很大程度上改进了算法的收敛速度,提高了解的质量。 本文探索将遗传算法融合在TSP问题的求解中,主要工作如下: (1)概述了旅行商问题的研究背景、研究现状、目的、意义及本文的主要工作,阐述了遗传算法及其特点、基础理论以及其研究现状。 (2)概述了旅行商问题的定义、数学模型及分类,重点讨论了几种经典的旅行商问题的求解算法。 (3)提出一种基于遗传算法和优化策略的求解TSP问题的混合算法,算法中设计两种交叉算子并且采用两算子结合使用的方法,使子代更好继承了父代的优秀基因,实验及分析表明了该算法的有效性。