TELKOM
NIKA
, Vol.14, No
.1, March 2
0
1
6
, pp. 342~3
4
8
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v14i1.3169
342
Re
cei
v
ed O
c
t
ober 3
0
, 201
5; Revi
se
d Ja
nuar
y 5, 201
6
;
Accepte
d
Ja
nuary 24, 20
1
6
A New Method Used for Traveling salesman problem
Based on Discrete Artificial Bee Colony Algorithm
Lei Meng
1
, Shoulin Yin*
2
, Xin
y
uan
Hu
3
Soft
w
a
re Co
lle
ge, Shen
ya
n
g
Normal U
n
iv
ersit
y
,
No.25
3
, Hua
n
g
H
e Bei Street, Hua
ngGu Distr
ict, Shen
yan
g
, P.C 1100
34 -
Chin
a
*Corres
p
o
ndi
n
g
author, em
ail
:
88713
46
@qq
.
com
1
, 35272
0
214
@qq.com
2
,
1138
07
491
6
@
qq.com
3
A
b
st
r
a
ct
W
e
prop
ose a
new
met
hod
b
a
sed
on d
i
scre
t
e Artificial B
e
e
Colo
ny a
l
gor
ithm (
D
ABC) for
travelin
g
sales
m
an
prob
le
m. W
e
re
def
ine t
he s
earch
ing strat
egy a
nd
tra
n
sfor
min
g
mech
an
is
m of
le
adi
ng be
e
s
,
follow
i
n
g
bees
and scout be
es accord
ing t
o
discrete va
ri
abl
es. T
he transitio
n of sw
arm rol
e
is base
d
o
n
ratios factor
o
f
definiti
on.
Le
adi
ng
bees
us
e 2-Opt
o
per
a
t
or and
le
arn
i
ng o
per
ator to
accel
e
rate th
e
conver
genc
e s
pee
d
and
to s
earch
the
ne
ig
hbor
hoo
d.
T
h
e
searc
h
in
g of follow
i
n
g
bees
intro
duc
es
ta
b
u
table to i
m
pr
ov
e the loca
l refi
ne
me
nt
abil
i
ty of the alg
o
rith
m. Scouts b
e
e
s
define a
n
ex
clusive
oper
ati
on to
ma
inta
in the d
i
versity of pop
u
l
atio
n,
so it is better to bal
an
ce the expl
or
at
ion a
nd ex
plo
i
tation a
b
il
ity of the
alg
o
rith
m. F
i
n
a
lly, the
exp
e
ri
me
ntal
r
e
su
lts show
that th
e
new
al
gorit
h
m
c
an fi
nd r
e
l
a
tively s
a
tisfac
tory
soluti
on in
a sh
ort time, an
d i
m
pr
ove the effi
ciency of solv
in
g the traveli
ng
sales
m
an pro
b
l
e
m.
Ke
y
w
ords
:
DA
BC alg
o
rith
m, T
abu tabl
e, T
r
avelin
g sal
e
s
m
a
n
prob
le
m, Exclusive
oper
atio
n, 2-Opt operat
or
Copy
right
©
2016 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Travelin
g sa
lesma
n
prob
lem (it is abbr
eviated
in TSP) [1] is an important
combi
nation
a
l
optimization
probl
em in th
e are
a
of mat
hematics. It belong
s to No
n-Determi
n
ist
i
c
Polynomial
(NP)
p
r
o
b
lem [2].
Although there are so
me
preci
s
e al
gorithm
s whi
c
h can
be used
to
solve th
e p
r
oblem, the
prin
ciple
of
pre
c
ise al
go
rithms is co
mplex, and
it can
produ
ce
“co
m
bin
a
tion
explosi
on p
r
o
b
lem” alon
g
with the
in
cre
a
se
num
ber
of city, theref
ore, the
do
m
e
stic
and foreign
schol
ars have
been tryin
g
to see
k
a hi
gh
ly efficient an
d stable
algo
rithm for solvi
n
g
this co
mplex probl
em.
Artificial be
es colo
ny alg
o
ri
thm (ABC) [3]
is
o
ne
of heu
ristic sear
ch
algorith
m
s ba
sed
on
swarm intelli
gen
ce, whi
c
h
was
pro
p
o
s
ed by Kara
b
oga et al. [4] in 2005. ABC algo
rithm [
5
] is
based on th
e self-organi
zation
of the swarm
si
mu
lation mod
e
l
with the adv
antage
s of l
e
ss
setting
para
m
eters, stron
g
ro
bu
st
ne
ss, it has
re
cei
v
ed extensiv
e
attention
of schola
r
s b
o
th at
home an
d ab
road, an
d be
en appli
ed in
many fields.
No
wad
a
ys,
many resea
r
che
r
s h
a
ve
studie
d
the
new alg
o
rith
m ab
out Arti
ficial b
e
e
s
colo
ny for TS
P. Sharma P
et al. [6] sho
w
ed th
at bee
s spe
c
ulative
modified ove
r
time and b
a
sed
on the be
st solution foun
d
by the bee itself and th
e swarm
s
of be
es were dyna
mically divide
d
into
small
e
r grou
ps and search
p
r
o
c
e
s
s
was
p
e
rfo
r
med by an i
ndep
ende
nt smalle
r g
r
ou
p of
bee
s. Ho
ng
-T
ao et al. [7] p
r
opo
se
d a
discrete
ar
tifici
al
bee
col
ony a
l
gorithm. An
d
he introdu
ce
d
a tabu list an
d a repul
sio
n
operator.
The ab
ove method
s alm
o
st are use
d
for
solvin
g
continu
o
u
s
domain opti
m
ization
probl
em
s. Howeve
r, ABC algorithm i
s
relatively
few u
s
ed in th
e asp
e
ct of
discrete
dom
ain
appli
c
ation.
To improve the perfo
rma
n
ce of TS
P
solution, we pro
pose i
m
prove
d
discrete
Artificial Bee Colo
ny algorit
hm throu
gh redefin
in
g lea
d
ing bee
s, followin
g
bee
s a
nd scout
s whi
c
h
better co
ordi
nates
an
d b
a
lan
c
e
s
the
exploratio
n a
nd mi
ning
proce
s
s of
ABC al
go
rithm. T
o
facilitate
the descri
p
tion,
t
h
is paper also
give
s
som
e
definitions.
We
present
a new di
screte
Artificial Bee
Colo
ny algo
ri
thm for traveling sa
le
sma
n
probl
em. Thi
s
new sch
e
me
take
s b
a
lan
c
e
of spa
c
e exp
l
oration a
nd the local refinement in
to
con
s
id
eratio
n
.
Finally, we condu
ct so
me
experim
ents
to verify its
perfo
rman
ce.
The re
su
lts
sho
w
that the new alg
o
rit
h
m has a g
o
od
effect on solvi
ng TSP quest
i
on.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A New Meth
o
d
Used for T
r
aveli
ng salesm
an problem
Based o
n
Di
screte A
r
tificial
… (Lei Me
ng)
343
2. Artifici
al Bee
s
Colon
y
Alg
o
rithm and
Discre
t
izatio
n
Optimizatio
n
pro
c
e
ss of a
r
tificial col
o
n
y
algorithm simulate
s th
e behavio
r of bees
sea
r
ching
a h
i
gh qu
ality ne
ctar
so
urce. It divides
artificial bee
col
ony
into leadi
ng
bee
s, followi
n
g
bee
s an
d scouts a
c
co
rdi
ng to thei
r
di
vision of
la
b
o
r.
They ch
a
nge role
s
b
a
s
ed on ce
rta
i
n
con
d
ition
s
. E
a
ch
be
e i
s
a
po
ssi
ble
sol
u
tion of
corresp
ondi
ng
problem,
profit
ability ratio
s
of
necta
r
sou
r
ce re
presents the q
uality
of the
so
lutio
n
. Each
lea
d
i
ng b
ee i
s
co
rre
sp
ondi
ng t
o
a
certai
n ne
ctar sou
r
ce, and i
n
the pro
c
e
ss of iter
ation it start
s
to sea
r
ch am
ong its
neigh
borhoo
d.
After sea
r
chi
ng, leadin
g
bee
s wo
uld
sha
r
e t
he se
arched info
rmation with the followi
ng bee.
Followi
ng be
es choo
se n
e
ctar
sou
r
ce
accord
i
ng to certai
n probability, and they keep
on
sea
r
ching in t
heir n
e
ighb
orhood. If leadi
ng bee
s
with
in a given nu
mber of
sea
r
ching do
n’t accep
t
better nectar
source, they will gi
ve up this nectar
so
urce and leading bees
would be transform
e
d
into scouts to
rando
mly se
arch feasi
b
le
new n
e
cta
r
source.
ABC algo
rith
m is an intelli
gent optimi
z
a
t
ion algo
rithm
,
and explora
t
ion and p
r
od
uction
is two m
a
in f
a
ctors,
whi
c
h
de
cide
s to
t
he p
e
rf
o
r
man
c
e of swa
r
m
intelligen
ce
o
p
timization;
the
better explo
r
i
ng ability an
d the strong
er sea
r
ch
i
n
g
ability for individual in gl
obally se
arch
ing
unkno
wn are
a
. What this amount
s is to
, global opt
imization capa
b
ility is strong
er, the exploiting
ability is bett
e
r. The
abilit
y of i
ndividual searching
optimal solu
ti
on in local area i
s
st
ronger
,
ability of loca
l refinem
ent i
n
better. T
h
e
r
efor, to
ensu
r
e the
sol
u
tio
n
quality of A
B
C algo
rithm,
i
t
need
s to coo
r
dinate a
nd b
a
lan
c
e the exploratio
n
and
mining pro
c
ess, whi
c
h is a core p
r
obl
em
in
intelligent
algorith
m
. When
solving
the p
r
obl
em o
f
contin
uou
s
variable
s
, AB
C alg
o
rithm
l
a
cks
con
s
id
eratio
n
of the exploration a
nd e
x
ploitation
ab
ility. That is
difficult to guarante
e
solving
spe
ed an
d qu
ality of algorithm. Here are
four definition
s
for di
scretization ABC.
Profitability ratio
i
r
: the ratio
betwe
en
sea
r
che
d
ne
ctar
source n
e
cta
r
amount
s of e
a
ch
bee
i
fit
and n
e
ct
ar
sou
r
ce ne
ctar amo
unts
of optimum in
dividual in
swam
best
fit
. For TSP, the
relation of
i
fit
and obje
c
tive function
)
(
i
X
f
is
:
)
(
1
i
i
X
f
fit
(1)
Similarity
j
i
s
,
: level of similarit
y
of any two solutio
n
vect
ors
i
X
and
j
X
,
N
M
s
j
i
/
,
.
Whe
r
e
N
is
the numb
e
r
of cities
and
M
is the
sa
me adja
c
e
n
t side
numb
e
r
of two
sol
u
tion
v
e
ct
or
s.
]
1
,
0
[
,
j
i
s
. For example,
N=10, X
1
=[1,5,6,2,4,8,3,10,7,9
]
and X
2
=[1,3,
6,2,4,8,10,5,7
,
9].
The t
w
o
sol
u
tion ve
ctors
h
a
ve five
sam
e
adj
acent
s
i
des
: [6 2], [2 4], [4 8], [7
9], [9 1], So
j
i
s
,
=0.
5
.
Exclusive op
eration: ra
nd
omly arra
nge
same
adja
c
e
n
t side of two
solution vect
ors a
n
d
get a new ve
ctor Y. And it acts Y on
j
X
, which d
e
crea
ses
j
i
s
,
.
Learning op
e
r
ation: ran
d
o
m
ly arran
ge same
a
d
ja
ce
nt side of two solution ve
ctors and
get a new ve
ctor Y. And it acts Y on
j
X
,
which in
cr
ea
se
s
j
i
s
,
.
3. Discre
t
e
Arti
ficial Bee
Co
lon
y
algorithm for TSP
Acco
rdi
ng to
the above definitions, we
divi
de artificial bee col
o
n
y
into leading bee
s,
followin
g
bee
s and sco
u
ts acco
rdi
ng to their
divisio
n
of labor. They chan
ge
role
s ba
sed
on
certai
n co
ndit
i
ons. Each b
ee is a po
ssi
ble soluti
o
n
o
f
correspondi
ng pro
b
lem, profitability ra
tios
of necta
r sou
r
ce re
presents the quality of
the solution.
We redefine t
he three b
e
e
s
.
3.1. Impro
v
e
d
Leading Bees
The leadi
ng bee
s in the discrete ABC algorithm h
a
ve the sam
e
function a
s
ABC
algorith
m
. It s
earche
s
an o
p
timal necta
r sou
r
ce
in the neighbo
rho
o
d
of each ne
ctar source.
But
it is a discrete variable
probl
em for
solv
ing TSP,
generation
mech
ani
sm
of neighb
orh
ood
solutio
n
ne
ed
s to be
re
def
ined. So the
detailed
pro
c
e
s
ses
of im
proved l
eadi
ng be
es
are
as
follows. Firstl
y, this paper
adopt
s 2-o
p
t neigh
borhoo
d
stru
cture to
sea
r
ch neig
h
borh
ood of e
a
ch
necta
r
so
urce
at the
be
gin
n
ing
of o
p
timization.
Wh
en
operatin
g 2-opt nei
ghb
orhood, se
co
nd
ly it
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 14, No. 1, March 2
016 : 342 – 3
4
8
344
remove
s two
non
-adj
ace
n
t
edge
s, an
d
then re-ope
rates
co
rre
sp
ondin
g
fou
r
cities on
the t
w
o
non-adja
c
e
n
t edge
s: first
city of first
si
de i
s
lin
k
ed
t
ogethe
r with the
first city of
se
co
nd si
de,
se
con
d
city of first sid
e
is li
nke
d
togethe
r with
the seco
nd city of se
cond
si
de. Th
e
n
it obtains th
e
new
solutio
n
as the the nei
ghbo
rho
od so
lution.
Example 1
.
There is a
5-note TSP, so
lution is
]
5
,
4
,
3
,
2
,
1
[
i
X
as
Figure1(a), a
nd we
operate
side
(1,2) an
d (4,5
) ba
se
d o
n
2
-
opt an
d g
e
t n
e
ighb
orh
ood
solutio
n
]
5
,
2
,
3
,
4
,
1
[
i
X
as
Figure 1(b
)
.
Figure 1. 2-o
p
t neighb
orh
o
od ope
ration
Comp
ari
ng
i
X
with
i
X
, the re
al ope
ration
of 2-opt i
s
that
it
inv
e
rt
s t
he se
con
d
cit
y
of
firs
t s
i
de as
t
he the firs
t c
i
t
y
of s
e
c
o
nd s
i
de.
3.2. Impro
v
e
d
Follo
w
i
ng
Bees
The follo
wing
bee
s in the
discrete
ABC alg
o
rithm
have the
sa
me fun
c
tion
as AB
C
algorith
m
. It cal
c
ulate
s
th
e proba
bility based o
n
the
roul
ette met
hod a
nd fo
rm
ula (2) to
cho
o
se
one ne
ctar
so
urce and it st
arts to condu
ct local
sea
r
ching.
SN
i
i
i
i
fit
fit
p
1
(2)
SN
is th
e total numb
e
r
of necta
r
sou
r
ce. The imp
r
o
v
ed followi
ng
bee
s in the
discret
e
ABC alg
o
rit
h
m introdu
ce Tab
u
tabl
e
)
2
,
1
(
SN
i
tabu
i
into re
cord
neig
hbo
rhoo
d
sea
r
ching
inf
o
rmatio
n of
b
ees ne
are
s
t
necta
r
sou
r
ce. For exam
ple, the
nea
rest n
e
igh
borhood
solut
i
o
n
i
X
of n
e
ctar sou
r
ce
i
X
in exam
ple 2
is o
b
taine
d
b
y
conve
r
ting
city 2 an
d
city 4. If we
again
ma
ke
2
-
opt tran
sformation fo
r
sid
e
(2,5) and
si
de
(1,4) in
thi
s
two
cities re
spe
c
tively, an
d it
will get neig
h
borh
ood
solu
tion
i
X
which is meaningl
ess. In order
to
avoid the be
es repeate
d
sea
r
ching
wit
h
in the
sam
e
neigh
borhoo
d and i
m
pr
ove the p
r
od
uction ability of algorith
m
, for
Tabu
table
i
tabu
i
n
exampl
e 2,
it just
nee
d
s
to
re
co
rd
(2,4) t
w
o
poin
t
s, nam
ely re
cord the
se
con
d
city of first side a
n
d
first cit of second si
de.
3.3.
Impro
v
e
d
Scouts
The scout
s a
r
e tran
sforme
d by leading
bee
s
and ha
ve the resp
o
n
sibl
e for finding the
individual
with possibility falling into a
local optim
u
m
and up
dat
ing it. That can
redu
ce t
h
e
prob
ability of
pre
c
o
c
ity. Leading be
es a
r
e tran
sfor
me
d into sco
uts,
which
satisfi
e
s the followi
ng
con
d
ition
s
: it doe
s not
obta
i
n better ne
ct
ar
sou
r
ce
within the
settin
g
searchi
ng n
u
mbe
r
. As
we
all
kno
w
, there a
r
e thre
e que
stions amo
ng
scouts
shift mech
ani
sm a
nd se
archin
g behavio
r in ABC
algorith
m
.
a.
The ch
angi
n
g
role of scouts de
pen
d
s
on the gi
ven sea
r
chin
g numbe
r. This
para
m
eter i
s
different for solving different pra
c
tical
probl
em
s an
d difficult to
set. Also sett
ing
unsuitable parameters
will affect the abil
i
ty of
algorithm to jump out of local opti
m
al.
b.
Scouts a
r
e transfo
rme
d
o
n
ly after in
dividual
cha
ngin
g
into p
r
e
c
o
c
i
t
y and it expl
ore
s
new n
e
cta
r
source
s, whi
c
h
leads to sl
ow
spee
d to find the global op
timal solution.
c.
Scouts
rand
o
m
ly search n
e
w ne
ctar so
ur
ces in ABC algorithm wit
hout con
s
id
ering
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A New Meth
o
d
Used for T
r
aveli
ng salesm
an problem
Based o
n
Di
screte A
r
tificial
… (Lei Me
ng)
345
positio
n of current domi
n
ant sea
r
chin
g leadin
g
be
es. It cann
ot guarantee t
hat scout
s search
more n
e
w n
e
c
tar
sou
r
ces i
n
global
scop
e. Finally,
this restrain
s exp
l
oring a
b
ility of the algorith
m
.
In order to
solve the above shortcomi
ngs,
thi
s
paper defines the profitability ratios,
leadin
g
bee
s are tra
n
sfo
r
m
ed into scout
s ba
sed
on t
he index. Th
e advantage
of this definition,
on the
one
h
and, is that the ind
e
x is m
o
re li
kely
to b
e
set
wh
en
solving differe
nt pro
b
lem
s
.
On
the other h
a
n
d
, swa
r
m role
and se
arch
mech
ani
sm
relies o
n
the d
y
namic
cha
n
g
ing of se
arching
numbe
r. At t
he o
p
timizin
g
initial
stag
e, the p
r
ofitabil
i
ty ratios
is relatively poo
r, leadin
g
b
e
e
s
immediately t
u
rn
into
scout
s. And
it op
erates
ex
clu
s
iv
e op
eration
b
a
se
d o
n
roul
ette metho
d
,
so
that it can fin
d
better n
e
ct
ar sou
r
ces i
n
global
sc
op
e. In the late
optimizatio
n, the profitabil
i
ty
ratios
are al
l good, l
eadi
ng be
es no
longe
r tu
rn
into sco
u
ts.
The
se
arch
mechani
sm
is
transfo
rme
d
from 2
-
opt to
learni
ng o
p
e
ration
ba
se
d on roulette
method. Na
mely, we sh
ould
adeq
uately consi
der the i
ndividual spe
c
ie
s divers
ity at the initial stage to improve explo
r
i
ng
ability of ABC al
gorithm.
At the end of
optimizat
ion,
population informat
ion sharing should
be
taken into a
c
cou
n
t to improve the prod
u
c
tion
ability a
nd optimization sp
eed of
ABC algorith
m
.
The detaile
d pro
c
e
ss of th
e prop
osed A
B
C algo
rithm is as follo
ws:
a.
Step 1. Initializin
g the
swarm.
Ran
dom
ly
initiali
zing nectar sources, namely
randomly generating popul
ation init
ial
solution, and calcul
ating prof
itability ratios of each nect
ar
sou
r
ce by formula (1
).
b.
Step
2.
T
h
e
se
archi
ng stage of leadi
ng bee
s. Ca
lculatin
g prof
itability ratios. If
profitability ra
tios are gre
a
ter than
o
r
eq
ual to the set
t
ing value
r
, then lea
d
ing
bee
s execute
2-
opt ope
ratio
n
, sea
r
ch n
e
w n
e
cta
r
source
s a
nd
get ca
ndid
a
te neig
hbo
rh
ood
solutio
n
i
X
.
Otherwise, leading be
es a
dopt roul
ette method ba
se
d on pro
babili
ty calculated
by formula (2
) to
cho
o
s
e
ne
ct
a
r
so
ur
ce
i
X
, execute le
arnin
g
ope
ration a
nd se
arch n
e
w
ne
ctar
sou
r
ce
s a
nd get
can
d
idate nei
ghbo
rho
od so
lution
i
X
. If candidate
profitability ratios
i
X
fit
is gre
a
ter than
i
X
fit
.
i
X
will replace
i
X
.
c.
Step 3. The
sea
r
ching
stage of follo
wing b
e
e
s
. Followi
ng be
es ad
opt ro
ulette
method b
a
se
d on proba
bi
lity calculate
d
by
formula
(2) to choo
se ne
cta
r
so
urce
i
X
. And it
execute
s
2-o
p
t ope
ration
within th
e pe
rmissi
bl
e ope
rating scope, sea
r
ch
a
ne
w
ne
ctar so
urces
and get a ca
ndidate n
e
igh
borh
ood
solut
i
on
i
X
. If candidate profitabil
i
ty ratios
i
X
fit
is
gr
e
a
t
er
than
i
X
fit
.
i
X
will replace
i
X
.
d.
Step 4. The
searching
stage of scouts.
Ca
l
c
ulating
profitability ratios. If profitability
ratios a
r
e
gre
a
ter th
an
or e
qual to
the
setting value
r. r
i
s
a
setting value.
T
h
en
it g
i
ves
up
th
e
necta
r source
i
X
whose profitability
ratios is less than
r
. It adopts roulette meth
od ba
sed o
n
probability calculated by formula(
2) to choose nectar source
i
X
, execute
s
lea
r
nin
g
operation
and search
es new
ne
ctar source
s
i
X
. Othe
rwi
s
e return t
o
step5.
e.
Step 5. Reco
rding the
searche
d
be
st sol
u
tion.
f.
Step 6. Whether the
proc
ess satisfies
termination c
onditions or
not. If YES,
then
finish. If NO, return ba
ck st
ep2.
4. Experiments
and Res
u
lts
4.1. The Effect of Profitab
ilit
y
Ratios Setting Value on DABC
The setting value
r
of profitability rat
i
os i
s
the
m
a
in param
e
ter in
Discrete ABC
algorith
m
(DA
B
C).
We m
a
ke sim
u
lation
experim
ents t
o
analy
z
e th
e
effect of
r
o
n
pe
rform
a
n
c
es
of algo
rithm
solutio
n
un
de
r the
MATLA
B
platform.
We
ado
pt different
r
to co
n
duct experi
m
ents
unde
r the oth
e
r sa
me pa
ra
meters co
ndit
i
ons. Setting maximum iterations
2000
max
T
, number
of bees i
s
48
m
, algorith
m
run
s
20 times i
ndep
ende
ntly. Table1 re
cord
s the re
sults with
different
r
(
r
is a setting val
ue).
From T
able
1 we
ca
n kn
ow that
whe
n
r
g
r
ad
ually
redu
ce
s a
b
o
u
t solutio
n
time, the
averag
e
runn
ing time i
s
little-chan
ged.
Whe
n
r=0.7, 0.8,
0.9
, average
run
n
ing
time is relativel
y
s
h
ort. And
r=
0.8
, avera
ge
runni
ng time
i
s
9.0
341
whi
c
h i
s
th
e
sho
r
test time. But
as a
whol
e, the
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 14, No. 1, March 2
016 : 342 – 3
4
8
346
averag
e
runn
ing time
of al
gorithm
ha
s
a little c
han
g
e
. This is mai
n
ly be
cau
s
e
whateve
r
val
ue
r
is,
the sum
o
f
leading b
e
e
s, follo
wing
bee
s and
scout
s re
main
s un
ch
ange
d
in the iterat
ion
pro
c
e
ss of al
gorithm. In current iteratio
n, leadi
ng be
es have be
en
transfo
rmed
into scouts, they
no long
er pe
rform op
erations of lea
d
in
g bee
s in
the next iteration. Also se
a
r
ch
strate
gy and
compl
e
xity of swam ha
s little difference
at
different stage based o
n
profitability ratios. When
r
grad
ually red
u
ce
s abo
ut
solution quality
,
the
solu
tion
perfo
rman
ce
gets goo
d
a
n
d
then
g
r
adu
ally
become
s
worse. When
r=1
,
0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0
, a
v
e
r
a
g
e
va
lu
e
o
f
D
ABC is
gr
e
a
t
er
than
3.5×1
0
-4
. The
worst value
s
are all
greate
r
than 3.6
×
1
0
-4
. Howev
e
r, whe
n
r=0.7, 0
.
8, 0.9
, avera
ge
value is l
e
ss
than 3.5
×
10
-4
. The worst value
s
a
r
e all
less than
3.6
×
10
-4
. When
r=0.8
, avera
g
e
value is 3.43
×10
-4
, wo
rst
value is 3.49
×10
-4
. Best value is 3.3
4
×10
-4
. The sta
ndard deviati
on is
3.58×10
-2
ju
st over the
sta
ndard deviati
on (3.
50×10
-2
) when
r=
0.7
. Therefore,
r=
0.8
i
s
the b
e
st
value for DA
BC.
Table 1. Diffe
rent
r
with diff
erent influe
nces on
DABC
r
Best
value×0.0001
Worst value
×0.0001
Average value
×0.0001
Standard deviati
on
×0.01
Average running
time/s
1 3.39
3.59
3.50
5.88
9.9222
0.9 3.35
3.57
3.47
4.94
9.0368
0.8 3.38
3.49
3.43
3.58
9.0341
0.7 3.42
3.52
3.44
3.50
9.0462
0.6 3.47
3.60
3.54
4.80
9.6879
0.5 3.44
3.66
3.55
4.85
9.6235
0.4 3.47
3.65
3.56
5.43
9.6235
0.3 3.48
3.65
3.57
4.47
9.5878
0.2 3.45
3.62
3.56
4.33
9.6211
0.1 3.44
3.64
3.56
5.84
9.6019
0 3.43
3.66
3.56
6.28
9.6218
4.2. The Experiment of
Algorithms Pe
rforman
ce Comparison
In orde
r to furthe
r verify the feasibility
and effectiv
ene
ss of thi
s
pape
r’s m
e
thod, we
choose multi
p
le instances in in
ternatio
nal unive
rsal
test library
for testin
g, a
nd u
s
e te
sti
n
g
res
u
lt
s t
o
ma
ke a co
mpa
r
i
s
on t
o
Re
so
u
r
ce
Re
cov
e
ry
Solutions Artificial Bees Colony (RRSA
B
C)
[8],
Ant Colony Optimiz
a
tion [9] (ACO) and ABC.
In the experi
m
ent, digit indicate
s nu
mb
er of citie
s
. Numb
er in p
a
renth
e
ses
repre
s
e
n
ts
kno
w
n
optim
al
solution. “O” sh
ows cal
c
ulatio
n
resul
t
of the in
dex
is n
o
t given
i
n
the
com
p
a
r
ation
literature. Experim
ental e
n
vironm
ent is the
sam
e
as above. Paramete
rs setting of DABC
algorith
m
: m
a
ximum nu
m
ber
of iterati
ons
2000
max
T
,
r=
0.8
, numbe
r
of b
ees
n
m
,
n
is
numbe
r of
cit
y
.
Paramete
rs setting of
ACO algo
rithm
:
n
m
,
1
,
5
,
9
.
0
. The t
w
o
algorith
m
s ru
n 20 times de
pend
ently. Calcul
at
ion re
sults are a
s
sh
own in Ta
ble
2.
From Table
2, RRSABC algorithm gets
t
he k
n
own
optimal s
o
lutions
in Berlin52,
Oliver30
a
n
d
Eil51. But it
eration
n
u
mb
er
of
DAB
C
has redu
ced
by 9
8pe
rce
n
t. What’
s
m
o
re,
step
s of DAB
C
are not
co
mplicate
d
. T
he aver
age v
a
lue ha
s in
creased by 0.5
%
(Not ex
ce
ed
0.5%). Co
mp
ared
with A
C
O algo
rithm, t
he be
st
value
and ave
r
a
g
e
value is rel
a
tively small, a
nd
for Bays2
9
,
Oliver30
an
d
Dant
zig4
2, the sta
nda
rd
deviation i
s
smaller. F
o
r th
e five insta
n
ces,
the runni
ng time of DABC
has
saved by
98.2%
, 98.3%, 98.66%, 98.96 and 9
8
.9
8% respe
c
tively.
ABC algorith
m
also ca
n o
b
tain the results clo
s
el
y to kno
w
n opti
m
al solutio
n
s for all instan
ce
s.
For Olive
r
30
and Bays29, DABC alg
o
rit
h
m gets the
same
re
sults as kno
w
n o
p
timal sol
u
tio
n
s.
For
Dant
zig4
2, cal
c
ulation
result of DA
BC al
go
rithm
has
de
cre
a
sed by 19.8%
comp
ared
with
ABC alg
o
rith
m. Figure 2
sh
ows th
e
experi
m
ent
al
sim
u
lation
diag
ram
of
Da
ntzig
42.
The
corre
s
p
ondin
g
optimal
path
is
[33,34,35,36,
37,38,39,4
0
,4
1,42,1,
2,3,4,5
,
6,7,8,9,10,25
,26,27,
11,12,
23,22,17,1
6
,1
3,14,15,18,1
9
,
20,21,28,2
9
,3
0,31,32].
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A New Meth
o
d
Used for T
r
aveli
ng salesm
an problem
Based o
n
Di
screte A
r
tificial
… (Lei Me
ng)
347
Table 2. Cal
c
ulation Results
Instance Calculation
index
DABC
RRSABC
ABC
ACO
Ba
y
s
29(20
20)
Best value
2020
O
2020
2040
Average value
2027.8
O
2031.4
2061.7
Iteration numbe
r
2000
O
50
2000
Running time
5.11
O
O
285.97
Oliver30(423.
74)
Best value
423.74
423.74
423.5
425.82
Average value
425.00
423.74
432.5
428.76
Iteration numbe
r
2000
100000
50
2000
Running time
5.36
O
O
317.73
Dantzig42(699
)
Best value
679.20
O
699
696.12
Average value
692.05
O
710.2
716.46
Iteration numbe
r
2000
O
100
2000
Running time
8.95
O
O
672.48
Eil51(429.98)
Best value
431.24
428.87
426.00
457.79
Average value
444.09
431.11
427.60
468.51
Iteration numbe
r
2000
100000
50.0
2000
Running time
10.36
O
O
1001.04
Berlin52(7544.4
)
Best value
7680.78
7554.37
7542
8048.07
Average value
7941.27
7562.80
7573.48
131.51
Iteration numbe
r
2000
100000
150
2000
Running time
10.76
O
O
1055.01
(a) O
p
timal p
a
th
(b) Be
st value evolution curve
Figure 2. Experime
n
tal sim
u
lation diag
ra
m of Dantzig
4
2
The
avera
ge
value of
DAB
C
al
gorith
m
i
s
rel
a
tively sm
all compa
r
e
d
with ABC alg
o
rithm
for Oliver3
0
, Dant
zig4
2 an
d Bays29. A
B
C algo
rithm
is mainly ba
sed o
n
the A
C
O alg
o
rithm
and
has
co
mbine
d
with oth
e
r
operation
s
. Whe
n
the n
u
m
ber
of pop
u
l
ation in ABC is eq
ual to t
hat in
ACO, the ru
n
n
ing time in
ABC is cl
osel
y to that
of ACO at lea
s
t. Neverth
e
le
ss,
the run
n
ing t
i
me
in ACO i
s
rel
a
tively long.
Therefor,
DA
BC alg
o
rithm
has the
better sol
u
tion
perf
o
rma
n
ce in
te
rms
of solution ti
me and soluti
on quality compar
ed with
ACO, ABC and RRSABC algorithm.
5. Conclu
sion
This p
ape
r prop
oses a
new di
screte
artificial col
ony algorith
m
for solvin
g TSP
que
stion. It e
x
tends
co
ntin
uou
s a
r
tificial
swa
r
m
opti
m
ization
alg
o
r
ithm to
di
screte do
main.
The
new
algo
rith
m makes t
r
a
n
sition fo
r
col
ony ch
ara
c
te
rs an
d sea
r
ch
mechani
sm
based o
n
in
come
ratios ind
e
x o
f
defination. It define
s
reje
ction ope
rato
r
to ke
ep the
d
i
versity of p
o
pulation, a
nd
it
introduces Tabu table
and
defines the learning
operat
o
r to improve the lo
cal
refinement ability of
the algo
rithm
and the
opti
m
al sp
eed. T
herefo
r
e,
the
new sche
me
can better coordi
nate sp
ace
exploratio
n a
nd the lo
cal
refinement a
b
i
lity of ABC
algorithm
at the sa
me time.
What’
s
mo
re
, it
accele
rate
s
conve
r
ge
nce
sp
eed
of t
he al
gorithm
.
The expe
ri
mental re
sult
s sho
w
th
at
the
algorith
m
can
find relatively satisfa
c
tory
solutio
n
in
a
sh
ort time
a
nd imp
r
ove t
he efficie
n
cy
of
solving the T
SP. In
the future, we
woul
d find mo
re e
ffective ABC
algorith
m
s to improve opti
m
um
sea
r
ching m
e
thod.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 14, No. 1, March 2
016 : 342 – 3
4
8
348
Ackn
o
w
l
e
dg
ements
The autho
rs also g
r
atefull
y
ackn
owl
e
d
ge t
he helpfu
l
comme
nts a
nd su
gge
stio
ns of the
reviewers, wh
ich have im
p
r
oved the pre
s
entation.
Referen
ces
[1]
Carrabs F
,
Cor
dea
u JF
, Lapor
te G. Variable
nei
ghb
orh
ood
search for the
picku
p and
del
i
v
er
y
trave
l
i
ng
salesm
an pro
b
l
e
m
w
i
t
h
LIF
O
load
ing.
Infor
m
s Journa
l on C
o
mputi
ng.
20
1
5
; 19(4): 20
07.
[2]
Len
in Kan
a
g
a
s
aba
i,
B Ravi
nd
ranath
R
edd
y,
M
Sur
y
a
Ka
lav
a
thi. Atmosp
he
re C
l
ou
ds M
o
d
e
l A
l
gor
ithm
for Solv
ing
Op
timal R
eactiv
e
Po
w
e
r
Dis
patc
h
Pro
b
lem.
In
d
ones
ian
Jo
urn
a
l
of Electric
al
Eng
i
ne
eri
n
g
and Infor
m
atic
s (IJEEI).
2014
; 2(2).
[3]
K Leni
n, B Ra
vindr
anath
Re
dd
y. Volta
ge P
r
ofile
En
ha
nce
m
ent and R
e
d
u
ction of R
eal
Po
w
e
r l
o
ss b
y
Hy
b
r
i
d
Bi
og
e
o
g
r
a
phy
Ba
se
d Arti
fi
ci
a
l
Be
e C
o
l
ony
al
gori
t
h
m
.
Indon
e
s
ian J
ourn
a
l
of Electrica
l
Engi
neer
in
g an
d Informatics (IJEEI)
, 2014; 2(2).
[4
]
Ka
ra
bo
ga
D
.
An
id
e
a
ba
sed
on
h
o
ney
be
e
s
w
a
rm for
numer
ical
op
timizatio
n
. T
e
chnic
a
l R
e
p
o
rt
T
R
06. 2014.
[5]
Anan
dh
akumar
R, Su
brama
n
ia
n S, Ga
ne
san S,
et a
l
. Mod
i
fied
AB
C Al
gorithm
for Gen
e
rat
o
r
Mainte
nanc
e S
c
hed
uli
ng.
Elec
tric Power System
s Research
.
2011; 2
4
: 812-
819.
[6]
Sharma
P, Gupta M.
T
SP P
r
obl
em Usi
n
g
Modifi
ed AB
C
Based
on
Dyn
a
mical
l
y D
i
visi
on
of Bees.
/
Comp
uting C
o
mmunicati
on
Contro
l and A
u
tomatio
n
(ICCUBEA), 201
5
Internation
a
l
Confer
ence
on
.
IEEE. 2015.
[7]
Hon
g
-T
ao YU, Gao LQ, T
i
an W
H
. Discret
e Ar
tificial Bee Colony
A
l
gorithm for T
S
P.
Journa
l of
Northe
astern U
n
iversity.
20
15.
[8]
Li S, Gao X, W
ang L, et al. A novel ma
xi
mum
po
w
e
r p
o
int trackin
g
control meth
od
w
i
t
h
varia
b
l
e
w
e
ath
e
r par
ameters for photo
v
oltaic s
y
stems
.
Solar Energy
.
2013; 9
7
(5): 5
29-5
36.
[9]
Yu L, Li M, Yang Y, et al.
An Impr
ove
d
Ant Colo
ny Optimi
z
a
ti
on for
Vehicl
e Ro
uti
ng Pro
b
le
m.
Log
istics@sT
he Emergin
g
F
r
ontiers of T
r
ansportati
o
n
and
Devel
opm
ent i
n
Chin
a, ASCE. 2015: 336
0-
336
6.
Evaluation Warning : The document was created with Spire.PDF for Python.