A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational results show that the RWCEA performs better than a weight-coded evolutionary algorithm pro-posed by Raidl (1999) and to some existing benchmarks, it can yield better results than the ones reported in the OR-library.
KeywordsWeight-CodingEvolutionary AlgorithmMultidimensional Knapsack Problem (MKP)
Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York.
Markowitz, H.M. and Manne, A.S. (1957) On the Solution of Discrete Programming Problems. Econometrica, 25, 84-110. http://dx.doi.org/10.2307/1907744
Gavish, B. and Pirkul, H. (1982) Allocation of Databases and Processors in a Distributed Computing System. In: Akoka, J., Ed., Management of Distributed Data Processing, North-Holland, 31, 215-231.
Shih, W. (1979) A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem. Journal of the Operational Research Society, 30, 369-378. http://dx.doi.org/10.1057/jors.1979.78
Gilmore, P.C. and Gomory, R.E. (1966) The Theory and Computation of Knapsack Func-tions. Operations Research, 14, 1045-1075. http://dx.doi.org/10.1287/opre.14.6.1045
Chu, P.C. and Beasley, J.E. (1998) A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4, 63-86. http://dx.doi.org/10.1023/A:1009642405419
Fréville, A. (2004) The Multidimensional 0-1 Knapsack Problem: An Overview. European Journal of Operational Research, 155, 1-21. http://dx.doi.org/10.1016/S0377-2217(03)00274-1
Kellerer, H., Pferschy, U. and Pisinger, D. (2004) Knapsack Problems. Springer, Berlin. http://dx.doi.org/10.1007/978-3-540-24777-7
Li, H., Jiao, Y., Zhang, L. and Gu, Z. (2006) Genetic Algorithm Based on the Orthogonal Design for Multidimensional Knapsack Problems. Advances in Natural Computation. Springer Berlin/Heidelberg, 696-705.
Kong, M., Tian, P. and Kao, Y. (2008) A New Ant Colony Optimization Algorithm for the Multidimensional Knapsack Problem. Computers & Operations Research, 35, 2672-2683. http://dx.doi.org/10.1016/j.cor.2006.12.029
Hanafi, S. and Wilbaut, C. (2008) Scatter Search for the 0-1 Multidimensional Knapsack Problem. Journal of Mathematical Modelling and Algorithms, 7, 143-159. http://dx.doi.org/10.1007/s10852-008-9078-9
Boyer, V., Elkihel, M. and El Baz, D. (2009) Heuristics for the 0-1 Multidimensional Knapsack Problem. European Journal of Operational Research, 199, 658-664. http://dx.doi.org/10.1016/j.ejor.2007.06.068
Fleszar, K. and Hindi, K.S. (2009) Fast, Effective Heuristics for the 0-1 Multi-Dimensional Knapsack Problem. Computers & Operations Research, 36, 1602-1607. http://dx.doi.org/10.1016/j.cor.2008.03.003
Puchinger, J., Raidl, G.R. and Gruber, M. (2005) Cooperating Memetic and Branch-and-Cut Algorithms for Solving the Multidimensional Knapsack Problem. Proceeding of the 6th Metaheuristics International Conference, Vienna, 22-26 August 2005, 775-780.
Zou, D., Gao, L., Li, S., et al. (2011) Solving 0-1 Knapsack Problem by a Novel Global Harmony Search Algorithm. Applied Soft Computing, 11, 1556-1564. http://dx.doi.org/10.1016/j.asoc.2010.07.019
Fréville, A. and Hanafi, S. (2005) The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects. Annals of Operations Research, 139, 195-227. http://dx.doi.org/10.1007/s10479-005-3448-8
Raidl, G.R. and Gottlieb, J. (2005) Empirical Analysis of Locality, Heritability and Heuristic bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem. Evolutionary Computation, 13, 441-475. http://dx.doi.org/10.1162/106365605774666886
Changdar, C., Mahapatra, G.S. and Pal, R.K. (2013) An Ant Colony Optimization Approach for Binary Knapsack Problem under Fuzziness. Applied Mathematics and Computation, 223, 243-253. http://dx.doi.org/10.1016/j.amc.2013.07.077
Hifi, M., M’Halla, H. and Sadfi, S. (2005) An Exact Algorithm for the Knapsack Sharing Problem. Computers & Operations Research, 32, 1311-1324. http://dx.doi.org/10.1016/j.cor.2003.11.005
Mavrotas, G., Figueira, J.R. and Florios, K. (2009) Solving the Bi-Objective Multi-Dimen-sional Knapsack Problem Exploiting the Concept of Core. Applied Mathematics and Computation, 7, 2502-2514. http://dx.doi.org/10.1016/j.amc.2009.08.045
Yuan, Q., Qian, F. and Du, W. (2010) A Hybrid Genetic Algorithm with the Baldwin Effect. Information Sciences, 180, 640-652. http://dx.doi.org/10.1016/j.ins.2009.11.015
Yuan, Q., He, Z. and Leng, H. (2008) A Hybrid Genetic Algorithm for a Class of Global Optimization Problems with Box Constraints. Applied Mathematics and Computation, 197, 924-929. http://dx.doi.org/10.1016/j.amc.2007.08.081
Yuan, Q. and Qian, F. (2010) A Hybrid Genetic Algorithm for Twice Continuously Differentiable NLP Problems. Computers & Chemical Engineering, 34, 36-41. http://dx.doi.org/10.1016/j.compchemeng.2009.09.006
Yuan, Q., He, Z. and Leng, H. (2008) An Evolution Strategy Method for Computing Eigenvalue Bounds of Interval Matrices. Applied Mathematics and Computation, 196, 257-265. http://dx.doi.org/10.1016/j.amc.2007.05.051
Yuan, Q. and Yang, Z. (2013) On the Performance of a Hybrid Genetic Algorithm in Dynamic Environments. Applied Mathematics and Computation, 219, 11408-11413. http://dx.doi.org/10.1016/j.amc.2013.06.006
Vasquez, M. and Hao, J.-K. (2001) A Hybrid Approach for the 0-1 Multidimensional Knapsack Problem. Proceeding of the 17th International Joint Conference on Artificial Intelligence, Seattle, 4-10 August 2001, 328-333.
Vasquez, M. and Vimont, Y. (2005) Improved Results on the 0-1 Multidimensional Knapsack Problem. European Journal of Operational Research, 165, 70-81. http://dx.doi.org/10.1016/j.ejor.2004.01.024
Vimont, Y., Boussier, S. and Vasquez, M. (2008) Reduced Costs Propagation in an Efficient Implicit Enumeration for the 0-1 Multidimensional Knapsack Problem. Journal of Combinatorial Optimization, 15, 165-178. http://dx.doi.org/10.1007/s10878-007-9074-4
Hanafi, S. and Wilbaut, C. (2011) Improved Convergent Heuristic for the 0-1 Multidimensional Knapsack Problem. Annals of Operations Research, 183, 125-142. http://dx.doi.org/10.1007/s10479-009-0546-z
Boussier, S., Vasquez, M., Vimont, Y., Hanafi, S. and Michelon, P. (2010) A Multi-Level Search Strategy for the 0-1 Multidimensional Knapsack Problem. Discrete Applied Mathematics, 158, 97-109. http://dx.doi.org/10.1016/j.dam.2009.08.007
Raidl, G.R. (1999) Weight-Codings in a Genetic Algorithm for the Multiconstraint Knapsack Problem. Proceedings of the 1999 Congress on Evolutionary Computation, Washington DC, 6-9 July 1999, 596-603. http://dx.doi.org/10.1109/CEC.1999.781987
Palmer, C.C. and Kershenbaum, A. (1994) Representing Trees in Genetic Algorithms. Proceeding of the 1st IEEE International Conference of Evolutionary Computation, Orlando, 27-29 June 1994, 379-384. http://dx.doi.org/10.1109/icec.1994.349921
Capp, K. and Julstrom, B. (1998) A Weight-Coded Genetic Algorithm for the Minimum Weight Triangulation Problem. Proceeding of 1998 ACM Symposium on Applied Computing, Atlanta, 27 February-1 March 1998, 327-331. http://dx.doi.org/10.1145/330560.330833
Julstrom, B. (1998) Comparing Decoding Algorithms in a Weight-Coded GA for TSP. Proceeding of 1998 ACM Symposium on Applied Computing, Atlanta, 27 February-1 March 1998, 313-317. http://dx.doi.org/10.1145/330560.330830
Raidl, G.R. (1999) A Weight-Coded Genetic Algorithm for the Multiple Container Packing Problem. Proceeding of the 14th ACM Symposium on Applied Computing, San Antonio, 28 February-2 March 1999, 291-296. http://dx.doi.org/10.1145/298151.298354
Glover, F. (1975) Surrogate Constraint Duality in Mathematical Programming. Operations Reserach, 23, 434-451. http://dx.doi.org/10.1287/opre.23.3.434
Hanafi, S. and Féville, A. (1998) An Efficient Tabu Search Approach for the 0-1 Multidimensional Kanpsack Problem. European Journal of Operational Research, 106, 659-675. http://dx.doi.org/10.1016/S0377-2217(97)00296-8
Gavish, B. and Pirkul, H. (1985) Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality. Mathematical Programming, 31, 78-105. http://dx.doi.org/10.1007/BF02591863
Rothlauf, F. and Goldberg, D.E. (2003) Redundant Representation in Evolutionary Computation. Evolutionary Computation, 11, 381-415. http://dx.doi.org/10.1162/106365603322519288
Hinterding, R. (1999) Representation, Constraint Satisfaction and the Knapsack Problem. Proceedings of the 1999 Congress on Evolutionary Computation, Washington DC, 6-9 July 1999, 1286-1292. http://dx.doi.org/10.1109/CEC.1999.782591