Abstract: According to the TSP character, an improved shuffled frog-leaping algorithm is designed. The algorithm improves the child population frog individual optimization way, not just the worst individual optimization. This way can improve the convergent speed of the algorithm effectively. In order to enhance the ability of searching, “guide optimal” probability and “guide suboptimal” probability are put forward. The “guide optimal” probability represents the global optimum solution probability that the individual reversal depends on. The “guide suboptimal” probability represents the subpopulation optimum solution probability that the individual reversal depends on. Through experiments to multiple problems of the TSPLIB, the results show that the algorithm is feasible and effective.

Key words: combinatorial optimization problem, Traveling Salesman Problem（TSP）, shuffled frog-leaping algorithm, probability, TSPLIB

摘要： 针对TSP问题的特点，设计了一种求解TSP问题的改进的混合蛙跳算法。该算法改进了子种群青蛙个体优化的方式，而不仅是对最坏个体进行优化，这种方式可以有效提高算法的收敛速度。提出了青蛙个体翻转时依赖于全局最优解的“导优”概率和依赖于子种群局部最优解的“导次优”概率，进一步提高了算法寻找最优解的能力。在多个TSPLIB上的实验结果表明，该算法是可行有效的。

关键词: 组合优化问题, 旅行商问题（TSP）, 混合蛙跳算法, 概率, TSPLIB