基于Spark大数据计算模型的多种群并行进化遗传算法

Multiple Population Parallel Evolutionary Spark-based Parallel Genetic Algorithm

由于经典SPGA缺乏多种群并行进化能力,当问题规模较大时,计算效率偏低。为此,深入研究Spark大数据计算模型并行机制与多种群并行进化机制的潜在关系,将多种群并行进化机制引入经典SPGA,形成一种新的SPGA——MPE-SPGA;将提出的算法应用于TSP,选取EIL51、CH130和TSP225三种数据集,分别代表小型、中型和大型数据集。实验结果表明,提出的MPE-SPGA在小型数据集上计算时间比原算法减少3%,计算性能有小幅提升;在中型和大型数据集上,计算时间分别减少了22%和31%,性能提升显著。

Due to lacking the ability of multi-population parallel evolution,in the face of a large-scale problem,the computation efficiency of the Spark-based Parallel Genetic Algorithm(SPGA)is relatively low and hardly meets the requirements of practical applications.To address this issue,on the basis of research on relationships of Spark parallel mechanism and multi-population parallel evolution scheme,a new SPGA:Multi-population Parallel Evolutionary SPGA(MPE-SPGA)is proposed.The proposed algorithm is applied into the Travelling Salesman Problem(TSP).The three datasets,EIL51,CH130 and TSP225,are selected and represent the small,medium,and large dataset,respectively.The experiment results show that comparing to the classic algorithm,the proposed algorithm has a reduction of 3%in the computing time on the small dataset.The performance of the two algorithms have no much difference.On the medium and large problems,the proposed has a reduction of 22%and 31%,respectively,has a considerable improvement in performance.