TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.6, Jun
e
201
4, pp. 4413 ~ 4
4
1
8
DOI: 10.115
9
1
/telkomni
ka.
v
12i6.547
6
4413
Re
cei
v
ed
De
cem
ber 2
2
, 2013; Re
vi
sed
Febr
uary 14,
2014; Accept
ed Feb
r
ua
ry
27, 2014
An Improved NSGA-II Algorithm for Multi-objective
Traveling Salesman Problem
Yabo Luo*
1,2
, Min Liu
3
, Zh
ongxiao Hao
4
, Dongbo Liu
1
1
Departme
n
t of Computer a
n
d
Communic
a
ti
o
n
, Huna
n Institute of Engi
neer
ing,
Xi
an
gtan 4
111
04, Chi
n
a
2
Colle
ge of T
r
ansportati
on a
n
d
Log
istics, Ce
ntral S
outh U
n
i
v
ersit
y
of F
o
re
str
y
an
d T
e
chnolo
g
y
,
Cha
ngsh
a
41
0
004, Ch
in
a
3
School of Co
mputer Scie
nc
e and En
gi
neer
ing, Hu
na
n Uni
v
ersit
y
of Sci
e
n
c
e and T
e
chno
log
y
,
Xi
an
gtan 4
112
01, Chi
n
a
4
School of Infor
m
ation Sci
enc
e and El
ectrica
l
Engi
neer
in
g, Heb
e
i Un
iversit
y
of Eng
i
ne
eri
n
g,
Han
dan 056
00
2,
Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: luo
y
a
bo@fo
xmail.com
A
b
st
r
a
ct
Multi-ob
jectiv
e
traveli
ng s
a
l
e
sman
pro
b
le
m (MOT
SP) i
s
an
extend
e
d
insta
n
ce
of traveli
n
g
sales
m
an
prob
le
m (T
SP), w
h
ich is
a w
e
ll-k
now
n NP
har
d
pro
b
le
m. In
th
is pa
per,
an
i
m
pr
ove
d
NSG
A
-II
alg
o
rith
m (
d
e
n
o
ted
by INSG
A-II-MOT
SP) i
s
pro
pose
d
to
solve
the
MOT
SP. Specific
all
y
, a l
a
yer
strateg
y
accord
ing
t
o
nee
d
is prop
o
s
ed
to avoi
d gen
eratin
g
unn
e
c
e
s
sa
ry no
n-d
o
m
i
na
te
d fron
ts. Th
e
a
r
ena’
s
princi
pl
e is
al
so ad
opte
d
to
construct n
o
n
-do
m
i
nat
e
d
s
e
t, so as to r
educ
e the c
o
unt of d
o
m
in
a
n
ce
comparis
on. In
add
itio
n, an
or
der cross
o
ver
l
i
ke o
per
ator a
n
d
an
inv
e
rsi
on
mutati
on
op
era
t
or are
ado
pte
d
for MOT
SP. The
exper
i
m
e
n
t resu
lts
show
that
the pro
p
o
s
ed
INSGA-II-MO
T
SP algor
ithm is
ab
le t
o
fi
n
d
better sprea
d
o
f
solutions co
mpare
d
to other three a
l
gor
ith
m
s.
Ke
y
w
ords
:
mu
lti-ob
jectiv
e
evoluti
onary
alg
o
rith
m, laye
r st
rategy accordi
ng to ne
e
d
, arena
’
s
pri
n
cipl
e,
mu
lti-ob
jectiv
e traveli
ng sal
e
s
m
a
n
pro
b
le
m
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Multi-obj
ectiv
e
problem
s
(MOPs) a
r
ise
in a n
a
tural f
a
shi
on in
mo
st discipli
ne
s
and thei
r
solutio
n
ha
s
been
a chall
enge to
re
se
arche
r
s fo
r a
long time [1
]. The prese
n
ce
of multip
le
obje
c
tives in
a probl
em, in
princi
ple, gives ri
se to a set of optimal solutio
n
s (l
argely kno
w
n a
s
Pareto-optim
al solutio
n
s), instead of a
single o
p
tim
a
l solutio
n
. In the absen
ce of any further
informatio
n, one of the
s
e
Pareto-optim
al solu
tio
n
s
cannot be
sai
d
to be bette
r than the ot
her.
This dem
and
s a
u
s
e
r
to
find a
s
ma
ny Pareto
-op
t
imal solutio
n
s
as po
ssi
b
le. Th
e u
s
e of
evolutiona
ry algorith
m
s (EAs) to solv
e MOPs
ha
s been motivated mainly becau
se of the
popul
ation-ba
sed n
a
ture of
EAs whi
c
h a
llows the ge
n
e
ration
of se
veral elem
ent
s of the Pare
to
optimal set in a sin
g
le run. To date
ther
e have
been ma
ny evolutionary
multi-obje
c
ti
ve
optimizatio
n (EMO) algo
rit
h
ms p
r
op
ose
d
for mu
lti-o
b
jective opti
m
ization p
r
o
b
lems. Amon
g of
them, the
No
n-do
minate
d
sortin
g g
eneti
c
al
gorithm
II (NS
G
A-II) [2
] is well-kn
o
w
n
and i
s
bei
ng
most wid
e
ly used.
Travelin
g Sa
lesma
n
Prob
lem (TSP
) i
s
a
cla
ssi
c
NP hard p
r
obl
em in
co
mbi
nation
optimizatio
n domain. Give
n
a colle
ctio
n
of
citie
s
a
n
d
the
co
st of travel bet
we
en ea
ch
pai
r o
f
them, the TSP is to find the ch
eape
st way of visi
ting all of the cities and returning to starti
ng
point. More f
o
rmally, it ca
n be re
pre
s
e
n
ted by a co
mplete weigh
t
graph,
G
= (
N,E
) with
N
being
the set of
citi
es
and
E
th
e
set
of e
dge
s fully conn
ect
i
ng the
n
ode
s
N
.
Ea
ch e
d
g
e
is assign
ed
a
value
d
ij
, whi
c
h is th
e len
g
th of edge
e
ij
∈
E
. The T
SP is probl
e
m
of finding
a minimal le
ngth
Hamiltoni
an circuit of the graph, wh
ere a
Hamiltoni
an
circuit is a
clo
s
ed tour visitin
g
exactly once
each of the
n
= |
N
| cities of
G
.
Much
of the
work
on th
e
TSP is m
o
tivated by its u
s
e
as
a pl
atform fo
r the
study of
gene
ral m
e
th
ods that can
be a
pplie
d to a
wide
ra
n
ge of di
scret
e
optimi
z
atio
n problem
s.
The
TSP naturall
y
arise
s
a
s
a su
b proble
m
in m
any transportatio
n
and lo
gisti
c
s appli
c
ation
s
,
for
example the
probl
em of arrangi
ng
sc
ho
ol bus
route
s
to pick u
p
th
e child
re
n in a school
district.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4413 – 4
418
4414
More
re
cent
appli
c
ation
s
i
n
volve the de
livery of
meal
s to ho
meb
o
u
nd pe
rson
s a
nd the
routin
g of
trucks for parcel post pickup. Therefore, in
recent years,
many
intelligent optimizat
ion
algorith
m
s, such a
s
evolu
t
ionary algo
rit
h
m (EA)
[3], ant colo
ny algorithm
(ACO) [4-5], pa
rticle
swarm optimi
z
ation (PSO
) algorithm [6] and simulate
d anneali
ng (SA) algorith
m
[7]
and so on,
were propo
se
d to solve the
TSP problem
.
Multi-obj
ectiv
e
traveling
salesm
an p
r
o
b
lem (M
OTS
P
) is an exte
nded in
stan
ce of TSP.
Given a
co
m
p
lete, wei
ght
ed g
r
ap
h
G
=(
N,E,c
) with being the set of
N
no
de
s,
E
being
th
e set o
f
edge
s fully conne
cting th
e
node
s, an
d
c
bei
ng a fu
n
c
tion that a
ssigns to
ea
ch
edge
(
i
,
j
)
∈
E
a
vec
t
or
c
c
k
ij
ij
,...,
1
, where each elem
ent
c
k
ij
corre
s
p
ond
s to a ce
rtain mea
s
u
r
e like di
stan
ce,
co
st, etc.
bet
wee
n
n
ode
s
i
and
j
. Fo
r t
he follo
win
g
we
assu
me t
hat
c
c
k
ji
k
ij
for all
p
a
irs of
node
s
i
,
j
and
o
b
j
ec
tive
s
k
, that is,
we
con
s
id
er
onl
y symmetri
c
probl
em
s. Th
e MOTSP i
s
also
the pro
b
lem
of finding “mi
n
imal”
Hamilt
onian
circuit
s
of the grap
h, that is, a set
of closed to
urs
visiting each of the
n
= |
N
| node
s
of
G
exactly once; h
e
re “mi
n
imal
” refers to the notion of Pareto
optimality.
A
numb
e
r of studie
s
we
re con
d
u
c
ted
in
the
mult
i-obje
c
tive optimi
z
a
t
ion literatu
r
e.
In [8],
a dyna
mic m
u
lti-obje
c
tive
particl
e
swarm optimi
z
e
r
(PSO),
maximinPSOD,
w
h
ic
h
is se
l
f
-
a
dap
ti
ve
and capabl
e of handling d
y
namic multi-obje
c
tive opt
imization p
r
ob
lems, wa
s propo
sed. In [9],
Goh an
d Tan
sugg
este
d a new dyna
mic multi-obje
c
ti
ve coevolutio
nary algo
rith
m that hybridize
s
comp
etitive and co
ope
rative mech
ani
sm
s.
Re
cently, so
me resea
r
ch
e
r
s have
de
sig
ned EM
O al
g
o
rithm
s
to
de
al with
MO
TSP in [10
-
15]. In this paper, an imp
r
o
v
ed NSGA-II algorith
m
(de
noted by INSGA-II-MOTS
P) is pro
p
o
s
e
d
to
s
o
lve the MOTSP. To improve the run-time effic
i
enc
y
of NSGA-II, a layering
s
t
rategy acc
o
rding
to nee
d is propo
sed to
av
oid ge
ne
ratin
g
un
necessa
ry non
-do
m
in
ated fro
n
ts,
and th
e a
r
en
a’s
prin
ciple i
s
al
so ad
opted t
o
con
s
truct n
on-d
o
min
a
ted
set. In addition, an order
cro
s
sove
r like
operator
and
an inve
rsi
o
n
mutation o
p
e
rato
r a
r
e d
e
sig
ned fo
r t
he MO
TSP. The exp
e
rim
ent
results sho
w
that the proposed INSG
A-II-MOTSP
algorith
m
is able to find better sp
re
ad
of
solutio
n
s
com
pare
d
to othe
r three al
gorit
hms.
2. R
e
lated
Work
First, assu
me
the size of set
P
is
n
, each individual i
n
P
has
r
attri
butes, an
d
f
k
( ) is an
evaluation fu
nction (
k
=1,
2
,
…
,
r
).
Defini
tion 1
(Pareto
Do
minance)
:
x
,
y
∈
P
, if
)
(
)
(
y
f
x
f
k
k
, (
k
=
1
,2,…,
r
), and
}
,
,
2
,
1
{
r
l
su
ch
t
hat
)
(
)
(
y
f
x
f
l
l
, then
x
domi
n
ates
y
(d
enot
ed
x
y
). Her
e
‘
’ r
e
pr
es
en
ts
domina
n
ce re
lationship, an
d
y
is a do
minated individ
ual.
Defini
tion 2
(No
n
-dom
i
n
ate
d
se
t)
:
x
∈
P
, if
y
∈
P
,
x
y
, then
x
is a n
on-
dominate
d
in
dividual
of
P
. The
set con
s
istin
g
of
all t
he n
on-domi
nated i
ndivid
uals of
P
i
s
called
the non-domi
nated set of
P
.
One
popul
ar
way of d
e
si
g
n
ing EM
O al
gorithm i
s
fi
st to con
s
truct
non
-domi
nat
ed
set,
and the
n
ma
ke
sele
ction,
cro
s
sove
r, an
d mutation
o
n
the po
pulati
on set
P
to g
enerate the
n
e
xt
gene
ration. S
o
co
nstructin
g
the non
-d
o
m
inated
set
i
s
an ve
ry imp
o
rtant ste
p
fo
r EMO alg
o
rit
h
ms
to find the final Pareto opti
onal solution
s. In
the NSGA-II algorith
m
, a non-d
o
m
inated
sorti
ng is
use
d
to so
rt a popul
ation i
n
to different
non-domi
nat
e
d
levels, an
d this sorting p
r
ocedu
re’
s
time
compl
e
x
i
t
y
is
O
(
rN
2
). In n
e
xt se
ction, a
n
imp
r
oved
NSGA
-II al
go
rithm i
s
p
r
o
p
o
se
d to
solve
the
MOTSP problem. To reduc
e
the
run-time of t
he non-dominated s
o
rting of the NSGA
-II, an
improve
d
no
n
-
domi
nated
sorting i
s
p
r
op
ose
d
by
u
s
in
g a layer strategy acco
rdin
g to nee
d an
d
an
aren
a’s p
r
in
ci
ple.
3. INSGA-II-MOTSP
Algorithm
The main fra
m
e of the INSGA-II-
MOTS
P algorithm is as follows:
Algorithm
INSGA-II-MOTSP
(1)
Read the
input data (th
e
deman
d amount, lo
cati
on of the city,
the distance and co
st
betwe
en citie
s
and
so on
);
(2) Initiali
ze the pop
ulation
;
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
An Im
proved
NSGA-II Algo
rithm
for Multi-obje
c
tive Tra
v
elin
g Salesm
an Problem
(Yabo Lu
o)
4415
(3) A
ssig
n
1 to
gen
a. Evaluate each in
dividual
’s fitness
accordin
g to the fitness functio
n
;
b. Gene
rate
a child
re
n p
opulatio
n by genetic
ope
rators of NS
GA-II (i.e., selectio
n,
c
r
oss
o
ver, mutation);
c. Co
mbine
the pa
rent
po
pulation
and
t
he chil
dren
popul
ation t
o
form a
co
mbined
popul
ation;
d. An im
prov
ed n
o
n
-
domi
nated
so
rting
(a
layer
strategy a
c
cord
ing to
nee
d
and th
e
aren
a’s p
r
in
ci
ple) is p
e
rfo
r
med on the
combine
d
pop
ulation to so
rt
the combi
n
e
d
popul
ation i
n
to
different no
n-dominate
d
fronts; If the total numbe
r of individual
s in
the fronts ha
s exce
ede
d the
size of a singl
e popul
ation, then the non
-dominate
d
so
rting
process will
stop.
e. Execute a truncation p
r
o
c
ed
ure o
n
the
non-domi
n
a
t
ed fronts to
make n
e
w p
o
pulation
of the next generatio
n;
f.
gen
++,
I
F
MAXGEN
gen
, GOTO a;
3.1. Population Initializati
on and Indiv
i
dual Ev
alua
tion
This p
ape
r a
dopts
nature
numbe
r cod
i
ng for
the e
x
pressio
n
of
chromo
som
e
in the
popul
ation. Every gene
of
the ch
rom
o
some
re
pr
e
s
ent a city an
d the sequ
e
n
ce
between
the
gene
s refle
c
t
s
the trip, for example the code is 0
1 2 3 4 5 0, w
h
ich exp
r
e
s
s that the trip
go
through the number 0 city to number 1 then 2,
...... at
last return the original
city.
After initialize
population,
every chrom
o
som
e
rep
r
e
s
ent
s a rand
om arrang
ed
of city’s
natural n
u
mb
er. Suppo
se
a codi
ng of chrom
o
some i
s
a
0
a
1
...a
n-1
a
0
for the bi-obj
ective TSP, the
two evaluativ
e fitness fun
c
tions are defi
ned a
s
follows:
The le
ngth
of the total
tour: Le
ngth
= di
st(a
0
,a
1
)+di
st(
a
1
,a
2
)+
…+di
st(a
n-1
,a
0
). He
re,
dist(a
i
,a
j
) mea
n
s the di
stan
ce bet
wee
n
ci
ty a
i,
and city
a
j.
The t
o
t
a
l co
st
:
Cost
s
= co
s
t
(a
0
,a
1
)+
co
st
(
a
1
,a
2
)+…
+
co
st
(a
n-1
,a
0
). He
re, co
st(a
i
, a
j
) means
the co
st between city a
i,
an
d city a
j.
3.2. Genetic
Opera
t
ors
The bina
ry ch
ampion
shi
p
s
sele
ction [1]
is utilize
d
as t
he sel
e
ctio
n operator.
The orde
r crossover
(OX) and inversio
n mutation [3
] is use
d
to gene
rate the
child
ren
individual
by cho
o
si
ng a
p
a
rt of the traveling
route a
n
d
ch
angi
ng o
v
er the
corre
s
po
ndin
g
ge
n
e
tic
seq
uen
ce.
3.3. Arena’s
Principle
This p
ape
r a
dopts the a
r
ena’
s prin
cipl
e to con
s
tru
c
t the non
-d
ominated
set
of the
popul
ation. T
he a
r
ena’
s
pri
n
cipl
e is
give
n as follows:
Assu
me
P
i
s
a evolution
a
l
popul
ation,
Q
is
a cons
truc
tion set, Set
Q
=
P
.
A
ssu
me
Nds
i
s
a n
o
n
-
d
o
minated
set and
let
Nd
s
be a
em
pty set.
Fist, select
a
n
individu
al
x
from the
Q
to be
cham
pion, the
n
co
mpare it
with
all the
othe
rs
individual
s in
Q
on
e by
one
. If
x
do
minat
es
y
, the
n
eli
m
inate
y
from
Q
, el
se
elimi
nate
x
a
nd
se
t
y
to be
x
(the
cham
pion
) a
nd go o
n
. After the first round
com
parison, move
x
into
Nd
s
. Next,
repe
at the ab
ove pro
c
ed
ure until
Q
is empty.
Whe
n
comp
are th
e in
dividual of
Q
with the
ch
a
m
pion, if it i
s
d
o
minate
d
by the
cham
pion, it will be elimin
ated and
will not go to t
he next round. M
o
re nu
mbe
r
o
f
individual in the
P
, Less com
pari
s
on
cou
n
t of the arena
’s prin
cipl
e.
In [16], the time com
p
lexity of the arena’s
prin
ciple i
s
analyze
d
to be
O
(
rm
N
), here
r
is the nu
mber of obje
c
ts,
m
is the
amount of no
n-
dominate
d
in
dividual,
N
i
s
the size of
popul
ation.
In usu
a
l, there exists
m
<
N
, The
r
efore, the
aren
a’s p
r
in
ci
ple ha
s lower time comple
xity
than that (i.e.,
O
(
rN
2
)) of
NSGA-II.
3.4. A La
y
e
r
Strateg
y
According to Ne
ed
The NSGA
-II algorithm di
vides the co
mbination p
o
pulation
R
t
(combine
d with
parent
popul
ation
P
t
and children
popul
ation
Q
t
) into multi-la
yer non
-domi
nated fro
n
ts
F
(
F
=
F
1
F
2
…
F
e
,
e
is the numbe
r of non-d
o
min
a
ted
layers). Fi
rst
l
y, use the same way like
con
s
tru
c
ting
the non-domi
nated set to get the non-dominate
d
set
R
t
, which
calle
d the first non-domi
n
ated
front
F
1
. The
n
, eliminate the individu
als of
F
1
from p
opulatio
n
R
t
, i.e., s
e
t
R
t
=
R
t
\
F
1
. Repea
ting
the above p
r
oce
dure, and
obtain
F
2,
F
3
,
F
4 ,
and so on, until
R
t
i
s
empty. The pro
c
ed
ure of the
la
ye
r
i
n
g
o
f
NSG
A
-
II is
des
cr
ib
ed
as
F
i
g
u
r
e 1
.
After the process of layerin
g
,
the next process
truncates the
dou
ble
size
of non
-do
m
in
ated
set
F
i
n
to a h
a
lf, to
obtain th
e ne
w p
opulatio
n
of
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4413 – 4
418
4416
next generation. It elimin
ates the
indi
viduals of the second p
a
r
t of
F
and
the first part
is
remai
ned to b
e
the new p
o
pulation
P
t+1
.
Figure 1. Pro
c
ed
ure of NS
GA-II
Ho
wever, th
e
way
of layeri
ng a
bove i
s
n
o
t goo
d en
ou
gh, ju
st like Fi
gure
1, afte
r l
a
yering
of
F
3
, the total individual
s of
F
1
，
F
2
，
F
3
have exce
e
ded the
size
of a singl
e p
opulatio
n. So the
layering of
F
4
，
F
5
，
F
6
is un
necessa
ry. Therefo
r
e, in t
h
is pa
pe
r, a layering
strate
gy according
to
need i
s
p
r
op
o
s
ed, a
nd it ca
n be d
e
scri
be
d as th
e Figu
re 2. When th
e numb
e
r
of total individual
s
is la
rge
r
th
an
the si
ze
of p
o
pulation, th
e l
a
yering
p
r
o
c
e
dure
will
sto
p
.
Hen
c
e, it i
s
better tha
n
th
e
layer method
of NSGA-II, for its l
e
ss number
of la
yeri
ng fronts and at the same
time still havi
ng
the same p
o
p
u
lation
P
t+1
[17].
Figure 2. Improved Pro
c
e
d
u
re of NSGA
-II
4.
Experiment Resul
t
s
and Analy
s
is
In this paper,
we have ad
opted the ca
se in [9
] as the test probl
em of the MOTSP. As
Figure 3
sh
o
w
s,
D1 i
s
th
e
length b
e
twe
en ea
ch
city
,
and
D2 i
s
the
co
st bet
wee
n
ea
ch
city. In the
experim
ent, the
comp
uter i
s
the
PC
of P
4
-1.7G
CP
U,
1024M
inte
rn
al sto
r
ag
e, Wi
ndo
ws XP, a
n
d
prog
ram
m
ing
VC++ 6.0 progra
mming pl
atform. The
parameter
s
e
tting is
set as
follows
: s
i
ze of
popul
ation
N
=50, th
e m
a
x of ge
ne
ratio
n
Maxge
n
=5, the
crossov
e
r
ratio
Pc
=
0
.9 and mutation
ratio
Pm
=0.08.
08
1
7
2
5
5
8
1
3
81
0
3
44
9
4
0
72
3
0
8
7
77
21
5
5
44
87
0
6
7
2
5
8
1
9
7
7
6
709
3
34
0
2
1
2
5
9
3
0
08
2
1
4
1
4
4
3
4
7
8
2
0
6
1
7
62
94
7
14
6
1
0
2
9
3
1
5
1
14
7
6
29
0
7
8
6
7
4
3
29
31
78
0
2
8
47
47
51
67
2
8
0
Figure 3. The
Length an
d Co
st
Matrix betwee
n
the Ci
ties
D1
=
D2
=
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
An Im
proved
NSGA-II Algo
rithm
for Multi-obje
c
tive Tra
v
elin
g Salesm
an Problem
(Yabo Lu
o)
4417
In this
tes
t
problem, both the NSGA
-II-MO
TSP a
n
d
the improve
d
NSGA
-II algorithm
(INSGA-II-M
O
TSP) a
r
e u
s
ed to
solve
MOTSP. Afte
r re
peat 5 tim
e
s exp
e
rim
e
n
t
s, the averag
e of
data is ado
pted. The re
sult
s of the two algorithm
s are expre
s
sed in Tabl
e 1, and
the deviation is
economi
z
ing
data ratio of INSGA-II-M
O
TSP than the NSGA-II.
Table 1. Re
sults of NSGA-II-MOTSP an
d INSGA-II-M
O
TSP
NSGA-II
-
M
O
TSP
INSGA-II
-M
OTS
P
deviation
Average count of
dominance comparison
2569.1
1955.7
-23.9%
Average running
time (s)
0.051
0.035
-31.3%
From
Tabl
e
1, INSGA-II-MOTSP is b
e
tter than
NSGA-II-MOT
SP both o
n
t
he ave
r
ag
e
cou
n
t of dom
inan
ce comp
arison a
nd a
v
erage
run
n
i
ng time. The
main re
ason
is that are
n
a’s
prin
ciple
is a
dopted.
The
time complex
i
ty of are
na’
s pri
n
ci
ple i
s
O
(
rm
N
)
which is better than
O
(
rN
2
)
of NS
GA-II. In addition, the layering strategy
as need reduces the number of layering.
In
sho
r
t, the experim
ent re
sult sho
w
s th
at there
are
better efficie
n
cy and solu
tions in the new
algorith
m
.
Table 2 i
s
t
he solution
s found by I
N
SGA-II-M
O
TSP and ot
her th
ree int
e
lligen
ce
algorith
m
s [9]
.
From this ta
ble, it can be
seen th
at ea
ch solution h
a
s two
entitie
s: (Le
ng, Co
st).
For exampl
e, the solution
(158, 280
), its corre
s
p
o
n
d
ing tour line
is 0-5-2-1-4
-
3-0, he
re, 15
8
pre
s
ent the t
o
tal length of
the tour and
280 is t
he total co
st. Fro
m
the results of Table 2, the
INSGA-II-MO
TSP is not only able to obtain the sa
me solutio
n
of other algo
rithm but also
can
find much mo
re Pareto sol
u
tions li
ke
(2
71, 197
), (19
4
, 265). Th
erefore, the INSGA-II-MOT
SP is
able to find much b
e
tter
spread of so
lutions a
nd b
e
tter conve
r
g
ence nea
r the true Paret
o
-
optimal front
comp
ared to other three al
gorithm
s.
Table 2. Solu
tions Fou
nd b
y
INSGA-
II-MOTSP and ot
her Th
ree Alg
o
rithm
s
ACO SA
2-opt
algorithm
INSGA-II
-M
OTS
P
(158, 280
)
(250, 208
)
(158, 280
)
(250, 208
)
(209, 248
)
(158, 280
)
(271, 197
)
(250, 208
)
(209, 248
)
(194, 265
)
(158, 280
)
5. Conclu
sion
In our re
ally l
i
fe, there
are
many p
r
obl
e
m
s
whi
c
h a
r
e
com
p
o
s
ed
with many
con
f
licting
multiple opti
m
ization
obje
c
ts. MO
TSP is an
extende
d insta
n
ce of
traveling
sal
e
sma
n
p
r
obl
em,
whi
c
h natu
r
al
ly arise
s
as a
subp
robl
em in many
transportation a
n
d
logistics appl
ication
s
. In this
pape
r, an im
proved
NSG
A
-II algorithm
(INSGA-II-M
O
TSP) is p
r
o
posed to solv
e the MOTSP. To
improve its
run-time effici
ency, a layeri
ng stra
tegy a
c
cordi
ng to n
eed is
pro
p
o
s
ed a
nd a
r
en
a’s
prin
ciple i
s
al
so ad
opted t
o
con
s
truct n
on-d
o
min
a
ted
set. In addition, an order
cro
s
sove
r like
operator an
d
an inversi
o
n
mutation op
erato
r
ar
e a
d
opted for MO
TSP. The experim
ent re
sults
sho
w
th
at th
e p
r
opo
se
d I
N
SGA-II-M
O
TSP algo
rith
m is abl
e to
find bette
r
sp
read
of
sol
u
tions
comp
ared to other three al
gorithm
s. Th
e better
re
sul
t
s and lo
w computation ti
me obtaine
d by
this algo
rithm
can b
e
expl
ained by the
layer st
rategy
according to
need.
We in
tend to exten
d
this strategy to other multi-obje
c
tive optimization p
r
o
b
l
ems.
In addition, we would like to use oth
e
r mea
s
u
r
e
s
whi
c
h allo
ws for a soun
d statistica
l
analysi
s
of
o
u
r re
sults. To
this goal
we will
a
dopt th
e
attainme
nt functio
n
s met
hodol
ogy [18]
for
experim
ental analysi
s
.
Ackn
o
w
l
e
dg
ements
This wo
rk
i
s
partially
supp
orted by
the Na
tion
al Natural S
c
ien
c
e
Found
ation o
f
Chin
a
unde
r G
r
ant
No. 5
1177
04
0. The
autho
rs
would
like
t
o
than
k
Dr. X
ilong Q
u
fo
r t
he di
scussio
n
s
about
the me
asu
r
e cod
e
. The
a
u
thors also grat
efull
y
ackno
w
led
ge the h
e
lpfu
l comm
ents
and
sug
g
e
s
tion
s of the reviewers,
whic
h ha
ve improved t
he pre
s
e
n
tation.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4413 – 4
418
4418
Referen
ces
[1]
CAC Coello,
GB Lamont, DA Van
Vel
d
h
u
i
z
en. Evo
l
utio
n
a
r
y
Alg
o
rithms
for Solv
in
g M
u
lti-Obj
e
ctive
Probl
ems. 2nd
ed. Ne
w
York:
Spring
er-Verl
a
g. 2007.
[2]
K Deb, A Prat
ap, S Agar
w
a
l,
T
Me
yariva
n. A
fast an
d
elitist
multio
bj
ective
genetic algorithm: NSGA-II.
IEEE Transactions on Evo
l
uti
onary C
o
mput
ation
. 20
02; 6(
2): 182-1
97.
[3]
DB F
ogel. Evol
ution
a
r
y
Comp
utation: T
o
w
a
r
d
a Ne
w
P
h
il
os
oph
y of Mac
h
in
e Intelli
ge
nce. T
h
ird Editi
o
n
ed. Ne
w
Jers
e
y
, USA: John
W
ile
y
& So
ns, Inc., 2006.
[4]
M Dorig
o
, LM
Gambard
e
ll
a. Ant Col
o
n
y
S
ystem
: A Coop
erative
Lear
ni
n
g
Appr
oach t
o
the T
r
aveling
Salesm
an Problem.
IEEE Transactio
n
s on E
v
oluti
onary C
o
mp
utatio
n.
199
7; 1(1): 53-66.
[5]
C García-Martí
nez, O C
o
rd
ón
, F
Herrer
a
. A
taxonom
y
a
n
d
an
empir
i
cal
a
nal
ysis
of
multi
p
le
ob
jectiv
e
ant colo
n
y
opti
m
izatio
n alg
o
rit
h
ms for the bi-criteria T
SP.
Europ
ean Jo
urn
a
l of Operatio
n
a
l Rese
arch
.
200
7; 180(
1): 116-1
48.
[6]
Y del
Val
l
e,
GK Vena
ya
ga
moorth
y
,
S M
oha
gh
egh
i, JC
Hern
an
dez,
RG Harl
e
y
.
P
a
rticle s
w
a
r
m
optimiz
ation: B
a
sic conc
ept
s, variants an
d app
licati
ons i
n
po
w
e
r s
y
ste
m
s.
IEEE Transactions
on
Evoluti
onary C
o
mputati
on.
20
08; 12(2): 1
71-
195.
[7]
KI Smith, RM
Everson, JE F
i
elds
end, C Mu
rph
y
,
R Misr
a. Domin
anc
e-ba
sed multi
obj
ective simul
a
t
e
d
ann
eal
in
g.
IEEE Transactions
on Evolutionar
y
Computation
.
2008; 1
2
(3): 3
23-3
42.
[8]
X
D
Li, J Br
anke, M K
i
rley
.
On
p
e
rfor
ma
nce metrics
a
nd particl
e
sw
arm meth
ods for
dyn
a
mi
c
mu
ltio
bjectiv
e
optimi
z
a
t
io
n
proble
m
s
.
Procee
din
g
of 2007 IEEE Congress o
n
Evoluti
onar
y
Comp
utation, Sing
apor
e. 200
7; 576-5
83.
[9]
CK Goh, KC
T
an. A competit
ive-coo
perati
v
e coev
oluti
o
n
a
r
y
par
a
d
i
g
m for d
y
namic
multio
bjectiv
e
optimiz
ation.
IEEE Transacti
ons on Evo
l
uti
onary C
o
mput
ation.
20
09; 13
(1): 103-1
27.
[10]
Min L
i
u, W
e
nh
ua Z
e
ng.
A
fast Evol
ution
a
ry A
l
gorit
hm for
Dy
na
mic
Bi-o
bjec
tive Opti
mi
z
a
t
i
on Pr
obl
e
m
s
.
T
he 7
th
Internation
a
l Co
nfere
n
c
e on Com
pute
r
Sci
ence & Ed
ucatio
n (ICCS
E 2012). 2
012;
130-1
34.
[11] D
Angus.
Cr
ow
ding p
o
p
u
l
a
tion-
base
d
a
n
t colony o
p
ti
mis
a
tio
n
for the multi-o
b
j
e
c
t
ive travelli
ng
sales
m
an pro
b
le
m.
Pr
oceedings
of the 2007 IEEE S
y
mposiu
m on
Computational
Intelligence in
Multicriteri
a De
cision M
a
kin
g
(MCDM 200
7), 200
7; 333-
340.
[12] L
Paq
uete,
T
Stutzle.
A tw
o-phase
loc
a
l se
a
r
ch for the
bio
b
j
ective trav
eli
n
g sal
e
s
m
an
pr
obl
e
m
. EMO
200
3, 200
3; 47
9–4
93.
[13]
L Ma, F
Jiang. Solvi
ng
mu
lti-criteri
a
traveli
ng sa
les
m
an pro
b
lem
b
y
a
n
t alg
o
r
ithm.
Systems
Engi
neer
in
g T
heory Metho
dol
ogy App
licati
o
n
s
.
1999; 8(4): 2
3
-27.
[14]
Sand
ip C
h
a
n
d
a
, Abhi
na
nd
an
De. Co
ng
esti
on R
e
li
ef of C
ontin
ge
nt Po
w
e
r Net
w
o
r
k
w
i
t
h
Evol
utio
nar
y
Optimization Algorithm.
T
E
LK
OMNIKA Indon
esia
n Journ
a
l o
f
Electrical Eng
i
ne
erin
g
. 201
2; 10(1): 1-8.
[15]
Xu
eso
n
g
Yan,
Qing
hua
W
u
,
Hammi
n
Liu.
An
Improv
ed
Rob
o
t Path
Pl
ann
ing
Al
gorit
hm Bas
ed
o
n
Genetic A
l
gor
ithm.
T
E
LKOMNIKA Indo
nesi
an Jo
urn
a
l
of Electrical
En
gi
neer
ing
. 20
12;
10(8): 19
48-
195
5.
[16]
JH Z
hen
g, H
Jian
g, D Ku
an
g,
Z
Z
Shi. An
appr
oac
h of
constructin
g
m
u
lti-o
b
jectiv
e p
a
reto o
p
timal
soluti
ons usi
n
g
arena
’s princ
i
p
l
e.
Journ
a
l of S
o
ftw
are
. 2007; 18(6): 12
87-
12
97.
[17]
Min Li
u, W
H
Z
eng, JF
Z
hao.
A fast bi
-ob
j
ect
i
ve n
on-d
o
min
a
ted sorti
ng
al
gorithm.
Patter
n
Rec
ogn
itio
n
and Artifici
al In
tellig
enc
e.
201
1; 24(4): 53
8-5
47.
[18]
VG da F
onsec
a,
C F
onsec
a, A Hall.
In
fe
re
n
t
i
a
l
pe
rfo
r
m
a
n
c
e
a
sse
ssme
n
t
o
f
sto
c
h
a
s
ti
c op
ti
mi
se
rs and
the attain
ment
function.
Ev
ol
ution
a
r
y
Multi-
Criterio
n Opti
mi
zatio
n
(EMO’ 20
01), LN
CS
199
3. 20
01;
213-
225.
Evaluation Warning : The document was created with Spire.PDF for Python.