See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/225153273

Survey of Multi-Objective Optimization Methods for Engineering

Article in Structural and Multidisciplinary Optimization · April 2004

DOI: 10.1007/s00158-003-0368-6

CITATIONS READS

4,549 18,420

2 authors:

R. Timothy Marler Jasbir Singh Arora

RAND Corporation University of Iowa
109 PUBLICATIONS 7,821 CITATIONS 325 PUBLICATIONS 18,955 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Jasbir Singh Arora on 11 November 2014.

The user has requested enhancement of the downloaded file.

 Struct Multidisc Optim 26, 369–395 (2004)
Review article DOI 10.1007/s00158-003-0368-6

Survey of multi-objective optimization methods for engineering

R.T. Marler and J.S. Arora

Abstract A survey of current continuous nonlinear multi- Finorm Normalized objective functions
objective optimization (MOO) concepts and methods is Fs Primary objective function
presented. It consolidates and relates seemingly differ- Fitrans Transformed objective functions
ent terminology and methods. The methods are divided F◦ Utopia point
into three major categories: methods with a priori ar- F Vector of objective functions (point in the criterion
ticulation of preferences, methods with a posteriori ar- space)
ticulation of preferences, and methods with no articula- gj Inequality constraints
tion of preferences. Genetic algorithms are surveyed as hl Equality constraints
well. Commentary is provided on three fronts, concern- k Number of objective functions
ing the advantages and pitfalls of individual methods, λ Min-max parameter
the different classes of methods, and the field of MOO m Number of inequality constraints
as a whole. The Characteristics of the most significant n Number of design variables
methods are summarized. Conclusions are drawn that re- p Exponent for a global criterion
flect often-neglected ideas and applicability to engineer- U Utility function
ing problems. It is found that no single approach is supe- w Vector of weighting coefficients/exponents
rior. Rather, the selection of a specific method depends on x Vector of design variables (point in the design space)
the type of information that is provided in the problem, X Feasible design space
the user’s preferences, the solution requirements, and the z Aspiration point
availability of software. Z Feasible criterion space

Key words optimization, multi-objective, multi-criteria,

engineering 1
Introduction

1.1
Background and objectives
List of key symbols
The process of optimizing systematically and simultan-
e Number of equality constraints eously a collection of objective functions is called multi-
Fg Global criterion function objective optimization (MOO) or vector optimization.
Fimax Maximum objective function values This paper is a survey of methods for MOO and is a con-
densation of the work by Marler and Arora (2003), which
Received: 25 September 2002 provided a comprehensive review of methods (and their
Revised manuscript received: 7 April 2003 variants) with an eye towards engineering applications.
Published online: 23 March 2004 In contrast, this survey excludes many of the technical
 Springer-Verlag 2004 details and, instead, provides a road map of currently
R.T. Marler and J.S. Arorau available continuous nonlinear methods and literature.
Optimal Design Laboratory, College of Engineering, The Uni- General concepts are briefly described, and references are
versity of Iowa, Iowa City, Iowa 52242, USA included for further investigation. In addition, this paper
e-mail: tmarler@engineering.uiowa.edu, consolidates seemingly different concepts, methods, and
jsarora@engineering.uiowa.edu terminology stemming from diverse applications.
370

1.2 on mathematics (Yu 1985; Dauer and Stadler 1986). Sur-

Definition of a multi-objective optimization problem veys that do explicitly present a variety of algorithms
tend to incorporate minimal discussion of their advan-
The general multi-objective optimization problem is tages and disadvantages, and most surveys only target
posed as follows: a limited number of approaches (Boychuk and Ovchin-
nikov 1973; Gerasimov and Repko 1978; Roy and Vincke
T
Minimize F (x) = [F1 (x) , F2 (x) , . . . , Fk (x)] 1981; Koski 1984; Osyczka 1985; Stadler 1988; Stadler
x (1) and Dauer 1992). Much of the early pioneering work with
subject to gj (x) ≤ 0 , j = 1, 2, . . . , m , multi-objective optimization focuses specifically on struc-
tural design (Baier 1977; Leitmann 1977; Stadler 1977,
hl (x) = 0 , l = 1, 2, . . . , e , 1978; Koski 1979, 1980; Carmichael 1980). There is a need
for a survey that is comprehensive in its consideration
where k is the number of objective functions, m is the of currently available methods, consolidating conceptual
number of inequality constraints, and e is the number of and practical developments. Textbooks can be complete
equality constraints. x ∈ E n is a vector of design variables in the treatment of a specific topic (Hwang and Md. Ma-
(also called decision variables), where n is the number sud 1979; Salukvadze 1979; Goicoechea et al. 1982; Ze-
of independent variables xi . F (x) ∈ E k is a vector of ob- leny 1982; Chankong and Haimes 1983; Osyczka 1984;
jective functions Fi (x) : E n → E 1 . Fi (x) are also called Steuer 1989; Eschenauer et al. 1990; Miettinen 1999). Al-
objectives, criteria, payoff functions, cost functions, or ternatively, a survey paper can provide a relatively quick
value functions. The gradient of Fi (x) with respect to overview of the literature.
x is written as ∇x Fi (x) ∈ E n . xi ∗ is the point that
minimizes the objective function Fi (x). Any comparison 1.4
(≤, ≥, etc.) between vectors applies to corresponding vec- Scope of the survey
tor components.
The feasible design space X (often called the feas- This survey addresses continuous nonlinear multi-objec-
ible decision space or constraint set) is defined as the tive optimization methods. Section 2 lays the foundation
set {x|gj (x) ≤ 0, j = 1, 2, ..., m; and hi (x) = 0, i = 1, 2, of fundamental concepts. Then, because a primary goal
..., e}. The feasible criterion space Z (also called the feas- of multi-objective optimization is to model a decision-
ible cost space or the attainable set ) is defined as the maker’s preferences (ordering or relative importance of
set {F(x)|x ∈ X}. Although the terms feasible criterion objectives and goals), methods are categorized depending
space and attainable set are both used in the literature on how the decision-maker articulates these preferences.
to describe Z, there is a subtle distinction between the Section 3 contains methods that involve a priori articula-
ideas of feasibility and attainability. Feasibility implies tion of preferences, which implies that the user indicates
that no constraint is violated. Attainability implies that the relative importance of the objective functions or de-
a point in the criterion space maps to a point in the de- sired goals before running the optimization algorithm.
sign space. Each point in the design space maps to a point Section 4 describes methods with a posteriori articulation
in the criterion space, but the reverse may not be true; of preferences, which entail selecting a single solution from
every point in the criterion space does not necessarily cor- a set of mathematically equivalent solutions. In Sect. 5,
respond to a single point x ∈ X. Consequently, even with methods that require no articulation of preferences are ad-
an unconstrained problem, only certain points in the cri- dressed. Algorithms that involve a progressive articulation
terion space are attainable. In this study, Z is used to of preferences, in which the decision-maker is continu-
indicate points in the criterion space that are feasible and ally providing input during the running of the algorithm,
attainable. are not discussed. Section 6 addresses genetic global al-
gorithms. Advantages and disadvantages of the different
methods are discussed throughout the paper. In addition,
1.3 each section is followed by a broader discussion of the
Motivation and overview of the literature methods. Section 7 provides a summary and conclusions
relevant to multi-objective optimization as a whole.
Although surveys of multi-objective optimization methods
are common, they are often incomplete in terms of com-
prehensive coverage, algorithm presentation, and gen- 2
eral applicability to engineering design. For example, Basic concepts and definitions
many surveys only target specific applications (Jendo
et al. 1985; Psarras et al. 1990; Tseng and Lu 1990), while 2.1
others only address the critical literature in the field. As Definition of terms
opposed to presenting computational methods, some sur-
veys focus on historical aspects (Stadler 1987). At the Multi-objective optimization originally grew out of three
opposite end of the spectrum are discussions that focus areas: economic equilibrium and welfare theories, game
 371

theory, and pure mathematics. Consequently, many and vector optimization methods. Given a vector of ob-
terms and fundamental ideas stem from these fields. jective functions, it is possible simply to combine the
The reader is referred to Stadler and Dauer (1992), and components of this vector to form a single scalar ob-
Stadler (1987, 1988) for extensive discussions of these jective function, hence the term scalarization. Although
topics and for the history of multi-objective optimization. few authors make the distinction, the term vector opti-
For the sake of brevity, only critical terms are defined be- mization loosely implies independent treatment of each
low. Many of these terms have multiple definitions in the objective function. Both approaches are discussed in this
literature stemming from the differences between engin- study.
eering and economic jargon, and in such cases, the most
common and most appropriate definitions are used.
Preferences. Preferences refer to a decision-maker’s 2.2
opinions concerning points in the criterion space. With Pareto optimality
methods that involve a posteriori articulation of prefer-
ences, the decision-maker imposes preferences directly on In contrast to single-objective optimization, a solution
a set of potential solution points. Then, theoretically the to a multi-objective problem is more of a concept than
final solution reflects the decision-maker’s preferences ac- a definition. Typically, there is no single global solution,
curately. With a priori articulation of preferences, one and it is often necessary to determine a set of points that
must quantify opinions before actually viewing points in all fit a predetermined definition for an optimum. The
the criterion space. In this sense, the term preference of- predominant concept in defining an optimal point is that
ten is used in relation to the relative importance of differ- of Pareto optimality (Pareto 1906), which is defined as
ent objective functions. Nonetheless, this articulation of follows:
preferences is fundamentally based on opinions concern-
ing anticipated points in the criterion space. Definition 1. Pareto Optimal: A point, x∗ ∈ X, is
Preference Function. A preference function is an ab- Pareto optimal iff there does not exist another point,
stract function (of points in the criterion space) in the x ∈ X, such that F (x) ≤ F (x∗ ), and Fi (x) < Fi (x∗ ) for
mind of the decision-maker, which perfectly incorporates at least one function.
his/her preferences.
All Pareto optimal points lie on the boundary of the
Utility Function. In the context of economics, utility,
feasible criterion space Z (Athan and Papalambros 1996;
which is modeled with a utility function, represents an
Chen et al. 2000). Often, algorithms provide solutions
individual’s or group’s degree of contentment (Mansfield
that may not be Pareto optimal but may satisfy other
1985). This is slightly different from the usual meaning of
criteria, making them significant for practical applica-
usefulness or worth. Instead, in this case, utility empha-
tions. For instance, weakly Pareto optimal is defined as
sizes a decision-maker’s satisfaction. In terms of multi-
follows:
objective optimization, an individual utility function is
defined for each objective and represents the relative im- Definition 2. Weakly Pareto Optimal: A point, x∗ ∈ X,
portance of the objective. The utility function U is an is weakly Pareto optimal iff there does not exist another
amalgamation of the individual utility functions and is point, x ∈ X, such that F (x) < F (x∗ ).
a mathematical expression that attempts to model the
decision-maker’s preferences. It is used to approximate A point is weakly Pareto optimal if there is no other point
the preference function, which typically cannot be ex- that improves all of the objective functions simultan-
pressed in mathematical form. eously. In contrast, a point is Pareto optimal if there is no
Global Criterion. A global criterion is a scalar function other point that improves at least one objective function
that mathematically combines multiple objective func- without detriment to another function. Pareto optimal
tions; it does not necessarily involve utility or preference. points are weakly Pareto optimal, but weakly Pareto op-
Game theory. Stadler (1988) writes that “the math- timal points are not Pareto optimal.
ematical and economic approaches [to multi-objective All Pareto optimal points may be categorized as being
problems] were eventually united with the inception of either proper or improper . The idea of proper Pareto opti-
game theory by Borel in 1921.” According to the tradi- mality and its relevance to certain algorithms is discussed
tional game theory interpretation, a game is any situation by Geoffrion (1968), Yu (1985), and Miettinen (1999). It
of conflict or cooperation between at least two players is defined as follows:
with multiple possible strategies or moves. Game the-
ory represents multi-objective optimization with multiple Definition 3. Properly Pareto Optimal: A point, x∗ ∈
X, is properly Pareto optimal (in the sense of Geoffrion)
decision-makers, each controlling certain design variables
(Vincent 1983). If all players cooperate, the result is the if it is Pareto optimal and there is some real number
M > 0 such that for each Fi (x) and each x ∈ X satisfy-
same as a single player acting as a decision-maker for
a multi-objective optimization problem. ing Fi (x) < Fi (x∗ ), there exists at least one Fj (x) such
F (x∗ )−Fi (x)
One of the predominant classifications of multi- that Fj (x∗ ) < Fj (x) and Fij (x)−Fj (x ∗ ) ≤ M . If a Pareto
objective approaches is that of scalarization methods optimal point is not proper, it is improper.
372

The quotient is referred to as a trade-off , and it repre- Theorem 1. Let F ∈ Z, x∗ ∈ X, and F∗ = F (x∗ ). Let
sents the increment in objective function j resulting from a scalar global criterion Fg (F) : Z → R1 be differen-
a decrement in objective function i. Definition 2.3 re- tiable with ∇F Fg (F) > 0 ∀ F ∈ Z. Assume Fg (F∗ ) =
quires that the trade-off between each function and at min {Fg (F) < F ∈ Z}. Then, x∗ is Pareto optimal.
least one other function be bounded in order for a point to
be properly Pareto optimal. Theorem 1 suggests that minimization of a global func-
Methods for determining whether a point is Pareto op- tion Fg (F) is sufficient for Pareto optimality if Fg (F)
timal or not are given in Benson (1978), and Brosowski increases monotonically with respect to each objective
and da Silva (1994). Miettinen (1999) summarizes the function. Furthermore, if x∗ is a Pareto optimal point,
work of Benson (1978) with the following common simple then there exists a function Fg (F) that satisfies Theo-
test for the point x∗ : rem 1 and captures x∗ (Messac et al. 2000a). If minimiz-
ing Fg (F) is to provide a necessary condition for Pareto


k optimality, the Hessian of Fg (F) with respect to F must
Minimize δi be negative definite (Athan and Papalambros 1996).
δ ≥0
x∈X,δ (2)
i=1

subject to Fi (x) + δi = Fi (x∗ ) , i = 1, 2, . . . , k. 2.4

Efficiency and dominance
If all δi are zero, then x∗ is a Pareto optimal point.
For any given problem, there may be an infinite num- Efficiency, which is the same idea as admissibility or non-
ber of Pareto optimal points constituting the Pareto inferiority (Steuer 1989), is another primary concept in
optimal set. Therefore, one must distinguish between multi-objective optimization and is defined as follows:
methods that provide the Pareto optimal set or some por-
Definition 4. Efficient and Inefficient: A point, x∗
tion of that set, and methods that actually seek a single
∈ X, is efficient iff there does not exist another point,
final point. Both approaches are considered in this survey.
x ∈ X, such that F (x) ≤ F (x∗ ) with at least one Fi (x) <
Fi (x∗ ). Otherwise, x* is inefficient.
2.3 Definition 5. Efficient Frontier: The set of all efficient
Necessary and sufficient conditions points is called the efficient frontier.

