1

A Novel Genetic Algorithm using Helper
Objectives for the 0-1 Knapsack Problem
Jun He, Feidun He and Hongbin Dong

arXiv:1404.0868v1 [] 3 Apr 2014

Abstract
The 0-1 knapsack problem is a well-known combinatorial optimisation problem. Approximation algorithms have been designed
for solving it and they return provably good solutions within polynomial time. On the other hand, genetic algorithms are well
suited for solving the knapsack problem and they find reasonably good solutions quickly. A naturally arising question is whether
genetic algorithms are able to find solutions as good as approximation algorithms do. This paper presents a novel multi-objective
optimisation genetic algorithm for solving the 0-1 knapsack problem. Experiment results show that the new algorithm outperforms
its rivals, the greedy algorithm, mixed strategy genetic algorithm, and greedy algorithm + mixed strategy genetic algorithm.
Index Terms
genetic algorithm, knapsack problem, multi-objective optimisation, solution quality

I. I NTRODUCTION
The 0-1 knapsack problem is one of the most important and also most intensively studied combinatorial optimisation problems
[1]. Several approximation algorithms have proposed for solving the 0-1 knapsack problem [1]. These algorithms always can
return provably good solutions, whose values are within a factor of the value of the optimal solution.
In last two decades, evolutionary algorithm, especially genetic algorithms (GAs), have been well adopted for tackling the
knapsack problem [2], [3]. The problem has received a particular interest from the evolutionary computation community for
the following reason. The binary vector representation is a natural encoding of of the candidate solutions to the 0-1 knapsack
problem. Thereby, it provides an ideal setting for the applications of GAs [4, Chapter 4].
Empirical results often assert that GAs produce reasonably good solutions to the knapsack problems [5], [6], [7]. A naturally
arising question is to compare the solution quality (reasonably good versus provably good) between GAs and approximation
algorithms. There are two approaches to answer the question. One approach is to make a theoretical analysis. A GA is proven
that it can produce a solution within a polynomial runtime, the value of which is within a factor of the value of an optimal
solution. This is a standard approach used in the study of approximation algorithms. Another approach is to conduct an empirical
study. A GA is compared with an approximation algorithm via computer experiments. If the GA can produce solutions better
or not worse than an approximative algorithm does in all instances within polynomial time, the GA is able to reach the same
solution quality as the approximation algorithm does.
The current paper is an empirical study of an GA which uses the multi-objectivization technique [8]. In multi-objectivization,
single-objective optimisation problems are transferred into multi-objective optimisation problems by decomposing the original
objective into several components [8] or by adding helper objectives [9]. Multi-objectivization may bring both positive and
negative effects [10], [11], [12]. This approach has been used for solving several combinatorial optimisation problems,
for example, the knapsack problem [13], vertex cover problem [14] and minimum label spanning tree problem [15]. This
paper focusses on the 0-1 knapsack problem. A novel GA using three helper objectives is designed for solving the 0-1
knapsack problem. Then the solution quality of the GA is compared with a well-known approximation algorithm via computer
experiments.
The remainder of the paper is organized as follows. The 0-1 knapsack problem, a greedy algorithm and a GA for it are
introduced in Section II. In Section III we present a novel GA using helper objectives. Section IV is devoted to an empirical
comparison among several algorithms. Section V concludes the article.
II. K NAPSACK P ROBLEM , G REEDY A LGORITHM

AND

G ENETIC A LGORITHM

In an instance of the 0-1 knapsack problem, given a set of n items with weights wi and profits pi , and a knapsack with
capacity C, the task is to maximise the sum of profits of items packed in the knapsack without exceeding the capacity. More
formally the target is to find a binary vector ~x = (x1 · · · xn ) so as to
max f (~x) =
~
x

n
X
i=1

pi xi ,

subject to

n
X

wi xi ≤ C,

i=1

This work was supported by the EPSRC under Grant No. EP/I009809/1.
Jun He is with Department of Computer Science, Aberystwyth University, Aberystwyth, SY23 3DB, UK (email: jun.he@aber.ac.uk).
Feidun He is with School of Information Science and Technology, Southwest Jiaotong University, Chengdu, China
Hongbin Dong is with College of Computer Science and Technology, Harbin Engineering University, Harbin, China

