An Improved Genetic Algorithm for the
Multiconstrained 0–1 Knapsack Problem
G¨unther R. Raidl
Abstract— This paper presents an improved hybrid Ge-
netic Algorithm (GA) for solving the Multiconstrained 0–1
Knapsack Problem (MKP). Based on the solution of the
LP-relaxed MKP, an efficient pre-optimization of the initial
population is suggested. Furthermore, the GA uses sophis-
ticated repair and local improvement operators which are
applied to each newly generated solution. Care has been
taken to define these new operators in a way avoiding prob-
lems with the loss of population diversity. The new algo-
rithm has been empirically compared to other previous ap-
proaches by using a standard set of “large-sized” test data.
Results show that most of the time the new GA converges
much faster to better solutions, in particular for large prob-
lems.
Keywords— Multiconstrained 0–1 Knapsack Problem, hy-
brid Genetic Algorithm, pre-optimized initialization, local
improvement.
I. Introduction
T
HE Multiconstrained 0–1 Knapsack Problem (MKP) is
a well known NP-complete combinatorial optimization
problem which can be formulated as follows:
maximize f(x
1
, . . . , x
n
) =
n
X
j=1
p
j
x
j
, (1)
subject to C
i
:
n
X
j=1
w
i,j
x
j
≤ b
i
, (2)
i = 1, . . . , m,
x
j
∈ {0, 1}, j = 1, . . . , n
with p
j
> 0, r
i,j
≥ 0, b
i
≥ 0.
The objective function f(x
1
, . . . , x
n
) should be maxi-
mized while taking care of m constraints C
i
. Note that
only the values 0 and 1 may be assigned to the x
j
, making
the problem a 0–1 integer programming problem. The sig-
nificant difference to general 0–1 programming problems is
the fact that in case of the MKP all w
i,j
are positive. This
property allows for better heuristics to obtain near optimal
solutions.
The MKP has many applications in various fields, e.g.
economy: Consider a set of projects (j = 1, . . . , n) and a
set of resources (i = 1, . . . , m). Each project has assigned a
profit p
j
and resource consumption values w
i,j
. The prob-
lem is to find a subset of all projects leading to the highest
possible profit and not exceeding given resource limits b
i
.
Most of the research concerning Knapsack Problems
deals with the much simpler uni-dimensional Knapsack
Problem (KP) with only a single constraint (m = 1). For
G. R. Raidl is with the Institute for Computer Graphics, Vienna
University of Technology, Karlsplatz 13/1861, 1040 Vienna, Austria.
E-mail: raidl@eiunix.tuwien.ac.at
this case, the MKP is not strongly NP-hard [13], and ef-
ficient approximation algorithms have been developed for
obtaining near-optimal solutions, see e.g. [16]. For cases
where both m and n are large, the efficiency of existing ex-
act and heuristic optimization metho ds is limited concern-
ing execution time and quality of found solutions. Some
exact algorithms which are only applicable to very small
MKPs are presented e.g. by Gavish and Pirkul in [10].
Balas and Martin [1] introduced a heuristic algorithm
for the MKP which utilizes linear programming (LP) by re-
laxing the integrality constraints x
j
∈ {0, 1} to 0 ≤ x
j
≤ 1.
Linear programming problems are not NP-hard and can be
solved efficiently, e.g. with the well known Simplex algo-
rithm [6]. The fractional x
j
are then set to 0 or 1 according
to a heuristic which maintains feasibility. More examples of
heuristic algorithms for the MKP can be found in [15], [16],
[19], [23]. A comprehensive review on exact and heuristic
algorithms is given in [7], [8].
In the last few years, Genetic Algorithms (GAs) have
shown to be very well suited for solving larger Knapsack
Problems, see [12], [14], [18], [22], [20], [7], [8], and general
0–1 integer programming problems [21].
The next section gives a survey of these GAs. In section
3 a new hybrid GA is introduced which starts with an ini-
tial population of pre-optimized solutions determined by
a heuristic based on the LP-relaxed MKP. Furthermore,
this GA uses sophisticated repair and local improvement
operators which are applied to each newly generated so-
lution. Empirical results of the new GA and comparisons
with other algorithms using standard test problems follow
in section 4. Finally, some conclusions and remarks for
further works are given in section 5.
II. Prior GA-Based Work
The mentioned prior GAs for the MKP mainly differ in
the ways of encoding solutions. Basically, there are two
techniques, namely bit string and order based representa-
tion.
A. Bit String Representation
The values of all variables x
j
are directly stored in a bit
string of length n.
At a first glance, this representation seems to be the most
direct and easiest way, but infeasible solutions containing
constraint violations need to be considered. One way to do
this is the usage of penalty functions incorporated into the
objective function. This well known approach is generally
discussed in e.g. [11], [17]. Difficulties lie in the selection
of the penalty function and its coefficients to prevent pre-
mature convergence and infeasible final solutions. In [18],
资源评论