Whether or not solving a particular multi-objective opti- Steuer also provides the following definition for non-
mization formulation serves as a necessary and/or a suf- dominated and dominated points:
ficient condition for Pareto optimality is central to its Definition 6. Non-Dominated and Dominated Points:
performance. However, these characterizations may veer A vector of objective functions, F (x∗ ) ∈ Z, is non-
slightly from their meaning in terms of single-objective dominated iff there does not exist another vector, F (x) ∈
optimization. If a formulation provides a necessary con- Z, such that F (x) ≤ F (x∗ ) with at least one Fi (x) <
dition, then for a point to be Pareto optimal, it must Fi (x∗ ). Otherwise, F (x∗ ) is dominated.
be a solution to that formulation. Consequently, every
Pareto optimal point is attainable with adjustments in For all practical purposes, Definitions 4 and 6 are the
method parameters (exponents, weights, etc.), which same. However, efficiency typically refers to a vector of
are discussed in Sect. 3. If a point is attainable using design variables in the design space, whereas dominance
a particular formulation, the formulation is said to cap- refers to a vector of functions in the criterion space.
ture that point. However, some solutions obtained using The definition of Pareto optimality is similar to that
this formulation may not be Pareto optimal. On the of efficiency, and a Pareto optimal point in the criterion
other hand, if a formulation provides a sufficient con- space is often considered the same as a non-dominated
dition, then its solution is always Pareto optimal, al- point. However, efficiency and dominance were originally
though certain Pareto optimal points may be unattain- given more general, less common definitions in terms of
able. Many authors discuss theoretical necessary and domination structures and convex cones (Yu 1974; Yu
sufficient conditions as a means of qualifying Pareto op- and Leitmann 1974). Pareto optimality is a subtly distin-
timality, and surveys on such conditions are available guishable special case of efficiency, but this distinction is
(Vincent and Grantham 1981; Miettinen 1999). How- irrelevant in terms of practical applications.
ever, in this paper, the terms necessary and sufficient are
used in a more practical sense to describe the ability of
a method/formulation to provide Pareto optimal points. 2.5
In terms of a global criterion Fg , Stadler (1988) Compromise solution
presents the following sufficiency condition for a Pareto
optimal point, which is useful for evaluating the effective- An alternative to the idea of Pareto optimality and ef-
ness of a scalarization method: ficiency, which yields a single solution point, is the idea
 373

of a compromise solution (Salukvadze 1971a,b). It entails also be determined using the absolute maximum (if it ex-
minimizing the difference between the potential optimal ists) of Fi (x) or its approximation based on engineering
point and a utopia point (also called an ideal point), which intuition.
is defined as follows (Vincent and Grantham 1981): An alternative to (4) is given as follows (Osyczka 1978;
Salukvadze 1979; Hwang and Md. Masud 1979):
Definition 7. Utopia Point: A point, F◦ ∈ Zk , is a uto-
pia point iff for each i = 1, 2 . . . , k, Fi◦ = minimum Fi (x) − Fi◦
x Fitrans (x) = . (5)
{Fi (x) |x ∈ X}. Fi◦
In general, F◦ is unattainable. The next best thing is a so- This approach also provides a non-dimensional objec-
lution that is as close as possible to the utopia point. Such tive function. However, in this case, the lower value of
a solution is called a compromise solution and is Pareto Fitrans (x) is restricted to zero, while the upper value is
optimal. A difficulty with the idea of a compromise so- unbounded. (5) is often referred to as the relative devi-
lution is the definition of the word close. The term close ation or fractional deviation. Computational difficulties
usually implies that one minimizes the Euclidean distance can arise not only if the denominator is zero but also if it is
N (x), which is defined as follows: negative. Consequently, one assumes that the denomina-
tor is positive (Koski and Silvennoinen 1987; Eschenauer
 k  12

et al. 1990), or uses its absolute value (Osyczka 1981).
◦
N (x) = |F (x) − F | = [Fi (x) − Fi◦ ]2 . (3) The following is a variation on (5) (Koski and Silven-
1 noinen 1987; Chen et al. 1999):
However, it is not necessary to restrict closeness to the Fi (x)
case of a Euclidean norm (Vincent 1983). In addition, if Fitrans (x) = , Fi◦ > 0 . (6)
Fi◦
different objective functions have different units, the Eu-
clidean norm or a norm of any degree becomes insufficient This approach yields non-dimensional objective function
to represent closeness mathematically. Consequently, the values with a lower limit of one.
objective functions should be transformed such that they The most robust approach to transforming objective
are dimensionless. functions, regardless of their original range, is given as fol-
lows (Koski 1984; Koski and Silvennoinen 1987; Rao and
Freiheit 1991):
2.6
Function transformations Fi (x) − Fi◦
Fitrans = . (7)
Fimax − Fi◦
For the sake of consistent comparison between methods,
it is assumed that the objective functions shown in (1) This approach is consistently referred to as normaliza-
are not modified. However, in many cases it is advanta- tion. In this case, Fitrans (x) generally has values between
geous to transform the original objective functions. This zero and one, depending on the accuracy and method
is especially true with scalarization methods that involve with which Fimax (x) and Fi◦ (x) are determined.
a priori articulation of preferences. Therefore, we present It may be prohibitively expensive to compute the
some common function transformation methods. utopia point used in the foregoing approaches; therefore,
The first approach is given as follows (Proos et al. one may use its approximation.
2001):

Fi (x) 3
Fitrans = , (4)
|Fimax | Methods with a priori articulation of preferences

which results in a non-dimensional objective function The methods in this section allow the user to specify pref-
with an upper limit of one (or negative one) and an un- erences, which may be articulated in terms of goals or the
bounded lower limit (note that Fimax = 0 is assumed). relative importance of different objectives. Most of these
There are two approaches for determiningFimax
 . One can methods incorporate parameters, which are coefficients,
define Fimax such that Fimax = max Fi x∗j , where x∗j exponents, constraint limits, etc. that can either be set
1≤j≤k
is the point that minimizes the jth objective function. to reflect decision-maker preferences, or be continuously
x∗j is a vertex
 of the Pareto optimal set in the design altered in an effort to represent the complete Pareto op-
space, and F x∗j is a vertex of the Pareto optimal set in timal set. The latter approach is discussed in Sect. 4.
the criterion space. This approach of determining Fimax Consideration of more than one objective function in
has been used in the development of membership func- an optimization problem introduces additional degrees
tions for fuzzy multi-objective optimization (Marler and of freedom. Unless these degrees of freedom are con-
Arora 2003) and for Rao’s method, which is discussed strained, mathematical theory indicates a set of solution
in Sect. 5.3. Alternatively, the denominator in (4) may points rather than a single optimal point. Preferences
374

dictated by the decision-maker provide constraints. The point (Wierzbicki 1986; Miettinen 1999), reference point
most common approach to imposing such constraints is to (Wierzbicki 1982), or target point (Hallefjord and Jorn-
develop a utility function as defined earlier. Thus, most sten 1986). When this is done, U is called an achievement
of the formulations in this section are based on different function. Assuming w is fixed, if z ∈ / Z, then minimizing
utility functions. (10) or (11) is necessary (with modifications in z) and
sufficient for Pareto optimality (Wierzbicki 1986). That
is, every Pareto optimal point may be captured by using
3.1 a different aspiration point z, as long as the aspiration
Weighted global criterion method point is not in the feasible criterion space Z. However,
this is not a practical approach for depicting the complete
One of the most common general scalarization methods Pareto optimal set. Often, it is not possible to determine
for multi-objective optimization is the global criterion whether z is in the feasible criterion space (z ∈ Z) before
method in which all objective functions are combined to solving the problem.
form a single function. The term global criterion techni- The solution to these approaches depends on the value
cally can refer to any scalarized function, but it often is of p. Generally, p is proportional to the amount of em-
reserved for the formulations presented in this subsection. phasis placed on minimizing the function with the largest
Although a global criterion may be a mathematical func- difference between Fi (x) and Fi◦ (Koski and Silvennoinen
tion with no correlation to preferences, a weighted global 1987). Hwang and Md. Masud (1979) exclude the root
criterion is a type of utility function in which method pa- 1/p, but formulations with and without the root theor-
rameters are used to model preferences. One of the most etically provide the same solution. Global criteria yield
general utility functions is expressed in its simplest form portions of the Pareto optimal set with continuous vari-
as the weighted exponential sum: ation in p (Yu 1973). However, varying only p (with all
other method parameters constant) usually yields only


k
U= wi [Fi (x)]p , Fi (x) > 0 ∀i , (8) a limited number of Pareto optimal solution points in
i=1 a relatively small neighborhood. The current literature

k does not address the repercussions of applying the expo-
U= [wi Fi (x)]p , Fi (x) > 0 ∀i . (9) nent p to the weights wi as shown in (9) and (11); these
i=1 formulations are not compared with the formulations in
(8) and (10). In fact, p and w typically are not varied or
The most common extensions of (8) and (9) are (Yu
determined in unison. Rather, one usually selects a fixed
and Leitmann 1974; Zeleny 1982; Chankong and Haimes
value for p. Then, the user either sets w to reflect prefer-
1983)
ences a priori or systematically alters w to yield a set of
 k  p1 Pareto points. With (9) and (11), using higher values for

p increases the effectiveness of the method in providing
wi [Fi (x) − Fi◦ ]
p
U= , (10)
the complete Pareto optimal set (Athan and Papalam-
i=1
 k  p1 bros 1996). This is the case with (8) and (10) as well

(Messac et al. 2000a,b).
(x) − Fi◦ ]
p
U= wip [Fi . (11)
Here, we briefly discuss under what conditions solu-
i=1
tions are Pareto optimal. (10) is sufficient for Pareto opti-
Here, w is a vectorof weights typically set by the decision- mality as long as w > 0 (Chankong and Haimes 1983; Mi-
k
maker such that i=1 wi = 1 and w > 0. As with most ettinen 1999). (11) is also sufficient for Pareto optimality
methods that involve objective function weights, set- (Zeleny 1982). Athan and Papalambros (1996) prove that
ting one or more of the weights to zero can result in (9), which is similar to (11), provides a necessary condi-
weak Pareto optimality where Pareto optimality may be tion for Pareto optimality assuming F (x) ≥ 0. Techni-
achievable. Generally, the relative value of the weights cally, this means that for each Pareto optimal point xp ,
reflects the relative importance of the objectives. there exists a vector w and a scalar p such that xp is a so-
One can view the summation arguments in (10) and lution to (9). However, a relatively large value of p may be
(11) in two ways: as transformations of the original ob- required in order to capture certain Pareto optimal points
jective functions, or as components of a distance func- especially with non-convex Pareto optimal sets, and as
tion that minimizes the distance between the solution p approaches infinity, minimizing (9) is no longer suffi-
point and the utopia point in the criterion space. Conse- cient for Pareto optimality; it is sufficient only for weak
quently, global criterion methods are often called utopia Pareto optimality. Therefore, for a fixed value of p, (9)
point methods or compromise programming methods, as cannot be both necessary and sufficient for Pareto opti-
the decision-maker usually has to compromise between mality. In this vein, the value of p determines the extent
the final solution and the utopia point. For computa- to which a method is able to capture all of the Pareto opti-
tional efficiency or in cases where a function’s indepen- mal points, even when the feasible criterion space may be
dent minimum may be unattainable, one may approxi- non-convex. Generally, although using a higher value for
mate the utopia point by z, which is called an aspiration p enables one to better capture all Pareto optimal points
 375

(with variation in w), doing so may also yield non-Pareto the eigenvalues of the matrix are the weights. Rao and
optimal points. Roy (1989) provide a method for determining weights
based on fuzzy set theory. For cases in which the rela-
tive importance of the objective functions is unclear,
3.2 Wierzbicki (1986) provides an algorithm that calculates
Weighted sum method weights based on the aspiration point and the utopia
point.
The most common approach to multi-objective optimiza- Many authors touch on difficulties with the weighted
tion is the weighted sum method: sum method (Koski 1985; Stadler 1995; Athan and Pa-
palambros 1996; Das and Dennis 1997; Messac et al.


k
2000a,b). First, despite the many methods for determin-
U= wi Fi (x) . (12)
ing weights, a satisfactory, a priori selection of weights
i=1
does not necessarily guarantee that the final solution will
This is a form of (8) or (9) with p = 1. If all of the weights be acceptable; one may have to resolve the problem with
are positive, the minimum of (12) is Pareto optimal new weights. In fact, weights must be functions of the ori-
(Zadeh 1963); i.e., minimizing (12) is sufficient for Pareto ginal objectives, not constants, in order for a weighted
optimality. However, the formulation does not provide sum to mimic a preference function accurately (Messac
a necessary condition for Pareto optimality (Zionts 1988). 1996).
Koski and Silvennoinen (1987) present a partial weight- The second problem with the weighted sum approach
ing method in which the original objective functions are is that it is impossible to obtain points on non-convex
grouped into sets with common characteristics. Each set portions of the Pareto optimal set in the criterion space.
is then used to form an independent weighted sum func- Das and Dennis (1997) and Messac et al. (2000a,b) give
tion with a unique set of weights, and in this way, the theoretical reasons for this deficiency. Although non-
number of original objective functions is reduced. convex Pareto optimal sets are relatively uncommon (Das
Steuer (1989) mathematically relates the weights to and Dennis 1998), some examples are noted in the litera-
the decision-maker’s preference function. Das and Dennis ture (Koski 1985; Stadler and Dauer 1992; Stadler 1995).
(1997) provide a graphical interpretation of the weighted The final difficulty with the weighted sum method is
sum method for two-objective problems to explain some that varying the weights consistently and continuously
of its deficiencies. Eschenauer et al. (1990) give a brief may not necessarily result in an even distribution of
depiction of the method in criterion space. Koski and Pareto optimal points and an accurate, complete rep-
Silvennoinen (1987) discuss and illustrate the weighted resentation of the Pareto optimal set. Das and Dennis
sum method as a special case of methods that involve (1997) discuss this deficiency in detail and illustrate the
a p-norm. necessary conditions for a series of weighted sum itera-
Misinterpretation of the theoretical and practical tions to yield an even spread of points on the Pareto curve
meaning of the weights can make the process of in- (in the criterion space).
tuitively selecting non-arbitrary weights an inefficient
chore. Consequently, many authors have developed sys-
3.3
tematic approaches to selecting weights, surveys of which
Lexicographic method
are provided by Eckenrode (1965), Hobbs (1980), Hwang
and Yoon (1981), and Voogd (1983). Here, we briefly
describe the basic general approaches. With ranking With the lexicographic method, the objective functions
methods (Yoon and Hwang 1995), the different objective are arranged in order of importance. Then, the following
functions are ordered by importance. The least import- optimization problems are solved one at a time:
ant objective receives a weight of one, and integer weights Minimize Fi (x) (13)
with consistent increments are assigned to objectives that x∈X
are more important. The same approach is used with  
subject to Fj (x) ≤ Fj x∗j , j = 1, 2, . . . , i − 1 , i > 1 ,
categorization methods, in which different objectives are
grouped in broad categories such as highly important, and i = 1, 2, . . . , k .
moderately important. With rating methods, decision-
makers assign independent values of relative importance Here, i represents a function’s position in the preferred
to each objective function. Such an approach attaches sequence, and Fj x∗j represents the optimum of the jth
a more than ordinal significance to each weight. Ratio objective function, found in the jth iteration. After the
questioning or paired comparison methods provide sys- first iteration (j = 1), Fj x∗j is not necessarily the same
tematic means to rate objective functions by comparing as the independent minimum of Fj (x), because new con-
two objectives at a time. In this vein, Saaty (1977) pro- straints have been introduced. The constraints in (13) can
vides an eigenvalue method of determining weights, which be replaced with equalities (Stadler 1988).
involves k (k − 1)/2 pair-wise comparisons between ob- Some authors distinguish the hierarchical method
jective functions. This yields a comparison matrix , and from the lexicographic approach, as having the following
376

constraints (Osyczka 1984): it is sufficient for weak Pareto optimality (Koski and Sil-
  vennoinen 1987). If the solution is unique, it is Pareto
δj   optimal.
Fj (x) ≤ 1 + Fj x∗j , j = 1, 2, . . . , i , i>1.
100 It is possible to modify the weighted min-max method
(14) in order to alleviate the potential for solutions that
are only weakly Pareto optimal, using the augmented
Compared with (13), (14) represents a constraint relax- weighted Tchebycheff method (Steuer and Choo 1983;
ation, induced by increasing the right
 hand side of the Kaliszewski 1985; Romero et al. 1998) or the modi-
constraint by a percentage of Fj x∗j . δj ranges between fied weighted Tchebycheff method (Kaliszewski 1987), as
0 and 100. One may vary δj to tighten the constraints and shown in (17) and (18) respectively:
in this way generate different Pareto optimal points.
Waltz (1967) proposes another variation of the lexi-

k
U = max {wi [Fi (x) − Fi◦ ]} + ρ Fj (x) − Fj◦ , (17)
cographic approach with which
 the constraints are for- i
mulated as Fj (x) ≤ Fj x∗j + δj . In this case, δj are
j=1
  
positive tolerances determined by the decision-maker, 

k
  
and as they increase, the feasible region dictated by the U = max wi Fi (x) − Fi◦ + ρ Fj (x) − Fj◦  .
i  
objective functions expands. This reduces the sensitiv- j=1

ity of the final solution to the initial objective-function (18)

ranking process. δj need not be less than 100. (14) and
Waltz’s approach combine characteristics of the lexico- ρ is a sufficiently small positive scalar assigned by the
graphic method and the ε-constraint approach discussed decision-maker. Miettinen (1999) discusses and illus-
in Sect. 3.8. Consequently, the nature of the solutions to trates the features of these methods thoroughly.
these formulations is not straightforward and is not dis- Minimizing (17) or (18) is necessary and sufficient for
cussed in the literature. Pareto optimality with discrete problems and with prob-
Rentmeesters et al. (1996) demonstrate that solutions lems involving only linear constraints (polyhedral prob-
with the lexicographic method do not satisfy the typical lems) (Steuer and Choo 1983; Kaliszewski 1987). For gen-
constraint qualification of regularity associated with the eral problems, the two formulations are necessary and
Kuhn–Tucker optimality conditions (Kuhn and Tucker sufficient for proper Pareto optimality (Choo and Atkins
1950). The authors present alternate optimality condi- 1983; Kaliszewski 1985). Steuer (1989) suggests that (17)
tions and solve them with Newton-like methods. is necessary and sufficient for Pareto optimality as long as
ρ is not too large, where “ . . . values between 0.0001 and
0.01 should normally suffice.”
The following modification to (17) also provides a ne-
3.4
cessary and sufficient condition for proper Pareto opti-
Weighted min-max method
mality (Wierzbicki 1986):
The weighted min-max formulation, or weighted Tcheby-

k
cheff method, is given as follows: U = max {wi [Fi (x) − Fi◦ ]} + ρ wj Fj (x) − Fj◦ .
i
j=1
U = max {wi [Fi (x) − Fi◦ ]} . (15) (19)
i

Sufficiency for proper Pareto optimality implies suffi-

A common approach for treating (15) is to introduce an
ciency for Pareto optimality. Therefore, (17) through (19)
additional unknown parameter λ:
always yield Pareto optimal points, but they may skip
improper Pareto optimal points. However, these formula-
Minimize λ (16)
x∈X,λ tions all eliminate the possibility of weakly Pareto opti-
mal results (Miettinen 1999).
subject to wi [Fi (x) − Fi◦ ] − λ ≤ 0 , i = 1, 2, . . . , k . The lexicographic weighted Tchebycheff method pro-
vides another modification that always yields Pareto opti-
However, increasing the number of constraints can in- mal points (Tind and Wiecek 1999). This approach stems
crease the complexity of the problem. from (17) and optimality in the min-max sense (Osyczka
As discussed in Sect. 3.1, increasing the value of p 1978). First, one solves (15) using the formulation in (16).
can increase the effectiveness of the weighted global crite- This results in an optimal point and an optimal λ-value.
rion method in providing the complete Pareto optimal set Then,
k with λ fixed at its optimum value, one minimizes
◦
(Messac et al. 2000a,b). The weighted min-max method i=1 [Fi (x) − Fi ], still subject to the constraints in (16).
shown in (15) is the limit of (11) as p → ∞. Therefore, In this way, the algorithm eliminates the possibility of
(15) can provide the complete Pareto optimal set with non-unique solutions, and the use of ρ becomes unneces-
variation in the weights; it provides a necessary condi- sary. This approach is necessary and sufficient for Pareto
tion for Pareto optimality (Miettinen 1999). In addition, optimality (Steuer and Choo 1983).
 377

− − −
and d+j dj = 0. Consequently, |dj | = dj + dj . di and di
+ +
3.5
Exponential weighted criterion represent underachievement and overachievement, re-
spectively, where achievement implies that a goal has
In response to the inability of the weighted sum method been reached. The optimization problem is formulated as
to capture points on non-convex portions of the Pareto follows:
optimal surface, Athan and Papalambros (1996) propose


k
 + 
the exponential weighted criterion, as follows: Minimize di + d−
i (22)
x∈X,d− ,d+
i=1


k
U= (epwi − 1) epFi (x) , (20) −
j −dj = bj ,
subject to Fj (x) + d+ j = 1, 2, . . . , k ,
i=1
−
where the argument of the summation represents an in- j , dj ≥ 0 ,
d+ j = 1, 2, . . . , k ,
dividual utility function for Fi (x). Although large values
−
of p can lead to numerical overflow, minimizing (20) d+
j dj = 0 , j = 1, 2, . . . , k .
provides a necessary and sufficient condition for Pareto
optimality. The qualifications concerning the authors’ In the absence of any other information, bj = Fj◦ , in which
proof for necessity and sufficiency, which are discussed in case (22) is theoretically similar to compromise program-
Sect. 3.1, apply here as well. ming and can be considered a type of global criterion
method (Romero et al. 1998). This is especially appar-
ent when an aspiration point is used with absolute values
3.6 signs in (9), (10), or (11). Lee and Olson (1999) provide
Weighted product method an extensive review of applications for goal programming.
However, despite its popularity and wide range of appli-
To allow functions with different orders of magnitude to cations, there is no guarantee that it provides a Pareto
have similar significance and to avoid having to trans- optimal solution. In addition, (22) has additional vari-
form objective functions, one may consider the following ables and nonlinear equality constraints, both of which
formulation: can be troublesome with larger problems.

k Archimedean goal programming (or weighted goal pro-
wi gramming) constitutes a subclass of goal programming,
U= [Fi (x)] , (21)
i=1 in which weights are assigned to the deviation of each
objective from its perspective goal (Charnes and Cooper
where wi are weights indicating the relative significance
1977). The preemptive (or lexicographic) goal program-
of the objective functions. Bridgman (1922) is the first ming approach is similar to the lexicographic method
to refer to this approach and calls it a product of pow- in that the deviations |dj | = d+ −
j + dj for the objectives
ers. Gerasimov and Repko (1978) successfully apply the
are ordered in terms of priority and minimized lexico-
method, which they refer to as the valid compromise, to graphically as described in Sect. 3.3. Archimedean goal
the multi-objective optimization of a truss. They mini- programming and preemptive goal programming provide
mize the weight, displacement, and difficulty of construc-
Pareto optimal solutions if the goals form a Pareto op-
tion. The cross-sectional areas of the rods are the de- timal point or if all deviation variables, d+
j for functions
sign variables, and constraints are on strength and sta-
being increased and d− j for functions being reduced, have
bility. However, other than the work of Gerasimov and
positive values at the optimum (Miettinen 1999). The
Repko, the approach has not been used extensively, and
latter condition suggests that all of the goals must be
the characteristics of the weights are unclear. This lack of
unattainable. Generally, however, Archimedean and pre-
extensive use could be the result of potential nonlineari-
emptive goal programming can result in non-Pareto opti-
ties in the utility function and consequent computational
mal solutions (Zeleny 1982).
difficulties.
Zeleny (1982) briefly mentions multigoal program-
ming, in which various functions of |dj | are minimized as
3.7 independent objective functions in a vector optimization
Goal programming methods problem.
Hwang and Md. Masud (1979) present the goal at-
Charnes et al. (1955), Charnes and Cooper (1961), Ijiri tainment method, initially proposed by Gembicki (1974),
(1965), and Charnes et al. (1967) developed the goal pro- which is computationally faster than typical goal pro-
gramming method, in which goals bj are specified for each gramming methods. It is based on the weighted min-max
objective function Fj (x). Then, the total deviation from approach and is formulated as follows:

the goals kj=1 |dj | is minimized, where dj is the devi-
Minimize λ (23)
ation from the goal bj for the jth objective. To model x∈X,λ
the absolute values, dj is split into positive and nega-
− − subject to Fi (x) − wi λ ≤ bi , i = 1, 2, . . . , k ,
tive parts such that dj = d+j − dj , with dj ≥ 0, dj ≥ 0,
+
378

where wi are weights indicating the relative importance tural constitutive relations, and limits are placed on each
of each objective function and λ is an unrestricted scalar, of the design variables.
similar to that which is used in (16). The method of proper equality constraints (PEC) is
In response to the inability of goal programming to a modified version of the ε-constraint approach that en-
consistently yield Pareto optimal solutions, Ogryczak tails using strict equality constraints (Lin 1976). How-
(1994) develops a method called reference goal program- ever, the method may not always produce Pareto op-
ming, which is loosely based on the weighted min-max timal solutions. Stadler and Dauer (1992) call this the
approach. Specifically, it entails using (19) with an as- method of constraints and determine limits for ε , suggest-
piration point rather than the utopia point. However, in ing that varying ε provides the Pareto optimal set. The
this case, the utility function is modeled with the goal approach is implemented with basic mathematical exam-
programming format such as (22) and always provides ples that have two and three objective functions. Dauer
a Pareto optimal solution. and Krueger (1980) integrate the method of constraints
with preemptive goal programming and are able to solve
problems with a larger number of objective functions.
3.8 They apply their approach to a water resource-planning
Bounded objective function method problem described by Cohon (1978). Five objective func-
tions are used to model budget, flood control capabilities,
The bounded objective function method minimizes the sin- irrigation potential, water recreation, and wildlife ben-
gle most important objective function Fs (x). All other efits. 1500 variables are used to model design parame-
objective functions are used to form additional con- ters for two reservoir sites, six smaller flood control sites,
straints such that li ≤ Fi (x) ≤ εi , i = 1, 2, . . . , k, i = s and three flood damage sites. 600 constraints are used
(Hwang and Md. Masud 1979). li and εi are the lower and to model continuity in water mass flow, reservoir storage
upper bounds for the objective function Fi (x), respec- capacity, irrigation restrictions, hydroelectric energy re-
tively. li is obsolete unless the intent is to achieve a goal quirements, and inter-basin water transfers.
or fall within a range of values for Fi (x), rather than to Miettinen (1999) summarizes the work of Wendell
determine a minimum. and Lee (1977) and Corley (1980) in presenting a hybrid
Haimes et al. (1971) introduce the ε-constraint ap- method , in which the primary objective function Fs (x) is
proach (also called the e-constraint or trade-off ap- a weighted sum of all the objective functions and is sub-
proach), in which li is excluded. In this case, a systematic ject to the constraints of the ε-constraint method. This
variation of εi yields a set of Pareto optimal solutions approach yields a Pareto optimal solution for any ε .
(Hwang and Md. Musad 1979). However, improper selec-
tion of ε ∈ Rk can result in a formulation with no feasible
solution. Goicoechea et al. (1976), Cohon (1978), and 3.9
Stadler (1988) present methods for selecting ε-values that Physical programming
reflect preferences. A general mathematical guideline for
selecting εi is provided as follows (Carmichael 1980): Initially developed by Messac (1996), physical program-
ming maps general classifications of goals and objectives,
Fi (x∗i ) ≤ εi ≤ Fs (x∗i ) . (24) and verbally expressed preferences to a utility function.
It provides a means of incorporating preferences without
If it exists, a solution to the ε-constraint formula- having to conjure relative weights. The reader is referred
tion is weakly Pareto optimal (Miettinen 1999), and any to Messac (1996) for a complete explanation and to Chen
weakly Pareto optimal point can be obtained if the feas- et al. (2000) for further illustration.
ible region is convex and if all objective functions are Objective functions, constraints, and goals are treated
explicitly quasi-convex (Ruiz-Canales and Rufian-Lizana equivalently as design metrics. In general, the decision-
1995). If the solution is unique, then it is Pareto opti- maker customizes an individual utility function, which is
mal (Miettinen 1999). Of course, uniqueness can be dif- called a class function F i [Fi (x)], for each design metric.
ficult to verify, although if the problem is convex and if Specifically, each type of design metric is first associated
Fs (x) is strictly convex, then the solution is necessar- with a type of individual utility function distinguished by
ily unique (Chankong and Haimes 1983). Solutions with a general form, such as a monotonically increasing, mono-
active ε-constraints (and non-zero Lagrange multipliers) tonically decreasing, or unimodal function. Then, for each
are necessarily Pareto optimal (Carmichael 1980). metric, the decision-maker specifies the numerical ranges
Carmichael (1980) applies the ε-constraint approach that correspond to different degrees of preference (desir-
to a five-bar two-objective truss problem from Majid able, tolerable, undesirable, etc.). These ranges include
(1974). Weight is minimized with an ε-constraint on limits on the values of the metrics, which are modeled as
nodal displacement, and ε is varied to yield a series of additional constraints. As the design process evolves, the
Pareto optimal solutions. Four design variables represent ranges defining designer preferences may change accord-
various dimensions and the areas of the truss members. ingly. Messac (1996) discusses the mathematical details
Two equality constraints are used to represent the struc- behind the construction of the class functions. Because
 379

of the way these class functions are constructed, physi- constrained simple beams with three objectives (mass,
cal programming is able to effectively optimize objective displacement, and width) and two design variables (beam
functions with significantly different orders of magnitude height and width). Chen et al. (2000) solve a propulsion
(Messac et al. 2004). The requirement that the decision- system design problem with two objectives, five design
maker quantitatively classify different ranges of values for variables, and three constraints. Martinez et al. (2001)
each metric can be viewed in two ways. On one hand, optimize a relatively complex wing spar with three ob-
it suggests that physical programming requires signifi- jectives: cost, weight, and deflection; twenty-two design
cant familiarity with each objective and constraint. On variables concerning spar dimensions; and 101 constraints
the other hand, in a more positive light, it implies that concerning strength and limits on design variables. Phys-
physical programming allows one to make effective use ical programming has also been used with complex prob-
of available information. The individual utility functions, lems such as finite element sizing optimization involving
as non-dimensional unimodal transformations, are com- inflatable thin-walled structural members for housing
bined into a utility function as follows: (Messac et al. 2004).
 
1

dm
Fa (x) = log F i [Fi (x)] , (25) 3.10
dm i=1
Discussion
where dm represents the number of design metrics being
considered. Given the variety of methods in this section, the ques-
Messac et al. (2001) prove that physical programming tion arises as to which method is the best. Unfortunately,
provides a sufficient condition for Pareto optimality. In there is no distinct answer. However, methods that pro-
addition, Messac and Mattson (2002) demonstrate how vide both necessary and sufficient conditions for Pareto
physical programming can be used as a necessary condi- optimality are preferable. When one is interested in deter-
tion for Pareto optimality, providing all Pareto optimal mining a single solution, the advantages of obtaining only
points. In fact, it is superior to the weighted sum method Pareto optimal solutions (using a formulation that pro-
and to compromise programming in its ability to repre- vides a sufficient condition) are clear. In addition, provid-
sent the complete Pareto optimal set with an even distri- ing a necessary condition for Pareto optimality is also ad-
bution of points (Chen et al. 2000; Messac 2000; Messac vantageous. Methods with this latter ability are more ef-
et al. 2001). The process by which physical programming fective in reflecting the decision-maker’s preferences than
is used to provide multiple Pareto optimal points is de- formulations that necessarily miss certain points (do not
scribed briefly in Sect. 4.1, in reference to methods with provide a necessary condition). This is because, assuming
a posteriori articulation of preferences. Martinez et al. all Pareto points are similar mathematically, distinguish-
(2001) demonstrate the method’s ability to handle non- able only by the user’s preferences, there is no reason
convex Pareto optimal surfaces. to inherently exclude potential solutions. Such exclusion
Physical programming has been applied to a variety may rob the decision-maker of a solution that best reflects
of problems. In summarizing the application details, note his/her preferences.
that constraints and objectives may be treated equiva- Of the methods that provide a necessary and suffi-
lently as design metrics. Messac and Hattis (1996) ap- cient condition, which one should be used? The answer
ply physical programming to the design of high-speed to this question hinges, in part, on how accurately one
transport planes. The design metrics are the tank- is able to approximate the preference function. Phys-
volume ratio, recurring cost per passenger seat, initial ical programming is effective in this respect. Whereas
cost per passenger seat, propellant mass ratio, fuselage- a weight represents the simplest form of an individual
length/wing-root-length ratio, engine inlet area, wing utility function, physical programming allows one to cus-
sweep-back angle, and number of passengers. The de- tomize a more complex and accurate individual utility
sign parameters are the engine inlet area, wingspan, wing function for each objective. In addition, although physical
sweep-back angle, number of passengers, and propellant- programming operates based on imposed preferences, it
tank volume. Certain quantities appear both as design provides a means to circumvent the use of weights, which
parameters and as metrics, shedding light on the versa- may be awkward. However, the initial coding can be rela-
tility of this method. Although parameters may vary, the tively complicated, and significant knowledge of the prob-
decision-maker may express preferences regarding their lem functions is needed. Consequently, although other
values. Messac and Wilson (1998) apply physical pro- methods that provide a necessary and sufficient condition
gramming to the design of a robust controller for a two may come with deficiencies, they can be useful.
degree-of-freedom spring-and-mass system. There are five The exponential weighted criterion and the aug-
design metrics: settling time, stability, noise amplifica- mented Tchebycheff approach provide formulations that
tion, control effort (output of controller), and controller are both necessary and sufficient for Pareto optimality.
complexity (indicated by controller order). The nine de- However, they involve additional parameters ρ and p,
sign variables are mathematical parameters used in the and it can be difficult to set them without inducing com-
development of the controller. Messac (2000) models un- putational complications. The lexicographic Tchebycheff
380

method also serves as a necessary and sufficient condition, treme, the decision-maker may have no preferences what-
but its pitfall is the computational expense of having to soever, in which case methods with no articulation of
solve multiple problems. preferences (discussed in Sect. 5) are most appropriate.
Formulations with an achievement function can also Thus, discussing effectiveness in reflecting preferences
provide sufficient and necessary conditions for Pareto op- assumes that preferences exist, which may not always
timality as long as the aspiration point is unattainable. be the case. In addition, the decision-maker may have
This is true regardless of whether or not weights are in- varying amounts of preference information, and this can
corporated; the aspiration point can be used as an in- dictate the complexity of the approach that should be
dependent method parameter. However, when using the used.
formulation as a necessary condition, different solution
points are determined by altering the aspiration point.
Systematically modifying the aspiration point in an ef- 4
fort to represent the complete Pareto optimal set, while Methods for a posteriori articulation of preference
ensuring that the aspiration point is infeasible, is imprac-
tical. Consequently, achievement function formulations In some cases, it is difficult for a decision-maker to ex-
are most accurately categorized as methods with no ar- press an explicit approximation of the preference func-
ticulation of preferences, unless weights are incorporated. tion. Therefore, it can be effective to allow the decision-
The aspiration point is most effectively used only as an maker to choose from a palette of solutions. To this end,
approximation of the utopia point. an algorithm is used to determine a representation of the
Most of the methods in this section allow one to de- Pareto optimal set. Such methods incorporate a posteri-
sign a utility function by setting method parameters. ori articulation of preferences, and they are called cafete-
The bounded objective function method and the more ria or generate-first-choose-later approaches (Messac and
robust ε-constraint method are apparent exceptions to Mattson 2002).
this idea. Rather than requiring weights or an ordering The use of weighted methods is a common means
of objectives, these methods involve setting limits on the of providing the Pareto optimal set (or subset). These
objectives. However, one can view the vector ε as a set methods all depend on the solution of multiple sequen-
of method parameters rather than as a set of functional tial optimization problems with a consistent variation in
limits. Consistent variation in these parameters theoret- method parameters. When these methods are used to
ically can yield the complete Pareto optimal set, although provide only a single Pareto optimal point, the decision-
difficulties may be encountered in selecting parameters maker’s preferences are presumably embedded in the pa-
that provide a feasible solution. Nonetheless, the differ- rameter set. On the other hand, when the decision-maker
ent types of method parameters discussed thus far can desires a set of Pareto optimal points, the parameters
be used to represent different types of preferences. Con- vary simply as a mathematical device. In such cases, it
sequently, the nature of the decision-maker’s preferences is important for the formulation to provide a necessary
(goals, relative importance of functions, limits, etc.) can condition for Pareto optimality, encompassing the abil-
dictate which approach is most suitable. ity to yield all of the Pareto optimal points. However,
Study of the physical programming method raises an repeatedly solving the weighted formulations in Sect. 3
issue that is central to multi-objective optimization. With can be ineffective in providing an even spread of points
physical programming, the decision-maker needs to spec- that accurately represents the complete Pareto optimal
ify a relatively large amount of information, and as we set. In addition, although a formulation theoretically pro-
implied, this can be viewed as a hindrance or as an oppor- vides a necessary condition, it may not be clear how to set
tunity. It is an opportunity in that physical programming method parameters in order to capture only Pareto opti-
is relatively effective in reflecting preferences, and this ef- mal points. Consequently, some algorithms are designed
fectiveness is a consequence of the method’s capacity for specifically to produce a set of Pareto optimal points that
information that the decision-maker may provide. With accurately represents the complete Pareto set.
relatively complex preferences, one must provide more in-
formation. Then, the more information one provides, the
more accurately preferences are represented. However, as 4.1
a method increases in its ability to incorporate more in- Physical programming
formation, its use inherently becomes more involved.
Some methods, such as the weighted sum, have a low Although it was initially developed for a priori articula-
capacity for preference information; they do not allow tion of preferences, physical programming can be effective
the user to provide extensive input. This is not neces- in providing Pareto optimal points that accurately rep-
sarily detrimental, as there may be instances when pref- resent the complete Pareto optimal set, even when the
erence information is limited or simply does not exist. Pareto optimal surface is non-convex (Messac and Matt-
The decision-maker may not know exactly what he/she son, 2002; Martinez et al. 2001). As explained earlier,
wants, and such scenarios do not warrant approaches when physical programming is used for a priori articula-
that can incorporate additional information. In the ex- tion of preferences, the decision-maker specifies a set of
 381

constants that delineates numerical ranges of objective and are not significant in terms of deciding with which
function and constraint values. These ranges are associ- objective to accept a loss and with which to pursue an
ated with different degrees of preference (desirable, tol- improvement. Das (1999) provides a modification to the
erable, undesirable, etc). This is done for each metric, NBI method that enables it to yield a greater number of
resulting in a unique utility function. In order to represent Pareto points in the nonlinear portions of the Pareto op-
the complete Pareto optimal set for a posteriori articu- timal surface.
lation of preferences, Messac and Mattson (2002), and Das and Dennis (1998) apply the NBI method to
Messac et al. (2001) provide a detailed algorithm for sys- a relatively simple two-objective mathematical example
tematically modifying these constants as a mathematical and to a three-bar truss design problem from Koski
tool rather than an indication of preferences. As the con- (1988). In the latter problem, five objective functions are
stants are shifted, contours of the utility function traverse used to represent the total volume, the nodal displace-
the criterion space, capturing different Pareto optimal ment, and the absolute value of the stress in each bar. The
points. four design variables are the cross-sectional area of each
bar and the position of the vertical bar, which has a fixed
length. The constraints consist of limits on the stresses.
4.2
Normal boundary intersection (NBI) method
4.3
In response to deficiencies in the weighted sum approach, Normal constraint (NC) method
Das (1999) and Das and Dennis (1998) present the nor-
mal boundary intersection (NBI) method. This method The normal constraint method provides an alternative to
provides a means for obtaining an even distribution of the NBI method with some improvements (Messac et al.
Pareto optimal points for a consistent variation in the 2003). When used with normalized objective functions
user-supplied parameter vector w, even with a non- and with a Pareto filter , which eliminates non-Pareto op-
convex Pareto optimal set. The approach is formulated as timal solutions, this approach provides a set of evenly
follows: spaced Pareto optimal points in the criterion space. In
fact, it always yields Pareto optimal solutions. In add-
Minimize λ (26) ition, its performance is independent of design objective
x∈X,λ
scales. The method proceeds as follows.
subject to Φw + λn = F (x) − F◦ . First, the utopia point is determined, and its com-
ponents are used to normalize the objectives with (7).
Φ is a k × k pay-off matrix in which the ith column is The individual minima of the normalized objective func-
composed of the vector F (xi ∗ ) − F◦ , where F (xi ∗ ) is the tions form the vertices of what is called the utopia hy-
vector of objective functions evaluated at the minimum perplane (in the criterion space). A sample of evenly dis-
of the ith objective function. The diagonal elements
k of Φ tributed points on the utopia hyperplane is determined
are zeros. w is a vector of scalars such that i=1 wi = 1 from a linear combination of the vertices with consis-
and w ≥ 0. n = −Φe, where e ∈ Rk is a column vector of tently varied weights in the criterion space. The user must
ones in the criterion space. n is called a quasi-normal vec- specify how many points are needed to accurately repre-
tor. Since each component of Φ is positive, the negative sent the Pareto optimal set. Then, each sample point is
sign ensures that n points towards the origin of the cri- projected onto the Pareto optimal surface (boundary of
terion space. n gives the NBI method the property that the feasible criterion space) by solving a separate single-
for any w, a solution point is independent of how the ob- objective problem. This problem entails minimizing one
jective functions are scaled. As w is systematically modi- of the normalized objective functions with additional in-
fied, the solution to (26) yields an even distribution of equality constraints. Note that the NBI method involves
Pareto optimal points representing the complete Pareto additional equality constraints. Under “contrived circum-
set. stances,” the method described thus far may generate
Technically, the NBI method finds the portion of the non-Pareto optimal solutions, so a Pareto filter is used
boundary of Z that contains the Pareto optimal points. to rectify this potential fault. Essentially, the filter al-
However, the method may also yield non-Pareto opti- gorithm searches for and deletes any dominated solution
mal points; it does not provide a sufficient condition for points. This is done by comparing each potential solution
Pareto optimality. This is not necessarily a disadvantage, point to every other solution point. All dominated points
since such points help construct a “ . . . smoother ap- are discarded. Similar procedures are common with ge-
proximation of the Pareto boundary” (Das and Dennis netic algorithms, as discussed in Sect. 6.
1998). Messac et al. (2003) apply this approach to two il-
The NBI method also overlooks some Pareto optimal lustrative mathematical examples, each with two objec-
points when k > 2; it does not always serve as a necessary tives, two variables, and one constraint. In addition, the
condition for Pareto optimality. However, the overlooked method is applied to a three-bar truss problem from
points tend to lie near the periphery of the Pareto set Koski (1985). The cross-sectional areas of the bars are
382

the design variables. The linear combination of nodal yields a single function Fg (F). Whereas such an approach
displacement and the volume are minimized. Limits are is the lowest common denominator, the primary general
placed on the design variables and on the stresses in each global criterion formulation, which can be reduced to
bar. many other formulations, is given by (10) or (11) with all
of the weights equal to one (Hwang and Md. Masud 1979;
Zeleny 1982; Stadler 1988). Variations of the basic global
4.4
criterion method are discussed as follows.
Discussion
Technique for order preference by similarity to ideal
solution
The methods in this section allow the decision-maker to
When forming a measure of distance, it is possible and
view options before making a decision. One does not con-
often necessary to seek a point that not only is as close
sider which objective function is more or less important;
as possible to the utopia point but also is as far away as
one only considers which solution is most appealing. This
possible from some detrimental point. The technique for
can be done in terms of the design space or in terms of
order preference by similarity to ideal solution (TOPSIS)
the criterion space; one may select a final point based
takes this approach and is a form of compromise program-
on objective function values or based on design variable
ming (Yoon 1980; Hwang et al. 1993). The utopia point is
values. Nonetheless, one must eventually present the solu-
the positive ideal solution, and the vector in the criterion
tions to the decision-maker in graphical or tabular form.
space that is composed of the worst or most undesirable
Graphical presentations of solutions generally are limited
solutions for the objective functions is called the nega-
to three-dimensional space, and even three-dimensional
tive ideal . Similarity is developed as a function that is
representations of a Pareto surface can be unclear. When
inversely proportional to the distance from the positive
presenting solutions in tabular form, selecting a single so-
ideal and directly proportional to the distance from the
lution can be an intimidating task with a relatively large
negative ideal. Then, the similarity is maximized.
number of objectives, variables, or solution points. Con-
Hwang et al. (1993) use this method with fuzzy the-
sequently, these methods are best suited to problems with
ory and solve a linear nutrition problem. The problem
a relatively small number of objectives.
involves seven variables that represent quantities of dif-
In terms of computational expense and in terms of
ferent types of food; three objective functions modeling
presentation to the user, one must decide how many
carbohydrate intake, cholesterol intake, and cost; and ten
points to use to represent the Pareto optimal set. On
constraints representing limits on the intake of various vi-
one hand, using more solution points requires additional
tamins and food groups.
computation time, but it can provide a clearer represen-
Objective sum method
tation of the Pareto optimal set. On the other hand, using
When (8) is used with p = 1 and w = 1, the result
fewer points requires less CPU and makes presentation of
is simply the sum of the objective functions. Not only
Pareto solutions in tabular form more manageable, but it
is this a special case of a global criterion method, it is
can result in an incomplete depiction of the Pareto set.
a special case of the weighted sum method discussed in
Genetic algorithms, which are discussed later in the
Sect. 3.2. We introduce the term objective sum method
paper, also provide a useful approach for determining
to highlight a fundamental approach that always provides
the Pareto optimal set for a posteriori articulation of
a Pareto optimal solution. In addition, it provides a fur-
preferences.
ther example of the similarities between the methods in
this section and those in Sect. 3.
5 Min-max method
Methods with no articulation of preferences A basic min-max formulation is derived by excluding
the weights in (8) and (9), and using p = ∞. Assuming the
weights are excluded (10) yields an L∞ -norm, which does
Often the decision-maker cannot concretely define what
not necessarily yield a Pareto optimal point (Yu 1973;
he or she prefers. Consequently, this section describes
Stadler 1988). However, in accordance with the definition
methods that do not require any articulation of pref-
of optimality in the min-max sense (Osyczka 1978), if the
erences. Most of the methods are simplifications of the
minimum of the L∞ -norm is unique, then it is Pareto
methods in Sect. 3, typically with the exclusion of method
optimal. If the solution is not unique, the definition of
parameters. Consequently, much of the discussion in
optimality in the min-max sense provides additional the-
Sect. 3 applies to this section as well.
oretical (impractical in terms of computational applica-
tion) criteria for a min-max algorithm to eventually yield
5.1 a Pareto optimal point. For the case of two objective func-
Global criterion methods tions, Yu (1973) derives conditions for the Pareto optimal
set in the criterion space under which the L∞ -norm has
The fundamental idea behind most global criterion a unique solution. In most cases, however, one cannot
methods is the use of an exponential sum, which is formed verify uniqueness, so it is unclear whether a solution is
by setting all of the weights in (8) or (9) to one. This Pareto optimal or not. Regardless of uniqueness, the L∞ -
 383

norm always provides a weakly Pareto optimal solution points) of the product of the players’ utilities. In this case,
(Wierzbicki 1986). the utility functions always have non-negative values and
The basic min-max formulation is posed as follows: have a value of zero in the absence of cooperation (when
no agreement is reached). In terms of a mathematical
Minimize max [Fi (x)] . (27) formulation in which individual objective functions are
x∈X i
minimized, the method entails maximizing the following
Osyczka (1978) treats (27) as a standard single objective global criterion (Straffin 1993):
function, where max [Fi (x)] provides the objective func-
i 
k
tion values at point x. Tseng and Lu (1990) incorporate Fg (x) = [si − Fi (x)] , (30)
Osyczka’s approach for a ten-member cantilever truss, i=1
a twenty-five-member transmission tower, and a two-
hundred-member plane truss, all of which are detailed by where si ≥ Fi (x). si may be selected as an upper limit
Haug and Arora (1979). There are four objectives: mini- on each function, guaranteeing that F (x) < s. This en-
mize the weight, minimize the maximum member-stress, sures that (30) yields a Pareto optimal point, considering
minimize the maximum nodal displacement, and maxi- that if any component of the product in (30) becomes
mize the natural frequency. The actual number of objec- negative, the result can be a non-Pareto optimal solu-
tive functions depends on the number of members and tion. Alternatively, si may be determined as the value of
nodes. The cross-sectional areas of the members represent objective i at the starting point, in which case the con-
the design variables, and the constraints are on member straints Fi (x) ≤ si must be added to the formulation to
stress and areas. ensure Pareto optimality. In any case, the solution to this
Eschenauer et al. (1990) follow Bendsoe et al. (1984), approach, in terms of game theory or in terms of multi-
and use a more common formulation like the one shown in objective optimization, depends on the value of s, and
(16), with additional constraints such that (Fi (x) − Fi◦ ) (30) tends to improve most significantly those objectives
/Fi◦ − λ ≤ 0. Vasarhelyi and Logo (1986) use a similar ap- that are farthest away from si (Davis 1983).
proach to design a steel frame. Volume and shear stress Mazumdar et al. (1991) demonstrate the use of (30)
are minimized using ten design variables representing in solving a telecommunications problem concerning op-
cross-sectional dimensions. timal network flow. The problem has two objective func-
In order to avoid additional constraints and the dis- tions (general performance indices for each network user),
continuity of (27), Li (1992) and Ben-Tal and Teboulle two design variables (the throughput for each user, asso-
(1989) develop the following smooth approximations: ciated with a specific objective function), and four basic
 k  constraints.
