基于Spark的并行遗传算法在旅行商问题中的应用

摘要

传统遗传算法存在早熟现象,而且其在海量数据模型下的求解精度和可扩展性也有待提高.为了改进上述问题,在研究孤岛模型和细粒度模型优势基础上,利用遗传算法自身的并行性,提出一种仿细粒度的粗粒度并行模型,基于Spark实现了一种双层并行的遗传算法.将改进算法应用于旅行商问题Berlin52数据集的求解,实验结果表明,与传统的并行模型相比,改进后的算法可以明显缩短计算时间,增大搜索范围,早熟现象也得到了改善.%The conventional genetic algorithm (GA) existed premature phenomenon,and its precision and expanding needed to be improved under the massive data set.To improve the problems above,using GA's inner parallel property,this paper implemented a bilayer parallel GA based on the advantage of island model and fine-grained model on Spark.The experiment applied the improved algorithm to traveling salesman problem(TSP) in Berlin52 data sets.The results show that compared with the traditional parallel model,the improved algorithm can significantly shorten the calculation time,increase the searching scope,and the premature phenomenon is improved.