A S udy o Mul iobjec i e Me aheu is ics When
Sol ing Pa ame e Scalable P oblems
Juan J. Du illo, S uden Membe , IEEE, An onio J. Neb o, Ca los A. Coello Coello, Senio Membe , IEEE,
Jos´
e Ga cía-Nie o, F ancisco Luna, and En ique Alba
Abs ac —To e alua e he sea ch capabili ies o a mul iobjec-
i e algo i hm, he usual app oach is o choose a benchma k
o known p oblems, o pe o m a ixed numbe o unc ion
e alua ions, and o apply a se o quali y indica o s. Howe e ,
while eal p oblems could ha e hund eds o e en housands o
decision a iables, cu en benchma ks a e no mally adop ed
wi h ela i ely ew decision a iables (no mally om 10 o
30). Fu he mo e, pe o ming a cons an numbe o e alua ions
does no p o ide in o ma ion abou he e o equi ed by an
algo i hm o ge a sa is ac o y se o solu ions; his in o ma ion
would also be o in e es in eal scena ios, whe e e alua ing he
unc ions de ining he p oblem can be compu a ionally expensi e.
In his pape , we s udy he e ec o pa ame e scalabili y in
a numbe o s a e-o - he-a mul iobjec i e me aheu is ics. We
adop a benchma k o pa ame e -wise scalable p oblems ( he
Zi zle –Deb–Thiele es sui e) and analyze he beha io o eigh
mul iobjec i e me aheu is ics on hese es p oblems when using
a numbe o decision a iables ha ange om 8 up o 2048.
By using he hype olume indica o as a s opping condi ion, we
also analyze he compu a ional e o equi ed by each algo i hm
in o de o each he Pa e o on . We conclude ha he wo
analyzed algo i hms based on pa icle swa m op imiza ion and
di e en ial e olu ion yield he bes o e all esul s.
Index Te ms—Compa a i e s udy, e iciency, me aheu is ics,
mul i-objec i e op imiza ion, scalabili y.
I.
In oduc ion
MANY REAL-WORLD op imiza ion p oblems equi e
he op imiza ion o mo e han one objec i e unc ion
a he same ime. These p oblems a e called mul iobjec i e
This wo k was suppo ed in pa by he Conseje ía de Inno aci´on,
Ciencia y Emp esa, Jun a de Andalucía unde Con ac P07-TIC-03044,
he DIRI-COM P ojec (h p://di icom.lcc.uma.es), and he Spanish
Minis y o Sci-ence and Inno a ion unde Con ac TIN2008-06491-
C04-01, he M* P ojec (h p://ms a .lcc.uma.es). The wo k o J. J. Du illo
and F. Luna is suppo ed by G an AP-2006-03349, G an ES-2006-13075,
espec i ely, om he Spanish Go e nmen . The wo k o C. A. Coello
Coello is suppo ed by CONACyT P ojec 103570
J. J. Du illo, A. J. Neb o, J. Ga cía-Nie o, F. Luna, and E. Alba a e wi h he
Depa amen o de Lenguajes y Ciencias de la Compu aci´on, Uni e si y o M
´alaga, M´alaga 29071, Spain (e-mail: [email p o ec ed]; [email p o ec ed];
[email p o ec ed]; [email p o ec ed]; [email p o ec ed]).
C. A. Coello Coello is wi h he Depa men o Compu e Sci-
ence, Cen e o Resea ch and Ad anced S udies, Mexico DF 07360,
Mexico, and also wi h he Uni é Mix e In e na ionale-Labo a oi e
F anco-Mexicaine d’In o ma ique e Au oma ique 3175 CNRS, Cen-
e o Resea ch and Ad anced S udies, Mexico DF 07360, Mexico
(e-mail: [email p o ec ed]).
op imiza ion p oblems (MOPs). In con as o single-objec i e
op imiza ion p oblems, he solu ion o MOPs is no a single
solu ion, bu a se o non-domina ed solu ions called he Pa e o
op imal se . A solu ion ha belongs o his se is said o
be a Pa e o op imum and, when he solu ions o his se a e
plo ed in objec i e space, hey a e collec i ely known as he
Pa e o on . Ob aining he Pa e o on is he main goal in
mul iobjec i e op imiza ion.
The ac ha eal-wo ld MOPs end o be nonlinea and wi h
objec i e unc ions ha a e e y expensi e o e alua e has led
o he use o me aheu is ics [1], [3], [13] o deal wi h hem.
Me aheu is ics a e a amily o echniques comp ising e olu-
iona y algo i hms (EAs), pa icle swa m op imiza ion (PSO),
an colony op imiza ion, abu sea ch, di e en ial e olu ion,
sca e sea ch, and many o he s. The mos popula algo i hms
o mul iobjec i e op imiza ion based on me aheu is ics in
cu en use (NSGA-II [8] and SPEA2 [35]) adop EAs as hei
sea ch engine [5], [7].
The pe o mance o hese algo i hms has been ypically
assessed using benchma k p oblems, such as he Zi zle –Deb–
Thiele (ZDT) es p oblems [34], he Deb–Thiele–Laumanns–
Zi zle (DTLZ) es p oblems [9], and he Walking-Fish-G oup
(WFG) es p oblems [15], [16]. These h ee p oblem amilies
a e scalable in he numbe o decision a iables, and he
las wo a e also scalable in he numbe o objec i es. The
me hodology commonly adop ed in he specialized li e a u e
is o compa e se e al algo i hms using a ixed (p e-de ined)
numbe o objec i e unc ion e alua ions and hen o e alua e
he alues o di e en quali y indica o s (e.g., gene a ional
dis ance [32] o hype olume [36], among o he s).
The main mo i a ion o his pape is ha many eal-wo ld
p oblems ha e hund eds o e en housands o decision a i-
ables, which con as s wi h he cu en p ac ice o alida ing
mul iobjec i e me aheu is ics using he a o emen ioned bench-
ma ks, bu wi h a low numbe o decision a iables (no mally,
no mo e han 30). Thus, he s udies cu en ly a ailable do no
conside he capabili y o cu en mul iobjec i e e olu iona y
algo i hms o p ope ly scale when dealing wi h a e y la ge
numbe o decision a iables. Scalabili y is a key issue in
op imiza ion algo i hms, bu i has been a ely add essed in
he mul iobjec i e domain. An example is he s udy p esen ed
in [14], in which he so-called in elligen mul iobjec i e e olu-
iona y algo i hm (IMOEA) is compa ed o se e al eli is and
non-eli is mul iobjec i e e olu iona y algo i hms (MOEAs)
in se e al o he ZDT es p oblems, adop ing 63 decision
a iables. This compa a i e s udy was unde aken o alida e
he hypo hesis o he au ho s o IMOEA, who a gued he
capabili y o such app oach o deal wi h la ge pa ame e
MOPs. Ano he example can be ound in [33], whe e a s udy
using only he ZDT1 p oblem wi h up o 100 a iables is
included. This con as s wi h he in e es in s udying unc ion
scalabili y, which is cu en ly an ac i e esea ch opic, leading
o he a ea known as many-objec i e op imiza ion [2], [10],
[17], [26], [27], [29].
Ano he in e es ing issue ha has been sca cely co e ed in
he specialized li e a u e is he analysis o he beha io o
a mul iobjec i e me aheu is ic eaching he Pa e o on o a
p oblem. Typically, a ixed numbe o e alua ions (and, in
consequence, o i e a ions) is de ined by he use , and he
pe o mance o he di e en algo i hms s udied is compa ed.
Howe e , his so o compa ison only measu es he on
aspec , and i does no p o ide any indica ion ega ding he
compu a ional e o ha a gi en algo i hm equi es o each
he ue Pa e o on o a p oblem, i.e., he e iciency o he
algo i hm. We belie e ha his is an impo an issue, because
i we ake in o accoun ha e alua ing he objec i e unc ions
o a MOP can be e y ime-consuming, i becomes o in e es
o know how expensi e o a ce ain algo i hm i is o gene a e
he Pa e o on .
We ca ied a i s analysis o hese ideas in [11], whe e
six s a e-o - he-a mul iobjec i e me aheu is ics we e com-
pa ed when sol ing he ZDT benchma k, conside ing hei
o mula ion anging om 8 up o 2048 a iables. The algo-
i hms included in he s udy epo ed in [11] we e h ee
gene ic algo i hms (GAs) (NSGA-II [8], SPEA2 [35], and
PESA-II [6]), one e olu ion s a egy (PAES [18]), one PSO
(OMOPSO [28]), and one cellula GA (MOCell [24]). In
ha pape , he numbe o e alua ions equi ed o p o ide a
sa is ac o y solu ion was also analyzed. Gi en ha he Pa e o
on s o he ZDT p oblems a e known, an algo i hm was
conside ed success ul when he hype olume o i s cu en
popula ion (o a chi e, depending on he algo i hm) was highe
han he 95% o he hype olume o he Pa e o on .
The cu en pape conduc s u he esea ch along his line.
Compa ed o ou p e ious pape in [11], he main con ibu ions
o his pape a e he ollowing.
1) Two addi ional mode n mul iobjec i e me aheu is ics
ha e been included: gene alized di e en ial e olu ion
(GDE3) [20] (a di e en ial e olu ion algo i hm) and
AbYSS [23] (a sca e sea ch algo i hm), leading o a
o al o eigh mul iobjec i e me aheu is ics, ep esen a-
i e o he s a e-o - he-a .
2) We analyze he sea ch capabili ies o he algo i hms
when sol ing he scalable ZDT p oblems using a
s onge s opping condi ion, by which he algo i hms
s op ei he when hey ind a solu ion se ha ing a
hype olume highe han he 98% o he hype olume
o he ue Pa e o on o when hey ha e pe o med
10 000 000 unc ion e alua ions (500 000 in [11]).
3) A mo e comple e s a is ical analysis is pe o med, in-
cluding pai -wise compa isons among he echniques in
o de o de e mine he signi icance o he esul s.
4) We s udy he beha io o he mos p omising echniques
in o de o p opose mechanisms ha enhance hei
sea ch capabili ies.
The emainde o his pape is o ganized as ollows.
Sec ion II includes basic backg ound on mul iobjec i e op-
imiza ion. Sec ions III and IV desc ibe, espec i ely, he
p oblems and he me aheu is ics we ha e used. Sec ion V is
de o ed o he p esen a ion and analysis o he expe imen s
ca ied ou . In Sec ion VI, we include a discussion abou he
ob ained esul s. Finally, Sec ion VII summa izes he pape
and discusses possible lines o u u e wo k.
II. Mul iobjec i e Op imiza ion
In his sec ion, we include some backg ound on mul iobjec-
i e op imiza ion. Mo e speci ically, we de ine he concep s o
MOP, Pa e o op imali y, Pa e o dominance, Pa e o op imal se ,
and Pa e o on . In hese de ini ions we a e assuming, wi hou
loss o gene ali y, he minimiza ion o all he objec i es.
A gene al mul iobjec i e op imiza ion p oblem (MOP) can
be o mally de ined as ollows.
De ini ion 1 (MOP): Find a ec o x∗=x∗
1,x
∗
2,...,x
∗
n
which sa is ies he minequali y cons ain s gi(x)≥0,i =
1,2,...,m, he pequali y cons ain s hi(x)=0,i =
1,2,...,p, and minimizes he ec o unc ion 
(x)=
 1(x),
