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

ﬁt 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

deﬁned 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,

proﬁts 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