(1)

2

where xi = 1 if the item i is selected in the knapsack and xi = 0 if the item i is not selected in the knapsack. A feasible
solution is an ~x which satisfies the constraint. An infeasible one is an ~x that violates the constraint.
Several approximation algorithms have been proposed for solving the 0-1 knapsack problem (see [1, Chapter 2] for more
details). Among these, the simplest one is the greedy algorithm described below. The algorithm aims at putting the most
profitable items as many as possible into the knapsack or the items with the highest profit-to-weight ratio as many as possible,
within the knapsack capacity.
1: input an instance of the 0-1 knapsack problem;
p
p
2: resort all the items via the ratio of their profits to their corresponding weights so that w1 ≥ · · · ≥ wn ;
1
n
3: greedily add the items in the above order to the knapsack as long as adding an item to the knapsack does not exceeding
the capacity of the knapsack. Denote the solution by ~y ;
4: resort all the items according to their profits so that p1 ≥ p2 ≥ · · · ≥ pn ;
5: greedily add the items in the above order as long as adding an item to the knapsack does not exceeding the capacity of
the knapsack. Denote the solution by ~z;
6: output the best of ~
y and ~z.
This algorithm is a 1/2-approximation algorithm for the 0-1 knapsack problem [1, Section 2.4], which means it always can
return a solution no worse than 1/2 of the value of the optimal solution.
The greedy algorithm stops after finding an approximation solution, and it has no ability to seek the global optimal solution.
Therefore GAs are often applied for solving the 0-1 knapsack problem.
In order to handle the constraint in the knapsack problem, we use repair methods since they are claimed to be the most
efficient for the knapsack problem [4], [16]. A repair method is explained as follows.
1: input an infeasible solution ~
x;
2: while ~
x is infeasible do
3:
i =: choose an item from the knapsack;
4:
setP
xi = 0;
n
5:
if i=1 xi wi ≤ C then
6:
~x is feasible;
7:
end if
8: end while
9: output a feasible solution ~
x.
There are different methods available for choosing an item in the repair procedure, described as follows.
1) Profit-greedy repair: sort all items according to the decreasing order of their corresponding profits. Then choose the item
with the smallest profit and remove it from the knapsack.
2) Ratio-greedy repair: sort all items according to the decreasing order of the corresponding ratios. Then choose the item
with the smallest ratio and remove it from the knapsack.
3) Random repair: choose an item from the knapsack at random and remove it from the knapsack.
Thanks to the repair method, all of the infeasible solutions are repaired into the feasible ones. The following pseudo-code
is a mixed strategy GA (MSGA) which chooses one of three repair methods in a probabilistic way and then applies the repair
method to generate a feasible solution.
1: input an instance of the 0-1 knapsack problem;
2: initialize population Φ0 consisting of N feasible solutions;
3: for t = 0, 1, · · · , tmax do
4:
generate a random number r in [0, 1];
5:
if r < 0.9 then
6:
children population Φt.c ← bitwise-mutate Φt ;
7:
else
8:
children population Φt.c ← one-point crossover Φt ;
9:
end if
10:
if a child is an infeasible solution then
11:
choose one method from the ratio-greedy repair, random repair and value-greedy repair with probability 1/3 and repair
the child into feasible;
12:
end if
13:
the best individual in the parent and children populations is selected into population Φt+1 ;
14:
N − 1 individuals from the parent and children populations into population Φt+1 by roulette wheel selection;
15: end for
16: output the maximum of the fitness function.
The genetic operators used in the above GA are explained below.
• Bitwise Mutation: Given a binary vector (x1 · · · xn ), flip each bit xi with probability 1/n.

3

•

One-Point Crossover: Given two binary vectors (x1 · · · xn ) and (y1 · · · yn ), randomly choose a crossover point k ∈
{1, · · · , n}, swap their bits at point k. Then generate two new binary vectors as follows,
(x1 · · · xk yk+1 · · · yn ),

(y1 · · · yk xk+1 · · · xn ).

Like most of GAs, the MSGA may find reasonably good solutions but has no guarantee about the solution quality. Thus it
is necessary to design evolutionary approximation algorithms with provably good solution quality. The most straightforward
approach is that we first apply the greedy algorithm for generating approximation solutions and then take these solutions as
the starting point of the MSGA. We call this approach greedy algorithm + MSGA. Since the MSGA starts at local optima, it
becomes hard for the MSGA to leave the absorbing basin of this local optimum for seeking the global optimum. This is the
main drawback of the approach.
III. G ENETIC A LGORITHM USING H ELPER O BJECTIVES FOR THE 0-1 K NAPSACK P ROBLEMS
In this section, we propose a novel multi-objective optimisation GA (MOGA) which can beat the combination of greedy
algorithm + MOGA mentioned in the previous section. The algorithm is based on the multi-objectivization technique. The
original single objective optimization problem (1) is recast into a multi-objective optimization problem using helper objectives.
The design of helper objectives depends on problem-specific knowledge. The first helper objective comes from an observation
on the following instance.
Item

1

2

3

4

5

Profit
Weight

10
10

10
10

10
10

12
10

12
10

Capacity

20

The global optimum in this instance is 00011. In the optimal solution, the average profit of packed items is the largest. Thus
the first helper objective is to maximize the average profit of items in a knapsack. The objective function is
n
1 X
h1 (~x) =
xi pi .
(2)
k ~x k1 i=1
Pn
where k ~x k1 = i=1 xi .
The second objective is inspired from an observation on another instance.
Item

1

2

3

4

5

Profit
Weight

15
10

15
10

20
20

20
20

20
20

Capacity

20

The global optimum in this instance is 11000. In the optimal solution, the average profit-to-weight ratio of packed items is
the largest. However, the average profit of these items is not the largest. Then the second helper objective is to maximize the
average profit-to-weight ratio of items in a knapsack. The objective function is
n
1 X pi
xi .
h2 (~x) =
(3)
k ~x k1 i=1 wi
Finally let’s look at the following instance.
Item

1

2

3

4

5

Profit
Weight

40
30

40
30

40
30

40
30

150
100

Capacity

120

It is not difficult to verify that the global optimum in this instance is 11110. In the optimal solution, neither the average
profit of packed items nor average profit-to-weight ratio is the largest, but the number of packed items is the largest. Thus the
third helper objective is to maximize the number of items in a knapsack. The objective function is
h3 (~x) =k ~x k1 .

(4)

We then come to the following multi-objective optimization problem:
max{f (~x), h1 (~x), h2 (~x), h3 (~x)},
~
x

subject to

n
X
i=1

wi xi ≤ C.

(5)

4

Besides the above three helper objectives, it is possible to add more helper objectives, for example, to minimise the average
weight of packed items.
The multi-objective optimisation problem (5) is solved by a MOGA using bitwise mutation, one-point crossover and multicriteria selection, plus a mixed strategy of three repair methods.
1: input an instance of the 0-1 knapsack problem;
2: initialize Φ0 consisting of N feasible solutions;
3: for t = 0, 1, · · · , tmax do
4:
generate a random number r in [0, 1];
5:
if r < 0.9 then
6:
children population Φt.c ← bitwise mutate Φt ;
7:
else
8:
children population Φt.c ← one-point crossover Φt ;
9:
end if
10:
if any child is an infeasible solution then
11:
choose one repair method from the ratio-greedy repair, random repair and value-greedy repair with probability 1/3;
12:
repair the child into a feasible solution;
13:
end if
14:
population Φt+1 ← multi-criterion select N individuals from Φt and Φt.c ;
15: end for
16: output the maximum of f (~
x) in the final population.
The multi-criteria selection operator, adopted in the above MOGA, is novel and inspired from multi-objective optimisation.
Since the target is to maximise several objectives simultaneously, we select individuals which have higher function values with
respect to each objective function. The pseudo-code of multi-criteria selection is described as follows.
1: input the parent population Φt and child population Φt.c ;
2: merge the parent and children populations into a temporary population which consists of 2N individuals;
(1)
(1)
3: sort all individuals in the temporary populations in the descending order of f (~
x), denote them by ~x1 , · · · , ~x2N ;
(1)
(1)
(1)
(1)
(1)
4: select all individuals from left to right (denote them by ~
xk1 , · · · , ~xkm ) which satisfy h1 (~xki ) < h1 (~xki+1 ) or h2 (~xki ) <
(1)

