作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

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

郭小燕,王联国,代永强   

  1. (甘肃农业大学信息科学技术学院,兰州 730070)
  • 收稿日期:2012-11-27 出版日期:2014-01-15 发布日期:2014-01-13
  • 作者简介:郭小燕(1976-),女,副教授、硕士,主研方向:人工智能,数据库技术;王联国,教授、博士;代永强,讲师、硕士
  • 基金资助:
    国家自然科学基金资助项目“混合蛙跳算法及应用研究”(61063028)

Traveling Salesman Problem Solution Based on Subsection Shuffled Frog Leaping Algorithm

GUO Xiao-yan, WANG Lian-guo, DAI Yong-qiang   

  1. (School of Information and Science Technology, Gansu Agriculture University, Lanzhou 730070, China)
  • Received:2012-11-27 Online:2014-01-15 Published:2014-01-13

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

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

Abstract: Because reduction of the diversity of solution causes the reduction of search speed and accuracy at the same time in the later period of search according to Traveling Saleman Problem(TSP). A Subsection Shuffled Frog Leaping Algorithm(S-SFLA) is proposed. In the initial period of search, in-over operator is used to reduce cross paths. In the latter period, the neighborhood search(individual neighborhood, local optimal area, the global optimal neighborhood) is introduced to increase the diversity of population. In the whole search process, global optimal solution of history and the local optimal solution of history are remembered to avoid circuit search, and in the process of local update, every frog has the opportunity to be updated. Experimental results show that, compared with genetic algorithm, ant colony algorithm, basic leapfrog algorithm, S-SFLA algorithm has higher precision and search speed in solving TSP problem of medium scale.

Key words: shuffled frog leaping, subsection, Traveling Saleman Problem(TSP), in-over mutation operator, neighborhood search

中图分类号: