MapReduce-Based Ant Colony Optimization Algorithm for Multi-Dimensional Knapsack Problem
Authors:
- 30 August 2013
- journal article
- Published by Trans Tech Publications, Ltd. in Applied Mechanics and Materials
- Vol. 380-384, 1877-1880
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.Keywords
This publication has 5 references indexed in Scilit:
- Scatter Search for the 0–1 Multidimensional Knapsack ProblemJournal of Mathematical Modelling and Algorithms, 2008
- The multidimensional 0–1 knapsack problem: An overviewEuropean Journal of Operational Research, 2004
- A new version of ant system for subset problems2003
- The Google file system2003
- A Genetic Algorithm for the Multidimensional Knapsack ProblemJournal of Heuristics, 1998