作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (4): 248-253. doi: 10.3969/j.issn.1000-3428.2013.04.057

• 人工智能及识别技术 • 上一篇    下一篇

求解多维背包问题的MapReduce蚁群优化算法

王会颖1,2,3,倪志伟1,2,吴 昊1,2   

  1. (1. 合肥工业大学管理学院,合肥 230009;2. 教育部过程优化与智能决策重点实验室,合肥 230009;3. 安徽财贸职业学院电子信息系,合肥 230601)
  • 收稿日期:2012-03-27 出版日期:2013-04-15 发布日期:2013-04-12
  • 作者简介:王会颖(1969-),女,讲师、博士研究生,主研方向:智能软件,群体智能;倪志伟,教授、博士、博士生导师;吴 昊,博士研究生
  • 基金资助:
    国家自然科学基金资助项目(71271071);国家“863”计划基金资助项目(2011AA040501);国家社会科学基金资助项目(10CGL024);安徽省教育厅自然科学基金资助项目(KJ2011A006, KJ2013B010);合肥学院科研发展基金资助重点项目(12KY03ZD)

MapReduce-based Ant Colony Optimization Algorithm for Multi-dimensional Knapsack Problem

WANG Hui-ying   1,2,3, NI Zhi-wei   1,2, WU Hao    1,2   

  1. (1. School of Management, Hefei University of Technology, Hefei 230009, 2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China; 3. Department of Electronics Information, Anhui Finance & Trade Vocational College, Hefei 230601, China)
  • Received:2012-03-27 Online:2013-04-15 Published:2013-04-12

摘要: 应用MapReduce编程模式实现蚁群优化算法的并行化计算,提出基于MapReduce的改进背包问题蚁群算法。通过改进概率计算时机、轮盘赌、交叉、变异等技术,降低蚁群算法的计算复杂度。在云计算环境中应用该算法分布式并行地求解大规模多维背包问题,仿真实验结果表明,该算法能改善蚁群算法搜索时间长的缺陷,增强对大规模问题的处理能力。

关键词: 云计算, MapReduce编程模式, 蚁群优化算法, 多维背包问题, 遗传算法, 群体智能

Abstract: This paper uses MapReduce parallel programming mode to make the Ant Colony Optimization(ACO) algorithm parallel and bring forward the MapReduce-based improved ACO for Multi-dimensional Knapsack Problem(MKP). A variety of techniques, such as change the probability calculation of the timing, roulette, crossover and mutation, are applied for improving the drawback of the ACO and complexity of the algorithm is greatly reduced. It is applied to distributed parallel as to solve the large-scale MKP in cloud computing. Simulation experimental results show that the algorithm can improve the defects of long search time for ant colony algorithm and the processing power for large-scale problems.

Key words: cloud computing, MapReduce programming mode, Ant Colony Optimization(ACO) algorithm, Multi-dimensional Knapsack Problem(MKP), Genetic Algorithm(GA), swarm intelligence

中图分类号: