Multiobjective Evolutionary Algorithm Test Suites

David A. Van Veldhuizen and Gary B. Lamont

Department of Electrical and Computer Engineering
Graduate School of Engineering
Air Force Institute of Technology
Wright-Patterson AFB, OH 45433-7765
{dvanveld,lamont}Qafit.af.mil

We thank Mr. Mike Putney for his support during code These empirical comparisons do not contribute much to
development and implementation, and the ASC MSRC for a common basis for MOEA comparison. The literature’s
providing the computing platforms. history of visually comparing MOEA performance on non-
standard and unjustified numeric MOPS does little to deter-
Abstract mine a given MOEA’s efficiency and effectiveness. A stan-
dard suite of numeric functions exhibiting relevant MOP
Multiobjective Evolutionary Algorithms (MOEAs) cur- problem domain characteristics provides a common compar-
rently have no generic benchmark test suites. This pa- ative basis.
per provides several Multiobjective Optimization Problems The MOEA community’s limited de facto test suite con-
(MOPS) for use as part of a standardized MOEA test suite, tains many functions used only because they appear to exer-
and proposes a methodology whereby various MOEAs can cise MOEA capabilities, or perhaps because other research-
be directly compared. Supporting these contributions is a ers used them as examples for their algorithms. Thus, a
detailed discussion of MOP landscape and general test suite documented MOP test suite is an asset to MOEA research.
issues, and presentation of a new theorem defining the struc- We provide various numeric MOPS for use in a standard-
tural limitations of an MOP’s global optimum. This paper ized MOEA test suite, and propose a methodology whereby
also discusses high-performance computer software deter- various MOEAs can be directly compared. Supporting these
ministically computing an MOP’s Pareto front at a given contributions is a detailed discussion of the MOP domain
computational resolution. and general test suite issues; a new theorem defining one
MOP characteristic and possible multiobjective NP-Complete
problems are also presented.
1 Introduction This paper is organized as follows. Section 2 introduces
necessary MOP concepts and related terminology. Section 3
Multiobjective Evolutionary Algorithms (MOEAs) are discusses general test suite issues and proposes appropriate
now a well-established field within Evolutionary Compu- numeric examples given the MOP domain. Section 4 offers
tation. They were “born” in 1985 when SchafIer (161 and a methodology for quantitatively comparing MOEA perfor-
Fourman [S] implemented the first MOEAs dealing with mance. Our conclusions and future work are presented in
Multiobjective Optimization Problems (MOPS). Since then, Section 5.
over 140 published papers propose various MOEA imple-
mentations and applications, and to a much lesser extent,
underlying MOEA theory [19]. Many of these efforts use nu- 2 Introducing the MOP Domain
meric MOPS as examples to show algorithmic performance.
Sowhere in the literature, however, is there a comprehensive Although a single objective optimization problem may
discussion of MOP landscape issues; nor is there any expla- have a unique optimal solution, MOPS (as a rule) present a
nation of why numeric MOPS may be appropriate MOEA possibly uncountable set of solutions, which when evaluated
test functions. produce vectors whose components represent trade-offs in
To date, most MOEA researchers’ modus operundi is an decision space. A decision maker then implicitly chooses
algorithm’s comparison (usually the researcher’s own new an acceptable solution by selecting one of these vectors. In
and improved variant) against an older MOEA and analyz- mathematical terms, an MOP minimizes’ the components of
ing results for some MOP (typically Schaffer’s MOEA and a vector F(Z) where f is an n-dimensional decision variable
examples [IS]). Many other example numeric MOPS are vector(s=zr,..., 2,) from some universe Q. Or in general,
also used [19]. Results are often “clearly” shown in graphi-
cal form, indicating which algorithm is more effective. minimize F(q = (fl(%***,fk(z))
subject to gi(z? 5 0,i = l,..., m, fc 0. (1)
An MOP thus consists of n variables, m constraints, and
k objectives, of which any or aJl of the objective functions
may be linear or nonlinear [12]. The MOP’s evaluation func-
1998 ACM l-58113-086-4/99/0001
tion, F : 52---) A, maps the decision variables to vectors.
‘Or maximises,sincemin(F(z)} = -msx{-F(z)}.
 2.1 Pareto Optimality and Terminology P currentI pk n0wun,
and Pt,, are sets of MOEA genotypes’;
each set’s phenotypes form a Pareto front. We term the
We have shown in a previous work [18] that the global associated Pareto front for each .of these solution sets as
optimum of an MOP is the Pareto front determined by eval- PFcumnt , PFk,,,, , and PFtruc. Thus, when using an MOEA
uating each member of the Pareto optimal solution set. Al- to solve MOPS, the implicit assumption is that one of the fol-
though “Pareto optimality,” and its related concepts and lowing holds: pkmowm = Pt,,, Pknow, C Pt...,,, or PFk,,,, E
terminology are frequently invoked, they are sometimes used [PFtrue, PFt,, + E] over some norm (Euclidean, RMS, etc.).
incorrectly in the literature. To ensure understanding and
consistency, we define Pareto Dominance and Optimality,
and introduce an associated notation. Using the MOP nota- 2.3 MOP Domain Features
tion presented in Equation 1, key Pareto concepts are math- What is the nature of a given MOP’s Pareto optimal
ematically defined as follows (11: set (Pt,, )? Few MOEA efforts report any description of
an example MOP’s underlying decision variable space, i.e.,
rion 1 (Pareto Dominance): A vector u = the space where Pt,, resides. Since an MOP is normally
I”‘, uk) is said to dominate v = (VI, . . . , vk) if and composed of two or more single-objective optimization prob-
only if u is partially less than v, i.e., lems, the solution space is restricted by the limitations of
vi E (1,. . . , k}, Ui 5 Vi A 3 E (1,. . . , k} 1 Ui < Vi. 0 those combined functions. Within that space, Pt,.,,, may be
connected, disconnected, a hyperarea, separate points, etc.
However, in MOEA search the Pareto front is of more in-
Deflnition 2 (Pareto Optimality): A solution x,, E R terest because solutions are often implicitly determined via
ia said to be Pareto optimal if and only if there ia no xv E 52 selecting a point from PFknomn.
for which v = f(x,) = (VI,. . . , Vk) dominate8 u = f (x,) = What is the nature of the Pareto front (PFt,.)? It
(W,...,Uk). 0 may be (dis)continuous, convex or concave, and multi-di-
mensional. Other researchers have noted that the structure
Pareto optimal solutions are also termed non-inferior, of any Pareto front (independent of dimensionality) haa the-
admissible, or eficient solutions. Their corresponding vec- oretical limitations. For example, any Pareto surface must
tors are termed non-dominated [lo]; selecting a vector(s) be monotonic (i.e., all first-order partial derivatives never
from this non-dominated vector set implicitly indicates ac- change sign), and has asymptotic bounds [5, 111. We have
ceptable Pareto optimal solutions (genotypes). These so- recently realized that an additional structural limitation ex-
lutions may have no clearly apparent relationship besides ists, and developed a theorem describing it.
their membership in the Pareto optimal set. This is the set
of all solutions whose associated vectors are nondominated; 2.3.1 PFt,, ‘s Structure
we stress here that Pareto optimal solutions are classified as
such based on their phenotypical expression. Their expres-
sion (the nondominated vectors), when plotted in criterion Theorem 1: The Pareto front of an MOP with Ic = 2
space, is known as the Pareto front. MOEA researchers have objectives is at most a (restricted) curve, and is at most a
inconsistently used these terms in the literature, suggesting (restricted) surface when k 2 3. 0
a more precise notation is required.
Proof: By definition, all vectors of the Pareto front are
2.2 Pareto Notation nondominated Given a minimization MOP, assume PFt,.,,, is
either a polygon (k = 2) or a hypervolume (k 1 3). Now
During MOEA execution, a “local” set of Pareto optimal take an imaginary line parallel to any of the objective axes
solutions (with respect to the current MOEA population) passing through at least two points (represented by vectors)
is determined at each EA generation and termed Peumnc. of the polygon or hypervolume. Since performance in each
Many MOEA implementations also use a secondary pop objective is to be minimized, one of these points is clearly
ulation, storing nondominated solutions found through the “better” than the other and dominates it. But PFt,,is
generations [19]. Because a solution’s classification aa Pareto composed only of nondominated vectors. Thus, the original
optimal depends upon the context within which it is eval- assumption is incorrect and the Pareto front of an MOP with
uated (i.e., the given set of which it’s a member), corre two objectives is at most a (restricted) curve, and that of an
sponding vectors of this set must be (periodically) tested, MOP with three or more objectives is at most a (restricted)
removing solutions whose associated vectors are dominated. surface. 0
We term this secondary population Ph.,,,,,, . However, Horn states that in a k-objective MOP, the Pareto front
to reflect the possible changes in membership between gen- ia a k - 1 dimensional surface [ll]. We have just shown this
erations we annotate our notation with the variable t rep- is incorrect; PFt,. is at moat a surface on(y when k 2 3. Al-
resenting the completion of t generations (e.g., Pb,,, (t)). though asymptotic bounds are useful, researchers must also
Pk.,,,,,, (0) is defined as 0 and Pk,O, alone as the final Set of understand the front’s possible shape within those bounds.
solutions returned by the MOEA. This theorem also implies that any MOEA test suite
Different secondary population storage strategies exist; should contain MOPS with both types of Pareto fronts: k-
the simplest is when Pcumnc is added at each generation (i.e., dimensional curves and 3-dimensional surfaces. This is nec-
P cumn! u pkmwm (t - 1)). At any given time, PI,,,,,,, (t) is essary to fully test an MOEA’s search capability.
thus the set of Pareto optimal solutions yet found by the
MOEA through generation t. Of course, the true Pareto op-
timal solution set (termed P,,,) is not explicitly known for
problems of any difficulty. PtNI is defined by the functions
composing an ,MOP; it is fixed and does not change. Be-
cause of the manner in which Pareto optimality is defined
Pcvrrcnt is always a non-empty solution set [18].

352
 3 An MOEA Test Function Suite Many of the numerical examples used by MOEA researchers
do not explicitly meet this criteria. Our research identifies
Test function suites have both supporters and detrac- over 25 different numerical MOPS (both constrained and
tors. Any algorithm successfully passing all submitted test unconstrained) used in published MOEA efforts [19]. All
functions has no guarantee of continual effectiveness and ef- but three use at most two decision variables and the ma-
ficiency (i.e., examples prove nothing). Automotive passen- jority use only two objective functions. This implies that
ger airbags are a prime example; not until they were widely unless the search space is very large, MOEA performance
fielded was it discovered that airbag-babyseat interactions claims and comparisons based on these functions may not be
were possibly deadly. Pattern recognition work has also meaningful. The algorithm may be operating in a problem
recognized the problem of “testing on the training data,” domain not particularly well-suited to its capabilities. Rel-
where an algorithm is tuned for only one or a few problem evant MOP problem domain characteristics must be iden-
instances [3]. These analogies hold when integrating prob- tified and considered in selecting appropriate MOEA test
lem and algorithm domains: new and unforeseen situations suite functions.
may arise resulting in undesirable consequences. Thus, an
MOEA test suite can be a valuable tool only if relevant is- 3.2 MOEA Test Suite Functions
sues are properly considered.
As indicated, a de facto test suite exists. We have else-
3.1 General MOEA Test Suite Issues where cataloged these functions and in this paper identi-
fied several MOP characteristics which must be dealt with
The “NO Free Lunch” (NFL) theorem [22] implies that by effective and efficient MOEAs 1191. An extensive liter-
if problem domain knowledge is not incorporated into the ature search has identified 28 numerical example MOPS;
algorithm domain, no formal assurances of an algorithm’s these MOPS incorporate 2-3 functions and O-12 side con-
general effectiveness exist. Previously, EA test suites con- straints. We now propose initial problems for an MOP test
taining various functions were proposed for testing an EA’s suite drawn from the published literature, which incorpo-
capability to “handle” various problem domain characteris- rate selected characteristics and address some of the issues
tics. These suites incorporate relevant search space features in Sections 3.1.
which should be addressed by a particular EA instantiation. We initially propose the three MOPS listed in Table 1.
For example, De Jong [2] suggests five single-objective op- MOP& an unconstrained two-objective MOP [16], is se-
timization test functions (Fl - FS), and Michalewicz [13] lected for three primary reasons. First is its historical sig-
suggests five single-objective conatmined optimization test nificance; almost all proposed MOEAs have been tested us-
functions(G1 - GS). Whitley et al. [21] and Goldberg et ing this function. It is also an exemplar of relevant MOP
al. [8] offer other test suite functions. Whitley et al. also concepts. Secondly, as we have noted elsewhere [18], this
offer general test suite guidelines which include incorporat- MOP sllows us to determine an analytical expression for
ing real world problems, problems ranging in difficulty from PFt,, (a curve) through substitution. Third, as noted by
“easy” to “hard”, and scalable problems. Rudolph [15], this MOP’s P,,, is given in closed form. At
De Jong’s test bed includes functions with the follow- any resolution, the representation of solutions composing
ing characteristics [7]: continuous and discontinuous, convex Pt,, is thus easily determined without the necessity of ex-
and nonconvex, unimodal and multimodal, quadratic and haustively enumerating the search space. However, its one
nonquadratic, low- and high-dimensionality, and determin- decision variable implies a large search space should be used
istic and stochastic. Michalewicz’s test bed addresses the when testing an MOEA.
following issues [13]: type of objective function, number of MOP2 is also an unconstrained two-objective MOP, hav-
decision variables and constraints, types of constraints, num- ing the additional advantage of arbitrarily adding decision
ber of active constraints at the function’s optimum, and the variables without changing PFt,. ‘s structure; Pt,, is also
ratio between the feasible and complete search space size. given in closed form [4]. Figures 1 and 2 shows MOP2’s
Particular EA instantiations are then subjected to test beds Pareto optimal set and front.
like these and judged on their performance. Finally, we propose MOPS [20]. This MOP has three
Note that the NFL theorem also implies that incorpo- objective functions, and its Pareto front appears to be a
rating too much problem domain knowledge into a search Ic-dimensional curve following a convoluted path through
algorithm reduces its effectiveness on other problems. How- objective space. This characteristic should challenge an
ever, as long as a test suite involves only major problem MOEA’s ability to find and maintain the entire front. Fig-
domain characteristics, any search algorithm giving effec- ures 3 and 4 show MOP3’s Pareto optimal set and front.
tive and efficient results over the test suite might remain Figures 1 through 4 are deterministically derived by com-
broadly applicable to problems from that domain Thus, we puting all variable combinations possible at a given compu-
must define traits common to all (most) MOPS for test suite tational resolution. As this underlying resolution is varied
consideration. the figures may slightly change.
When implementing an MOEA, it is (implicitly) assumed Although previously presented in the literature, these
that the problem domain (fitness landscape) has been exam- MOPS’ characteristics address some of the issues mentioned
ined, and a decision made that an MOEA is the most appro- in Section 3.1. MOP1 is arguably an “easy” MOP. MOP2
priate search tool for the given MOP. We also assume the is scalable, in that any number of decision variables may
&fOEA returns PA,.,,, , i.e., a set of solutions. It is not clear be used to increase the search space. MOP3’s functions
that all existing test functions are appropriate MOEA exam- result in a nonlinear and asymmetric PFI,, . Taken to-
ples; thus, identification of appropriate functions is required gether they begin to form a coherent basis for MOEA com-
to objectively determine MOEA efficiency and effectiveness. parisons. Other relevant MOP characteristics should be ad-
In general, it is accepted that EAs are useful search algo- dressed by further MOPS selected for test suite inclusion.
rithms when the problem domain is multidimensional (many Desired MOPS may need to be specifically constructed to
decision variables), and/or the search space is very large. exhibit desired characteristics.
 Table 1: Initial MOEA Test Suite Functions [19]
[ MOP Detlnition constrainte
F = (h(z), h(z)), where NolIe

f1(+) = 2,
h(2) = (5 - 2y

F = (h(S), h(S)), where -2 2 ti < 2

A(S) = 1 - exp(- &z, - $),

I=*
h(S) = 1 - exd- k(z, + -$Y)
1+1

M PS F = (fl(s, I/),fz(z, Y),fs(z, u)), where -3<z,y53

fl(Z,U) = 0.5* (2 + $2)t ain(2 + It),

(32 - 2Y t 411 f (2 - y t 112 f 15
fZ(5,Y) = a 27
1 _ l,le(-=%a)
fs(=,lJ) = (=a + g + 1)
-

MOP2 Pareto Cptlmal SoluUons

0.6
. *
0.6 - a * I .
* I I
0.4 - * * II
I * I
0.2 - l * i

* I I
3
* I I
a
:
zw
O-

N I *
SO’“-
-0.2 - * l * 0.4 -
l M *
0.3-
-0.4 - * I x
I I * 0.2-
-0.6 - l l -

l *
0.1-
11
t
-"z3.6 -0i -0:4 xl:2 ,-e,, 0:2 014 oi 0.6 OL
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.6 0.6 1
Funclion1

Figure 1: MOP25 Pareto Optimal Set Figure 2: MOP2’s Pareto Rant

3.3 NP-Complete MOPS jective knapsack problem) [23], and the other is a unitation
We also consider the use of combinatorial optimization problem [ll].
problems in the test suite. EAs often employ specialized
representations and operators when solving these real-world 4 MOEA Experimental Methodology
problems. This may prevent generai comparison between
various MOEAs, but the problems’ inherent difficulty should Having investigated the MOP domain and proposed func-
present the desired algorithmic challenges and complement tions for an MOP test suite, we are now in a position to per-
numeric test suite MOPS. Table 2 suggests possible NP- form meaningful MOEA experiments. Although test suite
Complete MOPS for inclusion. To date, only two non-nu- functions provide a common basis for MOEA comparison,
merical LMOP examples are found in the MOEA literature: these comparisons are still empirical unless PFt,, is known.
one is a multiobjective NP-Complete example (a multiob- We earlier intimated this is the case for most MOPS of any
 Table 2: Possible Multiobjective NP-Complete Functions

MOP3 Pareto cplimi s&uons MOP3 Pareto Front

0.2

0.15

0.1 I
-0.5 -
a
33 -l- :i
.:"*
L *Ex
-1.5- ::
a
x
a:*
-2-i g::
u'I*
l :*

Fundlon2 15 0
Fwdbnl
-3 -2.5 -2 -1.5 -1 -0.5 0
x-value

Figure 4: MOP3’s Pareto Front

Figure 3: MOP3’s Pareto Optimal Set
and solving the following:
complexity. However, there is a way to determine PFt,. at I+ i*(u-Z)
a given computational resolution! This section describes (2)
such a process we are currently using to construct an exper- 2”-1 ’
imental database. It also suggests appropriate metrics when where 1 and u correspond to the 1owe.rand upper decision
quantitatively comparing MOEAs. variable bounds, and n is the length of the binary string.
We suggest both a large search space and a binary en-
4.1 Experimental Database coding for any MOEA comparisons. The large search space
challenges an MOEA’s ability to 6nd the global optimum;
When the real (continuous) world is modeled (e.g., via the binary encoding aJlows for both a standard chromosomal
objective functions) on a computer (a discrete machine), representation and a method for deterministically searching
there is a fidelity loss between the real world and imple- an entire space. At a given resolution, each of the 2” bi-
mented model. However, at a standardized resolution and nary strings is enumerated and evaluated, thus obtaining
representation, MOEA results can be compared against both Pt,, and PFI,, (at that resolution).
each other and PFt,. . Thus, whether or not a given MOP’s For example, assume a 30-bit binary encoding. This
true Pareto front is actually continuous or discrete is then search space contains 230 possible solutions, over one billion
not a major concern, as the computed front is always com- distinct possibilities! Published results indicate most EAs
posed of discrete points at a specified computational resolu- execute between thousands and tens of thousands of fitness
tion. evaluations during search; the efFectiveness of any MOEA
For purposes of this discussion we determine computa- should be readily apparent in how well its results (Ph,, and
tional resolution by the equidistant sampling of points in
each decision variable dimension. For example, with a fixed PAmom 1 compare to fi,.,,. and PFt,. in a search space of
this large size. We have constructed an experimental data,
length binary string, the associated decision variable value base allowing this comparison for the proposed MOEA test
is determined by mapping the binary string to an integer i suite functions [19].
This effort is in part due in part to a paper suggest-
ing that exhaustive search may be the only viable approach

355
 to solving irregular or chaotic problems [14]. The authors vector (phenotype) dominates another’s (mathemat-
propose harnessing ever-expanding computational capabil- ically represented by a 4 b), or the two solutions are
ity to solve problems by exhaustive deterministic enumeril- equal (a = b). Coverage defines the size of objec-
tion. We constructed such a program executing on the IBM tive value space covered by PFk,,,,, . For example,
SP-2. a point on PFk,,,, in the two-dimensional (minimize
Our program’s “C” implementation uses the Message tion) case defines a rectangle bounded by the origin
Passing Interface (MPI) to distribute function evaluations and (fi(z), fz(z)). The union of sll such rectangles
among many processors. For a given MOP, each processor defined by each vector in P&,,,, is used as the com-
initially evaluates some subset of solutions and stores the re- parative measure. However, if PFt,. is not convex
sultant vectors. These vectors are compared on the basis of this metric may be misleading. Thus, for any two
Pareto optimality; nondominated solutions and their corre- pk.mm sets, they compute the fraction of solutions in
sponding vectors are written to disk. Noting that Pareto op- one set covered by solutions in the other.
timality places a partial ordering on the entire search space,
combining the separate solutions/vectors from different pro- Spread. Another possible metric is one measuring the spread
cessorsand again comparing vectors results in Pi,.,,, for that (distribution) of vectors throughout PFknow,,. Many
particular binary encoded resolution. Program timing and MOEAs perform sharing and niching [5, 11, 171, at-
processor loading are also recorded to determine problem tempting to spread each population (PFcumnt ) even-
scaling. To date, we have successfully extracted one MOP’s ly along the front. Because the true front’s “begin-
Pt,,, from a search space of size 2” and am currently com- ning” and “end” are known (at some resolution), a
puting MOP2 and MOP3’s Pt,, . suitably defined metric judges how well PFk,,,,, con-
Using this database, solutions offered by various MOEAs forms. Srinivas and Deb [17] define such a measure
can be compared not only against each other, but against expressing how well an MOEA has distributed indi-
the true Pareto optimal set and front. At least for selected viduals over a nondominated region. They define this
MOPS, relativity is removed and a true quantitative compar- metric as:
ison is possible. This methodology allows absolute, rather 9+1
than relative observations. ‘= p$i)2 )
d i=l

4.2 MOEA Comparative Metrics where q is the number of desired optimal points and the
We propose quantitative comparisons between MOEA (q + l)-th subregion is the dominated region, ni is the
implementations via a rigorous, carefully designed series of actual number of individuals serving the ith subregion
experiments. However, we must first define the metrics upon (niche) of the nondominated region, ?ii is the expected
which we base MOEA performance. number of individuals servin the ith subregion of the
Deterministic enumeration provides A,, and PFt,, (at nondominated region, and Qiei is the variance of indi-
viduals serving the ith subregion of the nondominated
a given level of resolution). After executing an MOEA on
region. They show that if the distribution of points is
some MOP we are then able to compare the reported front
ideal with +ii number of points in the ith subregion, the
(pFk,own ) against the true front and determine error mea- performance measure L = 0. Thus, a low performance
sures. The following are possible metrics for this purpose.
measure characterizes an algorithm with a good distri-
Error Ratio. An MOEA reports a finite number of solu- bution capacity. However, this metric only measures
tions; these solutions are or are not members of PFI,, . spread uniformity.
If they are not the MOEA has erred. This metric is
mathematically represented by: 5 Conclusions

CL ei, In the tradition of providing test suites for evolutionary

n (3) algorithms, we propose possible MOEA test functions for
evaluation. The development of this list is based upon ac-
where n is the number of vectors in PFk,,,,, ; ei = 0 if cepted and historic EA test suite guidelines. Specific MOP
vector i is a member of PFt,.,,, , and 1 otherwise. For test suites can evolve from our list based upon an individ-
example, an error of “0” means that every vector re- ual researcher’s objectives, including problem characteristic
ported by the MOEA in PFk,,,, is actually in PFt,. ; classification. We have classified numeric MOPS based upon
an error of 100 means that none are. type, dimensionality, constraint structure, landscape, and
Pareto front structure (curve, surface, continuous, cormec-
Generational Distance. Used in earlier experiments (181, tiveness, symmetry, convexity). Also, we have shown that a
this metric may be effective in gauging MOEA perfor- Pareto front is at most a hyper-surface, not a hyper-volume.
mance. Generational distance is a value representing With a generic MOEA test suite, researchers can now com-
how “far’, PFk,,,,, is from PFi,.,,. and is defined as: pare their numeric and NP-Complete problem results (re-
garding effectiveness and efficiency) with others, over a spec-
@xn-rx, trum of MOEAs. Using the proposed Pareto terminology
n (4)
and test suite functions, as well as high performance com-
where n is the number of vectors in PFh,, and di is putational experiments such as ours, MOEA comparison ef-
the distance (in objective space) between each of these forts can be made more precise.
and the newest member of PFt,. . Our future efforts include extending the MOEA test suite
and experimental methodology laid forth in this paper. We
Coverage. Zitzler and Thiele propose two MOEA compar- are constructing additional “MOEA challenging,, MOPS for
ative metrics [23]. First is that of coverage. Cover- the test suite, and investigating other high-performance com-
age occurs when one solution’s associated objective putational environments. Finally, the MOEA test suite and
experiments aid our development and analysis of parallel 1131Michalewicz, Zbigniew. “Genetic Algorithms, Numeri-
and distributed MOEAs. cal Optimization, and Constraints.” Proceedings of the
Sixth International Conference on Genetic Algorithms,
References edited by Larry J. Eshelman. 151-158. San Mateo CA:
Morgan Kaufmann Publishers, Inc., 1995.
PI Ben-Tal, Aharon. “Characterization of Pareto and Lex-
P41 Nievergelt, Jiirg, et al. “All the Needles in a
icographic Optimal Solutions.” Multiple Criteria De-
cision Making Theory and Application 177. Lecture Haystack: Can Exhaustive Search Overcome Combina-
Notes in Economics and Mathematical Systems, edited torial Chaos?.” Computer Science Today: Lecture Notes
in Computer Science 1000, edited by J. van Leeuwen.
by G. Fandel and T. Gal, l-11, Berlin: Springer-Verlag, 254-274. Berlin: Springer, 1995.
1980.
1151 Rudolph, Giinter. “On a Multi-Objective Evolutionary
PI De Jong, Kenneth A. An Analysis of the Behavior of a
Algorithm and Its Convergence to the Pareto Set.” Pro-
Class of Genetic Adaptive Systems. PhD dissertation,
ceedings of the 1998 IEEE Conference on Evolutionary
The University of Michigan, Ann Arbor MI, 1975.
Computation. 1998.
PI Duda, Richard 0. and Peter E. Hart. Pattern Classifi-
I161 Schaffer, J. David. “Multiple Objective Optimization
New York, NY: John Wiley
cation and Scene Analysis.
with Vector Evaluated Genetic Algorithms.” In Grefen-
& Sons, 1973. stette [9], 93-100.
PI Fonseca, Carlos M. and Peter J. Fleming. “Multiobjec-
P71 Srinivas, N. and Kalyanmoy Deb. “Multiobjective
tive Genetic Algorithms Made Easy: Selection, Shar- Optimization Using Nondominated Sorting in Genetic
ing, and Mating Restriction.” Proceedings of the lat In- Algorithms,” Evolutionary Computation, 6(3):221-248
ternational Conference on Genetic Algorithms in Engi-
(1994).
neering Systems: Innovations and Applications. Num-
ber 414. 45-52. September: IEE, 1995. P81 Van Veldhuizen, David A. and Gary B. Lament. “Evo-
lutionary Computation and Convergence to a Pareto
PI Fonseca, Carlos M. and Peter J. Fleming. “Multiob- Front.” Late Breaking Papers at the Genetic Pnqmm-
jective Optimization and Multiple Constraint Handling ming 1998 Conference, edited by John R. Koza. 221-
with Evolutionary Algorithms - Part I: A Unified For- 228. Stanford, CA: Stanford University Bookstore, July
mulation, and Part II: Application Example,” IEEE 1998.
ZYanaactions on Systems, Man and Cybernetics - Part
A: Systems and Humans, 28(1):26-47 (January 1998). WI Van Veldhuizen, David A. and Gary B. Lament. Multi-
objective Evolutionary Algorithm Rerearch: A History
Fourman, Michael P. ‘Compaction of Symbolic Layout and Analysiu. Technical Report TR-98-03, Air Force
Using Genetic Algorithms.” In Grefenstette [9], 14I- Institute of Technology, 1998.
153.
PO1 Viennet, R., et al. “Multicriteria Optimization Using
VI Goldberg, David E. Genetic Algorithms in Search, Op- a Genetic Algorithm for Determining a Pareto Set,”
timization, and Machine Learning. Reading, MA: Ad- International Joumal of Systems Science, 37(2):255-
dison Wesley, 1989. 260 (1996).
PI Goldberg, David E., et al. “Messy Genetic Algorithms: WI Whitley, Darrell, et al. “Evaluating Evolutionary Al-
Motivation, Analysis, and First Results,” Complex Sya- gorithms,” ArtifZcial Intelligence, 85:245-276 (1996).
terns, 3:493-530 (1989).
WI Wolpert, David H. and Wiiam G. Macready. “No Free
PI Grefenstette, John J., editor. Pnxeedings of the First Lunch Theorems for Optimization,” IEEE !&wwc-
International Conference on Genetic Algorithms and tiona on Evolutionary Computation, 1(1):67-82 (April
Their Applications, Hillsdale, New Jersey: Lawrence 1997).
Erlbaum Associates, Publishers, July 1985.
1231 Zitzler, E&art and Lothar Thiele. “Multiobjective
Op
PO1Horn, Jeffrey. Handbook of Evolutionary Computation, timization Using Evolutionary Algorithms - A Compar-
1, chapter Multicriterion Decision Making, F1.9:1 - ative Case Study.” Pan&l Problem Solving j+vm Na-
F1.9:15. IOP Publishing Ltd. and Oxford University ture - PPSN V, edited by A. E. Eiben, et al. Berlin:
Press, 1997. Springer, 1998.
WI Horn, Jeffrey and Nicholas Nafpliotis. Multiobjective
Optimization Using the Niched Panto Genetic Algo-
rithm. Technical Report 930005, University of Illinois
at Urbana-Champaign, 117 Transportation Building,
104 South Matthews Avenue, Urbana, IL 61801-2996:
Illinois Genetic Algorithms Laboratory (IlliGAL), July
1993.

PI Hwang, Ching-Lai and Abu Syed Md. Masud. Multiple

Objective Decision Making - Methods and Applications.
springer Verlag, 1979.

357