摘要: 应用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
中图分类号:
王会颖, 倪志伟, 吴昊. 求解多维背包问题的MapReduce蚁群优化算法[J]. 计算机工程, 2013, 39(4): 248-253.
WANG Hui-Ying, NI Zhi-Wei, TUN Hao. MapReduce-based Ant Colony Optimization Algorithm for Multi-dimensional Knapsack Problem[J]. Computer Engineering, 2013, 39(4): 248-253.