1
On a fundamental level, the Nash arbitration ap-
cFi (x)
Fg (x) = ln e , (28) proach simply entails minimizing the product of the
c i=1
 k  objective functions. In fact, doing so provides a basic,

Fi (x) though uncommon, approach to multi-objective opti-
/c
Fg (x) = c log e . (29)
mization, which may be called the objective product
i=1
method. It is equivalent to (21) with w = 1. Cheng and
c > 0 is called the controlling parameter . Although the Li (1996) prove that the solution to such a formulation
physical significance of c is unclear, in general it controls is always Pareto optimal. However, the proof involves
the accuracy with which (28) and (29) approximate (15). normalized objective functions, and the Pareto optimal
The accuracy improves as c tends to infinity with (28) characteristics of the solution depend on the nature of the
and as c tends to zero with (29). Li (1992) shows that normalization scheme.
the solution with (28) is “fairly insensitive” to changes Although the solution to is a function of the normal-
in c. This is done using simple unconstrained mathe- ization scheme, a benefit of this approach is that it is
matical examples with three objective functions and two not necessary to ensure that different functions have simi-
variables. Li recommends values between 104 and 106 , lar orders of magnitude. With a product, even objective
although Cheng and Li (1998b) suggest using values be- function values with relatively small orders of magnitude
tween 103 and 104 . can have a significant effect on the solution. However,
a caveat of any product-type global criterion is that it can
introduce unwieldy nonlinearities.
5.2 Cheng and Li (1996) apply the objective product
Nash arbitration and objective product method method to a three-story steel shear frame with four objec-
tive functions concerning weight, strain energy, potential
The Nash arbitration scheme is an approach that is de- energy, and input energy; seven constraints concerning
rived from game theory. Based on predetermined axioms stress, displacement, stiffness, and dimensions; and nine
of fairness, which are summarized by Davis (1983), Nash design variables representing the moments of inertia of six
(1950) suggests that the solution to an arbitration prob- columns and the mass of three girders. They also solve
lem be the maximum (over a convex compact set of a similar problem with control requirements.
384

5.3 value of the exponent. Different values of p do in fact con-

Rao’s method stitute an articulation of preferences, in that such stipu-
lations contribute to the design of the utility function. In
The following work by Rao (1987) and Rao and Frei- addition, the size of the exponent reflects the emphasis
heit (1991) involves a method that is based on the use of that is placed on the largest component of the summa-
a product-type global criterion shown in (30). First, the tion. However, articulation of preferences typically im-
following supercriterion is minimized: plies that one orders or indicates the relative importance
of objectives.

k
The objective product method and the Nash arbitra-
SU = [1 − Finorm (x)] , (31)
tion scheme provide approaches that alleviate the need
i=1
for function transformation. However, they introduce
where Finorm (x) is a normalized objective function, with nonlinearities and thus computational difficulties. These
values between zero and one, such that Finorm = 1 is the formulations are most often incorporated within other
worst possible value. Next, one forms the Pareto optimal algorithms, such as Rao’s method.
objective FC , which is any scalarized objective function
that yields a Pareto optimal solution. The method pa-
rameters that are incorporated in the scalarized objective 6
function are included as design variables. Then, a new Genetic algorithms
objective function, OBJ = F C − SU , is minimized. Al-
though Rao and Freiheit (1991) provide sound reason- The methods for multi-objective optimization presented
ing behind the development of this method, the work of thus far have involved unique formulations that are solved
Cheng and Li (1996), along with the properties of the using standard optimization engines (single-objective op-
Nash arbitration scheme, suggest that using FC may not timization method). However, other approaches such
be necessary. as genetic algorithms can be tailored to solve multi-
Rao and Hati (1980) apply this method to a three- objective problems directly. Holland (1975) introduced
degree-of-freedom spring-and-damper system. The rela- genetic algorithms. Kocer and Arora (1999) outline a gen-
tive displacement and transmitted force are minimized eral genetic algorithm and compare it with simulated
subject to limits on the design variables, which are the annealing in its ability to minimize the cost of H-frame
mass, spring constant, and damping coefficient for each transmission poles subjected to earthquake loading with
degree-of-freedom. Rao et al. (1988) optimize actively discrete variables. Gen and Cheng (1997) give a com-
controlled two-bar and twelve-bar trusses. There are four prehensive treatment of genetic algorithms with a slant
objective functions: weight, “control effort”, effective towards industrial engineering, whereas Davis (1991) and
damping response time, and performance index, which Goldberg (1989) provide a more general treatment.
provides a measure of the total system energy. The cross- Because genetic algorithms do not require gradient in-
sectional areas of the structural members are the design formation, they can be effective regardless of the nature
variables. Limits are placed on the damping ratios and of the objective functions and constraints. They combine
cross-sectional areas. Rao and Freiheit (1991) apply this the use of random numbers and information from previ-
approach to the probabilistic design of an eighteen-speed ous iterations to evaluate and improve a population of
gear train. Reliability in bending and in wear is maxi- points (a group of potential solutions) rather than a single
mized while weight is minimized. The width of each gear point at a time.
is used as a design variable. Genetic algorithms are global optimization techniques,
which means they converge to the global solution rather
than to a local solution. However, this distinction be-
5.4 comes unclear when working with multi-objective opti-
Discussion mization, which usually entails a set of solution points.
Mathematically, a single global solution to a multi-
Although this section covers a few different approaches, objective problem does not exist unless the utopia point
there are essentially two fundamental formulations: ex- happens to be attainable. The defining feature of multi-
ponential sum and objective product. The common min- objective optimization methods that involve global opti-
max and objective sum methods are special cases of mization is that they determine solutions that are glob-
the exponential sum formulation. Most other approaches ally Pareto optimal, not just locally Pareto optimal. This
that do not require any articulation of preferences simply means that Definitions 1 through 3 apply to the complete
entail some variation of these fundamental scalarization feasible space, and not just to a localized feasible region.
formulations. Global optimization techniques can be used for multi-
The global criterion method, which is a form of the objective optimization in two capacities. First, any single-
exponential sum, is a broad, easy-to-use approach encom- objective global optimization technique, of which there
passing many common algorithms. In the current liter- are many (Torn and Zilinskas 1987; Arora et al. 1995; El-
ature, there is little discussion of the significance of the wakeil and Arora 1996), can be used as an optimization
 385

engine for the formulations in Sects. 3–5. There are few on its fitness value. Fitness, which is determined by a fit-
examples for which techniques are used in this capacity, ness function, is an indication of how desirable a design
with the exceptions of interval analysis (Ichida and Fujii is in terms of surviving into the next generation. The se-
1990) and genetic algorithms (Leu and Yang 1999; Chi- lection probability represents the chance for survival and
ampi et al. 1998). This approach does have advantages. is proportional to a design’s fitness value. A roulette wheel
For instance, although there is a relatively high compu- approach is commonly used in the selection process in
tational expense with genetic algorithms, the ability to which a random number is generated and compared with
locate a global optimum and the independence from the the selection probability of each member of the popula-
structure of the constraints and objective functions can tion. The details of the process are outlined in Gen and
be worth the cost. However, in terms of multi-objective Cheng (1997).
optimization, the appeal of genetic algorithms is their Once a new generation of designs is determined,
ability to converge on the Pareto optimal set as a whole. crossover is conducted as a means to introduce variations
We refer to genetic algorithms that are used in this al- into the population of designs. Crossover is the process
ternative capacity as genetic multi-objective algorithms. of combining or mixing two different designs. Although
These algorithms compete with gradient-based methods there are many approaches for performing crossover
for a posteriori articulation of preferences. However, the (Goldberg 1989; Gen and Cheng 1997), the most com-
computational efficiency of these two approaches has not mon is the one-cut-point method . A cut point position
been compared. on a design’s genetic string is randomly determined and
Genetic algorithms loosely parallel biological evolu- marks the point at which two parent designs split. The
tion and are based on Darwin’s theory of natural selec- children are new members of the population. Selecting
tion. The specific mechanics of the algorithms involve how many or what percentage of designs crossover and at
the language of microbiology and, in developing new po- what points the crossover operation occurs, is part of the
tential solutions, mimic genetic operations. A population heuristic nature of genetic algorithms.
represents a group of potential solution points. A gener- The next operation, which also is used to introduce
ation represents an algorithmic iteration. A chromosome variations into the population, is mutation. It is a ran-
is comparable to a design point, and a gene is comparable dom process that entails altering part of a design’s genetic
to a component of the design vector. Following a dis- string. In the case of binary encoding, a bit (a digit in a bi-
cussion of genetic algorithms for single-objective prob- nary number) is switched from zero to one or vice versa.
lems, techniques used for multi-objective problems are Mutation plays a secondary role in the operation of ge-
presented. netic algorithms (Goldberg and Samtani 1986). However,
reproduction and crossover alone can lose genetic mate-
rial (potentially beneficial values of specific design vector
6.1 components). Gen and Cheng (1997) discuss the sensitiv-
Single-objective problems ity of genetic algorithms to the heuristic mutation rate.

A brief overview of the fundamentals of genetic algo-

rithms is given in this section. The reader is referred to 6.2
Goldberg (1989), Davis (1991), and Marler and Arora Multi-objective problems
(2003) for details. Genetic algorithms for single-objective
problems are composed of several steps. The first step in The primary questions when developing genetic algo-
the implementation of the algorithm is to decide on an en- rithms for multi-objective problems are how to evaluate
coding scheme, which determines the form in which the fitness, how to determine which potential solution points
design variables will be manipulated. Encoding is the pro- should be passed on to the next generation, and how to in-
cess of translating a real design vector (chromosome) into corporate the idea of Pareto optimality. The approaches
a genetic string, which is typically composed of binary that are described in this subsection collectively address
numbers. Although binary encoding is the most common these issues. Different techniques are discussed that serve
approach, Gen and Cheng (1997) mention real number en- as potential ingredients in a genetic multi-objective opti-
coding for constrained problems, and integer encoding for mization algorithm. In accordance with much of the lit-
combinatorial problems. After the details of the encoding erature on multi-objective genetic algorithms, constraints
process are determined, an initial population of designs is are not addressed directly. It is assumed that a penalty
randomly generated. Given a population of designs, three approach is used to treat constraints.
basic operations are applied: reproduction, crossover , and Vector evaluated genetic algorithm (VEGA)
mutation. Schaffer (1985) presents one of the first treatments
“Reproduction” is somewhat of a misnomer, and it of multi-objective genetic algorithms, although he only
would be more accurate to use the term selection or sur- considers unconstrained problems. The general idea be-
vival . Nonetheless, it involves selecting design vectors hind Schaffer’s approach, called the vector evaluated ge-
from the current generation to be used in the next gen- netic algorithm (VEGA), involves producing smaller sub-
eration, and whether or not a design is selected depends sets of the original population, or sub-populations, within
386

a given generation. One sub-population is created by eval- tion, and the points that are non-dominated relative to
uating one objective function at a time rather than ag- the remaining group are given a rank of two. This pro-
gregating all of the functions. The selection process is cess is repeated until all points are ranked. Those points
composed of a series of computational loops, and during with the lowest rank have the highest fitness value. That
each loop, the fitness of each member of the population is is, fitness is determined such that it is inversely propor-
evaluated using a single objective function. Then, certain tional to the rank. This may be done using any of several
members of the population are selected and passed on to methods (Fonseca and Fleming 1993; Srinivas and Deb
the next generation, using the stochastic selection pro- 1995; Cheng and Li 1998; Narayanan and Azarm 1999).
cesses discussed earlier. This selection process is repeated Belegundu et al. (1994) suggest discarding points with
for each objective function. Consequently, for a problem higher ranks and immigrating new randomly generated
with k objectives, k sub-populations are created, each points.
with η/k members, where η is the population size. The Pareto-set filter
resultant sub-populations are then shuffled together to It is possible to have a Pareto optimal point in a par-
yield a new complete population. ticular generation that does not survive into the next
This process is based on the idea that the minimum generation. In response to this condition, Cheng and Li
of a single objective function is a Pareto optimal point (1997) propose the use of a Pareto-set filter , which is
(assuming the minimum is unique). Such minima gener- described as follows. The algorithm stores two sets of so-
ally define the vertices of the Pareto optimal set. Conse- lutions: a current population and a filter . The filter is
quently, Schaffer’s method does not necessarily yield an called an approximate Pareto set, and it provides an ap-
even distribution of Pareto optimal points. Solutions in proximation of the theoretical Pareto optimal set. With
a given generation tend to cluster around individual func- each generation, points with a rank of one are saved in the
tion minima, giving rise to the evolution of species, where filter. When new points from subsequent generations are
a species is a class of organisms with common attributes. added to the filter, they are subjected to a non-dominated
Schaffer proposes two possible, though not completely ef- check within the filter, and the dominated points are dis-
fective, solutions. He suggests that non-dominated points carded. The capacity of the filter is typically set to the size
in each generation receive a “heuristic selection prefer- of the population. When the filter is full, points at a mini-
ence.” In addition, crossbreeding is encouraged among mum distance from other points are discarded in order to
species (different sub-populations). maintain an even distribution of Pareto optimal points.
Shuffling all of the sub-populations into one popula- The filter eventually converges on the true Pareto optimal
tion is paramount to determining fitness using a weighted set.
sum of the objective functions (Richardson et al. 1989; Ishibuchi and Murata (1996), and Murata et al. (1996)
Fonseca and Fleming 1993). However, considering only use a similar procedure called an elitist strategy, which
one objective function at a time is comparable to setting functions independent of rank. As with the Pareto-set
all but one of the weights to zero. The vector of weights filter, two sets of solutions are stored: a current popula-
represents a search direction in the criterion space, and tion and a tentative set of non-dominated solutions, which
if only one component of the vector is non-zero, then is an approximate Pareto set. With each generation, all
only orthogonal search directions, parallel to the axes of points in the current population that are not dominated
the criterion space, are used (Murata et al. 1996). Such by any points in the tentative set are added to the set.
a process can be relatively ineffective. Goldberg (1989), Then, dominated points in the set are discarded. After
Fonseca and Fleming (1993), and Srinivas and Deb (1995) crossover and mutation operations are applied, a user-
provide detailed explanations and critiques of Schaffer’s specified number of points from the tentative set are re-
ideas. introduced into the current population. These points are
Ranking called elite points. In addition, the k solutions with the
A class of alternatives to VEGA involves giving each best values for each objective function can be regarded as
member of a population a rank based on whether or not elite points and preserved for the next generation (Mu-
it is dominated (Goldberg 1989; Fonseca and Fleming rata et al. 1996).
1993; Srinivas and Deb 1995; Cheng and Li 1998). Fitness Tournament selection
then is based on a design’s rank within a population. The Horn et al. (1994) develop the tournament selection
means of determining rank and assigning fitness values technique for the selection process, which proceeds as fol-
associated with rank may vary from method to method, lows. Two points, called candidate points, are randomly
but the general approach is common as described below. selected from the current population. These candidate
For a given population, the objective functions are points compete for survival in the next generation. A sep-
evaluated at each point. All non-dominated points receive arate set of points called a tournament set or comparison
a rank of one. Determining whether a point is dominated set is also randomly compiled. The candidate points are
or not (performing a non-dominated check ) entails com- then compared with each member of the tournament set.
paring the vector of objective function values at the point If there is only one candidate that is non-dominated rela-
to the vector at all other points. Then, the points with tive to the tournament set, that candidate is selected to
a rank of one are temporarily removed from considera- be in the next generation. However, if there is no pref-
 387

erence between candidates, or when there is a tie, fit- Husbands (1994) demonstrates the use of co-evolutio-
ness sharing (explained in the next paragraph) is used nary genetic algorithms for multi-objective optimiza-
to select a candidate. The user specifies the size of the tion, focusing specifically on the application to job shop
tournament set as a percentage of the total population. scheduling problems. With such algorithms, each mem-
Consequently, the size of the tournament set imposes the ber of the population is allowed to conduct the crossover
degree of difficulty in surviving, which is called the domi- operation only with individuals in their own local neigh-
nation pressure. An insufficient number of Pareto optimal borhood, which is defined in terms of a Gaussian distri-
points will be found if the tournament size is too small, bution over distance from the individual (Hillis 1990).
and premature convergence may result if the tournament Neighborhoods overlap. Selection is based on ranking,
size is too large (Srinivas and Deb 1995). and offspring replace individuals from their parents’
Niche techniques neighborhood.
A niche in genetic algorithms is a group of points Additional techniques
that are close to each other, typically in the criterion Osyczka and Kundu (1996) develop an algorithm that
space. Niche techniques (also called niche schemes or determines fitness based on the Euclidean distance in the
niche-formation methods) are methods for ensuring that criterion space, between a point in the current population
a population does not converge to a niche, i.e., a limited and each point in the approximate Pareto set. In con-
number of Pareto points. Thus, these techniques foster junction with the elitist strategy, Ishibuchi and Murata
an even spread of points (in the criterion space). Genetic (1996) and Murata et al. (1996) use methods for selec-
multi-objective algorithms tend to create a limited num- tion that are based on a weighted-sum objective function.
ber of niches; they converge to or cluster around a limited Kursawe (1991) also presents a weighted-sum selection
set of Pareto points. This phenomenon is known as ge- process using discrete weights of zero or one. Gen and
netic drift (or population drift), and niche techniques Liu (1995) propose a method for selection based on con-
force the development of multiple niches while limiting strained preemptive goal programming. Schaumann et al.
the growth of any single niche. (1998) develop the idea of a Pareto fitness function with
Fitness sharing is a common niche technique the ba- which Pareto optimal designs have a fitness of one or
sic idea of which is to penalize the fitness of points in greater, and non-Pareto optimal designs have a fitness be-
crowded areas, thus reducing the probability of their sur- tween zero and one.
vival to the next generation (Goldberg and Richardson Applications
1987; Deb 1989; Srinivas and Deb 1995). The fitness of There are many potential applications for genetic
a given point is divided by a constant that is proportional multi-objective optimization algorithms. For example,
to the number of other points within a specified distance Belegundu et al. (1994) use them to design an airfoil
in the criterion space. In this way, the fitness of all the and a laminated ceramic composite. The airfoil problem
points in a niche is shared in some sense, thus the term is based on the work of Kielb and Kaza (1983), and it
“fitness sharing”. involves maximizing the torsional flutter margin while
In reference to tournament selection, when two candi- minimizing the torsional resonant amplitude. The ratio of
dates are both either non-dominated or dominated, the bending frequency to torsion frequency and the location
most fit candidate is the one with the least number of of the center of gravity provide the two design variables,
individuals surrounding it (within a specified distance which are subject to limits. With the ceramic compos-
in the criterion space). This is called equivalence class ite problem, the material cost and tensile stress in the
sharing. core are minimized with stress constraints and limits on
Cheng and Li (1998) present a technique in which off- the design variables. Six design variables represent the
spring replace a parent if the offspring have higher fitness thickness of different layers and the volume fractions.
values. Then, children always have characteristics that Schaumann et al. (1998) apply genetic algorithms to
are equivalent or superior to those of their parents and, the optimization of a reinforced concrete structure and to
in a sense remain close to their parents’ position, avoid- an urban planning problem. With the concrete structure,
ing drift. This approach does not necessarily mimic na- the material cost and construction time are minimized.
ture, but it can add to the effectiveness of the algorithm. 112 design variables are used to represent the dimen-
Cavicchio (1970) refers to this approach as preselection. sions of 217 structural members. 98 additional variables
Narayana and Azarm (1999) present a method in are used to represent the number of workers needed to
which a limit is placed on the Euclidean distance in form the structural elements and to represent the delay
the criterion space between points (parents) that are se- in construction time. Constraints are imposed to limit the
lected for crossover. If the distance is too small, then the amount of steel reinforcement in each structural mem-
parents are not selected for crossover. In addition, the ber. The urban planning problem involves minimizing the
authors suggest that only non-dominated points (points traffic travel time, minimizing the cost, and minimizing
with a rank of 1) be evaluated for constraint violation. the change in land use. Constraints are used to limit hous-
Those points that violate constraints then receive a fit- ing capacity and to insure housing for five income brack-
ness penalty, which is imposed by reassigning their rank ets. 130 discrete design variables are used to represent
to be a large number (e.g., the population size η). how different land zones are used. 25 additional discrete
388

variables are used to represent street characteristics (2- paradigm. There may be some blending of the methods,
lane collector, 3-lane arterial, etc.). as is the case with the Pareto-set filter (applied to points
with a rank of one).

6.3
Discussion 7
Summary and conclusions
Genetic multi-objective algorithms provide an approach
for a posteriori articulation of preferences; they are in- 7.1
tended for depicting the complete Pareto optimal set. In Summary
this sense, they provide an alternative to the methods
discussed in Sect. 4. There, the methods determine one A survey of predominant, continuous, and nonlinear
Pareto point at a time, and each point requires the so- multi-objective optimization methods is presented. Fun-
lution of a single-objective optimization problem. Alter- damental concepts are discussed in the context of the
natively, genetic multi-objective algorithms do not re- criterion space and the design space. Seemingly different
quire solving a sequence of single-objective problems. In methods and terminology are consolidated and related
addition, these algorithms are relatively robust, which with commentary on their strengths and weaknesses.
has led some researchers to combine them with gradient- The significant characteristics of the primary methods
based methods (Poloni et al. 2000; Coverstone-Carroll are summarized in Table 1. Each approach is listed along
et al. 2000). Such hybrid approaches can reduce the com- with its corresponding subsection in the survey. It is in-
putational burden of the genetic algorithms. dicated whether or not the method is a scalarization
An attractive feature of multi-objective genetic algo- method and whether or not the method requires a utopia
rithms is the use of a population of potential solution point. In many instances, determining a utopia point is
points, which is similar to the idea of a Pareto optimal set. optional, because it is potentially expensive. However,
However, Pareto optimality is not a concept embedded in for the sake of consistent comparison, it is assumed that
the fundamentals of genetic algorithms. It has no obvi- when possible, the utopia point is used, as this typic-
ous correlation to the natural origins of genetic methods. ally improves the quality of the solutions. It is indicated
Consequently, it is possible with certain multi-objective whether or not each method provides a necessary and/or
genetic algorithms that a Pareto optimal solution may sufficient condition for Pareto optimality. If a particular
be born and then, by chance, die out. This is typically formulation is neither necessary nor sufficient for Pareto
avoided by independently storing Pareto optimal solu- optimality, or if it is unknown whether a formulation is
tions as they arise. In fact, the use of an approximate necessary or sufficient, then it is indicated whether or not
Pareto set is central to many multi-objective genetic al- determining Pareto optimal solutions is at all possible. A
gorithms. However, the non-domination checks that are “*” indicates caveats in classifications. For instance, min-
necessary to update an approximate Pareto set can be imizing the weighted global criterion shown in (9) and
expensive. Nonetheless, such checks are inherent in most (11), referred to as weighted global criterion II in the
ranking procedures, and devices such as Pareto-set filters table, is necessary for Pareto optimality. However, its per-
require additional checks. An elitist strategy, however, in- formance depends on the value of the exponent p, and it
corporates non-domination checks without ranking and does not provide a practical means of obtaining all of the
consequently can be less expensive. Pareto optimal points.
The Pareto fitness function and the tournament selec- The programming complexity (PC), software use
tion approach can be relatively efficient methods of incor- complexity (SUC), and computational complexity (CC)
porating into fitness a point’s non-dominated tendencies. are rated on a scale of zero to five, five being the most
However, in exchange for relative efficiency, such methods complex. Programming complexity refers to the process
do not involve an approximate Pareto set and run the of programming an algorithm, whereas software use com-
risk of having Pareto optimal solutions appear in one gen- plexity concerns the actual use of an algorithm once it has
eration and not in the next. Consequently, one has two been coded. Computational complexity provides a gen-
paradigms for genetic multi-objective optimization algo- eral indication of how demanding the algorithm is com-
rithms: 1) search for and store Pareto optimal points (sep- putationally. However, this is not a formal reflection of
arate from the general population) that surface with each efficiency or convergence properties. In fact, the efficiency
generation, or 2) have the general population develop di- of many of the methods depends on the number of objec-
rectly into an approximation of the Pareto optimal set. tive functions being evaluated and on the optimization
Methods that involve an approximate Pareto set, such as engine being used. The preference articulation potential
the elitist strategy in conjunction with the weighted sum, (PAP) indicates a method’s capacity for preference in-
tend to fall into the first paradigm (Ishibuchi and Murata formation, as discussed in Sect. 3.10. This characteristic
1996; Murata et al. 1996). Use of a Pareto fitness function, is also rated on a scale of zero to five, five indicating the
methods that incorporate ranking, and tournament selec- greatest capacity. All of the methods for a posteriori ar-
tion (with fitness sharing), tend to fall into the second ticulation receive a high score in this category, as the
 389

