论文部分内容阅读
旅行商问题(简称TSP)既是组合优化问题又是经典的NP难问题,有很广泛的应用价值,近些年来伴随着计算机学科不断地前进,TSP这个“老问题”也逐渐回到人们的视野之中,成为了科研的新焦点,更是作为各种新算法正确性与可行性验证的重要依托。模拟退火算法自从被提出就因其简练且方便使用而具有极大的拓展空间,并且目前已经成功地投入到了很多方面的使用中,展示出了良好的效果。然而模拟退火算法依然存在着其自身的不足,即避免陷入局部极小值以及解空间的搜索能力和范围这两项指标不是很理想。本文针对模拟退火算法的两点不足,对传统的模拟退火算法进行了改进,提出了多种群多算子的模拟退火算法来求解经典的TSP问题。该算法借鉴了遗传算法的隐含并行性的优点,提出了多种群的并行机制来提高其寻优效率也就是全局最优解的寻找能力,和传统算法中一个个地优化解相比,改进了的方法在效率上有了很大的提高;为了增大解空间的搜索能力和范围,本文通过改进状态产生函数来解决,一般新路径的产生通常是用二变换法或三变换法等单一的构造方法来实现,而这里采用多种算子来产生新的解空间,并且通过某种设定概率的方式来决定运用哪种操作(即算子)来产生新的解空间,这样做大大增加了解空间的涵盖面积,进而为算法跳出局部最优解和搜索全局最优增大了可能性。本文运用了新改进的算法,通过旅行商问题来进行验证,分别对其中的CHN31、ATT48和EIL51进行求解。仿真结果表明,该算法得到了很好的效果,不仅避免了传统的模拟退火算法极易陷入局部极小值,而且增加了搜索全局最优解得质量,因而可以看出,改进后的算法提高了优化性能和优化效率。