Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
9,
No.
3,
June
2019,
pp.
2064
2074
ISSN:
2088-8708,
DOI:
10.11591/ijece.v9i3.pp2064-2074
r
2064
P
arallel
h
ybrid
chick
en
swarm
optimization
f
or
solving
the
quadratic
assignment
pr
oblem
Soukaina
Cherif
Bourki
Semlali,
Mohammed
Essaid
Riffi,
F
ayc
¸
al
Chebihi
Department
of
mathematics,
F
aculty
of
Sciences,
Uni
v
ersity
of
Chouaib
Doukkali,
El
Jadida,
Morocco
Article
Inf
o
Article
history:
Recei
v
ed
Aug
4,
2018
Re
vised
No
v
23,
2018
Accepted
Dec
20,
2018
K
eyw
ords:
Quadratic
assignment
problem
Metaheuristics
Hybrid
Chick
en
sw
arm
optimization
T
ab
u
search
QAPLib
ABSTRA
CT
In
this
research,
we
intend
to
suggest
a
ne
w
method
based
on
a
parallel
h
ybrid
chick
en
sw
arm
optimization
(PHCSO)
by
inte
grating
the
constructi
v
e
procedure
of
GRASP
and
an
ef
fecti
v
e
modified
v
ersion
of
T
ab
u
search.
In
this
v
ein,
the
goal
of
this
adapta-
tion
is
straightforw
ard
about
the
f
act
of
pre
v
enting
the
stagnation
of
the
research.
Fur
-
thermore,
the
proposed
contrib
ution
looks
at
pro
viding
an
optimal
trade-of
f
between
the
tw
o
k
e
y
components
of
bio-inspired
metaheuristics:
local
intensification
and
global
di
v
ersification,
which
af
fect
the
ef
ficienc
y
of
our
proposed
algorithm
and
the
choice
of
the
dependent
parameters.
Moreo
v
er
,
the
pragmatic
results
of
e
xhausti
v
e
e
xperiments
were
promising
while
applying
our
algorithm
on
di
v
erse
QAPLIB
instances.
Finally
,
we
briefly
highlight
perspecti
v
es
for
further
research.
Copyright
c
2019
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Soukaina
Cherif
Bourki
Semlali,
Laroseri
Laboratory
,
Department
of
mathematics,
F
aculty
of
Sciences,
Uni
v
ersity
of
Chouaib
Doukkali,
El
Jadida,
Morocco.
Email:
Soukaina.cherif.b
.s@ucd.ac.ma
1.
INTR
ODUCTION
Combinatorial
optimization
problems
are
an
substantial
paradigm
[1]
and
an
important
challenge,
a
lot
of
algorithm
has
been
applied
in
se
v
eral
fields
of
real
life
such
as
engineering
and
economics.
One
of
the
cate
gories
includes
problems
with
continuous
v
ariables,
then
this
refer
to
handling
the
discrete
optimization,
a
simple
e
xample
of
this
pu
r
vie
w
is
to
find
the
minimum
or
the
maximum
of
a
gi
v
en
function
f
under
a
set
of
constraints
[2].
In
the
last
tw
o
decades,
nature
has
been
a
source
of
inspiration
for
man
y
scientists.
Man
y
contem-
porary
metaheuristic
algorithms
ha
v
e
been
stemming
from
the
beha
vior
of
biological
systems
in
nature
[3].
especially
those
who
interact
with
each
other
in
a
sw
arm
([4],[5]).
Some
e
xamples
of
studies
are
also
proposed
to
shed
light
on
the
beha
vior
of
sw
arm
intelligence
whic
h
are
stretched
from
the
nature:
bee
algorithms[6]
[7],
harmon
y
search
[8],
ant
colon
y
optimization
[9]
[10],
bat
algorithm
[11],
particle
sw
arm
optimization
[12],
firefly
algorithm
[13]
and
cuck
oo
search
[14].
The
quadratic
assignment
problem
(QAP)
is
one
of
the
most
classical
NP-hard
combinatorial
opti-
mization
problem
[15].
There
are
no
e
xact
algorithms
which
could
be
used
to
solv
e
lar
ge
instances,
QAP
w
as
initiated
at
the
first
time
by
k
oopmans
and
beekmann
form
[16],
this
problem
has
been
dra
wing
man
y
scientists
attention.
The
aim
of
the
problem
i
s
to
minimize
the
objecti
v
e
function
QAP
(
A;
B
;
)
in
order
to
or
g
anize
the
formulation
of
a
gi
v
en
f
acilities
that
should
be
optimally
assigned
to
a
gi
v
en
locations.
Gi
v
en
tw
o
matri
ces
of
size
n
n
called
A=
a
ij
and
B=
b
(
i
)
(
j
)
as
A
refers
to
the
flo
ws
between
pairs
of
f
acilities
and
B
refers
to
the
distance
of
their
locations
(
i
)
and
(
j
)
.
The
quadrat
ic
assignment
problem
can
be
depicted
by
the
classical
J
ournal
homepage:
http://iaescor
e
.com/journals/inde
x.php/IJECE
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
r
2065
formulation
v
ersion
of
K
oopmans-Beckmann
as:
min
2
Q
QAP
(
A;
B
;
)
=
n
X
i
=1
n
X
j
=1
a
ij
:b
(
i
)
(
j
)
(1)
Where
the
function
denotes
the
cost
assignment
of
n
f
acilities
to
n
locations
and
Q
is
the
set
of
all
possible
permutations,
2
Q
is
the
permutation
that
minimizes
the
cost
function,
furthermore
each
solution
is
encoded
by
a
permutation.
The
fitness
landscape
w
as
introduced
in
1932
[17]
to
describe
the
beha
viors
of
e
v
olutionary
algo-
rithms,
then
by
predicting
its
performance
it
help
to
design
it.
The
fitness
landscape
(
S
;
f
;
d
)
of
an
y
instance
of
the
quadratic
assignment
problem
consists
of
a
set
of
solutions
S,
a
fitness
function
f
:
S
!
<
,
and
a
distance
measure
d
of
the
spatial
structure
of
the
landscape.
Moreo
v
er
,
the
neighborhood
operator
N
is
applied
in
order
to
con
v
ert
a
solution
s
2
S
into
a
ne
w
solution
S
0
.
the
search
space
can
be
generally
represented
as
G
=
(
S
;
E
)
where
S
is
the
v
ertices
and
E
is
the
edges
of
the
graph.
The
concept
of
fitness
landscapes
[17]
has
been
sho
wn
to
help
understanding
the
beha
vior
of
combina-
torial
optimization
algorithms.
Thus,
three
dif
ferent
classes
of
instances
as
sho
wn
in
Figure
1
could
be
defined
by
the
fitness
landscape
analysis
techniques,
the
entrop
y
and
the
distrib
ution
of
the
local
optima
([18],[19]),
the
first
type
of
instances
is
the
Nonstructured
Landscape
which
all
ha
v
e
a
uniform
random
nature
by
applying
a
local
search
on
this
instances
good
solutions
will
be
quickly
found,
the
second
la
nd
s
cape
is
the
Massif
central
which
surround
only
real
instances
then
the
use
of
tab
u
search
allo
ws
to
find
a
promising
results
and
finally
the
Multimassif
instances
which
comprises
only
lar
ge
instances.
Figure
1.
Dif
ferent
classes
of
instances
by
the
Correlation
between
the
w
alk
length
and
the
distrib
ution
entop
y-distance
[20]
Another
classification
is
proposed
according
to
T
aillard
[21],
the
classification
includes
four
class
es.
The
first
classe
is
the
unstructured
and
randomly
generated
instances;
the
second
classe
is
the
instances
with
the
distance
matrix
based
on
the
Manhattan
distance
on
a
grid;
then
the
real-life
instances;
and
finally
the
instances
which
are
randomly
generated
and
based
on
the
structure
of
the
real-life
instances.
In
this
paper
,
we
introduce
a
ne
w
h
ybrid
Chick
en
Sw
arm
Optimization
(PHCSO)
by
enhancing
the
search
strate
gy
of
the
original
CSO
algorithm.
The
first
step
will
be
the
use
of
the
constructi
v
e
procedure
of
GRASP
by
threads
to
create
the
popoluation
and
then
we
apply
a
ne
w
modifications
to
the
operations
and
the
operators
of
CSO
(position
representation
and
its
update
equation).
The
second
step
will
be
the
incorporate
of
the
random
pairwise
2-w
ay
perturbation
neighborhood
mechanism
as
a
mutation
process
in
order
to
impro
v
e
the
mo
v
ement
equation
of
rooster
.
In
the
third
step,
we
inte
grate
a
modified
sequential
constructi
v
e
crosso
v
er
operator
in
the
mo
v
ement
equation
of
chicks.
Finally
,
we
will
e
v
aluate
the
quality
of
our
approach
by
applying
a
fitness
landscape
analysis
and
a
propabilty
distrib
ution
,
in
order
to
ensure
the
balance
between
intensification
and
di
v
ersification
capabilities
of
PHCSO.
W
e
will
compare
the
performance
of
our
proposed
approach
to
other
algorithms
from
the
literature
in
term
of
run
time
and
quality
of
solution.
The
remainder
of
the
paper
i
s
di
vided
into
dif
ferent
sections:
The
second
section
pro
vides
an
o
v
ervie
w
of
the
related
w
ork
of
di
v
erse
QAP
applications.
In
the
third
section,
we
gi
v
e
a
brief
description
of
the
chick
en
sw
arm
algotrithm
used
in
this
contrib
ution.
In
the
fourth
section,
we
describe
the
tab
u
search,
the
constructi
v
e
P
ar
allel
hybrid
c
hic
k
en
swarm
optimization...
(Soukaina
Cherif
Bourki
Semlali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2066
r
ISSN:
2088-8708
procedure
of
GRASP
and
2-w
ay
perturbation
neighborhood
mechanism.
In
the
fifth
section,
we
present
the
ne
w
adapted
method.
In
the
ne
xt
section,
we
pro
vide
the
parameters
used
and
the
results
of
the
final
of
fspring
obtained
of
this
contrib
ution.
Finally
,
in
the
last
section,
we
close
this
paper
with
a
conclusion
and
the
prospects.
2.
RELA
TED
W
ORK
Since
the
apparition
of
the
mathematical
model
related
to
economic
acti
vities,
Quadratic
ass
ignment
problem
ha
v
e
been
ubiquitously
superv
ening
to
solv
e
se
v
eral
problems
and
v
arious
practical
applications
[22].
Recently
se
v
eral
researchers
around
the
w
orld
ha
v
e
demonstrated
a
huge
interest
to
QAP
,
some
of
them
ha
v
e
conducted
a
surv
e
y
on
theory
and
applications
techniques
used
in
order
to
solv
e
this
problem
[23],
QAP
models
and
presents
v
arious
theoretical
and
practical
problems
[24]
such
as
the
graphical
partitioning,
data
analysis,
hospital
layout
[25],
image
synthesis,
type
writer
k
e
yboard
design
[26]
and
the
problem
of
linear
arrangement.
W
e
can
notice
that
man
y
NP-hard
combinatorial
optimization
problems
can
be
sculptured
as
QAP
.
F
or
e
xample,
memory
layout
optimization
in
signal
processors
[27],
VLSI
design,
campus
planning
model,
dartboard
design
and
scheduling
process.
Some
of
the
popularly
studies
ha
v
e
been
w
orn
out
techniques
for
solving
QAP
such
as
Greedy
3-Opt
[28],
Ant
Colon
y
Optimization
(A
CO)
[29],
Genetic
Algorithms
(GA)
[30],
Scatter
Search
(SS)[31],
Iter
-
ated
local
search
algorithm
[32],
simulated
annealing
[33],
Greedy
Randomized
Adapti
v
e
Search
Procedure
(GRASP)
Numerous
natural
inspired
heuris
tics
is
applied
to
solv
e
QAP
and
a
v
ailable
as
a
guideline
for
im-
pro
v
ement,
among
the
contrib
utions
that
ha
v
e
reached
widespread
success
are:
a
ne
w
recombination
operator
for
the
genetic
algorithm
[34],
the
Backboard
W
iring
Problem
by
steinber
g
in
1961
[35],
Hef
fle
y
used
the
quadratic
assignment
problem
to
solv
e
the
best
inte
ger
assignment
and
a
set
of
sustaining
prices
in
1980
[36],
Geof
frion
and
Gra
v
es
in
1976
used
the
QAP
to
solv
e
the
problem
of
Scheduling
P
arallel
Production
Lines
with
Changeo
v
er
Costs
[37],
Benjaaf
ar
in
2002
introduced
a
ne
w
methods
for
designing
the
ne
xt
Generation
F
actory
Layouts
[38],
W
ess
and
Zeitlhofer
in
2004
applied
to
solv
e
the
phase
coupling
problem
between
data
memory
layout
generation
and
address
pointer
assignment
[27].
3.
CHIKEN
SW
ARM
OPTIMIZA
TION
Chick
en
sw
arm
optimization
(CSO)
is
a
ne
w
stochastic
algorithm
introduced
in
2014
[39].
CSO
is
based
on
the
beha
vior
of
chick
ens,
whic
h
simulates
the
hierarchical
order
in
the
sw
arm
while
searchinf
for
food.
The
approach
of
the
algorithm
spreads
o
v
er
the
follo
wing
four
h
ypothesis:
(1)
Each
subgroup
of
the
sw
arm
includes
a
Roosters,
hens
and
se
v
eral
chicks.
(2)
The
best
fitness
v
alue
helps
to
determine
the
subgroups
and
the
type
of
each
indi
vidual,
the
best
fitness
v
alue
denotes
the
roosters.
In
the
other
side,
the
w
orst
fitness
v
alue
defined
the
chicks.
Moreo
v
er
,
the
rest
of
indi
viduals
are
chick
ens
which
randomly
select
their
groups
and
the
mother
relationship
with
chicks.
Then,
each
chick
follo
ws
their
mothers
for
seeking
food.
(3)
The
hierarchical
order
and
the
relations
between
each
mother
and
their
childs
are
updated
after
a
fe
w
generations.
(4)
Indi
viduals
in
each
subgroup
follo
w
their
group-leader
to
search
for
food,
b
ut
may
also
steal
good
food
that
ha
v
e
been
found
by
other
indi
viduals.
Each
position
depict
aslo
a
gi
v
en
solution
of
our
problem.
The
first
equation
is
the
position
update
equation
of
the
rooster:
x
t
+1
i;j
=
x
t
i;j
(1
+
R
andn
(0
;
2
))
(2)
2
=
(
1
;
if
f
i
f
k
;
exp(
f
k
f
i
j
f
i
j
"
other
w
ise
k
2
[1
;
N
]
;
k
6
=
i
(3)
Where
K
i
s
the
inde
x
of
the
rooster
(the
leader
of
the
group)
randomly
selected
and
specified
by
the
Gaussian
distrib
ution
R
andn
(0
;
2
)
as
the
standard
de
viation
is
2
,
in
this
case
f
is
the
fitness
v
alue
of
the
current
rooster
.
IJECE,
V
ol.
9,
No.
3,
June
2019
:
2064
–
2074
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
r
2067
The
second
equation
is
the
position
update
equation
of
the
hens:
x
t
+1
i;j
=
x
t
i;j
+
S
1
R
and
(
x
t
r
1
;j
x
t
i;j
)
+
S
2
R
and
(
x
t
r
2
;j
-
x
t
i;j
)
(4)
Where
S
1
=
e
xp
(
f
i
f
r
1
j
f
i
j
+
"
)
and
S
2
=
exp((
f
r
2
-
f
i
)
F
inal
l
y
;
thepositionupdateeq
uationof
thechick
s
:
x
t
+1
i;j
=
x
t
i;j
+
F
L
(
x
t
m;j
x
t
i;j
))
(5)
Where
m
2
[1
;
N
]
represents
t
he
chick’
s
mother
and
F
L
2
[0
;
2]
is
a
randomly
selected
parameter
that
denotes
the
relationship
between
the
chicks
and
its
mother
.
In
2015
Dinghui
W
u
[40],
the
position
update
equation
of
the
chicks
has
been
strengthened
by
con-
sidering
the
learning
f
actor
C
of
the
rooster
r
and
the
self-learning
f
actor
W
which
ensures
the
approach
of
di
v
ersification
in
lar
ge
space,
the
ne
w
equation
of
chicks
is
surrog
ated
as
follo
ws:
x
t
+1
i;j
=
W
x
t
i;j
+
F
L
(
x
t
m;j
x
t
i;j
))
+
C
(
x
t
r
;j
x
t
i;j
))
(6)
4.
THE
CONSTR
UCTIVE
PR
OCEDURE
OF
GRASP
The
greedy
randomized
adapti
v
e
search
procedure
(GRASP)
is
an
iterati
v
e
method
for
combi
n
a
torial
optimization
problems
[41],
man
y
application
of
GRASP
for
the
quadratic
assignment
problem
w
as
presented
in
the
literature
[42]
[43].
GRASP
is
an
iterati
v
e
process,
each
iterati
on
goes
t
hroug
h
tw
o
phase
the
firs
t
one
is
a
construction
phase,
in
which
a
possible
solution
with
good
quality
is
generated.
The
second
phase
is
the
local
search,
a
local
optimum
could
be
found
in
the
neighborhood
of
the
feasible
solution
[44].
In
this
paper
,
we
will
accurately
use
t
he
construction
phase
of
GRASP
[42],
which
includes
tw
o
stages
in
order
to
pro
vide
better
initial
solutions
for
the
ne
w
approac
h
,
allo
wing
the
sw
arm
to
con
v
er
ge
more
quickly
to
w
ards
an
optimal
solutions
.
In
another
side
tw
o
components
could
illustrate
the
quality
of
this
approach,
the
adapti
v
e
Greedy
Measures
and
the
randomized
selection
of
assignments
which
e
v
aluate
the
choise
of
each
possible
assignment
and
then
g
arauntee
a
good
intensification
strate
gy
[45].
The
first
stage
of
construction
phase
proposed
by
Li
et
al.
selects
t
w
o
pairs
of
f
acility-location
then
the
n
2
n
distance
entries
in
D
are
sorted
in
an
ascending
order
and
the
smallest
i
nte
ger
[
(
n
2
n
)]
are
selected.
In
each
c
ycle
on
a
graph
of
QAP
,
each
f
acility-location
is
a
v
erte
x,
the
fully
connected
graph
for
n
elements
has
n
2
n
edges.
On
the
other
hand,
the
n
2
n
flo
w
entries
in
F
are
sorted
in
descendi
ng
order
and
the
lar
gest
inte
ger
[
(
n
2
n
)]
are
selected.
In
the
ne
xt
step,
the
cost
f
ij
d
k
l
are
sorted
in
increasing
order
by
k
eeping
the
smalest
[
(
n
2
n
)]
elements,
where
1
i;
j
;
k
;
l
n
;
i
6
=
j
;
k
6
=
l
.
The
percentage
and
will
be
defined
as
the
candidate
restriction
parameters
of
GRASP
,where
2
[0;
1]
and
2
[0;
1]
.
The
greedy
function
allo
ws
to
select
the
couple
f
acility-location
which
ha
v
e
the
smallest
f
i;
s
:d
k
;s
from
the
[
(
n
2
n
)]
,
where
i
=
2
A
to
location
k,
we
note
that
A
is
the
set
of
already-ass
igned
f
acilities,
its
v
alue
change
at
each
iteration,
then
it
will
be
computed
as
follo
w:
l
i;k
=
X
s
2
A
f
i;
s
:d
k
;s
(7)
The
candidate
restriction
limits
RCL
k
for
location
k
is
depicted
as:
R
LC
k
=
l
i;k
min
(
l
i;k
)
+
(
max
(
l
i;k
)
min
(
l
i;k
))
=i
=
2
A
(8)
In
the
stage
2,
tw
o
f
acility-location
pairs
(
j
1
;
l
1
)
and
(
j
2
;
l
2
)
are
randomly
selected
from
the
[
(
n
2
n
)]
sorted
pairs.
Finally
,
the
rest
f
acilities
are
assigned
to
the
rest
of
locations
by
respecting
the
greedy
function.
P
ar
allel
hybrid
c
hic
k
en
swarm
optimization...
(Soukaina
Cherif
Bourki
Semlali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2068
r
ISSN:
2088-8708
5.
T
AB
U
SEARCH
A
neighborhood
search
algorithm
looks
for
the
neighbors
of
a
current
solution
in
order
to
find
a
better
one.
The
main
concern
of
this
type
of
algorithm
is
that
it
can
easily
get
caught
in
a
local
optimum.
Accordingly
,
the
use
of
a
T
ab
u
search
can
help
to
a
v
oid
this
problem.
T
ab
u
search
w
as
introduced
by
Glo
v
er
[46]
in
order
to
a
v
oid
the
local
opt
imum.
Afterw
ards,
Glo
v
er
presented
[47]
the
essential
basis
which
are
enlar
ged
by
a
ne
w
strate
gy
of
tab
u
search
for
solving
combinatorial
optimization
problems.
In
1995,
taillard
of
fers
a
comparison
of
dif
ferent
tab
u
search
strate
gy
[21].
Man
y
application
of
tab
u
search
is
ada
p
t
ed
to
solv
e
combinatorial
optimization
problems
especially
for
the
quadratic
assignment
problem,
such
as:
the
rob
ust
tab
u
search
(Ro-TS)[48],
a
parallel
adapti
v
e
tab
u
search
approach
[49],
a
modified
v
ersion
of
the
tab
u
search
algorithm
[50]
which
unified
man
y
approaches
as
intensification
and
di
v
ersification
(I
&
D
approach).
The
aim
k
e
y
of
tab
u
search
is
to
allo
w
mo
v
es
of
S
a
set
of
solutions
e
v
en
if
ther
is
no
impro
ving
neighboring
solution
where
s
2
N
(
s
)
,
thus
it’
s
necessary
to
choose
a
random
permutation
as
an
initial
solution,
then
by
considering
as
the
current
solution
among
(
)
set
of
all
possible
permutations,
(
)
illustrate
as
well
the
set
of
neighbour
solutions
of
,
the
random
perturbations
are
applied
to
di
v
ersify
the
probabilty
in
the
search
space,
then
(
;
r
;
s
)
is
defined
as
the
v
alue
of
a
mo
v
e
or
the
cost
of
permutation
from
the
location
r
to
the
location
s
.
All
the
mo
v
es
is
stored
in
a
tab
u
list
T
,
then
the
information
is
memorisied
on
the
last
h
mo
v
es
or
the
tab
u
list
size.
The
tab
u
list
is
lightened
during
the
process
by
discarding
the
oldest
solution
based
on
the
FIFO
mechanism
(First
In
First
Out),
since
the
size
of
the
the
memory
is
limited
which
mak
es
it
impossible
to
record
all
the
solutions
found.
Then,
in
the
symmetric
case,
the
mathematical
equation
of
the
cost
is
represented
as
follo
ws:
(
;
r
;
s
)
=2.
P
n
k
6
=
r
;s
(
a
sk
a
r
k
)(
b
(
s
)
(
k
)
b
(
r
)
(
k
)
)
(9)
Then
it
is
easy
to
compute
the
costs
of
all
possible
permutations
in
0(
n
2
)
time.
The
mo
v
e
from
the
current
solution
i
to
the
neighboring
solution
j
is
defined
by
2-e
xchange
neigh-
borhood
function
N
2
:
!
2
and
N
2
(
)
=
(
0
=
0
2
;
d
(
;
0
)
=
2)
where
d
is
the
distance
between
solutions,
otherwise
2-e
xchange
neighborhood
operator
p
ij
:
!
0
(
i;
j
=
1
;
2
::n
)
allo
ws
to
e
xchange
ith
and
jth
elements
in
the
current
permutation
then
0
=
p
ij
.
6.
MUL
TIPLE
THREADS
In
this
paper
,
we
inte
grate
a
search
mechanism
based
on
a
cooperati
v
e
beha
vior
of
man
y
indi
viduals
of
chick
en
sw
arm
in
order
to
design
an
h
ybrid
parallel
CSO,
se
v
eral
groups
of
the
chick
en
sw
arm
cooperate
to
find
better
solutions.
The
ne
w
parall
el
approach
allo
ws
obtaining
high
quality
results
than
the
sequential
model
in
reasonable
e
x
ecution
time.
Each
thread
e
x
ecuted
one
indi
vidual
and
each
thread
block
w
as
used
for
an
independent
e
x
ecution
of
one
group.
The
pa
rallel
algorithm
runs
on
GPU,
while
the
CPU
is
used
to
initialize
the
solutions
by
the
constructi
v
e
procedure
of
GRASP
.
7.
P
ARALLEL
HYBRID
CSO
FOR
Q
U
ADRA
TIC
ASSIGNMENT
PR
OBLEM
The
pseudocode
of
the
ne
w
metaheuristic,
called
parallel
h
ybrid
chick
en
sw
arm
optimization
(PHCSO)
is
summarized
in
Algorithm
1.
In
this
paper
,
we
pro
vide
a
ne
w
redefinition
of
operators
and
operations
already
introduced
by
CSO
algorithm,
the
ne
w
approach
is
based
on
three
operations
,
the
subtraction
operat
ion
,
the
multiplication
op-
eration
and
the
addition
operation
.
On
the
one
side,
the
contructi
v
e
procedure
of
GRASP
allo
ws
to
ha
v
e
better
initial
solutions
for
the
adapted
algorithm.
On
the
other
side,
the
2
w
ay-perturbation
procedure
of
T
ab
u
search
will
be
inter
grated
to
solv
e
the
problem
found
in
the
rooster’
s
mo
v
ements,
as
in
the
pre
vious
studies,
a
rooster
can
mo
v
e
only
if
a
better
fitness
v
alue
is
check
ed.
The
main
equations
used
to
analyze
the
mo
v
ement
of
roosters,
hens
and
chicks
are
respecti
v
ely
defined
by
the
follo
wing
equations
10
,11
and
12.
x
t
+1
i
=
x
t
i
R
andn
(0
;
2
)
x
t
i
(10)
IJECE,
V
ol.
9,
No.
3,
June
2019
:
2064
–
2074
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
r
2069
x
t
+1
i
=
x
t
i
S
1
R
and
(
x
t
r
1
x
t
i
)
S
2
R
and
(
x
t
r
2
x
t
i
)
(11)
x
t
+1
i
=
W
x
t
i
F
L
(
x
t
m
x
t
i
)
C
(
x
t
r
x
t
i
)
(12)
In
this
paper
,
operator
depiced
the
crosso
v
er
operator
used
in
the
position
update
equation
of
hens
and
chicks.
Furthermore,
is
redefined
as
the
choice
of
one
crosso
v
er
operators.
The
uniform
crosso
v
er
(UX)
[51]
illustrates
the
mo
v
ement
to
w
ards
the
leader
of
groups
and
the
sequential
constructi
v
e
crosso
v
er
(SCX)
[52]
to
the
mo
v
ement
to
w
ards
the
neighbors,
which
could
guarantee
the
competition
in
each
group
of
the
sw
arm.
The
mutation
process
inspired
of
the
genetic
algorithm
i
ncreases
the
di
v
ersity
in
a
population
by
using
random
permutations
in
a
selected
solutions.
In
this
w
ork,
we
consider
2-e
xchange
neighborhood
as
a
mutation
operator
.
The
probabilty
of
applying
the
crosso
v
er
is
higher
than
the
probabilty
of
mutation.
Consequently
,
while
designing
the
strate
gy
of
searc
h
,
each
indi
vidual
of
the
sw
arm
inherited
the
best
qualities
from
each
of
the
parents
(rooster
and
hen).
Moreo
v
er
,
we
inte
grate
the
constructi
v
e
phase
of
GRASP
using
multiple
threads,
this
operation
will
generate
10
solutions
by
using
10
threads
per
phase
which
could
reduce
the
run
time.
The
multi-groups
ap-
proach
lets
se
v
eral
groups
of
chick
ens
cooperate
to
find
good
solutions.
In
this
paper
,
we
consider
that
all
the
indi
viduals
sho
w
a
similar
beha
viour
,
we
can
adapt
the
same
approache
[53].
Ev
ery
chick
en
then
sends
its
solution
to
the
leader
of
the
group.
Algorithm
1
:
Pseudo-code
of
PHCSO
1.
Initialize
the
size
of
population
PS
2.
Generate
PS
using
constructi
v
e
procedure
of
GRASP
3.
Initialize
parameters:
PS,
G
,FL
,
C
and
W
.
4.
Ev
aluate
the
fitness
v
alues
for
each
chick
en
5.
Rank
and
establish
a
hierarchal
order
6.
Create
groups
7.
Assign
chicks
to
mother
-hens
8.
Update
the
equations
10
,11
and
12
9.
Impro
v
e
the
equation
10
by
2-e
xchange
neighborhood
mechanism
10.
Update
the
ne
w
solution
when
it
is
better
.
11.
Return
to
step
5
if
G
is
reatched
until
stop
criterion
12.
Post
process
results
The
e
xperimental
results,
discussion
and
comparison
among
PHCSO
and
some
other
metaheuristi
cs
will
be
detailed
in
the
ne
xt
section.
8.
EXPERIMENT
AL
RESUL
TS
AND
DISCUSSION
8.1.
Experimental
pr
otocol
The
ne
w
algorithm
PHCSO
is
programmed
using
p
ython
and
tested
on
dif
ferent
QAPLIB
i
nstances,
we
test
each
instance
20
times
in
100
iterations.
The
empirical
researc
h
w
as
implemented
on
a
DELL
in
visual
studio
2017
and
simulated
with
Intel(R)
Core(TM)
i7-6500
U
CPU
2.5GHZ
(4
CPUs)
2.6
GHz
and
16.00
GB
of
RAM
and
Microsoft
W
indo
ws
10
Professional
(64-bit)
operating
system.
Based
on
preliminary
e
xperiments
Figure
2a
sho
ws
that
PHCSO
can
achie
v
e
good
results
in
term
of
quality
of
solutions
for
chr12a
and
b
ur26a
when
the
population
size
is
fix
ed
on
500.
Figure
2b
presents
the
best
solution
found
in
term
of
quality
of
solution
and
a
v
erage
of
run
time
of
chr25a
when
the
iteration
G
is
equal
to
10.
The
parameter
G
allo
ws
the
redistib
ution
of
the
sw
arm,
whi
ch
pre
v
ents
to
get
caught
in
local
optimum.
Furthermore,
Figure
3a,
Figure
3b
and
Figure
3c
indicate
re
specti
v
ely
the
choice
of
parameters
W
,C
and
FL.
T
able
1
summarizes
the
parameters
v
alues
of
PHCSO
algorithm.
P
ar
allel
hybrid
c
hic
k
en
swarm
optimization...
(Soukaina
Cherif
Bourki
Semlali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2070
r
ISSN:
2088-8708
T
able
1.
The
P
arameters
for
the
PHCSO
Algorithm
P
arameters
of
PHCSO
V
alues
PS
:
Population
size
500
RN
:
Number
of
roosters
(
%
)
12
HN
:
Number
of
hens
(
%
)
25
CN
:
Number
of
chicks
(
%
)
63
G
:
Number
of
iterations
to
update
the
algorithm
10
W
:
Self-learning
f
actor
0.5
FL
:
Learning
f
actor
from
the
mother
hens
0.4
C
:
Learning
f
actor
from
the
rooster
0.65
T
able
2.
Numerical
Results
by
PHCSO
Applied
to
Some
Instances
of
QAPLIB
Instance
B
K
S
BFS
av
g
t
av
g
(
s
)
Er(
%
)
PSD
Suc(
%
)
b
ur26a.dat
5426670
5426670
542667
0
1,02
0
0
100
b
ur26b
.dat
3817852
3817852
3817852
0,78
0
0
100
b
ur26c.dat
5426795
5426795
54267
95
0,65
0
0
100
b
ur26d.dat
3821225
3821239
38
21239
0,8
0
0
100
b
ur26e.dat
5386879
5386879
5386
879
0,79
0
0
100
b
ur26f.dat
3782044
3782044
3782044
0,33
0
0
100
b
ur26g.dat
10117172
10117172
1
0117172
0,15
0
0
100
b
ur26h.dat
7098658
7098658
7
098658
0,29
0
0
100
chr12a.dat
9552
9552
9552
0,07
0
0
100
chr15a.dat
9896
10136
10136
0,96
0
0
100
chr15b
.dat
7990
7990
7990
0,77
0
0
100
chr18a.dat
11098
11098
11098
0,03
0
0
100
chr20c.dat
14142
14142
14142
0,4
0
0
100
chr25a.dat
3796
3816
3825,8
4,65
1,224152456
0,154648201
76
els19.dat
17212548
17212548
17212548
0,06
0
0
100
esc16a.dat
68
68
68
0
0
0
100
esc16b
.dat
292
292
292
0
0
0
100
esc16c.dat
160
160
160
0
0
0
100
esc16d.dat
16
16
16
0
0
0
100
esc32a.dat
130
130
130
0,01
0
0
100
esc32g.dat
6
6
6
0,01
0
0
100
esc32h.dat
438
438
438
0,03
0
0
100
esc64a.dat
116
116
118,4
0,09
0,845482754
0,963504299
86
had12.dat
1652
1652
1652
0,54
0
0
100
had14.dat
2724
2724
2724
0,46
0
0
100
had20.dat
6922
6922
6922
0,9
0
0
100
kra30a.dat
88900
88900
90670
0,21
0,456037779
0,155668723
70
kra30b
.dat
91420
91420
91950
1,91
0,124863438
0,475663245
45
tai12a.dat
224416
224416
224416
0
0
0
100
tai12b
.dat
39464925
39464925
39464925
0,02
0
0
100
tai15a.dat
388214
388214
388214
0,33
0
0
100
tai15b
.dat
51765268
51765268
51765268
0,07
0
0
100
tai17a.dat
491812
491812
491812
0,21
0
0
100
tai20a.dat
703482
703482
703482
0,12
0
0
100
tai20b
.dat
122455319
122455319
122452668,1
0,06
0,195103824
0,132581236
75
tai25a.dat
1167256
1167256
1167256
8,09
0
0
100
tai25b
.dat
344355646
344355646
344355646
1,12
0
0
100
tai30a.dat
1818146
1824318
1843220
8,44
0,673556331
0,211723256
0
tai30b
.dat
637117113
637117113
637817426
2,04
1,183859442
0,802901585
30
tai35a.dat
2422002
2428322
2450094
16,19
0,563779923
0,277992451
0
tai35b
.dat
283315445
283315445
284108340
10,54
1,137765617
1,225566683
70
tai40a.dat
3139370
3139370
3222045
17,15
0,627579935
0,376791525
60
tai40b
.dat
637250948
637250948
637409733
9,61
0,55632584
0,624665444
53
tai50a.dat
4938796
5090356
5094687
12,19
0,176659532
0,157465496
0
tai50b
.dat
458821517
458845260
461827312
37,61
1,344666884
1,133887455
0
tai60a.dat
7205962
7351256
7414373
59,87
0,837172335
0,966633885
0
tai60b
.dat
608215054
608351453
610225577
32,22
0,953344891
1,725866636
0
tai64c.dat
1855928
1855928
1855928
0,14
0
0
100
tai80a.dat
13499184
13657560
13791379
62,13
0,863398752
0,178666868
0
tai80b
.dat
818415043
819081613
830812584
21,1
1,237856678
0,533677254
0
tai100a.dat
21052466
21503812
216046216
86,13
0,136558896
0,256695228
0
tai100b
.dat
1185996137
1190142016
1187096921
96,15
0,127566983
0,245669879
0
sk
o42
15812
15812
15951
31,02
0,355624789
0,245666587
55
sk
o49
23386
24124
23564
78,96
0,765481242
0,987451666
0
sk
o81
90998
91113
91452
215.91
0,567741557
0,456884455
85
IJECE,
V
ol.
9,
No.
3,
June
2019
:
2064
–
2074
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
r
2071
(a)
(b)
Figure
2.
(a)
size
PS
of
chr12a,
(b)
G
for
chr12a
(a)
(b)
(c)
Figure
3.
(a)
W
for
b
ur26a,
(b)
C
for
b
ur26a,
(c)
FL
for
b
ur26a
8.2.
Computational
r
esults
The
qualit
y
of
the
obtained
solutions
sho
wn
in
T
able
3
by
PHCSO
is
e
v
aluated
using
dif
ferent
mea-
sures
which
are
the
Percentage
of
the
Standard
De
viation
P
S
D
(13)
and
the
percentage
of
error
E
r
(15).
The
ne
w
proposed
PHCSO
allo
ws
to
obtain
the
best-kno
wn
solution
about
72
%
from
all
tested
instances.
P
S
D
=
S
D
av
g
100
(13)
S
D
=
s
P
20
i
=1
(
S
best
av
g
)
2
20
(14)
E
r
=
(
av
g
B
K
S
)
B
K
S
100
(15)
where
BKS
is
the
best
kno
wn
solution,
S
best
is
the
best
found
v
alue
and
av
g
the
a
v
erage
of
the
best
found
solution.
Figure
4a
and
Figure
4b
sho
w
the
results
obtained
while
applying
PHCSO
algorithm
and
the
com-
parison
with
other
algorithms
from
the
literature
such
as
DB
A
[54]
and
BeA
[55].
The
e
xperiments
sho
w
that
PHCSO
algorithm
is
able
to
pro
vide
better
results
which
pro
v
e
that
combining
constructi
v
e
procedure
of
GRASP
and
T
ab
u
search
neighborhood
mechanism
in
the
equation
of
rooster
is
able
to
enhance
the
perfor
-
mance
of
our
algorithm.
P
ar
allel
hybrid
c
hic
k
en
swarm
optimization...
(Soukaina
Cherif
Bourki
Semlali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2072
r
ISSN:
2088-8708
(a)
(b)
Figure
4.
(a)
Comparati
v
e
A
v
erage
time
between
PHCSO
and
DB
A,
(b)Comparati
v
e
A
v
erage
time
between
PHCSO
and
BeA
8.3.
Discussion
of
r
esults
PHCSO
algorithm
sho
ws
good
performance
when
compared
to
other
state-of-the-art
algorithms
used
to
solv
e
the
Quadratic
Assignment
Problem.
As
result,
we
found
that
when
we
applied
nonparametric
W
ilcoxon
signed-rank
tests,
at
the
=
0
:
05
,
the
null
h
ypotheses
are
accepted
in
the
case
since
the
QAP
is
a
minimization
problem,
which
means
that
samples
in
all
groups
of
the
population
are
obtained
from
groups
with
the
same
mean
v
alue
.
W
e
observ
e
from
T
able
4
that
PHCSO
re
turns
better
solutions
than
BeA
[55],
HPSO
[56]
and
DB
A
[54]
and
the
p-v
alues
are
smaller
than
the
correspondi
n
g
Holm
step-do
wn
threshold,
which
signify
that
the
use
of
constructi
v
e
procedure
of
GRASP
and
T
ab
u
Search
greatly
impro
v
e
the
performance
of
PHCSO.
T
able
3.
W
ilcoxon
signed-rank
tests
(at
the
=
0.05
le
v
el),
with
the
Holm-Bonferroni
step-do
wn
procedure
used
to
control
the
f
amily-wise
error
rate
Comparison
Instances
p-v
alues
Holm
PHCSO
vs
HPSO
44
5E-23
0.023
PHCSO
vs
BeA
16
0.005
0.0119
PHCSO
vs
DB
A
18
3.726E05
0.013
9.
CONCLUDING
REMARKS
In
this
paper
,
a
ne
w
algorithm
called
P
arallel
Hybrid
Chick
en
Sw
arm
Optimization
PHCSO
w
as
pro-
posed
to
solv
e
the
quadratic
assignment
problem
by
suggesting
a
ne
w
modification
on
the
original
v
ersion
of
Chick
en
Sw
arm
Algorithm.
The
constructi
v
e
procedure
of
GRASP
w
as
inte
grated
in
order
to
obtain
a
better
initial
population
using
multiple
threads,
then
2-e
xchange
neighborhood
in
T
ab
u
search
incorporated
as
a
mu-
tation
operator
in
order
t
o
enhance
the
local
search
capability
.
The
sequentianl
constructi
v
e
crosso
v
er
(SCX)
and
the
uniform
crosso
v
er
(UX)
as
crosso
v
er
operators
were
used
to
impro
v
e
the
position
update
equation
of
indi
viduals
in
the
sw
arm.
The
computational
results
sho
w
that
PHCSO
algorithm
is
much
better
than
other
algorithms
in
terms
of
the
quality
of
the
solutions
and
the
computing
time.
Our
future
research
will
aim
to
apply
PHCSO
in
other
combinatorial
optimization
problems
as
JSSP
and
VRP
.
REFERENCES
[1]
Sla
w
omir
K
oziel
and
Xin-She
Y
ang.
Computational
optimization,
methods
and
algorithms
,
v
olume
356.
Springer
,
2011.
[2]
Emile
HL
Aart
s
and
Jan
Karel
Lenstra.
Local
sear
c
h
in
combinatorial
optimization
.
Princeton
Uni
v
ersity
Press,
1997.
[3]
Xin-She
Y
ang.
Natur
e-inspir
ed
metaheuristic
algorithms
.
Luni
v
er
press,
2010.
[4]
James
K
ennedy
.
Sw
arm
intelligence.
In
Handbook
of
natur
e-inspir
ed
and
inno
vative
computing
,
pages
187–219.
Springer
,
2006.
[5]
Christian
Blum
and
Xiaodong
Li.
Sw
arm
intelligence
in
optimization.
In
Swarm
Intellig
ence
,
pages
43–85.
Springer
,
2008.
[6]
Xin-She
Y
ang.
Engineering
optimizations
via
nature-ins
pired
virtual
bee
algorithms.
Artificial
Intelli-
g
ence
and
Knowledg
e
Engineering
Applications:
A
Bioinspir
ed
Appr
oac
h
,
pages
317–323,
2005.
IJECE,
V
ol.
9,
No.
3,
June
2019
:
2064
–
2074
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
r
2073
[7]
Jianfeng
Qiu,
Jiwen
W
ang,
Dan
Y
ang,
and
Juan
Xie.
A
comparison
of
impro
v
ed
artificial
bee
colon
y
algorithms
based
on
dif
ferential
e
v
olution.
Indonesian
J
ournal
of
Electrical
Engineering
and
Computer
Science
,
11(10):5579–5587,
2013.
[8]
Kang
Seok
Lee
and
Zong
W
oo
Geem.
A
ne
w
meta-heuristic
algorithm
for
cont
inuous
engineering
opti-
mization:
harmon
y
search
theory
and
practice.
Computer
methods
in
applied
mec
hanics
and
engineering
,
194(36):3902–3933,
2005.
[9]
Marco
Dorigo,
Mauro
Birattari,
and
Thomas
Stutzle.
Ant
colon
y
optimization.
IEEE
computational
intellig
ence
ma
gazine
,
1(4):28–39,
2006.
[10]
K
o-W
ei
Huang,
Abba
Sug
anda
Girsang,
and
Tjeng
W
a
w
an
Cenggoro.
F
ast
ant
colon
y
optimization
for
clustering.
Indonesian
J
ournal
of
Electrical
Engineering
and
Computer
Science
,
12(1),
2018.
[11]
Xin-She
Y
ang.
A
ne
w
metaheuristic
bat-inspired
algorithm.
Natur
e
inspir
ed
cooper
ative
str
ate
gies
for
optimization
(NICSO
2010)
,
pages
65–74,
2010.
[12]
James
K
ennedy
.
P
article
sw
arm
optimization.
In
Encyclopedia
of
mac
hine
learning
,
pages
760–766.
Springer
,
2011.
[13]
AH
Gandomi,
X-S
Y
ang,
S
T
alatahari
,
and
AH
Ala
vi.
Firefly
algorithm
with
chaos.
Communications
i
n
Nonlinear
Science
and
Numerical
Simulation
,
18(1):89–98,
2013.
[14]
Gai-Ge
W
ang,
Amir
H
Gandomi,
Xi
n
-
She
Y
ang,
and
Amir
H
Ala
vi.
A
ne
w
h
ybrid
method
based
on
krill
herd
and
cuck
oo
search
for
global
optimisation
tasks.
International
J
ournal
of
Bio-Inspir
ed
Computation
,
8(5):286–299,
2016.
[15]
Christos
H
P
apadimitriou
and
K
enneth
Steiglitz.
Combinatorial
optimi
zation:
algorithms
and
comple
xity
.
Courier
Corporation,
1998.
[16]
Tjalling
C
K
oopmans
and
Martin
Beckmann.
Assignment
problems
and
the
location
of
economic
acti
vi-
ties.
Econometrica:
journal
of
the
Econometric
Society
,
pages
53–76,
1957.
[17]
Se
w
all
Wright.
The
r
oles
of
mutation,
inbr
eeding
,
cr
ossbr
eeding
,
and
selection
in
e
volution
,
v
olume
1.
na,
1932.
[18]
V
Bachelet,
P
Preux,
and
EG
T
albi.
The
landscape
of
the
quadratic
assignment
problem
and
local
search
methods.
In
10th
Meeting
of
the
Eur
opean
Chapter
on
Combinatorial
Optimization
,
1997.
[19]
Peter
Merz.
Adv
anced
fitness
landscape
analysis
and
the
performance
of
memetic
algorithms.
Evolution-
ary
Computation
,
12(3):303–325,
2004.
[20]
El-Ghazali
T
albi.
Metaheuristics:
fr
om
design
to
implementation
,
v
olume
74.
John
W
ile
y
&
Sons,
2009.
[21]
Eric
D
T
aillard.
Comparison
of
iterati
v
e
searches
for
the
quadratic
assignment
problem.
Location
science
,
3(2):87–105,
1995.
[22]
Ra
vi
K
umar
Bhati
and
Akhtar
Rasool.
Quadrat
ic
assignment
problem
and
its
rele
v
ance
to
the
real
w
orld:
a
surv
e
y
.
International
J
ournal
of
Computer
Applications
,
96(9),
2014.
[23]
Eliane
Maria
Loiola,
Nair
Maria
Maia
de
Abreu,
P
aulo
Osw
aldo
Boa
v
entura-Netto,
Peter
Hahn,
and
T
ania
Querido.
A
surv
e
y
for
the
quadratic
assignment
problem.
Eur
opean
journal
of
oper
ational
r
esear
c
h
,
176(2):657–690,
2007.
[24]
Gerd
Fink
e,
Rainer
E
Burkard,
and
Franz
Rendl.
Quadratic
assignment
problems.
North-Holland
Math-
ematics
Studies
,
132:61–82,
1987.
[25]
Al
w
alid
N
Elshafei.
Hospital
layout
as
a
quadratic
assignment
problem.
J
ournal
of
the
Oper
ational
Resear
c
h
Society
,
28(1):167–179,
1977.
[26]
MA
Pollatschek,
N
Gershoni,
and
YT
Radday
.
Optimization
of
the
type
writer
k
e
yboard
by
simulation.
Ang
e
wandte
Informatik
,
17(0):438–439,
1976.
[27]
Bernhard
W
ess
and
Thomas
Zeitlhofer
.
On
the
phase
coupling
problem
between
data
memory
layout
generation
and
address
pointer
assignment.
Lectur
e
notes
in
computer
science
,
pages
152–166,
2004.
[28]
Mahdi
Bashiri
and
Hossein
Karimi.
Ef
fecti
v
e
heuristics
and
meta-heuristics
for
the
quadratic
assignment
problem
with
tuned
parameters
and
analytical
comparisons.
J
ournal
of
Industrial
Engineering
Interna-
tional
,
8(1):6,
2012.
[29]
V
ittorio
Maniezzo
and
Alberto
Colorni.
The
ant
system
applied
to
the
quadratic
assignment
problem.
IEEE
T
r
ansactions
on
knowledg
e
and
data
engineering
,
11(5):769–778,
1999.
[30]
Zvi
Drezner
.
A
ne
w
genetic
algorithm
for
the
quadratic
assignment
problem.
INFORMS
J
ournal
on
Computing
,
15(3):320–330,
2003.
[31]
V
an-Dat
Cung,
Thierry
Mautor
,
Philipe
Michelon,
and
Andr
´
ea
T
a
v
ares.
A
scatter
search
based
approach
for
the
quadratic
assignment
problem.
In
Evolutionary
Computation,
1997.,
IEEE
International
Confer
-
P
ar
allel
hybrid
c
hic
k
en
swarm
optimization...
(Soukaina
Cherif
Bourki
Semlali)
Evaluation Warning : The document was created with Spire.PDF for Python.