2(x),...,
k(x)T, whe e x=[x1,x
2,...,x
n]Tis he
ec o o decision a iables.
The se o all alues sa is ying he cons ain s de ines he
easible egion and any poin x∈is a easible solu ion.
As men ioned be o e, we seek o he Pa e o op ima. I s o mal
de ini ion is p o ided nex .
De ini ion 2 (Pa e o Op imali y): A poin x∗∈is Pa e o
op imal i o e e y x∈and I={1,2,...,k
}ei he
∀i∈I( i(x)= i(x∗))o he e is a leas one i∈Isuch ha
i(x)>
i(x∗).
This de ini ion s a es ha x∗is Pa e o op imal i no easible
ec o xexis s which would imp o e some c i e ion wi h-
ou causing a simul aneous wo sening in a leas one o he
c i e ion. O he impo an de ini ions associa ed wi h Pa e o
op imali y a e he ollowing.
De ini ion 3 (Pa e o Dominance): A ec o
u=(u1,...,u
k)is said o domina e  =( 1,...,
k)(deno ed
by u ) i and only i uis pa ially smalle han  , i.e.,
∀i∈{1,...,k
},u
i≤ i∧∃i∈{1,...,k
}:ui<
i.
De ini ion 4 (Pa e o Op imal Se ): Fo a gi en MOP 
(x),
he Pa e o op imal se is de ined as P∗={x∈|¬∃x∈
, 
(x)
(x)}.
De ini ion 5 (Pa e o F on ): Fo a gi en MOP 
(x) and i s
Pa e o op imal se P∗, he Pa e o on is de ined as PF∗=
{
(x),x∈P∗}.
Ob aining he Pa e o on o a MOP is he main goal
o mul iobjec i e op imiza ion. Howe e , gi en ha a Pa e o
on can con ain a la ge numbe o poin s, a good solu ion
mus con ain a limi ed numbe o hem, which should be as
close as possible o he ue Pa e o on , as well as being
uni o mly sp ead; o he wise, hey would no be e y use ul o
he decision make . Closeness o he Pa e o on ensu es ha
we a e dealing wi h op imal solu ions, and a uni o m sp ead
TABLE I
ZDT Tes Func ions
P oblem Objec i e Func ions Va iable Bounds Commen s
ZDT1
1(x)=x1
2(x)=g(x)[1 −x1/g(x)]
g(x) = 1+9n
i=2 xi/(n−1)
0≤xi≤1Con ex
ZDT2
1(x)=x1
2(x)=g(x)1−(x1/g(x))2
g(x) = 1+9n
i=2 xi/(n−1)
0≤xi≤1Non-con ex
ZDT3
1(x)=x1
2(x)=g(x)1−x1
g(x)−x1
g(x)sin (10πx1)
g(x) = 1+9n
i=2 xi/(n−1)
0≤xi≤1Con ex
Disconnec ed
ZDT4
1(x)= x1
2(x)= g(x)[1 −(x1/g(x))2]
g(x) = 1 + 10(n−1)+
n
i=2[x2
i−10 cos (4πxi)]
0≤x1≤1
−5≤xi≤5
i=2, ..., n
Non-con ex
Mul i on al
ZDT6
1(x)=1−e−4x1sin6(6πx1)
2(x)=g(x)[1 −( 1(x)/g(x))2]
g(x) = 1 + 9[(n
i=2 xi)/(n−1)]0.25
0≤xi≤1
Non-con ex
Many- o-one
Non-uni o mly spaced
o he solu ions means ha we ha e made a good explo a ion
o he sea ch space and no egions a e le unexplo ed.
III. Scalable Pa ame e -Wise Mul iobjec i e
Op imiza ion P oblems
To ca y ou ou pape , i would be help ul o use p ob-
lems which a e scalable in e ms o he numbe o decision
a iables while keeping an in a iable Pa e o on . The ZDT
es unc ion amily [34] ul ills his equi emen . I o e s,
u he mo e, a g oup o p oblems wi h di e en p ope ies:
con ex, non-con ex, disconnec ed, mul i on al, many- o-one
p oblems (see Table I). These p oblems ha e been widely used
in many s udies in he ield since hey we e i s o mula ed.
Table I shows he o mula ion o he ZDT es p oblem amily.
We omi ed p oblem ZDT5 because i is bina y encoded. The
Pa e o on o each p oblem is plo ed in Fig. 1.
Since we a e in e es ed in s udying he beha io o he
algo i hms when sol ing scalable pa ame e -wise p oblems,
we ha e e alua ed each ZDT p oblem wi h 8, 16, 32, 64,
128, 256, 512, 1024, and 2048 a iables. This way, we can
s udy no only wha echniques beha e mo e e icien ly when
sol ing p oblems ha ing many a iables, bu also i hei
sea ch capabili ies emain cons an o no when he numbe
o decision a iables inc eases.
IV. Mul iobjec i e Op imiza ion Algo i hms
In his sec ion, we b ie ly desc ibe he eigh me aheu is ics
ha we ha e conside ed in his pape . We ha e used he
implemen a ion o hese algo i hms p o ided by jMe al [12],
a Ja a-based amewo k aimed a mul i-objec i e op imiza ion
wi h me aheu is ics.1
1jMe al is eely a ailable o download a he ollowing URL:
h p://jme al.sou ce o ge.ne .
The NSGA-II algo i hm was p oposed by Deb e al. [8].
I is a gene ic algo i hm based on ob aining a new popula ion
om he o iginal one by applying he ypical gene ic ope a o s
(selec ion, c osso e , and mu a ion); hen, he indi iduals in
he wo popula ions a e so ed acco ding o hei ank, and he
bes solu ions a e chosen o c ea e a new popula ion. In case
o ha ing o selec some indi iduals wi h he same ank, a
densi y es ima ion based on measu ing he c owding dis ance
o he su ounding indi iduals belonging o he same ank is
used o ge he mos p omising solu ions.
SPEA2 was p oposed by Zi le e al. in [35]. In his
algo i hm, each indi idual has a i ness alue ha is he sum o
i s s eng h aw i ness plus a densi y es ima ion. The algo i hm
applies he selec ion, c osso e , and mu a ion ope a o s o ill
an a chi e o indi iduals; hen, he non-domina ed indi iduals
o bo h he o iginal popula ion and he a chi e a e copied in o
a new popula ion. I he numbe o non-domina ed indi iduals
is g ea e han he popula ion size, a unca ion ope a o based
on calcula ing he dis ances o he k h nea es neighbo is used.
This way, he indi iduals ha ing he minimum dis ance o any
o he indi idual a e chosen.
PESA-II [6] uses an in e nal popula ion om which pa en s
a e selec ed o c ea e new solu ions, and an ex e nal popula ion
in which he non-domina ed solu ions ound a e s o ed. This
ex e nal popula ion uses he same hype -g id di ision o phe-
no ype (i.e., objec i e unc ion) space adop ed by PAES [19] o
main ain di e si y in which egion-based selec ion is adop ed.
In egion-based selec ion, he uni o selec ion is a hype box
a he han an indi idual. The p ocedu e lies in selec ing
(using any o he adi ional selec ion echniques) a hype -
box and hen andomly choosing an indi idual wi hin ha
hype box.
PAES is a me aheu is ic p oposed by Knowles and
Co ne [19]. The algo i hm is based on a simple (1 + 1) e o-
lu ion s a egy. To ind di e se solu ions in he Pa e o op imal
Fig. 1. Pa e o on s o he ZDT es unc ions.
se , PAES uses an ex e nal a chi e o nondomina ed solu ions,
which is also used o decide abou he new candida e solu ions.
An adap i e g id is used as a densi y es ima o in he a chi e.
We ha e used a eal coded e sion o PAES, applying a
polynomial mu a ion ope a o .
OMOPSO is a pa icle swa m op imiza ion algo i hm o
sol ing MOPs [28]. I s main ea u es include he use o
he c owding dis ance om NSGA-II o il e ou leade
solu ions and he use o mu a ion ope a o s o accele a e he
con e gence o he swa m. The o iginal OMOPSO algo i hm
makes use o he concep o -dominance o limi he numbe
o solu ions p oduced by he algo i hm. We conside he e a
a ian disca ding he use o -dominance, and conside ing he
leade popula ion as he esul yielded by he algo i hm.
GDE3 [20] is an imp o ed e sion o he GDE algo i hm
[21]. I s a s wi h a popula ion o andom solu ions, which be-
comes he cu en popula ion. A each gene a ion, an o sp ing
popula ion is c ea ed using he di e en ial e olu ion ope a o s;
hen, he cu en popula ion o he nex gene a ion is upda ed
using he solu ions o bo h, he o sp ing and he cu en
popula ion. Be o e p oceeding o he nex gene a ion, he size
o he popula ion is educed using non-domina ed so ing and a
p uning echnique aimed a di e si y p ese a ion, in a simila
way as NSGA-II, al hough he p uning used in GDE3 modi ies
he c owding dis ance o NSGA-II in o de o sol e some o
i s d awbacks when dealing wi h p oblems ha ing mo e han
wo objec i es.
MOCell [24] is a cellula gene ic algo i hm (cGA). Like
many mul iobjec i e me aheu is ics, i includes an ex e nal
a chi e o s o e he non-domina ed solu ions ound so a . This
a chi e is bounded and uses he c owding dis ance o NSGA-II
o keep di e si y in he Pa e o on . We ha e used he e an
asynch onous e sion o MOCell, called aMOCell4 in [25], in
which he cells a e explo ed sequen ially (asynch onously).
The selec ion is based on aking an indi idual om he
neighbo hood o he cu en solu ion (called cell in cGAs)
and ano he one andomly chosen om he a chi e. A e
applying he gene ic c osso e and mu a ion ope a o s, he
new o sp ing is compa ed wi h he cu en one, eplacing
i i be e ; i bo h solu ions a e non-domina ed, he wo s
indi idual in he neighbo hood is eplaced by he cu en one.
In hese wo cases, he new indi idual is inse ed in o he
a chi e.
AbYSS is an adap a ion o he sca e sea ch me aheu is ic
o he mul iobjec i e domain [23]. I uses an ex e nal a chi e
simila o he one employed by MOCell. The algo i hm in-
co po a es ope a o s om he e olu iona y algo i hms domain,
including polynomial mu a ion and simula ed bina y c osso e
in he imp o emen and solu ion combina ion me hods,
espec i ely.
V. Expe imen a ion
In his sec ion, we desc ibe he pa ame e se ings used in
he expe imen s, as well as he me hodology we ha e ollowed
in he es s, and he esul s we ha e ob ained.
A. Pa ame e iza ion
We ha e chosen a se o pa ame e alues such ha we allow
a ai compa ison among all he algo i hms compa ed. All he
GAs (NSGA-II, SPEA2, PESA-II, and MOCell) as well as
GDE3 use an in e nal popula ion size equal o 100; he size
o he a chi e is also 100 in PAES, OMOPSO, GDE3, MOCell,
and AbYSS. OMOPSO has been con igu ed wi h 100 pa icles.
Fo AbYSS, he popula ion and he e e ence se ha e a size
o 20 solu ions.
TABLE II
Pa ame e iza ion (L= Indi idual Leng h)
Pa ame e iza ion Used in NSGA-II [8]
Popula ion size 100 Indi iduals
Selec ion o pa en s Bina y ou namen + bina y ou namen
Recombina ion Simula ed bina y, pc=0.9
Mu a ion Polynomial, pm=1.0/L
Pa ame e iza ion Used in SPEA2 [35]
Popula ion size 100 indi iduals
Selec ion o pa en s Bina y ou namen + bina y ou namen
Recombina ion Simula ed bina y, pc=0.9
Mu a ion Polynomial, pm=1.0/L
Pa ame e iza ion Used in PESA-II [6]
Popula ion size 100 indi iduals
Selec ion o pa en s Region based selec ion + egion based selec ion
Recombina ion Simula ed bina y, pc=0.9
Mu a ion Polynomial, pm=1.0/L
A chi e size 100 indi iduals
Pa ame e iza ion Used in PAES [18]
Mu a ion Polynomial, pm=1.0/L
A chi e size 100 indi iduals
Pa ame e iza ion Used in OMOPSO [28]
Pa icles 100 pa icles
Mu a ion Uni o m + non-uni o m
Leade s size 100 indi iduals
Pa ame e iza ion Used in GDE3 [20]
Popula ion size 100 indi iduals
Recombina ion Di e en ial e olu ion, CR =0.1, F=0.5
Pa ame e iza ion Used in MOCell [25]
Popula ion size 100 indi iduals (10 ×10)
Neighbo hood 1-hop neighbo s (8 su ounding solu ions)
Selec ion o pa en s Bina y ou namen + bina y ou namen
Recombina ion Simula ed bina y, pc=0.9
Mu a ion Polynomial, pm=1.0/L
A chi e size 100 indi iduals
Pa ame e iza ion Used in AbYSS [23]
Popula ion size 20 indi iduals
Re e ence se size 10 + 10
Recombina ion Simula ed bina y, pc=1.0
Mu a ion (local sea ch) Polynomial, pm=1.0/L
A chi e size 100 indi iduals
In he GAs, we ha e used simula ed bina y c osso e (SBX)
and polynomial mu a ion [7]. The dis ibu ion indices o
bo h ope a o s a e ηc= 20 and ηm= 20, espec i ely. The
c osso e p obabili y is pc=0.9 and he mu a ion p obabili y
is pm=1/L, whe e Lis he numbe o decision a iables. In
PAES we ha e also adop ed a polynomial mu a ion ope a o ,
wi h he same dis ibu ion index as indica ed be o e. AbYSS
uses polynomial mu a ion in he imp o emen me hod and
SBX in he solu ion combina ion me hod. GDE3 uses 0.1
and 0.5 o he wo pa ame e s CR and F, espec i ely [20].
OMOPSO applies a combina ion o uni o m and non-uni o m
mu a ion o he pa icle swa m [28]. A de ailed desc ip ion o
he pa ame e alues adop ed o ou expe imen s is p o ided
in Table II.
B. Me hodology
We a e in e es ed in wo main goals: analyzing he beha io
o he algo i hms when sol ing he scalable ZDT benchma k
and hei speed (e iciency) in eaching he Pa e o on .
Gi en ha he Pa e o on s o he ZDT p oblems a e known
be o ehand, a s a egy could be o un he algo i hms un il hey
a e able o p oduce hem. Howe e , i is possible ha some o
hem ne e p oduce he ue Pa e o on , o simply ake oo
Fig. 2. Pa e o on s wi h di e en HV alues ob ained o p oblem ZDT1.
long o do i . Thus, we adop ins ead a s opping condi ion o
all he algo i hms compa ed, based on he high quali y o he
Pa e o on p oduced. Fo ha pu pose, he hype olume [36]
quali y indica o is adop ed.
The hype olume compu es he olume (in objec i e unc-
ion space) co e ed by membe s o a non-domina ed se
o solu ions Q o p oblems in which all objec i es a e o
be minimized. Ma hema ically, o each solu ion i∈Q,a
hype cube iis cons uc ed wi h a e e ence poin Wand
he solu ion ias he diagonal co ne s o he hype cube. The
e e ence poin can simply be ound by cons uc ing a ec o
o wo s objec i e unc ion alues. The ea e , he union o all
hype cubes is ound and i s hype olume (HV ) is calcula ed
HV = olume |Q|

