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

发布时间：2019-03-31 17:53

【摘要】：传统遗传算法存在早熟现象,而且其在海量数据模型下的求解精度和可扩展性也有待提高。为了改进上述问题,在研究孤岛模型和细粒度模型优势基础上,利用遗传算法自身的并行性,提出一种仿细粒度的粗粒度并行模型,基于Spark实现了一种双层并行的遗传算法。将改进算法应用于旅行商问题Berlin52数据集的求解,实验结果表明,与传统的并行模型相比,改进后的算法可以明显缩短计算时间,增大搜索范围,早熟现象也得到了改善。
[Abstract]:The traditional genetic algorithm has the phenomenon of premature, and its precision and expansibility in the mass data model need to be improved. In order to improve the above-mentioned problems, on the basis of studying the advantages of island model and fine-grained model, a coarse-grained parallel model simulating fine-grained genetic algorithm is proposed by using the parallelism of genetic algorithm itself, and a double-layer parallel genetic algorithm is implemented based on Spark. The improved algorithm is applied to solve the Berlin52 data set of traveling Salesman problem. The experimental results show that the improved algorithm can obviously shorten the computing time, enlarge the search range and improve the premature phenomenon compared with the traditional parallel model.
【作者单位】： 河北工业大学计算机科学与软件学院;河北省大数据计算重点实验室;
【基金】：天津市应用基础与前沿技术研究计划资助项目(13JCQNJC00200) 河北省自然科学基金资助项目(F2015202311)
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 王大志;汪定伟;闫杨;;一类多旅行商问题的计算及仿真分析[J];系统仿真学报;2009年20期

2 莫愿斌;刘贺同;王勤;;旅行商问题的综述教学研究[J];中国科教创新导刊;2008年08期

3 苏丽杰,聂义勇;现实旅行商问题[J];小型微型计算机系统;2005年04期

4 顾大权;徐四林;袁媛;汪晋;;求解旅行商问题的一个有效算法[J];解放军理工大学学报(自然科学版);2006年02期

5 陈文兰;戴树贵;;旅行商问题算法研究综述[J];滁州学院学报;2006年03期

6 江贺;张宪超;陈国良;;有向黑白旅行商问题[J];计算机学报;2007年03期

7 管琳;白艳萍;;用分支定界算法求解旅行商问题[J];中北大学学报(自然科学版);2007年02期

8 黄可为;汪定伟;;热轧计划中的多旅行商问题及其计算方法[J];计算机应用研究;2007年07期

9 张敏;金琴玲;;旅行商问题的一种新解法[J];重庆职业技术学院学报;2008年01期

10 高春涛;;求解旅行商问题的几种解法[J];边疆经济与文化;2010年05期

相关会议论文 前10条

1 冯纯伯;;旅行商问题的一种解法[A];1991年控制理论及其应用年会论文集（下）[C];1991年

2 张雷;郑维敏;;广义旅行商问题、放映员问题和一类调度模型[A];1996年中国控制会议论文集[C];1996年

3 胡巧华;吴怀宇;陈乔礼;陈媛;;一种求解旅行商问题的启发交叉算子的研究[A];第25届中国控制会议论文集（中册）[C];2006年

4 张辉;王锡淮;肖健梅;;基于改进蚁群算法的旅行商问题[A];2007中国控制与决策学术年会论文集[C];2007年

5 李大卫;王梦光;;热轧调度与多旅行商问题[A];1996年中国控制会议论文集[C];1996年

6 刘春波;潘丰;杨丹;;基于改进的蚁群算法在中国旅行商问题中的求解[A];2007中国控制与决策学术年会论文集[C];2007年

7 冯纯伯;蒋珉;;应用模拟电场法解旅行商问题[A];1993年控制理论及其应用年会论文集[C];1993年

8 李丽;程玉荣;牛奔;;离散人工蜂群算法求解旅行商问题[A];第十三届中国管理科学学术年会论文集[C];2011年

9 孙启瑞;李俊;丁健;戴先中;;新型访问域部分重叠的多旅行商问题的GA求解[A];2013年中国智能自动化学术会议论文集（第四分册）[C];2013年

10 韩爱丽;朱大铭;;旅行商问题的一种新DNA编码方案[A];2006年全国理论计算机科学学术年会论文集[C];2006年

相关博士学位论文 前4条

1 张梦颖;不确定因素下路径规划问题研究[D];中国科学技术大学;2016年

2 温新刚;基于服务时间约束的在线旅行商问题研究[D];西安交通大学;2017年

3 谭阳;求解广义旅行商问题的若干进化算法研究[D];华南理工大学;2013年

4 王刚;两类圈问题的算法研究[D];国防科学技术大学;2013年

相关硕士学位论文 前10条

1 刘欣欣;旅行商问题的基因片段插入算法研究[D];闽南师范大学;2015年

2 陈玲;基于PSO-GA混合算法的时间优化的旅行商问题的研究[D];合肥工业大学;2015年

3 赵丽娜;带油耗的单商品取送货旅行商问题研究[D];沈阳师范大学;2016年

4 毛巍;一种新的改进人工蜂群算法及其在旅行商问题中的应用[D];四川理工学院;2016年

5 卢雨潇;基于多头绒泡菌模型的优化蚁群算法及其在旅行商问题中的运用[D];西南大学;2016年

6 肖聪;农产品配送中的流旅行商问题及启发式算法的研究[D];吉林农业大学;2016年

7 孙文成;基于多目标方法的旅行商问题复杂度研究[D];大连理工大学;2016年

8 徐东镇;蚁群算法及其在广义旅行商问题求解中的应用[D];合肥工业大学;2007年

9 黄厚生;求解旅行商问题的新方法研究[D];天津大学;2005年

10 王玲丽;随机存储下的有容量限制的广义旅行商问题[D];上海交通大学;2012年

，

本文编号：2451142