TELK
OMNIKA
,
V
ol.
15,
No
.
3,
September
2017,
pp
.
1247
1256
ISSN:
1693-6930,
accredited
A
b
y
DIKTI,
Decree
No:
58/DIKTI/K
ep/2013
DOI:
10.12928/telk
omnika.v15.i3.3656
1247
HABCO:
A
Rob
ust
Ag
ent
on
Hybrid
Ant-Bee
Colon
y
Optimization
Abba
Suganda
Gir
sang*
1
,
Chun-W
ei
Tsai
2
,
and
Chu-Sing
Y
ang
2
1
Master
in
Computer
Science
,
Bina
Nusantar
a
Univ
ersity
,
J
akar
ta,
Indonesia
2
Depar
tment
of
Computer
Science
and
Engineer
ing,
National
Chung-Hsing
U
niv
ersity
,
T
aichung,
T
aiw
an
3
Institute
of
Computer
and
Comm
unication
Engineer
ing,
Depar
tment
of
Electr
i
cal
Engineer
ing,
National
Cheng
K
ung
Univ
ersity
,
T
ainan,
T
aiw
an
*Corresponding
author
,
e-mail:
agirsang@bin
us
.edu
Abstract
The
pur
pose
of
this
research
is
to
gener
ate
a
rob
ust
agent
b
y
combinin
g
bee
colon
y
optimization
(BCO)
and
ELU-Ants
f
or
solving
tr
a
v
elin
g
salesman
prob
lem
(TSP),
called
HABCO
.
The
rob
ust
agents
,
called
ant-bees
,
firstly
are
g
rouped
into
three
types
scout,
f
ollo
w
er
,
recr
uiter
at
each
stages
.
Then,
the
bad
agents
are
high
proba
b
ly
discarded,
while
the
good
agents
are
high
probab
ly
dup
licated
in
ear
lier
steps
.
This
first
tw
o
steps
mimic
BCO
algor
ithm.
Ho
w
e
v
er
,
constr
ucting
tours
such
as
choosing
nodes
,
and
updating
pheromone
are
b
uilt
b
y
ELU-Ants
method.T
o
e
v
aluate
the
perf
or
mance
of
the
proposed
algor
ithm,
HABCO
is
perf
or
med
on
se
v
er
al
benchmar
k
datasets
and
compared
to
A
CS
and
BCO
.
The
e
xper
imental
results
sho
w
that
HABCO
achie
v
es
the
better
solution,
either
with
or
without
2opt.
K
e
yw
or
ds:
Ant
Colon
y
Optimization,
Bee
Colon
y
Optimization,
Hybr
id,
Rob
ust
Agent,
T
r
a
v
eling
S
alesman
Prob
lem
Cop
yright
c
2017
Univer
sitas
Ahmad
Dahlan.
All
rights
reser
ved.
1.
Intr
oduction
Intelligent
algor
ithm
is
popular
to
solv
e
se
v
er
al
optimization
prob
lems
because
if
its
per-
f
or
mance
[1-11].Some
intelligent
algor
ithms
such
as
ant
colon
y
optimization
[1-2],
genetic
algo-
r
ithm
[3],
par
ticle
s
w
ar
m
optimization
[4-5],
sim
ulated
annealing
[6],
cat
s
w
ar
m
optimization
[7],
bee
colon
y
optimization
[8-10],
and
so
f
or
th
w
ere
proposed
to
solv
e
tr
a
v
elling
salesman
prob
lem
(TSP).
In
ant
colon
y
optimization
(A
CO),
ants
la
y
a
pheromone
tr
ail
in
their
paths
while
tr
a
v
el-
ing
from
their
nest
to
f
ood
source
[1]
to
find
the
shor
test
tour
f
or
the
f
ood.
Since
then,
man
y
researchers
also
contin
ued
this
approach
f
or
better
results
on
v
ar
ious
optimization
prob
lems
[11-
13].
In
[12]
p
roposed
an
adaptiv
e
par
ameter
control
scheme
f
or
de
v
eloping
an
adaptiv
e
A
CS
namely
AA
CS
.
The
par
ameters
v
alue
in
AA
CS
are
adaptiv
ely
controlled
based
on
inf
or
mation
of
pheromone
tr
ails
distr
ib
ution
in
each
iter
ation
that
is
utiliz
ed
to
estimate
the
optimization
state
.
Naimi
and
T
aher
inejad
proposed
ELU-Ants
and
KCC-Ants
to
modify
A
CS
b
y
introduce
ne
w
local
update
[13].
This
research
emphasiz
ed
that
the
update
pheromone
on
ear
lier
step
is
more
than
the
later
step
.
The
other
researchers
presented
a
combining
A
CO
with
the
other
methods
[14-15].
Lucic
et
al
[16-17]
then
proposed
another
intelligent
algor
ithm
bee
colon
y
opti-
mization
(BCO),which
is
designed
to
create
the
m
ulti-agent
system
(colon
y
of
ar
tificial
bees)
f
or
solving
the
combinator
ial
optimization
prob
lems
[17-24].
This
research
is
tr
ied
to
adopt
ELU-Ants
algor
ithm
which
considers
the
beginning
step
as
the
more
impor
tant
step
to
constr
uct
the
tour
.
Logically
,
an
agent
with
bad
choice
of
tr
a
v
eling
some
cities
(par
t
of
tour)
should
be
discarded
b
ut
an
agent
with
good
choice
should
be
duplicated
at
the
beginning
step
.
The
discarded
and
duplicated
agent
in
ear
lier
step
guar
antees
the
agent
will
be
more
competitiv
e
.
Theref
ore
the
update
pheromone
on
ear
lier
step
is
more
than
the
later
step
.
In
spite
of
star
ting
with
good
or
bad
choice
,
ants
m
ust
contin
ue
selecting
a
path
f
or
completing
their
tour
.
Receiv
ed
Ma
y
17,
2016;
Re
vised
Ma
y
4,
2017;
Accepted
J
une
1,
2017
Evaluation Warning : The document was created with Spire.PDF for Python.
1248
ISSN:
1693-6930
Figure
1.
Illustr
ation
agent
M
tr
a
v
els
cities
with
tw
o
step
constr
uctions
.
Fig.
1
descr
ibes
the
a
gents
M
constr
ucts
the
tour
which
is
split
into
tw
o
impor
tant
step
constr
ucting.
Suppose
in
beginning
step
,
agents
M
constr
uct
the
par
t
tour
which
consists
i
cities
.
Each
agents
tr
a
v
els
cities
C
1
,
C
2
,
C
3
,...,
C
i
at
beginning
step
.
While
constr
ucting
the
tour
,
the
ant
is
possib
le
to
get
bad
choice
at
first
stage
and
leads
tr
apped
on
bad
constr
ucting
as
w
ell.
At
last
it
probab
ly
br
ings
to
the
bad-tour
.
In
BCO
,
after
tr
a
v
eling
some
nectars
or
stage
,
each
bees
bac
ks
to
the
hiv
e
to
comm
u-
nicate
their
w
a
y
.
In
the
hiv
e
,
the
y
g
roup
into
three
type
a
nd
perf
or
m
w
aggle
dance
to
identify
their
quality
of
f
ood
source
.
The
longer
dance
indicates
the
better
quality
of
nectars
f
ound.
Bees
e
xchange
inf
or
mation
to
each
other
f
or
their
ne
xt
stage-tour
.
Bees
finding
bad-source
f
ood
tend
to
f
ollo
w
the
others
with
good-source
f
ood
at
ne
xt
stage
.
This
step
sho
ws
that
BCO
discards
bee
with
bad
stage-tour
in
order
to
get
the
better
tour
f
or
the
ne
xt
stage
,
and
in
other
side
automatically
the
bee
with
good
stage-tour
is
duplicated.
So
based
on
discussion
abo
v
e
,
the
proposed
algor
ithm,
HABCO
,
is
gener
ate
d
b
y
con-
str
ucting
the
rob
ust
agent
as
BCO
algor
ithm,
ho
w
e
v
er
the
process
of
selecting
nodes
(cities)
is
done
b
y
ELU-Ants
.
HABCO
w
as
first
presented
b
y
Ab
ba
et
al
in
a
proceeding
of
a
conf
erence
[25].
Ho
w
e
v
er
this
paper
presented
mor
e
detail
of
the
related
w
or
k
and
processing
of
judgment
agent.
2.
Related
W
ork
2.1.
Ant
Colon
y
System
Ant
colon
y
system
(A
CS)
is
one
of
the
most
widely
used
and
best-perf
or
ming
A
CO
.
While
ants
search
f
ood,
the
y
will
deposit
the
pheromone
on
the
path
where
the
y
passed.
The
ants
will
tend
to
choose
the
path
whose
the
highest
amount
pheromone
on
it,
and
a
v
oid
the
lo
w
pheromone
path.
There
are
some
substantial
par
ts
to
descr
ibe
A
CS
br
iefly
[1].
Constr
uction
T
our
:
While
the
kth
ant
is
in
city
i
,
the
ne
xt
city
j
is
selected
from
the
un
visited
city
set
J
k
(i)
according
to
the
tw
o
possibilities
,
P
k
(i,j)
,
in
Eq.
(1)
and
in
Eq.
(2)
:
a.
if
q
q
0
(e
xploitation)
j
=
ar
g
max
b
(
i;
u
)
:
(
i;
u
)
c
;
2
J
k
(
i
)
;
(1)
TELK
OMNIKA
V
ol.
15,
No
.
3,
September
2017
:
1247
1256
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
1249
b
.
if
q
>
q
0
(bias
e
xplor
ation)
P
k
(
i;
j
)
=
[
(
i;
j
)]
:
[
(
i;
j
)]
2
J
k
(
i
)
[
(
i;
j
)]
:
[
(
i;
j
)]
;
(2)
where
q
is
a
r
andom
n
umber
;
q
0
is
a
par
ameter
;
represents
pheromone
v
alue
.
Local
pheromone
updating
:
Ants
visit
edge
i
,
j
and
change
the
pheromone
(i,j)
edge
le
v
el
b
y
local
updating
r
ule
in
Eq.
(3)
:
(
i;
j
)
=
(1
)
(
i;
j
)
+
(
i;
j
)
;
(3)
Global
pheromone
updating
:
The
pheromone
of
edges
on
the
globally
best
tour
is
updat
ed
b
y
global
updating
r
ules
Eq.
(4)
and
Eq.
(5).
(
i;
j
)
=
(1
)
(
i;
j
)
+
(
i;
j
)
;
(4)
(
i;
j
)
=
8
<
:
(
L
g
b
)
1
if
(
i;
j
)
2
global
best
tour
0
Otherwise
(5)
0
<
<
1
is
the
pheromone
deca
y
par
ameter
,
and
L
g
b
is
the
length
of
the
globally
best
tour
.
2.2.
ELU-Ants
ELU-Ants
[4]
is
a
modified
of
the
or
iginal
A
CS
.
Hosein
in
his
research
off
ered
t
w
o
equation
to
implement
the
algor
ithm,
one
is
named
Kcc-Ants
and
the
another
one
is
ELU-Ants
.
Al
though
both
of
them
used
the
similar
approach,
the
y
represented
their
proposed
on
diff
erent
equation.
The
results
of
both
equation
are
almost
similar
.
This
research
uses
the
ELU-Ants
approach.
The
main
idea
of
this
research
is
the
ants
ha
v
e
more
ability
to
add
more
the
ph
eromone
of
the
pr
imar
y
links
than
the
last
links
.
While
in
ear
ly
steps
,
the
ant
has
a
lot
of
options
to
choose
which
city
tr
a
v
eled,
because
it
has
passed
just
a
f
e
w
cities
.
As
a
consequence
,
it
mak
es
just
a
f
e
w
edge
are
prohibited
to
be
selected.
Theref
ore
,
the
ant
can
freely
choose
the
most
desir
ab
le
link
(with
more
pheromone
and
less
length)
as
its
ne
xt
link.
Contr
ar
y
on
final
steps
of
tour
,
the
ant
already
passed
most
of
the
cities
,
and
the
current
selecte
d
link
ma
y
not
ha
v
e
a
significant
eff
ect
on
the
quality
of
the
tour
,
so
it
seems
logical
to
reduce
its
ability
of
changing
the
last
link
pheromone
.
In
other
w
ords
,
ants
ha
v
e
more
eff
ect
on
pheromone
update
where
the
y
are
in
their
initial
steps
and
less
eff
ect
when
the
y
are
going
to
finish
the
tour
.
Based
on
abo
v
e
discussion,
local
update
or
iginal
(Eq.(3))
is
modified
to
be
ELU-Ants
(Eq.
(6))
and
Kcc-Ants
(Eq.
(7)).
(
i;
j
)
=
(
i;
j
)
+
0
:e
5
:cc
n
;
(6)
(
i;
j
)
=
(
i;
j
)
+
K
:cc:
0
cl
cc
!
;
(7)
where
cc
represents
the
n
umber
of
cities
passed
till
no
w;
n
is
total
n
umber
of
cities
;
K
and
!
denote
tw
o
par
ameters
giv
en;
Cl
represents
c
u
rrent
length
of
passed
path
of
each
ants
and
represents
initial
pheromone
.
2.3.
Bee
Colon
y
Optimization
Bee
colon
y
optimization
(BCO)
is
designed
to
create
the
m
ulti
agent
system
to
solv
e
the
combinator
ial
optimization
prob
lems
.
Lucic
et
al
[16-17]
proposed
BCO
to
solv
e
TSP
.
On
implementation
BCO
on
TSP
,
the
tour
consists
n
umerous
stages
.
A
stage
is
a
collection
of
a
cer
tain
amount
of
nectars
.
In
TSP
model,
nectars
can
represent
cities
.
In
constr
ucting
the
tour
,
a
be
e
star
ts
as
an
unemplo
y
ed
f
or
ager
without
kno
wledge
about
the
f
ood
(
nectar).
Bees
star
t
e
xplor
ing
from
nectar
to
nectars
or
tr
a
v
el.
This
step
is
called
f
orw
ard
pass
(FP).
As
a
notion,
not
all
bees
star
t
f
or
aging
in
the
first
stage
.
Some
of
them
star
t
at
the
second
stage
,
third
stage
,
etc.
HABCO:
A
Rob
ust
Agent
on
Hybr
id
Ant-Bee
Colon
y
Optimization
(Ab
ba
Suganda
Girsang)
Evaluation Warning : The document was created with Spire.PDF for Python.
1250
ISSN:
1693-6930
Once
a
bee
is
on,
she
will
be
activ
e
till
the
end
of
iter
ation.
After
perf
or
ming
one
stage
,
a
bee
retur
ns
to
the
hiv
e
in
order
to
unload
and
store
the
nectar
.
It
is
called
bac
kw
ard
pass
(BP).
In
BP
,
bees
will
perf
or
m
w
aggle
dance
to
sho
w
their
quality
tour
and
star
t
e
xchanging
inf
or
mation.
The
kind
of
comm
unication
betw
een
individual
bees
contr
ib
utes
to
the
f
or
mation
of
the
bee
colon
y
.
Bef
ore
comm
unicating,
BCO
selects
r
andomly
with
a
par
ticular
probability
(e
.g.10
%)
to
be
scout.
The
bees
which
retain
the
pre
vious
stage
and
contin
ue
the
ne
xt
stage
without
inter
acting
with
the
others
are
named
scout.
The
remind
bees
will
be
categor
iz
ed
into
f
ollo
w
er
and
recr
uiter
.
BCO
uses
Eq.
(8)
f
or
deter
mining
the
probability
that
the
bee
k
in
ne
xt
stage
(u+1)
with
the
same
par
tial
tour
at
stage
u
in
iter
ation
z
as
descr
ibed
belo
w
:
P
k
(
u
+
1
;
z
)
=
e
L
k
(
u;z
)
min
r
2
w
(
u;z
)
(
L
r
(
u;z
))
uz
(8)
where
L
k
(u,z)
is
the
length
stage-tour
that
is
disco
v
ered
b
y
bee
k
in
stage
u
in
iter
ation
z
.
As
a
result
of
inter
action,
in
addition
of
scout,
the
bees
ha
v
e
the
tw
o
other
types
,
recr
uiter
and
f
ollo
w
er
.
The
bees
which
retain
their
pre
vious
stage
and
recr
uit
the
f
ollo
w
er
bees
on
their
w
a
y
are
named
recr
uiter
.
The
bee
s
which
abandon
the
f
ood
source
(pre
vious
stage)
and
f
ollo
w
the
recr
uiter
bees
on
their
w
a
y
are
named
f
ollo
w
er
.
Since
the
probabilit
y
of
best
path
bee
will
be
1
(
P
k
=
1),
she
will
use
absolutely
the
same
par
tial
and
categor
iz
ed
as
g
roup
of
recr
uiter
.
BCO
introduced
the
probability
of
par
tial
tour
will
be
chosen
b
y
an
y
bee
that
decided
to
choose
the
ne
w
route
in
one
stage
.
The
probability
is
gener
ated
regarding
tw
o
main
attr
ib
ute
the
total
length
tour
and
n
umber
bee
that
are
adv
er
tising
the
par
tial
tour
.
The
smaller
the
nor
maliz
ed
v
alue
of
the
total
length,
the
better
is
the
par
tial
tour
,
while
the
bigger
nor
maliz
ed
v
alue
of
n
umber
bees
,
the
better
is
the
par
tial
tour
.
Procedure
BCO
can
be
descr
ibed
as
on
Fig.
2.
Procedure
BCO
f
or
solving
TSP
Set
par
ameters
and
n
umber
stage
F
or
each
stages
F
or
each
bees
Constr
uct
Solution
Classify
bee
into
scout,
recr
uiter
,
f
ollo
w
er
End
bee
All
bees
e
xchange
inf
or
mation
End
stage
Local
Search
End
Figure
2.
BCO
Algor
ithm.
3.
Pr
oposed
Algorithm
3.1.
The
Concept
Since
there
is
a
consider
ation
f
or
beginning
step
and
last
step
in
constr
ucting
tour
,
the
tour
should
be
split
into
some
par
ts
of
tour
.
This
par
t
of
tour
can
be
identified
as
the
stage
in
BCO
which
consists
some
cities
.
The
stage-tour
agent
constr
ucted
is
e
xpected
to
judge
the
quality
agent.
On
BCO
,
after
tr
a
v
eling
one
stage
,
bees
bac
k
to
hiv
e
and
g
roup
into
three
types
f
ollo
w
er
,
recr
uiter
,
and
scout
based
on
their
quality
.
This
algor
ithm
uses
”ant-bee”
as
its
agent
and
mimics
the
beha
vior
of
bee
on
BCO
.
F
ollo
w
er
ant-bee
is
identified
as
the
agent
which
perf
or
ms
bad
choice
on
its
stage-tour
.
Recr
uit
ant-bee
is
identified
as
the
agent
which
perf
or
m
good
choice
on
its
stage-tour
.
Scout
ant-bee
is
identified
as
the
agent
which
alw
a
ys
find
the
ne
w
alter
nativ
e
tour
.
Fur
ther
,
f
ollo
w
er
will
change
their
st
age-tour
and
f
ollo
w
the
stage-tour
of
recr
uiter
agents
.
Scouts
neither
f
ollo
w
nor
recr
uit
the
other
agent,
y
et
k
eep
their
stage-tour
.
Fig.
3
giv
es
the
illustr
ation
ho
w
gener
ates
the
competitiv
e
agents
.
Suppose
there
are
three
agents
M
1
,
M
2
and
M
3
and
three
cities
at
first
stage
.
S
11
,
S
12
,
S
13
are
the
collection
of
TELK
OMNIKA
V
ol.
15,
No
.
3,
September
2017
:
1247
1256
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
1251
Figure
3.
Illustr
ation
ho
w
gener
ates
the
competitiv
e
agent.
cities
tr
a
v
eled
a
t
the
first
stage
b
y
agent
M
1
,
M
2
and
M
3
respectiv
ely
.
C
11
-
C
21
-
C
31
,
C
12
-
C
22
-
C
32
,
C
13
-
C
23
-
C
33
are
the
sequence
cities
tr
a
v
eled
at
first
stage
b
y
M
1
,
M
2
and
M
3
respectiv
ely
.
After
tr
a
v
eling
the
first
stage
,
all
agents
are
e
v
aluated
to
conclude
their
type
.
Suppose
M
1
,
M
2
and
M
3
become
recr
uiter
,
f
ollo
w
er
and
scout
respectiv
ely
.
At
the
end
of
first
stage
,
M
1
as
recr
uiter
k
eeps
its
stage-tour
,
M
2
as
f
ollo
w
er
changes
its
stage-tour
and
f
ollo
w
M
1
’
s
stage-tour
,
M
3
as
scout
k
eeps
its
stage-tour
.
Theref
ore
,
at
beginning
second
stage
the
agents
M
1
,
M
2
and
M
3
should
contin
ue
the
tour
from
city
C
31
,
C
31
,
C
33
respectiv
ely
.
The
interesting
question
is
ho
w
to
mak
e
a
good
judgment
in
order
to
classify
the
quality
of
agents
on
constr
ucting
stage-tour
.
The
sub
section
3.3
will
e
xplain
that
the
total
amount
pheromon
e
gathered
on
each
stage
can
be
used
as
a
good
judgment.
3.2.
Construct
T
our
In
constr
uction
tour
f
or
solving
TSP
,
the
ant-bee
chooses
cities
with
A
CS
algor
ithm
(Eq.
(1)
and
Eq.
(2)).
After
each
ant-bees
tr
a
v
eling
one
stage
using
the
r
ule
of
A
CS
,
it
bac
ks
to
hiv
e
to
inter
acting
with
each
other
(supposing
distance
f
rom
hiv
e
to
each
city=0),
and
calculating
t
he
total
amount
of
pheromone
.
HABCO
also
categor
iz
es
ant-bees
into
three
types
based
on
pheromone
gathered
namely
scout(
S
),
f
ollo
w
er(
F
),
and
recr
uiter(
R
)
as
BCO
.
Scout
retains
the
pre
vious
stage
and
contin
ues
the
ne
xt
stage
without
inter
acting
with
the
others
,
f
ollo
w
er
abandons
the
pre
vious
stage
and
f
ollo
ws
the
recr
uiter
,
recr
uiter
retains
her
pre
vious
stage
and
recr
uits
the
f
ollo
w
er
to
join
her
pre
vious
stage
tour
.
On
HABCO
,
the
judgment
of
quality
of
agents
is
based
on
the
amount
pheromone
that
agent
gathers
in
each
stages
.
J
udgment
is
used
to
classify
ant-bees
into
F
ollo
w
er
,
and
Recr
uiter
.
Scout
agent
is
firstly
chosen
10
%
from
all
agents
.
The
scout
agent
guar
antees
the
alter
nativ
e
tour
is
k
ept
on
the
process
.
The
remainder
agents
is
categor
iz
ed
as
f
ollo
w
er
and
recr
uiter
.The
probability
ant-bee
into
f
ollo
w
er
after
tr
a
v
eling
one
stage
is
used
b
y
Eq.
(9).
P
F
=
max
i
P
M
i
=1
(
max
i
)
;
(9)
HABCO:
A
Rob
ust
Agent
on
Hybr
id
Ant-Bee
Colon
y
Optimization
(Ab
ba
Suganda
Girsang)
Evaluation Warning : The document was created with Spire.PDF for Python.
1252
ISSN:
1693-6930
where
i
is
agent
inde
x;
M
is
the
total
n
umber
agent
ant-bees;
i
represents
pheromone
gathered
at
each
stages
b
y
agent;
max
represents
pherom
one
maxim
um
gathered
at
each
stages
b
y
agent.
F
rom
Eq.
(9)
sho
ws
that
agent
which
gathers
the
high
pheromone
has
lo
w
probability
to
be
f
ollo
w
er
.
F
or
the
highest
pheromone
(
max
)
agent
is
impossib
le
to
be
f
ollo
w
er
(
P
F
=0).
In
other
w
ords
,
it
will
absolutely
become
a
recr
uiter
.
After
categor
iz
ed
the
agents
into
f
ollo
w
er
and
recr
uiter
,
the
f
ollo
w
er
will
change
he
r
tour
and
f
ollo
w
one
of
the
f
ollo
w
er
agent
r
andomly
.
After
e
xchanging
inf
or
mation
on
hiv
e
,
the
agent
ant-bees
contin
ue
the
ne
xt
stages
until
finish
the
tour
.
3.3.
Pher
omone
updating
There
are
3
types
pheromone
updating
on
HABCO
.
The
y
are
local
update
,
semi-global
update
and
global
update
.
Local
updat
e
is
perf
or
med
as
local
updating
r
ule
in
A
CS
al
gor
ithm
(Eq.
(3)).
While
ant-bees
choosing
their
edge
,
the
y
also
modify
their
pheromone
.
After
perf
or
ming
one
sta
ge
,
HABCO
updates
the
pheromone
called
semi-global
update
.
This
update
is
based
on
modified
ELU-Ants
algor
ithm
that
ants
ha
v
e
more
eff
ect
on
pheromone
update
where
the
y
are
in
their
ear
lier
steps
and
less
eff
ect
when
the
y
are
going
to
finish
the
tour
.
(
i;
j
)
=
(
i;
j
)
+
0
:e
5
S
j
S
j
;
(10)
where
S
is
current
stage;
j
S
j
is
total
n
umber
stage
.
Ob
viously
from
Eq.
(10),
the
pheromone
after
perf
or
ming
the
first
stage
(
S=1
)
is
added
more
than
the
ne
xt
stage
.
So
the
ant-bees
pla
y
f
e
w
er
impact
in
update
pheromone
when
the
y
are
in
their
final
par
t
of
tour
.
In
last
stage
(final
par
t),
S=
total
n
umber
stage
,
it
mak
es
the
impact
pheromone
update
to
w
ard
z
ero
.
At
last,
the
ph
eromone
on
the
edges
are
tr
a
v
elled
b
y
th
e
best
ant-bee
will
be
updated
with
global
updating
r
ule
as
the
A
CS
Eq.
(4)
and
Eq.
(5).
3.4.
Ruin
local
optima
In
the
obser
v
ation,
the
best
length
tour
is
possib
le
same
in
some
iter
ations
in
a
ro
w
especially
on
the
relativ
e
small
benchmar
k.
The
best
ant-bee
probab
ly
tr
a
v
els
on
same
edge
in
each
iter
ations
.
So
,
it
might
the
process
tr
aps
to
be
local
optimal.
This
situation
mak
es
the
algor
ithm
sometimes
f
ails
to
get
the
optimal
solution.
T
o
a
v
oid
this
prob
lem
(r
uin
local
optimal),
the
pheromone
on
that
edges
is
reduced/e
v
apor
ated,
when
the
best
of
length
tour
is
same
f
or
t
times
iter
ations
(
t=100
)
in
a
ro
w
.
r
s
=
x:
r
s
;
(11)
where
0
<
x
<
1.
V
ar
iab
le
is
consider
ed
as
a
f
air
n
umber
.
When
x
is
set
too
high,
r
u
ining
of
local
optim
um
will
f
ail
to
be
obtained.
Contr
ar
ily
,
if
x
is
set
too
small,
it
will
decrease
pheromone
significantly
and
aff
ect
the
constr
uction
of
tour
.
The
algor
ithm
of
HABCO
is
descr
ibed
as
Fig.
4.
4.
P
erf
ormance
and
Anal
ysis
Results
4.1.
Anal
ysis
Constructing
the
Rob
ust
Ag
ent
As
af
erementioned,
the
pheromone
and
distance
nodes
are
tw
o
v
ar
iab
les
impor
tant
in
A
CO
.
This
section
probes
whether
the
tw
o
v
ar
iab
les
can
be
to
a
judgment
of
the
quality
agent.
One
benchmar
k
TSP
,
st70
,
is
in
v
estigated
to
see
impact
of
the
distance
and
amount
pheromone
at
each
stages
that
is
perf
or
med
b
y
ants
.
This
actions
are
tr
ied
on
three
stages
while
n
umber
agents
are
ten.
Firstly
the
agent
(ant)
tr
a
v
els
all
cities
stage
b
y
stage
with
f
ollo
w
the
A
CS
r
ule
on
Eq.
(2).
W
e
obser
v
er
tw
o
kind
the
agents
.
The
first
is
the
best
agent
which
get
the
best
complete
tour
.
The
second
one
is
the
w
orst
agent
which
get
the
w
orst
complete
tour
.
While
tr
a
v
eling,
the
total
distance
and
the
amount
of
pheromone
at
each
edges
is
added
and
calculated
in
one
stage
.
After
tr
a
v
eling
one
stage
,
each
agent
contin
ues
ne
xt
stage
without
inter
action
each
other
.
At
last,
after
each
agents
completes
the
ir
tour
,
the
length
complete
tour
and
pheromone
of
each
ants
also
be
calculated
and
r
ank
ed.
In
t
he
obser
v
ation,
consider
ing
b
y
calculating
the
distance
tr
a
v
ele
d
at
one
stage
is
not
reliab
le
.
It
sho
ws
the
best
ant
which
gets
the
shor
test
distance
tour
has
v
ar
ious
position
r
ank
on
first
stage
.
Fur
ther
,
the
w
orst
ant
which
tr
a
v
els
the
longest
distance
has
not
alw
a
ys
bad
position
TELK
OMNIKA
V
ol.
15,
No
.
3,
September
2017
:
1247
1256
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
1253
Set
par
ameters
and
n
umber
stage
F
or
each
stages
F
or
each
ant-bees
constr
uct
solution;
local
update
End
ant-bees
Semi-global
update;
Rank
ed
ant-bees
F
or
each
ant-bees
//Bac
k
to
hiv
e
Classify
ant-bees
into
scout,
recr
uiter
,
f
ollo
w
er
End
ant-bees
All
ant-bees
e
xchange
inf
or
mation
If
(stage=n
umber
stage)
Calculating
the
length
complete
tour
of
each
ant-bees
Global
update
b
y
the
best
ant-bee
Ruin
local
optima
End
if
End
Stage
Local
Search
Figure
4.
HABCO
Algor
ithm.
on
first
stage
.
It
means
that
an
ant
can
not
guar
antee
getting
the
relativ
ely
shor
t
in
the
complete
tour
when
tr
a
v
eling
relativ
ely
shor
t
at
the
first
stage
.
Contr
ar
ily
,
when
an
ant
tr
a
v
els
relativ
ely
long
at
first
stage
,
she
can
not
guar
antee
getting
relativ
ely
long
in
the
complete
tour
.
It
is
because
each
ants
is
possib
le
to
choose
se
v
er
al
cities
which
ha
v
e
shor
t
distance
in
the
beginning,
b
ut
she
has
no
choice
e
xcept
contin
uing
the
long
distance
at
last.
Thus
,
the
total
tour
might
be
still
relativ
e
long
at
last.
The
second
obser
v
ation
is
to
rely
on
the
total
amount
of
pheromone
in
one
stage-tour
tr
a
v
eled
b
y
each
ants
.
In
this
e
xper
iment,
it
sho
ws
that
the
ant
which
gathered
a
lot
of
pheromone
at
first
stage
tends
to
be
a
good
or
best
ant
in
the
complete
tour
.
The
other
hand,
the
ant
which
get
the
shor
test
distance
probab
ly
gets
the
high
pheromone
on
its
first
stage
.
So
,
it
is
more
reasonab
le
that
total
amount
of
pheromone
at
each
stage
indicates
the
quality
sub-tour
.
The
g
reater
total
pheromone
that
the
ant
achie
v
es
in
one
stage
,
the
ant
has
high
probability
of
getting
the
good
complete
tour
.
So
if
the
amount
at
ear
ly
stage-tour
is
higher
,
the
ant
tends
to
get
the
best
complete
tour
.
Contr
ar
y
,
if
the
pheromone
at
ear
ly
stage-tour
is
lo
w
er
,
the
ant
tends
to
the
w
orst
complete
tour
.
As
a
notion,
this
research
is
perf
or
med
on
three
stages
.
In
our
in
v
estigation,
the
result
of
f
our
or
more
stages
is
not
be
reliab
le
.
It
mean
s
the
pheromone
gathered
b
y
agents
at
first
stage
can
not
be
a
good
judgment
of
quality
agents
.
Exper
iments
are
conducted
to
e
v
aluate
the
perf
or
mance
of
HABCO
.
T
ab
le
1
sho
ws
the
settings
of
v
ar
ious
par
ameters
f
or
the
proposed
algor
it
hm.This
paper
details
tw
o
compar
ison.The
first
one
is
a
compar
ison
HABCO
and
BCO
,
and
the
second
one
is
a
compar
ison
HBCO
and
A
CS
.
All
algor
ithms
are
e
x
ecuted
10
times
and
nine
dataset
benchmar
k
TSP
.
T
ab
le
1.
P
ar
ameter
Setting
of
HABCO
algor
ithm
P
ar
ameter
Symbol
Set
v
alue
n
umber
ant-bee
M
10
n
umber
stage
S
3
iter
ation
nc
1000
deg
ree
pheromone
B
2
par
ameter
local
update
0.1
pheromone
deca
y
0.1
limit
e
xploitation
q
0
10
%
f
actor
r
uin
local
optima
X
0.95
T
ab
le
2
displa
y
the
results
of
all
algor
ithms
and
optimal
solution
(BKS/best
kno
wn
solu-
HABCO:
A
Rob
ust
Agent
on
Hybr
id
Ant-Bee
Colon
y
Optimization
(Ab
ba
Suganda
Girsang)
Evaluation Warning : The document was created with Spire.PDF for Python.
1254
ISSN:
1693-6930
tion)
as
w
ell.
The
first
compar
ison
is
HABCO
and
BCO
.
T
ab
le
4
sho
ws
HABCO+2opt
outper-
f
or
ms
BCO+2opt.
On
some
datasets
(eil51,
kroa1
50,
a280),
HABCO
without
2opt
outperf
or
ms
BCO+2opt.
At
first
HABCO
uses
A
CS
method
(Eq.
(1)
and
Eq.
(2))
to
constr
uct
the
tour
.
A
CS
has
an
adv
antage
to
mak
e
the
edge
more
dynamic
b
y
perf
or
m
local
update
.
With
local
update
,
pheromone
o
n
edge
visited
is
diminished
and
mak
e
it
less
desir
ab
le
.
Theref
ore
the
premature
con
v
erge
can
be
a
v
oided.
As
a
consequence
,
the
agent
(ant)
has
man
y
v
ar
ious
options
to
de-
v
elop
its
tour
.
With
only
ten
agents
,
A
CS
can
get
the
good
quality
tour
.
In
other
hand,
BCO
has
main
adv
antage
on
e
xchange
inf
or
mation
agents
(bees)
on
their
hiv
e
.
Bef
ore
bac
king
to
hiv
e
,
constr
uction
bee
depends
only
the
role
on
Eq.
(7).
It
mak
es
the
selection
candidate
node
is
more
static.
BCO
has
also
a
slightly
comple
x
f
or
m
ula
than
A
CS
,
and
also
has
man
y
v
ar
iab
les
to
set.
The
diff
erence
setting
sometimes
gener
ates
the
diff
erent
sign
ificant
results
.
The
second
compar
i-
son
should
be
discussed
is
compar
ing
HABCO
and
A
CS
.
T
ab
le
4
sho
ws
that
HABCO
outperf
or
ms
A
CS
either
with
2opt
or
without
2opt.
HABCO
also
sho
ws
slightly
better
either
in
a
v
er
age
or
best
case
.
Although
A
CS
and
HABCO
uses
the
same
role
to
constr
uct
the
tour
(Eq.
(1),
Eq.
(2))
at
each
stages
,
HABCO
has
an
adv
antage
in
producing
the
competitiv
e
tour
of
their
agents
b
y
dupli-
cating
the
good
sub
tour
and
discarding
the
bad
sub
tour
in
their
hiv
e
.
Theref
ore
,
in
constr
ucting
the
tour
,
HABCO
has
smar
ter
agents
than
A
CS
.
T
ab
le
2.
P
erf
or
mance
HABCO
,
A
CS
and
BCO
on
nine
benchmar
k
datasets
Bench
BKS
A
CS
A
CS+2opt
BCO+2opt
HABCO
HABCO+2opt
mar
k
A
vg
Best
A
vg
Best
A
vg
Best
A
vg
Best
A
vg
Best
eil51
426
432.4
430
430.3
428
432.1
429
430.7
428
429.1
427
ber
lin52
7542
7715.8
7542
7611.4
7542
7652.6
7542
7577.9
7542
7543.5
7542
st70
675
693.4
684
686.2
680
683.2
675
686.5
680
681.1
678
kroa100
21282
22054.8
21716
21568
21369
21927.3
21369
21789.9
21402
21413.5
21282
eil101
629
649.9
641
643.9
636
656.2
645
643
634
641.7
634
kroa150
26524
27476.9
26889
27219.1
26912
27452.4
27063
27139.1
26881
27015.9
26781
d198
15780
16480.2
16202
16207
15918
16351.5
16021
16421.5
16182
16030
15895
a280
2579
2739.6
2686
2669.9
2640
2834.1
2701
2702.4
2653
2665.1
2630
u724
41910
46363
44688
44136.4
43781
46516.7
44091
45117.8
43901
44002.3
43432
5.
Conc
lusion
HABCO
as
combination
three
algor
ithms
,
A
CS
,
BCO
and
ELU-Ants
,
is
an
aff
ectiv
e
algo-
r
ithm
to
solv
e
the
TSP
prob
lem.
In
solving
TSP
,
HABCO
divides
the
tour
into
some
stages
lik
es
on
BCO
algor
ithm.
In
tour
ing
some
cities
in
a
stage
,
HABCO
uses
the
A
CS
method
from
choos-
ing
the
nodes
,
and
updating
local
and
global
updating
pheromone
.
The
quality
of
each
agents
HABCO
is
judged
based
on
the
pheromone
gathered
at
each
stages
.
The
pheromone
gathered
in
A
CS
algor
ithm
classifies
agent
into
f
ollo
w
er
,
recr
uiter
and
scout
agent
lik
e
on
BCO
algor
ithm.
A
good
judgment
on
premature
step
mak
es
the
probab
ly
good
agent
(ide
ntified
as
recr
uiter)
du-
plicated,
and
t
he
probability
bad
agent
(identified
as
f
ollo
w
er)
is
discarded.
The
scout
agent
is
e
xist
to
maintain
the
ne
w
alter
nativ
e
t
our
.
This
process
gener
ates
the
competitiv
e
agent
in
each
iter
ation.
This
algor
ithm
also
proposed
the
semi-global
update
pheromone
to
adopt
the
ELU-Ants
algor
ithm.Compar
ing
A
CS
and
BCO
,
HABCO
can
solv
e
TSP
prob
lem
better
.
It
can
be
seen
from
solving
some
dataset
TSP
prob
lem
with
local
or
without
local
search.
6.
Ac
kno
wledg
ement
This
ar
ticle
is
etx
ended
v
ersion
of
proceeding
[25]
with
entitled
”A
Hybr
id
Ant-Bee
Colon
y
Optimization
f
or
Solving
T
r
a
v
eling
Salesman
Prob
lem
with
Competitiv
e
Agents
.
Ref
erences
[1]
Dor
igo
M,
Gambardella
L
M.
Ant
Colon
y
System:
A
Cooper
ativ
e
Lear
ning
Approach
to
The
T
r
a
v
eling
Salesman
Prob
lem.
IEEE
T
r
ansactions
on
Ev
olutionar
y
Computation
.
1997;
1(1):
5366.
TELK
OMNIKA
V
ol.
15,
No
.
3,
September
2017
:
1247
1256
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
1255
[2]
Girsang
A
S
,
Tsai
C
W
and
Y
ang
C
S
.
Rectifying
the
Inconsistent
Fuzzy
Pref
erence
Matr
ix
in
AHP
Using
a
Multi-Objectiv
e
Bicr
iter
ionAnt.
Neur
al
Processing
Letters
.2016;
44(2)
:
519-538.
[3]
P
otvin
J
V
,
Genetic
Algor
ithms
f
or
the
T
r
a
v
eling
Salesman
P
rob
lem.
Annals
of
Oper
ations
Research
.
1996;
63
:
339-370.
[4]
Clerc
M.
Discrete
P
ar
ticle
Sw
ar
m
Optimization
Illustr
ated
b
y
The
T
r
a
v
eling
Salesman
Prob
lem.
Ne
w
optimization
T
echniques
in
Engineer
ing
.
2004;
219-239.
[5]
W
ang
K
P
,
Hu
ang
L,
Zhou
C
G,
P
ang
W
.
P
ar
ticle
Sw
ar
m
Optimization
f
or
T
r
a
v
eling
Salesman
Prob
lem
.
Inter
national
Conf
erence
on
Machine
Lear
ning
and
Cyber
netics
.
2003;
15831585.
[6]
Chu
S
C
,
Tsai
P
W
,
P
an,
J
S
.
Cat
S
w
ar
m
Optimization
.
PRICAI
2006:
T
rends
in
Ar
tificial
Intelligence
.
2006;
854-858.
[7]
Lucic
P
.
Modeling
T
r
anspor
tation
Prob
lems
Using
Concepts
of
Sw
ar
m
Intelligence
and
Soft
Computing.
PhD
Thesis
.
Virginia
:
F
aculty
of
the
Virginia
P
olytechnic
Institute
and
State
Uni-
v
ersity;
2002.
[8]
T
eodoro
vic
P
,
Lucic
P
,
Mar
k
o
vic
G,
DellOrco
M.
Bee
Colon
y
Optimization:
Pr
inciples
and
Ap-
plications
.
8th
Seminar
on
Neur
al
Netw
or
k
Applications
in
Electr
ical
Engineer
ing,
NEUREL.
2006.
[9]
W
ong
L
P
,
Lo
w
M
Y
H,
Chong
C
S
.
A
Bee
Colon
y
Optimization
Algor
ithm
f
or
T
r
a
v
elling
Sales-
man
Prob
lem
,
Proceedings
of
Second
Asia
Inter
national
Conf
erence
on
Modelling
and
Sim
u-
lation
(AMS).
2008;
818-823.
[10]
Lucic
P
,
T
eodoro
vic
D
.
V
ehicle
Routing
Prob
lem
with
Un
cer
tain
Demand
at
Nodes:
The
Bee
System
and
Fuzzy
Logic
Approach.
Fuzzy
Sets
in
Optimization
.
2003;
67-82.
[11]
Girsang
A
S
,
Tsai
C
W
,
Y
ang,
C
S
.
A
F
ast
Bee
Colon
y
Optimization
f
or
T
r
a
v
eling
Sales-
man
Prob
lem
.
Third
Inter
national
Conf
erence
on
Inno
v
ations
in
Bio-Inspired
Computing
and
Applications
(IBICA).Kaohsiung.
2012;
7-12.
[12]
Y
u
W
J
,
and
Zhang
J
.
Pheromone-distr
ib
ution-based
adaptiv
e
Ant
Colon
y
System
.
Proceed-
ings
of
the
12th
ann
ual
conf
erence
on
Genetic
and
e
v
olutionar
y
computation.
P
or
tland.
2010.
[13]
Naimi
H
M,
T
aher
inejad
N.
Ne
w
Rob
ust
and
Efficient
Ant
Colon
y
Algor
ithms:
Using
Ne
w
Inter
pretation
of
Local
Updating
Process
.
Exper
t
Systems
with
Applications
.
2009;
36
(1):
481-488.
[14]
Chen
S
M,
Chien
C
Y
.
P
ar
alleliz
ed
Genetic
Ant
Colon
y
Systems
f
or
Solving
The
T
r
a
v
eling
Salesman
Prob
lem.
Exper
t
Systems
with
Applications
.
2011;
38
(4):
3873-3883.
[15]
Chen
S
M,
Chien
C
Y
.
Solving
The
T
r
a
v
eling
Salesman
Prob
lem
B
ased
on
The
Genetic
Sim
ulated
Annealing
Ant
Colon
y
System
with
P
ar
ticle
Sw
ar
m
Optimization
T
echniques
.
Exper
t
Systems
with
Applications
.
2011;
38
(12):
14439-14450.
[16]
Lucic
P
.
Modeling
T
r
anspor
tation
Prob
lems
Using
Concepts
of
Sw
ar
m
Intell
igence
and
Soft
Computing
.
Virginia.
2002.
[17]
T
eodoro
vic
D
,
Lucic
P
,
Mar
k
o
vic
P
,
Orco
M
D
.
Bee
Colon
y
Optimization:
Pr
inciples
and
Ap-
plications
.
8th
Seminar
on
Neur
al
Netw
or
k
Applications
in
Electr
ical
Engineer
ing,
NEUREL
,
2006.
[18]
Lucic
P
,
T
eodoro
vic
D
.
V
ehicle
Routing
Prob
lem
with
Un
c
e
r
tain
Demand
at
Nodes:
The
Bee
System
and
Fuzzy
Logic
Approach.
Studies
in
Fuzziness
and
Soft
Computing
.
2003;
126
:
67-82.
[19]
Kar
aboga
D
,
Bastur
k
B
.
A
P
o
w
erful
and
Efficient
Algor
ithm
f
or
Numer
ical
Fu
nction
Opti-
mization:
Ar
tificial
Bee
Colon
y
(ABC)
Algor
ithm.
Jour
nal
of
Global
Optimization
.
2007;
39(3):
459-471.
[20]
Benatchba
K,
Admane
L,
K
oudil
M.
Using
Bees
to
Solv
e
a
Data-Mining
Prob
lem
Expressed
as
a
Max-Sat
One
.
Ar
tificial
Intelligence
and
Kno
wledge
Engineer
ing
Applications:
A
Bioin-
spired
Approach
.
2005
;
75-86.
[21]
Chong
C
S
,
Lo
w
M
Y
H,
Siv
akumar
A
I,
Ga
y
K
L.
A
Bee
Colon
y
Optimization
Algor
ithm
to
Job
Shop
Scheduling
.
Proceedings
of
Winter
Sim
ulation
Conf
erence
.
2006;
1954-1961.
[22]
F
athian
M,
Amir
i
B
,
Maroosi
A.
Application
of
Hone
y-Bee
Mating
Optimization
Algor
ithm
on
Cluster
ing.
Applied
Mathematics
and
Computation
.
2007;
190
(2),
1502-1513.
[23]
W
ang
J
,
Zhan
g
D
.
Image
Denoising
Based
on
Ar
tificial
Bee
Colon
y
and
BP
Neur
al
Netw
or
k.
HABCO:
A
Rob
ust
Agent
on
Hybr
id
Ant-Bee
Colon
y
Optimization
(Ab
ba
Suganda
Girsang)
Evaluation Warning : The document was created with Spire.PDF for Python.
1256
ISSN:
1693-6930
TELK
OMNIKA
(T
elecomm
unication
Computing
Electronics
and
Control)
.
2015;
13(2)
:
614-
623.
[24]
Meng
L,
Y
in
S
,
Hu
X.
A
Ne
w
Method
Used
f
or
T
r
a
v
eling
Salesman
Prob
lem
Based
on
Dis-
crete
Ar
tificial
Bee
Colon
y
Algor
ithm.
TELK
OMNIKA
(T
elecomm
unication
Computing
Electron-
ics
and
Control)
.
2016;
14(1):342-348.
[25]
Girsang
A
S
,
Tsai
C
W
,
Y
ang
C
S
.
A
Hybr
id
Ant-Bee
Colon
y
Optimization
f
or
Solving
T
r
a
v
eling
Salesman
Prob
lem
with
Competitiv
e
Agents
Proceeding
in
Mobile
,
Ubiquitous
,
and
Intelligent
Computing.
2014;
643-648.
TELK
OMNIKA
V
ol.
15,
No
.
3,
September
2017
:
1247
1256
Evaluation Warning : The document was created with Spire.PDF for Python.