i=1
i.(1)
Highe alues o he HV pe o mance measu e imply mo e
desi able solu ions. A p ope y o his quali y indica o is ha
i measu es bo h con e gence o he Pa e o on and di e si y
o he ob ained on s.
Once he quali y indica o we a e going o use has been
desc ibed, we need o es ablish a s opping condi ion o be
used in he execu ion o he algo i hms. The idea is ha he
me aheu is ics s op when hey each a ce ain pe cen age o
he HV o he Pa e o on , which ensu es ha he ob ained
on ep esen s an accu a e app oxima ion o i . To decide
abou ha pe cen age, we show di e en app oxima ions o he
Pa e o on o he p oblem ZDT1 wi h di e en pe cen ages
o HV in Fig. 2. We can obse e ha a on wi h a hype -
olume o 98.26% ep esen s a easonable app oxima ion o
he ue Pa e o on s in e ms o con e gence and di e si y
o solu ions. This same alue has been co obo a ed using he
o he es p oblems om he ZDT sui e. So, we ha e aken
98% o he HV o he Pa e o on as a c i e ion o conside
ha a MOP has been success ully sol ed. Fu he mo e, hose
algo i hms equi ing ewe unc ion e alua ions o achie e his
e mina ion condi ion can be conside ed o be mo e e icien
o as e . In hose si ua ions in which an algo i hm is unable
o ob ain a on ul illing his condi ion a e he maximum
numbe o unc ion e alua ions, we conside ha i has ailed
in sol ing he p oblem; his way, we can ob ain a hi a e o
he algo i hms, i.e., hei pe cen age o success ul execu ions.
We se he maximum numbe o e alua ions o en million.