Table 1 Summary of primary methods

Survey Scalar Possible Necessary Sufficient Utopia PC SUC CC PAP

Section Method Pareto for for Point (0 to 5) (0 to 5) (0 to 5) (0 to 5)
Opt. Pareto Pareto
Opt. Opt.

Wtd. Global Critn. I 3.1 x F.W. x x 0 1 1 2

Wtd. Global Critn. II 3.1 x x* x x 0 1 1 2
A Priori Articulation

Weighted Sum 3.2 x x 0 1 0 1

of Preferences

Lexicographic 3.3 x 2 1 2 1
Weighted Min-Max 3.4 x x-weak x 1 1 2 1
Exponential Weighted 3.5 x x x 0 1 0 1
Weighted Product 3.6 x F.W. x 0 1 1 1
Goal Programming 3.7 x 1 1 2 1
Bounded Obj. Fnc. 3.8 x 1 1 1 1
Physical Programming 3.9 x x x 3 3 1 4
Articulation
A Posteriori

Physical Programming 4.1 x x x 4 1 – 5*

NBI 4.2 x x 2 1 – 5*
Normal Constraint 4.3 x x x 2 1 – 5*
Genetic 6.2 x 5 1 – 5*

Global Criterion 5.1

No Articulation

Achievement Fnc. 5.1 x x x 0 1 0 0

