Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (10): 2777-2780.DOI: 10.11772/j.issn.1001-9081.2015.10.2777

Previous Articles     Next Articles

Ant colony optimization algorithm based on Spark

WANG Zhaoyuan1,2, WANG Hongjie1,2, XING Huanlai1, LI Tianrui1,2   

  1. 1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu Sichuan 611756, China;
    2. Key Laboratory Cloud Computing and Intelligent Technology of Sichuan Province, Chengdu Sichuan 611756, China
  • Received:2015-06-15 Revised:2015-07-01 Online:2015-10-10 Published:2015-10-14

基于Spark的蚁群优化算法

王诏远1,2, 王宏杰1,2, 邢焕来1, 李天瑞1,2   

  1. 1. 西南交通大学 信息科学与技术学院, 成都 611756;
    2. 四川省云计算与智能技术高校重点实验室, 成都 611756
  • 通讯作者: 邢焕来(1983-),男,河北唐山人,副教授,博士,CCF会员,主要研究方向:进化计算、网络编码、软件定义网络,hxx@home.swjtu.edu.cn
  • 作者简介:王诏远(1989-),男,山西吕梁人,硕士研究生,CCF会员,主要研究方向:进化算法、云计算;王宏杰(1991-),男,河北唐山人,硕士研究生,CCF会员,主要研究方向:数据挖掘、云计算;李天瑞(1969-),男,福建莆田人,教授,博士生导师,博士,CCF会员,主要研究方向:智能信息处理、数据挖掘、云计算。
  • 基金资助:
    国家自然科学基金资助项目(61175047,61401374);中央高校基本科研业务费专项资金资助项目(2682014RC23);教育部留学回国人员科研启动基金资助项目;四川省苗子工程(2015045);西南交通大学"竢实之星"培养计划。

Abstract: To deal with the combinatorial optimization problem in the era of big data, a parallel Ant Colony Optimization (ACO) algorithm based on Spark, a framework for the distributed memory computing, was presented. To achieve the parallelization of the phase of solution construction in ant colony optimization, a class of ants was encapsulated to a resilient distributed dataset and the corresponding transformation operators were given. The simulation results in solving the Traveling Salesman Problem (TSP) prove the feasibility of the proposed parallel algorithm. Under the same experimental environment, the comparison results between MapReduce based ant colony algorithm and the proposed algorithm show that the proposed algorithm significantly improves the optimization speed at least ten times than the MapReduce one.

Key words: Ant Colony Optimization (ACO) algorithm, paralleling, Spark, Hadoop, cloud computing

摘要: 为应对大数据时代中组合优化问题的求解,基于云计算框架Spark,借助其基于内存、分布式的特定,提出一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集,由此给出相应的一系列转换算子,实现了蚂蚁构造解过程的并行化。通过在旅行商问题(TSP)求解的仿真实验结果说明了所提出的并行算法的可行性;并在同等实验环境下对比基于MapReduce的蚁群优化算法,优化速度提升达10倍以上。

关键词: 蚁群优化算法, 并行, Spark, Hadoop, 云计算

CLC Number: