Indonesian
Journal
of
Electrical
Engineering
and
Computer
Science
V
ol.
1,
No
.
3,
March
2016,
pp
.
411
418
DOI:
10.11591/ijeecs
.v1.i3.pp411-418
411
A
Ne
w
Hybrid
P
ar
tic
le
Swarm
Optimization
and
Greed
y
f
or
0-1
Knapsac
k
Pr
ob
lem
Phuong
Hoai
Nguy
en
a,b
,
Dong
W
ang
a
,
and
T
ung
Khac
T
ruong
*
a
College
of
Computer
Science
and
Electronic
Engineer
ing,
Hunan
Univ
ersity
,
Changsha
4
10082,
China.n
b
Depar
tment
of
Computer
Science
,
Univ
ersity
of
Labour
and
Social
Aff
airs
,
Vietnam.
*
F
aculty
of
Inf
or
mation
T
echnology
and
IUHYRA,
Industr
ial
Univ
ersity
of
Ho
Chi
Minh
city
,
Vietnam.,
e-mail:
tungtk@iuh.edu.vn
Abstract
This
paper
proposes
a
ne
w
b
inar
y
par
ticle
s
w
ar
m
optimization
with
a
g
reedy
str
ategy
to
solv
e
0-
1
knapsac
k
prob
lem.
T
w
o
constr
aint
handling
techniques
are
consider
to
cooper
a
tion
with
binar
y
par
ticle
s
w
ar
m
optimization
that
are
penalty
function
and
g
reedy
.
The
sigmoid
tr
ansf
er
functi
on
is
used
to
con
v
er
t
real
code
to
binar
y
code
.
The
e
xper
imental
results
ha
v
e
pro
v
en
the
super
ior
perf
or
mance
of
the
proposed
algor
ithm.
K
e
yw
or
ds:
Combinator
ial,
Greedy
,
0-1
knapsac
k
prob
lem,
PSO
.
Cop
yright
c
2016
Institute
of
Ad
v
anced
Engineering
and
Science
.
All
rights
reser
ved.
1.
Intr
oduction
The
0-1
knapsac
k
prob
lem(KP01)
is
kno
wn
to
be
a
combinator
ial
optimization
prob
lem.
The
knapsac
k
prob
lem
has
a
v
ar
iety
of
pr
actical
applications
such
as
cutting
stoc
k
prob
lems
,
por
tf
olio
optimization,
scheduling
prob
lems
[1]
and
cr
yptog
r
aph
y
[2,
3
,
4].
The
knapsac
k
appears
as
a
sub-prob
lem
in
man
y
comple
x
mathematical
models
of
real-w
or
ld
prob
lems
.
In
a
giv
en
set
of
n
items
,
each
of
them
has
an
integer
w
eight
w
i
and
an
integer
profit
p
i
.
The
prob
lem
is
to
select
a
subset
from
the
set
of
n
items
such
that
the
o
v
er
all
profit
is
maximiz
ed
without
e
xceeding
a
giv
en
w
eight
capacity
C
.
It
is
a
NP-Hard
prob
lem
and
hence
it
does
not
ha
v
e
a
polynomial
time
algor
ithm
unless
P
=
N
P
[5].
The
prob
lem
ma
y
be
mathematically
modelled
as
f
ollo
ws:
M
aximiz
e
n
X
i
=1
x
i
p
i
;
(1)
S
ubj
ect
to
n
X
i
=1
x
i
w
i
C
;
x
i
2
f
0
;
1
g
;
8
i
2
f
1
;
2
;
:
:
:
;
n
g
;
where
x
i
tak
es
v
alues
either
1
or
0
which
represents
the
selection
or
rejection
of
the
i
th
item.
In
recent
y
ears
,
man
y
heur
istic
algor
ithms
ha
v
e
been
emplo
y
ed
to
solv
e
KP01
prob
lems:
an
ant
colon
y
optimization
algor
ithm
f
or
KP01
proposed
in
[6]
proposed
;
a
modified
the
par
am-
eters
of
the
ant
colon
y
optimization
model
to
adapt
itself
to
KP01
prob
lems
propose
d
in
[7];
a
bi-
nar
y
par
ticle
s
w
ar
m
optimization
based
on
m
ulti-m
utation
str
ategy
to
solv
e
the
knapsac
k
prob
lem
proposed
in
[8]
;
a
quantum-inspired
e
v
olutionar
y
algor
ithm
f
or
KP01
proposed
in
[9];
a
schema-
guiding
e
v
olutionar
y
algor
ithm
to
solv
e
KP01
prob
lems
proposed
[10];
a
global
har
mon
y
search
algor
ithm
to
solv
e
KP01
proposed
in
[11];
a
genetic
algor
ithm
(GA)
f
or
KP01
proposed
in
[12];
an
impro
v
ed
GA
with
a
du
al
population
f
or
KP01
proposed
in
[13];
a
schema-modified
oper
ator
to
adjust
the
distr
ib
ution
of
the
popula
tion
can
be
f
ound
in
[10],
an
ar
tificial
chemical
reaction
optimization
f
or
KP01
proposed
in
[14].
Although
man
y
KP01
prob
lems
ha
v
e
been
solv
ed
successfully
b
y
these
methods
,
the
research
on
them
is
still
impor
tant,
because
some
ne
w
and
more
difficult
KP01
prob
lems
hidden
Receiv
ed
J
an
19,
2016;
Re
vised
F
eb
11,
2016;
Accepted
F
eb
27,
2016
Evaluation Warning : The document was created with Spire.PDF for Python.
412
ISSN:
2502-4752
in
the
real
w
or
ld
ha
v
e
not
y
et
bee
n
solv
ed.
Man
y
algor
ithms
pro
vide
possib
le
solutions
f
or
some
KP01
prob
lems
,
b
ut
the
y
ma
y
lose
their
efficiency
on
solving
t
hese
prob
lems
due
to
their
o
wn
disadv
antages
.
F
or
e
xam
ple
,
some
methods
proposed
recent
ly
can
only
solv
e
KP01
prob
lems
with
v
er
y
lo
w
dimension,
b
ut
the
y
ma
y
be
una
v
ailab
le
to
solv
e
KP01
prob
lems
with
high
dimension.
Giv
en
the
abo
v
e
consider
ation
,
w
e
designed
an
par
ticle
s
w
ar
m
optimization
with
g
reedy
str
ategy
to
solv
e
KP01.
The
par
ticle
s
w
ar
m
optimization
has
a
good
searching
ability
that
sho
ws
e
xcellent
oper
ation
in
tw
o
impor
tant
f
eatures
of
optimization
metaheur
istics:
intensification
and
div
ersification[8,
15].
Besid
e
,
the
g
reedy
str
ategy
in
this
research
is
used
in
one
phase
of
repair
function,
b
ut
in
another
phase
a
r
andomly
method
is
used
which
is
proposed
in
[9].
The
repair
function
mentioned
in
the
paper
adopts
tw
o
adv
antages
,
the
first
is
to
mak
e
the
algor
ithm
ha
v
e
f
ast
con
v
ergence
b
y
using
a
g
reedy
str
ategy
.
The
e
xper
imental
results
demonstr
ate
the
proposed
algor
ithm
is
super
ior
.
The
rest
of
this
paper
is
organiz
ed
in
sections:
section
2.
present
pre
vious
algor
ithm
f
or
KP01,
section
3.
br
iefly
giv
es
the
or
iginal
fr
ame
w
or
k
of
par
ticle
s
w
ar
m
optimization.
Section
4.
present
the
binar
y
par
ticle
s
w
ar
m
optimization.
Constr
aint
handling
techniques
are
descr
ibed
in
section
5..
W
e
sur
v
e
y
the
beha
vior
of
par
ticle
s
w
ar
m
optimization
and
compare
the
sim
ulated
results
of
the
PSO
in
section
6..
W
e
conclude
this
paper
and
suggest
potential
future
w
or
k
in
section
7..
2.
Related
W
orks
2.1.
Ar
tificial
c
hemical
reaction
optimization
algorithm
(A
CR
O
A)
The
A
CR
O
A
is
a
heur
istic
method
p
roposed
b
y
Alatas
in
[16].
I
t
inspired
from
the
chemical
reaction
process
.
In
the
chemical
reaction
process
,
the
system
tend
to
w
ard
the
highest
entrop
y
and
the
lo
w
est
enthalp
y
.
The
chemical
reactions
possess
efficient
objects
,
states
,
process
,
and
e
v
ents
that
can
be
designed
as
a
computational
method.
Enthalp
y
or
potential
energy
f
or
mini-
mization
prob
lem
and
entrop
y
f
or
maximization
prob
lem
can
be
utiliz
ed
as
objectiv
e
functions
f
or
the
interested
prob
lem
[16,
17].
3.
P
ar
tic
le
s
warm
optimization
The
PSO
conducts
searches
using
a
population
of
par
ticles
,
a
population
of
par
ticles
is
r
andomly
gener
ated
initially
.
The
standard
par
ticle
s
w
ar
m
optimiz
er
maintains
a
s
w
ar
m
of
par
ticle
that
represent
the
potential
solutions
to
prob
lem
on
hand.
Suppose
that
the
search
space
is
D
-
dimensional,
and
the
position
of
i
th
par
ticle
of
the
s
w
ar
m
can
be
represented
b
y
a
D
-dimensional
v
ector
,
x
i
=
(
x
i
1
;
:::;
x
id
;
:::;
x
iD
)
.
The
v
elocity
of
the
par
ticle
x
i
can
be
represented
b
y
another
D
-
dimensional
v
ector
v
i
=
(
v
i
1
;
:::;
v
id
;
:::;
v
iD
)
.
The
best
position
pre
viously
visited
b
y
the
i
th
par
ticle
is
denoted
as
p
i
=
(
p
i
1
;
:::;
p
id
;
:::;
p
iD
)
.
In
essence
,
the
tr
ajector
y
of
each
par
ticle
is
updated
according
to
its
o
wn
flying
e
xper
ience
as
w
ell
as
to
that
of
the
best
par
ticle
in
the
s
w
ar
m.
The
basic
PSO
algor
ithm
can
be
descr
ibed
as:
v
k
+1
i;d
=
w
:v
k
i;d
+
c
1
:r
k
1
:
(
p
k
i;d
x
k
i;d
)
+
c
2
:r
k
2
:
(
p
k
g
;d
x
k
i;d
)
(2)
x
k
+1
i;d
=
x
k
i;d
+
v
k
+1
i;d
(3)
where
v
k
i;d
is
d
th
dimension
v
elocity
of
par
ticle
i
in
cycle
k
;
x
k
i;d
is
the
d
th
dimension
position
of
par
ticle
i
in
cycle
k
;
p
k
i;d
is
the
d
th
dimension
position
of
personal
best
(pbest)
of
par
ticle
i
in
cycle
k
;
p
k
g
;d
is
the
d
th
dimension
position
of
global
best
par
ticle
(gbest)
in
cycle
k
;
w
is
the
iner
tia
w
eight;
c
1
is
the
cognitiv
e
w
eight
and
c
2
is
a
social
w
eight;
r
1
and
r
2
are
tw
o
r
andom
v
alues
unif
or
mly
distr
ib
uted
in
the
r
ange
of
[0,1][8].
The
pseudocode
of
the
PSO
is
giv
en
in
the
algor
ithm
1.
IJEECS
V
ol.
1,
No
.
3,
March
2016
:
411
418
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
413
Algorithm
1:
PSO
algor
ithm
Input:
Initial
par
ameters
Output:
optimal
solution
1
f
or
each
par
ticle
do
2
Initializ
e
par
ticle
3
While
maxim
um
iter
ations
or
minim
um
error
cr
iter
ia
is
not
attained
f
or
each
par
ticle
do
4
Calculate
fitness
v
alue
5
if
the
fitness
v
alue
is
better
than
its
peronal
best
then
6
set
current
v
alue
as
the
ne
w
pBest
7
Choose
the
par
ticle
with
the
best
fitness
v
alue
of
all
as
gBest
8
f
or
each
par
ticle
do
9
Calculate
par
ticle
v
elocity
according
equation
(2)
10
Update
par
ticle
position
according
equation
(3)
11
return
Figure
1.
Sigmoid
function
used
in
BPSO
4.
Binar
y
par
tic
le
s
warm
optimization
The
binar
y
par
ticle
s
w
ar
m
optimization
algor
ithm
w
as
introduced
b
y
Bansal
and
Deep
to
allo
w
the
PSO
algor
ithm
to
oper
ate
in
binar
y
prob
lem
spaces
[18].
It
uses
the
concept
of
v
elocity
as
a
probability
that
a
bit
(position)
tak
es
on
one
or
z
ero
.
In
the
BPSO
,
Eq.
(2)
f
or
updating
the
v
elocity
remains
unchanged,
b
ut
Eq.
(3)
f
or
updating
the
position
is
re-defined
b
y
the
r
ule
x
k
+1
i;d
=
(
0
if
r
and
()
S
(
v
k
+1
i;d
)
1
if
r
and
()
<
S
(
v
k
+1
i;d
)
where
S(.)
is
the
sigmoid
function
f
or
tr
ansf
or
ming
the
v
elocity
to
the
probability
as
the
f
ollo
wing
e
xpression:
S
(
v
k
+1
i;d
)
=
1
1
+
e
(
v
k
+1
i;d
)
(4)
Fig.
1
sho
ws
the
sigmoid
function
using
in
BPSO
.
5.
Handling
Constraints
The
present
b
y
binar
y
str
ing
sometimes
mak
e
the
solution
violate
the
constr
aint.
There
are
tw
o
common
techniques
that
are
penalty
and
repair
function
are
used
to
handle
it.
In
the
first
method,
a
penalty
coefficient
r
atio
with
violated
v
alue
is
used
to
add
to
the
fitness
v
alue
.
Through
the
iter
ations
,
the
solutions
with
larger
fitness
ha
v
e
more
change
to
reproduce
,
and
otherwise
[11].
Although,
this
method
can
help
the
algor
ithm
can
find
the
sufficient
solution,
b
ut
it
do
not
helpful
impro
v
e
the
quality
of
the
solution.
F
ollo
wing,
tw
o
techniques
are
presented
in
details
.
5.1.
P
enalty
function
The
KP01
is
maximization
prob
lem.
The
v
alue
of
the
position
is
equal
to
P
n
i
=1
x
i
p
i
when
the
solution
is
not
violated.
Otherwise
,
a
penal
ty
F
actor
is
used
to
decrease
the
fitness
of
the
violate
position.
In
this
research,
w
e
use
penal
ty
F
actor
=
100
.
The
fitness
function
is
descr
ibed
in
algor
ithm
2.
A
h
ybr
id
PSO
f
or
0-1
knapsac
k
prob
lem
(P
.H.
Nguy
en)
Evaluation Warning : The document was created with Spire.PDF for Python.
414
ISSN:
2502-4752
Algorithm
2:
Fitness
function
Input:
Solution
x
Output:
F
itness
1
F
itness
=
P
n
i
=1
x
i
p
i
penal
ty
F
actor
max
(0
;
P
n
i
=1
x
i
w
i
C
)
2
return
Fitness
5.1.1.
Greed
y
The
repair
oper
ator
is
based
on
repeated
r
a
ndom
selection
until
the
knapsac
k
constr
aints
are
met,
although
this
ma
y
consume
a
lot
of
CPU
time
in
some
cases
.
Con
v
ersely
,
the
tr
aditional
g
reedy
str
ategy
has
some
other
dr
a
wbac
ks
in
the
knapsac
k
prob
lem
and
is
analyz
ed
in
[12].
In
this
paper
,
a
ne
w
repair
oper
ator
is
used
and
it
depends
on
both
the
g
reedy
str
ategy
and
r
andom
selection
[19
].
The
adv
antage
of
this
repair
procedure
is
the
balance
betw
een
CPU
time
cost
and
not
getting
stuc
k
in
local
optima.
The
items
are
sor
ted
according
to
the
profit-to-w
eight
r
atio
p
i
/
w
i
(
i
=
1,
2,.
.
.
,
n
)
so
that
the
y
are
not
increasing.
It
means
that:
p
i
w
i
p
j
w
j
;
f
o
r
i
<
j
:
This
repair
oper
ator
consists
of
tw
o
ph
ases
.
The
first
ph
ase
(called
ADD)
e
xamines
each
v
ar
iab
le
in
decreasing
order
of
p
j
=w
j
and
changes
the
v
ar
iab
le
from
z
ero
to
one
as
long
as
f
easibility
is
not
violated.
The
second
phase
(called
DR
OP)
e
xamines
each
v
ar
iab
le
in
increasing
order
of
p
j
=w
j
and
changes
the
v
ar
iab
le
f
rom
one
to
z
ero
if
f
easibility
is
violated.
The
aim
of
the
DR
OP
phase
is
to
obtain
a
f
easib
le
solution
from
an
inf
easib
le
solution,
whilst
the
ADD
phase
seeks
to
impro
v
e
the
fitness
of
a
f
easib
le
solution.
The
pseudo-code
f
or
the
repair
oper
ator
is
giv
en
in
Algor
ithm
3.
Algorithm
3:
Repair
oper
ator
Input:
Solution
x
Output:
Solution
x
1
%
ADD
phase
2
g
ap
C
P
n
i
=1
x
i
w
i
3
i
1
4
while
(
g
ap
>
0)
and
(
i
n
)
do
5
if
(
g
ap
w
i
)
then
6
x
i
1
7
g
ap
g
ap
w
i
8
i
i
+
1
9
%
DR
OP
phase
10
ov
er
P
n
i
=1
x
i
w
i
C
11
i
n
12
while
(
ov
er
>
0)
and
(
i
1
)
do
13
if
(
ov
er
w
i
)
then
14
x
i
0
15
ov
er
ov
er
w
i
16
i
i
1
17
return
x
IJEECS
V
ol.
1,
No
.
3,
March
2016
:
411
418
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
415
T
ab
le
1.
The
dimension
and
par
ameters
of
fiv
e
test
prob
lems
.
Instance
Dimension
P
ar
ameters
(q,
C
,
p)
f
1
4
q
=
(6,
5,
9,
7),
C
=
20,
p
=
(9,
11,
13,15)
f
2
10
q
=
(30,
25,
20,18,
17,
11,
5,
2,
1,
1),
C
=
60,
p=
(20,
18,
17,
15,
15,
10,
5,
3,
1,
1)
f
3
7
q
=
(31,
10,
20,
19,
4,
3,
6),
C
=
50,
p
=
(70,
20,
39,
37,
7,
5,
10)
f
4
5
q
=
(15,
20,
17,
8,
31),
C
=
80,
p
=
(33,
24,
36,
37,
12)
f
5
20
q
=
(84,
83,
43,
4,
44,
6,
82,
92,
25,
83,
56,
1
8,
58,
14,
48,
70,
96,
32,
68,
92),
C
=
879,
p
=
(91,
72,
90,
46,
55,
8,
35,
75,
61,
15,
77,
40,
63,
75,
29,
75,
17,
78,
40,
44)
T
ab
le
2.
The
detailed
inf
or
mation
of
the
optimal
solutions
.
Instance
Opt.solution
x
Opt.v
alue
f(
x
)
V
alue
of
constr
aint
g(
x
)
f
1
(1,1,0,1)
35
-2
f
2
(0,0,1,0,1,1,1,1,0,0)
50
0
f
3
(1,0,0,1,0,0,0)
107
0
f
4
(1,1,1,1,0)
130
-20
f
5
(1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,1)
1025
-8
6.
Sim
ulation
Results
In
this
section,
w
e
use
BPSO
and
BPSOG
f
or
binar
y
par
ticle
s
w
ar
m
optimization
with
penalty
constr
aint
and
g
reedy
constr
aint
techniques
,
respectiv
ely
.
The
A
CR
O
A
use
the
g
reedy
constr
aint.
The
perf
or
mance
of
BPSOG
algor
ithm
is
e
xtensiv
ely
in
v
estigated
b
y
a
large
n
umber
of
e
xper
imental
studies
.
Nine
0-1
knapsac
k
instances
are
considered
to
testify
the
v
alidity
of
the
BPSOG.
All
the
algor
ithms
are
implemented
in
matlab
2014a.
The
test
en
vironment
is
set
up
on
a
laptop
with
core
i5
M520
CPU
at
2.4
GHz,
4G
RAM,
r
unning
on
Windo
ws
8.1.
6.1.
The
perf
ormance
of
three
a
lgorithms
on
solving
0-1
knapsac
k
pr
ob
lems
with
small
dimension
siz
es
In
this
section,
fiv
e
test
functions
collected
from
[11]
are
used.
In
T
ab
le
1,
f
our
test
func-
tions
with
dimension
are
4,
10,
7,
5,
and
20,
respectiv
ely
.
T
ab
le
2
descr
ibes
the
optimal
solutions
of
each
function.
The
e
xper
iment
f
or
these
fiv
e
test
functions
is
r
un
25
independent
times
.
T
o
e
xtend
study
the
perf
or
mance
of
BPSOG,
f
our
strong
correlated
instances
with
large
dimension
are
also
used.
6.2.
The
perf
ormance
of
three
algorithms
on
solving
0-1
knapsac
k
pr
ob
lems
with
lar
g
e
dimension
siz
es
T
o
test
the
perf
or
mance
of
BPSOG
on
KP01
with
large
dimension,
it
is
compared
with
both
BPSO
and
A
CR
O
A
on
the
0-1
knapsac
k
prob
lem.
In
these
test
cases
,
strongly
correlated
sets
of
data
are
considered.
The
w
eights
w
i
,
re
spectiv
e
pr
ices
p
i
and
the
knapsac
k
capacity
C
are
calculated
as
f
ollo
ws:
w
i
=
r
and
(1
;
10);
(5)
A
h
ybr
id
PSO
f
or
0-1
knapsac
k
prob
lem
(P
.H.
Nguy
en)
Evaluation Warning : The document was created with Spire.PDF for Python.
416
ISSN:
2502-4752
T
ab
le
3.
Exper
imental
results:
the
n
umber
of
items
50,
100,
500
and
1000,
the
maxim
um
n
umber
of
function
e
v
aluation
100000,
the
n
umber
of
r
uns
25.
Instances
Algor
ithms
Best
profit
W
orst
profit
A
v
er
age
profit
stDe
v
A
CR
O
A
1536
1507
1528.70
6.10
50
BPSO
1533
1485
1501.20
17.64
BPSOG
1536
1536
1536.00
0.00
A
CR
O
A
2927
2855
2893.76
18.73
100
BPSO
2876
2792
2827.92
19.73
BPSOG
2978
2977
2977.96
0.20
A
CR
O
A
14775
14428
14582.96
102.22
500
BPSO
14152
13908
14017.44
56.61
BPSOG
15369
15234
15298.24
37.18
A
CR
O
A
28840
27961
28257.48
192.94
1000
BPSO
27332
27044
27173.92
88.74
BPSOG
30050
29712
29819.76
81.17
Figure
2.
The
con
v
ergence
cur
v
es
of
BPSO
and
BPSOG
on
the
kp01.
p
i
=
w
i
+
5
;
i
=
1
;
2
;
:
:
:
;
n
;
(6)
C
=
1
2
n
X
i
=1
w
i
;
(7)
where
r
and(1,
10)
gener
ates
an
integer
in
[1,
10]
unif
or
mly
at
r
andom.
W
e
do
e
xper
iment
on
f
our
test
instances
with
50,
100,
500
and
1000
items
.
Fig.
2
sho
ws
the
con
v
ergence
cur
v
es
of
the
best
profits
of
BPSO
and
BPSOG
in
the
f
our
instances
.
The
BPSOG
sho
ws
better
div
ersification
and
intensification
when
it
is
f
ast
con
v
ergence
a
nd
finds
out
the
better
profit
v
alue
compared
with
BPSO
.
It
indicates
the
global
search
ability
and
the
con
v
ergence
ability
of
BPSOG.
BPSOG
out-
perf
or
med
BPSO
and
A
CR
O
A
in
ter
ms
of
con
v
ergence
r
ate
and
profit
amount.
As
sho
wn
in
Figs
.
2,
the
BPSOG
displa
ys
no
premature
con
v
ergence
in
a
v
er
age
profits
throughout
the
iter
ations
.
The
BPSO
sho
w
premature
con
v
ergence
compared
with
BPSOG
in
500
items
test
instances
.
The
BPSOG
sho
ws
better
div
ersification
and
intensification
when
it
is
f
ast
con
v
ergence
and
finds
out
the
better
profit
v
alue
compared
with
BPSO
.
T
ab
le
3
sho
ws
the
e
xper
imental
results
of
the
instances
.
W
e
ad
opt
the
same
ter
mination
cr
iter
ion,
and
the
function
e
v
aluation
limit
is
set
to
100000,
f
or
all
the
test.
F
or
all
the
instances
,
the
BPSOG
yields
super
ior
results
compared
with
that
of
BPSO
and
A
CR
O
A.
The
ser
ies
of
e
x-
per
imental
results
demonstr
ate
the
super
ior
ity
and
eff
ectiv
eness
of
BPSOG.
In
compar
ison
with
BPSO
and
A
CR
O
A;
the
e
xper
imental
results
sho
w
that
BPSOG
outperf
or
ms
the
other
algor
ithms
in
both
solution
quality
and
computing
time
.
The
reason
f
or
this
super
ior
perf
or
mance
of
BPSOG
is
that
our
proposed
algor
ithm
has
a
good
search
ability
and
a
g
reedy
repair
oper
ator
.
The
A
CR
O
A
is
coded
as
descr
ibing
in
[14].
A
CR
O
A
there
is
only
par
ameter
r
eactantN
um
and
it
is
set
to
10.
There
are
man
y
possib
le
PSO
par
ameter
setting.
In
this
study
,
the
par
ameters
f
or
BPSO
and
BPSOG
are
setting
as:
iner
tia
w
eight
w
=
2
,
local
w
eight
c
1
=
2
,
global
w
eight
c
2
=
2
.
IJEECS
V
ol.
1,
No
.
3,
March
2016
:
411
418
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2502-4752
417
7.
Conc
lusion
In
this
paper
,
a
ne
w
algor
ithm
has
been
p
roposed
based
on
the
binar
y
par
ticle
s
w
ar
m
optimization
with
a
g
reedy
to
solv
e
0-1
knapsac
k
prob
lem
efficiently
.
T
w
o
constr
aint
techniques
based
on
penalty
f
actor
and
g
reedy
str
ategy
is
proposed
to
impro
v
e
the
efficiency
of
the
proposed
algor
ithm.
The
sim
ulation
results
on
fiv
e
state
of
the
ar
t
benchmar
k
instances
and
strong
cor-
related
data
sets
demonstr
ate
that
the
proposed
algor
ithm
has
super
ior
perf
or
mance
compared
with
pre
vious
algor
ithms
.
The
ne
w
approach
pro
vides
better
quality
solutions
when
solv
e
large
scale
instances
.
Ac
kno
wledg
ement
This
w
or
k
w
as
par
tly
suppor
ted
b
y
National
Natur
al
Science
F
oundations
of
China
(No
.
61301148
and
No
.
61272061),
the
fund
amental
research
funds
f
or
the
centr
al
univ
ersities
of
China
(No
.531107040263,
345
531107040276),
the
Research
Funds
f
or
the
Doctor
al
Prog
r
am
of
Higher
Education
of
China
(No
.
20120161110002
and
No
.
201301611200
19),
Hunan
Natur
al
Science
F
oundation
of
China
(No
.
14JJ7023).
Ref
erences
Ref
erences
[1]
S
.
Mar
tello
,
Knapsac
k
Prob
lem:
Algo
r
ithms
and
Computer
Implementations
,
John
Wile
y
and
Sons
,
Ne
w
Y
or
k,
1990.
[2]
B
.
Chor
,
R.
Riv
est,
A
knapsac
k-type
pub
lic
k
e
y
cr
yptosystem
based
on
ar
ithmetic
in
finite
fields
,
Inf
or
mation
Theor
y
,
IEEE
T
r
ansactions
on
34
(5)
(1988)
901
–909.
[3]
R.
Goodman,
A.
McA
ule
y
,
A
ne
w
tr
apdoor
knapsac
k
pub
lic
k
e
y
cr
yptosystem,
in:
T
.
Beth,
N.
Cot,
I.
Ingemarsson
(Eds
.),
Adv
ances
in
Cr
yptology
,
V
ol.
209
of
Lecture
Notes
in
Computer
Science
,
Spr
inger
Ber
lin
/
Heidelberg,
1985,
pp
.
150–158.
[4]
C
.-S
.
Laih,
J
.-Y
.
Lee
,
L.
Har
n,
Y
.-K.
Su,
Linear
ly
shift
knapsac
k
pub
lic-k
e
y
cr
yptosystem,
Selected
Areas
in
Comm
unications
,
IEEE
Jour
nal
on
7
(4)
(1989)
534
–
539.
[5]
M.
R.
Gare
y
,
D
.
S
.
Johnson,
Computers
and
Intr
actability:
A
Guide
to
the
Theor
y
of
NP-
Completeness
,
W
.H.
F
reeman,
Amer
ica,
1979.
[6]
C
.-Y
.
Lee
,
Z.-J
.
Lee
,
S
.-F
.
Su,
A
ne
w
approach
f
or
solving
0/1
knapsac
k
prob
lem,
in:
Systems
,
Man
and
Cyber
netics
,
2006.
SMC
’06.
IEEE
Inter
national
Conf
erence
on,
V
ol.
4,
2006,
pp
.
3138
–3143.
[7]
H.
Shi,
Solution
to
0/1
knapsac
k
prob
lem
based
on
impro
v
ed
ant
colon
y
algor
ithm,
in:
Inf
or-
mation
Acquisition,
2006
IEEE
Inter
national
Conf
erence
on,
2006,
pp
.
1062
–1066.
[8]
Z.
Li,
N.
Li,
A
no
v
el
m
ulti-m
utation
binar
y
par
ticle
s
w
ar
m
optimization
f
or
0/1
knapsac
k
prob-
lem,
in:
Proceedings
of
the
21st
ann
ual
inter
national
conf
erence
on
Chinese
control
and
decision
conf
erence
,
CCDC’09,
IEEE
Press
,
Piscata
w
a
y
,
NJ
,
USA,
2009,
pp
.
3090–3095.
[9]
K.-H.
Han,
J
.-H.
Kim,
Quantum-inspired
e
v
olutionar
y
algor
ithm
f
or
a
class
of
combinator
ial
optimization,
Ev
olutionar
y
Computation,
IEEE
T
r
ansactions
on
6
(6)
(2002)
580
–
593.
[10]
Y
.
Liu,
C
.
Liu,
A
schema-guiding
e
v
olutionar
y
algor
ithm
f
or
0-1
knapsac
k
prob
lem,
in:
Com-
puter
Science
and
Inf
or
mation
T
echnology
-
Spr
ing
Conf
erence
,
2009.
IA
CSITSC
’09.
Inter-
national
Association
of
,
2009,
pp
.
160
–164.
[11]
D
.
Zou,
L.
Gao
,
S
.
Li,
J
.
W
u,
Solving
01
knapsac
k
prob
lem
b
y
a
no
v
el
global
har
mon
y
search
algor
ithm,
Applied
Soft
Computing
11
(2)
(2011)
1556
–
1564,
the
Impact
of
Soft
Computing
f
or
the
Prog
ress
of
Ar
tificial
Intelligence
.
[12]
J
.
Zhao
,
T
.
Huang,
F
.
P
ang,
Y
.
Liu,
Genetic
algor
ithm
based
on
g
reedy
str
ategy
in
the
0-1
knapsac
k
prob
lem,
in:
Genetic
and
Ev
olutionar
y
Computing,
2009.
WGEC
’09.
3rd
Inter
na-
tional
Conf
erence
on,
2009,
pp
.
105
–107.
[13]
W
.
Shen,
B
.
Xu,
J
.
ping
Huang,
An
impro
v
ed
genetic
algor
ithm
f
or
0-1
knapsac
k
prob
lems
,
in:
Net
w
or
king
and
Distr
ib
uted
Computing
(ICNDC),
2011
Second
Inter
national
Conf
erence
on,
2011,
pp
.
32
–35.
A
h
ybr
id
PSO
f
or
0-1
knapsac
k
prob
lem
(P
.H.
Nguy
en)
Evaluation Warning : The document was created with Spire.PDF for Python.
418
ISSN:
2502-4752
[14]
T
.
K.
T
r
uong,
K.
Li,
Y
.
Xu,
A.
Ouy
ang,
T
.
T
.
Nguy
en,
Solving
0–1
knapsac
k
prob
lem
b
y
ar
tificial
chemical
reaction
optimization
algor
ithm
with
a
g
reedy
str
ategy
,
Jour
nal
of
Intelligent
and
Fuzzy
Systems
8
(5)
(2015)
2179–2186.
[15]
R.
P
oli,
J
.
K
ennedy
,
T
.
Blac
kw
ell,
P
ar
ti
c
l
e
s
w
ar
m
optimization,
Sw
ar
m
intelligence
1
(1)
(2007)
33–57.
[16]
B
.
Alatas
,
Acroa:
Ar
tificial
chemical
reaction
optimization
algor
ithm
f
or
global
optimization,
Exper
t
Systems
with
Applications
38
(10)
(2011)
13170
–
13180.
[17]
B
.
Alatas
,
A
no
v
el
chemistr
y
based
metaheur
istic
optimization
method
f
or
mining
of
classifi-
cation
r
ules
,
Exper
t
Systems
with
Applications
39
(12)
(2012)
11080
–
11088.
[18]
J
.
C
.
Bansal,
K.
Deep
,
A
modified
binar
y
par
ticle
s
w
ar
m
optimization
f
or
knapsac
k
prob
lems
,
Applied
Mathematics
and
Computation
218
(22)
(2012)
11042
–
11061.
[19]
T
.
K.
T
r
uong,
K.
Li,
Y
.
Xu,
Chemical
reaction
optimization
with
g
reedy
str
ategy
f
or
the
0–1
knapsac
k
prob
lem,
Applied
Soft
Computing
13
(4)
(2013)
1774–1780.
IJEECS
V
ol.
1,
No
.
3,
March
2016
:
411
418
Evaluation Warning : The document was created with Spire.PDF for Python.