基于分段混合蛙跳算法的旅行商问题求解

摘要：

针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题，提出一种解决TSP问题的分段混合蛙跳算法(S-SFLA)。该算法在搜索初期利用逆转变异算子减少交叉路径，在搜索的后期引入邻域搜索(个体邻域，局部最优领域，全局最优邻域)增加种群多样性。在整个搜索过程中记忆全局历史最优解与局部历史最优解，进行全局更新和局部更新，避免迂回搜索。在局部更新中，每一个青蛙都有机会得到更新。实验结果表明，与遗传算法、蚁群算法、基本蛙跳算法相比，S-SFLA算法在求解中等规模的TSP问题上具有更快的搜索速度和更高的求解精度。

关键词：混合蛙跳、分段、旅行商问题、逆转变异算子、邻域搜索

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金资助项目“混合蛙跳算法及应用研究”61063028

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

页数：共5页

页码：191-194,198