of Preferences

Compromise Fnc. 5.1 x x x 0 1 1 0

Objective Sum 5.1 x x 0 0 0 0
Min-Max 5.1 x x-weak x 1 0 2 0
Nash Arbitration 5.2 x F.W. x 0 1 1 0
Objective Product 5.2 x x x 0 0 1 0

decision-maker incorporates preferences exactly, by di- not available in the current literature. The symbol x-weak
rectly selecting a specific solution point. However, this indicates weak Pareto optimality.
is effective only with a limited number of objectives. Al-
though these ratings are subjective, they give a general
relative indication of performance. 7.2
In Table 1, the term genetic refers to genetic multi- Concluding remarks
objective algorithms. This approach receives a particu-
larly high rating for programming complexity, and this is
based on the assumption that it requires the development (1) In general, multi-objective optimization requires
of a new code. However, in recent years, some codes for more computational effort than single-objective
genetic multi-objective optimization have become avail- optimization. Unless preferences are irrelevant or
able on the Internet. Of course, the use of pre-existing completely understood, solution of several single-
codes reduces implementation complexity significantly. objective problems may be necessary to obtain an
Genetic algorithms can require one to set several heuristic acceptable final solution.
parameters and this process is not necessarily straight- (2) Solutions obtained with no articulation of prefer-
forward; it may require significant experience. However, ences are arbitrary relative to the Pareto optimal
some codes allow this process to be invisible to the user. set. In this class of methods, the objective sum
Then, genetic multi-objective algorithms are relatively method is one of the most computationally effi-
easy to use. cient, easy-to-use, and common approaches. Conse-
The symbol F.W. indicates that there is potential for quently, it provides a benchmark approach to multi-
future work. In such cases, classification of a method is objective optimization.
390

