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

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

作　　者：王会颖[1,2,3] 倪志伟[1,2] 吴昊[1,2] 

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]教育部过程优化与智能决策重点实验室,合肥230009 [3]安徽财贸职业学院电子信息系,合肥230601

出　　处：《计算机工程》2013年第4期248-253,共6页Computer Engineering

基　　金：国家自然科学基金资助项目(71271071);国家"863"计划基金资助项目(2011AA040501);国家社会科学基金资助项目(10CGL024);安徽省教育厅自然科学基金资助项目(KJ2011A006;KJ2013B010);合肥学院科研发展基金资助重点项目(12KY03ZD)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]