论文部分内容阅读
组合优化问题是指从组合问题的可行解中求出最优解,但是目前利用传统方式解决组合优化问题需要极大的存储空间和极长的运行时间,而在当今大数据时代,各行业每年产生的数据量都呈指数增长,Spark作为一种新型的并行计算模型应运而生,因此利用Spark并行计算模型解决“组合爆炸”问题是一种很可行的方案。在解决组合优化问题时,人们倾向于选择元启发式算法,例如蚁群算法就是受蚂蚁觅食行为的启发而提出的一种元启发式算法,它具有鲁棒性、分布式运行、易于和其它算法相融合等优点。目前该算法已经广泛应用于组合优化领域,并且取得了较好的成果,但它也存在易陷入局部最优解和收敛速度慢等问题。论文根据蚁群构建可行解过程的内在并行性及云计算平台分布式计算的特点,提出一种基于Spark的混沌蚁群优化算法,进而展开了以下几方面的研究：1.针对基本蚁群算法在处理大规模旅行商问题时易陷入局部最优解及收敛速度慢等问题,论文提出当蚂蚁选择路径时采用轮盘赌策略从候选城市中随机选择下一个城市,从而扩大蚁群搜索空间；然后引用混沌理论动态地调整信息素挥发系数,避免算法陷入局部最优解；再使用遗传变异算子对每一次迭代的路径结果进行变异操作,以期望得到路径最优解；最后将改进的蚁群算法使用MapReduce并行计算模型编程实现,并将其部署在Hadoop平台中运行,以大幅提高蚁群算法的运行速度。2.论文在对Spark平台充分研究的基础上,又将改进的蚁群算法使用Spark并行计算模型编程实现。首先把蚁群封装为弹性分布式数据集RDD,并将其初始化为大小规模均等的多个小种群；再使用Spark提供的广播机制在集群节点中共享信息素矩阵,并充分利用Spark基于内存计算的特点实现蚁群并行地构建可行解,从而更快地处理大规模组合优化问题。3.通过实验证明：对于特定规模大小的蚁群,增加集群节点数量并不能持续地提升蚁群算法的运行速度；论文选用TSPLIB库中不同的旅行商实例验证改进蚁群算法的性能。结果表明：随着蚁群规模的增大,基于MapReduce的混沌蚁群优化算法比基本蚁群算法的运行时间大幅缩短,而基于Spark的混沌蚁群优化算法比前两者算法的运行速度更快；此外,改进的蚁群算法相对于基本蚁群算法的路径寻优结果也得到了极大改善。