(3) Methods with a priori articulation of preferences re- Acknowledgements The authors would like to thank the re-
quire the user to specify preferences only in terms viewers of our paper for their insightful and helpful comments
of objective functions. Alternatively, methods with and suggestions.
a posteriori articulation of preferences allow the user
to view potential solutions in the criterion space
and/or in the design space, and to select an accept- References
able solution. Arora, J.S.; Elwakeil, O.A.; Chahande, A.I.; Hsieh, C.C. 1995:
(4) Selection of a specific scalarization method for a pri- Global optimization methods for engineering applications:
ori articulation of preferences, which allows one to a review. Struct. Optim. 9, 137–159
design a utility function, depends on the type of
preferences that the decision-maker wishes to artic- Athan, T.W.; Papalambros, P.Y. 1996: A note on weighted
criteria methods for compromise solutions in multi-objective
ulate and on the amount of preference-information
optimization. Eng. Optim. 27, 155–176
that the decision-maker has.
(5) The results of methods with a posteriori articulation Baier, H. 1977: Über Algorithmen zur Ermittlung und Charak-
of preferences, i.e. the Pareto optimal set, are typ- terisierung Pareto-optimaler Lösungen bei Entwurfsaufgaben
ically depicted in the criterion space. Consequently, Elastischer Tragwerke. Z. Angew. Math. Mech. 57, 318–320
much literature addresses the issue of providing an Belegundu, A.D.; Murthy, D.V.; Salagame, R.R.; Con-
even spread of points in the criterion space. This tans, E.W. 1994: Multi-objective optimization of laminated
is a consequence of the tendency to make decisions ceramic composites using genetic algorithms. In: 5th AIAA/
based on objectives or criteria. However, similar USAF/NASA/ISSMO Symposium on Multidisciplinary An-
points in the criterion space may correspond to dis- alysis and Optimization (held in Panama City Beach),
tinctly different points in the design space. Thus, pp. 1055–1022. Washington, DC: American Institute of Aero-
when possible, solutions in the design space should nautics and Astronautics
be used to complement solutions in the criterion Bendsoe, M.P.; Olhoff, N.; Taylor, J.E. 1984: A variational
space. formulation for multicriteria structural optimization.
(6) In terms of CPU time, methods with a posteri- J. Struct. Mech. 11, 523–544
ori articulation of preferences are less efficient than
methods with a priori articulation of preferences. Benson, H.P. 1978: Existence of efficient solutions for vector
maximization problems. J. Optim. Theory Appl. 26, 569–580
Since only one solution is selected, the time spent in
determining other Pareto optimal points is wasted. Ben-Tal, A.; Teboulle, M. 1989: A smooth technique for non-
In addition, regardless of the method being used, differentiable optimization problems. In: Dolecki, S. (ed.) Op-
presenting the Pareto optimal set clearly can be timization, Proceedings of the Fifth French-German Confer-
a formidable task. ence (held in Castel-Novel 1988), Lecture Notes in Mathemat-
(7) Genetic multi-objective algorithms provide a rela- ics, No. 1405, pp. 1–11. Berlin: Springer-Verlag
tively new approach for a posteriori articulation of Boychuk, L.M.; Ovchinnikov, V.O. 1973: Principal methods
preferences. Depending on the application, these for solution of multicriteria optimization problems (survey).
methods can be effective in obtaining the Pareto op- Sov. Autom. Control 6, 1–4
timal set.
(8) Most multi-objective optimization algorithms are Bridgman, P.W. 1922: Dimensional Analysis. New Haven:
Yale University Press
beholden to the efficiency of the optimization engine
(single-objective optimization algorithm). There- Brosowski, B.; da Silva, A.R. 1994: Simple tests for multi-
fore, it is important to select an efficient single- criteria optimality. OR Spektrum 16, 243–247
objective optimization algorithm and associated
software. Carmichael, D.G. 1980: Computation of Pareto optima in
structural design. Int. J. Numer. Methods Eng. 15, 925–952
(9) Even an approximate determination of utopia points
can be expensive, particularly when there are many Cavicchio, D.J. 1970: Adaptive Search Using Simulated Evo-
objective functions. If CPU time is an issue, utopia lution. Ph.D. Dissertation, University of Michigan, Ann Ar-
points should be avoided. Unattainable aspiration bor, MI
points provide a reasonable substitution.
Chankong, V.; Haimes, Y.Y. 1983: Multiobjective Decision
(10) Formulations that entail additional constraints, Making Theory and Methodology. New York: Elsevier Science
such as Tchebycheff methods, require additional Publishing
constraint gradients, which can be expensive. These
approaches should be avoided if CPU time is Charnes, A.; Clower, R.W.; Kortanek, K.O. 1967: Effective
limited. control through coherent decentralization with preemptive
(11) Vector methods, such as the lexicographic method, goals. Econometrica 35, 294–320
require the solution of a sequence of problems and Charnes, A.; Cooper, W.W. 1961: Management Models and
tend to require more CPU time than scalarization Industrial Applications of Linear Programming. New York:
methods. John Wiley and Sons
 391

Charnes, A.; Cooper, W.W. 1977: Goal programming and Dauer, J.P.; Krueger, R.J. 1980: A multiobjective optimiza-
multiple objective optimization; part 1. Eur. J. Oper. Res. tion model for water resources planning. Appl. Math. Model.
1, 39–54 4, 171–175

Charnes, A.; Cooper, W.W.; Ferguson, R.O. 1955: Optimal Dauer, J.P.; Stadler, W. 1986: A survey of vector optimization
estimation of executive compensation by linear programming. in infinite dimensional spaces, part II. J. Optim. Theory Appl.
Manage. Sci. 1, 138–151 51, 205–242

Chen, W.; Sahai, A.; Messac, A.; Sundararaj, G. 2000: Explo- Davis, L. (ed.) 1991: Handbook of Genetic Algorithms. New
ration of the effectiveness of physical programming in robust York: Van Nostrand Reinhold
design. J. Mech. Des. 122, 155–163
Davis, M.D. 1983: Game Theory, A Nontechnical Introduc-
Chen, W.; Wiecek, M.M.; Zhang, J. 1999: Quality utility tion. New York: Dover Publications
– a compromise programming approach to robust design.
J. Mech. Des. 121, 179–187 Deb, K. 1989: Genetic Algorithms in Multimodal Function Op-
timization. MS Thesis, TCGA Report No. 89002, University
Cheng, F.Y.; Li, D. 1996: Multiobjective optimization of of Alabama, Tuscaloosa, AL
structures with and without control. J. Guid. Control Dyn.
19, 392–397 Eckenrode, R.T. 1965: Weighting multiple criteria. Manage.
Sci. 12, 180–192
Cheng, F.Y.; Li, D. 1997: Multiobjective optimization design
with Pareto genetic algorithm. J. Struct. Eng. September, Elwakeil, O.A.; Arora, J.S. 1996: Two algorithms for global
1252–1261 optimization of general NLP problems. Int. J. Numer.
Methods Eng. 39, 3305–3325
Cheng, F.Y.; Li, D. 1998: Genetic algorithm development
Eschenauer, H.; Koski, J.; Osyczka, A. (eds.) 1990: Multicrite-
for multiobjective optimization of structures. AIAA J. 36,
ria Design Optimization Procedures and Applications. Berlin:
1105–1112
Springer-Verlag
Cheng, F.Y.; Li, X.S. 1998b: A generalized center method for
Fonseca, C.M.; Fleming, P.J. 1993: Genetic algorithms for
multiobjective optimization. In: Frangopol, D.M. (ed.) Op-
multiobjective optimization: formulation, discussion, and gen-
timal Performance of Civil Infrastructure Systems. Reston:
eralization. In: The Fifth International Conference on Genetic
American Society of Civil Engineers
Algorithms (held in Urbana-Champaign), pp. 416–423. San
Chiampi, M.; Fuerntratt, G.; Magele, C.; Ragusa, C.; Repet- Mateo: Morgan Kaufmann
to, M. 1998: Multi-objective optimization with stochastic
Gembicki, F.W. 1974: Performance and Sensitivity Optimiza-
algorithms and fuzzy definition of objective function. Int.
tion: A Vector Index Approach. Ph.D. Dissertation, Case
J. Appl. Electromagn. Mech. 9, 381–389
Western Research University, Cleveland, OH
Choo, E.-U.; Atkins, D.R. 1983: Proper efficiency in noncon-
Gen, M.; Cheng, R. 1997: Genetic Algorithms and Engineering
vex multicriteria programming. Math. Oper. Res. 8, 467–470
Design. New York: John Wiley and Sons
Cohon, J.L. 1978: Multiobjective Programming and Planning. Gen, M.; Liu, B. 1995: A Genetic Algorithm for Nonlinear
New York: Academic Press Goal Programming. Technical Report ISE95-5, Ashikaga In-
stitute of Technology, Ashikaga, Japan
Corley, H.W. 1980: A new scalar equivalence for Pareto opti-
mization. IEEE Trans. Autom. Control 25, 829–830 Geoffrion, A.M. 1968: Proper efficiency and the theory of vec-
tor maximization. J. Math. Anal. Appl. 22, 618–630
Coverstone-Carroll, V.; Hartmann, J.W.; Mason, W.J. 2000:
Optimal multi-objective low-thrust spacecraft trajectories. Gerasimov, E.N.; Repko, V.N. 1978: Multicriterial optimiza-
Comput. Methods Appl. Mech. Eng. 186, 387–402 tion. Sov. Appl. Mech. 14, 1179–1184; translated from Prik-
ladnaya Mekhanika 14, 72–78 (1978)
Das, I. 1999: An improved technique for choosing parameters
for Pareto surface generation using normal-boundary inter- Goicoechea, A.; Duckstein, L.; Fogel, M.M. 1976: Multiobjec-
section. In: ISSMO/UBCAD/AIASA, Third World Congress tive programming in watershed management: A case study of
of Structural and Multidisciplinary Optimization (held in Buf- the Charleston watershed. Water Resour. Res. 12, 1085–1092
falo). Buffalo: University of Buffalo, Center for Advanced
Design Goicoechea, A.; Hansen, D.R.; Duckstein, L. 1982: Multiobjec-
tive Decision Analysis with Engineering and Business Applica-
Das, I.; Dennis, J.E. 1997: A closer look at drawbacks of mini- tions. New York: John Wiley and Sons
mizing weighted sums of objectives for Pareto set generation
in multicriteria optimization problems. Struct. Optim. 14, Goldberg, D.E. 1989: Genetic Algorithms in Search, Opti-
63–69 mization and Machine Learning. Reading: Addison-Wesley

Das, I.; Dennis, J.E. 1998: Normal-boundary intersection: Goldberg, D.E.; Richardson, J.J. 1987: Genetic algorithms
a new method for generating the Pareto surface in nonlin- with sharing for multimodal function optimization. In: Ge-
ear multicriteria optimization problems. SIAM J. Optim. 8, netic Algorithms and Their Applications: Proceedings of
631–657 the Second International Conference on Genetic Algorithms
392

(held in Cambridge, MA), pp. 41–49. Hillsdale: L. Erlbaum on Evolutionary Computation (held in Nagoya), pp. 119–124.
Associates Piscataway: Institute of Electrical and Electronics Engineers

Goldberg, D.E.; Samtani, M.P. 1986: Engineering optimiza- Jendo, S.; Marks, W.; Thierauf, G. 1985: Multicriteria opti-
tion via genetic algorithm. In: Proceedings of the Ninth mization in optimum structural design. Large Scale Syst. 9,
Conference on Electronic Computation (held in Birming- 141–150
ham, AL), pp. 471–482. New York: American Society of Civil
Engineers Kaliszewski, I. 1985: A characterization of properly efficient
solutions by an augmented Tchebycheff norm. Bull. Pol.
Haimes, Y.Y.; Lasdon, L.S.; Wismer, D.A. 1971: On a bicrite- Acad. Sci., Tech. Sci. 33, 415–420
rion formulation of the problems of integrated system iden-
tification and system optimization. IEEE Trans. Syst. Man Kaliszewski, I. 1987: A modified Tchebycheff metric for multi-
Cybern. SMC-1, 296–297 ple objective programming. Comput. Oper. Res. 14, 315–323

Hallefjord, A.; Jornsten, K. 1986: An entropy target-point Kielb, R.E.; Kaza, K.R.V. 1983: Aeroelastic characteristics of
approach to multiobjective programming. Int. J. Syst. Sci. a cascade of mistuned blades in subsonic and supersonic flows.
17, 639–653 J. Vib. Acoust. Stress Reliab. Des. 105, 425–433

Haug, E.J.; Arora, J.S. 1979: Applied Optimal Design: Me- Kocer, F.Y.; Arora, J.S. 1999: Optimal design of H-frame
chanical and Structural Systems. New York: Wiley and Sons transmission poles for earthquake loading. J. Struct. Eng.
125, 1299–1308
Hillis, W.D. 1990: Co-evolving parasites improve simulated
evolution as an optimization procedure. Physica D 42, Koski, J. 1979: Truss Optimization with Vector Criterion.
228–234 Report Number 6, Tampere University of Technology, Tam-
pere, Finland
Hobbs, B.F. 1980: A comparison of weighting methods in
power plant siting. Decis. Sci. 11, 725–737 Koski, J. 1980: Truss Optimization with Vector Criterion, Ex-
amples. Report Number 7, Tampere University of Technol-
Holland, J.H. 1975: Adaptation in Natural and Artificial Sys- ogy, Tampere, Finland
tems. Ann Arbor: The University of Michigan Press
Koski, J. 1984: Multicriterion optimization in structural de-
Horn, J.; Nafpliotis, N.; Goldberg, D.E. 1994: A niched Pareto sign. In: Atrek, E.; Gallagher, R.H.; Ragsdell, K.M.; Zienkie-
genetic algorithm for multiobjective optimization. In: The wicz, O.C. (eds.) New Directions in Optimum Structural De-
First IEEE Conference on Evolutionary Computation (held sign, pp. 483–503. New York: John Wiley and Sons
in Orlando), pp. 82–87. Piscataway: IEEE Neural Networks
Council Koski, J. 1985: Defectiveness of weighting method in multi-
criterion optimization of structures. Commun. Appl. Numer.
Husbands, P. 1994: Distributed coevolutionary genetic algo- Methods 1, 333–337
rithms for multi-criteria and multi-constraint optimization.
In: Fogarty, T.C. (ed.) Evolutionary Computing (Selected pa- Koski, J. 1988: Multicriteria truss optimization. In: Stad-
pers from AISB workshop, Leeds, UK), pp. 150–165. Berlin: ler, W. (ed.) Multicriteria Optimization in Engineering and in
Springer-Verlag the Sciences. New York: Plenum Press

