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

第40 卷 第1 期 计 算 机 工 程 2014 年1 月 Computer Engineering January 2014 Vol.40 No.1 文献标识码文献标识码：：A 文献标识码文献标识码：： 中图分类号中图分类号：：TP18 文章编号文章编号：：1000——3428(2014)01——0191——04 中图分类号中图分类号：： ·人工智能及识别技术·人工智能及识别技术·· 文章编号文章编号：： —— —— —— ··人工智能及识别技术人工智能及识别技术·· 基于分段混合蛙跳算法的旅行商问题求解基于分段混合蛙跳算法的旅行商问题求解 基于分段混合蛙跳算法的旅行商问题求解基于分段混合蛙跳算法的旅行商问题求解 郭小燕郭小燕，王联国，王联国 ，代永强，代永强 郭小燕郭小燕，，王联国王联国，，代永强代永强 (甘肃农业大学信息科学技术学院，兰州 730070) 摘摘 要：要 ：针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题 ，提出一种解决 TSP 问题的分段混合蛙跳算法(S-SFLA) 。 摘摘 要要 ：： 该算法在搜索初期利用逆转变异算子减少交叉路径 ，在搜索的后期引入邻域搜索(个体邻域 ，局部最优领域，全局最优邻域)增加种 群多样性 。在整个搜索过程中记忆全局历史最优解与局部历史最优解 ，进行全局更新和局部更新，避免迂回搜索。在局部更新中， 每一个青蛙都有机会得到更新。实验结果表明，与遗传算法、蚁群算法、基本蛙跳算法相比，S-SFL 算法在求解中等规模的 TSP 问题上具有更快的搜索速度和更高的求解精度。 关键词关键词：混合蛙跳： ；分段；旅行商问题；逆转变异算子；邻域搜索 关键词关键词：： Traveling Salesman Based on Subsection Shuffled Frog Leaping Algorithm GUO Xiao-yan, WANG Lian-guo, DAI Yong-qiang (School of Information and Science Technology,