TELKOM
NIKA
, Vol.13, No
.1, March 2
0
1
5
, pp. 193~2
0
1
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i1.728
193
Re
cei
v
ed O
c
t
ober 1
0
, 201
4; Revi
se
d Ja
nuary 14, 20
1
5
; Acce
pted Janua
ry 3
0
, 20
15
Data Partition and Communication on Parallel Heuristik
Model Based on Clonal Selection Algorithm
A
y
i Purbasa
ri*
1
, Iping Su
priana Su
w
a
rdi
2
, Oerip Santo
s
o
2
, Rila Mandala
2
1
Informatics Engin
eeri
ng, Pas
und
an U
n
ivers
i
t
y
2
School of Elec
trical Eng
i
ne
eri
ng an
d Info
rma
tics, Bandun
g Institute of T
e
chno
log
y
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: pbasar
i@u
n
p
a
s.ac.id,
ipi
n
g
@
informatik
a
.o
rg,
oerip
@infor
matika.org,
rila@informatik
a
.org
A
b
st
r
a
ct
T
h
is
rese
arch cond
ucted exp
e
ri
ments on po
pul
ati
on-
bas
ed
heur
istic p
a
ral
l
e
l a
l
gor
ith
m
s, w
h
ich ar
e
inspir
ed
by th
e clo
n
a
l
se
lec
t
ion, cal
l
e
d
Cl
ona
l Se
lectio
n
Algor
ith
m
(C
SA). Course-
g
rain
ed
para
lle
li
s
m
mo
de
l app
lie
d
to improv
e executi
on ti
me. Inter-proce
ss commu
n
ic
a
t
ion over
he
ad
is address
e
d
by
adj
usting c
o
mmu
n
ic
ation fre
que
ncies
an
d
si
z
e
of
data
communic
a
te
d. Experi
m
e
n
t
s
on six p
a
ra
llel
computi
ng
mo
dels re
pres
ent
all p
o
ssib
l
e p
a
rtitions
a
nd c
o
mmunic
a
tio
n
s
and us
in
g dat
a of NP-Prob
l
em,
T
r
avelin
g Sal
e
sma
n
Probl
e
m
(T
SP). T
he algorit
hm
is i
m
ple
m
ented us
i
ng mod
e
l of mess
ag
e pass
i
ng
librar
i
es MPJE
xpress a
nd ra
n in
a cluster
computat
i
on
e
n
viro
nment. R
e
sult sh
ow
s the best p
a
ral
l
e
l
i
s
m
mo
de
l is
achi
e
v
ed by
partiti
o
n
in
g i
n
itia
l p
o
p
u
lati
on
dat
a
at
the b
egi
nni
ng
of co
mmun
icati
on a
nd t
he
en
d of
gen
eratio
n. C
o
mmu
n
icati
o
n
frequ
ency c
an
b
e
up
to p
e
r 1
%
of a
po
pu
la
tion si
z
e
g
e
n
e
r
a
ted. Usi
n
g
fo
ur
dataset fro
m
T
SPLib, ex
per
i
m
e
n
ts show
th
e effect
of co
mmu
n
icati
on fr
equ
ency th
at i
n
creas
ed
best
cost,
from 4
4
.16
%
to 87.0
1
% for
berli
n5
2.tsp; from
9.61
% to
53.43
% for kr
oA10
0.tsp, an
d from
12.2
2
%
to
17.18
% for tsp
225.tsp. W
i
th
eig
h
t proc
esso
rs, using
co
mmu
n
ic
ation
fre
que
ncy w
ill
be
reduc
ed
exec
uti
o
n
time e.g 9
3
.07
%
, 91.60%, 8
9
.60%, 74.7
4
%
for burma
1
4
.tsp, berlin
52.
tsp, kroA100.tsp, and tsp22
5.tsp
respectiv
e
ly.
W
e
conc
lud
e
t
hat freq
ue
ncy
of co
mmu
n
icati
on greatly
affe
cts
executi
o
n
ti
me, an
d also
best
cost. It impr
ove
d
executi
on ti
me and b
e
st cost.
Ke
y
w
ords
:
cl
ona
l sel
e
ctio
n
alg
o
rith
m, par
alle
l cl
ona
l se
l
e
ction
al
gorith
m
, p
a
ral
l
el
he
uristic
mo
del,
dat
a
partitio
n
, coar
se-grai
n
e
d
co
mmu
n
icati
on,
travel
i
ng s
a
le
sma
n
pr
obl
e
m
,
mess
age
passi
ng i
n
terf
ace,
MPJExpress
1. Introduc
tion
CSA (Clon
a
l
Selection
Alg
o
rithm) is on
e of
the pop
u
l
ation-b
a
sed heuri
s
tic
search algo
-
rithms. T
h
is
algorithm has been
able
to solve
com
b
inatori
a
l problems [1],[2], from
classical
problem the
Traveling Sales
m
an
Problem (TSP) [2],[3] to partic
u
lar optimiz
ation problems
in
Iterative Lea
rning Control (ILC) [4]. CSA is part
of t
he Artificial I
mmune Syst
em (AIS), a
bio-
inspi
r
ed
com
puting approach to solve comp
lex problem
s [5],[6]. This approach, like ot
her
popul
ation ap
proa
ch
es, re
quire
s
significant amou
nt
of computatio
n
time. Many idea
s attempt
to
address this
probl
em by adopting pa
ra
ll
el comp
utatio
n para
d
igm. As the initiators, Wat
ski
n [7] is
not sp
ecifi
c
t
o
the
CSA a
nd ap
plied
to
pattern
re
co
gnition p
r
o
b
le
ms. Hong
bin
g
et al. [8] a
pply
the CSA
para
llelism fo
r
pro
t
ein structu
r
e
pre
d
ic
tio
n
u
s
ing O
pen
-MP
I. Dabrowski
and Ko
bale
[9]
usin
g the parallel-CSA co
mputation for
grap
h col
o
rin
g
probl
em.
In this research, parallel computing model
s will be
developed to exploit the a
v
ailabl
e
parall
e
lism
p
o
tential o
n
th
e cl
onal
sele
ction an
d
CSA. In ad
dition t
o
con
s
ide
r
ing
the
cha
r
a
c
te
ris-
tics po
sse
s
se
d by the immune sy
stem o
n
the clon
al
selectio
n even
ts, model
s bu
ilt refers to th
e
prin
ciple
s
an
d con
c
ept
s of parallel
computation
d
e
sig
n
, taking
into acco
un
t many aspe
cts:
partitionin
g
, communi
catio
n
, agglome
r
at
ions, an
d ma
pping [10]
Based
on
the
pri
n
cipl
e of
communi
catio
n
, there a
r
e
two
gro
u
p
s
of mod
e
ls of
computa
-
tion, the ma
ster-slave m
o
d
e
l with
a p
r
o
c
essor a
c
ts
as a commu
nications control
l
er, an
d oth
e
rs
acting a
s
sl
a
v
e pro
c
e
sso
rs are govern
ed by t
he main pro
c
e
s
so
r/maste
r
. Oth
e
r computati
onal
model i
s
cal
l
ed multi-co
mmuni
cation
model
or
coa
r
se-grai
n
e
d
communi
cation, wh
ere
all
pro
c
e
s
sors communi
cate
with ea
ch oth
e
r witho
u
t
an
y centrali
zed
control proce
s
sor [11],[10].For
a pop
ulation
that has
be
en set, the multi-co
mmu
nicatio
n
mod
e
l sh
ows b
e
tter computati
o
n
spe
ed. Howe
ver, this h
a
s
yet to be sh
o
w
ed th
e lin
ka
ge bet
wee
n
computing
sp
e
ed pe
rform
a
n
c
e
and CSA’
s param
eters, i.e. population
size, num
be
r of the sele
ction, and the amount of data
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 193 – 2
0
1
194
comm
uni
cate
d bet
wee
n
th
e whole
p
r
o
c
esse
s. On
th
e othe
r
han
d, one
of th
e
other drawba
cks i
s
the nee
d fo
r inter-p
r
o
c
e
s
sor
comm
u
n
icatio
n. We
need to
minimize the
effect of this
comm
uni
cati
on overh
ead.
This research will
be fo
cused
to search for
pa
tterns of relations bet
ween parameters of
CSA an
d its
relation
s with
parall
e
l
comp
utation. Th
e
para
m
eters i
n
vestigate
d
a
r
e: si
ze
of init
ial
popul
ation (whether p
a
rtiti
oned o
r
not
),
size of po
pu
lation data th
at is comm
u
n
icate
d
between
pro
c
e
s
ses,
a
nd
their relati
ons with com
putational
re
sults (b
est
co
st and
execu
t
ion time). Th
is
study al
so
make
s o
b
servations on t
he comm
uni
cation frequ
e
n
cie
s
on
mu
lti-comm
uni
cation
model
s. The
model
s are
implemente
d
on pa
rall
e
l
comp
uting
with multicore a
nd
clu
s
ter
environ
ment usin
g
MPJEx
p
re
ss (Java Messag
e
Pa
ssi
ng Mo
del).
MPJExpre
ss is a library that
impleme
n
ted
with Messa
ge Passing
Interface (M
PI’s) spe
c
ification libra
ry [12]. MPI could
sup
port pa
rall
elizin
g popul
a
t
ion based al
gorithm, such
us gen
etic al
gorithm [13].
The
study fo
cuse
s
on th
e a
s
pe
cts that m
u
st b
e
con
s
id
ered
in th
e lib
rary
appli
c
ati
on, the
resulting com
putational mo
dels, a
s
well
as the re
sults of the comp
utation itself. Systematicall
y
,
this pa
per
co
ntains: Intro
d
u
ction, Th
e P
r
opo
se
d
Met
hod/Algo
rith
m, Resea
r
ch
Method
s, Re
sults
and Di
scu
ssi
on, and Con
c
lusio
n
.
2.
The Propos
e
d
Method/
Al
gorithm
2.1. Parallel
Clonal Selection Algorithm
Clon
al Select
ion Algorithm
(CSA) is a
n
algor
ith
m
tha
t
inspire
d
by the immune
system,
esp
e
ci
ally on
the clo
nal
selectio
n even
ts [9
]. Clonal
sele
ction i
s
an event in t
he immu
ne re-
spo
n
se, whe
r
eby an attack of antigen, B-cell
s a
s
anti
body-p
ro
du
cing cell
s woul
d be multiplie
d if
its re
cepto
r
s
match
with the antigen
s’ re
cepto
r
.
Cell
s
that do not h
a
ve match
ed
recepto
r
do n
o
t
partici
pate in
the sele
ction.
The match
calc
ul
ation is
known as affini
ty maturation.
CSA is part
of Bio-Inspi
r
ed Algo
rith
m family called Artificial Immune Syst
em (AIS)
[2],[14],[1]. C
SA maps ant
ibodies
(an i
mmune
com
ponent) as
a popul
ation i
n
tended to be a
solu
-tion, wh
erea
s antig
e
n
mappe
d as an issue
(probl
em). In mappin
g
the
problem
with a
solutio
n
ba
se
d on the inspiration of i
mmune
sy
st
em, there is an activity
calle
d as im
mune
engin
eeri
ng [6] [3].
In the TSP proble
m
; immune resp
on
se re
prese
n
ts a solution whe
r
e
a
s
antigen
rep
r
e
s
ent
s the p
r
o
b
lem; in this
ca
se i
s
a col
l
ection
of no
de/city wh
ere
the sal
e
sm
a
n
must visit, the B-cell
s (a
ntibody)
represents a tour th
at is form
ed [
3
]. Details ab
out the CSA can
be found in [2
] and the prin
ciple
s
of this
parall
e
l algo
ri
thm desig
n can be seen in
[10].
Usi
ng multi
c
ommuni
catio
n
model,
whi
c
h all
pro
c
e
s
se
s commu
ni
cate
with ea
ch oth
e
r
without a
n
y
maste
r
control, we th
en d
e
fined p
opul
a
t
ion data
part
i
tion. Refe
rrin
g
to the
beha
vior
of the im
mun
e
sy
stem
and
clo
nal
sel
e
cti
on, the
r
e
are
two id
ea
s, e.
g. initial p
opu
lation g
ene
rat
e
d
by single p
r
ocesso
r, an
d each pro
c
e
s
sor
ind
e
pend
ently generating ini
t
ial populati
on..
Comm
uni
cati
on between
pro
c
e
s
sors is done after
cl
on
al sel
e
cti
on ope
ration,
i.e. selectio
n -
cloni
ng
- hyp
e
rmutatio
n - random
repla
c
ement. Th
e
b
e
st p
opul
ation in e
a
ch p
r
o
c
e
s
sor th
en
sent
to all processors.
2.2. Parallel
Clonal Selection Algorithm for TSP
To apply the
clonal sele
ction algo
rithm
into the optimization p
r
ob
lem, in this case the
TSP pro
b
lem
,
we
nee
d m
appin
g
b
e
twe
en p
r
obl
em
and
a
clon
al
sel
e
ctio
n al
gorithm
sch
e
me.
This me
cha
n
i
sm i
s
calle
d
immun
e
e
n
g
inee
ring. In
immun
e
e
n
g
inee
ring, th
ere
are two
main
activities th
at must be con
s
id
ere
d
, namel
y representat
ion and af
finity maturation.
Rep
r
e
s
entati
on is a p
r
o
b
l
e
m that ma
p
ped into
p
o
p
u
lation
s in th
e immun
e
system, which i
s
the
expecte
d optimal individua
l tour TSP. T
he affini
ty maturation i
s
cost cal
c
ulatio
n betwee
n
th
e
proximity of
a tour in
each po
pul
ation
with the
exp
e
cted
be
st solution. Here'
s
a
n
ove
r
vie
w
of
immune e
ngi
neeri
ng in Ta
ble 1.
3. Res
earc
h
Method
This stu
d
y is
experim
ental,
sta
r
ted
with t
he
con
s
tructi
on of
co
mput
ational m
odel
s, which
are then impl
emented
by utilizing MP
JExpress libra
ry in parallel
computing environments such
as multicore and cl
uste
r. Re
sea
r
ch
me
thod ca
n be seen in the Fig
u
re 1.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Data Partition and Com
m
unication on Parallel
He
urist
i
k Model Based on .... (Ayi Purbasari
)
195
Table 1. Imm
une en
ginee
ri
ng
Clonal Selection
Processes
TSP Problem
Population initialization
Set of randoml
y
generated
tour.
T
her
e ar
e (n
-1)
!
p
o
ssibilities that th
e tours ma
y be r
a
ised.
This population is part of the
whole tours. The
num
ber of tou
r
s is generated b
y
the
specified population size.
Affinity
evaluatio
n
Evaluation of affi
nity
checks each tour that h
a
s raised,
find the cost required to fo
rm t
he
tour.
Selection: affinity
maturation
Affinity
is ho
w
clo
s
e the cost of a tour
w
i
th the o
p
timal/best cost. The closer, the higher
affinity
and
w
ill be selected.
Cloning
Cloning is process to cop
y
selected tour
, num
ber of
copies are depe
nds on clone factor:
H
y
pe
rmutation
Cloned/copied to
ur
w
ill be mutate
d according to h
y
permutation p
r
ob
ability
mutat
e
factor:
Edit r
e
ceptor
/elisitation
After
mutate,
we
w
ill have the best
tour
s-
that
w
ill be r
eplacedthe
w
o
rst tour
s in the initial
population.The n
u
mber
w
o
rst tour repl
aced
w
ill be depends on som
e
random size
replacement d.
Stop condition
Clonal selection
process w
ill be repeat
ed until a st
op condition obta
i
ned. Stopping criteria
could be the num
ber of gen
eration
s
, or number
s of
populations (tour
s) are evaluated,
or
best cost found.
Processing element
communications
Exchange best t
ours produced
b
y
each of the
pro
c
essing element
s to other pr
ocessing
elements.
Here the de
scriptio
n abo
ut rese
arch
met
hod that used
in this re
sea
r
ch:
Figure 1. Re
seach method
The
pro
b
lem
s
a
r
e
goi
ng t
o
have
immu
ne e
ngin
eere
d
; whi
c
h
a
r
e
rep
r
e
s
entatio
n an
d af
-
finity maturation.The
r
e a
r
e parallel
clo
nal sele
ction
algorith
m
ca
lled cl
onal
selectio
n in
spi
r
ed
parall
e
l alg
o
ri
thm (CSI-PA
)
that ha
s several
paramet
ers that ha
s
been
set. Pa
ramete
rs of the
clon
al sel
e
cti
on co
nsi
s
ts
o
f
the populati
on si
ze
(N), the num
ber
of sele
ct
ion (n), the numbe
r
of
gene
ration
s (g), a
nd th
e
n
u
mbe
r
of
no
d
e
s
(n
on) fro
m
TSP Pro
b
le
m. The
s
e
alg
o
rithm
s
a
r
e
e
x
e-
cuted i
n
pa
ra
llel execution
environ
ment,
e.g mu
ltico
r
e and
clu
s
ter comp
uter. T
here
are several
pro
c
e
s
ing ele
m
ents
to pro
c
e
ss.T
h
e
s
e
e
x
ecution
s
w
ill
re
sult solust
ion, e.g. the
best tou
r
with
their be
st co
st and time for execution. T
hese
algo
rith
ms are imple
m
ented u
s
in
g
single
pro
g
ram
multiple d
a
ta
mod
e
l, u
s
in
g me
ssage
passin
g
inte
rface
stan
da
rd (MPI) an
d
libray
nam
ed
MPJExpre
s
u
s
ing
Java
Progra
mming
l
angu
age. T
h
e algo
rithm
s
will be
exe
c
u
t
ed u
s
ing
so
me
variant of data partition an
d comm
uni
ca
tion freque
ncy.
Experiment
s con
d
u
c
ted on
multicore a
n
d
clu
s
ter envi
r
onm
ent with
a headno
de
and 16
comp
ute no
d
e
s. Eight
co
mpute no
de
s use
d
in th
e
s
e experi
m
ent
s with th
eir
specifi
c
ation:
16 x
2.90G
Hz CP
Us sto
r
ag
e o
f
895.46
5GB
in RAID5
con
f
iguration. Th
e
he
ad-nod
e is
u
s
in
g CPUs
32x2.90G
Hz, 126.1
3
GB
memory, l
o
cal di
sk 8
95.
4
65GB
and
Li
nux 2.6.32
-2
79. Th
e
com
pute-
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 193 – 2
0
1
196
node
s are usi
ng CPUs 16x
2.70G
Hz, 15.
66GB memo
ry, local disk 1
42.835
GB an
d Linux 2.6.32-
279. Software environm
e
n
ts are u
s
in
g Java Me
ssag
e Passin
g Model, MPJExpre
ss t
hat
develop
ed u
s
ing the I
D
E Netbean
7.2.1
with Java 1.7
.
0_13 ve
rsi
o
n
.
Entirely run
on
Windo
ws
7
Operating System v6.1.
To execute it,
compile
d sim
u
lation exe
c
u
t
ion can b
e
seen in Tabl
e 2 as follo
ws:
Table 2. Experime
n
ts sce
nario
Dataset Name
Burma14, Be
rlin52, KroA100, tsp
225
Kno
w
n Best Cost
from TSPLib [
16
] 3.323,7.542,
21.2
82,3.916
Number of
Node
14, 52, 100, 2
2
5
Number of
Gen
e
r
ation
100,000
Parameter
Value
N, initial population
50
n, number o
f
selection
10
Size of population data communicated
Number of
partiti
on- N
Clone factor
β
0.1
Mutate factor
δ
2.5
Number of
proce
ssor
2, 4, 8
Processing Envir
onment
Multicore, Cluster
Some pa
ram
e
ter valu
es
h
a
ve bee
n d
e
fined, such a
s
the value
of
the initial p
o
p
u
lation,
the numbe
r o
f
selection, cl
one facto
r
, and mutate
factor. Initial po
pulation pa
rtition wa
s don
e
in
Figure 2 as fo
llows:
Figure 2. Population pa
rtition
De
scription:
Numb
er of pa
rtition = num
b
e
r of pro
c
e
ssors
(np
)
Population
si
ze in 1
s
t, 2nd
… (np
-
1)th P
a
rtition (p
p) = N/np
np
th
Numb
er
of Population
in Partition (p
p) =
N – (np*
pp)
Example: N = 50, np = 4. Numbe
r
of part
i
tion
= 4, Population si
ze in
1st, 2nd , 3rd partition =
12, popul
atio
n size in 4th partition = 1
4
.
Experiment
overview
ca
n be re
sum
ed in
Figure
3. Thus we
have six model
s for
experim
ent. We d
o
several execution
s
for ea
ch
experim
ent, an
d then g
e
t the avera
ge
re
sult
from e
a
ch ex
-pe
r
iment
to report
in
se
cti
on
Re
sult a
n
d
Di
scu
ssi
on.
After that,
we will
che
c
k t
h
e
effect of com
m
unication freque
ncy to e
x
ecution time
result an
d the best cost o
b
tained.
Figure 3. Experime
n
t scen
ario
s
Init
ial
Pop
u
lation
Si
ng
le
Po
pulatio
n
Mult
iple
Po
pulatio
n
Us
ing
Partition
Withou
t
Partition
Be
st Po
pulatio
n -
eac
h
Ge
n
e
rat
i
o
n
Using
Partition
Wi
thout
Partition
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Data Partition and Com
m
unication on Parallel
He
urist
i
k Model Based on .... (Ayi Purbasari
)
197
4.
Resul
t
and Discussion
Based
on the
above sce
n
a
r
io, co
ndu
cte
d
experim
ent
s on
clu
s
ter
e
n
vironm
ent with four
datasets, e.g.
, burm
a14.tsp
,
berlin
52.tsp,
kroA10
0.tsp,
and t
s
p2
25.tsp. Re
sult
s log
ged from m
a
i
n
pro
c
e
s
sor
(p
roce
ss 0
)
. Fo
r the six m
o
d
e
ls,
we o
b
served effect
s o
f
the num
ber of gen
eratio
ns
and the freq
uen
cy of co
mmuni
cation
on the best
cost an
d the executio
n time. We do
with
100.00
0 num
ber of ge
nera
t
ion. There a
r
e two re
sult
e
x
perime
n
ts, first re
sult
will sho
w
the effe
ct
of partition a
n
d
the se
co
nd
one is th
e effect of commu
nicatio
n
freq
u
ency to exe
-
cution time an
d
best cost obt
ained. Detail of the result w
ill be presen
ted in the followin
g
se
ction
.
4.1.
Result I
The first exp
e
rime
nt wa
s t
o
ob
serve
th
e six mo
dels
in term
s of th
e numb
e
r
of gene
ra-
tions, be
st co
st, and execution time. Table 3 bel
o
w
sho
w
s the result
s for the
six experime
n
ts
based
on
we
ight an
d exe
c
ution
time.
Experiment
s about execution
time
are summ
ari
z
ed
in
Table 4 bel
o
w
.
Table 3. Best
cost for all d
a
taset
Number
of Node
Number
of
Process
Best Cost
Model 1
Model 2
Model 3
Model 4
Model 5
Model 6
14
2
3.394
3.359
3.323
3.394
3.359
3.323
4
3.371
3.323
3.323
3.371
3.323
3.323
8
3.403
3.336
3.336
3.323
3.438
3.413
Average
3.389
3.339
3.327
3.363
3.373
3.353
52
2
17.079
19.226
17.573
17.079
19.226
17.573
4
20.028
20.341
20.325
20.028
20.341
20.325
8
19.353
20.124
19.070
20.856
19.437
19.453
Average
18.820
19.897
18.989
19.321
19.668
19.117
100
2
109.807
124.267
124.241
110.579
114.163
113.407
4
108.539
122.320
122.265
116.127
113.717
121.420
8
127.794
125.157
121.283
119.702
116.325
121.233
Average
115.380
123.915
122.596
115.469
114.735
118.687
225
2
32.309
34.333
32.283
33.411
33.543
34.193
4
34.440
32.047
33.814
33.344
33.883
33.913
8
34.321
33.392
33.823
32.281
34.556
33.731
Average
33.690
33.257
33.307
33.012
33.994
33.946
Table 4. Execution time for all dataset
Number
of Node
Number
of
Process
Execution Time
Model 1
Model 2
Model 3
Model 4
Model 5
Model 6
15
2
71.039
65.484
55.213
64.205
72.257
60.230
4
105.511
96.915
102.549
93.889
102.149
92.042
8
186.131
203.690
180.388
186.855
174.511
179.612
Average
120.894
122.030
112.717
114.983
116.306
110.628
52
2
186.928
156.777
202.463
181.735
168.952
210.396
4
298.612
340.347
340.399
291.097
316.998
349.252
8
347.178
456.233
477.473
435.925
464.344
459.695
Average
277.573
317.786
340.112
302.919
316.765
339.781
100
2
382.329
412.065
395.405
396.022
380.500
378.781
4
584.470
684.217
664.053
674.349
671.874
667.572
8
572.945
855.017
845.576
864.971
849.929
872.740
Average
513.248
650.433
635.011
645.114
634.101
639.698
225
2
1.441.560
1.400.791
1.393.369
1.430.928
1.408.072
1.535.162
4
1.854.656
1.908.771
1.975.035
1.912.938
1.952.451
1.876.631
8
1.649.006
2.430.180
2.456.985
2.404.307
2.436.130
2.381.234
Average
1.648.407
1.913.247
1.941.796
1.916.058
1.932.218
1.931.009
As we
can
see, each mo
dels g
a
in thei
r be
st
co
st di
fferently for e
a
ch d
a
taset a
nd num-
ber of
processing elem
ent
s.
Fo
r
data
s
e
t
burma
14 th
at has num
b
e
r
of
node
=
14, the b
e
st
co
st
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 193 – 2
0
1
198
wa
s obtain
e
d
by several m
odel
s, with 2
and 4 n
u
mb
e
r
of pro
c
e
s
sin
g
eleme
n
ts. T
heir b
e
st
co
sts
are
33
23
whi
c
h i
s
same
a
s
b
e
st
kno
w
n be
st
co
st f
r
om
TSPLib
for b
u
rm
a14.t
s
p
data
s
et.
But
increa
sing
nu
mber
of nod
e
made diffe
re
nt result
s,
a
s
we can se
e model
n
u
mbe
r
1
gai
ned be
tter
best
co
st fo
r data
s
et b
e
rli
n52,
kroA
10
0, and
ts
p
2
2
5
with
2
nu
mber of p
r
o
c
essing
elem
e
n
ts,
clo
s
e to mod
e
l numbe
r 2 with 4 numb
e
r
of proc
essin
g
element. Ta
ble above sh
ows that num
ber
of processing
eleme
n
ts ha
s n
o
di
re
ct i
m
pact
for
be
st cost
obtain
ed fo
r all
dat
aset. It b
e
ca
use
,
best cost
s o
b
tained a
r
e
more d
epe
nd
on.cloni
ng a
nd hypermut
a
tion mecha
n
ism that re
sult
rand
om tou
r
.
Tabel
4 sho
w
s expe
rime
nt re
sults fo
r e
x
ecution tim
e
. If we u
s
e m
o
re
pro
c
e
s
sin
g
element, then
we will need
more time to exec
ute. The
r
e are commu
nicatio
n
overhead
s betwe
en
pro
c
e
ssi
ng el
ements. Exce
pt model
1, that if we use 8 numbe
r of pro
c
e
ssi
ng el
ements, we will
have better e
x
ecution time
than if we use 4 num
b
e
r
of processin
g
elem
ents. Averagely, mo
del
numbe
r 1 ha
s better execut
ion time
than others for all
datasets.
4.2. Result II
In this
experi
m
ent, we
carried
out
som
e
re
du
ction
s
of the fre
que
ncy of
com
m
unication
betwe
en p
r
o
c
essors. Th
e
ultimate goal
is to g
e
t the
executio
n time a
s
po
ssib
le, but doe
s
not
redu
ce
the
qu
ality of the fin
a
l result, i.e. best
co
st. Ta
ble 5
sho
w
s
summary
of th
e be
st
co
st af
ter
we controll
ed
the commu
ni
cation fre
que
ncy.
Table 5. Best
cost for all d
a
taset after
controlle
d co
m
m
unication freque
ncy
Number of
Node
Number of P
r
oce
s
s
Execution Time
after controlled C
o
mm. Fre
quenc
y
Model 1
Model 2
Model 3
Model 4
Model 5
Model 6
14
2
13.965
13.876
13.101
12.822
13.064
14.593
4
13.695
13.488
14.166
14.059
15.296
15.936
8
12.905
16.469
15.904
13.848
17.521
17.213
Average
13.522
14.611
14.390
13.576
15.294
15.914
52
2
48.347
49.279
48.468
47.233
51.105
47.659
4
48.690
54.209
52.884
51.390
55.027
52.415
8
39.501
55.954
53.954
36.604
55.549
53.125
Average
45.513
53.147
51.769
45.076
53.894
51.066
100
2
118.584
119.178
122.385
116.806
118.913
118.218
4
116.400
117.955
122.642
123.459
121.134
121.325
8
90.327
124.685
125.294
89.993
122.733
127.565
Average
108.437
120.606
123.440
110.086
120.927
122.369
225
2
788.580
786.276
782.141
789.671
793.007
787.424
4
777.486
798.155
787.218
790.475
794.047
781.497
8
620.036
794.198
803.693
607.228
797.229
793.964
Average
728.701
792.876
791.017
729.125
794.761
787.628
Table 6 sho
w
s the be
st executio
n times after we cont
rolled
comm
u
n
icatio
n frequ
ency.
Table 6. Execution for all d
a
taset
after
controlle
d co
m
m
unication freque
ncy
.
Number of
Process
Best Cost after c
ontrolled Comm.
Freque
nc
y
Model 1
Model 2
Model 3
Model 4
Model 5
Model 6
14
2
3.371
3.323
3.394
3.359
3.359
3.346
4
3.323
3.336
3.388
3.323
3.369
3.336
8
3.323
3.336
3.323
3.323
3.371
3.336
Average
3.339
3.332
3.368
3.335
3.366
3.339
52
2
13.887
13.938
12.437
12.896
13.026
13.289
4
9.034
12.988
12.904
8.735
12.888
13.795
8
9.303
12.399
12.582
8.668
10.997
11.892
Average
10.741
13.108
12.641
10.100
12.304
12.992
100
2
49.952
55.588
54.893
62.895
58.913
53.916
4
39.830
47.974
52.386
41.524
44.997
47.142
8
46.211
43.555
46.905
46.971
51.436
43.100
Average
45.331
49.039
51.395
50.463
51.782
48.053
225
2
24.384
24.646
25.364
25.231
25.456
25.911
4
22.793
23.861
24.283
23.146
24.474
24.621
8
23.811
23.661
23.978
23.856
23.725
23.557
Average
23.663
24.056
24.542
24.078
24.552
24.696
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Data Partition and Com
m
unication on Parallel
He
urist
i
k Model Based on .... (Ayi Purbasari
)
199
After
we co
n
t
rolled com
m
unication
fre-quen
cy, we
gaine
d exe
c
u
t
ion times
12
.822ms
(M4; np2
), 36.604m
s (M4
;
np2), 89.9
93ms
(M
4; n
p8), and 6
0
7
.228m
s (M4
;
np8) for b
u
r-
ma14.tsp, be
rlin52.tsp, kro
A
100.tsp an
d
tsp225.tsp
re
spe
c
tively. Compa
r
e to Ta
ble 4 above, the
executio
n time red
u
ctio
ns
are 9
3
.07%, 91.60%
, 89.
60%, 74.74%
respe
c
tively. The averag
e
executio
n time sho
w
s that Model 1
gai
n
ed the be
st execution time
.
We
ca
n
see t
hat controll
ed
frequ
en
cy greatly affects the exe
c
ut
ion
time,
and also
the best co
st.
It improved e
x
ecution time
and also be
st cost.
4.3. Result III
This
se
ct
ion
sho
w
s comp
aris
on
t
h
e re
sult
f
r
om
se
ction 4.2
with
a
nother ap
pro
a
ch
from
anothe
r rese
arche
r
. Since
anothe
r research
s u
s
in
g
different ca
se a
nd different parallel
pro
-
grammi
ng
en
vironme
n
t, we ne
ed to
do
re
-create
d
a
l
gorithm
and
prog
ram
an
d
apply it to t
he
same
case, TSP probl
em
, with some
assumptio
n
.
Since m
odel
1, with
singl
e
popul
ation a
nd
partition
sh
o
w
s th
e b
e
st
result, we
cho
o
se it
and
co
mpare to al
g
o
rithm from [
8
]. Figure
4
de-
scriri
be p
a
rall
el com
puting
model from
Hongbi
ng,
u
s
in
g ring
comm
unci
a
tion; co
mpare to mo
del
1 from se
ctio
n 4.2, using
mesh
comm
u
n
icatio
n, can
be sh
own in Figure 5 belo
w
:
Figure 4. Single-p
opul
atio
n with ring
co
mmuni
cation
Figure 5. Single-p
opul
atio
n with mesh communi
catio
n
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 193 – 2
0
1
200
Figure 6 sho
w
s
be
st co
st comp
ari
s
o
n
for all d
a
taset with num
ber
of pro
c
e
ssi
ng
elemen
t
2, 4, and 8 and Fig
u
re 7
sho
w
execu
t
ion time
co
mpari
s
o
n
for all dataset
with num
ber of
pro
c
e
ssi
ng el
ement 2,
4, and 8.
As
we
can se
e,
from b
e
st
co
st
, there
are
some
differen
c
e
s
results from
each data
s
et. But over all, result fr
om rese
arche
r
ga
in better be
st cost than ot
he
r
resea
r
cher. F
r
om exe
c
utio
n time point
of view,
re
sul
t
from re
sea
r
che
r
gai
n si
g
n
ificant imp
r
o
v
e-
ment than re
sult from other rese
arch
er. We con
c
lud
e
that our app
roaced lea
d
to better re
sult.
Figure 6. Best cost co
mpa
r
ison for all d
a
t
aset
with several nu
mbe
r
of processin
g
element
Figure 7. Execution time compa
r
ison for all datas
et wi
th several n
u
m
ber of p
r
ocessing el
eme
n
t
5. Conclu
sion
Experiment result
s sho
w
t
hat
all
the
m
odel
s,
produ
ce
be
st wei
g
ht relatively
clo
s
e to
kno
w
n
-
be
st-cost fo
r b
u
rm
a14
data
s
et. Ho
weve
r, fo
r oth
e
r data
s
et nee
d m
o
re ge
ne
ration
to
obtain
be
st
know result. Before
an
d aft
e
r
co
ntrolle
d
comm
uni
cati
on frequ
en
cy, there
a
r
e
some
model
s that
obtaine
d 10
0
%
kno
w
n
be
st cost e.
g:M
odel 2
wih
n
p
=4
(M2;
np
4),M4; np
8,M
5
;
np4,M6; np
2
np4,M1; np
4
np8,M2; np
2,M3; np8,M4;
np4
n
p8. The
executio
n time sig
n
ifica
n
t
ly
2
4 8
2
4
8
2 4
8
52
100
225
Ho
ng
bi
ng
17
.
079
16
.
304
10
.
662
10
9.
807
11
3
.
618
37
.
438
32
.
309
33
.
293
22.
325
Re
s
e
arch
er
11
.
960
9
.
6
5
1
8
.
357
52.
22
2
4
0
.
8
4
9
5
2
.
068
25
.
079
23
.
337
24.
097
-
20.
0
0
0
40.
0
0
0
60.
0
0
0
80.
0
0
0
100.
000
120.
000
Be
st
Co
s
t
Bes
t
Co
s
t
Co
m
p
a
r
i
s
o
n
fo
r
Nu
mb
er
of
No
de
52,
100,
225
wit
h
Nu
mber
of
Pr
ocess
i
ng
Elemen
t
=
2,
4,
8
2
4
8 2 4
8
2 4 8
52
1
0
0
22
5
H
o
ngb
i
ng
4
3
1
.
891
6
2
5
.
0
4
8
774.
74
7
820.
68
5
1
.
0
4
6
.
232
1
.
098
.0
0
1
2.
728.
1
5
1
3
.
0
7
7
.
894
3
.
1
6
1.
612
Re
s
e
ar
che
r
49.
41
3
52.5
1
5
3
8
.
7
0
8
121.
47
4
1
2
0
.
451
99.0
9
0
803.
73
9
790.
40
2
6
3
6
.5
58
-
50
0
1
.
000
1
.
500
2
.
000
2
.
500
3
.
000
3
.
500
Exe
c
u
t
io
n
Ti
m
e
(
s
ec
ond)
Ex
e
c
ution
Tim
e
Comp
a
r
ison
fo
r
Nu
m
b
e
r
of
Node
52,
1
00,
22
5
wi
t
h
Number
of
Pr
ocessing
Eleme
n
t
=
2,
4,
8
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Data Partition and Com
m
unication on Parallel
He
urist
i
k Model Based on .... (Ayi Purbasari
)
201
differs for ea
ch mo
del, in
creases with
th
e nu
mbe
r
of
gene
r-ation
s
and th
e n
u
m
ber of p
r
o
c
e
s
sors
use
d
. It app
e
a
rs that th
e a
m
ount of
processing
affe
ct
s the exe
c
utio
n time b
u
t do
es
not affe
ct the
best
co
st. Freque
ncy of
communi
catio
n
gre
a
tly a
ffects the
execution time, a
nd al
so the
best
co
st. It impro
v
ed executio
n time an
d b
e
st
co
st. Co
mmuni
cation
freque
ncy
ca
n be
up to
pe
r 1%
of a
pop
ulatio
n si
ze
g
ene
ra
ted. Using
fo
ur
data
s
et fro
m
TSPLib,
experim
ents sh
ow th
e
effect
of
comm
uni
cati
on fre
que
ncy
that in
cre
a
sed b
e
st
co
st, from
44.16
% to 87.01%
for
berli
n52.
tsp;
from 9.6
1
% to 53.43%
for kroA100.t
s
p,
and f
r
om
12
.22% to 17.1
8
% for tsp22
5.tsp. With
ei
ght
pro
c
e
s
sors,
usin
g comm
unication fre
quen
cy w
ill
be redu
ce
d
executio
n time e.g
93.0
7
%,
91.60%, 8
9
.60%, 74.7
4
%
for
burma14.tsp,
b
e
rlin5
2
.tsp,
kroA
100.tsp, and
tsp22
5.tsp
r
e
spec
tively.
We
con
c
lu
de
that with
six
model
s, to o
b
tain
be
st
co
st the b
e
st m
odel i
s
M1,
e
.
g singl
e
popul
ation wit
h
partition in initial populati
on and it
s be
st populatio
n; and to obtain best executi
o
n
time, the best
model i
s
M4,
e.g sin
g
le po
pulation
with
partition at th
e end of g
e
n
e
ration. F
o
r t
he
averag
e exe
c
ution time
we
ca
n
see
Mod
e
l 1
gaine
d th
e be
st
co
st a
nd the
exe
c
ut
ion time. T
h
e
s
e
con
d
ition
s
are best if the
commu
nication freq
uen
cy
is co
ntrolle
d
.
After comp
are to an
oth
e
r
approa
ch fro
m
anoth
e
r
re
sea
r
che
r
, fro
m
execution
time point of
view, re
sult
from researcher
gain sig
n
ificant improve
-
ment than result fr
om o
t
her re
se
archer. We
co
nclu
de that our
approa
ced le
ad to better result
Referen
ces
[1]
Kulturel-Konak, S Ulutas BH
.
A Rev
i
e
w
of
Clon
a
l
Sel
e
ctio
n Al
gorithm
an
d Its App
licati
o
ns.
Artificial
Intelli
genc
e Re
view
. 2011; 36
(2): 117-1
38.
[2]
De Castro
LN
, Von Z
F
.
Learni
ng a
nd O
p
timi
zati
on Usi
ng the C
l
o
nal
Selectio
n Pri
n
cipl
e.
IEEE
T
r
ansactio
n
s On Evoluti
o
n
a
ry Co
mp
utation
. 2
002; 6(3): 2
39-
251.
[3]
Gaber J, Bakhou
ya M. An
Immune Insp
ired-b
a
se
d Op
timizatio
n
Alg
o
rithm: Appl
ic
ation to the
T
r
aveling Sal
e
sman Prob
lem.
AMO - Advanced Mod
e
li
ng a
nd Opti
mi
z
a
ti
o
n
. 2007; 9(
1): 105-1
16.
[4]
Qun G, Xiao
H
H
, Xian
JD, W
e
i T
X
, Yua
n
y
u
an J. C
l
on
al S
e
lecti
on A
l
gor
ithm Base
d Iter
a
tive L
ear
nin
g
Contro
l
w
i
t
h
R
and
om D
i
sturb
ance.
T
E
LKO
M
NIKA Indo
ne
sian J
our
nal
of
Electrical
En
gi
neer
ing
. 20
13;
11(1): 44
3-4
4
7
.
[5]
Alshar
han S,
JR Al-Enez
i, Abbo
d MF
. Artifi
cial Immun
e
S
y
stems
–
Models, Al
g
o
rithms an
d
Appl
icatio
ns.
Internati
o
n
a
l Jo
urna
l of R
e
se
arch a
nd
Revi
ew
s in Ap
pli
e
d Scie
nce (IJ
RRAS)
. 20
10
;
1(1): 118-
13
1.
[6]
T
i
mmis J, De Castro LN.
Arti
ficial Immun
e
S
y
stems: A Ne
w
C
o
mp
utation
a
l Appr
oac
h. 2002.
[7]
Watkins A, Bi X
,
Phadke
A.
Parall
eli
z
i
n
g an I
m
mun
e
-
Inspirin
g Al
go
rithm for Effic
i
ent Patter
n
Reco
gniti
on
. I
n
Intell
ig
ent
Engi
neer
in
g
S
y
stems thr
o
ugh Artific
i
al
Neur
al
Net
w
o
r
ks: Smart
Engi
neer
in
g. 2003: 22
5-2
30.
[8]
Hon
gbi
ng
Z
,
Siche
ng
C, Ji
an
guo
W
.
Paral
l
e
lin
g
Clo
na
l S
e
lecti
on A
l
g
o
rit
h
m w
i
th Ope
n
M
P
. In 3rd
Internatio
na
l C
onfere
n
ce o
n
Intelli
ge
nt Net
w
or
ks and Inte
lli
gent S
y
stems (I
CINIS). Shenya
ng. 20
10
;
1: 463 - 46
6.
[9]
Dabr
o
w
ski J,
Kuba
le M.
Co
mp
uter Exp
e
ri
me
nts w
i
th a Parall
el C
l
o
nal
Selecti
on Al
g
o
rith
m for th
e
Graph Col
o
ri
n
g
Probl
em
. In IEEE Internationa
l S
y
m
posi
u
m on Parall
el
and Distri
bute
d
Processi
ng.
Miami. F
l
orid
a. 2008: 1-6.
[10]
Ian F
.
Designi
n
g
and Bu
il
din
g
Parall
el Pro
g
ra
ms
. 19
95. [Onli
ne]. http://
w
ww.mcs.anl.gov/~
i
tf/dbpp/
[11]
Blais
e
.
Introducti
on
to Paral
l
e
l
Co
mp
uting
. 2
012.
[Onlin
e].
https://computing.llnl.gov
/tutorials/parallel_comp
[12]
Baker M, C
a
rp
enter B, S
hafi
A.
MPJ Expres
s: towards thread s
a
fe Jav
a
HPC
. In IEEE
Internationa
l
Confer
ence on
Cluster
Com
p
uting. 20
06:1-
1
0
.
[13]
Z
hang
JJ, Li
u
W
J
, Liu GY. P
a
rall
el Ge
netic
Algorit
hm Bas
e
d on
the MPI E
n
viro
nment.
TEL
K
OMNIKA
Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2012; 1
0
(7): 1
708-
171
5.
[14]
Bro
w
nl
ee J.
Clon
a
l S
e
lecti
on Alg
o
rithms.
Compl
e
x Intelli
ge
nt Systems L
abor
atory
,
Centre for
Information T
e
chno
logy
Res
earch, F
a
cu
lty of In
formati
o
n Co
mmu
n
ic
ation T
e
c
hno
lo
g
y
, Sw
inburn
e
Univers
i
ty of Techn
o
lo
gy, Mel
bour
ne, Austral
i
a
. 200
9.
[15]
T
SPLIB.
[Online]. http://
w
w
w
.
i
w
r
.
u
n
i-h
e
i
del
be
rg.de/gro
ups
/c
omopt/soft
w
ar
e/T
SPLIB95/tsp/
Evaluation Warning : The document was created with Spire.PDF for Python.