摘要： 针对旅行商问题(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

中图分类号: 

• TP18