Fig. 3. S a is ical analysis pe o med in his pape .
In ou expe imen s, we check he s opping condi ion e e y
100 e alua ions ( ha is, each i e a ion in he popula ion-based
me aheu is ics), whe e we measu e he hype olume o he
non-domina ed solu ions ound so a . The e o e, in NSGA-II,
SPEA2, and GDE3 we ha e conside ed he non-domina ed
solu ions a each gene a ion: in PESA-II, PAES, AbYSS, and
MOCell, he ex e nal popula ion and, in MOPSO, he leade s
a chi e.
We ha e execu ed 100 independen uns o each algo i hm
and each p oblem ins ance. Since we a e dealing wi h s ochas-
ic algo i hms, we need o pe o m a s a is ical analysis o
he ob ained esul s o compa e hem wi h a ce ain le el
o con idence. Nex , we desc ibe he s a is ical es ha we
ha e ca ied ou o assu ing his [30]. Fi s , a Kolmogo o –
Smi no es is pe o med in o de o check whe he he
alues o he esul s ollow a no mal (Gaussian) dis ibu ion
o no . I so, he Le ene es checks o he homogenei y
o he a iances. I samples ha e equal a iance (posi i e
Le ene es ), an ANOVA es is done; o he wise we pe o m a
Welch es . Fo non-Gaussian dis ibu ions, he non-pa ame ic
K uskal–Wallis es is used o compa e he medians o he
algo i hms.
We always conside in his pape a con idence le el o
95% (i.e., signi icance le el o 5% o p- alue unde 0.05)
in he s a is ical es s, which means ha he di e ences a e
unlikely o ha e occu ed by chance wi h a p obabili y o
95%. Success ul es s a e ma ked wi h “+” symbols in he las
ow in he ables con aining he esul s (see Tables III–VII);
con e sely, “−” means ha no s a is ical con idence was
ound (p- alue >0.05). Fo he sake o homogenei y in he
p esen a ion o he esul s, all he ables include he median,
˜x, and he in e qua ile ange, IQR, as measu es o loca ion
(o cen al endency) and s a is ical dispe sion, espec i ely.
We ha e pe o med a pos -hoc es ing phase using he
mul compa e unc ion p o ided by MATLAB, which al-
lows o a mul iple compa ison o samples. This way, we can
make pai wise compa ison be ween algo i hms o know abou
he signi icance o hei esul s.
C. Analysis o Resul s
Tables III–VII show he median and he in e qua ile ange
o he numbe o e alua ions needed by he di e en op i-
mize s o ZDT1, ZDT2, ZDT3, ZDT4, ZDT6, espec i ely.
This indica es ha all he 100 independen uns ha e been
success ul, which means a hi a e o 1.0. When an op imize
Fig. 4. Numbe o e alua ions when sol ing ZDT1.
is no able o each an accep able on upon pe o ming
10 000 000 unc ion e alua ions in all he 100 independen
uns, i s cell in he ables includes he “−” symbol, and i is
no aken in o accoun in he s a is ical es s. In o he wo ds,
he “−” symbol means ha , in o de o sol e success ully he
p oblem in all he independen uns, he op imize may need
mo e han 10 000 000 o unc ion e alua ions. In hese cases,
he hi a e would be less han 1.0. To ease he analysis o he
esul s in hese ables, he cells con aining he lowes numbe
o unc ion e alua ions ha e a g ey colo ed backg ound. The e
a e wo g ey le els: he da ke g ey indica es he bes (lowes )
alue, while ligh e g ey is used o poin ou he second bes
alue. We can obse e ha he esul s in hese ables a e
signi ican , as can be seen in he las ow o each o hem,
whe e each cell con ains a “+” symbol, excep o ZDT4
wi h 1024 and 2048 a iables (whe e he e a e no esul s o
compa e).
Nex , we analyze he esul s ob ained o each o he
p oblems. To make he esul s clea e , we include a igu e
summa izing he alues, using a loga i hmic scale, in addi ion
o he co esponding able. The discussion is o ganized in he
ollowing o de : i s , we analyze he success o he algo i hms
when sol ing he di e en ins ances o he p oblem; second,
we analyze he speed o he echniques o ob ain he Pa e o
on when sol ing he p oblems; and, inally, we make a
pai wise compa ison o he algo i hms, conside ing hose
p oblems in which he e a e no s a is ical di e ences be ween
each pai o echniques (i we included he p oblems wi h
s a is ical signi icance, his would lead o la ge ables).
1) ZDT1: This p oblem p esen s a uni o m densi y o
solu ions in he sea ch space and a con ex Pa e o on .
Table III and Fig. 4 show he numbe o e alua ions needed o
ob ain a Pa e o on wi h 98% o he HV o he Pa e o on
o his p oblem. Table VIII p esen s he hi a e indica o ,
whe e we ha e used he symbol √ o indica e a alue o 1.0
(a 100% success a e). Table IX con ains he p oblems o
which no s a is ical di e ences ha e been ound be ween each
pai o algo i hms.
We begin by analyzing which algo i hms a e able o sol e
he p oblems in all he independen uns ca ied ou . The
esul s in Table III show ha all he algo i hms ha e success in
all he ins ances, excep o PAES in he ins ance wi h 2048
TABLE III
E alua ions o ZDT1
Algo i hm 8 16 32 64 128 256 512 1024 2048
a iables a iables a iables a iables a iables a iables a iables a iables a iables
NSGA-II 4.40e+3 4.0e+2 8.10e+3 5.0e+2 1.52e+4 9.0e+2 2.88e+4 1.4e+3 5.72e+4 3.0e+3 1.21e+5 5.2e+3 2.71e+5 9.3e+3 6.31e+5 1.6e+4 1.45e+6 3.3e+4
SPEA2 5.00e+3 3.0e+2 9.30e+3 8.0e+2 1.69e+4 1.1e+3 3.14e+4 1.4e+3 6.03e+4 2.7e+3 1.25e+5 5.0e+3 2.69e+5 9.4e+3 6.01e+5 1.6e+4 1.34e+6 2.8e+4
PESA-II 4.15e+3 1.2e+3 8.40e+3 9.5e+2 1.73e+4 1.6e+3 3.74e+4 2.8e+3 8.36e+4 5.0e+3 1.96e+5 9.3e+3 4.78e+5 1.8e+4 1.18e+6 4.0e+4 2.93e+6 8.9e+4
PAES 3.40e+3 2.5e+3 7.25e+3 4.4e+3 1.34e+4 8.0e+3 2.57e+4 1.6e+4 4.70e+4 3.5e+4 9.07e+4 3.9e+4 1.73e+5 1.3e+5 3.68e+5 4.7e+5 –
OMOPSO 1.40e+3 4.0e+2 3.40e+3 9.0e+2 7.40e+3 1.8e+3 1.38e+4 2.8e+3 2.80e+4 4.4e+3 6.31e+4 7.4e+3 1.58e+5 1.8e+4 4.55e+5 3.4e+4 1.41e+6 1.0e+5
GDE3 2.80e+3 2.0e+2 5.30e+3 3.0e+2 1.00e+4 4.0e+2 1.81e+4 4.5e+2 3.30e+4 9.0e+2 6.10e+4 1.2e+3 1.16e+5 1.8e+3 2.40e+5 3.0e+3 5.64e+5 7.0e+3
MOCell 1.80e+3 3.0e+2 3.80e+3 6.0e+2 9.20e+3 8.0e+2 2.18e+4 1.8e+3 4.92e+4 4.0e+3 1.13e+5 6.4e+3 2.56e+5 8.6e+3 5.62e+5 1.6e+4 1.20e+6 2.7e+4
AbYSS 3.40e+3 7.0e+2 6.80e+3 9.0e+2 1.49e+4 1.8e+3 3.30e+4 2.7e+3 7.29e+4 6.1e+3 1.58e+5 7.8e+3 3.50e+5 1.2e+4 7.06e+5 2.1e+4 1.39e+6 2.6e+4
+ + + + + + + + –
TABLE IV
E alua ions o ZDT2
Algo i hm 8 16 32 64 128 256 512 1024 2048
a iables a iables a iables a iables a iables a iables a iables a iables a iables
NSGA-II 7.50e+3 6.0e+2 1.37e+4 8.0e+2 2.60e+4 1.6e+3 4.98e+4 3.2e+3 1.01e+5 4.8e+3 2.08e+5 1.0e+4 4.54e+5 1.8e+4 1.01e+6 2.6e+4 2.28e+6 4.5e+4
SPEA2 7.80e+3 1.0e+3 1.46e+4 1.3e+3 2.60e+4 1.7e+3 4.86e+4 3.2e+3 9.50e+4 4.4e+3 1.90e+5 6.0e+3 3.95e+5 9.0e+3 8.51e+5 1.7e+4 1.89e+6 2.6e+4
PESA-II 1.50e+4 7.8e+3 3.51e+4 2.5e+4 9.38e+4 6.0e+4 3.98e+5 4.2e+5 −− − − −
PAES 3.14e+4 4.5e+4 6.94e+4 7.1e+4 1.29e+5 1.2e+5 2.93e+5 4.2e+5 − − − − −
OMOPSO 1.75e+3 4.0e+2 3.90e+3 1.6e+3 9.70e+3 3.8e+3 1.68e+4 5.0e+3 3.06e+4 5.3e+3 5.44e+4 8.4e+3 1.11e+5 1.1e+4 2.83e+5 2.7e+4 7.71e+5 7.9e+4
GDE3 3.20e+3 2.0e+2 6.10e+3 4.5e+2 1.18e+4 6.5e+2 2.26e+4 1.2e+3 4.33e+4 1.8e+3 8.18e+4 1.3e+3 1.58e+5 2.1e+3 3.27e+5 4.2e+3 7.66e+5 9.8e+3
MOCell 2.90e+3 1.0e+3 4.90e+3 1.4e+3 8.25e+3 2.2e+3 1.74e+4 1.1e+4 4.42e+4 2.5e+4 1.26e+5 4.3e+4 2.91e+5 1.1e+4 6.60e+5 1.1e+4 1.46e+6 2.0e+4
AbYSS 4.50e+3 7.5e+2 9.10e+3 1.7e+3 1.86e+4 2.5e+3 3.96e+4 3.5e+3 8.26e+4 7.2e+3 1.75e+5 8.6e+3 3.68e+5 9.6e+3 7.74e+5 1.9e+4 1.60e+6 2.4e+4
+ + + + + + + + +
TABLE V
E alua ions o ZDT3
Algo i hm 8 16 32 64 128 256 512 1024 2048
a iables a iables a iables a iables a iables a iables a iables a iables a iables
NSGA-II 4.20e+3 5.0e+2 7.40e+3 6.0e+2 1.36e+4 9.5e+2 2.53e+4 1.4e+3 5.06e+4 3.1e+3 1.08e+5 4.8e+3 2.38e+5 9.0e+3 5.37e+5 1.6e+4 1.20e+6 2.5e+4
SPEA2 4.90e+3 6.0e+2 9.10e+3 7.0e+2 1.62e+4 1.0e+3 3.00e+4 2.0e+3 5.89e+4 4.0e+3 1.21e+5 5.8e+3 2.56e+5 9.4e+3 5.58e+5 1.6e+4 1.22e+6 2.5e+4
PESA-II 3.75e+3 9.0e+2 7.60e+3 1.0e+3 1.59e+4 2.0e+3 3.43e+4 3.8e+3 7.76e+4 7.8e+3 1.77e+5 8.0e+3 4.14e+5 1.5e+4 9.83e+5 3.3e+4 2.28e+6 4.5e+4
PAES 6.90e+3 8.8e+3 1.21e+4 1.2e+4 2.56e+4 3.2e+4 5.68e+4 6.1e+4 9.92e+4 1.2e+5 2.03e+5 2.0e+5 3.65e+5 6.3e+5 8.17e+5 8.4e+5 –
OMOPSO 2.60e+3 1.0e+3 5.40e+3 2.4e+3 1.01e+4 3.3e+3 2.20e+4 4.0e+3 5.06e+4 8.1e+3 1.26e+5 2.3e+4 3.53e+5 3.9e+4 1.03e+6 8.3e+4 3.17e+6 1.9e+5
GDE3 2.90e+3 2.5e+2 5.60e+3 3.0e+2 1.08e+4 4.0e+2 1.96e+4 8.0e+2 3.46e+4 9.5e+2 6.29e+4 1.3e+3 1.20e+5 1.8e+3 2.50e+5 2.8e+3 6.07e+5 7.2e+3
MOCell 1.90e+3 6.0e+2 4.20e+3 8.0e+2 9.90e+3 1.4e+3 2.30e+4 2.2e+3 5.24e+4 3.4e+3 1.16e+5 9.3e+3 2.57e+5 1.7e+4 5.44e+5 1.6e+4 1.15e+6 3.6e+4
AbYSS 3.35e+3 1.6e+3 6.75e+3 1.8e+3 1.40e+4 2.1e+3 2.87e+4 3.8e+3 6.02e+4 6.1e+3 1.23e+5 1.6e+4 2.57e+5 2.0e+4 5.47e+5 4.4e+4 1.12e+6 4.5e+4
+ + + + + + + + +
TABLE VI
E alua ions o ZDT4
Algo i hm 8 16 32 64 128 256 512 1024 2048
a iables a iables a iables a iables a iables a iables a iables a iables a iables
NSGA-II 1.62e+4 3.4e+3 4.38e+4 1.2e+4 1.37e+5 3.3e+4 4.25e+5 9.1e+4 1.20e+6 1.8e+5 3.29e+6 3.5e+5 8.85e+6 6.7e+5 − −
SPEA2 2.11e+4 4.2e+3 4.54e+4 8.7e+3 1.34e+5 3.1e+4 3.69e+5 6.4e+4 1.07e+6 1.3e+5 2.98e+6 2.4e+5 8.24e+6 5.9e+5 −−
PESA-II 1.84e+4 5.2e+3 5.00e+4 1.4e+4 1.51e+5 3.2e+4 4.12e+5 7.3e+4 1.06e+6 1.3e+5 2.72e+6 2.5e+5 6.69e+6 3.8e+5 − −
PAES 3.08e+4 1.1e+4 8.53e+4 4.1e+4 2.17e+5 6.4e+4 5.41e+5 1.9e+5 1.28e+6 3.0e+5 3.18e+6 7.2e+5 − − −
OMOPSO − − − − − − − − −
GDE3 1.18e+4 8.0e+2 − − − − − − − −
MOCell 8.80e+3 2.2e+3 2.04e+4 5.4e+3 5.86e+4 1.0e+4 1.65e+5 2.7e+4 4.67e+5 5.8e+4 1.23e+6 1.0e+5 3.25e+6 1.6e+5 8.14e+6 2.8e+5 −
AbYSS 1.46e+4 5.4e+3 5.46e+4 2.1e+4 1.61e+5 4.3e+4 4.82e+5 1.0e+5 1.39e+6 1.5e+5 3.81e+6 4.2e+5 − − −
+ + +−+ + + − −
TABLE VII
E alua ions o ZDT6
Algo i hm 8 16 32 64 128 256 512 1024 2048
a iables a iables a iables a iables a iables a iables a iables a iables a iables
NSGA-II 2.31e+4 1.3e+3 4.60e+4 1.4e+3 8.84e+4 2.8e+3 1.68e+5 3.5e+3 3.24e+5 6.4e+3 6.47e+5 1.1e+4 1.33e+6 1.6e+4 2.77e+6 2.7e+4 5.80e+6 4.6e+4
SPEA2 2.64e+4 1.2e+3 5.26e+4 2.0e+3 9.94e+4 2.2e+3 1.87e+5 4.2e+3 3.53e+5 7.0e+3 6.84e+5 1.1e+4 1.37e+6 1.4e+4 2.81e+6 2.3e+4 5.82e+6 3.8e+4
PESA-II 2.16e+4 1.8e+3 4.78e+4 2.4e+3 9.85e+4 4.7e+3 2.01e+5 7.2e+3 4.10e+5 1.1e+4 8.57e+5 2.1e+4 1.83e+6 2.9e+4 3.89e+6 4.4e+4 8.32e+6 8.9e+4
PAES 6.80e+3 6.8e+3 1.62e+4 1.6e+4 3.21e+4 2.8e+4 − − − − − −
OMOPSO 2.90e+3 1.6e+3 4.20e+3 1.9e+3 7.70e+3 2.7e+3 1.38e+4 3.5e+3 2.88e+4 5.2e+3 6.10e+4 1.0e+4 1.26e+5 1.6e+4 2.76e+5 3.0e+4 6.12e+5 6.6e+4
GDE3 3.70e+3 5.0e+2 6.60e+3 5.0e+2 1.32e+4 1.1e+3 3.14e+4 2.6e+3 1.53e+5 6.7e+3 3.21e+5 3.8e+3 6.36e+5 4.0e+3 1.35e+6 7.5e+3 3.27e+6 1.8e+4
MOCell 1.07e+4 1.0e+3 2.58e+4 1.4e+3 5.65e+4 2.6e+3 1.19e+5 3.0e+3 2.47e+5 4.7e+3 5.18e+5 7.8e+3 1.10e+6 9.4e+3 2.35e+6 1.9e+4 5.00e+6 3.4e+4
AbYSS 1.23e+4 1.1e+3 2.57e+4 1.8e+3 5.26e+4 3.0e+3 1.08e+5 3.8e+3 2.26e+5 7.2e+3 4.67e+5 9.2e+3 9.60e+5 1.4e+4 1.96e+6 2.1e+4 4.00e+6 4.1e+4
+ + + + + + + + +
TABLE VIII
Hi Ra e o ZDT1
Algo i hm/Va iables 8 16 32 64 128 256 512 1024 2048
NSGA-II √ √ √ √ √ √ √ √ √
SPEA2 √√√√ √ √ √ √ √
PESA-II √√√√√ √ √ √ √
PAES √√ √ √ √ √ √ √0.95
OMOPSO √ √ √ √ √√ √ √ √
GDE3 √√ √ √ √ √ √ √ √
MOCell √ √ √ √ √ √ √ √ √
AbYSS √ √ √ √ √ √ √ √ √
Fig. 5. Numbe o e alua ions when sol ing ZDT2.
a iables. This is co obo a ed conside ing he hi a e (see
Table VIII), whe e all he algo i hms ha e a hi a e o 1.0
excep o PAES in he 2048 ins ance, which has 0.95. This
means ha in i e ou o he 100 execu ions ca ied ou o his
ins ance, PAES eached he maximum numbe o e alua ions
be o e ob aining a Pa e o on wi h he desi ed HV alue.
We pay a en ion now o he speed, i.e., he numbe o
unc ion e alua ions needed by he me aheu is ics o ind a
Pa e o on acco ding o ou success condi ion. In Fig. 4, we
plo he esul s using a loga i hmic scale. We ha e connec ed
by a line he symbols o he wo algo i hms yielding he bes
alues. Thus, we can obse e ha OMOPSO (do ed line)
is he as es algo i hm up o 128 a iables, while GDE3
scales be e om 256 o 2048 a iables. The lines clea ly
depic ha he e is a endency change in hese wo algo i hms
a 256 a iables, indica ing ha GDE3 ends o be as e
han he o he echniques as he numbe o decision a iables
Fig. 6. Numbe o e alua ions when sol ing ZDT3.
inc eases, while OMOPSO exhibi s he opposi e beha io . This
sugges s ha GDE3 could be he mos app op ia e algo i hm
o sol e ZDT1 wi h mo e han 2048 a iables. Acco dingly,
we de e mine ha GDE3 is he algo i hm ha scales he bes
in p oblem ZDT1.
Conside ing he es o echniques, MOCell is he second
as es algo i hm up o 32 a iables and in he case o 2048
a iables. NSGA-II, SPEA2, and AbYSS end o need a simila
numbe o e alua ions when he ins ances a e la ge .
Finally, we make an analysis conside ing he ou come
o he s a is ical es s included in Table IX. I we ocus
on OMOPSO and GDE3, he es s a e non-success ul
only in he ins ances o 128 and 256 a iables, which
does no a ec he p e ious analysis. I is in e es ing o
no e ha PAES, he simples o he e alua ed echniques,
p esen s no di e ences in many ins ances compa ed o
NSGA-II and MOCell. We can also obse e ha NSGA-II
TABLE IX
Non-Success ul S a is ical Tes s o he Numbe o E alua ions o ZDT1
NSGA-II 128, 256, 512, 1024 8, 16 16, 32, 64, 128 2048 – 256 32
SPEA2 16, 32 2048 − − −64
PESA-II 8 − − − 128
PAES 512, 1024 −128, 256, 512, 1024 8, 16, 32
OMOPSO 128, 256 8, 16, 32 2048
GDE3 32 −
MOCell −
SPEA2 PESA-II PAES OMOPSO GDE3 MOCell AbYSS
TABLE X
Hi Ra e o ZDT2
Algo i hm/Va iables 8 16 32 64 128 256 512 1024 2048
NSGA-II √ √ √ √ √ √ √ √ √
SPEA2 √√ √ √ √ √ √ √ √
PESA-II √√ √ √ 0.43 0.0 0.0 0.0 0.0
PAES √ √ √ √ 0.99 0.98 0.99 0.96 0.79
OMOPSO √√ √ √ √ √ √ √ √
GDE3 √√ √ √ √ √ √ √ √
MOCell √ √ √ √ √ √ √ √ √
AbYSS √ √ √ √ √ √ √ √ √
and SPEA2 do no p esen s a is ical con idence in ou
cases.
2) ZDT2: This p oblem also p esen s a uni o m densi y
o solu ions in he sea ch space, bu i has a non-con ex
Pa e o on . The numbe s o e alua ions needed o sol e he
ZDT2 p oblem a e included in Table IV and Fig. 5. Table X
shows he hi a e o each algo i hm. The p oblems in which
each pai o algo i hms a e s a is ically independen appea in
Table XI.
We s a by commen ing ha some op imize s ha e di i-
cul ies when sol ing his p oblem, as can be seen in Table IV
and Fig. 5. In pa icula , nei he PAES no PESA-II a e able
o each a hi a e o 1.0 in ins ances wi h mo e han 64
a iables. These esul s indica e ha p oblems ha ing a non-
con ex Pa e o on can cause di icul ies o some algo i hms.
Consequen ly, he hi a e indica o shows ha six algo-
i hms ha e a 100% success a e in all he ins ances. Among
he algo i hms wi h a hi a e smalle han 1.0, PESA-II is
he algo i hm ha ing he wo s alue, 0.49 in he p oblem
wi h 128 a iables, and 0.0 in he nex ones. PAES does no
achie e a 100% o success a e 128 a iables bu , in con as
o PESA-II, he alues a e nea 100% in he ins ances anging
om 128 o 1024 a iables.
Le us examine now he speed o he algo i hms. A look
a Fig. 5 e eals ha OMOPSO and GDE3 a e he as es
algo i hms. The lines connec ing he alues o hese sol e s
indica e ha OMOPSO equi es a lowe numbe o unc ion
e alua ions han GDE3 o ge he desi ed Pa e o on s in all
bu in he la ges ins ance. In ac , when obse ing he lines we
can see ha he one o GDE3 sugges s again ha i could scale
be e han he o he echniques in o de o sol e ins ances
o mo e han 2048 a iables. MOCell, AbYSS, SPEA2, and
NSGA-II, in his o de , a e he ollowing me aheu is ics in
e ms o speed, al hough hey end o ge close o each
Fig. 7. Numbe o e alua ions when sol ing ZDT4.
o he when he numbe o decision a iables o he p oblem
inc eases.
The pai wise es s in Table XI e eal some in e es ing ac s.
On he one hand, he esul s o GDE3 and OMOPSO in he
wo la ges ins ances a e non-signi ican ; on he o he hand, he
es s show he di e ences be ween MOCell and OMOPSO up
o 64 a iables and be ween MOCell and GDE3 up o 512
a iables a e also non-signi ican .
3) ZDT3: This p oblem p esen s a uni o m densi y o so-
lu ions in he sea ch space and i s Pa e o on is composed o
se e al discon inuous egions; he e o e, he main complexi y
is o ind all hese discon inuous egions. The e alua ions e-
qui ed o sol ing he di e en ins ances a e shown in Table V
and Fig. 6. Table XII p esen s he hi a e o he algo i hms.
The p oblems in which he e a e no s a is ical di e ences
be ween each pai o algo i hms a e shown in Table XIII.
P oceeding as be o e, we s a by analyzing which algo-
i hms a e able o sol e success ully all he ins ances o he
p oblem. The e o e, in Table V we see ha all he algo i hms
Fig. 14. Resul s o GDE3 wi h polynomial mu a ion on he ZDT p oblem amily.
TABLE XXII
GDE3 wi h Polynomial Mu a ion: E alua ions
P oblem 8 16 32 64 128 256 512 1024 2048
a iables a iables a iables a iables a iables a iables a iables a iables a iables
ZDT1 3.30e+3 3.0e+2 6.50e+3 4.0e+2 1.18e+4 5.0e+2 2.12e+4 8.0e+2 3.80e+4 9.0e+2 6.98e+4 1.4e+3 1.33e+5 2.4e+3 2.74e+5 3.5e+3 6.45e+5 8.4e+3
ZDT2 4.10e+3 3.0e+2 8.00e+3 5.0e+2 1.54e+4 7.5e+2 2.88e+4 9.0e+2 5.41e+4 1.6e+3 1.02e+5 1.8e+3 1.98e+5 3.4e+3 4.14e+5 4.4e+3 9.91e+5 1.4e+4
ZDT3 2.60e+3 1.0e+3 5.40e+3 2.4e+3 1.01e+4 3.3e+3 2.20e+4 4.0e+3 5.06e+4 8.1e+3 1.26e+5 2.3e+4 3.53e+5 3.9e+4 1.03e+6 8.3e+4 3.17e+6 1.9e+5
ZDT4 2.11e+4 1.4e+3 5.98e+4 4.8e+3 1.88e+5 1.4e+4 7.78e+5 6.9e+4 3.41e+6 4.6e+5 ––– –
ZDT6 4.50e+3 4.0e+2 9.10e+3 7.5e+2 1.90e+4 2.0e+3 5.02e+4 5.2e+3 2.24e+5 8.0e+3 4.67e+5 5.0e+3 9.39e+5 7.4e+3 2.02e+6 1.4e+4 4.97e+6 3.3e+4
changes in he beha io o he echnique. This, howe e , does
no mean ha he e is no oom o imp o emen ; he use o
di e en mu a ion and c osso e ope a o s may change he
sea ch capabili ies o a GA.
E. Compa ison wi h P e ious Pape
In his sec ion, we compa e he esul s o his pape wi h
hose ob ained in some o ou p e ious pape [11]. In ha
pape , he main conclusions we e ha , conside ing scalabil-
i y, PAES was he mos compe i i e algo i hm ollowed by
OMOPSO, while he la e appea ed as he as es algo i hm.
In his pape , howe e , PAES appea s in he las posi ions in
he scalabily anking. This is explained by he ac ha we
ha e no conside ed he e he impac o no ha ing a 100%
hi a e in he ables con aining he compu ed e alua ions,
which undoub edly has penalized PAES in p ac ically all he
p oblems conside ed.
I we conside OMOPSO, i s esul s in [11] emain ba-
sically he same. The inclusion in his pape o GDE3 and
AbYSS has a ec ed OMOPSO only in he scalabi y anking,
and OMOPSO is s ill among he as es algo i hms assessed
(excluding he ZDT4 es p oblem).
Finally, we would like o men ion he e o ha has been
equi ed o ca y ou his pape . I we conside ha we
ha e s udied eigh algo i hms o sol e nine ins ances o i e
p oblems, he numbe o expe imen s is 360. As we ha e
execu ed one hund ed independen uns pe expe imen , his
means a o al o 36 000 uns. Fu he mo e, he expe imen s
wi h SMPSO and GDE3 wi h mu a ion ha e equi ed 9000
addi ional uns. Taking in o accoun also he pilo es s wi h
he o he algo i hms o s udy he in luence o he dis ibu ion
indices in he mu a ion and c osso e ope a o s, he o al
numbe o uns ha e been in he o de o 50 000. The ac
ha we ha e used a s onge e mina ion condi ion (98%

ins ead o 95% o he hype olume o he Pa e o on ) and
ha he maximum numbe o e alua ions ha e been aised
om 500 000 in [11] o 10 000 000 in his pape , has had
as a consequence he ac ha he compu a ional ime o he
algo i hms unable o sol e he p oblems wi h 1024 and 2048
a iables was highe han one hou .
To execu e his la ge numbe o expe imen s, we ha e
used he compu e s o he labo a o ies o he Depa men o
Compu e Science o he Uni e si y o M´
alaga, in Spain. Mos
o hem a e equipped wi h mode n dual co e p ocesso s so,
aking in o accoun ha he e a e mo e han 180 compu e s,
ha means ha up o 360 co es ha e been a ailable. To un all
he p og ams, we ha e used Condo [31], a middlewa e ha
ac s as a dis ibu ed schedule , which has p o en o be an ideal
ool o cope wi h he la ge amoun o asks we ha e deal wi h.
VII. Conclusion and Fu u e Wo k
We ha e e alua ed eigh s a e-o - he-a me aheu is ics o e
a se o pa ame e scalable p oblems in o de o s udy he
beha io o he algo i hms conce ning hei capabili ies o
sol e p oblems ha ing a la ge numbe o decision a iables.
The benchma k has been composed o i e p oblems om
he ZDT amily, using ins ance sizes anging om 8 o 2048
a iables. We ha e also s udied he speed o he echniques
when sol ing he p oblems. The s opping condi ion has been
o each a on wi h a hype olume highe han he 98% o he
hype olume o he ue Pa e o on , o o compu e 10 000 000
unc ion e alua ions.
Ou s udy has e ealed ha di e en ial e olu ion and pa -
icle swa m op imiza ion a e he mos p omising app oaches
o deal wi h he scalable p oblems used in his pape . GDE3
and OMOPSO do no only scale well, bu hey a e among
he as es algo i hms. Fu he mo e, we ha e shown ha hei
sea ch capabili ies can be imp o ed o sol e ZDT4, he p ob-
lem which has appea ed as he mos di icul one o sol e.
Two mode n op imize s, MOCell and AbYSS, ha e shown
a high deg ee o egula i y in he es s. Wi h he excep ion
o MOCell in ZDT4 (whe e i is he o e all bes echnique),
hey a e no in he i s posi ion in he scalabily and he speed
ankings, bu also hey a e always a ound he hi d and i h
posi ions. Bo h me aheu is ics a e in he g oup o algo i hms
ha ing sol ed a highe numbe o ins ances. In his g oup we
ind NSGA-II and SPEA2, which a e, in gene al, e y close in
he ankings, bu hey usually appea a e MOCell. PESA-II
has di icul ies in ZDT2 and i no mally appea s among he
algo i hms equi ing highe numbe s o unc ion e alua ions
o each a on wi h he a ge HV alue.
Finally, PAES, he simples o he op imize s in he pape ,
is he algo i hm scaling he wo s , due o he low hi a es i
ob ains in many ins ances.
We ha e p esen ed a pape abou he beha io o eigh
mul iobjec i e me aheu is ics conce ning hei scalabili y and
speed when sol ing a scalable benchma k. The nex s ep is an
ex ension including mo e scalable p oblems (e.g., DTLZ and
WFG) o assess whe he o no he ea u es o hese p oblems
con i m he esul s ob ained in his pape . Ou analysis o
OMOPSO and GDE3 has also shown ha an open esea ch
line is o s udy a ia ions and di e en pa ame e se ings o
he exis ing mul iobjec i e me aheu is ics in o de o imp o e
hei scalabili y, and ha is ano he pa h o u u e esea ch
ha we aim o explo e.
Re e ences
[1] C. Blum and A. Roli, “Me aheu is ics in combina o ial op imiza ion:
O e iew and concep ual compa ison,” ACM Compu . Su eys, ol. 35,
no. 3, pp. 268–308, 2003.
[2] D. B ockho and E. Zi zle , “A e all objec i es necessa y? On di-
mensionali y educ ion in e olu iona y mul iobjec i e op imiza ion,”
in P oc. Nin h In . Con . Pa allel P oblem Sol ing Na u e (PPSN),
Lec u e No es in Compu e Science 4193. Reykja ik, Iceland, Sep. 2006,
pp. 533–542.
[3] E. K. Bu ke and G. Kendall, Sea ch Me hodologies: In oduc o y Tu-
o ials in Op imiza ion and Decision Suppo Techniques. New Yo k:
Sp inge , 2005.
[4] M. Cle c and J. Kennedy, “The pa icle swa m: Explosion, s abili y, and
con e gence in a mul idimensional complex space,” IEEE T ans. E ol.
Compu ., ol. 6, no. 1, pp. 58–73, 2002.
[5] C. A. Coello Coello, G. B. Lamon , and D. A. Van Veldhuizen,
E olu iona y Algo i hms o Sol ing Mul iobjec i e P oblems, 2nd ed.
New Yo k: Sp inge , Sep. 2007.
[6] D. W. Co ne, N. R. Je am, J. D. Knowles, and M. J. Oa es, “PESA-II:
Region-based selec ion in e olu iona y mul iobjec i e op imiza ion,” in
P oc. Gene ic E ol. Compu . Con . (GECCO), San Ma eo, CA: Mo gan
Kau mann, 2001, pp. 283–290.
[7] K. Deb, Mul iobjec i e Op imiza ion Using E olu iona y Algo i hms.
Chiches e , U.K.: Wiley, 2001.
[8] K. Deb, A. P a ap, S. Aga wal, and T. Meya i an, “A as and eli is
mul iobjec i e gene ic algo i hm: NSGA-II,” IEEE T ans. E ol. Compu .,
ol. 6, no. 2, pp. 182–197, Ap . 2002.
[9] K. Deb, L. Thiele, M. Laumanns, and E. Zi zle , “Scalable es p oblems
o e olu iona y mul iobjec i e op imiza ion,” in E olu iona y Mul-
iobjec i e Op imiza ion: Theo e ical Ad ances and Applica ions,A.
Ab aham, L. Jain, and R. Goldbe g, Eds. New Yo k: Sp inge , 2005,
pp. 105–145.
[10] F. di Pie o, S. Khu, and D. A. Sa i´
c, “An in es iga ion on p e e ence
o de anking scheme o mul iobjec i e e olu iona y op imiza ion,”
IEEE T ans. E ol. Compu ., ol. 11, no. 1, pp. 17–45, Feb. 2007.
[11] J. J. Du illo, A. J. Neb o, C. A. Coello Coello, F. Luna, and E. Alba, “A
compa a i e s udy o he e ec o pa ame e scalabili y in mul iobjec i e
me aheu is ics,” in P oc. Cong . E ol. Compu . (CEC), Jun. 2008, pp.
1893–1900.
[12] J. J. Du illo, A. J. Neb o, F. Luna, B. Do onso o, and E. Alba,
“Jme al: A Ja a amewo k o de eloping mul iobjec i e op imiza ion
me aheu is ics,” Dep . Lenguajes Ciencias Compu aci´
on, Uni . M´
alaga,
ETSI In o m´
a ica, M´
alaga, Spain, Tech. Rep. ITI-2006-10, 2006.
[13] F. W. Glo e and G. A. Kochenbe ge , Handbook o Me aheu is ics.
No ell, MA: Kluwe , 2003.
[14] S. Ho, L. Shu, and J. Chen, “In elligen e olu iona y algo i hms o la ge
pa ame e op imiza ion p oblems,” IEEE T ans. E ol. Compu ., ol. 8,
no. 6, pp. 522–541, Dec. 2004.
[15] S. Huband, L. Ba one, R. L. While, and P. Hings on, “A scalable
mul iobjec i e es p oblem oolki ,” in P oc. Thi d In . Con . E ol.
Mul ic i e ion Op imiza ion (EMO), Lec u e No es in Compu e Science
3410. Be lin, Ge many: Sp inge , 2005, pp. 280–295.
[16] S. Huband, P. Hings on, L. Ba one, and L. While, “A e iew o
mul iobjec i e es p oblems and a scalable es p oblem oolki ,” IEEE
T ans. E ol. Compu ., ol. 10, no. 5, pp. 477–506, Oc . 2006.
[17] V. Kha e, X. Yao, and K. Deb, “Pe o mance scaling o mul iobjec-
i e e olu iona y algo i hms,” in P oc. Second In . Con . E ol. Mul i-
C i e ion Op imiza ion (EMO), Lec u e No es in Compu e Science
2632. Fa o, Po ugal, Ap . 2003, pp. 376–390.
[18] J. Knowles and D. Co ne, “The pa e o a chi ed e olu ion s a egy: A
new baseline algo i hm o mul iobjec i e op imiza ion,” in P oc. Cong .
E ol. Compu ., 1999, pp. 98–105.
[19] J. D. Knowles and D. W. Co ne, “App oxima ing he nondomina ed
on using he pa e o a chi ed e olu ion s a egy,” E ol. Compu ., ol. 8,
no. 2, pp. 149–172, 2000.
[20] S. Kukkonen and J. Lampinen, “GDE3: The hi d e olu ion s ep o
gene alized di e en ial e olu ion,” in P oc. IEEE Cong . E ol. Compu .
(CEC), 2005, pp. 443–450.
[21] J. Lampinen, “DE’s selec ion ule o mul iobjec i e op imiza ion,” Dep .
In . Technol., Lappeen an a Uni . Technol., Lappeen an a, Finland,
Tech. Rep., 2001.
[22] H. Li and Q. Zhang, “Mul iobjec i e op imiza ion p oblems wi h compli-
ca ed pa e o se , MOEA/D and NSGA-II,” IEEE T ans. E ol. Compu .,
ol. 2, no. 12, pp. 284–302, Ap . 2009.
[23] A. J. Neb o, F. Luna, E. Alba, B. Do onso o, J. J. Du illo, and A. Be-
ham, “AbYSS: Adap ing sca e sea ch o mul iobjec i e op imiza ion,”
IEEE T ans. E ol. Compu ., ol. 12, no. 4, pp. 439–457, Aug. 2008.
[24] A. J. Neb o, J. J. Du illo, F. Luna, B. Do onso o, and E. Alba, “A cellu-
la gene ic algo i hm o mul iobjec i e op imiza ion,” in P oc. Wo kshop
Na u e Inspi ed Coope a i e S a egies Op imiza ion (NICSO), G anada,
Spain, 2006, pp. 25–36.
[25] A. J. Neb o, J. J. Du illo, F. Luna, B. Do onso o, and E. Alba, “Design
issues in a mul iobjec i e cellula gene ic algo i hm,” in P oc. Fou h
In . Con . E ol. Mul i-C i e ion Op imiza ion (EMO), Lec u e No es in
Compu e Science 4403. 2007, pp. 126–140.
[26] K. P adi wong and X. Yao, “How well do mul iobjec i e e olu iona y
algo i hms scale o la ge p oblems,” in P oc. IEEE Cong . E ol. Compu .
(CEC), Sep. 2007, pp. 3959–3966.
[27] R. C. Pu shouse and P. J. Fleming, “On he e olu iona y op imiza ion
o many con lic ing objec i es,” IEEE T ans. E ol. Algo i hms, ol. 11,
no. 6, pp. 770–784, Dec. 2007.
[28] M. Reyes and C. A. Coello Coello, “Imp o ing PSO-based mul iobjec-
i e op imiza ion using c owding, mu a ion and -dominance,” in P oc.
Thi d In . Con . E ol. Mul ic i e ion Op imiza ion (EMO), Lec u e No es
in Compu e Science 3410. Be lin, Ge many: Sp inge , 2005, pp. 509–
519.
[29] D. K. Saxena and K. Deb, “Non-linea dimensionali y educ ion p o-
cedu es o ce ain la ge-dimensional mul iobjec i e op imiza ion p ob-
lems: Employing co en opy and a no el maximum a iance un olding,”
in P oc. Fou h In . Con . E ol. Mul ic i e ion Op imiza ion (EMO),
Lec u e No es in Compu e Science 4403. Ma sushima, Japan, Ma .
2007, pp. 772–787.
[30] D. J. Sheskin, Handbook o Pa ame ic and Nonpa ame ic S a is ical
P ocedu es, 4 h ed. New Yo k: Chapman & Hall/CRC P ess, 2007.
[31] D. Thain, T. Tannenbaum, and M. Li ny, “Dis ibu ed compu ing in
p ac ice: The condo expe ience,” Concu ency Compu . P ac ice Expe-
ience, ol. 17, nos. 2–4, pp. 323–356, Feb. 2005.
[32] D. A. Van Veldhuizen and G. B. Lamon , “Mul iobjec i e e olu iona y
algo i hm esea ch: A his o y and analysis,” Dep . Elec. Compu . Eng.,
G adua e School Eng., Ai Fo ce Ins . Technol., W igh -Pa e son A b,
OH, Tech. Rep. TR-98-03, 1998.
[33] Q. Zhang and H. Li, “MOEA/D: A mul iobjec i e e olu iona y algo i hm
based on decomposi ion,” IEEE T ans. E ol. Compu ., ol. 8, no. 11,
pp. 712–731, 2008.
[34] E. Zi zle , K. Deb, and L. Thiele, “Compa ison o mul iobjec i e
e olu iona y algo i hms: Empi ical esul s,” E ol. Compu ., ol. 8,
no. 2, pp. 173–195, 2000.
[35] E. Zi zle , M. Laumanns, and L. Thiele, “SPEA2: Imp o ing he
s eng h pa e o e olu iona y algo i hm,” in P oc. E ol. Me hods Design
Op imiza ion Con ol Applica . Ind. P oblems (EUROGEN), A hens,
G eece, 2002, pp. 95–100.
[36] E. Zi zle and L. Thiele, “Mul iobjec i e e olu iona y algo i hms: A
compa a i e case s udy and he s eng h pa e o app oach,” IEEE T ans.
E ol. Compu ., ol. 3, no. 4, pp. 257–271, No . 1999.
Juan J. Du illo (S’08) ecei ed he Enginee ing
deg ee in compu e science om he Uni e si y o
Málaga, Málaga, Spain, in 2006. He is cu en ly
pu suing he Ph.D. deg ee om he Depa amen o de
Lenguajes y Ciencias de la Compu aci´
on, Uni e si y
o M´
alaga.
His esea ch in e es s include mul iobjec i e op i-
miza ion and he design o new models o pa allel
mul iobjec i e me aheu is ics.
An onio J. Neb o ecei ed he M.S. and Ph.D.
deg ees in compu e science om he Uni e si y o
M´
alaga, M´
alaga, Spain, in 1992 and 1999, espec-
i ely.
He is cu en ly an Associa e P o esso o Com-
pu e Science wi h he Depa amen o de Lenguajes
y Ciencias de la Compu aci´
on, Uni e si y o M´
alaga.
Since 1999, he has published mo e han en scien-
i ic pape s in in e na ional indexed jou nals, mo e
han 20 pape s in in e na ional con e ences, and co-
au ho ed 12 book chap e s. His cu en esea ch
in e es s include he design and implemen a ion o pa allel e olu iona y
algo i hms, mul iobjec i e op imiza ion wi h me aheu is ics, g id compu ing
applied o me aheu is ic echniques, and he applica ion o hese echniques
o eal-wo ld p oblems.
Ca los A. Coello Coello (SM’04) ecei ed he B.S.
deg ee in ci il enginee ing om he Uni e sidad
Au ónoma de Chiapas, Chiapas, Mexico, in 1991,
and he M.S. and Ph.D. deg ees in compu e science
om Tulane Uni e si y, New O leans, LA, in 1993
and 1996, espec i ely.
He is cu en ly a P o esso wi h he Depa men
o Compu e Science, Cen e o Resea ch and Ad-
anced S udies, Mexico Ci y, Mexico. He has au-
ho ed and coau ho ed o e 200 echnical pape s and
se e al book chap e s, which epo o e 3600 ci a-
ions (hal o hem in he Ins i u e o Scien i ic In o ma ion Web o Science).
He coau ho ed he book E olu iona y Algo i hms o Sol ing Mul iobjec i e
P oblems (2nd ed., New Yo k: Sp inge , 2007).
D . Coello is cu en ly an Associa e Edi o o he IEEE T ansac ions on
E olu iona y Compu a ion and se es in he Edi o ial Boa d o 11 o he
in e na ional jou nals. He also chai s he IEEE Compu a ionally In elligen
Socie y Task Fo ce on Mul iobjec i e E olu iona y Algo i hms. He ecei ed
he 2007 Na ional Resea ch Awa d om he Mexican Academy o Sciences in
he a ea o Exac Sciences. He is a membe o he Associa ion o Compu ing
Machine y, Sigma Xi, and he Mexican Academy o Sciences.
José Ga cía-Nie o ecei ed he Enginee ing deg ee
in compu e science and he Mas e deg ee in a -
i icial in elligence om he Uni e si y o Málaga,
Málaga, Spain, in 2006 and 2008, espec i ely.
He is cu en ly wo king owa d he Ph.D. deg ee
in op imiza ion algo i hms a he Depa amen o de
Lenguajes y Ciencias de la Compu aci´
on, Uni e si y
o M´
alaga.
His esea ch in e es s include swa m in elligence
and gene al me aheu is ics, and hei applica ion
o complex eal-wo ld p oblems in he domains
o elecommunica ions, bioin o ma ics, eal-pa ame e , and mul iobjec i e
op imiza ion.
F ancisco Luna ecei ed he Ph.D. deg ee in
compu e science om he Uni e si y o M´
alaga,
M´
alaga, Spain, in 2008.
He is cu en ly an Assis an Resea che o com-
pu e science wi h he Depa amen o de Lenguajes
y Ciencias de la Compu aci´
on, Uni e si y o M´
alaga.
He has published mo e han en scien i ic pape s
in in e na ional indexed jou nals and mo e han
20 pape s in in e na ional con e ences. His cu en
esea ch in e es s include he design and implemen-
a ion o pa allel and mul iobjec i e me aheu is ics,
and hei applica ion o sol e complex p oblems in he domain o elecom-
munica ions and combina o ial op imiza ion.
En ique Alba ecei ed he Ph.D. deg ee in com-
pu e science on pa allel and dis ibu ed gene ic
algo i hms, in 1999.
He is cu en ly a Full P o esso o Compu e
Science wi h Depa amen o de Lenguajes y Ciencias
de la Compu aci´
on, Uni e si y o M´
alaga, M´
alaga,
Spain. Since 1999, he has published mo e han 30
scien i ic pape s in in e na ional indexed jou nals
and mo e han 150 pape s in in e na ional con-
e ences. His esea ch in e es s include he design
and applica ion o e olu iona y algo i hms and o he
me aheu is ic p ocedu es o eal p oblems, including elecommunica ions,
combina o ial op imiza ion, and bioin o ma ics. The main ocus o all his
wo k is on pa allelism.
D . Alba has won se e al awa ds o his esea ch quali y.