摘要
遗传算法是一种启发式智能优化算法,但在解决城市规模较大的巡回旅行商问题时往往存在着许多问题和不足。以大型巡回旅行商问题作为研究的切入点,对遗传算法、蛙跳算法进行了混合研究。根据巡回旅行商问题的离散特征,提出了离散蛙跳搜索策略;结合两种算法的特点,给出算法的混合思想,并运用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.
作者
唐天兵
张铭明
蒙祖强
TANG Tian-bing;ZHANG Ming-ming;MENG Zu-qiang(School of Computer and Electronical Information,Guangxi University,Nanning 530004,China)
出处
《广西大学学报(自然科学版)》
CAS
北大核心
2018年第5期1811-1817,共7页
Journal of Guangxi University(Natural Science Edition)
基金
国家自然科学基金资助项目(61762009)
广西自然科学基金资助项目(2015GXNSFAA139292)
关键词
并行分布式计算
旅行商问题
遗传算法
蛙跳算法
distributed parallel computing
traveling salesman problem
genetic algorithm
frog leaping algorithm