TELKOM
NIKA
, Vol.13, No
.3, Septembe
r 2015, pp. 1
029
~10
3
6
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i3.1806
1029
Re
cei
v
ed Ma
rch 2
8
, 2014;
Re
vised June
12, 2015; Accepte
d
Ju
ne
28, 2015
Application of Ant Colony Algorithm in Multi-objective
Optimization Problems
Juan Li*, Xianghong Tian
Schoo
l of Com
puter Eng
i
n
eeri
ng,Jin
lin
g Instit
ute of T
e
chnol
og
y, Nan
jin
g 2
111
69,Ji
angs
u,Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: iamlj6@
1
6
3
.com
A
b
st
r
a
ct
In actua
l
a
p
p
lic
ation
an
d sc
ien
t
ific rese
arch,
mu
lti-ob
jectiv
e opti
m
i
z
at
ion
is an extre
m
ely
i
m
p
o
rtan
t
researc
h
sub
j
e
c
t. In reality, many issu
es are
relate
d
to the s
i
multa
neo
us op
timi
z
a
t
i
o
n
un
de
r multi-
ob
jectiv
e
cond
itions. T
h
e researc
h
sub
j
ect of mu
lti-o
b
j
ective o
p
ti
mi
zation is
gettin
g
increas
ing
attentio
n. In orde
r to
better solve s
o
me no
nli
n
e
a
r
,
restricted comp
lex
mu
lti-ob
jective o
p
ti
mi
zation pr
ob
le
ms, based o
n
th
e
current stu
d
i
e
s
of
mu
lti-ob
je
cti
v
e o
p
ti
mi
z
a
ti
on
an
d
evol
utio
n
a
ry a
l
gor
ith
m
, this
pap
er
ap
pli
e
s the
a
n
t co
lo
ny
alg
o
rith
m to
multi-o
b
jectiv
e o
p
timi
z
a
ti
on, an
d prov
es
throu
gh ex
peri
m
ent
s that multi-o
b
j
e
ctive a
n
t colo
n
y
alg
o
rith
m ca
n c
onver
ge th
e re
al Par
e
to front
of the st
and
ard
test function
mor
e
q
u
ickly
a
nd acc
u
rately,
and
can als
o
maint
a
in the d
i
strib
u
tivity of the better soluti
on.
Ke
y
w
ords
: ant
colony algorithm
,
multi-object
i
v
e opti
m
i
z
at
ion
,
pareto opti
m
a
l
set
Copy
right
©
2015 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Origin
ated
from the
de
si
gn, pla
n
ing
scal
e, p
r
oj
ect adju
s
tment
and
oth
e
r
essential
deci
s
io
n issu
es of ma
ny complex sy
ste
m
s in real
lif
e, multi-obje
c
tive optimizat
ion ha
s al
wa
ys
been on
e of the importa
nt subje
c
ts
of enginee
rin
g
pra
c
tice a
nd scientific
resea
r
ch. In
the
asp
e
ct
s of
computing
sci
ence, de
cisi
o
n
scie
n
c
e
an
d ope
ratio
n
scien
c
e, the
r
e
once a
ppea
red
much
ce
rtaint
y, randomi
z
at
ion method
s
spe
c
iali
zed
fo
r multi-obj
ecti
ve optimizati
on [1]. In recent
year, along
with the improvement in the cal
c
ul
atin
g sp
eed and
cap
ability of calculation devices,
the appli
c
ati
on of intellig
ent evolution
a
ry alg
o
rith
m
s
in m
u
lti-ob
jective optimi
z
ation, a
s
wi
th
geneti
c
algo
rithm, genetic planing a
n
d
genetic
pro
g
ram d
e
si
gni
ng, etc., has gained
wid
e
confirmation,
whi
c
h
is m
a
inly be
ca
use the
s
e
evo
l
utionary
alg
o
rithm
s
p
r
o
c
ess intelli
ge
nce
feature
s
of se
lf-adaptivity, self-dir
ecte
d le
arnin
g
and
se
lf-org
ani
zing [
2
].
In terms
of m
u
lti-obje
c
tive
optimizatio
n, us
u
a
lly
there are confli
cts and
rest
rain
s
among
different ta
rg
ets of th
e op
timization
pro
b
lem. Th
eref
ore, in
orde
r to maintai
n
balan
ce
amo
n
g
these ta
rg
ets,
the rese
arch
aim of the
al
gorithm
is
to
try bes
t to locate
the o
p
timal set
nea
r th
e
actual
Pareto
front.
Con
s
i
derin
g the
fo
llowe
d d
e
ci
si
on
step, the
solutio
n
s in t
he
solutio
n
se
t
sho
u
ld be di
stribute
d
as
evenly as po
ssi
ble to
increase the diversity of
the possibl
e solu
tion.
Con
s
id
erin
g the effect of a
c
tual ap
plication, t
he time perio
d of se
a
r
chi
ng the Pa
reto solution
set
sho
u
ld be as sho
r
t
a
s
po
ssible
[3].
Mo
st of
the
cu
rrent
studi
es a
dop
t geneti
c
algo
rithm to
explo
r
e
multi-obj
ectiv
e
optimizatio
n, and the
amount
of
studie
s
ad
opting em
erging intellig
e
n
ce
algorith
m
, su
ch a
s
ant col
ony algorith
m
, to expl
ore multi-obj
ectiv
e
optimizatio
n is quite limi
t
ed.
With
characteristi
c
s of im
plicit paralleli
sm and
intelli
gen
ce, ant
co
lony algo
rith
m is q
u
ite
sui
t
able
for optimi
z
ati
on. It can
be
see
n
from th
e cu
rrent
research
re
sults that ant
colo
ny algorith
m
has
good
pe
rform
ance. It is p
r
o
v
ed by practi
ce that th
e
a
pplication of
ant col
ony al
gorithm i
n
sol
v
ing
singl
e-objective problem
s
is very
successful [4]. However, ther
e are still a lot of problem
s to
solve i
n
the
appli
c
ation
of
ant
colo
ny a
l
gorithm
in
m
u
lti-obje
c
tive optimizatio
n. Fields worthy
of
exploratio
n in
clud
e ho
w to sele
ct the init
ial ant col
ony
, how to co
nstruct Pareto o
p
timal sol
u
tio
n
set, ho
w to set the para
m
eters
of any colo
ny al
go
rithm, how to
condu
ct sim
u
l
a
tion expe
rim
ent
and the verifi
cation of rel
a
ted theori
e
s, e
t
c[5].
This
pap
er first explain
ed t
he ba
si
c p
r
in
ciple
s
of m
u
lti-obje
c
tive p
r
o
b
lems an
d an
t colon
y
algorith
m
in detail, base
d
on which, it
provide
d
the compl
e
te pro
c
ed
ure of mu
lti-obje
c
tive ant
colo
ny optimi
z
ation, a
nd
with the sim
u
la
tion, test
an
d
analysi
s
of th
e stan
da
rd te
st fun
c
tion, a
nd
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 1029 – 10
36
1030
the evaluatio
n of pe
rforma
nce
mea
s
u
r
e
m
ent fun
c
tion
, it proved th
e excellent p
e
rform
a
n
c
e
a
n
d
advantag
e of ant colo
ny algorithm in a
s
pect
s
su
ch
a
s
uniformity of solutio
n
distri
bution, etc.
2. Introduc
tion to Multi-o
b
jectiv
e Optimization
Most of the e
ngine
erin
g an
d sci
en
ce p
r
o
b
le
ms are
m
u
lti-obje
c
tive optimizatio
n probl
em
(MOP), which requi
re
s si
multaneo
us
optimizatio
n
of several o
b
j
ects. However, usu
a
lly these
obje
c
ts a
r
e
contradi
cto
r
y. That is, the i
m
provem
ent
of one obj
ect
might wo
rsen
other o
b
je
ct. It is
often impossi
ble to optimize all the obje
c
ts. The
r
efo
r
e, one ca
n o
n
ly try best to coordinate e
a
ch
obje
c
t to optimize all the o
b
ject
s, more
o
v
er, the
optimal of su
ch
probl
em
s often con
s
i
s
ts of the
Pareto optim
al with larg
e, even endl
ess amount [6].
Under restrai
n
conditions,
multi-objective
optimizati
on is also called multi-objective
planin
g
, which can
be
bri
e
fly descri
b
e
d
a
s
: sea
r
chi
ng fo
r a
vector
set
con
s
i
s
ts
of de
ci
si
on
variable
s
, whi
c
h can both
meet the assi
gned rest
ra
int
,
and optimize each
sub
-
o
b
ject fun
c
tion
. In
whi
c
h, the sub-o
b
je
ct function i
s
th
e mat
hemati
c
al de
scri
ption of perfo
rmance sta
n
dard
evaluation. G
enerally,
these
pe
rfor
man
c
e ind
e
xes a
r
e contradi
ctory.
Therefo
r
e,
“multi-o
bje
c
tive
optimizatio
n”
is to
see
k
for
a solution
tha
t
ma
kes the
p
e
rform
a
n
c
e
in
dexes
represented
by all
the
sub
-
obj
ect
functio
n
s a
r
e
rel
a
tively g
ood
sol
u
tion
s a
c
cepta
b
le
for
de
cisi
o
n
ma
ke
rs.
The
mathemati
c
al
descriptio
n
o
f
perform
ance stand
ard ev
aluation i
s
:
mi
n
/
m
a
x
(
)
.
.
(
)
0,
1
,
2,
,
j
fx
s
tg
X
j
m
(
1
)
In the e
quati
on,
1
(
)
[
(
),
,
(
)]
T
N
f
xf
x
f
x
refers to objec
t
func
tion ve
c
t
or
, in
wh
ic
h
,
2
N
is obje
c
t fu
nction
sum,
1
()
[
(
)
,
,
(
)
]
T
m
g
xg
x
g
x
is
m
re
strai
n
ts,
x
is
D
d
i
me
ns
io
n
de
c
i
s
i
on
variables
[7].
MO problem
s requi
re th
e
optimizatio
n
of a set of
o
b
ject fun
c
tion
. Its solution
is not a
singl
e dot, bu
t the set of a
grou
p of dots,
which is call
ed Pareto o
p
timal set.
Pareto optim
al set ca
nnot
be cont
rolle
d by any sol
u
tions in the
possibl
e sol
u
tion set.
Suppo
se
*
x
is
a possible solution, if
*
x
is the Pa
reto
op
timal in
stead
of the
infe
ri
or
sol
u
tion,
whe
n
and o
n
l
y
when there is no
X
(deci
s
io
n variable in t
he feasi
b
le re
gion) m
a
ke
*
x
x
.
The set co
nsi
s
ts of all the
non-i
n
feri
or
solution
s is
ca
lled the Pareto optimal set of the
MOP, and i
s
al
so calle
d the non
-in
f
erior
sol
u
tion set o
r
val
i
d solutio
n
set, defined
as
{,
}
P
xX
x
X
x
x
.
The cu
rved surface whe
r
e
the
Pa
reto o
p
timal
is
located is called the Pareto f
r
ont, A, B
and
C a
s
sho
w
n in
Figu
re
1 are all the
Pareto o
p
tim
a
l, and th
e curved
su
rface
whe
r
e th
ey
are
loc
a
ted is
the Pareto front.
Figure 1. The
pareto optim
al of mu
lti-obj
ective optimization pro
b
lem
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Applicatio
n of Ant Colony A
l
gorithm
in Mu
lti-obje
c
tive Optim
i
zation Problem
s (Ju
an Li)
1031
The set gain
ed throu
gh m
u
lti-obje
c
tive optimizatio
n is the Pareto
optimal set.
Ho
wever,
con
s
id
erin
g t
he
reality, it i
s
n
e
cessa
r
y t
o
combin
e th
e de
ci
sion
m
a
ke
r’s
subje
c
tive requi
rem
ents
for the optimi
z
ed o
b
je
ct wi
th the cal
c
ula
t
ing pro
c
e
s
s to sele
ct the solutio
n
that best me
ets the
deci
s
io
n ma
kers re
quirem
ents from the
non
-inferi
o
r
s
o
lution set, that is
, the
“preferred
s
o
lution”
[8].
3. Basic Prin
ciple of An
t Colon
y
Algorithm
Ant colony al
gorithm
(ACA
) is the si
mul
a
tion algo
rith
m put forwa
r
d throug
h si
mulating
the behavio
r
of ant sea
r
chi
ng for food.
With ma
ssive
careful ob
servation, bi
onici
sts find that a
n
ts
comm
uni
cate
with e
a
ch ot
her th
ro
ugh t
he mate
rial
called p
h
e
r
om
one.
Duri
ng t
he move
men
t
,
ants
ca
n leav
e this mate
ria
l
on th
e road
i
t
passe
d,
an
d
they can
also pe
rceive thi
s
mate
rial, th
us
to guid
e
thei
r dire
ction.
Th
erefo
r
e, the
communi
ty b
e
havior
of a l
a
rge
amo
unt o
f
ants
ha
s th
e
phen
omen
on
of po
sitive f
eedb
ack: the
more a
tou
r
bein
g
p
a
sse
d
by the
a
n
ts, the
bigg
er the
probability of other ants
choosi
ng
thi
s
tour.
The basic principle of
ACA is: si
mulating the real ant
colo
ny coo
p
e
r
ation p
r
o
c
e
s
s ba
se
d on t
he stu
d
y
of food
sea
r
chin
g behavio
r of
real a
n
t col
o
ny.
The al
go
rith
m finds the
sho
r
test to
ur to a
c
hi
eve the
optimi
z
at
ion
throug
h con
s
tru
c
ting
the
solutio
n
tour
together by several ant
s, and l
eaving a
nd exch
angin
g
pheromo
n
e
on the soluti
on
tour to improv
e the quality f the solution [
9
].
3.1. Ant Sy
stem
Ant system i
s
the ea
rlie
st ant col
ony al
gor
ithm. It ap
proximate
se
arching
proce
ss i
s
a
s
follows
:
At the initialization
stag
e,
m
ants a
r
e
ra
ndomly put i
n
the city, the initial value
of the
pheromo
n
e
s
on e
a
ch tou
r
are
same,
suppo
se
0
(0)
ij
a
s
th
e ph
eromon
e
initial valu
e
, then
0
/
m
mL
,
m
L
refe
rs to
the di
stan
ce
of the to
ur
constructe
d
b
y
nea
re
st nei
ghbo
r
heu
rist
ics.
Then, ant
(1
,
2
,
)
kk
m
sel
e
cts th
e city
as the
next tran
sf
er
de
stination a
c
cording to rand
o
m
ratio. The sel
e
ction probability is:
[(
)
]
[
(
)
]
,
[(
)
]
[
(
)
]
()
0,
o
t
h
e
rw
i
s
e
k
ij
ij
k
k
ij
ij
ij
s
a
llo
w
e
d
tt
j
a
llo
w
e
d
tt
pt
In which,
ij
is the pheromon
e
on
(,
)
ij
,
1/
ij
ij
d
is the heuri
s
tic facto
r
of the city
i
- c
i
ty
j
trans
fer,
k
al
l
o
wed
is
the next c
i
ty s
e
t that ant
k
are allowed to visit.
In order to p
r
event the
ant
from vi
siting
t
he al
ready
visited
city, it a
dopts tabu
list
k
t
abu
to reco
rd the
cities that ha
ve already be
en visited by ant
k
. When p
a
ssing
t
, all th
e ants finish
the first circu
l
ation. Cal
c
ul
ate the dista
n
ce
of the tour visited b
y
each ant, and re
se
rve the
sho
r
test di
sta
n
ce, me
an
wh
ile, update th
e phe
rom
one
on ea
ch
sid
e
.
The first i
s
the volatilization
of the ph
ero
m
one. Th
e
seco
nd i
s
the
ants
rele
as
in
g phe
rom
one
on the
sid
e
s they are
pa
ssin
g
throug
h, the equatio
n is a
s
follows:
(1
)
ij
ij
, in which
is the pherom
o
ne volatilization coeffici
ent, and
01
.
1
m
k
ij
ij
ij
k
, in whic
h,
k
ij
is the p
hero
m
one
relea
s
ed on th
e side by the
k
numbe
ra
nt, defined a
s
:
1
/
,
i
f
s
i
d
e(
,
)
i
s
on t
our
0
,
ot
he
r
w
i
s
e
k
ij
k
ij
di
j
T
t
(2)
Acco
rdi
ng to
(2), the
sm
all
e
r the
tour di
st
an
ce
co
nstructed
by th
e ant , the
m
o
re
pheromo
ne g
a
ined
from
e
a
ch
si
de
on t
he tou
r
, an
d i
t
is mo
re
likel
y to be
sel
e
ct
ed by
other a
n
ts
in future iterat
ion.
ij
d
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 1029 – 10
36
1032
After compl
e
ting the first
ci
rcul
ation, em
pty t
he tabu list, turn ba
ck to the initial city, and
prep
are for th
e next ci
rcula
t
ion. Massive
simul
a
tion e
x
perime
n
ts
shows th
at wh
en
solving
small-
scale TSP p
r
oble
m
s, the
performan
ce
of the ant
system is not
bad. It can quickly find the
optimize
d
sol
u
tion. However, alo
ng
wit
h
the i
n
crea
se
of the
scale, the
perf
o
rma
n
ce of
AS
algorith
m
we
ake
n
s
se
rio
u
s
ly, and i
s
e
a
sy to
st
agn
ate. The
r
efore, a la
rge
a
m
ount of im
p
r
oved
algorith
m
for its dra
w
ba
cks
appe
are
d
[10
]
.
3.2. Elite Ant Sy
stem
Elite ant system first put forw
ard by Do
rigo, et. al. is t
he improve
m
ent of the b
a
si
c AS
algorith
m
. Its con
c
e
p
t is to provide extra pheromo
ne for the optimi
z
ed tour after
each ci
rcul
ation.
The ant that finds thi
s
sol
u
tion is called th
e elite ant.
This
best
-
so-f
ar tou
r
is
bs
T
. Th
e extra e
nha
ncem
ent for
bs
T
is gai
ned th
ro
ugh in
crea
sin
g
the phe
romo
ne with the a
m
ount of
/
bs
eL
of each sid
e
on
the
bs
T
. In which,
e
is a para
m
eter,
whi
c
h de
cide
s
the
weight
of
the
bs
T
,
bs
L
is the length of
bs
T
. Then, th
e u
p
dated
equ
ation of
pheromo
ne is:
1
(
1
)
(
1
)
()
()
()
m
kb
s
i
j
ij
ij
i
j
k
tt
t
e
t
(3)
In whi
c
h, the
definition m
e
thod of
()
k
ij
t
is the
same
a
s
befo
r
e, the d
e
finition of
()
bs
ij
t
is:
1
,(
,
)
()
0,
o
t
h
e
r
w
i
s
e
bs
bs
bs
ij
if
i
j
T
L
t
(4)
The
re
sults o
f
Dori
go, et.
al.’s p
ape
r
sh
ows t
hat
usin
g the
elite st
rategy an
d sel
e
cting
a
prop
er
e
ca
n n
o
t only ma
ke
the AS algo
rithm gai
n a b
e
tter solution, b
u
t also
re
du
ce the iteratio
n
amount [11].
3.3. Maximum-Minimum Ant Sy
stem
The maximu
m-minim
u
m
ant system
(M
MAS)is the o
ne of the be
st ACO alg
o
rithms for
solvingTSP
probl
em
s so
far. On the
basi
s
of A
S
, MMAS mainly con
d
u
c
ts the following
improvem
ent: (1) Prevent t
he alg
o
rithm
from conve
r
gi
ng to the l
o
cal optimal to
o
early, it limited
the possible
exohormon
e
con
c
e
n
tration
of each tour
within
mi
n
m
ax
,
, values surp
ass this
rang
e
will be forcef
ully set as
mi
n
or
ma
x
, whi
c
h can eff
e
ctively avoid
the
informati
on volume of
certai
n
tour bein
g
too large
r
than
that
of other tours, thus to avoid
all the ants gathe
ring to the same
tour. (2) Em
phasize the utilization of the optim
i
z
ed
sol
u
tion.
Aftereachiteration, only the
informatio
n o
n
the tou
r
wh
ere th
e o
p
timized
solution i
s
lo
cated
will
be up
dated,
whi
c
h e
nabl
e
s
to
better use the former info
rmation. (3) T
he initia
l value of the pheromone i
s
set
as the up
per l
i
mit
of its ra
nge.
At the begin
n
i
ng of the
alg
o
rithm, when
is smalle
r, the
algo
rithm is
more
ca
pabl
e
of finding th
e batter
sol
u
tion. After all t
he ants compl
e
ting
one iteration,
update all
the
informatio
n o
n
the tour a
c
cordin
g to Equ
a
tion (5
):
(
1
)
(
1
)
()
()
,
(
0
,
1
)
be
st
ij
ij
ij
tt
t
(5)
1
,
i
f
side
,
i
s
inc
l
ude
d in the
optim
iz
e
d
tour
0,
o
t
h
e
r
w
i
s
e
be
st
be
s
t
ij
ij
L
(6)
The allo
wed
update
d
tour
can be the gl
obal opt
imi
z
e
d
solution, o
r
the optimize
d
solution
of this ite
r
atio
n. The
pra
c
ti
ce
prove
d
th
at gra
dual i
n
crea
se
of the
usa
ge frequ
e
n
cy of the
glo
bal
optimize
d
sol
u
tion ena
ble
s
the algorithm
to perform b
e
tter [12].
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Applicatio
n of Ant Colony A
l
gorithm
in Mu
lti-obje
c
tive Optim
i
zation Problem
s (Ju
an Li)
1033
3.4. Ant Colon
y
Optimization Base
d on Rank
Ant system b
a
se
d on ra
nk (ASRANK) i
s
t
he improvement of AS
algorith
m
. Its con
c
ept
is: after every iteration, the tour passed by the
ant
s will be
ranked from
small
to large, that
is,
12
(
)
()
()
m
Lt
L
t
L
t
. The tour wil
l
be weighte
d
accordi
ng to
its length, the sho
r
ter the
length,
the big
ger th
e weight [1
3]. The
wei
ght
of the gl
obal
optimize
d
sol
u
tion i
s
w
, the
weig
ht of the
numbe
r optim
ized
solutio
n
is
ma
x
{
0
,
}
wr
, and then the phe
rom
o
n
e
update rule
of ASRANK is:
1
1
(
1
)
(
1
)
()
(
)
()
()
,
(
0
,
1
)
In
w
h
i
c
h
,
(
)
1
/
(
)
,
(
)
1
/
w
rg
b
ij
ij
ij
ij
r
r
r
gb
gb
ij
ij
tt
w
r
t
w
t
tL
t
t
L
(7)
3.5. An
y
Colon
y
Sy
stem
Any colony system(A
C
S)is the improved
ant co
lony algorithm put forward by Do
rigo, et.
al. There a
r
e
three
differe
nce
s
b
e
twe
e
n
it and AS:
(1) It ado
pts t
he differe
nt tour
sele
ction
rule,
whi
c
h can better use the
search
ing ex
perience accumulated by
the ant. (2) T
he volatilizati
o
n
and
re
seali
n
g
of ph
ero
m
on
e will
be
only
co
ndu
cted
o
n
the
sid
e
of
the be
st-so
-
far tou
r
. Th
at
is,
after every iteration, only the best ant so far is
allo
wed
to release ph
erom
one. (3
)
Except for the
global p
hero
m
one up
date
rule, it also
a
dopts the lo
cal pheromo
n
e
update rul
e
.
In ACS, ant
k
l
o
cat
e
d in
cit
y
i
sel
e
ct
s cit
y
j
as th
e
next city to be vi
sited a
c
co
rding
to
the pse
udo ra
ndom ratio rul
e
. The tour selectio
n rule i
s
provid
ed by
the following
equatio
n:
0
arg
m
a
x
[
]
,
i
f
,o
t
h
e
r
w
i
s
e
il
il
qq
j
J
(8)
()
()
()
(
)
()
0
k
ij
ij
k
k
ij
ij
ij
s
a
llowe
d
tt
if
j
a
llowe
d
tt
pt
el
s
e
(
9
)
In which,
q
is a
rando
m vari
able evenly d
i
stribute
d
in
[0
,
1
]
,
00
(0
1
)
qq
is a paramete
r
.
J
is a ran
dom
variable g
e
n
e
rated by th
e prob
ab
ility distrib
u
tion p
r
ovided by E
quation (9) (i
n
whi
c
h,
1
).
The ACS glo
bal phe
rom
o
n
e
update rule
is:
(1
)
,
(
,
)
bs
bs
ij
ij
ij
ij
T
(10)
1/
bs
bs
ij
C
(11)
The ACS local pheromo
n
e
update rul
e
d
e
fines:
Duri
ng the
proce
s
s of tou
r
con
s
tructi
o
n
, whe
never th
e ant pa
sse
s
a sid
e
(,
)
ij
, it will
immediately
use thi
s
rule t
o
update the
pheromo
ne o
n
the side:
0
(1
)
ij
i
j
(12
)
In which,
and
0
are two pa
rameters,
meets
01
,
0
is the i
n
itial value of the
pheromo
ne a
m
ount. The functio
n
of local updat
e is that when
ever the ant passesside
(,
)
ij
, the
pheromo
n
e
ij
on this side
wil
l
redu
ce, thus to reduce
the prob
ability of other ants
sele
cting this
side [14].
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 1029 – 10
36
1034
4. The Design of Multi-obj
ectiv
e Ant C
o
lony
Optim
i
zatio
n
The
sub
-
obj
e
c
ts of th
e M
O
P are
co
ntradi
cto
r
y. The
improvem
en
t of one
sub
-
obje
c
t
might wea
k
e
n
the performance of another o
b
je
ct
or other o
b
ject
s. In other word
s, it is
impossibl
e to
optimi
z
e
sev
e
ral
sub-obje
c
ts
at th
e
sa
me time. In
st
ead, it
can
o
n
l
y coo
r
din
a
te
and
comp
romi
se
among the
m
. The re
alization pro
c
ed
ure
of multi-obje
c
tive ant colon
y
optimization
is
all follows
[15]:
(1) Even th
e
ra
ndomly
ge
nerate
d
initia
l
ant colo
ny pop with a scale
of
N
, cal
c
ulate
each ant obje
c
tive function
()
,
1
,
2
,
,
i
f
xi
k
and the re
strain functio
n
,1
,
2
,
j
ej
J
in the pop.
(2) S
epa
rate
the non
-fea
si
ble solution
set
({
|
(
)
0
}
)
imp
Xx
P
O
P
e
x
from the feas
ible
solut
i
o
n
set
({
|
(
)
0
}
)
f
Xx
P
O
P
e
x
.
(3) Iterate the feas
ible
s
o
lut
i
on s
e
t
f
X
in the initial solution.
(4) Initialize the external
set BP, its initial
value i
s
t
he n
on-co
ntrol solution i
n
all the
feasibl
e
sol
u
tions of po
p. That is,
{|
(
)
0
}
,
{
|
,
}
ff
f
X
xP
O
P
e
x
B
P
x
X
x
X
X
X
.
(5) Set the ite
r
ation time
0
c
N
.
(6) ma
ke
1
i
.
(7) A ra
ndo
m numbe
r
p
within the ra
nge of [0,1] is gene
rate
d, comp
are i
t
with
para
m
eter
0
p
,
0
p
is a p
a
ramete
r within
the
ra
nge
of [0,1].
Whe
n
0
pp
, let the current
ant
i
to
optimize
ba
sed o
n
the
gui
dan
ce
of t
he global optimi
z
ed
expe
rien
ce,
wh
en
0
pp
, let ant
i
to
optimize th
ro
ugh ph
eromo
ne exch
ang
e
.
It can be seen that, the
large the
0
p
, the large the
prob
ability of adoptin
g the global o
p
timized experi
e
n
c
e.
(8) Move
ant
i
within
its a
c
tivity range,
and
add
a
random
pe
rturbation
on its f
i
nal
positio
n. Ree
v
aluation ant
i
, calcul
ate its obje
c
tive function and re
strain functio
n
.
(9)
Up
date th
e optimized
experie
nce set BP, if ant
i
is fea
s
ible
solution, an
d i
s
no
n-
control to
set
BP. Then in
clud
e ant
i
into set BP, an
d
delete th
e
solution
s in th
e set that are
controlled by
i
.
(10
)
1
ii
, if
iN
, then turn to step (7).
(11
)
1
tt
, if
t
is sm
aller tha
n
the
maximum ite
r
ation time, t
u
rn to
step
(6
), otherwi
se,
end the alg
o
ri
thm.
5. Ev
aluation of the Per
f
ormance o
f
the Multi-obj
ectiv
e Ant Colon
y
Optimizatio
n
Table 1. 4 Standa
rd Te
st Functio
n
s
Problem Dimension
Range
Ob
jective function
Convergence
SCH 1
[-103,103]
2
1
2
2
()
()
(
2
)
fx
x
fx
x
Convergent
PO
L
3
[,
]
22
11
1
2
2
22
21
2
1
2
2
()
[
1
(
)
(
)
]
()
[
(
3
)
(
1
)
]
0.
5
s
i
n
1
c
os
1
2
si
n
2
1.
5
c
os
2
0.
5
s
i
n
1
2
c
o
s
1
s
i
n
2
1.
5
c
os
2
1.
5
s
i
n
1
c
os
1
2
si
n
2
0.
5
c
os
2
fx
A
B
A
B
fx
x
x
A
A
xx
x
x
Bx
x
x
Non-
convergent,
non-continuous
ZDT1
30
[0,1]
11
1
2
2
()
()
(
)
[
1
]
()
()
1
9
(
)
/
(
1
)
n
i
i
fx
x
x
fx
g
x
g
x
gx
x
n
Convergent
ZDT3
30
[0,1]
6
11
1
2
21
0.
25
2
()
1
e
x
p
(
4
)
s
i
n
(
4
)
()
()
[
1
(
(
)
/
()
)
]
(
)
1
9
[(
)
/
(
1
)]
n
i
i
f
xx
x
f
x
gx
f
x
gx
gx
x
n
Convergent,
continuous
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Applicatio
n of Ant Colony A
l
gorithm
in Mu
lti-obje
c
tive Optim
i
zation Problem
s (Ju
an Li)
1035
In order to te
st the
pe
rformance
of the
algo
rit
h
m,
t
h
is
p
ape
r sel
e
ct
ed 4 cla
ssi
cal
t
e
st
function
s to t
e
st the im
pro
v
ed mu
lti-o
b
j
e
ctive ant
col
ony optimi
z
at
ion, whi
c
h i
n
clud
es th
e m
o
st
rep
r
e
s
entativ
e issu
es in Z
D
T test functi
on. The
sele
cted test fun
c
tion
s are
sh
own in Figu
re 1.
The
simul
a
tio
n
re
sult
s a
r
e
sh
own in
Fi
gure
2. All t
he te
st fun
c
tions gai
ned
satisfying Pa
reto
front. The m
a
in pa
ramet
e
r value
s
of
the algor
ith
m
: ant amo
unt=1
00, opti
m
ization tim
e
of
pheromo
n
e
=
150, optimization time of global
experie
nce=5, ant st
ep le
ngth=0.8, global
experie
nce
step len
g
th=0.7, pe
rturb
a
tioncoefficie
n
t=0.4, volatili
zation
coeffici
ent=0.0
1, ni
che
radiu
s
=0.01,
phe
rom
one
minimum
=0.001, p
h
e
r
om
one
maximu
m=0.3,
phe
romone
he
uri
s
tic
fac
t
or
1
, expect
a
tion heu
risti
c
facto
r
3
.
(a) Pa
reto fro
n
t gained by test functio
n
SCH
(b) Pa
reto fro
n
t gained by test functio
n
POL
(c) Pareto fro
n
t gained by test functio
n
Z
D
T1
(d) Pa
reto fro
n
t gained by test functio
n
Z
D
T3
Figure 2. Pareto front gain
ed by test function
s
It can be se
en from Figu
re 2 that the non-infe
rio
r
solutio
n
set gaine
d throu
gh thi
s
algorith
m
is
cl
ose
s
t to the o
p
timal set fro
n
t, and maint
a
ins g
r
e
a
t ad
vantage in th
e aspect of e
v
en
distrib
u
tion, whi
c
h is mai
n
ly beca
u
se this algo
rithm
’
s sel
e
ctio
n of local an
d global o
p
timize
d
solutio
n
main
tains the diversity of optimized
solutio
n
, and is co
mbined
with the con
c
e
p
ts of
individual di
stance al
gorit
hm and n
on-inferio
r
opt
im
al cont
rol, which
sele
cts
the optimal
set
accurately, to make it distri
bute evenly,
therefo
r
e, pe
rform
s
relativel
y
well.
6. Conclusio
n
No matte
r i
n
the ap
plication of scie
ntific
re
sea
r
ch or e
ngin
e
e
ring, m
u
lti-obje
c
tive
optimizatio
n i
s
a very imp
o
rtant research
subje
c
t, b
e
ca
use in m
any real life
appli
c
ation
s
, it is
often re
quire
d to optimi
z
e
many an
d o
ften cont
radi
ctory obje
c
ts
at the sa
me
time. In orde
r to
solve thi
s
m
u
lti-obje
c
tive
optimizatio
n
probl
em
, this pape
r ha
s
put forward
the ant colo
n
y
algorith
m
, and fully proved the efficien
cy and exce
ll
ent performa
n
ce of the multi-obje
c
tive ant
colo
ny optimization with
tests from its pivota
l op
erato
r
s to st
anda
rd test function
s, an
d
evaluation
of perfo
rman
ce measurement
index.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 1029 – 10
36
1036
Referen
ces
[1]
Giacomo F
ili
p
po Porzi
o
, Gianl
uca Nastas
i, Valenti
na C
o
lla, Marco V
ann
ucci, T
e
resa Annu
nziat
a
Branca. Comparison of Multi-obj
ective Opt
i
mization T
e
chniques
Applied to Off-gas
Management
w
i
t
h
in A
n
Integ
r
ated Steel
w
o
r
k
.
Applie
d Ener
gy
. 2014; 1
36(
31): 108
5-1
097
.
[2]
Z
o
rka Nov
a
k
Pintari
č
, Z
d
rav
k
o Krava
n
j
a
. Suitab
le Pr
oc
ess
Mod
e
ll
in
g
for Prop
er
Multi-Objectiv
e
Optimization of Pr
o
c
e
ss Fl
ow
Sh
ee
ts.
Co
mp
uter Ai
de
d
Che
m
ic
al E
ngi
neer
ing
.
201
4;
33(6): 1
3
8
7
-
139
2.
[3]
Cherif
Laro
u
ci,
Kamal E
jja
bra
oui, Pi
erre
Lef
ranc
, et al. Im
pact of the
Co
ntrol C
onstrai
n
t
on A Buck
Conv
erter
Des
i
gn
B
a
sed on Multio
bjectiv
e
Optimizatio
n
P
r
oced
ure.
Inter
natio
nal J
our
n
a
l of Pow
e
r
Electron
ics an
d Drive Syste
m
s
. 2012; 2(3): 257-
266.
[4]
Hossei
n
Hem
m
atian, Abd
o
lh
ossei
n
F
e
reid
o
on, A
li Sad
o
ll
a
h
, Ardeshir Ba
hrei
nin
e
ja
d. Optimizati
on of
Lami
nate Stac
king S
equ
enc
e
for Minimiz
i
ng
W
e
ight a
nd C
o
st Usin
g Elitis
t Ant
Sy
stem Optimization.
Advanc
es in E
ngi
neer
in
g Softw
are
. 2013; 57
(3): 8-18.
[5]
RM Rizk-Al
lah,
Elsa
ye
d M Z
a
ki, Ahme
d Ah
med El-S
a
w
y.
H
y
brid
izin
g An
t Colo
n
y
Opti
mizatio
n
w
i
t
h
Firefly
Algorithm for Unc
onst
r
ain
ed Optimiz
a
tion Pr
ob
lem
s
.
Appli
ed
M
a
the
m
atics an
d Co
mp
utation
.
201
3; 224(
1): 473-4
83.
[6]
A Sadig
h
man
e
sh, K Z
a
re,
M Sabah
i. Distribut
ed Gen
e
ratio
n
Unit a
nd Ca
pacitor
Placem
ent fo
r
Multio
bjectiv
e
Optimization.
Internati
o
n
a
l Jo
urna
l of El
ectr
ical a
nd C
o
mp
uter Eng
i
n
eeri
n
g
. 20
12; 2(
5)
:
615-
620.
[7]
Qi Z
hang, Gua
ngch
un Ya
ng,
Rui T
ang, et al
.
Multi Objectiv
e Optimizatio
n
Algorithms D
e
sign Bas
ed
on Sup
port V
e
ctor Regr
ess
i
on Metam
o
d
e
ling.
T
E
LKOM
NIKA Indon
es
ian Jo
urna
l o
f
Electrical
Engi
neer
in
g
. 2013; 11(
11): 64
06-6
412.
[8]
KZ
Gao, PN
Suga
ntha
n, QK Pan, T
J
Ch
ua,
T
X
C
a
i, C
S
Ch
ong. P
a
r
e
to-Base
d
Gro
upi
ng
Discret
e
Harmon
y
Se
ar
ch Alg
o
rithm
for Multi-Ob
ject
ive Fle
x
ibl
e
J
o
b Sh
op Sc
he
d
u
lin
g.
Infor
m
ati
on Sci
enc
es
.
201
4; 289(
24): 76-9
0
.
[9]
Khalid M Salama, Alex
A Frei
tas. Cl
assific
a
tion
w
i
th
Clu
ster-Based
Ba
yes
i
a
n
Multi-
N
e
ts usin
g An
t
Colony
Optimisation.
Sw
arm a
nd Evol
utio
nar
y Computati
o
n
.
2014; 1
8
(10):
54-7
0
.
[10]
Alberto C
a
n
o
, Juan L
u
is Ol
mo, Sebastiá
n
Vent
ura. Par
a
lle
l Multi-Ob
j
e
ctive Ant Pro
g
rammin
g
for
Classification using GPUs.
Jo
urna
l of Parall
e
l
and D
i
stribute
d
Co
mp
uting
. 2
013; 73(
6): 713
-728.
[11]
T
i
anshun H
u
a
ng. Optimizati
on of R
outin
g
Prot
ocol i
n
W
i
reless Se
ns
or Net
w
orks
b
y
Improv
ed A
n
t
Colo
n
y
and
P
a
rticle S
w
a
rm
Algorit
hm.
T
E
L
K
OMNIKA Ind
ones
ian
Jo
urn
a
l of E
l
ectric
al
Engi
ne
erin
g
.
201
4; 12(1
0
): 7486-
749
4.
[12]
Askar Ba
gher
i
nasa
b
, Mahm
o
ud Z
a
deh
ba
gh
eri, Sa
if
uln
i
za
m Abd
u
l K
hal
i
d
, et a
l
. Optim
a
l Pl
acem
ent
o
f
DST
A
T
C
OM
Using
H
y
b
r
id
Genetic
an
d
Ant Co
lo
n
y
Al
gorithm
to
Lo
sses R
educti
o
n
.
International
Journ
a
l of App
l
ied Pow
e
r En
gi
neer
ing
. 2
013;
2(2): 53-6
0
.
[13]
Len
in Kan
a
g
a
s
aba
i, B Ravind
ranath R
edd
y,
M Sur
y
a Ka
lav
a
thi. Optimal P
o
w
e
r F
l
o
w
us
in
g Ant Colo
n
y
Search Al
gorit
hm to Evaluat
e Loa
d Curtai
lment Inco
rp
or
ating Vo
ltag
e Stabil
i
t
y
Mar
g
i
n
Criterio
n.
Internatio
na
l Journ
a
l of Electr
ical a
nd Co
mp
uter Engi
ne
erin
g
. 2013; 3(
5): 603-6
11.
[14]
Che
ngmi
ng Qi
. Vehicle R
o
u
t
ing Optimizati
on in L
ogistic
s Distributio
n Using H
y
b
r
i
d
Ant Colo
n
y
Algorit
hm.
T
E
LKOMNIKA Indones
ian J
ourn
a
l of Electrica
l
Engi
neer
in
g
. 2013; 11(
9): 530
8-53
15.
[15]
Juan
Ra
da-Vi
l
e
la, Ma
nu
el C
h
ica, Óscar C
o
rd
ó
n
, Serg
io
Damas. A
C
o
mpar
ative St
ud
y of M
u
lti-
Objective Ant
Colo
n
y
Optimi
zation Al
gorit
h
m
s for
T
he
T
i
me and Sp
ac
e Assembl
y
L
i
ne Bal
anci
n
g
Probl
em.
Appli
ed Soft Co
mp
u
t
ing
. 201
3; 13(
11): 437
0-4
382
.
Evaluation Warning : The document was created with Spire.PDF for Python.