Abstract
The 0-1 multidimensional knapsack problem (0-1 MKP) is the problem of finding a subset of items that yields maximum profit under several knapsack constraints. It belongs to the class of NP-hard problems. When the dimension increases, the computing time needed for exact methods increase rapidly. However, problems of high dimensionality often arise in the modeling of real-world applications, so we need to develop computationally efficient methods for approaching the optimums of them. Genetic algorithms (GAs) are intelligent and probabilistic search algorithm established upon the principles of natural evolution. They have been shown to be able to find good and fast solutions for hard optimization problems.In this study, we propose a hybrid GA for the large-scale 0-1 MKP. Unlike the past GAs for the 0-1 MKP, we fix a large portion of variables to be 0 or 1 before applying GAs. Then we design a GA for solving the reduced 0-1 MKP (with less variables). The proposed GA is made up of several hybrid operators which are used to make the search more flexible and intelligent. Computational study is conducted on the medium-scale problem sets taken from literature. We also test the proposed GA on several sets of randomly generated large-scale problems (with up to 10000 variables and 1000 constraints). Computational results show that: (1) The proposed GA is superior to all the GAs so-far designed for the 0-1 MKP. (2) The GAs proposed by Chu and Raidl respectively can also be improved significantly in solution quality and computing time if the proposed variable reduction procedure is incorporated into their algorithms. (3) The proposed GA also outperforms Chu and Raidl GAs in which the proposed variable reduction procedure is incorporated.