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

Multiple Population Parallel Evolutionary Spark-based Parallel Genetic Algorithm

作　　者：任刚 吴长茂[2] 魏勇 刘小杰 郜广兰 王鲜芳 REN Gang;WU Changmao;WEI Yong;LIU Xiaojie;GAO Guanglan;WANG Xianfang(School of Computer Science and Technology,Henan Institute of Technology,Xinxiang 453003,China;Laboratory of Parallel Software and Computational Science,Institute of Software,Chinese Academy of Science,Beijing 100190,China;Henan IoT Big Data Engineering Technology Research Center of Manufacturing Industry,Xinxiang 453003,China)

机构地区：[1]河南工学院计算机学院,河南新乡453003 [2]中国科学院软件研究所并行软件实验室,北京100190 [3]河南省生产制造物联大数据工程技术研究中心,河南新乡453003

出　　处：《河南工学院学报》2021年第3期26-32,共7页Journal of Henan Institute of Technology

基　　金：国家重点研发计划资助项目(2020YFB1712104,2018YFB1404404);国家自然科学基金资助项目(61802116,62072157);河南省科技攻关计划资助项目(192102210113,192102210248,202102210372,202102210153);河南工学院高层次人才科研启动基金项目(KQ1864)。

摘　　要：由于经典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.

关 键 词：Spark计算模型 并行遗传算法 多种群并行进化 旅行商问题 大数据 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]