应用LK算法求解旅行商问题的混合蚂蚁算法

摘要：

目前求解TSP问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法,文章通过对几种局部搜索的灵活运用,并结合改进的接受准则接受局部优化解,提出了一种高效的混合蚂蚁算法.算法前期使用3-opt这种简单高效的局部搜索的解初始化信息素矩阵,加快收敛速度,后期采用改进的Lin-Kernighan算法生成局部优化解然后依Metropolis接受准则概率接受,有效地避免陷入局部最优,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性.

关键词：最大最小蚂蚁算法、局部搜索优化、Lin-Kernighan算法、Metropolis接受准则、旅行商问题

所属期刊栏目：34

分类号：TP301.6(计算技术、计算机技术)

资助基金：湖南省自然科学基金06JJ50107

在线出版日期：2008-05-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：228-230