基于MapReduce的遗传算法在组合优化问题中的研究

发布时间：2017-08-08 15:26

  本文关键词：基于MapReduce的遗传算法在组合优化问题中的研究

  更多相关文章： 组合优化 遗传算法 分布式 MapReduce

【摘要】：在现实社会中,很多生产和生活问题都可以建模为组合优化问题,特别是随着“互联网+”时代的到来,科学技术水平得以飞速发展,数据信息呈爆炸式的增长,越来越多的新型组合优化问题得以涌现。研究如何能更好的解决组合优化问题将为人们的生产生活带来巨大的收益。本文采用了遗传算法来求解组合优化问题,但是传统单机遗传算法在解决组合优化问题上存在稳定性差,多次实验需要消耗大量时间等缺点,本文实现了基于MapReduce分布式计算框架下的并行遗传算法。使每个种群在相应节点上并发执行,最后通过适应度评比选出最优个体。本文主要做了如下的工作：(1)将传统的遗传算法进行了优化,在种群初始化中加入了贪心策略,在选择策略上采用了轮盘赌与最佳个体保留的策略,并对交叉算子和变异算子进行了参数分析实验,采用了启发式交叉算子和自适应变异算子相结合的方法。(2)将优化后的遗传算法移植到了MapReduce分布式计算框架上,同时对MapReduce分布式计算框架进行了参数优化,进一步提高了整个框架的计算性能。最终将程序部署在Hadoop平台上运行,以旅行商问题作为实验对象,采用TSPLIB库提供的数据作为实验数据,实验结果表明,当实验次数大于10次时,相比于传统单机遗传算法,程序运行时间减少了近56.4%,寻解能力明显增强。同时,因为分布式并行遗传算法具有一次运行多次实验的特点,从而在一定程度上克服了遗传算法稳定性差的缺点。
【关键词】：组合优化 遗传算法 分布式 MapReduce
【学位授予单位】：内蒙古农业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157;TP18
【目录】：

• 摘要3-4
• Abstract4-10
• 1 引言10-15
• 1.1 研究背景及意义10-11
• 1.1.1 研究背景10
• 1.1.2 研究意义10-11
• 1.2 国内外研究现状11-13
• 1.2.1 国内研究现状12
• 1.2.2 国外研究现状12-13
• 1.3 论文研究内容13-14
• 1.4 论文组织结构14-15
• 2 基本理论和相关技术15-26
• 2.1 TSP问题概述15
• 2.2 遗传算法15-18
• 2.2.1 遗传算法概述15-17
• 2.2.2 遗传算法基本原理17-18
• 2.3 分布式计算技术18-20
• 2.4 开源分布式行计算平台Hadoop20-23
• 2.4.1 Hadoop平台的基本架构20-21
• 2.4.2 分布式文件系统HDFS21
• 2.4.3 分布式计算框架MapReduce21-23
• 2.5 其它分布式计算平台23-24
• 2.6 本章小结24-26
• 3 基于遗传算法求解TSP问题的方法及优化26-44
• 3.1 编码方式和种群初始化26-28
• 3.1.1 种群初始化的优化27-28
• 3.2 评价函数设定28
• 3.3 选择策略28-31
• 3.3.1 选择策略的优化30-31
• 3.4 交叉操作31-36
• 3.4.1 交叉算子参数分析33-35
• 3.4.2 交叉算子优化35-36
• 3.5 变异操作36-40
• 3.5.1 变异算子参数分析38-40
• 3.5.2 变异算子优化40
• 3.6 求解TSP问题的仿真实验40-43
• 3.7 本章小结43-44
• 4 基于MapReduce的遗传算法及TSP实验分析44-57
• 4.1 算法描述44-47
• 4.2 Map端设计47-48
• 4.3 Reduce端设计48-49
• 4.4 Hadoop实验平台搭建49-51
• 4.4.1 集群配置49-51
• 4.4.2 Hadoop平台结合Eclipse的搭建51
• 4.5 MapReduce参数优化51-52
• 4.6 实验结果与分析52-56
• 4.7 本章小结56-57
• 5 总结与展望57-60
• 5.1 总结57-58
• 5.2 展望58-60
• 致谢60-61
• 参考文献61-64
• 作者简介64

【相似文献】

中国期刊全文数据库 前10条

1 陈琨;张志明;;一种改进遗传算法的设计与实现[J];贵州大学学报(自然科学版);2006年01期

2 胡兰萍;黄海斌;;遗传算法及其在化学领域中的应用[J];海南师范学院学报(自然科学版);2006年03期

3 王珊珊;;遗传算法的理论基础及应用[J];科协论坛(下半月);2008年09期

4 高翔;海洋;;遗传算法应用[J];赤峰学院学报(自然科学版);2009年03期

