混合蛙跳遗传算法求解旅行商问题

Research on hybrid leapfrog genetic algorithm for solving the traveling salesman problem

遗传算法是一种启发式智能优化算法,但在解决城市规模较大的巡回旅行商问题时往往存在着许多问题和不足。以大型巡回旅行商问题作为研究的切入点,对遗传算法、蛙跳算法进行了混合研究。根据巡回旅行商问题的离散特征,提出了离散蛙跳搜索策略;结合两种算法的特点,给出算法的混合思想,并运用Web技术设计了并行分布式混合蛙跳遗传算法(PC-SFLA-GA),进而针对4种不同规模的TSP问题进行了实验测试。测试结果表明:PC-SFLA-GA算法的全局搜索能力、收敛速度都有了比较明显的改善,算法稳定性较高。

Genetic algorithm is a heuristic intelligent optimization algorithm,but there are many problems and shortcomings in solving traveling salesman problem in large scale of city.Based on the large-scale traveling salesman problem as the starting point of the research,a hybrid study of genetic algorithm and hybrid leapfrog algorithm are presented.Based on the discrete characteristics of the traveling salesman problem,the strategy of the discrete frog leap search is proposed.Based on the characteristics of two algorithms,the hybrid idea of the two algorithms is given,and then a parallel distributed hybrid leap-frog genetic algorithm(PC-SFLA-GA)is implemented by using Web technique.Four TSP problems of different sizes were tested.The experimental results show that the PC-SFLA-GA algorithm has high stability and obvious improvement in global search ability and convergence speed.