A Review and Comparison of Genetic Algorithms for the 0-1 Multidimensional Knapsack Problem

Introduction

Consider a situation with a multitude of projects i and resources j. Each project has an objective value c_i, for example, profit, and resource consumption values a_ij, for example, required machine minutes. Projects can either be carried out or not. A project’s selection is determined through the decision variable x_i. Because of a limited resource capacities b_j, not all projects can be carried out, and one has to find the subset of all projects that maximizes the overall profit. Such a non-deterministic polynomial-time-hard 0-1 multidimensional knapsack problem (MKP) can be expressed as followed (Kellerer et al., 2004):

The 0-1 MKP is one of the best known integer programming problem. Two general approaches on solving the 0-1 MKP have emerged during the past decades: exact methods and heuristics. Even though exact methods (cf. Martello et al., 1999, 2000) have made improvements, large problems with an increased number of constraints remain a challenge. Heuristics like greedy algorithms (cf. Senju & Toyoda, 1968), mathematical programming, (cf. Hillier, 1969), or metaheuristics such as tabu search (cf. Dammeyer & Voss, 1991; Hanafi & Freville, 1998), simulated annealing (cf. Drexl, 1988), or genetic algorithms are competitive alternatives, especially at such large problems (Fréville, 2004). In particular, genetic algorithms (GA) have been very well suited for solving these 0-1 MKPs (cf. Raidl, 1998, 1999) and are often applied for solving various types of general optimization problems (cf. Pal & Chakraborti, 2013) and knapsack problems (cf. Lin, 2008). Therefore, this article focuses on the performance of genetic algorithms.

Apart from general parameters such as the population size or the crossover rate, a GA’s effectiveness and efficiency are dependent on its design. Even though multiple individual GAs have been discussed in literature, a direct validation of the proposed algorithms’ efficiencies has only sparsely been performed by Raidl & Gottlieb (2005). Rather than objective evaluations of the GAs in homogenous conditions, single approaches are primarily analyzed in the context of a new GA’s exposure. Typically, the algorithms are contrasted to a very limited set of other alternative approaches (Hoff et al., 1996; Raidl, 1998; Gottlieb, 2000; Levenhagen et al., 2001). A combination of multiple such studies, however, is not possible due to diverging equipment characteristics, databases, and parameter settings. Consequently, one must be cautious to select the “best” GA (Chu & Beasley, 1998). For this purpose, we provide a systematic evaluation of 11 carefully chosen genetic algorithms using all 270 standard-problems by Chu & Beasley (1997, 1998) publicly available (Beasley, 1998). The selected GAs had to meet two selection criteria. First, GAs must be specifically designed for solving the 0-1 MKP. Second, GAs have to show significant progress compared with the previous algorithms. In other words, algorithms that only provide little benefit were not selected.

The addressees of our research are primarily practitioners requiring a suited algorithm for solving the 0-1 MKP but also scientists trying to further improve current best approaches. Consequently, the research question this article answers is: Which GA should be applied to solve the 0-1 MKP?