MapReduce-Based Ant Colony Optimization Algorithm for Multi-Dimensional Knapsack Problem

Rui Tao Liu; Xiu Jian Lv

doi:10.4028/www.scientific.net/AMM.380-384.1877

Paper Titles

A Novel Relational Database Data Mining Method Based on Artificial Neural Network
p.1860

Research on Aircraft Sortie Generation Rate Using Multi-Class Closed Queueing Network
p.1864

3D Reconstruction and Analysis Base on Shape Matching
p.1868

Research on Feasibility Evaluation of Helicopter Route Based on GIS and Analytic Hierarchy Process
p.1873

MapReduce-Based Ant Colony Optimization Algorithm for Multi-Dimensional Knapsack Problem
p.1877

Research on Real-Time Network Forensics Based on Improved Data Mining Algorithm
p.1881

Research on Learning Beliefs and Strategies of Freshmen's Vocabulary Based on Regression Analysis and Mathematical Statistics
p.1886

Empirical Analysis of the Demand for Interpretation System of World Cultural Heritage Based on Optimized Selection Model and Mathematical Physics Equations
p.1891

A Verifiable Ring Signature Scheme Based on Multivariate Public-Key Cryptosystem
p.1899

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 380-384MapReduce-Based Ant Colony Optimization Algorithm...

MapReduce-Based Ant Colony Optimization Algorithm for Multi-Dimensional Knapsack Problem

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.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 380-384)

Pages:

1877-1880

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.380-384.1877

Citation:

Cite this paper

Online since:

August 2013

Authors:

Rui Tao Liu, Xiu Jian Lv

Keywords:

Ant Colony Optimization Algorithm (ACOA), Cloud Computing, Genetic Algorithm (GA), MapReduce Programming Model, Multi-Dimensional Knapsack Problem (MKP), Swarm Intelligence

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Chu P, Beasley J. A Genetic Algorithm for the Multidimensional Knapsack Problem[J]. Journal of Heuristics, 1998, 4(1): 63-86.

Google Scholar

[2] Freville A. The Multidimensional 0-1 Knapsack Problem: An Overview[J]. European Journal of Operational Research, 2004, 155(1): 1-21.

Google Scholar

[3] Hanafi S, Wilbaut C. Scatter Search for the 0-1 Multidimensional Knapsack Problem[J]. Journal of Mathematical Modeling and Algorithms, 2008, 7(2): 143-159.

DOI: 10.1007/s10852-008-9078-9

Google Scholar

[4] Leguizamon C, Michalewicz Z. A New Version of Ant System for Subset Problems[C]/Proc. of Congress on Evolutionary Computation. Piscataway, USA: [s. n. ], 1999: 1459-1464.

DOI: 10.1109/cec.1999.782655

Google Scholar

[5] Ghemawat S, Gobioff H, Leung S T. The Google FileSystem[C]/Proc. of the 19th ACM Symposium on Operating Systems Principles. New York, USA: ACM Press, 2003: 29-43.

DOI: 10.1145/945445.945450

Google Scholar

[6] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters[C]/Proc. of the 6th Symposium on Operating System Design and Implementation. Berkeley, USA: USENIX Association, 2004: 137-150.

Google Scholar