Hwang, C.-L.; Lai, Y.-J.; Liu, T.-Y. 1993: A new approach Koski, J.; Silvennoinen, R. 1987: Norm methods and partial
for multiple objective decision making. Comput. Oper. Res. weighting in multicriterion optimization of structures. Int. J.
20, 889–899 Numer. Methods Eng. 24, 1101–1121

Hwang, C.-L.; Md. Masud, A.S., in collaboration with Pai- Kuhn, H.W.; Tucker, A.W. 1950: Nonlinear programming. In:
dy, S.R. and Yoon, K. 1979: Multiple objective decision mak- Neyman, J. (ed.) The Second Berkley Symposium on Math-
ing, methods and applications: a state-of-the-art survey. In: ematical Statistics and Probability (held in Berkley 1951),
Beckmann, M.; Kunzi, H.P. (eds.) Lecture Notes in Eco- pp. 481–492. Berkley: University of California Press
nomics and Mathematical Systems, No. 164 . Berlin: Springer-
Verlag Kursawe, F. 1991: A variant of evolution strategies for vector
optimization. In: Schwefel, H.-P.; Manner, R. (eds.) Parallel
Hwang, C.-L.; Yoon, K. 1981: Multiple attribute decision Problem Solving from Nature. Berlin: Springer-Verlag
making methods and applications: a state-of-the-art survey.
In: Beckmann, M.; Kunzi, H.P. (eds.) Lecture Notes in Eco- Lee, S.M.; Olson, D.L. 1999: Goal programming. In: Gal, T.;
nomics and Mathematical Systems, No. 186 . Berlin: Springer- Stewart, T.J.; Hanne, T. (eds.) Multicriteria Decision Mak-
Verlag ing: Advances in MCDM Models, Algorithms, Theory, and Ap-
plications. Boston: Kluwer Academic Publishers
Ichida, K.; Fujii, Y. 1990: Multicriterion optimization using
interval analysis. Comput. 44, 47–57 Leitmann, G. 1977: Some problems of scalar and vector-
valued optimization in linear viscoelasticity. J. Optim. Theory
Ijiri, Y. 1965: Management Goals and Accounting for Control . Appl. 23, 93–99
Amsterdam: North-Holland
Leu, S.-S.; Yang, C.-H. 1999: GA-based multicriteria optimal
Ishibuchi, H.; Murata, T. 1996: Multi-objective genetic local model for construction scheduling. J. Constr. Eng. Manage.
search algorithm. In: 1996 IEEE International Conference 125, 420–427
 393

Li, X.S. 1992: An entropy-based aggregate method for mini- Murata, T.; Ishibuchi, H.; Tanaka, H. 1996: Multi-objective
max optimization. Eng. Optim. 18, 277–285 genetic algorithm and its applications to flowshop scheduling.
Comput. Ind. Eng. 30, 957–968
Lin, J.G. 1976: Multiple-objective problems: Pareto-optimal
solutions by method of proper equality constraints. IEEE Narayana, S.; Azarm, S. 1999: On improving multiobjective
Trans. Autom. Control AC-21, 641–651 genetic algorithms for design optimization. Struct. Optim. 18,
146–155
Majid, K.I. 1974: Optimal Design of Structures. London: But-
terworths Nash, J. 1950: The bargaining problem. Econometrica 18,
155–162
Mansfield, E. 1985: Microeconomics Theory/Applications, 5th
edn. New York: W.W. Norton Ogryczak, W. 1994: A goal programming model of the refer-
ence point method. Ann. Oper. Res. 51, 33–44
Marler, R.T.; Arora, J.S. 2003: Review of Multi-Objective Op-
timization Concepts and Methods for Engineering. Technical Osyczka, A. 1978: An approach to multicriterion optimiza-
Report Number ODL-01.01, University of Iowa, Optimal De- tion problems for engineering design. Comput. Methods Appl.
sign Laboratory, Iowa City, IA Mech. Eng. 15, 309–333

Martinez, M.P.; Messac, A.; Rais-Rohani, M. 2001: Manufac- Osyczka, A. 1981: An approach to multicriterion optimization
turability-based optimization of aircraft structures using for structural design. In: International Symposium on Opti-
physical programming. AIAA J. 39, 517–525 mal Structural Design: 11th ONR Naval Structural Mechanics
Symposium (held in Tucson), pp. 10.37–10.40. Tucson: Uni-
Mazumdar, R.; Mason, L.G.; Douligeris, C. 1991: Fairness in versity of Arizona
network optimal flow control: optimality of product forms.
IEEE Trans. Commun. 39, 775–782 Osyczka, A. 1984: Multicriterion Optimization in Engineering
with Fortran Programs. New York: John Wiley and Sons
Messac, A. 1996: Physical programming: effective optimiza-
tion for computational design. AIAA J. 34, 149–158 Osyczka, A. 1985: Computer aided multicriterion optimiza-
tion method. Adv. Model. Simul. 3, 41–52
Messac, A. 2000: From dubious construction of objective func-
tions to the application of physical programming. AIAA J. Osyczka, A.; Kundu, S. 1996: A modified distance method for
38, 155–163 multicriteria optimization, using genetic algorithms. Comput.
Ind. Eng. 30, 871–882
Messac, A.; Hattis, P. 1996: Physical programming design op-
timization for high speed civil transport (HSCT). J. Aircr. Pareto, V. 1906: Manuale di Economica Politica, Societa Ed-
33, 446–449 itrice Libraria. Milan; translated into English by A.S. Schwier
as Manual of Political Economy, edited by A.S. Schwier and
Messac, A.; Ismail-Yahaya, A.; Mattson, C.A. 2003: The nor- A.N. Page, 1971. New York: A.M. Kelley
malized normal constraint method for generating the Pareto
frontier. Struct. Multidisc. Optim. 25, 86–98 Poloni, C.; Giurgevich, A.; Onesti, L.; Pediroda, V. 2000: Hy-
bridization of a multi-objective genetic algorithm, a neural
Messac, A.; Mattson, C.A. 2002: Generating well-distributed network, and a classical optimizer for a complex design prob-
sets of Pareto points for engineering design using physical pro- lem in fluid dynamics. Comput. Methods Appl. Mech. Eng.
gramming. Optim. Eng. 3 431–450 186, 403–420

Messac, A.; Puemi-Sukam, C.; Melachrinoudis, E. 2001: Math- Proos, K.A.; Steven, G.P.; Querin, O.M.; Xie, Y.M. 2001:
ematical and pragmatic perspectives of physical program- Multicriterion evolutionary structural optimization using the
ming. AIAA J. 39, 885–893 weighted and the global criterion methods. AIAA J. 39,
2006–2012
Messac, A.; Sukam, C.P.; Melachrinoudis, E. 2000a: Aggre-
gate objective functions and Pareto frontiers: required rela- Psarras, J.; Capros, P.; Samouilidis, J.-E. 1990: Multiobjec-
tionships and practical implications. Optim. Eng. 1, 171–188 tive programming. Energy 15, 583–605

Messac, A.; Sundararaj, G.J.; Tappeta, R.V.; Renaud, J.E. Rao, J.R.; Roy, N. 1989: Fuzzy set theoretic approach of as-
2000b: Ability of objective functions to generate points on signing weights to objectives in multicriteria decision making.
nonconvex Pareto frontiers. AIAA J. 38, 1084–1091 Int. J. Syst. Sci. 20, 1381–1386

Messac, A.; Wilson, B. 1998: Physical programming for com- Rao, S.S. 1987: Game theory approach for multiobjective
putational control. AIAA J. 36, 219–226 structural optimization. Comput. Struct. 25, 119–127

Messac, A.; Van Dessel, S.; Mullur, A.A.; Maria, A. 2004: Op- Rao, S.S.; Freiheit, T.I. 1991: A modified game theory ap-
timization of large scale rigidified inflatable structures for proach to multiobjective optimization. J. Mech. Des. 113,
housing using physical programming. Struct. Multidisc. Op- 286–291
tim. 26, 139–151
Rao, S.S.; Hati, S.K. 1980: Optimum design of shock and vi-
Miettinen, K. 1999: Nonlinear Multiobjective Optimization. bration isolation systems using game theory. Eng. Optim.
Boston: Kluwer Academic Publishers 4, 215–226
394

Rao, S.S.; Venkayya, V.B.; Khot, N.S. 1988: Game theory ap- nomics and Mathematical Systems, No. 294, pp. 3–25. Berlin:
proach for the integrated design of structures and controls. Springer-Verlag
AIAA J. 26, 463–469
Stadler, W. 1988: Fundamentals of multicriteria optimization.
Rentmeesters, M.J.; Tsai, W.K.; Lin, K.-J. 1996: A theory of In: Stadler, W. (ed.) Multicriteria Optimization in Engineer-
lexicographic multi-criteria optimization. In: Second IEEE In- ing and in the Sciences, pp. 1–25. New York: Plenum Press
ternational Conference on Engineering of Complex Computer
Systems (held in Montreal), pp. 76–79. Los Alamitos: IEEE Stadler, W. 1995: Caveats and boons of multicriteria opti-
Computer Society Press mization. Microcomput. Civ. Eng. 10, 291–299
Richardson, J.T.; Palmer, M.R.; Liepins, G.; Hilliard, M. 1989: Stadler, W.; Dauer, J.P. 1992: Multicriteria optimization in
Some guidelines for genetic algorithms with penalty func- engineering: a tutorial and survey. In: Kamat, M.P. (ed.)
tions. In: Schaffer, J.D. (ed.) Third International Conference Structural Optimization: Status and Promise, pp. 211–249.
on Genetic Algorithms (held in Arlington), pp. 191–197. San Washington, DC: American Institute of Aeronautics and
Mateo: Morgan Kaufmann Astronautics
Romero, C.; Tamiz, M.; Jones, D.F. 1998: Goal programming,
compromise programming and reference point method formu- Steuer, R.E. 1989: Multiple Criteria Optimization: The-
lations: linkages and utility interpretations. J. Oper. Res. Soc. ory, Computation, and Application. Malabar: Robert E. Krie-
49, 986–991 ger Publishing

Roy, B.; Vincke, P. 1981: Multicriteria analysis: survey and Steuer, R.E.; Choo, E.-U. 1983: An interactive weighted
new directions. Eur. J. Oper. Res. 8, 207–218 Tchebycheff procedure for multiple objective programming.
Math. Program. 26, 326–344
Ruiz-Canales, P.; Rufian-Lizana, A. 1995: A characterization
of weakly efficient points. Math. Program. 68, 205–212 Straffin, P.D. 1993: Game Theory and Strategy. Washing-
ton, DC: The Mathematical Association of America
Saaty, T.L. 1977: A scaling method for priorities in hier-
archies, multiple objectives and fuzzy sets. J. Math. Psych. Tind, J.; Wiecek, M.M. 1999: Augmented Lagrangian and
15, 234–281 Tchebycheff approaches in multiple objective programming.
J. Global Optim. 14, 251–266
Salukvadze, M.E. 1971a: Optimization of vector function-
als, I, programming of optimal trajectories. Avtomatika i Tele- Torn, A.A.; Zilinskas, A. 1987: Global optimization. In:
mekhanika 8, 5–15 (in Russian) Goos, G.; Hartmanis, J. (eds.) Lecture Notes in Economics
Salukvadze, M.E. 1971b: Optimization of vector function- and Mathematical Systems, No. 350 . Berlin: Springer-Verlag
als, II, the analytic construction of optimal controls. Av-
tomatika i Telemekhanika 9, 5–15 (in Russian) Tseng, C.H.; Lu, T.W. 1990: Minimax multiobjective opti-
mization in structural design. Int. J. Numer. Methods Eng.
Salukvadze, M.E. 1979: Vector-Valued Optimization Problems 30, 1213–1228
in Control Theory. New York: Academic Press
Vasarhelhi, A.; Logo, J. 1986: Design of steel frames by multi-
Schaffer, J.D. 1985: Multiple objective optimization with vec- criterion optimization. Acta Tech. (Budapest) 99, 413–418
tor evaluated genetic algorithms. In: The First International
Conference on Genetic Algorithms and their Applications Vincent, T.L. 1983: Game theory as a design tool. ASME
(held in Pittsburgh), pp. 93–100. Hillsdale: Lawrence Erl- J. Mech. Transm. Autom. Des. 105, 165–170
baum Associates
Vincent, T.L.; Grantham, W.J. 1981: Optimality in Paramet-
Schaumann, E.J.; Balling, R.J.; Day, K. 1998: Genetic algo- ric Systems. New York: John Wiley and Sons
rithms with multiple objectives. In: Seventh AIAA/
USAF/NASA/ISSMO Symposium on Multidisciplinary An- Voogd, H. 1983: Multicriteria Evaluation for Urban and Re-
alysis and Optimization (held in St. Louis), pp. 2114–2123. gional Planning. London: Pion
Washington, DC: American Institute of Aeronautics and
Astronautics Waltz, F.M. 1967: An engineering approach: hierarchical op-
timization criteria. IEEE Trans. Autom. Control AC-12,
Srinivas, N.; Deb, K. 1995: Multiobjective optimization using 179–180
nondominated sorting in genetic algorithms. Evol. Com-
put.2, 221–248 Wendell, R.E.; Lee, D.N. 1977: Efficiency in multiple objective
Stadler, W. 1977: Natural structural shapes of shallow arches. optimization problems. Math. Program. 12, 406–414
J. Appl. Mech. 44, 291–298
Wierzbicki, A.P. 1982: A mathematical basis for satisficing de-
Stadler, W. 1978: Natural strutural shapes (the static case). cision making. Math. Model. 3, 391–405
Q. J. Mech. Appl. Math. 31, 169–217
Wierzbicki, A.P. 1986: A methodological approach to compar-
Stadler, W. 1987: Initiators of multicriteria optimization. In: ing parametric characterizations of efficient solutions. In: Fan-
Jahn, J.; Krabs, W. (eds.) Recent Advances and Historical del, G.; Grauer, M.; Kurzhanski, A.; Wierzbicki, A.P. (eds.)
Development of Vector Optimization, Lecture Notes in Eco- Large-Scale Modeling and Interactive Decision Analysis, Lec-
 395

ture Notes in Economics and Mathematical Systems, No. 273, Yu, P.-L. 1985: Multiple-Criteria Decision Making Con-
pp. 27–45. Berlin: Springer-Verlag cepts, Techniques, and Extensions. New York: Plenum Press

Yoon, K.P. 1980: System Selection by Multiple Attribute De- Yu, P.-L.; Leitmann, G. 1974: Compromise solutions, domina-
cision Making. Ph.D. Dissertation, Kansas State Univer- tion structures, and Salukvadze’s solution. J. Optim. Theory
sity, Manhattan, KS Appl. 13, 362–378

Zadeh, L.A. 1963: Optimality and non-scalar-valued perform-

Yoon, K.P; Hwang, C.-L. 1995: Multiple Attribute Decision
ance criteria. IEEE Trans. Autom. Control AC-8, 59–60
Making, An Introduction. London: Sage Publications
Zeleny, M. 1982: Multiple Criteria Decision Making. New
Yu, P.-L. 1973: A class of solutions for group decision prob- York: McGraw Hill
lems. Manage. Sci. 19, 936–946
Zionts, S. 1988: Multiple criteria mathematical programming:
Yu, P.-L. 1974: Cone convexity, cone extreme points, and non- an updated overview and several approaches. In: Mitra, G.
dominated solutions in decision problems with multiobjec- (ed.) Mathematical Models for Decision Support, pp. 135–167.
tives. J. Optim. Theory Appl. 14, 319–377 Berlin: Springer-Verlag

View publication stats