Abstract
This work addresses the application of a population based evolutionary algorithm called shuffled complex evolution (SCE) in the multidimensional knapsack problem. The SCE regards a natural evolution happening simultaneously in independent communities. The performance of the SCE algorithm is verified through computational experiments using well-known problems from literature and randomly generated problem as well. The SCE proved to be very effective in finding good solutions demanding a very small amount of processing time.
Research supported by Fundação de Amparo à Pesquisa do Espírito Santo.
Chapter PDF
Similar content being viewed by others
References
Achterberg, T.: Scip: Solving constraint integer programs. Mathematical Programming Computation 1(1), 1–41 (2009). http://mpc.zib.de/index.php/MPC/article/view/4
Chu, P.C., Beasley, J.E.: A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics 4(1), 63–86 (1998). http://dx.doi.org/10.1023/A:1009642405419
Duan, Q., Sorooshian, S., Gupta, V.: Effective and efficient global optimization for conceptual rainfall-runoff models. Water Resources Research 28(4), 1015–1031 (1992)
Elbeltagi, E., Hegazy, T., Grierson, D.: A modified shuffled frog-leaping optimization algorithm: applications to project management. Structure and Infrastructure Engineering 3(1), 53–60 (2007)
Freville, A., Plateau, G.: An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem. Discrete Applied Mathematics 49(1), 189–212 (1994)
Gavish, B., Pirkul, H.: Allocation of data bases and processors in a distributed computing system (1982)
Gilmore, P.C., Gomory, R.E.: The Theory and Computation of Knapsack Functions. Operations Research 14, 1045–1074 (1966)
McMillan, C., Plaine, D.: Resource allocation via 0–1 programming. Decision Sciences 4, 119–132 (1973)
Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33(1), 60–100 (1991)
Shih, W.: A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem. Journal of The Operational Research Society 30, 369–378 (1979)
Zhao, F., Zhang, J., Wang, J., Zhang, C.: A shuffled complex evolution algorithm with opposition-based learning for a permutation flow shop scheduling problem. International Journal of Computer Integrated Manufacturing (ahead-of-print), 1–16 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Baroni, M.D.V., Varejão, F.M. (2015). A Shuffled Complex Evolution Algorithm For the Multidimensional Knapsack Problem. In: Pardo, A., Kittler, J. (eds) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. CIARP 2015. Lecture Notes in Computer Science(), vol 9423. Springer, Cham. https://doi.org/10.1007/978-3-319-25751-8_92
Download citation
DOI: https://doi.org/10.1007/978-3-319-25751-8_92
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25750-1
Online ISBN: 978-3-319-25751-8
eBook Packages: Computer ScienceComputer Science (R0)