h2 (~xki+1 ) for any ki .
5: if the number of selected individuals is greater than m N
3 then
6:
truncate them to N3 individuals;
7: end if
8: add these selected individuals into the next population Φt+1 ;
9: resort all individuals in the temporary population in the descending order of h1 (~
x), still denote them by ~x1 , · · · , ~x2N ;
10: select all individuals from left to right (still denote them by ~
xk1 , · · · , ~xkm ) which satisfy h3 (~xki ) < h3 (~xki+1 ) for any ki .
11: if the number of selected individuals is greater than N
3 then
12:
truncate them to N3 individuals;
13: end if
14: add these selected individuals into the next population Φt+1 ;
15: resort all individuals in the temporary populations in the descending order of h2 (~
x), still denote them by ~x1 , · · · , ~x2N ;
16: select all individuals from left to right (still denote them by ~
xk1 , · · · , ~xkm ) which satisfy h3 (~xki ) < h3 (~xki+1 ) for any ki .
17: if the number of selected individuals is greater than N
3 then
18:
truncate them to N3 individuals;
19: end if
20: add these selected individuals into the next population Φt+1 ;
21: while the population size of Φt+1 is less than N do
22:
randomly choose an individual from the parent population and add it into Φt+1 ;
23: end while
24: output a new population Φt+1 .
In the above algorithm, Steps 3-4 are for selecting the individuals with higher values of f (~x). In order to preserve diversity,
we choose these individuals which have different values of h1 (~x) or h2 (~x). Similarly Steps 9-10 are for selecting the individuals
with a higher value of h1 (~x). We choose the individuals which have different values of h3 (~x) for maintaining diversity. Steps
15-16 are for selecting individuals with a higher value of h2 (~x). Again we choose these individuals which have different values
of h3 (~x) for preserving diversity. We don’t explicitly select individuals based on h3 (~x). Instead we implicitly do it during
Steps 9-10, and Steps 15-16.
Steps 5-7, Steps 11-13, Steps 17-19, plus Steps 21-23 are used to maintain an invariant population size N .

5

The benefit of using multi-criterion selection is its ability of making search along different directions f (~x), h1 (~x), h2 (~x)
and implicitly h3 (~x). Hence the MOGA may not get trapped into the absorbing area of a local optimum.
IV. E XPERIMENTS
In this section, we implement computer experiments. According to [1], [4], the instances of the 0-1 knapsack problem are
often classified into two categorises.
1) Restrictive capacity knapsack: the knapsack capacity is so small that only a few items can be packed in the knapsack.
An instance with restrictive capacity knapsack is generated in the following way. Choose a parameter B which is an
upper bound on the weight of each item. In the experiments, set B = n. For item i, its profit pi and weight wi are
generated at uniformly random in [1, B]. Set the capacity of the knapsack C = B.
2) Average capacity knapsack: the knapsack capacity is so large that it is possible to pack half of items into the knapsack.
An instance with average capacity knapsack is generated as follows. Choose a parameter B which is the upper bound
on the weight of each item. In the experiments, set B = n. For item i, its profit pi and weight wi are generated at
uniformly random in [1, B]. Since the average weight of each item is 0.5B, thus the average of the total weight of items
is 0.5nB. So we set the capacity to be the half of the total weight, that is C = 0.25nB.
For each type of the 0-1 knapsack problem, 10 instances are generated at random. For each instance, the number of items
n is 100. The population size is 3n. The number of maximum generations is 30n for the MSGA and 10n for the MOGA. All
individuals in the initial population are generated at random. If an individual is an infeasible solution, it is repaired to feasible
using random repair.
Besides the above randomly generated instances, we also consider two special instances. Special instance I is given Table I.
TABLE I
S PECIAL I NSTANCE I: n = 500 AND α = 0.2
Item i

n
1, · · · , ⌈ 1+α
⌉

Profit pi
Weight wi

1
1

n
⌈ 1+α
⌉+1

n
⌈ 1+α
⌉ + 2, · · · , n

αn
1+α

1
n
1
2n

n
1+α

n
1+α

Capacity
Initialisation

−

α
4+4α

0

1

half bits are 1

Special instance II is given in Table II.
TABLE II
S PECIAL I NSTANCE II: n = 200
Item i
Profit pi
Weight wi

1, · · · , n
4
√
0.25n√n + 2
0.25n n + 1

Capacity
Initialisation

one bit is 1, others 0

n
4

+ 1, · · · ,
√
0.3n√n
0.5n n
√
0.5n n
0

n
2

n
2

+ 1, · · · , n
√
√n
n

half bits are 1

The population size is n for Instances I and II. The number of maximum generations is 15n for the MSGA and 5n for the
MOGA. The initialisation of individuals in both MSGA and MOGA refer to the above tables.
Tables III gives experiment results of comparing the greedy algorithm, MSGA, greedy algorithm + MSGA and MOGA.
From the table, we observe that
• the solution quality of MSGA is better or not worse than the greedy algorithm in 20 random instances. However for
Instance I, the MSGA only finds a solution whose value is about 20% of the optimal value.
• the solution quality of greedy algorithm + MSGA is better or not worse than the greedy algorithm in all instances. However
for Instance II, the algorithm gets trapped into a local optimum, and is worse than the MOGA.
• the MOGA is the winner among 4 algorithms and its the solution quality is better or not worse than the greedy algorithm
and MSGA in all instances.
V. C ONCLUSIONS
A novel MOGA using helper objectives is proposed in this paper for solving the 0-1 knapsack problem. First the original
0-1 knapsack problem is recast into a multi-objective optimization problem (i.e. to maximize the sum of profits packed in the

6

TABLE III
A

COMPARISON AMONG 4 ALGORITHMS IN 20 RANDOMLY GENERATED INSTANCES AND 2 SPECIAL INSTANCES . T HE FIRST 10 INSTANCES BELONG TO
THE RESTRICTIVE CAPACITY KNAPSACK PROBLEM . T HE SECOND 10 INSTANCES BELONG TO THE AVERAGE CAPACITY KNAPSACK PROBLEM . ‘ MAX ’:
THE MAXIMUM VALUE OF f (~
x) PRODUCED DURING 10 RUNS . ‘AVERAGE ’: THE AVERAGE VALUE OF f (~
x) OVER 10 RUNS . ‘ STDEV ’: THE STANDARD
DERIVATION OF f (~
x) IN 10 RUNS .

Greedy
Instance

MSGA

Greedy + MSGA

MOGA

max

average

stdev

max

average

stdev

max

average

stdev

1
2
3
4
5
6
7
8
9
10

674
714
561
631
585
787
736
1042
982
906

683
714
622
631
621
787
773
1076
994
942

683
714
622
631
621
787
773
1076
994
942

0
0
0
0
0
0
0
0
0
0

683
714
622
631
621
787
773
1076
994
942

683
714
622
631
620.7
787
773
1076
993
942

0
0
0
0
0.95
0
0
0
3.16
0

683
714
622
631
621
787
773
1076
994
942

681.2
714
622
631
620.7
787
773
1076
993
942

1.55
0
0
0
0.95
0
0
0
3.16
0

11
12
13
14
15
16
17
18
19
20

4107
4090
4138
3901
3997
3984
3820
3914
4456
4149

4111
4102
4169
3925
4047
3994
3848
3920
4471
4177

4110.9
4100.6
4168.6
3923.9
4047
3993
3848
3919.4
4470.1
4175.3

0.32
1.43
1.26
1.29
0
1.05
0
1.90
0.57
1.34

4111
4102
4169
3925
4047
3994
3848
3920
4470
4177

4111
4097.1
4165.6
3922.2
4043.2
3992.5
3845.1
3915.2
4465.4
4171.9

0
4.41
2.37
2.15
3.71
0.85
1.97
2.53
2.59
2.73

4111
4102
4169
3927
4047
3994
3848
3920
4471
4177

4111
4101.2
4169
3923.7
4047
3993.8
3848
3920
4470.4
4176

0
1.03
0
1.95
0
0.632
0
0
0.97
0.82

I
II

416.2
1402.1

83.4
1402.1

83.4
1402.1

0
0

416.2
1402.1

416.2
1402.1

0
0

416.2
1414.2

416.2
1414.2

0
0

knapsack, to maximize the average profit-to-weight ratio of items, to maximize the average profit of items, and to maximize the
number of packed items). Then a MOGA (using bitwise mutation, one-point crossover and multi-criterion selection plus a mixed
strategy of three repair methods) is designed for the multi-objective optimization problem. Experiment results demonstrate that
the MOGA using helper objectives outperforms its rivals, which are the greedy algorithm, MSGA and greedy algorithm +
MSGA. The results also show that the MSGA can find reasonably good solutions but without a guarantee; and the greedy
algorithm + MSGA sometimes gets trapped into a local optimum.
R EFERENCES
[1] S. Martello and P. Toth, Knapsack Problems. Chichester: John Wiley & Sons, 1990.
[2] Z. Michalewicz and J. Arabas, “Genetic algorithms for the 0/1 knapsack problem,” in Methodologies for Intelligent Systems. Springer, 1994, pp.
134–143.
[3] S. Khuri, T. Bäck, and J. Heitkötter, “The zero/one multiple knapsack problem and genetic algorithms,” in Proceedings of the 1994 ACM Symposium
on Applied Computing. ACM, 1994, pp. 188–193.
[4] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, 3rd ed. New York: Springer Verlag, 1996.
[5] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach,” IEEE Transactions on
Evolutionary Computation, vol. 3, no. 4, pp. 257–271, 1999.
[6] A. Jaszkiewicz, “On the performance of multiple-objective genetic local search on the 0/1 knapsack problem-a comparative experiment,” IEEE
Transactions on Evolutionary Computation, vol. 6, no. 4, pp. 402–412, 2002.
[7] M. Eugénia Captivo, J. Clı̀maco, J. Figueira, E. Martins, and J. Luis Santos, “Solving bicriteria 0–1 knapsack problems using a labeling algorithm,”
Computers & Operations Research, vol. 30, no. 12, pp. 1865–1886, 2003.
[8] J. D. Knowles, R. A. Watson, and D. W. Corne, “Reducing local optima in single-objective problems by multi-objectivization,” in Evolutionary MultiCriterion Optimization. Springer, 2001, pp. 269–283.
[9] M. T. Jensen, “Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation,” Journal of Mathematical Modelling
and Algorithms, vol. 3, no. 4, pp. 323–347, 2005.
[10] J. Handl, S. C. Lovell, and J. Knowles, “Multiobjectivization by decomposition of scalar cost functions,” in Parallel Problem Solving from Nature–PPSN
X. Springer, 2008, pp. 31–40.
[11] D. Brockhoff, T. Friedrich, N. Hebbinghaus, C. Klein, F. Neumann, and E. Zitzler, “On the effects of adding objectives to plateau functions,” IEEE
Transactions on Evolutionary Computation, vol. 13, no. 3, pp. 591–603, 2009.
[12] D. F. Lochtefeld and F. W. Ciarallo, “Helper-objective optimization strategies for the job-shop scheduling problem,” Applied Soft Computing, vol. 11,
no. 6, pp. 4161–4174, 2011.
[13] R. Kumar and N. Banerjee, “Analysis of a multiobjective evolutionary algorithm on the 0–1 knapsack problem,” Theoretical Computer Science, vol.
358, no. 1, pp. 104–120, 2006.
[14] T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, “Approximating covering problems by randomized search heuristics using multi-objective
models,” Evolutionary Computation, vol. 18, no. 4, pp. 617–633, 2010.
[15] X. Lai, Y. Zhou, J. He, and J. Zhang, “Performance analysis of evolutionary algorithms for the minimum label spanning tree problem,” IEEE Transactions
on Evolutionary Computation, 2014, (accpeted, online).
[16] J. He and Y. Zhou, “A comparison of GAs using penalizing infeasible solutions and repairing infeasible solutions II,” in Proceedings of the 2nd
International Symposium on Intelligence Computation and Applications. Wuhan, China: Springer, 2007, C1, pp. 102–110.

