基于Spark的并行遗传算法及其在TSP问题中的应用

摘要

在互联网加速普及的今天，信息的传递越来越快，产生的数据也越来越大，所以很多问题会产生大量的数据。在现实生活中，这些具体的问题往往无法用数学模型很好地归纳，典型的问题就是NP问题中的旅行商问题。对于这些问题的解决，一般的方式是使用优化算法来得出近似解。 遗传算法(Genetic Algorithm,简称GA)是一种的经典的优化算法，在面对很多具体问题时，它具有数学建模简单，不需要问题的相关知识，对问题的适用性强的优势。但是遗传算法本身也有一些缺陷。遗传算法在单机环境下的搜索空间有限，无法在算法运行的后期有效地得到最优解，并且，随着迭代次数的增加，遗传算法的耗时也大大增加，很可能无法在可以接受的时间内得到最优解。并行化的遗传算法可以利用现在硬件多核平台的优势，使得很多问题的搜索空间进一步增大，对于复杂系统，尤其是会产生巨量数据的复杂系统，有很强的优化能力。因此，并行化的遗传算法，一直是遗传算法领域的重点研究对象。 本文提出一种基于仿细粒度的粗粒度并行遗传算法。算法通过引入细粒度模型的信息交流方法，改善了传统的粗粒度并行模型的不足，有效地解决了传统并行模型下的遗传算法所存在的早熟问题。为了进一步提升遗传算法的搜索能力，选择了遗传算法在进化过程中的比较适合并行化的进化策略，在进化的过程中，通过对于不同算子的对比，引入合适的遗传算子。同时，在对于遗传算法本身的并行性进行研究后，引入了种群、基因型双层并行的策略，在一般启发式算法所用到的种群并行的基础上，将基因再次分割后在弹性分布式数据集中并行。最后，利用Spark平台内存交互数据的优势，加速算法的运行。为了验证改进后遗传算法的性能，将改进算法应用于旅行商问题Berlin52数据集的求解，实验结果表明，与传统的并行模型相比，改进后的算法可以明显缩短计算时间，增大搜索范围，早熟现象也得到了改善。

目录

声明

第一章 绪论

1.1遗传算法的背景与发展

1.1.1遗传算法的起源

1.1.2遗传算法的发展过程

1.1.3 遗传算法的应用领域

1.1.4遗传算法所面临的问题

1.2 分布式的并行遗传算法

1.2.1 分布式计算和并行计算的演变发展

1.2.2 分布式并行遗传算法的研究意义和可行性

第二章 遗传算法的相关概念与技术

2.1 遗传算法流程

2.2 遗传算法的特点

2.3 遗传算法的原理

2.3.1遗传算法的数学原理

2.4 遗传算法进化阶段策略选择

2.4.1合适的编码策略

2.4.2遗传算子的选择

2.4.3参数的调整

第三章 遗传算法的并行化处理

3.1粗粒度并行模式

3.1.1 粗粒度并行的实现模式

3.1.2 粗粒度并行的性能分析

3.2细粒度并行模式

3.2.1 细粒度并行的实现模式

3.2.2细粒度并行模式的性能分析

3.3仿细粒度并行模式的设计

3.3.1收敛性分析

3.3.2加速比分析

第四章 并行遗传算法的分布式实现

4.1 分布式计算

4.2 分布式并行平台

4.3 spark简介与其他并行方案的比较

4.3.1 Spark

4.3.2 Spark的优势

4.3.3 Spark与其他平台对比

4.4 基于Spark的遗传算法的实现

4.4.1 RDD

4.4.2基于SFCPGA的TSP求解流程

第五章 并行遗传算法在TSP问题中的应用

5.1旅行商问题

5.1.1 旅行商问题的现状和瓶颈

5.1.2旅行商问题的应用

5.2实验数据和测试依据

5.3实验结果分析

5.3.1计算结果分析

5.3.2算法运行时间对比

5.3.3算法的收敛效率对比

第六章 结论与展望

参考文献

攻读学位期间所取得的相关科研成果

致谢