5 刘定理;;遗传算法综述[J];中国西部科技;2009年25期

6 欧阳柏平;;基于遗传算法优化独立分量分析[J];科技信息;2010年07期

7 储育青;齐义飞;肖立顺;陈晖敏;石玉文;;遗传算法研究概述[J];科技风;2010年09期

8 曾瑛;;遗传算法在优化求解中的应用[J];科技创业月刊;2012年10期

9 丁承民,张传生,刘辉;遗传算法纵横谈[J];信息与控制;1997年01期

10 施光林,史维祥;遗传算法及其研究与应用新进展[J];科技导报;1997年04期

中国重要会议论文全文数据库 前10条

1 陈家照;廖海涛;张中位;罗寅生;;一种改进的遗传算法及其在路径规划中的应用[A];2009系统仿真技术及其应用学术会议论文集[C];2009年

2 李国云;刘颖;薛梅;邬志敏;;遗传算法在高温空冷冷凝器优化设计中的应用[A];第五届全国制冷空调新技术研讨会论文集[C];2008年

3 王志军;李守春;张爽;;改进的遗传算法在反演问题中的应用[A];新世纪 新机遇 新挑战——知识创新和高新技术产业发展（上册）[C];2001年

4 任燕翔;姜立;刘连民;从滋庆;;改进遗传算法在三维日照方案优化中的应用[A];工程三维模型与虚拟现实表现——第二届工程建设计算机应用创新论坛论文集[C];2009年

5 韩娟;;遗传算法概述[A];第三届河南省汽车工程科技学术研讨会论文集[C];2006年

6 庞国仲;王元西;;基于遗传算法控制步长的定性仿真方法[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

7 张忠华;杨淑莹;;基于遗传算法的聚类设计[A];全国第二届信号处理与应用学术会议专刊[C];2008年

8 何翠红;区益善;;遗传算法及其在计算机编程中的应用[A];1995年中国智能自动化学术会议暨智能自动化专业委员会成立大会论文集（下册）[C];1995年

9 靳开岩;张乃尧;;几种实用遗传算法及其比较[A];1996年中国智能自动化学术会议论文集（下册）[C];1996年

10 王宏刚;曾建潮;李志宏;;摄动遗传算法[A];1996年中国智能自动化学术会议论文集（下册）[C];1996年

中国重要报纸全文数据库 前1条

1 林京;《神经网络和遗传算法在水科学领域的应用》将面市[N];中国水利报;2002年

中国博士学位论文全文数据库 前10条

1 蔡美菊;交互式遗传算法及其在隐性目标决策问题中的应用研究[D];合肥工业大学;2015年

2 张士伟;三维声学快速多极基本解法在机械噪声预测中的应用研究[D];沈阳工业大学;2016年

3 高军;无铅焊料本构模型及其参数识别方法研究[D];南京航空航天大学;2015年

4 Amjad Mahmood;半监督进化集成及其在网络视频分类中的应用[D];西南交通大学;2015年

5 周辉仁;递阶遗传算法理论及其应用研究[D];天津大学;2008年

6 郝国生;交互式遗传算法中用户的认知规律及其应用[D];中国矿业大学;2009年

7 侯格贤;遗传算法及其在跟踪系统中的应用研究[D];西安电子科技大学;1998年

8 马国田;遗传算法及其在电磁工程中的应用[D];西安电子科技大学;1998年

9 唐文艳;结构优化中的遗传算法研究和应用[D];大连理工大学;2002年

10 周激流;遗传算法理论及其在水问题中应用的研究[D];四川大学;2000年

中国硕士学位论文全文数据库 前10条

1 张英俐;基于遗传算法的作曲系统研究[D];山东师范大学;2006年

2 钟海萍;原对偶遗传算法与蚁群算法的一种融合算法[D];暨南大学;2013年

3 彭骞;基于遗传算法的山区高等级公路纵断面智能优化方法研究[D];昆明理工大学;2015年

4 周玉林;基于小波分析和遗传算法的配电网故障检测[D];昆明理工大学;2015年

5 郭颂;基于粗糙集和遗传算法的数字管道生产管理系统研究[D];昆明理工大学;2015年

6 吴南;数值逼近遗传算法的研究应用[D];华南理工大学;2015年

7 于光帅;一类优化算法的改进研究与应用[D];渤海大学;2015年

8 吴欣欣;改进GA-TS算法优化的BP神经网络入侵检测研究[D];湖南工业大学;2015年

9 王垒;基于遗传算法的A型单喇叭互通立交线形优化[D];长安大学;2015年

10 龚高;基于遗传算法的桥梁结构传感器优化布置研究[D];长安大学;2015年

，

本文编号：640697