组合优化问题的目标是在给定约束条件下从可行解集中找到最优解。在求解组合优化问题的众多算法中,蚁群算法是应用最为广泛的一种算法,但由于它是一种基于概率的群体搜索算法,因此存在着两个致命的弱点:一是搜索容易停滞不前而陷入局部最优;二是在处理大规模数据时耗时巨大,针对这些问题,人们提出了多种改进方法,但是大多数方案很难在这两方面取得平衡,因此急需一种既能提高搜索质量又能快速求解的优化算法。本文在蚂蚁系统算法(ACS)的基础上引入一系列改进措施,同时依据可行解构建过程中存在的天然并行性和Spark分布式框架的计算特点,提出了基于Spark的改进蚁群算法。本文主要在以下几个方面展开了研究:(1)传统蚁群算法及其改进算法容易陷入局部最优,存在着求解质量不高的缺陷。在中等及以上规模的旅行商问题中,求解速度也不尽人意。为改进上述问题,本文提出了添加带有加速功能的局部搜索技术,同时采用了蚂蚁数量动态增加的策略。改进算法不仅提高了发现最优解的能力,也在一定程度上降低了因算法复杂性的增加而造成的时间成本急剧增大的影响,相对节约了运行时间。(2)Spark是一个新兴的基于内存运算的并行计算框架。它允许数据加载至集群内存,并对其进行多次查询,极其适用于机器学习和算法研究。正是由于蚁群算法的天然并行性和Spark在并行计算方面的巨大优势,论文将两者相结合后既能发挥蚁群算法在求解TSP问题时的全局寻优能力,又能通过改进措施提高局部搜索质量,同时基于Spark集群大幅度加快搜索速度,从而更好的解决类似TSP问题的组合优化问题。仿真结果表明,改进后的新算法在求解质量上有了明显的提升。在面对较大规模的TSP问题时,不仅具有更强的能力发现最优解,同时得益于Spark集群的并行计算能力,运行时间相比以往算法有了极大减少。在保证求解质量提高的同时,新算法有效提高了计算速度,做到了整体性能的大幅度提高。