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

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

Bernhard Lienland (University of Regensburg, Regensburg, Germany) and Li Zeng (University of Regensburg, Regensburg, Germany)
DOI: 10.4018/ijoris.2015040102

Abstract

The 0-1 multidimensional knapsack problem (MKP) is a well-known combinatorial optimization problem with several real-life applications, for example, in project selection. Genetic algorithms (GA) are effective heuristics for solving the 0-1 MKP. Multiple individual GAs with specific characteristics have been proposed in literature. However, so far, these approaches have only been partially compared in multiple studies with unequal conditions. Therefore, to identify the “best” genetic algorithm, this article reviews and compares 11 existing GAs. The authors' tests provide detailed information on the GAs themselves as well as their performance. The authors validated fitness values and required computation times in varying problem types and environments. Results demonstrate the superiority of one GA.
Article Preview

Introduction

Consider a situation with a multitude of projects i and resources j. Each project has an objective value ci, for example, profit, and resource consumption values aij, for example, required machine minutes. Projects can either be carried out or not. A project’s selection is determined through the decision variable xi. Because of a limited resource capacities bj, 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):

(1)
(2)
(3)

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?

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing