A Hybrid Parallel Multi-Objective Genetic Algorithm for 0/1 Knapsack Problem317
c
The 0/1 knapsack problem is a widely studied prob-
lem due its NP-hard nature and practical importance.
Generally, a 0/1 knapsack problem consists of a set of
items, weight and profit associated with each item, and
an upper bound for the capacity of the knapsack. The
task is to find a subset of items which maximizes the
total of profits in the subset, yet all the selected items
fit into the knapsack, i.e. the total weight does not ex-
ceed the given capacity [7]. This single objective
problem can be extended directly to a multi-objective
case by allowing an arbitrary number of the knapsacks.
Formally, the multi-objective 0/1 knapsack problem is
defined through (1) and (2).
Given a set of m items and a set of n knapsacks with
pij = profit of item j according to knapsack i, wij =
weight of item j according to knapsack i, ci = capacity
of knapsack i.
Find a vector such that,
12
,,,0,1
m
m
xxx x
1
1, 2,,:m
ij ji
j
inw.x
(1)
and for which
12
,,,
n
xfxfx fx is
max imum, whe r e
iijj
xpx (2)
and xj = 1 if item j is selected.
In order to obtain reliable and sound result, three
different test problems are investigated where both the
number of knapsacks (i.e., number of objectives) and
the number of items are varied. Two knapsacks (i.e.,
two objectives) are taken under consideration in com-
bination with 250, items. Following suggestions in,
profits and weights are chosen, where pij and wij are
random integers in the interval (10,100) [7]. Also as
reported, about half of the items are expected to be in
the optimal solutions when this type of knapsack ca-
pacity is used [7]. Thus, the knapsack capacities are
normally set to half the total weight according to the
corresponding knapsack as indicated in Equation (3)
1
05m
i
j
c.w
i
j
(3)
The paper is structured as follows: Section 2 deals
with review on PMOGA and its models. Section 3 pre-
sents the proposed hybrid model. The problem is
evaluated and studied empirically by using the above
model in Section 4. Finally conclusion is drawn in Sec-
tion 5.
2. Review of Parallel MOGA Models
Evolutionary algorithms are very suitable for paralleliza-
tion, as crossover, mutation, and in particular the time-
consuming fitness evaluation can be performed inde-
pendently on different individual.
The approaches to parallelize multi-objective GAs can
be grouped into three categories:
1) Jakobovic Master-Slave: Jakobovic model is one
type of master slave models [1]. In this model the master
only triggers the slaves. Each slave and the master (also
perform as a slave instead of being idle), then creates
random initial population, evaluates created individuals,
perform whole evaluation process and then return the
final results to the master. This eliminates the time re-
quired to generate each population at the server for slaves,
the communication overhead and allows for an exhaus-
tive search of the solution space by the slaves through
random explorations [1].
2) Island Model: In this model, every processor runs an
independent EA, using a separate sub-population. The
processors cooperate by regularly exchanging migrants
(good individuals). The island model is particularly suit-
able for computer clusters, as communication is limited
[3]. This model scales very well. Low communication
overhead as less population migration between the is-
lands. This model is robust to failure as it is willing to
lose small populations. This model has higher diversity
as it has the working principle of isolated population with
migration.
3) Cone Separation model: It was suggested by Branke
et al. in 2004 [2]. The basic idea of this model is to di-
vide the search space in several regions and assign it to
the different processor. The partitioning of the search
space is adopted at regular intervals by normalizing the
fitness values in such a way that the whole non-domi-
nated front is within the unit square (hypercube, for more
than 2 dimensions). After the normalization, the fitness
space is partitioned into equal cones. Each processor is
then assigned one part. Therefore, whenever the con-
straints are adapted, individuals violating the constraints
are migrated into the population where they do not vio-
late the constraints. Thereby, individuals are just added
to the receiving population, without explicitly deleting
others. Overall, the approach is integrated into NSGA-II
[4,6].
3. Hybrid Model
Master-slave and multiple-deme parallel GAs can
quickly reach to good solutions when they are designed
properly, but even better quality result can be found by
combining any two basic form of parallel GA, in to a
hierarchical algorithm. The basic idea is to design a mul-
tiple-deme algorithm where the demes themselves are
some form of parallel MOGAs. In our proposed model
we have integrated two basic models Island i.e., multiple
deme model at the higher level with Jakobovic model at
Copyright © 2011 SciRes. JSEA